用於高傳輸率渦輪碼之交錯器設計

Abstract

渦輪碼以其優異的性能獲得通訊界的青睞，但為達到較佳的效能，渦輪碼需要進行較多次的遞回運算並搭配較長的交錯器，也因此造成較長的解碼延遲。因此我們提出一種系統化的交錯器設計流程去解決解碼延遲與解碼效能之間的兩難。我們的設計考量代數特性與硬體限制。從代數特性的觀點來看，此設計利用較短的交錯器去建構較長的交錯器以保持較佳的碼距特性，我們所提出的交錯器還可額外滿足高解碼率與平行解碼的硬體限制，其中包括避免記憶體衝突，有限的網路複雜度以及較簡單的記憶體控制線路。所提出的交錯器有較簡單的代數形式，也允許較有彈性的平行度並較容易適應各種不同的交錯器長度。就算並非應用於平行解碼，在相同的交錯器長度下，本設計亦提供較佳的碼距特性。

我們將區塊間交錯重排交錯器分成方塊式與串接式，針對兩者我們為重量為二的輸入序列推導碼重邊界，此推導亦給了我們設計區塊間重排交錯器的參考依據，我們另外證明為了達成好的碼重性質並避免記憶體競爭的代數性質。針對方塊式區塊間重排交錯器，我們提出記憶體配置函數去描述與提供具彈性的解碼器平行度與支援高基數後驗機率解碼器。網路導向設計概念解決了平行解碼架構下網路複雜度的問題。我們亦提出有效率的交錯器設計流程去做大範圍的交錯器設計。我們亦用一個超大型積體電路設計去展現本設計確可同時兼顧高速與低複雜並提供較好的錯誤率。

串接式區塊間交錯排列交錯器是針對導管型解碼架構而設計，此架構非常適合高解碼率應用但須付出複雜度的代價。為了得到複雜度與解碼率的最佳折衷點，我們提出了一個動態結構。我們處理其所面對的解碼排程與記憶體控制問題，我們亦介紹了一種新穎的結合冗餘檢測碼與正負號檢測的終止機制，在一個較佳的解碼排程，記憶體控管與終止機制下，我們可以減少硬體複雜度並在較短的平均解碼延遲下達成更好的錯誤率。

為了描述各種遞回式解碼排程與分析其特性，我們發展了一個圖形工具稱為多階層元素圖，基於這個新工具，我們推導了可提供較佳錯誤率與使用較少記憶體的新解碼排程，基於完整性，我們亦展出非規則性打洞樣式去提供更好的錯誤率。

With all its remarkable performance, the classic turbo code (TC) suffers from prolonged latency due to the relatively large iteration number and the lengthy interleaving delay required to ensure the desired error rate performance. We present a systematic approach that solves the dilemma between decoding latency and error rate performance. Our approach takes both algebraic and hardware constraints into account. From the algebraic point of view, we try to build large interleavers out of small interleavers. The structure of classic TC implies that we are constructing long classic TCs from short classic TCs in the spirit of R. M. Tanner. However, we go far beyond just presenting a new class of interleavers for classic TCs. The proposed inter-block permutation (IBP) interleavers meet all the implementation requirements for the parallel turbo decoding such as memory contention-free, low routing complexity and simple memory addressing circuitry. The IBP interleaver has simple algebraic form; it also allows flexible degrees of arallelism and is easily adaptable to variable interleaving lengths. Even without high throughput demand, the IBP design is capable of improving the distance property with increased equivalent interleaving length but not the decoding delay except for the initial blocks.

We classify the IBP interleavers into block and stream ones. For both classes we derive codeword weight bounds for weight-2 input sequences that give us important guidelines for designing good IBP interleavers. We prove that the algebraic properties required to guarantee good distance properties satisfying the memory contention-free requirement as well. For block IBP interleavers, we propose memory mapping functions for flexible parallelism degrees and high-radix decoding units. A network-oriented design concept is introduced to reduce the routing complexity in the parallel decoding architectures. We suggest efficient interleaver design flows that offer a wide range of choices in the interleaving length. A VLSI design example is given to demonstrate that the proposed interleavers do yield high throughput/low complexity architecture and, at the same time, give excellent error rate performance.

The stream-oriented IBP interleavers are designed for the pipeline decoding architecture which is suitable for high throughput applications but has to pay the price of large hardware complexity. In order to achieve optimal trade-off between hardware complexity and decoding throughput, a dynamic decoder architecture is proposed. We address the issues of decoding schedule and memory management and introduce the novel stopping mechanisms that incorporate both CRC code and sign check. With a proper decoding schedule, memory manager and early-stopping rule, we are able to reduce the hardware complexity and achieve improved error rate performance with a shorter average latency.

In order to describe various parallel and pipeline iterative decoding schedules and analyze their behaviors, we develop a graphic tool called multi-stage factor graphs. Based on this new tool we derive a new decoding schedule which gives compatible error rate performance with less memory storage. For completeness, we show some irregular puncturing patterns that yield good error rate performance.