Turbo码编译码方法研究与实现
|
摘要
Turbo码，又称并行级联卷积码(PCCC)，是由C.Berrou等在1993年ICC会议上提出的。当时的模拟结果表明，如果采用大小为65535的随机交织器，并且进行18次迭代，则在E_b/N_o≥0.7dB时，码率为1/2的Turbo码在AWGN信道上的误比特率(BER)≤10~(-5)，达到了近Shannon限的性能。尽管目前对Turbo码算法性能还缺乏有效的理论解释，但Turbo码已经被看作自1982年TCM技术问世以来信道编码理论上一项伟大的技术成就，而且它重要的编译码思想正引起众多学者的关注和兴趣。
本文对Turbo码的研究工作主要集中在以下几个方面：
对Turbo码的编译码方法进行研究。Turbo码是建立在一种特殊的系统卷积码的基础上的，它以两个RSC码作为它的分量码，因此分量码的选取对Turbo码的性能有重要的影响。本文主要使用了16状态的(37，21)原始码型和8状态的(15，13)码型。Turbo码的译码算法主要有MAP算法和SOVA算法两大类，本文重点研究了前者。
研究了几种在MAP算法基础上的改进算法。由于MAP算法存在巨大的计算量和时延，为了克服MAP算法的缺点，研究了MAP算法的对数域内的简化算法Log-MAP算法以及滑动窗MAP算法。为了避免短帧情况下trellis的结束带来的译码性能的降低，本文把一种新颖的MAP译码结构应用到Log-MAP中并进行了计算机模拟，模拟结果表明短帧情况下这种新结构的译码方法在性能方面略有改进。
交织器对于Turbo码的性能有重大的影响，文中给出了Turbo码交织器的设计原则，对几种常用的Turbo码交织器的原理和实现方法进行了研究，进行了计算机模拟并对其性能进行了分析比较。
其它诸如trellis结尾问题、删余矩阵的设计、TCM调制等方面，本文给出了初步介绍，详细可查阅文献。
Turbo码现在正得到越来越广泛的应用，但是由于理论的缺乏和算法的时延性，使Turbo码的实际应用受到一定的限制。本文考虑了适合于短帧情况下Turbo码的设计方法，并得到较好的结果。
Turbo code, also named parallel concatenated convolution code , was presented by C.Berrou, A. Glavieux and P.Thifimajshiwa in ICC'93 . According to the simulation results Turbo code can approach the Shannon bound with iteratively processed maximum-a-posteriori decoders . Because of its excellent performance , Turbo code is considered one of the most exciting and potentially important developments in coding theory in many years. Now Turbo code is widely applied in mobile communication and personal communication .
The thesis investigates some aspects of Turbo code with emphasis on the improvement of the decoding algorithm and the design of the interleaver. The main results are below.
The principles of Turbo code coding and decoding are described. Simulation are conducted employing 16 and 8 states constituent codes such as (37,21)RSC and (15,13)RSC. There are two sorts of decoding methods : MAP algorithm and SOVA algorithm and the thesis emphasizes the former.
Several improved decoding algorithms are discussed including Log-MAP algorithm and sliding window MAP algorithm . And a new decoding structure is presented to avoid the decreasing of the decoding performance in case of the end of trellis. Simulation results show that the new algorithm has improved the performance of Turbo code in transmission of short frames.
The interleaver is very important for Turbo code , and its design is described in the thesis. Several kinds of interleavers are studied , and their implementation methods are proposed . The influence of different interleavers on the performance of Turbo code is developed.
The thesis also gives a simple introduction about the end of trellis , the design of puncture matrix and TCM technology , etc.
Though Turbo code is becoming more and more popular , its practical application is limited because of absence in theory and time delay in algorithm . The thesis developed some suitable methods for short frames and gets a better performance at a certain level.
本文对Turbo码的研究工作主要集中在以下几个方面：
对Turbo码的编译码方法进行研究。Turbo码是建立在一种特殊的系统卷积码的基础上的，它以两个RSC码作为它的分量码，因此分量码的选取对Turbo码的性能有重要的影响。本文主要使用了16状态的(37，21)原始码型和8状态的(15，13)码型。Turbo码的译码算法主要有MAP算法和SOVA算法两大类，本文重点研究了前者。
研究了几种在MAP算法基础上的改进算法。由于MAP算法存在巨大的计算量和时延，为了克服MAP算法的缺点，研究了MAP算法的对数域内的简化算法Log-MAP算法以及滑动窗MAP算法。为了避免短帧情况下trellis的结束带来的译码性能的降低，本文把一种新颖的MAP译码结构应用到Log-MAP中并进行了计算机模拟，模拟结果表明短帧情况下这种新结构的译码方法在性能方面略有改进。
交织器对于Turbo码的性能有重大的影响，文中给出了Turbo码交织器的设计原则，对几种常用的Turbo码交织器的原理和实现方法进行了研究，进行了计算机模拟并对其性能进行了分析比较。
其它诸如trellis结尾问题、删余矩阵的设计、TCM调制等方面，本文给出了初步介绍，详细可查阅文献。
Turbo码现在正得到越来越广泛的应用，但是由于理论的缺乏和算法的时延性，使Turbo码的实际应用受到一定的限制。本文考虑了适合于短帧情况下Turbo码的设计方法，并得到较好的结果。
Turbo code, also named parallel concatenated convolution code , was presented by C.Berrou, A. Glavieux and P.Thifimajshiwa in ICC'93 . According to the simulation results Turbo code can approach the Shannon bound with iteratively processed maximum-a-posteriori decoders . Because of its excellent performance , Turbo code is considered one of the most exciting and potentially important developments in coding theory in many years. Now Turbo code is widely applied in mobile communication and personal communication .
The thesis investigates some aspects of Turbo code with emphasis on the improvement of the decoding algorithm and the design of the interleaver. The main results are below.
The principles of Turbo code coding and decoding are described. Simulation are conducted employing 16 and 8 states constituent codes such as (37,21)RSC and (15,13)RSC. There are two sorts of decoding methods : MAP algorithm and SOVA algorithm and the thesis emphasizes the former.
Several improved decoding algorithms are discussed including Log-MAP algorithm and sliding window MAP algorithm . And a new decoding structure is presented to avoid the decreasing of the decoding performance in case of the end of trellis. Simulation results show that the new algorithm has improved the performance of Turbo code in transmission of short frames.
The interleaver is very important for Turbo code , and its design is described in the thesis. Several kinds of interleavers are studied , and their implementation methods are proposed . The influence of different interleavers on the performance of Turbo code is developed.
The thesis also gives a simple introduction about the end of trellis , the design of puncture matrix and TCM technology , etc.
Though Turbo code is becoming more and more popular , its practical application is limited because of absence in theory and time delay in algorithm . The thesis developed some suitable methods for short frames and gets a better performance at a certain level.
引文
[1] Shannon C E. A mathematical theory of communication. BSTJ, 2-7:379～423,July and: 623～656, Dct 1948
[2] Berrou C, Glavieux A, Thitimajshima P. Near Shannon limit error-correcting coding and decoding: turbo-codes. IEEE Int. Conf. On Commun. Geneva, May 1993:1064～1070
[3] Jung,P.,et al. Dependence of the error performance of Turbo codes on the interleaver structure in short frame transmission systems. Electron. Lett., 1994,30(4):287～288
[4] Burbuleacu. A. S. , et al. Interleaver design for turbo codes. Electron. Lett., 1994,30(25):2107-2108
[5] Hagenauer J. , et al. Iterative decoding of binary block and convolutional codes. IEEE Trans. Inf. Th .,1996,42(2):429～445
[6] Svirid Y. V.. Weight distributions and bounds for turbo-codes. Europ. Trans. Telecom. Rel. Tech. 1995, 6(5):543～555
[7] Benedetto S. , et al. Design of parallel convolutional codes. IEEE Trans. Commun. 1996,44(5):591～600
[8] Perez L. C. , Seghers J. , Costello D. J. , A distance spectrum interpretation of turbo codes. IEEE Trans. Inf. Th, 1996, 42(6):1689～1709
[9] Robertson P. et al. A comparison of optimal and sub-optimal MAP Decoding Algorithms Operating in the Log Domain. ICC'95, 1995:1009～1013
[10] Jung P. Novel low complexity decoder for Turbo-codes. Electron. Lett., 1995,31(2):86～87
[11] Hagenauer J., et al. A Viterbi Algorithm with soft-output and Its Applications. GLOBECOM'89,1989:1680～1687
[12] Jung P., et al, Comparison of Turbo-code decoders applied to short frame trame transmission systems. IEEE J-SAC, 1996,
14(3):530～537
[13] Zhou S. D. , et al. Soft-output Algorithm with low memory requirement.
[14] S.Benedetto et al, "Serial concatenation of interleaved codes: Performance analysis ,design, and iterative decoding,"IEEE Trans. Inform. Theory, vol.44,no.3,pp.909-926,May 1998.
[15] Benedetto S, , et al. Unveiling turbo codes:some results on parallel concatenated coding schemes. IEEE Trans. Inf. Th. , 1996, 42(2): 409～428
[16] Burbuleacu. A. S. , et al. Interleaver design for turbo codes. Electron. Lett., 1994,30(25): 2107-2108
[17] Benedetto S., et al. Algorithm for continuous decoding of turbo codes. Electron. Lett., 1996,32(4):314～315
[18] Benedetto S.,et al. Bandwidth efficient parallel concatenated coding schemes. Electron. Lett. 1995,31 (24): 2067～2069
[19] Jung P. , et al, Comparison of Turbo-code decoders applied to short frame trame transmission systems. IEEE J-SAC, 1996, 14(3):530～537
[20] 张豫伟，王新梅．调制下的多进制Turbo码．中国科学(E辑)．1996，26(6)：534～540
[21] 吴伟陵．通向信道编码定理的turbo码及其性能分析．电子学报，1998，26(7)：35～40
[22] 周世东，梅顺良，姚彦，并行级联卷积码的最新进展．电子学报，1998，26(7)：59～66
[23] 叶中行，Victor Wei.Turbo码的若干新进展．电子学报，1998，26(7)：41～46
[24] 王新梅，马建峰，马啸．软判决译码进展．电子学报，1998, 26(7)：19～26
[25] T.Richardson,"The geometry of turbo-decoding dynamics," IEEE Trans. Inform. Theory, Jan.2000, 46:9-23
[26] Assaf Sella and Yair Be'erry Convergence Analysis of Turbo Decoding of Product Codes. IEEE Trans. Inform. Theory, 2001. ,47(2): 723-735,
[27] Dakshi Agrawal, Alexander Vardy. The Turbo Decoding Algorithm and Its Phase Trajectories. IEEE Trans. Inform. Theory. 2001, 47(2): 699-722
[28] 古建，杨大成．一种新颖的Turbo码MAP译码器．通信学报，2001，22(4)：96～100．
[29] Assaf Sella and Yair Be'erry. Convergence Analysis of Turbo Decoding of Product Codes. IEEE Trans.Inform. Theory, 2001,47(2): 723-735,
[30] 赵向群．改进的滑动窗最大后验译码．微计算机信息，2001，17(10)：56～57
[31] Hokfelt J , Edfors O, Maseng T. A survey on trellis termination alternatives for Turbo Codes. IEEE Vehicular Technology Conference, VTC'99[C]. 2225-2229
[32] 许成谦，林雪红，陈嘉兴．Turbo码Log-MAP译码算法的一种改进算法．燕山大学学报，2002，26(4)：286～288
[33] Battail G. A conceptual framework for understanding turbo codes[J]. IEEE J-SAC, Feb 1998, 16(2): 245～254.
[34] 张中培，靳蕃．从相关性分析Turbo码交织器的设计．电子科技大学学报．2000，29(1)：25～28
[35] Barbulescu A.S.,Pietrobon S. Interleaver design for three dimensional turbo codes. Proc 1995 IEEE Int Symp Inform. Theory. Canada,37
[36] Battail G. A conceptual framework for understanding turbo codes[J]. IEEE J-SAC, Feb 1998, 16 (2):245～254 .
[37] 徐衡平，赵勋．确定性交织器的研究．通信学报，2002，23(3)：96～99
[38] 白宝明，马啸，王新梅．随机交织器的设计与实现．通信学报，2000,21(6)：6～11
[39] 徐衡平，戎梦恬，赵勋，潘晟．Turbo码中交织器和子码的综合设计．通信技术，2002，121(6)：15～19
[40] 叶永涛，张申如．Turbo码中交织器的设计及其性能．解放军理工大学学报，2000，1(3)
[41]徐韦峰，秦东，刘石，周汀．Turbo码中交织器的设计及其改进．微电子学，2000，30(2)：92～96．
[42]靳蕃．信息论与编码方法．中国铁道出版社，1990
[43]王新梅，肖国镇．纠错码—原理与方法．西安电子科技大学出版社，2001
[44]朱旭明．m-QAM调制技术及其在移动通信中的应用．移动通信．2001(1)：30-34
[45]王强，孙锦涛．衰落信道中TURBO码的应用研究．无线电通信技术．2000,9(3)：14～17
[46]刘东华．不同译码器结构对Turbo码性能的影响．通信技术．1999(3)
[47]刘光亮，胡正明．最小化符号错误率译码的矩阵算法．通信学报．1998，19(8)：1～6
[48]白宝明．Turbo码理论及其应用的研究．西安电子科技大学博士论文，1999
[49]张忠培．Turbo码特性及译码实现研究．西南交通大学博士论文．2000
[50]Patric Roberston, etc. Bandwidth-Efficient Turbo Trellis Coded Modulation Using Punctured Component Codes. IEEE J-SAC, 1998, 16(2): 206～216
[51]Tolga M. Duman, etc. Performance Bounds for Turbo Coded Modulation Systems. IEEE Trans. On Commun. 1999, 47(4): 511～512
[52]R.Hoshyar, etc. Ant Colony Algorithm for finding good interleavering Pattern in Turbo Codes. IEE Proceeding Commun. 2000, 147(5)
[53]J.A.Briffa,V. Buttigieg. Interleaving and termination in unpunctured symmetric turbo codes. IEE Proc. Commun.2002,149(1):6～12
[54]M.A.Kousa, A.H.Mugaibel. Puncturing effects on turbo codes. IEE Proc. Commun.2002,149(3): 132～138
[2] Berrou C, Glavieux A, Thitimajshima P. Near Shannon limit error-correcting coding and decoding: turbo-codes. IEEE Int. Conf. On Commun. Geneva, May 1993:1064～1070
[3] Jung,P.,et al. Dependence of the error performance of Turbo codes on the interleaver structure in short frame transmission systems. Electron. Lett., 1994,30(4):287～288
[4] Burbuleacu. A. S. , et al. Interleaver design for turbo codes. Electron. Lett., 1994,30(25):2107-2108
[5] Hagenauer J. , et al. Iterative decoding of binary block and convolutional codes. IEEE Trans. Inf. Th .,1996,42(2):429～445
[6] Svirid Y. V.. Weight distributions and bounds for turbo-codes. Europ. Trans. Telecom. Rel. Tech. 1995, 6(5):543～555
[7] Benedetto S. , et al. Design of parallel convolutional codes. IEEE Trans. Commun. 1996,44(5):591～600
[8] Perez L. C. , Seghers J. , Costello D. J. , A distance spectrum interpretation of turbo codes. IEEE Trans. Inf. Th, 1996, 42(6):1689～1709
[9] Robertson P. et al. A comparison of optimal and sub-optimal MAP Decoding Algorithms Operating in the Log Domain. ICC'95, 1995:1009～1013
[10] Jung P. Novel low complexity decoder for Turbo-codes. Electron. Lett., 1995,31(2):86～87
[11] Hagenauer J., et al. A Viterbi Algorithm with soft-output and Its Applications. GLOBECOM'89,1989:1680～1687
[12] Jung P., et al, Comparison of Turbo-code decoders applied to short frame trame transmission systems. IEEE J-SAC, 1996,
14(3):530～537
[13] Zhou S. D. , et al. Soft-output Algorithm with low memory requirement.
[14] S.Benedetto et al, "Serial concatenation of interleaved codes: Performance analysis ,design, and iterative decoding,"IEEE Trans. Inform. Theory, vol.44,no.3,pp.909-926,May 1998.
[15] Benedetto S, , et al. Unveiling turbo codes:some results on parallel concatenated coding schemes. IEEE Trans. Inf. Th. , 1996, 42(2): 409～428
[16] Burbuleacu. A. S. , et al. Interleaver design for turbo codes. Electron. Lett., 1994,30(25): 2107-2108
[17] Benedetto S., et al. Algorithm for continuous decoding of turbo codes. Electron. Lett., 1996,32(4):314～315
[18] Benedetto S.,et al. Bandwidth efficient parallel concatenated coding schemes. Electron. Lett. 1995,31 (24): 2067～2069
[19] Jung P. , et al, Comparison of Turbo-code decoders applied to short frame trame transmission systems. IEEE J-SAC, 1996, 14(3):530～537
[20] 张豫伟，王新梅．调制下的多进制Turbo码．中国科学(E辑)．1996，26(6)：534～540
[21] 吴伟陵．通向信道编码定理的turbo码及其性能分析．电子学报，1998，26(7)：35～40
[22] 周世东，梅顺良，姚彦，并行级联卷积码的最新进展．电子学报，1998，26(7)：59～66
[23] 叶中行，Victor Wei.Turbo码的若干新进展．电子学报，1998，26(7)：41～46
[24] 王新梅，马建峰，马啸．软判决译码进展．电子学报，1998, 26(7)：19～26
[25] T.Richardson,"The geometry of turbo-decoding dynamics," IEEE Trans. Inform. Theory, Jan.2000, 46:9-23
[26] Assaf Sella and Yair Be'erry Convergence Analysis of Turbo Decoding of Product Codes. IEEE Trans. Inform. Theory, 2001. ,47(2): 723-735,
[27] Dakshi Agrawal, Alexander Vardy. The Turbo Decoding Algorithm and Its Phase Trajectories. IEEE Trans. Inform. Theory. 2001, 47(2): 699-722
[28] 古建，杨大成．一种新颖的Turbo码MAP译码器．通信学报，2001，22(4)：96～100．
[29] Assaf Sella and Yair Be'erry. Convergence Analysis of Turbo Decoding of Product Codes. IEEE Trans.Inform. Theory, 2001,47(2): 723-735,
[30] 赵向群．改进的滑动窗最大后验译码．微计算机信息，2001，17(10)：56～57
[31] Hokfelt J , Edfors O, Maseng T. A survey on trellis termination alternatives for Turbo Codes. IEEE Vehicular Technology Conference, VTC'99[C]. 2225-2229
[32] 许成谦，林雪红，陈嘉兴．Turbo码Log-MAP译码算法的一种改进算法．燕山大学学报，2002，26(4)：286～288
[33] Battail G. A conceptual framework for understanding turbo codes[J]. IEEE J-SAC, Feb 1998, 16(2): 245～254.
[34] 张中培，靳蕃．从相关性分析Turbo码交织器的设计．电子科技大学学报．2000，29(1)：25～28
[35] Barbulescu A.S.,Pietrobon S. Interleaver design for three dimensional turbo codes. Proc 1995 IEEE Int Symp Inform. Theory. Canada,37
[36] Battail G. A conceptual framework for understanding turbo codes[J]. IEEE J-SAC, Feb 1998, 16 (2):245～254 .
[37] 徐衡平，赵勋．确定性交织器的研究．通信学报，2002，23(3)：96～99
[38] 白宝明，马啸，王新梅．随机交织器的设计与实现．通信学报，2000,21(6)：6～11
[39] 徐衡平，戎梦恬，赵勋，潘晟．Turbo码中交织器和子码的综合设计．通信技术，2002，121(6)：15～19
[40] 叶永涛，张申如．Turbo码中交织器的设计及其性能．解放军理工大学学报，2000，1(3)
[41]徐韦峰，秦东，刘石，周汀．Turbo码中交织器的设计及其改进．微电子学，2000，30(2)：92～96．
[42]靳蕃．信息论与编码方法．中国铁道出版社，1990
[43]王新梅，肖国镇．纠错码—原理与方法．西安电子科技大学出版社，2001
[44]朱旭明．m-QAM调制技术及其在移动通信中的应用．移动通信．2001(1)：30-34
[45]王强，孙锦涛．衰落信道中TURBO码的应用研究．无线电通信技术．2000,9(3)：14～17
[46]刘东华．不同译码器结构对Turbo码性能的影响．通信技术．1999(3)
[47]刘光亮，胡正明．最小化符号错误率译码的矩阵算法．通信学报．1998，19(8)：1～6
[48]白宝明．Turbo码理论及其应用的研究．西安电子科技大学博士论文，1999
[49]张忠培．Turbo码特性及译码实现研究．西南交通大学博士论文．2000
[50]Patric Roberston, etc. Bandwidth-Efficient Turbo Trellis Coded Modulation Using Punctured Component Codes. IEEE J-SAC, 1998, 16(2): 206～216
[51]Tolga M. Duman, etc. Performance Bounds for Turbo Coded Modulation Systems. IEEE Trans. On Commun. 1999, 47(4): 511～512
[52]R.Hoshyar, etc. Ant Colony Algorithm for finding good interleavering Pattern in Turbo Codes. IEE Proceeding Commun. 2000, 147(5)
[53]J.A.Briffa,V. Buttigieg. Interleaving and termination in unpunctured symmetric turbo codes. IEE Proc. Commun.2002,149(1):6～12
[54]M.A.Kousa, A.H.Mugaibel. Puncturing effects on turbo codes. IEE Proc. Commun.2002,149(3): 132～138