1、Alterra中文資資料FPGA在在軟件無線線電中的應應用介紹軟件無線電（SDR）是具有可重配置硬件平臺的無線設備，可以跨多種通信標準。它們因為更低的成本、更大的靈活性和更高的性能，迅速稱為軍事、公共安全和商用無線領域的事實標準。SDR成為商用流行的主要原因之一是它能夠對多種波形進行基帶處理和數字中頻（IF）處理。IF處理將數字信號處理的領域從基帶擴展到RF。支持基帶和中頻處理的能力增加了系統靈活性，同時減小了制造成本。基帶處理無線標準不斷地發展，通過先進的基帶處理技術如自適應調制編碼、空時編碼（STC）、波束賦形和多入多出（MIMO）天線技術，支持更高的數據速率。基帶信號處理器件需要巨大的處

2、理帶寬，以支持這些技術中大計算量的算法。例如，美國軍事聯合戰術無線系統（JTRS）定義了軍事無線中20多種不同的無線波形。一些更復雜的波形所需的計算能力在標準處理器上是每秒數百萬條指令（MIPS），或者如果在FPGA實現是數千個邏輯單元。協處理器特性SDR基帶處理通常需要處理器和FPGA。在這類應用中，處理器處理系統控制和配置功能，而FPGA實現大計算量的信號處理數據通道和控制，讓系統延遲最小。當需要從一種標準切換至另一種標準時，處理器能夠動態地在軟件的主要部分間切換，而FPGA能夠根據需要完全重新配置，實現特定標準的數據通道。FPGA可以作為協處理器同DSP和通用處理相連，這樣具有更高的系統

3、性能和更低的系統成本。自由地選擇在哪實現基帶處理算法為實現SDR算法提供了另一種方式的靈活性。 基帶部件也需要足夠靈活讓所需的SDR功能支持在同一種標準增強版本之間的移植，并能夠支持完全不同的標準。可編程邏輯結合軟核處理器和IP，具有了提供在現場遠程升級的能力。圖1 是一個框圖，其中FPGA能夠通過IP功能如Turbo編碼器、Reed-Solomon編碼器、符號交織器、符號映射器和IFFT，很容易地重配置支持WCDMA/HSPDA或802.16a標準的基帶發送功能。 圖1. 兩種無線信號的SDR基帶數據通道重配置例子數字IF處理數字頻率變化具有比傳統模擬無線處理方式更高的性能。FPGA提供了一

4、種高度靈活和集成的平臺，在這之上以合理的功率實現大計算量的數字IF功能，這在便攜系統中是一個關鍵的因素。能夠在FPGA實現的IF功能包括數字上變頻器（DUC）和下變頻器（DDC），以及數字預畸變（DPD）和波峰系數削減（CFR），幫助降低功放的成本和功率（見圖2）1. DUC:數字上變頻器 2. CFR: 波峰系數削減 3. DPD: 數字預畸變 4. DDC: 數字下變頻器 5. PA: 功放 6. LNA: 低噪放 圖2. 在SDR架構中中頻處理單元例子數字上變頻器數字格式（在基帶處理單元和上變頻器之間一般需要）可以順利地加到上變頻器的前端。這項技術為上變頻器提供了全定制的前端，容許信道化

5、的高帶寬輸入數據。定制邏輯或軟核嵌入式處理器可用來控制上變頻器和FPGA中實現的基帶處理單元之間的接口。在數字上變頻中，輸入數據在用可調的載波頻率進行正交調制之前經過基帶濾波和插值。為了實現插值基帶有限沖激響應（FIR）濾波器，必須在速度面積之間進行權衡為特定的標準獲得優化的固定或自適應架構。數控振蕩器核也能夠產生多種架構，它們具有超過115db無寄生動態范圍和非常的高性能。根據支持的頻率分配數量，在FPGA中可以很容易地例化多個上變頻器。波峰系數削減3G 基于CDMA的系統和多載波系統如正交頻分復用（OFDM）的信號具有很高的峰平比（波峰系數）。這樣的信號會極大地降低基站中功放的效率。對多波

