臺灣博碩士論文加值系統

本論文探討使用平行架構及無競爭式交錯器之渦輪碼解碼器來達到高速的資料輸出量。我們首先分析傳統平行架構的方法，整理各個方法的優缺點，也列出影響資料輸出量的關鍵因素。文中的討論主要是針對採用多個soft-in soft-out (SISO)處理器來對單一個接收到的字碼進行解碼這種技術所衍生出的議題。除了增加SISO處理器的數目之外，我們也結合了其他平行架構的方法來大幅提昇速度。然而，該方法將會導致相當高的硬體複雜度及降低處理器的運算效能。為了解決複雜度的問題，本論文介紹了兩種多層級的網路系統來負責平行解碼器中所有SISO處理器與記憶體之間的資料傳輸。這兩個網路系統分別支援採用inter-block permutation (IBP)交錯器及quadratic permutation polynomial (QPP)交錯器之渦輪碼解碼器。此多層級網路連結系統可以有效地降低實作時平行架構電路的繞線複雜度。至於另一個難題，則須透過調整處理器的執行程序來解決。我們提出兩套可防止資料相關性造成低運算效能的策略，並制定了各自對應的處理器執行程序。在這兩種高效能的程序中，其一是針對廣泛應用進行的設計，而另一則只能在特定的條件下使用。它們縮短了解碼流程中各個功能單元的閒置時間；因此，SISO處理器的運算效能得到了改善。

基於上述之各項技術，我們實作了四個平行架構之渦輪碼解碼器。當中有兩個採用了IBP交錯器以及對應的多層級網路系統；它們皆使用了多個SISO處理器，且每個處理器在一個時脈週期中可處理複數筆資料；其中一個還利用了廣泛用途的高效能程序，讓硬體不會進入閒置的狀態。第三個解碼器則使用QPP交錯器和第二種網路連結系統；藉由這個裝置，再加上適當的控制電路，該解碼器最多可提供八個平行SISO處理器來支援在第三代合作伙伴計劃長期演進技術規格中所函括的全部區塊長度之渦輪碼解碼。最後一個解碼器亦使用QPP交錯器和多層級網路；它比其他三個解碼器有更高的平行度；另一方面，因為符合另一個高效能程序的限制條件，它也具備最高的處理器運算效能；這個解碼器的資料輸出量可達到1.4 Gb/s。實驗結果顯示我們所提的方法能夠得到預期的成效，也使得平行架構解碼器的速度有顯著的提昇。

This dissertation investigates the turbo decoders with parallel architecture and contention-free interleaver in pursuit of high throughput with reasonable cost. The benefits and disadvantages of conventional parallel schemes are examined; then the essential factors for throughput calculation are determined. Our discussions put emphasis on using multiple soft-in soft-out (SISO) decoders for single codeword. In addition to increasing the parallelism, the hybrid of parallel schemes is further applied for more speedup. However, the methodology leads to considerable complexity and inefficiency of processor. To reduce the complexity, we develop the multi-stage networks for the parallel data transmission in the turbo decoder. Two different types of apparatus are proposed for the designs using inter-block permutation (IBP) interleaver and quadratic permutation polynomial (QPP) interleaver, respectively. They can alleviate the routing congestion in the parallel design. To overcome the other difficulty, the processing schedule must be modified. We propose two different strategies to remove the data dependency and set their corresponding highefficiency schedules. One of them is aimed for general application, whereas the other is designed for specific case. The inactive periods within the decoding flow are greatly shortened in these schedules. Hence, the efficiency of the SISO decoder can increase.

Four implemented works are presented in this dissertation. The multi-stage interconnection for IBP interleavers is applied to the first two parallel turbo decoders. Both the two designs contain multiple SISO decoders, each of which can process two or more symbols per cycle. One of them operates with the general high-efficiency schedule, and its idle time is completely removed. The third design exploits another interconnection for QPP interleavers. With such apparatus and appropriate control flow, it can use at most 8 SISO decoders to decodes all codeword blocks defined in the 3rd Generation Partnership Project Long Term Evolution standard. The remaining design also adopts QPP interleavers and the multi-stage network. It has higher parallelism than the other designs; moreover, its support of specific high-efficiency schedule results in the best efficiency. This design can achieve 1.4 Gb/s while decoding size-4096 blocks for 8 iterations. The implementation results reveal that the proposed methods work successfully in the parallel architecture and raise the throughput significantly.

