论文标题:信道上LDPC码的译码算法及应用研究
A Study on LDPC Decoding Algorithm and Application over Channels
论文作者
论文导师 郭树旭,论文学位 硕士,论文专业 电子与通信工程
论文单位 吉林大学,点击次数 226,论文页数 66页File Size987K
2007-10-18论文网 http://www.lw23.com/lunwen_200672987/
LDPC码是一种逼近仙农限的、易实现和系统复杂度低的优秀的线性纠错码。由于低密度校验码的诸多优点,在信息可靠传输中具有良好应用前景,已经引起学术界和IT业界的高度重视,成为当今信道编码领域最受瞩目的研究热点之一。 本文主要从LDPC码译码、译码算法分析和编码方法以及LDPC码的应用四个方面对LDPC码的相关技术进行了阐述。LDPC码的各种译码算法可以归于一种基于图的消息传播算法(Message Passing Algorithm),文中首先介绍一般意义的Message Passing算法以及置信传播算法,然后介绍不同信道上LDPC码的译码算法。LDPC码的性能分析不是针对某个具体的LDPC码,而是分析由度分布多项式确定的LDPC码集合的平均性能,文中采用这种思想,分析了BEC信道、BSC信道上的译码以及连续输出信道上的BP译码算法。LDPC码的编码复杂度较高,Jorge Campello和Dharmendra S.Modha从图论的观点提出一种叫做比特填充(Bit Filling)的算法,文中重点对比特填充算法进行了研究,并应用于LDPC码校验矩阵的构造。本文简要介绍了基于LDPC码的OFDM,MIMO-OFDM系统的主要特点。 文中从译码、性能分析及编码和应用的角度系统的介绍了LDPC码。结果显示,LDPC码具有性能优异、译码简单以及译码速度快等优点。这些优点使LDPC码非常适合高速通信系统。
Gallager 1963 invented Low density parity check code in PhD thesis based on a relatively simple decoder. LDPC codes have been largely ignored by the coding community until Mackay 1996 showed that LDPC have near-Shannon limit performance. A Low density parity check code is the code specified by sparse matrix, which is one of the researches focus of Error–correcting code field at present. In this paper LDPC codes are detailedly introduced from the following aspects, basic decoding algorithm, performance analysis, main simplified decoding algorithm, optimization designing, construction of check matrix and efficient encoding and OFDM, MIMO-OFDM system model based on LDPC codes and the main features. The iterative decoding algorithm, Belief Propagation, based on bipartite graph is used to decode LDPC. If the code length is infinite the decoding algorithm is optimal, but when the code length is final the circles are inevitable so the algorithm is Hypo-optimal. LDPC codes’performances are excellent. The simulation results show that they are error-correcting codes capable of getting close to the Shannon limit. LDPC codes are inherently parallel and thus are faster to decode, so that they are suitable for the high-speed communication systems. In this paper we introduce detailedly the basic principles of the algorithm of decoding over BSC, BEC and the continuous channel and analyze their decoding complexity. The result shows that LDPC codes have linear-complexity decoding. Belief Propagation is based on simpler bipartite graph and we will see that under a suitable set of symmetry assumptions the conditional decoding probability will become independent of the transmitted codeword, allowing us in the sequel to assume that the all-zero codeword was transmitted. And we typically analyze their collective and asymptotic behavior. Under the idea we analyze the performance of LDPC codes over BSC, BEC and continuous channel. The result shows that there is a threshold phenomenon for BP algorithm. If the signal to noise ratio larger than the threshold, it is possible to communicate in an error free manner, otherwise communicate in error free manner is impossible. If the degree distributions of a LDPC code are known, its threshold can be calculated by a complicated numerical analysis, density evolution. The simulation results the performance of the codes is very close to the asymptotic theoretical bounds.. For example, the (n,3,6) regular code’s signal to noise ratio threshold is 1.1dB over AWGN channel, while the simulation result shows that achieves a bit-error probability of 10-5 less than 0.15 dB away form the threshold. In Gallagher’s original paper the LDPC codes are regular. That is, the degrees of all bit nodes are equal, and the degrees of all check nodes are equal. This means that the parity-check matrix of the code described above contains the same number of ones in each row and the same number of ones in each column. M.G.Luby improved performance comes from using codes based on irregular graphs. That is, the degrees of the nodes on each side of the graph can vary widely. The simulation results show that the idea is correct. Each channel, even each decoding algorithm has LDPC codes that are most suitable for the channel or for the algorithm. In paper Thomas J. Richardson design LDPC codes that perform at rates extremely close to the Shannon capacity on AWGN channel and Jilei Hou design LDPC codes on Rayleigh fading channels. Michael G. Luby, in paper , analyze LDPC codes on BEC and put forward a construction method of LDPC codes on BEC. Except for LDPC codes on BEC other LDPC codes are optimized by numerical analysis. Not a good degree distribution but also the appropriate check matrix is necessary for a practical LDPC code. In Gallagher’s original paper a method is posed for constructing the regular LDPC codes’check matrix. After the invention irregular, several methods are presented in for the problem of low weight code words. Jorge Campello and Dharmendra S.Modha form the point of graph pose the Bit Filling algorithm. In our paper we study the algorithm and use it to construction LDPC codes check matrix. In many ways LDPC codes can be considered serious competitors to turbo codes. In particular, LDPC codes exhibit an asymptotically better performance than turbo codes and they admit a wide range of trade-offs between performance and decoding complexity. One major criticism concerning LDPC codes has been their apparent high encoding complexity. Whereas turbo codes can be encoded in linear time, a straightforward encoder implementation for a LDPC code has complexity quadratic in the block length. It was suggested to use cascaded rather than bipartite graphs. By choosing the number of stages and the relative size of each stage carefully one can construct codes which are encodable and decodable in linear time. One drawback of this approach lies in the fact that each stage has a length which is in general considerably smaller than the length of the overall code. These results, in general, in a performance loss compared to a standard LDPC code with the same overall length. In it was suggested to force the parity check matrix to have (almost) lower triangular form, i.e., the ensemble of codes is restricted not only by the degree constraints but also by the constraint that the parity check matrix have lower triangular shape. This restriction guarantees a linear time encoding complexity but, in general, it also results in some loss of performance. In Tom Richardson has shown that, even without cascade constructions or restrictions on the shape of the parity check matrix, the encoding complexity is quite manageable in most cases and provably linear in many cases. More precisely, for a (3, 6)-regular code of length n the encoding complexity seems indeed to be of order n2 but the actual number of operations required is no more than 0.0172n2+O(n). The author also shows that“optimized”irregular codes have a linear encoding complexity and that the required amount of preprocessing is of order at most n3/2. In our paper we study the algorithm and implement the efficient encoding of LDPC codes posed by Tom Richardson. The practical results also show that the“optimized”irregular codes’encoding can be implemented with linear complexity. LDPC codes have good performance that approximate shannon limit. The OFDM, MIMO-OFDM system are based on LDPC codes. It need to be further studied.
|