6、形標準，在FPGA中實現的波峰系數削減技術是一種降低功放成本和復雜度的合算的方式。數字預畸變高速移動數據傳輸采用非恒包絡調制技術如QPSK和正交幅度調制（QAM）。這對PA的線性度有嚴格的要求。DPD線性化技術，包括查找表和多項式方式都可以有效地在包含DSP塊的FPGA中實現。這些DSP塊中的乘法器可以在很高的時鐘速率下運行，可以有效地分時實現復數乘法。當SDR基站中使用FPGA時，FPGA可以為特定的標準重配置來實現合適的DPD算法，有效地線性化PA。數字下變頻器在接收器側，數字IF技術可以對IF信號進行采樣，在數字域執行信道化和采樣率轉換。使用降采樣技術，高頻IF信號（同時100MHz以上

7、）可以被量化。因為不同的標準有不同的碼片/比特速率，對SDR應用需要非整數采樣率，把采樣數轉換為任何標準基本碼片/比特速率的整數倍。結論FPGA提供了通用的計算結構，非常適合于軟件無線電中基帶和IF數字處理的需要。另外，結合通用處理器或DSP，它們作為通用處理器或DSP軟件處理的硬件協處理器，能夠增強功能，改善吞吐量，減小系統成本和降低系統功率。作者：Joel A. SeelyTechnical Marketing ManagerAutomotive, Industrial and Military Business UnitAltera Corporation采用編譯增增強技術，提提高高密度

8、度FPGAA設計工作作效率現場可編程程門陣列（FPGA）體系創新以及向90nm工藝技術的過渡顯著提高了FPGA的密度和性能。FPGA設計人員不僅需要更高的邏輯密度和更快的性能表現，還要求具有嵌入式處理器、數字信號處理（DSP）模塊以及其他硬件IP結構等復雜的器件功能。但是，由于FPGA設計規模越來越大、越來越復雜，為了能夠抓住稍縱即逝的市場機會，設計人員必需盡快完成其設計。FPGA器器件供應商商一直努力力提高編譯譯時間效率率，改善時時序逼近流流程，但是是卻無法滿滿足設計人人員更高效效工作的要要求。Allteraa Quaartuss II軟件件5.0增強強編譯技術術明顯縮短短設計迭代代時間，在

9、在關鍵性能能通路上進進行設計優優化，保持持性能已達達到要求的的區域特性性不變，該該技術是前前所未有的的，極大的的提高了設設計效率。編譯增強優優勢現在的一個個高級FPPGA標準準編譯流程程包括RTTL綜合、布局布線線等，高密密度FPGGA的每次次設計編譯譯在任何情情況下都要要耗費455分鐘到4個多小時時的時間，這這顯然限制制了設計人人員每天所所能進行的的迭代次數數，可能會會少至兩次次，明顯減減緩了設計計過程。設設計人員采采用標準編編譯設計流流程來優化化部分設計計時序性能能時也會降降低設計效效率。這種種優化通常常不利于邏邏輯布局，影影響設計中中其他部分分的性能，不不得不進行行額外的多多次設計迭迭代

10、。對于當今的的高密度、高性能FFPGA設設計，必需具有有設計和調調試階段快快速迭代的的能力。Alteera QQuarttus III軟件5.00為高密度度FPGAA設計提供供了最先進進的技術，如如以前只有有專用集成成電路（AASIC）才才具有的增增強設計和和編譯能力力等。與相相應的ASSIC相比比，FPGGA編譯效效率更高，ASIC即使采用增強方法，仍需要幾小時到幾天的時間來完成編譯，而FPGA編譯只需要幾分鐘到幾小時的時間。設計人員采采用Quaartuss II增增強編譯技技術，可以以逐步編譯譯其設計分分區，比進進行全部設設計的標準準編譯時間間縮短近770%。性性能保留是是增強編譯譯技術的

