准循环LDPC码编译码的FPGA实现
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
低密度奇偶校验(LDPC)码是由Gallager于1962年提出的一种基于稀疏校验矩阵的线性分组码,具有逼近香农限的良好译码性能。LDPC码已成为多个通信标准中的纠错编码方案,因此对LDPC码编译码器的硬件实现是目前的研究热点之一。
     LDPC编码的主要问题是找到编码复杂度与码长成线性关系的编码方法,而译码的主要问题是找到一种译码结构实现译码复杂度、译码性能和译码器吞吐量的有效折衷。
     准循环LDPC (QC-LDPC)码是一类重要的LDPC码,其校验矩阵具有准循环性,在编码上可以利用反馈移位寄存器实现具有线性复杂度的编码器,译码时也大大降低了存储空间。本文从理论研究和硬件实现两个方面对QC-LDPC码进行了深入研究,并基于FPGA实现了QC-LDPC码的编、译码器的硬件设计。主要工作包括:
     1、针对QC-LDPC码的快速编码,实现了校验矩阵满秩时准循环校验矩阵转换到准循环生成矩阵的算法,并对校验矩阵不满秩时的转换算法进行了研究。
     2、基于准循环生成矩阵,研究和实现了串行编码、并行编码、两级编码三种编码算法。在两级编码的基础上,增加一级电路的复用,提出了一种新的编码器结构,提高了编码效率和运行时间。
     3、在对LDPC码编、译码器的计算机浮点仿真的基础上,对基于最小和算法的译码初始化和译码过程进行了定点仿真。结果表明,定点仿真的结果比浮点仿真的结果有0.3-0.5dB的性能损失,采用的定点处理算法是合理有效的。
     4、在ISE8.2和modelsim6.2软件平台上,运用Verilog HDL编程语言,基于译码器的部分并行结构,设计实现了QC-LDPC码的最小和算法译码。
Low density parity-check (LDPC) code was proposed in 1962 by Gallager, which is a kind of linear block codes based on a sparse check matrix. its decoding performance can achieve Shannon Limit. Many communication standards have already adopted LDPC codes as the Error-Correcting codes. So, the hardware implementation of LDPC encoder and decoder are one of the research interests at present.
     The main problem of LDPC encoding is to find an efficient encoding algorithm with linear complexity, and the main problem of LDPC decoding is to make a trade-off between hardware complexity, performance and throughput.
     QC-LDPC code is an important subclass of LDPC codes. Because of the cyclic symmetry, the encoding complexity of QC-LDPC codes are linearly proportional with code length and the decoding storage space is reduced greatly. This thesis studies both the theory and hardware implementation of LDPC codes, and implements the encoder and decoder of QC-LDPC codes on FPGA. The main works are as follows:
     1. The algorithm from the parity-check matrix to the generator matrix is realized when the check matrix is full rank, and the case when the check matrix is not full rank is also researched.
     2. Three fast encoding algorithms for QC-LDPC codes are researched and realized, which are serial encoder, parallel encoder and two-stage encoder. Based on the two-stage encoder, a more effective encoding structure by reusing the first stage circuits is proposed. Simulation results show that the encoding efficiency and working frequency are improved.
     3. Floating simulation of the LDPC encoding and decoding system is performed and fixed simulation of the Mim-Sum decoder is completed. The results show that there are about 0.3 to 0.5 performances losses and the fixed-point processing program is reasonable and effective.
     4. Hardware design and implementation of partially-parallel decoder are completed on the ISE 8.2 and modelsim 6.2 software platform using Verilog HDL.
