最近，小型毫微微蜂窩基站概念在移動應用中越來越受歡迎。與傳統宏蜂窩相比，毫微微蜂窩在覆蓋范圍、兼容性和成本方面都具有優勢。

由于成本和性能的制約，毫微微蜂窩設計必須具有與宏蜂窩大致相同的模塊化水平和復雜度，并且與個人而非社群的經濟承受能力相適應。

但是，為了實現至少與傳統宏蜂窩系統相同的信號強度，毫微微蜂窩必須采用支持高達14.4 Mbps比特率的多通道設計。因此，設計人員面臨著嚴峻挑戰：利用系統的數字信號處理(DSP)引擎編碼多通道比特流，同時為系統的其它關鍵操作提供足夠的計算裕量。

本文介紹如何實現基于Turbo編碼的高效算法以支持基于Blackfin的14.4 Mbps 3G毫微微蜂窩設計，該設計僅消耗Blackfin可提供的600 MIPS計算能力中的100 MIPS，從而為系統的其它必要操作留下了充沛的資源。

Turbo碼性能卓越，因此自1993年推出以來，便在業界和學術界引起了極大的關注。Turbo碼的工作效率幾乎達到了香農所確定的信道容量極限，信噪比(SNR)間隔小于或等于0.7dB。

Turbo碼最初由Berrou、Glavieux和Thitimajshima提出1，它是利用兩個并行級聯的卷積編碼器構建而成。在Turbo編碼方案中，同一信息序列的不同交織版本上產生兩個分量碼。在解碼器端，使用兩個最大后驗概率(MAP)解碼器以迭代方式解碼判決結果。MAP解碼算法使用接收到的數據和奇偶校驗符號（對應于根據真實和交織形式的數據位計算而來的奇偶校驗位）及其它解碼器軟輸出（外部）的信息，產生更可靠的判決結果。

關于Turbo碼的高效解碼，學術界已提出了許多算法和實現技術，但有關如何高效實現Turbo編碼器以支持高比特率應用的技術則不多見。在基站等應用中，一次須傳輸多個數據流。因此，必須高效實現Turbo編碼器，使之能以較少的處理能力編碼多個比特流。

毫微微蜂窩的服務對象是個體而非群體，因此用戶將擁有專屬的無線基礎設施，能夠為其所有移動設備提供良好的信號強度。就數據處理而言，宏蜂窩與毫微微蜂窩的模塊和復雜度大致相同。但是，毫微微蜂窩設計的目標用戶是個人而非群體，所以應做到價格低廉。因此，在毫微微蜂窩設計中使用多個昂貴的處理器件并不現實。本文并未闡述毫微微蜂窩完整架構的細節，但在討論用于無線網絡糾錯功能的3G標準2 Turbo編碼時，已特別注意了毫微微蜂窩設計的預算要求。

3G Turbo編碼器的實現

Turbo編碼器主要包括兩個成分編碼器，一個交織器將二者隔開。3G Turbo遞歸系統碼(RSC)編碼器的原理框圖如圖1所示。每個RSC編碼器均包括一個傳遞函數為(1+D+D3)的正向通道和一個傳遞函數為(1+D2+D3)的反饋通道。每個輸入的交織地址產生過程參見3GPP的論文2。利用雙MAC（乘法累加器）DSP（如Blackfin等）無法即時計算交織地址，除非我們有許多計算單元。

3G Turbo遞歸系統碼[RSC]編碼器

  
  
圖1.

通常是預先計算交織地址，并將其存儲在存儲器中。存儲的交織地址可以用于Turbo編碼和解碼。如果碼字很大，則預計算的交織地址存儲在L3存儲器中，否則存儲在L1存儲器中。對于更大的碼字，我們使用窗口方法編碼或解碼各位，并使用直接存儲器訪問方法根據需要從L3傳輸數據（如輸入和交織地址等）。

由圖1可知，對于每個輸入，我們輸出一個系統位Xi和兩個奇偶校驗位Yi和Zi。這里，奇偶校驗位Zi并不直接取決于實際輸入位bi，而是取決于交織緩沖器中索引為i的位b'i。給定N位的輸入消息塊B時，我們或者執行地址計算，從塊B獲得各輸入位索引的交織位b'i，或者立即執行整個塊B的交織，并存儲為交織塊B'，然后用索引i線性訪問b'i。請注意，根據3G標準計算交織位地址并非易事，因此，我們傾向于在開始編碼多個消息數據塊之前，預先計算所有N位的地址，并將其一次性存儲在存儲器中。這樣，我們就能忽略Turbo編碼產生交織地址的復雜性。