Chapter 1 Introduction 1
Chapter 2 Turbo Code 5
2.1 Overview of convolutional codes 6
2.1.1 Convolutional codes and encoders 6
2.1.2 The maximum a posteriori probability algorithm 10
2.2 Turbo code design 19
2.2.1 Parallel concatenated convolutional code 19
2.2.2 Iterative decoding flow 23
2.3 Practical turbo decoder architecture 27
Chapter 3 Parallel Architecture and Interleaver 37
3.1 Parallel turbo decoder architecture 37
3.1.1 Turbo decoder level 37
3.1.2 SISO decoder level 38
3.1.3 Trellis stage level 41
3.2 IBP interleaver and interconnection 45
3.3 QPP interleaver and interconnection 49
Chapter 4 High-Efficiency Processing Schedule 56
4.1 Interlaced half-iterations 56
4.2 Overlapping half-iterations 59
4.2.1 Interleaver constraints of such schedule 60
4.2.2 Performance and process of such schedule 65
Chapter 5 Implementation Results 70
5.1 Hybrid parallel design using IBP interleaver 70
5.2 Reconfigurable design for 3GPP LTE system 74
5.3 Full-efficiency design using QPP interleaver 81
Chapter 6 Conclusion 86
6.1 Summary 86
6.2 Future work 88
References 89