11、另另一個主要要優勢。通通過只對設設計中的一一個分區進進行編譯，可可以保持其其他部分的的性能和結結果不變。這種性能能保留特性性使設計人人員能夠以以更少的設設計迭代，更更高效的達達到時序逼逼近 Quarrtus II 55.0編譯譯增強設計計流程。編譯增強使使設計人員員能夠以邏邏輯和物理理分區的形形式組織設設計，進行行綜合和適適配。只針針對特定設設計分區進進行新的編編譯，從而而能夠顯著著縮短設計計迭代時間間。編譯增增強特性有有助于基于于模塊的設設計，對沒沒有修改的的設計模塊塊，保持其其性能不變變。設計人人員還可以以只對特定定設計分區區采用物理理綜合等優優化技術，而而不改動其其他模塊。傳統上，一一個

12、層次設設計在進行行邏輯綜合合和適配之之前轉換為為單一的網網表，每修修改一次設設計，就要要對整個設設計進行重重新編譯，減減緩了設計計過程。而而編譯增強強特性使設設計人員能能夠沿任意意層次邊界界劃分設計計分區。采采用Alttera Quarrtus II軟件件，可分別別對不同的的層次設計計分區進行行綜合和適適配。分區區可以組合合、合并形形成網表后后，進入后后面的Quuartuus III編譯流程程。重新編編譯設計時時，設計人人員可以為為每個分區區選擇使用用新的源代代碼、后綜綜合結果以以及后適配配結果。編譯增強設設計流程Quarttus III編譯增增強特性改改善了標準準Quarrtus II設計計

13、流程，使使設計人員員能夠重新新使用、保保留前次編編譯結果，節節省編譯時時間。在一一個標準設設計流程中中，源代碼碼完成后，如如果修改設設計中的任任何部分，設設計都要重重新進行編編譯，處理理源代碼，布布局所有邏邏輯。采用用這種方法法的原因之之一在于能能夠得到質質量最佳的的結果。通通過處理全全部設計，編編譯器能夠夠進行全局局優化，改改善面積大大小，提高高性能。但但是，對于于有些情況況，需要采采用增強編編譯設計流流程。當選選好設計中中的一個分分區，并在在器件平面面布置中進進行布局后后，設計人人員可以加加速其設計計編譯時間間，而保持持結果質量量不變，甚甚至提高結結果質量。設計人員可可能希望在在設計主體體

14、完成后，在在設計后期期修改或優優化一個特特定模塊時時，采用編編譯增強技技術。在這這種情況下下，他們可可以保持沒沒有改動的的模塊性能能不變，縮縮短后面迭迭代的編譯譯時間。編編譯增強特特性在有些些情況下，能能夠同時有有利于縮短短編譯時間間和達到時時序逼近。設計中有有些分區丟丟失或不完完整時，該該特性還可可以用于對對其他分區區進行編譯譯和優化。設計分區和和設計層次次通常的設計計實踐是生生成模塊化化或層次化化的設計，對對實體分別別進行設計計，然后在在高級工程程中例化，形形成一個完完整的設計計。編譯增增強技術對對設計中的的每個實體體不自動處處理為設計計分區；設設計人員必必需在該工工程頂層以以下，指定定一

15、個或多多個層次。生成分區區使編譯器器不對整個個分區邊界界進行優化化，但仍可可以通過對對每個分區區分別進行行綜合和布布局，來實實現編譯增增強技術。 層次設設計使邊界界獨立的分分區能夠采采用編譯增增強技術。由于分區必必需由層次次化的邊界界進行隔離離，因此分分區無法成成為一個層層次化實體體中邏輯的的一部分。形成一個個分區后，該該分區內的的每個層次次化實體成成為同一分分區的組成成。設計人人員能夠在在一個已有有分區中，為為該層次化化實體生成成新的分區區，在這種種情況下，新新分區中的的實體不再再是更高級級別分區的的組成部分分。設計分區和和物理區域域編譯增強特特性的設計計分區為邏邏輯分區，有有別于器件件平面