簡單編碼。在簡單編碼中，我們逐位編碼。對于每個輸入位，我們輸出三位。模擬RSC編碼器的一段C代碼樣例如表1所示。通常，輸入數據位以8位字節的形式從存儲器存取，因為處理器可以從存儲器存取的最小數據為一個字節（或一個8位量）。獲得一個字節的數據后，為了逐位進行編碼，必須拆包各位，每位需要大約1.125周期（總共9個周期：使用Blackfin rot指令，第一位拆包需要2個周期，其余各位需要1個周期）。然后，編碼此位又需要7個周期，因為編碼僅涉及到序列化操作。完成編碼后，必須將編碼位封包，并存儲在存儲器中，以便進行其它處理和傳輸。數據封包所需的周期數與拆包相同，即每位1.125周期。因此，編碼1位數據并輸出1個奇偶校驗位總共需要10個周期（包括開銷）。

計算復雜度。由于我們使用查找表來檢索交織地址，而不是即時計算，因此只有訪問查找表需要一些周期（可能不涉及計算操作）。交織一個數據位需要大約三個周期（一個周期用于加載偏移，兩個周期用于計算絕對地址）。Turbo編碼涉及到兩個RSC編碼器和一個交織操作，因此編碼一個數據位總共需要25個周期（包括開銷）。對于14.4 Mbps比特率的毫微微蜂窩應用，我們需要大約360 MIPS，即約60%的Blackfin處理器MIPS。

Turbo碼的處理

如前所述，如果實現不當，更高比特率的Turbo編碼器將是一個昂貴的模塊。接下來，我們將討論高效實現Turbo編碼器的技術。我們將Turbo編碼器分為兩部分：第一部分是來處理位的編碼，第二部分是處理數據位的交織。

使用查找表進行編碼。如前所述，使用兩個RSC編碼器進行Turbo編碼時，每個輸入位需要大約20個周期。下面我們將介紹一種不同的使用查找表方法，每個輸入位只需2.5個周期（用于兩個編碼器）。為了存儲查找表數據，需要256個字節的額外存儲器。考慮到RSC編碼器的目前狀態，使用查找表一次可以編碼多個位。通過預先計算長度L的輸入位的所有可能組合和狀態位的所有三種組合的查找表，我們一次可以編碼L位。在這種編碼中，我們使用的查找表含有2L+3項。隨著L值增大，查找表也會增大。L = 4時（換言之，一次編碼4位），查找表含有27或128項，如圖2所示。各項包含4個編碼位和3位更新狀態信息。換言之，一個字節（或8位）足以代表查找表的各項。

基于查找表的Turbo編碼

圖2.

深入研究8位查找表設計可以發現，為了從4個輸入位（假設位于寄存器r0）和3個當前狀態位（假設位于寄存器r1）計算128項查找表的7位偏移，我們必須從輸入字節（或從r0）提?。?個周期）4個數據位（假設存入寄存器r2），從前一編碼的查找表輸出（或從r1）提?。?個周期）當前狀態（假設存入寄存器r3），將3個狀態位移動（1個周期）4位(r3 = r3<<4)，以及對提取的4個輸入數據位至狀態位求“或”（1個周期；即r4 = r2|r3）。只要正確設計查找表，我們就能避免狀態位的提取和移位操作。如果我們對各查找表項使用兩個字節，并將狀態位置于移位位置，如圖3所示，我們就能省掉兩個偏移計算周期（節約50%）。

高效Turbo編碼的查找表設計

圖3.

完成編碼位的計算之后，我們必須將編碼位封包。我們一次編碼4位，并且一次輸出一個編碼的4位半字節，因此將半字節封包成字節是很容易的事。我們用兩個周期將兩個半字節封包成一個字節，一個周期用于左移，另一個周期用于“或”或“和”運算。對于雙編碼器輸出封包，Blackfin需要四個周期。利用乘法累加器(MAC)，我們可以在兩個周期內完成兩個編碼器的封包工作，因為Blackfin有兩個MAC單元。對于單迭代循環，用于Turbo編碼器編碼和封包的Blackfin ASM代碼如表2所示。該ASM代碼包括兩個RSC編碼器的編碼和封包。ASM代碼清楚地顯示，一個字節的Turbo編碼需要20個周期，或者說每個位需要2.5個周期。

