臺灣博碩士論文加值系統

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

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

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

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

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.

1 Introduction 1
1.1 Turbo decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Performance analysis and graph codes . . . . . . . . . . . . . . . . . . . . 3
1.3 Low latency/high performance interleavers . . . . . . . . . . . . . . . . . 4
1.4 Statement of purpose: main contributions . . . . . . . . . . . . . . . . . 7
1.5 Existing interleavers as instances of IBP interleaver . . . . . . . . . . . . 9
1.6 Overview of chapters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Fundamentals 13
2.1 Digital communication system . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Discrete memoryless channel model . . . . . . . . . . . . . . . . . 15
2.1.2 Mapper and de-mapper . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.3 Error control system . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Convolutional code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Mathematical notations . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2 Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.3 State space, state diagram and trellis representation . . . . . . . . 20
2.2.4 Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.5 Soft output decoding algorithm for convolutional code . . . . . . 24
2.3 Turbo code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.1 Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.2 Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4 Factor graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5 Convergence analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5.1 EXIT chart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5.2 Density evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.6 High throughput turbo decoder architecture . . . . . . . . . . . . . . . . 37
2.7 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.7.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3 Inter-block permutation interleaver 40
3.1 Inter-block permutation turbo code . . . . . . . . . . . . . . . . . . . . . 41
3.2 Inter-block permutation interleaver . . . . . . . . . . . . . . . . . . . . . 42
3.3 IBP properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.1 First property: invariant permutation . . . . . . . . . . . . . . . . 46
3.3.2 Second property: periodic permutation . . . . . . . . . . . . . . . 47
3.4 Constraints on the intra-block permutations . . . . . . . . . . . . . . . . 50
3.4.1 TP-IBPTC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4.2 TB-IBPTC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4.3 C-IBPTC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.5 TB-IBPTC bounds of codeword weights for weight-2 input sequences . . 55
3.5.1 The achievable weight-2 lower bound . . . . . . . . . . . . . . . . 56
3.5.2 Analytical results . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4 Block-oriented inter-block permutation interleaver 63
4.1 The parallel turbo decoder architecture and memory contention . . . . . 64
4.2 Block-oriented IBPTC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2.1 B-IBP interleaver . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.2 Parallelization method in the B-IBP manner . . . . . . . . . . . . 71
4.2.3 Parallelization method in the reversed B-IBP manner . . . . . . . 75
4.2.4 Generalized maximal contention-free and intra-block permutation 77
4.2.5 High-radix APP decoder and intra-block permutation . . . . . . . 80
4.3 Network-oriented interleaver design . . . . . . . . . . . . . . . . . . . . . 82
4.3.1 Network-oriented B-IBP design . . . . . . . . . . . . . . . . . . . 83
4.3.2 Butterfly network . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.3.3 Barrel shifter network . . . . . . . . . . . . . . . . . . . . . . . . 88
4.4 B-IBP interleaver supports variable information length . . . . . . . . . . 89
4.4.1 Shortening and puncturing . . . . . . . . . . . . . . . . . . . . . . 90
4.4.2 Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.4.3 Comparison between shortening and pruning . . . . . . . . . . . . 91
4.5 An interleaver design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.5.1 Interleaver description . . . . . . . . . . . . . . . . . . . . . . . . 94
4.5.2 Comparison to 3GPP LTE QPP . . . . . . . . . . . . . . . . . . . 95
4.6 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.7 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.7.1 The interleaver design . . . . . . . . . . . . . . . . . . . . . . . . 98
4.7.2 Shortening and puncturing . . . . . . . . . . . . . . . . . . . . . . 100
4.7.3 Separate and continuous encoding . . . . . . . . . . . . . . . . . . 101
5 Stream-oriented inter-block permutation interleaver 106
5.1 Stream-oriented IBP interleaver and the associated encoding storage . . . 107
5.2 Stream-oriented IBPTC encoding and the associated storage . . . . . . . 108
5.3 Pipeline decoder and the associated message-passing on the factor graph 110
5.4 Bound and constraints modification for S-IBP interleaver . . . . . . . . . 111
5.5 Codeword weight upper-bounds of stream-oriented IBPTC . . . . . . . . 114
5.5.1 The upper-bound for weight-2 input sequences . . . . . . . . . . . 116
5.5.2 The upper-bound for weight-4 input sequences . . . . . . . . . . . 118
5.5.3 Interleaving gain comparison . . . . . . . . . . . . . . . . . . . . . 121
5.6 Stream-oriented IBP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.7 Modified semi-random interleaver . . . . . . . . . . . . . . . . . . . . . . 121
5.8 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.8.1 Covariance and convergence behavior . . . . . . . . . . . . . . . . 124
5.8.2 Error probability performance . . . . . . . . . . . . . . . . . . . . 126
6 Dynamic IBPTC decoder and stopping criteria 134
6.1 IBP turbo coding system with stopping mechanism . . . . . . . . . . . . 135
6.1.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.1.2 Iterative decoder with variable termination time . . . . . . . . . . 137
6.1.3 Graphical representation of an IBPTC and CRC codes . . . . . . 141
6.2 Dynamic decoder and the associated issues . . . . . . . . . . . . . . . . . 141
6.2.1 Dynamic decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.2.2 Decoding delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.2.3 Memory contention and decoding schedule for multiple ADUs . . 146
6.2.4 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . 148
6.3 Multiple-round stopping tests . . . . . . . . . . . . . . . . . . . . . . . . 152
6.3.1 A general algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.3.2 T1.m: the m-round CRCST . . . . . . . . . . . . . . . . . . . . . 154
6.3.3 T2.m: the m-round SCST . . . . . . . . . . . . . . . . . . . . . . 155
6.3.4 T3.m: the m-round hybrid stopping test (MR-HST) . . . . . . . . 156
6.3.5 Genie stopping test . . . . . . . . . . . . . . . . . . . . . . . . . . 156
6.4 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7 Multi-stage factor graph 163
7.1 Multi-stage factor graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
7.1.1 LDPC code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
7.1.2 S-IBPTC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
7.2 Multi-stage factor sub-graph . . . . . . . . . . . . . . . . . . . . . . . . . 172
7.2.1 LDPC code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
7.2.2 S-IBPTC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
7.2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
7.3 Causal multi-stage sub-graph . . . . . . . . . . . . . . . . . . . . . . . . 176
7.4 A memory-saving schedule for S-IBPTC . . . . . . . . . . . . . . . . . . 179
7.5 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
8 Conclusions 183
A Proof of Lemma 3.6 185
B Proof of Lemma 3.7 187
C Proof of Theorem 3.3 188
D Proof of Theorem 5.10 190
E Puncturing Patterns 197