16、布置置圖中的物物理區域，在在平面布置置圖中，對對大小和位位置進行了了規定。一一個邏輯設設計分區不不是指器件件的物理部部分，不用用于直接控控制邏輯布布局。一個邏輯設設計分區在在設計層次次之間建立立一個虛擬擬邊界，因因此每個分分區分別進進行編譯，彼彼此之間不不會發生邏邏輯優化。在采用編編譯增強技技術建立設設計時，建建議設計人人員將每個個設計分區區分配給一一個物理區區域，來提提高結果質質量。生成設計分分區的建議議設計人員規規劃設計時時，應牢記記每個分區區的大小和和范圍，以以及設計中中的不同部部分在設計計過程中會會怎樣變化化。由于采采用分區時時，不會出出現交叉邊邊界優化，設設計結果質質量以及性性能會隨

17、著著分區數量量的增加而而下降。因因此，盡管管更多的分分區能夠更更大的縮短短編譯時間間，設計人人員還是應應該限制分分區數量，防防止結果質質量下降。在ASICC設計流程程中，設計計人員要記記錄每個分分區的輸入入和輸出端端口，盡可可能避免越越過分區邊邊界的任何何時延。此此外，設計計人員應盡盡量減少越越過分區邊邊界的通路路數量，以以簡化時序序逼近處理理，也應盡盡可能以時時鐘域來劃劃分區域。生成設計平平面布置圖圖一旦完成設設計分區后后，設計人人員應在器器件中為每每個分區分分配一個物物理位置。分區設計計生成平面面布置圖的的最簡單辦辦法是對每每個分區（包包括頂層分分區）生成成一個物理理位置約束束。對于采用編

18、編譯增強的的設計而言言，平面布布置圖位置置規劃非常常重要，這這是因為當當器件中某某個區域的的多數資源源已經占用用時，它可可以幫助避避免適配器器向該區域域放置或替替換部分設設計。在這這種情況下下，其他分分區的后適適配網表布布局迫使適適配器在器器件的空閑閑部分放置置新的或修修改后的分分區。這樣樣做會直接接導致兩個個不利結果果。第一，由由于物理約約束的數量量增多，適適配器必需需全速運轉轉，因此編編譯時間明明顯延長。第二，由由于目標分分區的布局局分散在器器件中，因因此結果質質量會下降降，有時甚甚至非常顯顯著。 帶帶有位置分分配的典型型器件平面面布置圖。 不帶帶有位置分分配的典型型器件平面面布置圖。利用

19、Quaartuss II早早期時序估估算器的優優勢早期時序估估算器不必必進行完整整的設計編編譯，即可可提供準確確的設計時時序估算。估算結果果平均在實實際設計性性能的111以內。設計人員員可以采用用時序逼近近平面布置置圖編輯器器來查看該該功能生成成的“布局估算算”，識別出出關鍵通路路，根據需需要加入或或修改平面面布置圖約約束。然后后，早期時時序估算器器能夠迅速速評估平面面布置圖位位置分配或或邏輯修改改的效果，對對設計變量量進行快速速迭代，幫幫助設計人人員找到最最佳方案。分區和平面面布置圖方方案成功的的關鍵設計人員在在為結果生生成平面布布置圖位置置分配之前前，應對結結果進行比比較，如果果不能符合合

20、以下準則則，應考慮慮采用其他他方案： 在在設計分區區完成和生生成平面布布置圖位置置分配之后后，不應觀觀察到fMAX劣化化。在許多多情況下，允允許fMAX略有有增加。 在設計分分區完成和和生成平面面布置圖位位置分配之之后，面積積增加不應應超過5。 布布線階段花花費的時間間不應明顯顯增加。如如果布線時時間明顯增增加，平面面布置圖位位置分配可可能產生了了大量的布布線擁塞。為幫助修改改和優化每每個分區的的位置分配配，設計人人員可采用用Quarrtus II軟件件的時序逼逼近平面布布置圖來確確定布線擁擁塞的區域域。結論Alterra Quuartuus III編譯增強強技術顯著著縮短了設設計迭代時時間，