[1] C. E. Shannon, “A mathematical theory of communication,” Bell Syst. Tech. J., vol. 27, pp. 379–428(Part I), Jul. 1948.
[2] ——, “A mathematical theory of communication,” Bell Syst. Tech. J., vol. 27, pp. 623–656(Part II), July 1948.
[3] R. J. McEliece, The theory of information and coding, 2nd ed. Cambridge, UK: Cambridge University Press, 2004.
[4] S. Lin and D. J. Costello, Jr., Error control coding: fundamentals and applications, 2nd ed. Englewood Cliffs, NJ: Pearson-Hall, 2004.
[5] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: turbo-codes,” in IEEE Proc. Int. Conf. Communications, May 1993, pp. 1064–1070.
[6] D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electronics Letters, vol. 33, no. 6, pp. 457–458, Mar. 1997.
[7] B. Vucetic and J. Yuan, Turbo codes: principles and applications. Boston, MA: Kluwer Academic, 2000.
[8] D. J. Costello, Jr. and G. D. Forney, Jr., “Channel coding: The road to channel capacity,” Proc. IEEE, vol. 95, no. 6, pp. 1150–1177, Jun. 2007.
[9] E. Boutillon, C. Douillard, and G. Montorsi, “Iterative decoding of concatenated convolutional codes: Implementation issues,” Proc. IEEE, vol. 95, no. 6, pp. 1201–1227, Jun. 2007.
[10] K. Gracie and M.-H. Hamon, “Turbo and turbo-like codes: Principles and applications in telecommunications,” Proc. IEEE, vol. 95, no. 6, pp. 1228–1254, Jun. 2007.
[11] B. Vucetic, Y. Li, L. C. Perez, and F. Jiang, “Recent advances in turbo code design and theory,” Proc. IEEE, vol. 95, no. 6, pp. 1323–1344, Jun. 2007.
[12] Technical Specification Group Radio (3GPP) Access Network; Multiplexing and channel coding (FDD), 3GPP Std. TS 25.212, Rev. 8.0.0, 2007.
[13] Physical Layer Standard for CDMA2000 Spread Spectrum Systems, 3GPP2 Std. C.S0002-C, 2002.
[14] Local and Metropolitan Area Network Part 16: Air Interface for Fixed Broadband Wireless Access Systems, IEEE Std. 802.16e/D11, 2005.
[15] Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access; Multiplexing and channel coding (Release 8), 3GPP Std. TS 36.212, Rev. 8.5.0, Dec. 2008.
[16] L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inf. Theory, vol. IT-20, pp. 284–287, Mar. 1974.
[17] P. Elias, “Coding for noisy channels,” IRE Conv. Rec., vol. pt.4, pp. 37–47, 1955.
[18] G. D. Forney, Jr., “Convolutional codes I: algebraic structure,” IEEE Trans. Inf. Theory, vol. IT-16, pp. 720–738, Nov. 1970.
[19] R. Johannesson and Z. X. Wan, “A linear algebra approach to minimum convolutional encoders,” IEEE Trans. Inf. Theory, vol. 39, no. 4, pp. 37–47, Jul. 1993.
[20] A. J. Viterbi, “Error bounds for convolutional codes and asymptotically optimum decoding algorithm,” IEEE Trans. Inf. Theory, vol. IT-13, no. 2, pp. 260–269, Apr. 1967.
[21] J. Hagenauer, E. Offer, and L. Papke, “Iterative decoding of binary block and convolutional codes,” IEEE Trans. Inf. Theory, vol. 42, no. 2, pp. 429–445, Mar. 1996.
[22] P. Robertson, E. Villebrun, and P. Hoeher, “A comparison of optimal and suboptimal decoding algorithm,” in IEEE Proc. Int. Conf. Communications, Jun. 1995, pp. 1009–1013.
[23] J. A. Erfanian, S. Pasupathy, and G. Gulak, “Reduced complexity symbol detectors with parallel structures for ISI channels,” IEEE Trans. Commun., vol. 42, no. 2/3/4, pp. 1261–1271, Feb./Mar./Apr. 1994.
[24] S. A. Barbulescu, “Iterative decoding of turbo codes and other concatenated codes,”Ph.D. dissertation, Univ. South Australia, 1996.
[25] A. J. Viterbi, “An intuitive justification and a simplified implementation of the MAP decoder for convolutional codes,” IEEE J. Sel. Areas Commun., vol. 16, no. 2, pp. 260–264, Feb. 1998.
[26] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near optimum error correcting coding and decoding: turbo-codes,” IEEE Trans. Commun., vol. 44, no. 10, pp. 1261–1271, Oct. 1996.
[27] C. WeiB, C. Bettstetter, S. Riedel, and D. J. Costello, “Turbo decoding with tailbiting trellises,” in IEEE Proc. URSI Int. Symp. Signals, Systems, and Electronics, Oct. 1998, pp. 343–348.
[28] S. Benedetto and G. Montorsi, “Unveiling turbo codes: Some results on parallel concatenated coding schemes,” IEEE Trans. Inf. Theory, vol. 42, no. 2, pp. 409–428, Mar. 1996.
[29] S. Benedetto, G. Montorsi, and D. Divsalar, “Concatenated convolutional codes with interleavers,” IEEE Commun. Mag., vol. 41, no. 8, pp. 102–109, Aug. 2003.
[30] H. R. Sadjadpour, N. J. A. Sloane, M. Salehi, and G. Nebe, “Interleaver design for turbo codes,” IEEE J. Sel. Areas Commun., vol. 19, no. 5, pp. 831–837, May 2001.
[31] T. A. Summers and S. G. Wilson, “SNR mismatch and online estimation in turbo decoding,” IEEE Trans. Commun., vol. 46, no. 4, pp. 421–423, Apr. 1998.
[32] A. Worm, P. Hoeher, and N. Wehn, “Turbo-decoding without SNR estimation,”IEEE Commun. Lett., vol. 4, no. 6, pp. 193–195, Jun. 2000.
[33] J. Vogt and A. Finger, “Improving the Max-Log-MAP turbo decoder,” IET Electronics Letters, vol. 36, no. 23, pp. 1937–1937, Nov. 2000.
[34] P. H. Y. Wu and S. M. Pisuk, “Implementation of a low complexity, low power, integer-based turbo decoder,” in IEEE Global Telecommunications Conf., Nov. 2001, pp. 946–951.
[35] Y. Wu, B. D. Woener, and T. K. Blankenship, “Data width requirements in SISO decoding with modulo normalization,” IEEE Trans. Commun., vol. 49, no. 11, pp. 1861–1868, Nov. 2001.
[36] T. K. Blankenship and B. Classon, “Fixed-point performance of low-complexity turbo decoding algorithms,” in IEEE Vehic. Tech. Conf., May 2001, pp. 1483–1487.
[37] A. P. Hekstra, “An alternative to metric rescaling in Viterbi decoders,” IEEE Trans. Commun., vol. 37, no. 11, pp. 1220–1222, Nov. 1989.
[38] C. B. Shung, P. H. Siegel, G. Ungerboeck, and H. K. Thapar, “VLSI architectures for metric normalization in the Viterbi algorithm,” in IEEE Proc. Int. Conf. Communications, vol. 4, Atlanta, CA, Apr. 1990, pp. 1723–1728.
[39] J. H. Han, A. T. Erdogan, and T. Arslan, “High speed Max-Log-MAP turbo SISO decoder implementation using branch metric normalization,” in IEEE Computer Society Annual Symp. VLSI, 2005, pp. 173–178.
[40] I. Lee and J. L. Sonntag, “A new architecture for the fast Viterbi algorithm,” IEEE Trans. Commun., vol. 51, no. 10, pp. 1624–1628, Oct. 2003.
[41] R. Y. Shao, S. Lin, and P. C. Fossorier, “Two simple stopping criteria for turbo decoding,” IEEE Trans. Commun., vol. 47, no. 8, pp. 1117–1120, Aug. 1999.
[42] Y. Wu, B. D. Woener, and W. J. Ebel, “A simple stopping criteria for turbo decoding,”IEEE Commun. Lett., vol. 4, no. 8, pp. 258–260, Aug. 2000.
[43] G. Masra, G. Piccinini, M. R. Roch, and M. Zamboni, “VLSI architecture for turbo codes,” IEEE Trans. VLSI Syst., vol. 7, no. 3, pp. 369–379, Sep. 1999.
[44] G. Masera, M. Mazza, G. Piccinini, F. Viglione, and M. Zamboni, “Architectural strategies for low-power VLSI turbo decoders,” IEEE Trans. VLSI Syst., vol. 10, no. 3, pp. 279–285, Jun. 2002.
[45] S. Yoon and Y. Bar-Ness, “A parallel MAP algorithm for low latency turbo decoding,”IEEE Commun. Lett., vol. 6, no. 7, pp. 288–290, Jul. 2002.
[46] Z. He, P. Fortier, and S. Roy, “Highly-parallel decoding architecture for convolutional turbo codes,” IEEE Trans. VLSI Syst., vol. 14, no. 10, pp. 1147–1151, Oct. 2006.
[47] R. Dobkin, M. Peleg, and R. Ginosar, “Parallel VLSI architecure for MAP turbo decoder,” in IEEE Int. Symp. Personal, Indoor and Mobile Radio Communications, Sep. 2002, pp. 15–18.
[48] M. Bickerstaff, L. Davis, C. Thomas, D. Garrett, and C. Nicol, “A 24Mb/s radix-4 LogMAP turbo decoder for 3GPP-HSDPA mobile wireless,” in IEEE Int. Solid-State Circuit Conf., Feb. 2003, pp. 151–484.
[49] C. Benkeser, A. Burg, T. Cupaiuolo, and Q. Huang, “A 58mw 1.22mm2 HSDPA turbo decoder ASIC in 0.13um cmos,” in IEEE Int. Solid-State Circuit Conf., Feb. 2008, pp. 264–266.
[50] O. Muller, A. Baghdadi, and M. Jezequel, “Exploring parallel processing levels for convolutional turbo decoding,” in 2nd Information and Communication Technologies, Apr. 2006, pp. 2353–2358.
[51] Y.-X. Zheng and Y.-T. Su, “A new interleaver design and its application to turbo codes,” in Proc. IEEE Vehicular Technology Conf., vol. 3, Sep. 2002, pp. 1437–1441.
[52] O. Y. Takeshita, “On maximum contention-free interleavers and permutation polynomials over integer rings,” IEEE Trans. Inf. Theory, vol. 52, no. 3, pp. 1249–1253, Mar. 2006.
[53] M. J. Thul, N. Wehn, and L. P. Rao, “Enabling high-speed turbo decoding through concurrent interleaving,” in IEEE Proc. Int. Symp. Circuits and Systems, May 2002, pp. 26–29.
[54] A. Tarable, S. Benedetto, and G. Montorsi, “Mapping interleaving laws to parallel turbo and LDPC decoder architecture,” IEEE Trans. Inf. Theory, vol. 50, no. 9, pp. 2002–2009, Sep. 2004.
[55] A. Giulietti, L. V. der Perre, and M. Strum, “Parallel turbo coding interleavers: Avoiding collisions in accesses to storage elements,” Elec. Lett., vol. 38, no. 5, pp.232–234, Feb. 2002.
[56] D. Gnaedig, E. Boutillon, M. Jezequel, V. C. Gaudet, and P. G. Gulak, “On multiple slice turbo code,” in Proc. 3rd Int. Symp. Turbo Codes and Related Topics, Sep. 2003, pp. 343–346.
[57] A. Abbasfar and K. Yao, “Interleaver design for high speed turbo decoders,” in IEEE Wireless Communications and Networking Conf., Mar. 2004, pp. 1611–1615.
[58] L. Dinoi and S. Benedetto, “Variable-size interleaver design for parallel turbo decoder architectures,” in IEEE Global Telecommunications Conf., Nov. 2004, pp. 3108–3112.
[59] Z. He, S. Roy, and P. Fortier, “High speed and low power design of parallel turbo decoder,” in IEEE Proc. Int. Symp. Circuits and Systems, 2005, pp. 6018–6021.
[60] G. Prescher, T. Gemmeke, and T. Noll, “A parameterizable low-power highthroughput turbo decoder,” in IEEE Int. Acoustics, Speech, and Signal Processing Conf., Mar. 2005, pp. V/25–V/28.
[61] H. Moussa, O. Muller, A. Baghdadi, and M. Jezequel, “Butterfly and bene-based on-chip communication networks for multiprocessor turbo decoding,” in Design, Automation and Test in Europe Conference and Exhibition, Apr. 2007, pp. 1–6.
[62] R. Dobkin, M. Peleg, and R. Ginosar, “Parallel interleaver design and VLSI architecture for low-latency MAP turbo decoders,” IEEE Trans. VLSI Syst., vol. 13, no. 4, pp. 427–438, Apr. 2005.
[63] D. Gnaedig, E. Boutillon, J. Tousch, and M. Jezequel, “Towards an optimal parallel decoding of turbo codes,” in Proc. 4th Int Symp. Turbo Codes Related Topics, Apr. 2006.
[64] P. J. Black and T. H. Meng, “A 140 Mb/s, 32-state, radix-4 Viterbi decoder,” IEEE Commun. Lett., vol. 27, no. 12, pp. 1877–1885, Dec. 1992.
[65] H. Dawid, G. Fettweis, and H. Meyr, “A CMOS IC for Gb/s Viterbi decoding: system design and VLSI implementation,” IEEE Trans. VLSI Syst., vol. 4, no. 1, pp. 17–31, Mar. 1996.
[66] C. C. Lin, C. C. Wu, and C. Y. Lee, “A low power and high speed Viterbi decoder chip for WLAN applications,” in Proc. 29th Europe Solid State Circuits Conf., Sep. 2003, pp. 723–726.
[67] M. Anders, S. Mathew, R. Krishnamurthy, and S. Borkar, “A 64-state 2GHz 500Mbps 40mW Viterbi accelerator in 90nm CMOS,” in Symop. VLSI Circuits Dig. Tech. Papers, 2004, pp. 174–175.
[68] S. W. Choi and S. S. Choi, “200Mbps Viterbi decoder for UWB,” in Int. Conf. Advanced Communication Tech., vol. 2, 2005, pp. 904–907.
[69] C.-L. Chen, “High-speed Viterbi decoder based on the two-dimensional ACS structure,” Master’s thesis, National Chiao-Tung University, 2005.
[70] C.-C. Lin, “Channel decoder design and implementation,” Ph.D. dissertation, National Chiao-Tung University, 2006.
[71] C.-H. Tang, C.-C. Wong, C.-L. Chen, C.-C. Lin, and H.-C. Chang, “A 952Mb/s Max-Log MAP decoder chip using radix-4x4 ACS architecture,” in IEEE Asian Solid-State Circuits Conf., Nov. 2006, pp. 79–82.
[72] S. Crozier, J. Lodge, P. Guinand, and A. Hunt, “Performance of turbo codes with relative prime and golden interleaving strategies,” in 6th Int. Mobile Satellite Conf., Jun. 1999, pp. 268–275.
[73] C.-C. Wong, C.-H. Tang, M.-W. Lai, Y.-X. Zheng, C.-C. Lin, H.-C. Chang, C.-Y. Lee, and Y. T. Su, “A 0.22nJ/b/iter 0.13um turbo decoder chip using inter-block permutation interleaver,” in IEEE Custom Integrated Circuits Conf., Sep. 2007, pp. 273–276.
[74] J. Ryu and O. Y. Takeshita, “On quadratic inverse for quadratic permutation polynomials over integer rings,” IEEE Trans. Inf. Theory, vol. 52, no. 3, pp. 1254–1260, Mar. 2006.
[75] R. Asghar, D. Wu, J. Eilert, and D. Liu, “Memory conflict analysis and implementation of a re-configurable interleaver architecture supporting unified parallel turbo decoding,” Journal of Signal Processing Systems, vol. 60, no. 1, pp. 15–29, Jul. 2010.
[76] I. Ahmed and C. Vithanage, “Dynamic reconfiguration approach for high speed turbo decoding using circular rings,” in Proceedings of the 19th ACM Great Lakes symposium on VLSI, May 2009, pp. 475–480.
[77] C.-C. Wong, Y.-Y. Lee, and H.-C. Chang, “A 188-size 2.1mm2 reconfigurable turbo decoder chip with parallel architecture for 3GPP LTE system,” in Symposium on VLSI Circuits, Jun. 2009, pp. 288–289.
[78] S. Dolinar and D. Divsalar, “Weight distribution of turbo codes using random and nonrandom permutations,” Jet Propulsion Lab., TDA Progress Report 42-122, Aug. 1995.
[79] S. Crozier, “New high-spread high-distance interleavers for turbo-codes,” in Proc. 20th Bienn. Symp. Communications, May 2000, pp. 3–7.
[80] S. Crozier, P. Guinand, and A. Hunt, “Estimating the minimum distance of turbo codes using double and triple impulse methods,” IEEE Commun. Lett., vol. 9, no. 7, pp. 631–633, Jul. 2005.
[81] C.-C. Wong, M.-W. Lai, C.-C. Lin, H.-C. Chang, and C.-Y. Lee, “Turbo decoder using contention-free interleaver and parallel architecture,” IEEE J. Solid-State Circuits, vol. 45, no. 2, pp. 422–432, Feb. 2010.
[82] C.-C. Wong and H.-C. Chang, “Reconfigurable turbo decoder with parallel architecture for 3GPP LTE system,” IEEE Trans. Circuits Syst. II, vol. 57, no. 7, pp. 566–570, Jul. 2010.
[83] Y. Sun, Y. Zhu, M. Goel, and J. R. Cavallaro, “Configurable and scalable high throughput turbo decoder architecture for multiple 4G wireless standard,” in IEEE Int. Conf. on Application-Specific Systems, Architectures and Processors, Jul. 2008, pp. 209–214.
[84] C.-H. Lin, C.-Y. Chen, A.-Y. Wu, and T.-H. Tsai, “Low-power memory reduced traceback MAP decoding for double-binary convolutional turbo decoder,” IEEE Trans. Circuits Syst. I, vol. 56, no. 5, pp. 1005–1016, May 2009.