[1] TS 25.222 v3.1.1 Multiplexing and channel coding (TDD), 3GPP TSG RAN WG1,
Dec. 1999.
[2] TS 25.212 v6.4.0 Multiplexing and channel coding (FDD), 3GPP TSG RAN WG1,
Mar. 2005.
[3] TS 36.212 V1.0.0 Multiplexing and channel coding, 3GPP TSG RAN WG1, Mar.
2007.
[4] D. Agrawal, A. Vardy, “The turbo decoding algorithm and its phase trajectories,”
in IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 699-722, Feb. 2001.
[5] J. B. Anderson, S. M. Hladik,“Tailbiting MAP decoders,” in IEEE J. Select. Areas
Commun., vol. 16, no. 2, pp. 297-302, Feb. 1998.
[6] S. L. Ariyavisitakul, “Turbo space-time processing to improve wireless channel ca-
pacity,” IEEE Trans. Commun., vol.48, no. 8, pp. 1347-1359, Aug. 2000.
[7] S. Baero, J. Hagenauer, M. Witzke, “Iterative detection of MIMO transmission
using a list-sequenctial (LISS) detector,” in Int’l Conf. Commun., Anchorage, USA,
May 2003.
[8] L. R. Bahl, J. Cocke, F. Jelinek, F. Raviv, ”Optimal decoding of linear codes for
minimizing symbol error rate,” IEEE Trans. on Inform. Theory, vol. 20, no. 2, pp.
284-287, Mar. 1974.
[9] S. Benedetto, G. Montorsi, “Unveiling turbo codes: some results on parallel con-
catenated coding schemes,” IEEE Trans. Inform. Theory, vol. 42, no. 2, pp. 409-428,
Mar. 1996.
[10] S. Benedetto, D. Divsalar, G. Montorsi, F. Pollara, “A soft-input soft-output APP
module for iterative decoding of concatenated codes,” in IEEE Commun. Letters,
vol. 1, no. 1, pp. 22-24, Jan. 1997.
[11] S. Benedetto, G. Montorsi,“Performance of continuous and blockwise decoded turbo
codes,” IEEE Commun. Lett., vol. 1, no. 3, pp. 77-79, May 1997.
[12] C. Berrou, Y. Saouter, C. Douillard, S. K´erou´edan, M. J´ez´equel, “Designing good
permutations for turbo codes: towards a single model,” in Proc. IEEE Int’l Conf.
Commun., Paris, France, vol. 1, pp. 341-345, Jun. 2004.
[13] C. Berrou, A. Glavieux, and P. L. Thitimajshima, “Near Shannon limit error-
correcting coding and decoding: turbo-codes,” in Proc. Proc. IEEE Int’l Conf.
Commun., Geneva, Switzerland, pp. 1064-1070, May 1993.
[14] C. Berrou, M. J´ez´equel, “Non-binary convolutioanl codes for turbo coding,” in
Electronics. Letters, vol. 35, no. 1, pp. 39-40, Jan 1999.
[15] C. Berrou, M. J´ez´equel, C. Douillard, S. Kerouedan, “The advantages of non-binary
turbo codes,” in Proc. ITW2001, Sep. 2001.
[16] M. Bickersta®, L. Davis, C. Thomas, D. Garrett, C. Nicol, “A 24Mb/s radix-4
log MAP turbo decoder for 3GPP-HSDPA mobile wireless,” in ISSCC Dig. Tech.
Papers, pp. 151-484, 2003.
[17] P.J. Black, T.H.-Y. Meng,“Hybrid survivor path architectures for Viterbi decoders,”
ICASSP 93, vol. 1, pp. 433-436, Apr. 1993.
[18] W. J. Blackert, E. K. Hall, S. G. Wilson, “Turbo code termination and interleaver
conditions,” Electron. Lett., vol. 31, pp. 2082-2084, Nov. 1995.
[19] D. W. Bliss, A. M. Chan, N. B. Chang, “MIMO wireless communication channel
phenomenology,” in IEEE Trans. Antennas and Propagation, vol. 52, no. 8, pp.
2073-2082, Aug. 2004.
[20] B. Bougard, A. Giulietti, V. Derudder, J. Willem, S. Dupond, L. Hollevoet, F.
Catthoor, L. V. der Perre, H. D. Man, R. Lauwereins, “A scalable 8.7nj/bit
75.6Mb/s parallel concatenated convolutional (turbo-)codec,” in ISSCC Dig. Tech.
Papers, pp. 152-484, 2003.
[21] E. Boutillon, W. J. Gross, P. G. Gulak, “VLSI architectures for the MAP algo-
rithm,” in IEEE Trans. Commun., vol. 51, no. 2, pp. 175-185 , Feb. 2003.
[22] E. Boutillon, D. Gnaedig, “Maximum spread of D-dimensional multiple turbo
codes,” IEEE Trans. Commun., vol. 53, no. 8, pp. 1237-1242, Aug. 2005.
[23] J. Boutros, G. Caire, E. Viterbo, H. Sawaya, S. Vialle, ”Turbo code at 0.03 dB
from capacity limit,” in Proc. Int’l Sympo. on Inform. Theory, pp. 56, 30 Jun.-5
Jul. 2002.
[24] M. Breiling, J. B. Huber,“Upper bound on the minimum distance of turbo codes,”
IEEE Trans. Commun., pp. 808-815, May 2001.
[25] M. Breiling, J. B. Huber, “Combinatorial analysis of the minimum distance of turbo
codes,” IEEE Trans. Inform. Theory, pp. 2737-2750, Nov. 2001.
[26] A. J. Blanksby, C. J. Howland, “A 690mW 1Gb/s 1024-b, rate-1/2 low-density
parity-check code decoder,” in IEEE Journal of Solid-State Circuits, vol. 37, no. 3,
pp. 404-412, Mar. 2002.
[27] S. T. Brink, “Convergence of iterative decoding,” in Electronics Letters, vol. 35, no.
13, pp. 1117-1119, Jun. 1999.
[28] S. ten Brink, “Convergence behavior of iteratively decoded parallel concatenated
codes,” in IEEE Trans. Commun., vol. 49, no. 10, pp. 1727-1737, Oct. 2001.
[29] R. Brualdi, Introductory Combinatorics, Amsterdam, The Netherlands: North-
Holland, 1977.
[30] S. Crozier, J. Lodge, P. Guinand, A. Hunt, “Performance of turbo codes with
relative prime and golden interleaving strategies”, in Proc. of the 6th Int’l Mobile
Satellite Conference (IMSC ’99), Ottawa, Ontario, Canada, pp. 268-275, Jun. 16-
18, 1999.
[31] S. Crozier, P. Guinand, “Distance upper bounds and true miimum distance restuls
for turbo codes with DRP interleavers,” in Proc. 3rd Int’l Sympo. on Turbo Codes
& Related Topics, Brest, France, pp. 169-172, Sep. 2003.
[32] F. Daneshgaran, P. Mulassano, “Interleaver pruning for construction of variable-
length turbo codes,” in Trans. Inform. Theory vol. 50, no.3, pp. 455-466, Mar.
2004.
[33] V. C. Gaudet, R. J. Gaudet, G. Gulak, “Programmable interleaver design for analog
iterative decoders,” in IEEE Trans. on Circuits and Systems-II: Analog and Digital
Signal Processing, vol. 49, no. 7, pp. 457-464 , Jul. 2002.
[34] D. Divsalar, S. Dolinar, F. Pollara,“Iterative turbo decoder analysis based on den-
sity evolution.” in IEEE J. Select. Areas Commun., vol. 19, no. 5, pp. 891-907, May
2001.
[35] R. Dobkin, M. Peleg, R. Ginosar, “Parallel interleaver design and VLSI architecture
for low-lantecy MAP turbo decoders,” in IEEE Trans. VLSI Systems, vol. 13, no.
4, pp. 427-438 , Apr. 2005.
[36] C. Douillard, M. J´ez´equel, C. Berrou, “Iterative correction of intersymbol interfer-
ence: turbo-equalization,” in European Trans. Telecommunications, vol. 6, no. 5,
pp. 507-511, Sep./Oct. 1995.
[37] DVB, ”Interaction channel for satellite distribution systems,” ETSI EN 301 790,
V1.2.2, pp. 21-24, Dec. 2000.
[38] DVB, ”Interaction channel for digital terrestrial television,” ETSI EN 301 958,
V1.1.1, pp. 28-30, Aug. 2001.
[39] H. El Gamal, A. R. Hammons, Jr., “Analyzing the turbo decoder using the Gaussian
approximation,” in IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 671-686, Feb.
2001.
[40] W. Feng, J. Yuan, B. S. Vucetic, “A code-matched interleaver design for turbo
codes,” in IEEE Trans. Commun., vol. 50, no. 6, pp. 926-937, Jun. 2002.
[41] G. D. Forney, “The Viterbi algorithm,” Proc. of the IEEE, vol 61, no. 3, pp. 268-278,
Mar. 1973.
[42] G. D. Forney, Jr., “Codes on graphs: normal realizations,” in IEEE Trans. Inform.
Theory, vol. 47, no. 2, pp. 520-548, Feb. 2001.
[43] M. P. C. Fossorier, “Quasi-cyclic low-density parity-check codes from circulant per-
mutation matrices,” in IEEE Trans. Inform. Theory, vol. 50, no. 8, pp. 1788-1793,
Aug. 2004.
[44] C. Fragouli, R. D. Wesel,“Semi-random interleaver design criteria,” in Proc. Globe-
com’99, Rio de Janeiro, Brazil, pp. 2352-2356, 1999.
[45] B. J. Frey, D. J. C. MacKay, “Irregular turbocodes,”in Proc. Int’l Symposium on
Information Theory, pp. 121, Jun. 25-30, 2000.
[46] R. G. Galleger, Low-density parity-check codes, MIT Press, Cambridge, Mass., 1963.
[47] O. Gazi, ¨O. Yilmaz, “Fast decodable turbo codes,” in IEEE Commun. Letters, vol.
11, no. 2, pp. 173-175, Feb. 2007.
[48] W. Gellert, H. Justner, M. Hellwich, H. Kastner, The Vnr Concise Encyclopedia of
Mathematics, Van Nostrand Reinhold, pp. 97-99, 1977.
[49] A. Giulietti, L. Van der Perre, M. Strum, “Parallel turbo coding interleavers: avoid-
ing collisions in accesses to storage elements,” in Electronics Letter, vol. 38, no. 5,
pp. 232-234, Feb. 2002.
[50] J. Hagenauer, E. O®er, and L. Papke, “Iterative decoding of binary block and
convolutional codes” IEEE Trans. Inform. Theory, vol. 42, no. 2, pp. 429-445, Mar.
1996.
[51] E. K. Hall, S. G. Wilson, “Stream-oriented turbo codes,” IEEE Trans. Inform.
Theory, vol. 47, no. 5, pp. 1813-1831, Jul. 2001.
[52] K. Hasung, G. L. St¨uber, “Rate compatible punctured turbo coding forW-CDMA,”
in Proc. IEEE Int’l Conf. Personal Wireless Commun., pp. 143-147, Dec. 2000.
[53] P. Hoeher, J. Lodge, ““Turbo DPSK”: iterative di®erential PSK demodulation and
channel decodign,” in IEEE Trans. Commun., vol. 47, no. 6, pp. 837-843 , Jun.
1999.
[54] J. Hokfelt, O. E®ors, T. Maseng, “A turbo code interleaver design criterion based
on the performance of iterative decoding,” IEEE Commun. Lett, vol. 5, no. 2, pp.
52-54, Feb. 2001.
[55] C. J. Howland, A. J. Blanksby, ”A 220mW 1Gb/s 1024-b, rate-1/2 low-density
parity-check code decoder,” in IEEE Conf. on Custom Integrated Circuits, pp. 293-
296, May. 2001.
[56] IEEE Std 802.16e-2005, 802.16 TGe, Feb. 2006.
[57] H. Jin, A. Khandekar, R. J. McEliece, “Irregular repeat-accumulate codes,” in Proc.
3rd Int’l Sympo. on Turbo Codes & Related Topics, Brest, France, pp. 1-8, Sep. 2000.
[58] R. Johannesson, K. Sh. Zigangirov, Fundamentals of Convolutional Codes, The
Institute of Electrical and Electronics Engineering, Inc, 1999.
[59] M. A. Kousa, A. H. Mugaibel, “Puncturing e®ects on turbo codes,” in IEE Proc.
Commun., vol. 149, pp. 132-138, Jun. 2002.
[60] F. R. Kschischang, B. J. Frey, H.-A. Loeliger, “Factor graphs and the sum-product
algorithm,” in IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 498-519, Feb. 2001.
[61] T.-C. Lee, J. Cong, “The new line in IC design,” in IEEE Spectrum, pp. 52-58, Mar.
1997.
[62] C.-C. Lin, K.-L. Lin, H.-C. Chang, C.-Y. Lee, ”A 3.33Gb/s (1200,720) low-density
parity check code decoder,” in Proc. ESSCIRC 2005, pp.211-214, Sep. 2005.
[63] M. M. Mansour and N. R. Shanbhag, “High throughput LDPC decoders,” in IEEE
Trans. VLSI Systems, vol. 11, pp. 976-996, Dec. 2003.
[64] J. L. Massey, M. K. Sain, “Codes, automata, and continuous systems: explicit
interconnections,” IEEE Trans. on Automatic Control, AC-12:644-650, 1968.
[65] A. Matache, S. Dolinar, F. Pollara, “Stopping rules for turbo decoders,” in TMO
Progress Report 42-142, 15 Aug. 2000.
[66] R. J. McEliece, D. J. C. MacKay, J.-F Cheng “Turbo decoding as an instance of
Pearl’s “Belief propagation” algorithm,” in IEEE J. Select. Areas Commun., vol.
16, no. 2, pp. 260-264, Feb. 1998.
[67] H. Moussa, O. Muller, A. Baghdadi, M. M. J´ez´equel, “Butterfly and Benes-based
on-chip communication networks for multiprocessor turbo decoding,” in Proc. De-
sign, Automation and Test in Europe, pp. 654-659, Apr. 2007.
[68] O. Muller, A. Baghdadi, M. J´ez´equel, “ASIP-based multiprocessor SOC design for
simple and double binary turbo decoding,” in Proc. Design, Automation and Test
in Europe, pp. 6-10, Mar. 2006.
[69] A. Nimbalker, K. T. Blankenship, B. Classon, T. E. Fuja, D. J. Costello, Jr., “Inter-
window shu²e interleavers for high throughput turbo decoding,” in Proc. 3rd Int’l
Sympo. on Turbo Codes & Related Topics, Brest, France, pp. 355-358, Sep. 2003.
[70] A. Nimbalker, T. E. Fuja, D. J. Costello Jr., T. K. Blankenship, B. Classon,
“Contention-free interleavers,” in Proc. Int’l Symposium on Information Theory,
pp. 52, Jun. 27-Jul. 2, 2004.
[71] S. Y. Le Go®, “Signal constellations for bit-interleaved coded modulation,” in IEEE
Trans. Inform. Theory, vol. 49, no. 1, pp.307-313, Jan. 2003.
[72] X. Li, J. A. Ritcey, “Trellis-coded modulation with bit interleaving and iterative
decoding,” in IEEE J. Select. Areas Commun., vol. 17, no. 4, pp. 715-724, Apr.
1999.
[73] S. Paraharalabos, P. Sweeney, B. G. Evans, “Constant log-MAP decoding algorithm
for duo-binary turbo codes,” in Electronics Letters, vol. 42, no. 12, pp. 709-710, Jun.
2006.
[74] L. C. Perez, J. Seghers, D. J. Costello, “A distance spectrum interpretation of turbo
codes,” IEEE Trans. Inform. Theory, Vol. 42, no. 6, pp. 1698-1709, Nov. 1996.
[75] A. Perotti, S. Benedetto, “A new upper bound on the minimum distance of turbo
codes,” IEEE Trans. Inform. Theory, vol. 50, no. 12, pp. 2985-2997, Dec. 2004.
[76] J. Pittermann, M. Lentmaier, K. S. Zigangirov, “On bandwidth-e±cient convolu-
tional LDPC code,” in Proc. Int’l Sympo. on Inform. Theory, pp. 235, 29 Jun.-4
Jul. 2003.
[77] V. Poor, S. Verd´u, “Probability of error in MMSE multiuser detection,” in IEEE
Trans. Inform. Theory, vol. 43, no. 3, pp. 858-871, May 1997.
[78] G. Prescher, T. Gemmeke, T. G. Noll, ”A parametrizable low-power high-
throughput turbo-decoder,” in IEEE ICASSP 2005, vol. 5, pp. 25-28, Mar. 2005.
[79] J. G. Proakis, Digital communications 4th, Mc Graw Hill, Inc., 2000.
[80] R. M. Pyndiah, “Near-optimum decoding of product codes: block turbo codes,” in
IEEE Trans. Commun., vol. 46, pp. 1003-1010, Aug. 1998.
[81] R. M. Pyndiah, A. Glavieux, A. Picart, S. Jacq, “Near Optimum decoding of
pruduct codes,” in Proc. IEEE Globecom’94, San Francisco, USA, vol. 1, pp. 339-
343, Nov. 28-Dec. 2 1994.
[82] T. J. Richardson, R. L. Urbanke, “Thresholds for turbo codes,” in Proc. IEEE Int’l
Symp. Inform. Theory, Sorrento, Italy, pp. 172, June 2000.
[83] T. J. Richardson, R. L. Urbanke, “The capacity of low-density parity-check codes
under message-passing decoding,” in IEEE Trans. Inform. Theory, vol. 47, no. 2,
pp. 599-618, Feb. 2001.
[84] P. Robertson, T. W¨orz, “Bandwidth-e±cient turbo trellis-coded modulation using
puctured component codes,” in IEEE J. Select. Areas Commun., pp. 206-218, Feb.
1998.
[85] J. Ryu, O. Y. Takeshita, “On quadratic inverses for quadratic permutation poly-
nomials over integer rings,” in IEEE Trans. Inform. Theory, vol. 52, no. 3, pp.
1254-1260, Mar. 2006.
[86] H. R. Sadjadpour, N. J. A. Sloane, M. Salehi, G. Nebe, “Interleaver design for turbo
codes,” IEEE J. Select. Areas Commun., vol. 19, no. 5, pp. 831-836, May 2001.
[87] I. Sason, S. Shamai,“Improved upper bounds on the ML decoding error proba-
bility of parrallel and serial concatenated turbo codes via their ensemble distance
spectrum,” in IEEE Trans. Inform. Theory, vol. 46, no. 1, pp. 24-47 Jan. 2000.
[88] R. Y. Shao, S. Lin, and M. P. C. Fossorier, “Two simple stopping criteria for turbo
decoding,” in IEEE Trans. Commun., vol. 47, no. 8, Aug. 1999.
[89] Jens Sparso, Henrik N. Jorgensen, Erik Paaske, Steen Pendersen, and Thomas
Rubner-Petersen, “An area-e±cient topology for VLSI implementation of Viterbi
decoders and other shu²e-exchange type structures,” IEEE J. Solid-State Circuit,
vol. 26, No.2, pp. 90-97, February 1991.
[90] J. Sun, O. Y. Takeshita, “Interleavers for turbo codes using permutation polynomi-
als over integer rings,” in IEEE Trans. Inform. Theory, vol. 51, no. 1, pp. 101-119,
Jan. 2005.
[91] O. Y. Takeshita, O. M. Collins, P. C. Massey, D. J. Costello, Jr., “A note on
asymmetric turbo codes,” in IEEE Commun. Letters, vol. 3, pp. 69-71, Mar. 1999.
[92] O. Y. Takeshita, “On maximum contention-free interleavers and permutation poly-
nomials over integer rings,” in IEEE Trans. Inform. Theory, vol. 52, no. 3, pp.
1249V1253, Mar. 2006.
[93] O. Y. Takeshita, “Permutation polynomial interleavers: an algebraic-geometric per-
spective,” in IEEE Trans. Inform. Theory, vol. 53, no. 6, pp. 2116-2132, Jun. 2007.
[94] R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, D. J. Costello “LDPC block
and convolutional codes based circulant matrices,” in IEEE Trans. Inform. Theory,
vol. 50, no. 12, pp. 2966-2984, Dec. 2004.
[95] A. Tarable, S. Benedetto, “Mapping interleaving laws to parallel turbo decoder
architectures,” in IEEE Commun. Letters, vol. 8, no. 3, pp. 162-164, Mar. 2004.
[96] A. Tarable, S. Benedetto, G. Montorsi, “Mapping interleaving laws to parallel turbo
and LDPC decoder architectures,” in IEEE Trans. Inform. Theory, vol. 50, no. 9,
pp. 2002-2009, Sep. 2004.
[97] M. Thul, N. Wehn, L. Rao, “Enabling high-throughput turbo-decoding throughput
concurrent interleaving,” in Proc. IEEE Int’l Sympo. on Circuits and Systems, pp.
897-900, Phoenix, USA, May 2002.
[98] M. J. Thul, F. Gilbert, N. Wehn, “Optimized concurrent interleaver for high-speed
turbo-decoding,” in Proc. IEEE Int’l Conf. on Electronics, Circuits and Systems,
Dubrovnik, Croatia, pp. 1099-1102, Sep. 2002.
[99] G. Ungerboeck, “Channel coding with multilevel/phase signals,” in IEEE Trans.
Inform. Theory, vol. 28, no. 1, pp. 55-67, Jan. 1982.
[100] G. Ungerboeck, “Trellis-coded modulation with redundant signal sets part I: in-
troduction,” in IEEE Commun. Magazine, vol. 25, no. 2, pp. 5-11, Feb. 1987.
[101] P. Urard, L. Paumier, M. Viollet, E. Lantreibecq, H. Michel, S. Muroor, B. Gupta,
“A generic 350Mb/s turbo-codec based on a 16-states SISO decoder,” in ISSCC Dig.
Tech. Papers, pp. 424-536, 2004.
[102] M. C. Valenti, J. Sun, “The UMTS turbo code and an e±cient decoder implemen-
tation suitable for software-defined radios,” in Int’l Journal of Wireless Information
Networks, vol. 8, no. 4, pp. 203-215, Oct. 2001.
[103] A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically opti-
mum decoding algorithm,” IEEE Trans. Inform. Theory, vol. 13, no 2, pp. 260-269,
Apr. 1967.
[104] A. J. Viterbi, “An intuitive justification and a simplified implementation of the
MAP decoder for convolutional codes,” IEEE J. Select. Areas Commun., vol. 16,
no. 2, pp. 260-264, Feb. 1998.
[105] K. Wu, H. Li, Y. Wang,“The influence of interleaver on the minimum distance of
turbo code,” in Electron. Lett., vol. 35, no. 17, pp. 1456-1458, Aug. 1999.
[106] C.Weiss, C. Bettstetter and S. Riedel, “Code construction and decoding of parallel
concatenated tail-biting codes,” IEEE Trans. Inform. Theory, Vol. 47, no. 1, pp.
366-386, Jan. 2001.
[107] C.Weiss, C. Bettstetter, S. Riedel, D. J. Costello, “Turbo decoding with tail-biting
trellis,” in ISSSE’98, Pisa, Italy, pp. 343-348, 1998.
[108] N. Wiberg, Codes and decoding on general graphs, Ph. D. thesis, Department of
Electrical Engineering, U. Linkoping, Sweden, 1996.
[109] S. B. Wicker, Error Control Systems for Disgital Communication and Storage 2nd,
Prentice Hall Internationl, Inc., 1995.
[110] S. Winograd, “On computing the discrete Fourier transform,” in Mathematics of
Computation, vol. 32, pp. 175-199, 1978.
[111] W. Wolf Modern VLSI Design-System on Chip Design 3rd, Baker & Taylor Books,
2002.
[112] C.-C Wong, C.-H. Tang, M.-W. Lai, Y.-X. Zheng, C.-C. Lin, H.-C. Chang, C.-
Y. Lee, Yu T. Su, “A 0.22nJ/iter 0.13µm turbo decoder chip using inter-block
permutation interleaver,” in Proc. IEEE CICC 2007, San Jose, California, USA,
Sep. 16-19, 2007.