21、其性能保保留特性是是前所未有有的，極大大的提高了了設計人員員工作效率率。設計人人員采用該該技術每天天能夠進行行4至5次的高密密度FPGGA設計迭迭代，而采采用傳統編編譯方法只只能進行11至2次迭代，設設計迭代時時間減少近近70%，明明顯縮短了了全部開發發時間。編編譯增強特特性實現的的性能保留留功能使設設計人員能能夠以更少少的設計迭迭代，更高高效的達到到時序逼近近復用器重構構降低FPPGA成本本摘要本文介紹了了一種新的的能夠降低低FPGAA實際設計計20成本本的綜合算算法。該算算法通過減減少復用器器所需查找找表（LUUT）的數數量來實現現。算法以以效率更高高的4:11復用器替替代2:11復用器樹

22、樹。算法性性能關鍵在在于尋找總總線上出現現的復用器器數量。新新的優化方方法占用一一定的邏輯輯，這些邏邏輯由總線線進行分擔擔，從而減減少了總線線上每個比比特位所需需的邏輯。關鍵詞FPGA、復用器、重構、重重新編碼、總線、邏邏輯優化、綜合。1. 引言言復用器是數數據通道常常用的構建建模塊，被被廣泛應用用在處理器器1、處處理器總線線、網絡交交換，甚至至是資源共共享的DSSP設計中中。據估計計，復用器器一般要占占用一個FFPGA設設計2 25%以上的面面積。因此此，優化FFPGA設設計的關鍵鍵在于怎樣樣優化復用用器。本文介紹了了一種新的的復用器重重構算法，該該算法減小小了復用器器在基于44輸入查找找表

23、（4-LUT）FPGAA體系結構構中所占用用的面積。基準測試試結果表明明復用器平平均減少了了17%，在在一些設計計中，4-LUT整整體減少220%。2.1節闡闡述了復用用器是如何何由行為級級VHDLL4或或Veriilog5代碼碼產生的，2.2和2.3節闡述復用器樹和復用器總線在設計中是怎樣生成的。2.4節說明這些結構怎樣由4-LUT實現，闡述如何采用兩個4-LUT有效實現一個4:1二進制復用器。第 REF _Ref97560363 r h * MERGGEFORRMAT 3節介紹了了一種叫做做壓縮的新新技術，該該技術附加加一些控制制邏輯，將將多個2:1復用器器重新組合合為有效的的4:1復用用

24、器，從而而減少了為為總線上每每一個比特特位實現復復用器所需需要的4-LUT數數量，所附附加的控制制邏輯代價價由整個總總線來分擔擔。優化復復用器總線線是復用器器重構算法法的核心。4.1節闡闡述復用器器重構算法法如何構建建設計中的的復用器樹樹總線。 REF _Ref97605769 r h * MMERGEEFORMMAT 44.2節的的重構方法法用于執行行 REF _Ref97605782 r h * MERGGEFORRMAT 4.3節中中定義的均均衡算法。均衡增加加了由壓縮縮生成的有有效4:11復用器的的數量。第5節總結結了在Allteraa Quaartuss II集集成綜合中中運行的整整

25、個算法。第 REF _Ref97605805 r h * MERRGEFOORMATT 6節列出了了來自1220個Alteera真實實用戶設計計實例的基基準測試結結果，測試試表明面積積減少超過過20%，平平均節省了了4.2%。2. 背景景知識2.1 復復用器在設設計中是怎怎樣實現的的行為級HDDL設計中中的任何條條件代碼通通常會綜合合為復用器器。本節闡闡述兩個最最常用的復復用器生成成代碼實例例。圖1是VHHDL的casee聲明及其其2:1復用用器樹的實實現。采用用Veriilog casee聲明的“paraallell casse”指令5可產生相相似的結果果。注意，并不不是所有的的casee聲

