Turbo码编译码器的研究与实现
摘要
Turbo码1993年诞生,以其优秀的抗噪声性能在无线通信系统中广泛应用。3GPP LTE(第三代通信系统长期演进),WiMAX(全球微波接入互操作)等无线通信标准化组织或技术纷纷将Turbo码作为自己的信道编码手段。而大规模数字集成电路技术的发展,使满足各种不同性能需求的Turbo编译码器在硬件上得以实现。
Turbo码译码算法常用的有软输出Viterbi(维特比)、Log_map(对数化最大后验概率算法)、Max_log_map(简化的最大后验概率算法)等,本文选择性能和复杂度折中的Max_log_map算法作为译法算法,并结合LTE系统规范下的二次置换多项式(QPP)交织器,分析和设计了Turbo编译码器。
本文在Matlab环境下,从算法选择、交织长度、迭代次数、数据量化及归一化等角度,对Turbo编译器的架构及算法进行仿真分析,确定适合FPGA实现的参数。在选定硬件实现参数的基础上,以FPGA：现场可编程门阵列)为目标平台,用硬件描述语言(HDL)对Turbo编译码器进行了寄存器传输级的(RTL)详细设计。在编码器方面,优化了QPP交织器的关键路径使编码电路的最高频率由130MHz提高到200MHz左右,再结合输入双缓冲机制提高了编码器的吞吐量。在译码器方面,通过合理的并行处理优化了软输入软输出计算模块的加比选关键路径,利用滑窗法减少了存储器的使用,在单个Turbo处理机译码的情况下,本设计的译码器吞吐量接近9Mbps。
Turbo-code was borned in 1993, which has found its way in wireless communication for its outstanding performance. Many Wireless Communication Standards Organization select Turbo-code as their channel codes, like 3GPP LTE, WiMAX, etc. As the developing of VLSI technology, the Turbo-codec meet different system requirements has been implemented in hard-ware.
The generally used decoding algorithm for Turbo-code include siso-Viterbi, LogMap, Max_Log_Map and so on. This thesis select QPP as the interleaver and use Max_Log_Map as the decoding algorithm for which has a more acceptable complexity and performance.
Also, some important parameters of Turbo-code like the length of interleaver, iteration times, quantitative of datas and normalized have been anylysised in Matlab. Then, a RTL design of Turbo-code has been done by Verilog-HDL with those special parameters above. Under the platform of FPGA,this thesis get a Turbo encoder with the maximum clock rate at 200MHz, by the optimization for QPP's critical path. As for Turbo-decoder, some ctitical path in SISO'S ACSO cicurit were been parallelzied, and the sliding-window method was employed to reduce the area of RAM and the dual-buffer mechanism was applyed in the Turbo-codec. Finally,this thesis get a Turbo-decoder with the throughput at 9Mbps.
Turbo码译码算法常用的有软输出Viterbi(维特比)、Log_map(对数化最大后验概率算法)、Max_log_map(简化的最大后验概率算法)等,本文选择性能和复杂度折中的Max_log_map算法作为译法算法,并结合LTE系统规范下的二次置换多项式(QPP)交织器,分析和设计了Turbo编译码器。
本文在Matlab环境下,从算法选择、交织长度、迭代次数、数据量化及归一化等角度,对Turbo编译器的架构及算法进行仿真分析,确定适合FPGA实现的参数。在选定硬件实现参数的基础上,以FPGA：现场可编程门阵列)为目标平台,用硬件描述语言(HDL)对Turbo编译码器进行了寄存器传输级的(RTL)详细设计。在编码器方面,优化了QPP交织器的关键路径使编码电路的最高频率由130MHz提高到200MHz左右,再结合输入双缓冲机制提高了编码器的吞吐量。在译码器方面,通过合理的并行处理优化了软输入软输出计算模块的加比选关键路径,利用滑窗法减少了存储器的使用,在单个Turbo处理机译码的情况下,本设计的译码器吞吐量接近9Mbps。
Turbo-code was borned in 1993, which has found its way in wireless communication for its outstanding performance. Many Wireless Communication Standards Organization select Turbo-code as their channel codes, like 3GPP LTE, WiMAX, etc. As the developing of VLSI technology, the Turbo-codec meet different system requirements has been implemented in hard-ware.
The generally used decoding algorithm for Turbo-code include siso-Viterbi, LogMap, Max_Log_Map and so on. This thesis select QPP as the interleaver and use Max_Log_Map as the decoding algorithm for which has a more acceptable complexity and performance.
Also, some important parameters of Turbo-code like the length of interleaver, iteration times, quantitative of datas and normalized have been anylysised in Matlab. Then, a RTL design of Turbo-code has been done by Verilog-HDL with those special parameters above. Under the platform of FPGA,this thesis get a Turbo encoder with the maximum clock rate at 200MHz, by the optimization for QPP's critical path. As for Turbo-decoder, some ctitical path in SISO'S ACSO cicurit were been parallelzied, and the sliding-window method was employed to reduce the area of RAM and the dual-buffer mechanism was applyed in the Turbo-codec. Finally,this thesis get a Turbo-decoder with the throughput at 9Mbps.
引文
[I]Shannon,C.E. A Mathematical Theory of Communication. Bell system technoledge Journal vlo.27,1948,pp623-657.
[2]Bernard Sklar著,徐平平等译.数字通信——基础与应用.北京：电子工业出版社2002.9.
[3]Elias,P. predictive coding.IEEE Trans.on information theory,vol.l march 1995.pp16-24.
[4]G.David forney,JR. the viterbi algorithm.Proceedings of IEEE,vol.61 No.3,March 1973,pp268-278.
[5]吴湛击著.现代纠错编码与调制理论及应用.北京：人民邮电出版社.12,2008.
[6]I.S.Reed,G.Solomon. Polynomial codes over certain finite fields.IEEE Journal of industrial and applied mathematics,vol.8,No.2,1960.
[7]Berrou,C.,Glavieux,A., Thitimajshima, P. Near Shannon limit:Turbo-codes.IEEE conf.on communications,vol.2,1993,pp1064-1070.
[8]D.J.C.MacKay,R.M. Neal.Near Shannon limit performance of Low Density Parity Check codes.IEEE eletronics letters,1996,pp1645-1646.
[9]Punya Thitimajshima. recursive systematic convolutional codes and application to parallel concatenation.IEEE global telecommunications conf.,vol.3,1995,pp2267-2272.
[10]S.Benedetto,G.Montorsi. role of recursive convolutional codes in turbo codes.IEEE electronics letters,vol.31,1995,pp858-859.
[11]Hagenauer J. etc all. iterative decoding of binary block and convolutional codes.IEEE Trans. On information theory,1996,pp429-445.
[12]Berrou,C.etc all. improving the distance properties of turbo codes using a third component code:3D turbo codes.IEEE Trans.on communications,vol.57,2009,pp2505-2509.
[13]L.R.Bahl,J.Cocke. optimal decoding of linear codes for minimizing symbol error rate.IEEE Trans.on information theory,vo120,1974,pp284-287.
[14]P.Robertson,E.villebrun,P.Hoeher. A comparison of optimal and suboptimal MAP decoding algorithms operating in the Log domain.IEEE Proc.of ICCC'95,1995,pp1009-1018.
[15]L.Lang,C.Y.Tsui, R.S.Cheng. Low power soft output viterbi decoder scheme for turbo code decoding. IEEE Proc. Int.Symp.on Circuits and Systems,Vo12,1997,pp1369-1372.
[16]P.Robertson,E. villebrun, and P.Hoeher. Comparison of optimal and sub-optimal map decoding algorithms operating in the log domain. IEEE Conf.on communications,1995.
[17]Talakoub,S. Shahrrava,B. A Linear log_map algorithm for turbo decoding over AWGN channels.IEEE Information technology conference,EIT 2004,pp293-296.
[18]Li Jianping,Cai Chaoshi,etc all. an adaptive turbo Decoding algorithm.IEEE wireless communications conference,WICOM'08 2008,pp1-3.
[19]C.Berrou,P.Combelles,etc all. An IC for Turbo-codes encoding and decoding.IEEE International solid-state circuits conference,session5,1995 pp9-9.
[20]Sangjin Hong,Wayne E.Stark. VLSI circuit complexity and decoding performance analysis for low-power rsc turbo-code and iterative block decoders design. IEEE Conf.of military communications,vol.3,1998,pp708-712.
[21]H.Dawid and H.Meyr. Real-time algorithms and VLSI architectures for soft output MAP convolutional decoding. IEEE Proc. Of Indoor and Mobile Radio communications, vol.1995,pp193-197.
[22]Seema Verma,Usha Landge. A concept paper on'VLSI Implementation of Turbo Decoders. IEEE military communications conference,vol.31998,pp708-712.
[23]Michael B.Purlsley,Jason S.Skinner. Adaptive coding for frequency-Hop transmission in Mobile Ad Hoc networks with Partial-Band interference. IEEE Trans. On communications, Vo1.57 march 2009,pp801-811.
[24]Roth,J.,Manjikian,N.,Sudharsanan,S. Performance optimization and parallelization of turbo decoding for software-defined radio. IEEE journal of Electrical and Computer engineering vol.34 2009,pp115-123.
[25]Jah-Ming Hsu,Chin-Liang Wang. A parallel decoding scheme for turbo codes. IEEE conference on Circuits and systems,vol.4 1998,pp445-448.
[26]Seokhyun Yoon,Bar-Ness,Y. A parallel Map algorithm for low latency turbo decoding. IEEE communitions letters,Vol.6 July 2002,pp288-290.
[27]A.Nimbalker,T.Keith Blankenship,etc all. contention-free interleavers for high-throughput turbo decoding. IEEE Trans. On communications,vol.56,2008,pp1258-1267.
[28]Oscar Y. Takeshita. A new metric for permutation ploynomial interleavers. IEEE ISIT 2006,Seattle,USA,2006,pp1983-1987.
[29]Jing Sun,Oscar Y.Takeshita. interleavers for turbo codes using permutation polynomials over integer rings. IEEE Trans. On information theory,vol.51 2005,pp101-119.
[30]Jonghoon ryu,Oscar Y.Takeshita. on quadratic inverses for quadratic permutation polynomials over integer rings. IEEE Trans. On information theory,vol.52 2006,pp1254-1260.
[31]胡宏林,徐景著.3GPP LTE无线链路关键技术.北京：电子工业出版社,2008.
[32]Altera.Ltd.3GPP LTE Turbo reference design. www.altera.com/,2010.
[33]Xilinx.Ltd. Tcc deocder 3GPP LTE. www.xilinx.com/products/,2009.
[34]Studer,C. Benkeser,C etc all. A 390Mb/s 3.57mm23GPP-LTE turbo decoder ASIC in 0.13um CMOS. IEEE Solid-state Circuits conference Digest of technicalPapers,2010,P274-275.
[35]3GPP Technical Specification Group Radio Access Network;E-UTRA.3GPP TS 36.212,Release 8.1.0.2007,11.
[36]柯德军,徐友云.删余Turbo码的交织删余的综合设计研究.信息技术,2006年11期,pp5-8.
[37]刘东华著.Turbo码原理与应用技术.北京：电子工业出版社,2004,1.
[38]柯召,孙琦著.数论讲义(下).北京：高等教育出版社.1987,5.
[39]Nimbalker, A.; Blankenship, Y.etc all. ARP and QPP Interleavers for LTE Turbo Coding. IEEE Wireless communications conference,WCNC 2008,pp1032-1037.
[40]Jung-fu Cheng,Cary. QPP interleaver/de-interleaver for Turbo Codes. US pantent,AI,2008/0115034.
[41]John B.Andersion,Stephen M.Hladik. Tailbiting MAP Decoders. IEEE Journal on selected areas in communications,vol.16,Feb.1998.
[42]Ying Wang,xinjun du;Hui Li;Xiaoyan Zhu. tail-biting theory for turbo codes. IEEE Annual WAMICON'062006,pp1-4.
[43]Patrick Robertson,Peter Hoeher,Emmanuelle villeburm. Optimal and sub-optimal Maximum A Posteriori Algorithms Suitable for Turbo Decoding. European.Trans.Telecomm,vol.8 1997,pp119-125.
[44]F.Raouafi,A.Dingninou,C.Berrou. Saving memory in turbo-decoders using the Max_Log_Map algorithm. Turbo codes in digital broadcasting,IEEE Colloquium,Nov.1999,pp1-4.
[45]Johannes Steensma,Chris Dick. FPGA implementation of a 3GPP Turbo Codec. IEEE signals,Systems and computers Conference Record,vol.12001,pp61-65.
[46]Peter H.-Y. Wu and Stephen M.Pisuk. Implementation of a low complexity,low power, integer-based turbo decoder. IEEE global telecommunications conference,vol.22001,pp946-951.
[47]wayne wolf著,闫敬文等译.基于FPGA的系统设计.北京：机械工业出版社,2006.
[2]Bernard Sklar著,徐平平等译.数字通信——基础与应用.北京：电子工业出版社2002.9.
[3]Elias,P. predictive coding.IEEE Trans.on information theory,vol.l march 1995.pp16-24.
[4]G.David forney,JR. the viterbi algorithm.Proceedings of IEEE,vol.61 No.3,March 1973,pp268-278.
[5]吴湛击著.现代纠错编码与调制理论及应用.北京：人民邮电出版社.12,2008.
[6]I.S.Reed,G.Solomon. Polynomial codes over certain finite fields.IEEE Journal of industrial and applied mathematics,vol.8,No.2,1960.
[7]Berrou,C.,Glavieux,A., Thitimajshima, P. Near Shannon limit:Turbo-codes.IEEE conf.on communications,vol.2,1993,pp1064-1070.
[8]D.J.C.MacKay,R.M. Neal.Near Shannon limit performance of Low Density Parity Check codes.IEEE eletronics letters,1996,pp1645-1646.
[9]Punya Thitimajshima. recursive systematic convolutional codes and application to parallel concatenation.IEEE global telecommunications conf.,vol.3,1995,pp2267-2272.
[10]S.Benedetto,G.Montorsi. role of recursive convolutional codes in turbo codes.IEEE electronics letters,vol.31,1995,pp858-859.
[11]Hagenauer J. etc all. iterative decoding of binary block and convolutional codes.IEEE Trans. On information theory,1996,pp429-445.
[12]Berrou,C.etc all. improving the distance properties of turbo codes using a third component code:3D turbo codes.IEEE Trans.on communications,vol.57,2009,pp2505-2509.
[13]L.R.Bahl,J.Cocke. optimal decoding of linear codes for minimizing symbol error rate.IEEE Trans.on information theory,vo120,1974,pp284-287.
[14]P.Robertson,E.villebrun,P.Hoeher. A comparison of optimal and suboptimal MAP decoding algorithms operating in the Log domain.IEEE Proc.of ICCC'95,1995,pp1009-1018.
[15]L.Lang,C.Y.Tsui, R.S.Cheng. Low power soft output viterbi decoder scheme for turbo code decoding. IEEE Proc. Int.Symp.on Circuits and Systems,Vo12,1997,pp1369-1372.
[16]P.Robertson,E. villebrun, and P.Hoeher. Comparison of optimal and sub-optimal map decoding algorithms operating in the log domain. IEEE Conf.on communications,1995.
[17]Talakoub,S. Shahrrava,B. A Linear log_map algorithm for turbo decoding over AWGN channels.IEEE Information technology conference,EIT 2004,pp293-296.
[18]Li Jianping,Cai Chaoshi,etc all. an adaptive turbo Decoding algorithm.IEEE wireless communications conference,WICOM'08 2008,pp1-3.
[19]C.Berrou,P.Combelles,etc all. An IC for Turbo-codes encoding and decoding.IEEE International solid-state circuits conference,session5,1995 pp9-9.
[20]Sangjin Hong,Wayne E.Stark. VLSI circuit complexity and decoding performance analysis for low-power rsc turbo-code and iterative block decoders design. IEEE Conf.of military communications,vol.3,1998,pp708-712.
[21]H.Dawid and H.Meyr. Real-time algorithms and VLSI architectures for soft output MAP convolutional decoding. IEEE Proc. Of Indoor and Mobile Radio communications, vol.1995,pp193-197.
[22]Seema Verma,Usha Landge. A concept paper on'VLSI Implementation of Turbo Decoders. IEEE military communications conference,vol.31998,pp708-712.
[23]Michael B.Purlsley,Jason S.Skinner. Adaptive coding for frequency-Hop transmission in Mobile Ad Hoc networks with Partial-Band interference. IEEE Trans. On communications, Vo1.57 march 2009,pp801-811.
[24]Roth,J.,Manjikian,N.,Sudharsanan,S. Performance optimization and parallelization of turbo decoding for software-defined radio. IEEE journal of Electrical and Computer engineering vol.34 2009,pp115-123.
[25]Jah-Ming Hsu,Chin-Liang Wang. A parallel decoding scheme for turbo codes. IEEE conference on Circuits and systems,vol.4 1998,pp445-448.
[26]Seokhyun Yoon,Bar-Ness,Y. A parallel Map algorithm for low latency turbo decoding. IEEE communitions letters,Vol.6 July 2002,pp288-290.
[27]A.Nimbalker,T.Keith Blankenship,etc all. contention-free interleavers for high-throughput turbo decoding. IEEE Trans. On communications,vol.56,2008,pp1258-1267.
[28]Oscar Y. Takeshita. A new metric for permutation ploynomial interleavers. IEEE ISIT 2006,Seattle,USA,2006,pp1983-1987.
[29]Jing Sun,Oscar Y.Takeshita. interleavers for turbo codes using permutation polynomials over integer rings. IEEE Trans. On information theory,vol.51 2005,pp101-119.
[30]Jonghoon ryu,Oscar Y.Takeshita. on quadratic inverses for quadratic permutation polynomials over integer rings. IEEE Trans. On information theory,vol.52 2006,pp1254-1260.
[31]胡宏林,徐景著.3GPP LTE无线链路关键技术.北京：电子工业出版社,2008.
[32]Altera.Ltd.3GPP LTE Turbo reference design. www.altera.com/,2010.
[33]Xilinx.Ltd. Tcc deocder 3GPP LTE. www.xilinx.com/products/,2009.
[34]Studer,C. Benkeser,C etc all. A 390Mb/s 3.57mm23GPP-LTE turbo decoder ASIC in 0.13um CMOS. IEEE Solid-state Circuits conference Digest of technicalPapers,2010,P274-275.
[35]3GPP Technical Specification Group Radio Access Network;E-UTRA.3GPP TS 36.212,Release 8.1.0.2007,11.
[36]柯德军,徐友云.删余Turbo码的交织删余的综合设计研究.信息技术,2006年11期,pp5-8.
[37]刘东华著.Turbo码原理与应用技术.北京：电子工业出版社,2004,1.
[38]柯召,孙琦著.数论讲义(下).北京：高等教育出版社.1987,5.
[39]Nimbalker, A.; Blankenship, Y.etc all. ARP and QPP Interleavers for LTE Turbo Coding. IEEE Wireless communications conference,WCNC 2008,pp1032-1037.
[40]Jung-fu Cheng,Cary. QPP interleaver/de-interleaver for Turbo Codes. US pantent,AI,2008/0115034.
[41]John B.Andersion,Stephen M.Hladik. Tailbiting MAP Decoders. IEEE Journal on selected areas in communications,vol.16,Feb.1998.
[42]Ying Wang,xinjun du;Hui Li;Xiaoyan Zhu. tail-biting theory for turbo codes. IEEE Annual WAMICON'062006,pp1-4.
[43]Patrick Robertson,Peter Hoeher,Emmanuelle villeburm. Optimal and sub-optimal Maximum A Posteriori Algorithms Suitable for Turbo Decoding. European.Trans.Telecomm,vol.8 1997,pp119-125.
[44]F.Raouafi,A.Dingninou,C.Berrou. Saving memory in turbo-decoders using the Max_Log_Map algorithm. Turbo codes in digital broadcasting,IEEE Colloquium,Nov.1999,pp1-4.
[45]Johannes Steensma,Chris Dick. FPGA implementation of a 3GPP Turbo Codec. IEEE signals,Systems and computers Conference Record,vol.12001,pp61-65.
[46]Peter H.-Y. Wu and Stephen M.Pisuk. Implementation of a low complexity,low power, integer-based turbo decoder. IEEE global telecommunications conference,vol.22001,pp946-951.
[47]wayne wolf著,闫敬文等译.基于FPGA的系统设计.北京：机械工业出版社,2006.