在表2中，借助此ASM代碼，我們可一次實現兩個編碼器的4位數據編碼。但實際上，第二個編碼器并不直接從輸入比特流字節中獲得數據。傳送給第二編碼器之前，我們必須對輸入比特流進行交織處理。我們已經討論了第二個編碼器的交織，交織位存儲在交織緩沖器中。我們假設，通過將交織位存儲在可尋址的邊界內（換言之，存儲一位必須使用最小的字節），所存儲的交織位可以直接從緩沖器存取進行編碼。由于我們是利用查找表方法以半字節形式進行編碼，因此必須先將交織位封包成字節，再將其存儲在交織緩沖器中。

交織器設計。由于上述基于查找表的編碼方法需要字節形式的交織位，因此必須將交織位封包成字節。這樣，為了以正確的順序將這些位送入第二個編碼器，必須執行以下三個步驟：拆包、交織、封包。我們以字節表示數據，封包是將位多路復用為字節，拆包是將字節解多路復用為位。將位封包成字節需要所有交織位，我們首先必須完成交織處理。對于這兩種操作（拆包和交織），每位大約需要3個周期，如表3所示。表3中的ASM代碼對一個字節的輸入數據執行拆包和交織處理。帶進位的循環移位指令rot r by -1可提供從結尾最高有效位(MSB)開始的拆包數據位。

下一步是將交織數據位封包成字節。封包操作與表3所示的拆包操作完全相反。但是，如果我們使用進位循環指令rot r by 1進行封包，則每位需要2個周期，其中一個周期用于將寄存器中的數據位移入cc。因此，我們不使用循環，而使用比較和選擇指令vit_max進行封包。vit_max指令將兩個寄存器中存在的兩個最低有效位(LSB)字與同一寄存器的兩個MSB字相比較，從而一次封包兩位。vit_max指令的比較結果輸出標志保存于累加器中，經過四次迭代后，我們從累加器中提取封包的字節。由于我們無法在一個周期內從同一緩沖器加載兩位數據提供給vit_max指令，因此必須再花一個周期來加載數據位。這樣，封包兩位需要兩個周期，或者一位一個周期，如表4所示。

計算復雜度評估

無論是依據每位周期數來評估，還是依據執行任務所需的存儲空間來評估，這種Turbo碼算法實現方法的計算負荷都是相對適中的。

周期估算。如表3和表4所示，對交織數據執行拆包、交織和封包處理，每位需要4個周期。在表2所示的數據編碼中，每位需要2.5個周期。這樣，Turbo編碼器總的周期成本為每位6.5個周期。請注意，這一估算沒有考慮周期開銷。假設每位的開銷為1個周期，則執行Turbo編碼，每位需要大約7.5個周期。借助這一高效的實現方法，我們在14.4 Mbps比特率時只需使用Blackfin處理器的108 MIPS，或者約18%的處理器MIPS。相比之下，簡單編碼方法則需要使用60%的處理器MIPS。由于Turbo編碼器只消耗18%的MIPS，還剩下約82%的處理器MIPS，因此我們有充足的裕量來應對毫微微蜂窩基站的其它模塊。

存儲空間估算。利用查找表方法實現Turbo編碼時，我們需要256字節的數據存儲空間來存儲預計算的編碼信息。采用高效方法時，我們將各位封包成字節，因而存儲交織數據所需的數據存儲空間更小（僅1/8）。即時計算交織地址的方法非常昂貴，所以兩種方法均需要數據存儲器來存儲交織地址。

利用預先計算的查找表，我們可以僅使用18%的處理器MIPS來執行Turbo編碼；否則，使用簡單方法則要消耗約60%的MIPS。這種高效方法使用256字節的存儲器來存儲查找表，所用的總存儲空間少于簡單方法所需的存儲空間。

作者：Hazarathaiah Malepati和Yosi Stein，ADI半導體

參考文獻

1. Berrou C, A Glavieux, and P. Thitimajshima,, "Near Shannon Limit Error-Correcting Coding: Turbo Codes," Proc IEEE Int. Conf. Commun., Geneva, Switzerland, pp.1064–1070, 1993.
2. 3GPP: 3rd Generation Partnership Project, "Technical Specification Group Radio Access Network, Multiplexing and Channel Coding," V8.0.0, 2007.