26、明將可可能的事件件都描述清清楚，需要要依靠“defaault”或者“otheers”條件來進進一步說明明。在這些些情況下，可可以繼續將將casee聲明表征征為2:11復用器樹樹，但是這這種樹結構構可能達不不到平衡。 REF _Ref87828357 h * MMERGEEFORMMAT 圖圖2顯示了“if-thhen-eelse”聲明是怎怎樣產生一一個2:11復用器鏈鏈的。Veriilog的的“?:”和非平行行casees可同樣產產生相似的的結構。注注意，復用用器鏈確保保如果第一一個if條件為為“真”，將選擇擇“a”數據輸入入，而復用用器其他部部分將被忽忽略。本文闡述的的復用器重重構算法應應用

27、于2:1復用器器。綜合工工具由行為為級代碼開開始通常會會生成較大大的復用器器。較大的的復用器總總是被分解解為2:11復用器樹樹，如何實實現這種分分解已經超超出本文討討論范圍。2.2 復復用器樹設計中復用用器之間的的饋入是常常見的現象象。例如，在一段HDDL代碼中中，如下面面的 REF _Ref88915488 h * MERGEFORMAT * MERRGEFOORMATT 圖3所示，iff-theen-ellse聲明明中含有ccase聲聲明就會產產生這種現現象。在復用器重重構算法中中，識別出出較大的復復用器樹對對于盡可能能減少面積積是非常重重要的。2.3 復復用器總線線VHDL信信號或Vee

28、riloog線寬通通常會超過過一個比特特位。當采采用if-thenn-elsse和casee聲明時，將將會生成大大量具有不不同數據輸輸入的相同同復用器樹樹，圖4是一個實實例。一組具有相相同結構的的復用器稱稱為復用器器樹總線。本文闡述的的復用器重重構技術采采用了新的的對整個復復用器總線線進行優化化的方法，它它通過由44.1節中中進一步闡闡述的總線線識別和形形成技術來來實現。2.4 復復用器代價價在許多情況況下，每個個2:1復用用器都需要要一個單獨獨的4-LLUT。這這樣，圖11和圖2中的復用用器結構都都需要三個個4-LUUT。盡管管這些結構構控制編碼碼不同，但但是它們都都具有4個不同的的數據輸入

29、入，因此可可以當作44:1復用用器。本節節闡述如何何實現只需需要兩個44-LUTT的4:1復用用器。圖5是控制制輸入S00低電平時時，一個有有效的4:1復用器器是如何工工作的。44:1復用用器由兩個個鏈接在一一起的4-LUT（陰陰影框所示示）構成。每個4-LUT被被設置為含含有陰影框框中的邏輯輯功能。如如白框所示示，復用器器含有四個個輸入a、b、c和d，以及兩兩個控制輸輸入S0和S1。S0低電平平時，低位位控制比特特S1在輸入入c和d中進行選選擇，其結結果通過第第二個4-LUT，將將a或者b輸入旁路路。圖6是控制制輸入S00高電平時時，一個有效效的4:11復用器是是如何工作作的。低位位控制比特

30、特S1旁路c和d輸入，直直接進入第第二個4-LUT，對對a或者b輸入進行行選擇，其其結果成為為第二個44-LUTT的輸出。第3節描述述的壓縮算算法采用這這種有效的的4:1復用用器，重新新實現復用用器結構，達達到了減小小面積的目目的。3. 壓縮縮壓縮是將低低效的4:1復用器器實現轉換換為高效實實現的過程程。復用器器重構算法法的面積節節省由壓縮縮實現。但是，在不不同的復用用器表征中中進行轉換換，通常需需要附加控控制邏輯。實際上，由由于附加邏邏輯結構抵抵消了使用用高效復用用器結構的的優勢，這這種轉換很很少能夠產產生真正的的面積節省省。而復用用器重構算算法采用新新穎的將整整個復用器器總線進行行轉換的方

31、方法，這樣樣，總線上上的多個復復用器可以以共享控制制邏輯，因因此，改善善后的復用用器結構優優勢可通過過總線上的的每個復用用器來實現現。圖7顯示了了如何將三三個2:11復用器組組成的優先先級鏈轉換換為一個44:1二進進制復用器器。假設控控制輸入由由不相關的的邏輯饋入入，那么這這種轉換至至多需要兩兩個額外的的4-LUUT控制邏邏輯。如果果最初的復復用器至少少占用三個個4-LUUT，而4:11復用器只只需要兩個個即可實現現，那么這這種轉換將將節省3寬度或者者更寬總線線的面積。圖8顯示了了如何將一一組排列成成樹的2:1復用器器轉換為一一個4:11復用器。在這種情情況下，通通過仔細為為4:1復用用器選擇