引文
[I]John. G. Proakis.数字通信(第三版).电子工业出版社,2002.
    [2]C. E. Shannon.A mathematical theory of communication. Bell Systems Technical Journal, vol.27, pp.379-423,1948.
    [3]王新梅,肖国镇,纠错码原理与方法.西安:西安电子科技大学出版社,2001.
    [4]樊昌信,詹道庸,徐炳祥,吴成柯,通信原理(第四版)[M].国防工业出版社,1995.
    [5]R. G.Gallager. Low-density parity-check codes [J]. IEEE Transactions On Information Theory,1962,8(1):21-28.
    [6]D. J. C. MacKay and R. M. Neal, "Near-Shannon-limit performance of low density parity check codes," Electron. Lett. vol.32, pp.1645-1646, Aug.1996.
    [7]D. J. C. MacKay.Good error-correcting codes based on very sparse matrices [J]. IEEE Transaction on Information Theory,1999,45(2):399-431.
    [8]C. Berrow, A. Glavieux, P.Thitimajshima. Near Shannon limit error-correcting coding and decoding:turbo-codes. IEEE International Conference on Communications,1993,2:1064-1070.
    [9]C.Berrouw, A. Olavieux.Near optimum error correcting coding and ecoding: turbo-codes. IEEE Trans on Communications,1996,44(10):1261-1271.
    [10]M. G.Luby, M. Mitzenmacher, M. A. Shokrollah, D. A. Spielman. Improved low-density Parity-check Codes Using Irregular Graphs, Information Theory. IEEE Transactions on, Vol.47, Issue 2, pp.585-598, Feb 2001.
    [11]T. J. Richardson and R. L. Urbanke. The Capacity of Low-density Parity-check Codes Under Message-passing Decoding. IEEE Transaction on Information Theory, Vol.47, pp.599-618, Feb.2001.
    [12]Zongwang Li, Lei Chen, Lingqi Zeng,Shu Lin and Wai H. Fong. Efficient Encoding of Quasi-Cyclic Low-Density Parity-CheckCodes. IEEE Trans. Commun. Janu.2006,54(1):71-81.
    [13]R. M. Tanner. A Recursive Approach to Low Complexity Codes. IEEE Transactions on Information. Theory,Vol.27, pp.533-547, Sept.1981.
    [14]ETSI. EN 302 307 V1.1.1. Digital Video Broad-casting(DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications[S]. Lucioles:EBU UER,2004.
    [15]IEEE P802.16E/d8 IEEE Standard for Local and metropolitan Area networks. IEEE, May2005.
    [16]中华人民共和国国家标准.“数字电视地面广播传输系统帧结构、信道编码和调制”,征求意见稿,2004.4.
    [17]王诚,薛小刚,钟信潮,FPGA/CPLD设计工具-Xilinx ISE使用详解,北京:人民邮电出版社,2005年.
    [18]刘波,精通Verilog HDL语言编程,北京:电子工业出版社,2007年.
    [19]侯伯亨,顾新,VHDL硬件描述语言与数字逻辑电路设计[M].西安:西安电子科技大学出版社,1998.
    [20]夏宇闻,Verilog数字系统设计教程,北京:北京航空航天大学出版社,2003.
    [21]段吉海,黄智伟,基于CPLD/FPGA的数字通信系统建模与设计.电子工业出版社。2004.
    [22]孙航,Xilinx可编程逻辑器件的高级应用与设计技巧.电子工业出版杜,2004.
    [23]N. Wiberg, H.A.Loeliger, and R.Kotter. Codes and Iterative Decoding on General Graphs, Euro. Transactions. Telecomm. Vol.6, pp.513-525,1995.
    [24]N. Wiberg. Codes and Decoding on General Graphs. PH.D Thesis, Linkoping University, S-581 83 Linkoping, Sweden,1996.
    [25]Y. Kou, S. Lin and M. Fossoriet. Low-Density Parity-Check Codes Based On Finite Geometries:Arediscovery and New Results[J]. IEEE Trans Inform Theory, Vol.47, No.7, lap.2711-2736, Nov 2001.
    [26]X.-Y. Hu, E. Eleftheriou, and D.-M. Arnold, "Progressive Edge-Growth Tanner Graphs," IEEE Global Telecommunications Conference 2001, vol.2, pp.995-1001, 25-29 November,2001.
    [27]Z. Li and B.V.K.V. Kumar, "A class of good quasicyclic low-density parity check codes based on progressive edge growth graph," in Proc. IEEE 38th Conf. Signals, Systems and Computers, Pacific Grove, CA, Nov.2004, pp.1990-1994.
    [28]M. C. Davey and D. J. C. Mackay, Low density parity check codes over GF (q) [J], IEEE Communication Letter, Vol.2, PP.165-167, June 1998.
    [29]S. Lin and D. J. Costello, Error Control Coding: Fundamentals and Applications, 2nd ed. Upper Saddle River, NJ:Prentice-Hall,2004.
    [30]W. W. Peterson and E. J. Weldon, Error Correcting Codes,2nded. Cambridge, MA: MIT Press,1972.
    [31]Richarddson T, Urbranke R. "Efficient encoding of low-density parity-check codes". IEEE Trans.Info.Theory,2001,47 (2):638-656.
    [32]王新梅,纠错码-原理与方法,西安电子科技大学,2002.
    [33]欧阳玉梅,“数的定点表示与浮点表示”问题分析,Research in Teaching, Vol.28, No.l,Jan.2005.
    [34]赵胜凯,邱宽民,DSP的发展及定点、浮点处理方法的比较,北方交通大学学报Oct.2000, Vol.24 No.5.
    [35]陈国军,万民康,王大明,郭锐,乘除法和开方运算的FPGA串行实现。解放军信息工程大学,PLD CPLD FPGA应用.
    [36]徐爱芸,郭文燕,定点除法运算中余数的处理方法,高等函授学报(自然科学版),Vol.13 No.4 August 2000.
    [37]G Masera, F. Quaglio and F.Vacca.Finite precision implementation of LDPC decoders, IEEE Proc.-Commun, Vol.152, No.6, December 2005.
    [38]Zhengya Zhang, Lara Dolecek, MartinWainwright, Venkat Anantharam,and Borivoje Nikolic, Quantization Effects in Low-Density Parity-Check Decoders, Department of Electrical Engineering and Computer Sciences University of California, Berkeley, CA 94720, USA.
    [39]童胜,王鹏,王单,王新梅,LDPC码量化和积译码的高效实现,西安电子科技大学学报(自然科学版),Oct.2004 Vol.31 No.5.
    [40]刘斌彬,白栋,梅顺良,基于Min-Sum近似算法的QC-LDPC译码器,《无线通信技术》2008年第一期.
    [41]夏红星,丁幺明,一种LUT函数运算单元的FPGA实现方法。中文核心期刊《微计算机信息》(嵌入式与SOC),2006年第22卷第5-2期.
    [42]R. Koetter and P. O. Vontobel, "Graph covers and iterative decoding offinite-length codes," in Proc. 3rd Int. Conf. Turbo Codes and Related Topics, Brest, France, Sep.2003, pp.75-82.
    [43]Jon Feldman, Martin J. Wainwright, Using Linear Programming to Decode BinaryLinear Codes, IEEE Trans. Inf. Theory, vol.51, NO.3 march,2005.
    [44]C. Di, D. Proietti, I. E. Telatar, T. J. Richardson, and R. L. Urbanke, “Finite-lengthanalysis of low-density parity-check codes on the binary erasure channel,” IEEE Trans. Inf. Theory, vol.48, no.6, pp.1570-1579,2002.
    [45]Jon Feldmanl, Tal Malkin, Rocco A. Servedio, LP Decoding Corrects a Constant Fraction of Errors, ISIT 2004, Chicago, USA, June 27-July 2,2004.
    [46]Shui Shu-Tao Xia and Fang-Wei Fu, Minimum Pseudoweight and Minimum Pseudocodewords of LDPC Codes, IEEE Trans. Inf. Theory, VOL.54, NO.1, JANUARY 2008.
    [47]Zhiqiang Cui and Zhongfeng Wang, Area-Efficient Parallel Decoder Architecture for High Rate QC-LDPC Codes, ISCAS 2006.
    [48]Luoming Zhang, Lin GUI, Youyun Xu, and Wenjun Zhang, Configurable Multi-Rate Decoder Architecture for QC-LDPC Codes Based Broadband Broadcasting System, IEEE Trans, on broadcasting,2008.
    [49]Guido Masera, Member, IEEE, Federico Quaglio, Implementation of a Flexible LDPC Decoder, IEEE Trans. on circuits and systems:express briefs, vol.54, NO.6, june 2007.
    [50]Jui-Hui Hung and Sau-Gee Chen2, A 1.45Gb/s (576,288) LDPC Decoder for 802.16e standard,2007 IEEE International Symposium on Signal Processing and Information Technology.
    [51]Chih-Hao Liu, Shau-Wei Yen, Chih-Lung Chen, Hsie-Chia Chang, Chen-Yi Lee,An LDPC Decoder Chip Based on Self-Routing Network for IEEE 802.16e Applications, IEEE Journal of Solid-state Circuits, vol.43, NO.3 march 2008.
    [52]H. Chen, "A FPGA and ASIC implementation of rate 1/2,8088-b irregular Low-density parity-check decoder," in Proc. IEEE Globecom,2003, vol. I, pp. 113-117.
    [53]M. M. Mansour and N. R. Shanbhag, "A 640-Mb/s 2048-bit programmable LDPC decoder chip," IEEE J. Solid-State Circuits, vol.41, no.3, pp.634-698, Mar.2006.
    [54]Ahmad Darabiha, Anthony Chan Camsone, Frank R.Kschischang. A bit-serial approximate min-sum LDPC decoder and FPGA implementation[J]. ISCAS 2006.
    [55]D. E. Hocevar, "A reduced complexity decoder architecture via layered Decoding of LDPC codes," in Proc. IEEE Workshop on Signal Processing Systems, Austin, TX, Oct.2004, pp.107-112.
    [56]Z. Wang, Y. Chen, and K. Parhi, "Area-efficient quasi-cyclic LDPC code decoder architecture" in Proc. ICASSP,2004, pp.49-52.
    [57]H. Zhong and T. Zhang, "Quasi-Cyclic LDPC Codes for the Magnetic Recording Channel:Code Design and VLSI Implementation," IEEE Trans. Magazine, vol.43, no.3, Mar.2007.
    [58]Hao Zhang, Wei Xu, Ningde Xie, and Tong Zhang, "Area-Efficient Min-Sum Decoder Design for High-Rate Quasi-Cyclic Low-Density Parity-Check Codes in Magnetic Recording, "IEEE Trans. Magazine, vol.43, no.12, Dec.2007, pp. 4117-4122.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700