32、編編碼方式，使使S0在（A、B）和（C、D）之間進進行選擇，限限制附加控控制邏輯，只只加入最多多一個4-LUT。此時，這這種轉換將將節省2寬度或者者更寬總線線的面積。一般來講，任任何的三個個2:1復用用器組都可可以通過圖圖7或圖8的方式轉轉換為一個個4:1復用用器。但是是，這兩種種轉換必須須在寬度大大于2的復用器器總線上進進行，以減減小所需44-LUTT的數量，實實際上，如如果這兩種種轉換不在在總線上進進行，將沒沒有意義。總線上2:1復用器器三聯重新新編碼是復復用器重構構算法的核核心。下一一節將闡述述形成數量量最多三聯聯的新方法法。4. 復用用器總線4.1 “庫”的構造壓縮減小了了其所編碼碼的

33、每一個個2:1復用用器三聯面面積，因此此，壓縮應應用在較大大的復用器器樹上最有有效。本節節闡述大型型復用器樹樹是如何構構建的。設設計中所有有的總線都都將被存儲儲在一種稱稱為“庫”的數據結結構中。復用器樹采采用下面的的方法構建建。設計中中所有2:1復用器器以反向深深度順序排排列。這意意味著那些些離寄存器器或者輸出出引腳最近近的復用器器將排在列列表前面。然后從頭頭至尾掃描描列表，尋尋找每一個個2:1復用用器，如果果其輸出僅僅與另一個個2:1復用用器相連，則則將該復用用器和與其其相連的復復用器一起起加到復用用器樹中。否則，將將此2:11復用器作作為一個新新復用器樹樹的首復用用器。以此此方式來構構建的

34、復用用器樹含有有最大數量量的復用器器。如果復用器器樹中復用用器的所有有數據輸入入均不是由由同一個樹樹中其他的的2:1復用用器饋入，則則稱此復用用器為初級級輸入（對對整個樹而而言）。一旦所有的的復用器樹樹已經形成成，則將其其合并成總總線。如果果兩個復用用器樹要并并入同一個個總線，它它們必須具具有相同的的結構，即即，2:11復用器的的排列相同同，并且每每個都有完完全一致的的控制輸入入。這可以以通過根據據復用器結結構，對所所有復用器器樹列表排排序來實現現，在列表表中將結構構相同的樹樹靠近排列列。總線可可直接由結結構相同的的樹構成。通過規則選選取來實現現總線寬度度最大化。寬總線可可以將由壓壓縮引入的的

35、控制邏輯輯開銷降低低到最小。4.2 重重構 REF _Ref97605782 r h * MMERGEEFORMMAT 44.3節描描述均衡方方法，該方方法能夠使使壓縮得到到的面積減減小最大化化。均衡建建立在重構構的基礎上上，其概念念由本節給給出。通過2:11復用器所所饋入的一一個2:11復用器，重重構移動該該復用器及及其一個輸輸入。圖99顯示了陰陰影復用器器與其“f”輸入的重重構。為保保持原始復復用器總線線的功能，需需要附加一一些控制邏邏輯。這些些控制邏輯輯同樣可以以由總線上上的每一個個復用器樹樹來分擔。圖9中，重重新編碼邏邏輯(c66 ANDD (NOOT c33)必須須確保當cc1、c3

36、為“假”而c6為“真”時，選擇擇輸入“f”（與轉換換前的情況況一致）。同樣，當當c1、c3、c6為“假”時，選擇擇輸入“g”，即(c66 ANDD (NOOT c33)也是是“假”。重構轉換將將選中的復復用器進一一步向復用用器樹頂端端移動。因因此，不斷重復復重構轉換換，可以將將任意位置置的復用器器向頂端移移動。4.3 均均衡壓縮通過轉轉換2:11復用器三三聯，能夠夠減少實現現復用器總總線所需的的4-LUUT數量。但是，如如果不進行行復用器樹樹重構，有有些結構是是不可能得得到最佳三三聯分組的的。例如，無無法將圖110中所有有的2:11復用器進進行分組，這這是因為每每一種可能能的分組都都將會剩余余

37、一個2:1復用器器而無法處處理。均衡的目的的在于通過過最少的重重構得到最最佳的壓縮縮。對于圖圖10的例子子，可以采采用圖111所示的方方法，得到到兩組2:1復用器器三聯。均衡算法由由圖12的遞歸歸定義。由由首復用器器開始，算算法首先均均衡復用器器樹左面和和右面數據據輸入。均均衡返回還還沒有連接接為三聯的的2:1復用用器的數量量。均衡確確保形成盡盡可能多的的三聯，這這樣只會剩剩余一個或或者兩個22:1復用用器，甚至至沒有剩余余。Balannce( m ) if (iis_a_ mulltipllexerr (m) numm_muxxes = 1; / Couunt tthis mux numm_

38、muxxes += Baalancce(m。leftt); numm_muxxes += Baalancce(m。righht); if (numm_muxxes = 3) iif (nnum_mmuxess = 4) Appply trannsforrmatiion sshownn in Figuure 113; elsse iff (nuum_muuxes = 55) Appply trannsforrmatiion sshownn in Figuure 114; nnum_mmuxess = nnum_mmuxess 33; retturn num_muxees; elsse reetu

39、rnn 0; / priimaryy inpput: 0 muuxes圖12: 均衡算算法均衡中的任任何階段，都都需要對11到5個2:1復用用器進行均均衡（從左左側分支開開始最多兩兩個，從右右側分支開開始為兩個個，還要算算上當前的的2:1復用用器本身）。1或2個復用器器不會形成成更多的三三聯，而33個復用器器總是能夠夠形成三聯聯。4或5個復用器器則需要進進行重構，以以免剩余無無法處理的的復用器，這這種重構方方法在圖113和圖14中示出出。5. 算法法總結本文引入了了復用器樹樹總線概念念，描述了了可用來提提高壓縮性性能的均衡衡方法，壓壓縮以效率率更高的44:1復用用器來替代代2:1復用用器三聯。

40、圖15顯示了了全部復用用器重構算算法。Conveert_ Multtipleexerss_to_2:1ss ( )Form_Multtipleexer_Treees( )Mergee_Mulltipllexerr_Treees_iinto_Bussses( )Foreaach bbus Balannce(bbus) / (Miniimallly reearraange 2:1 intoo triipless)Comprress(bus) / (Connvertt 2:11 triipless intto effficiient 4:1s) 圖15: 復用器器重構算法法復用器重構構算法性能能依賴

41、于對對較大復用用器樹總線線的識別。由于復用用器重構算算法在整個個總線上分分擔控制邏邏輯，因此此，總線越越寬，壓縮縮的效果就就越明顯。優化會減減小復用器器樹間的相相似性，從從而減小所所尋找的總總線寬度，因因此在復用用器重構之之前，應盡盡量避免優優化。復用器重構構以分解大大的復用器器為2:11復用器開開始。設計計中所有22:1復用用器都用于于形成4.1節所描描述的復用用器樹。結結構相似的的復用器樹樹然后合并并形成4.1節中的的總線結構構。算法的主要要部分依次次優化每一一個總線。均衡將22:1復用用器重新排排列為三聯聯，這樣在在壓縮階段段，每個三三聯能夠重重新編碼為為效率更高高的4:11復用器6. 結果果本文所闡述述的算法已已經集成到到Alteera QQuarttus III 4.2綜合軟軟件中。 REF _Ref88915936 * MMERGEEFORMMAT 圖圖16顯示1200個真實用用戶設計中中，Alttera基基準測試的的面積減小小結果。結果表明，一一些設計所所需的LUUT數量減減小了200%，超過過40