共查询到20条相似文献,搜索用时 15 毫秒
1.
LDPC block and convolutional codes based on circulant matrices 总被引:18,自引:0,他引:18
Tanner R.M. Sridhara D. Sridharan A. Fuja T.E. Costello D.J. Jr. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2004,50(12):2966-2984
A class of algebraically structured quasi-cyclic (QC) low-density parity-check (LDPC) codes and their convolutional counterparts is presented. The QC codes are described by sparse parity-check matrices comprised of blocks of circulant matrices. The sparse parity-check representation allows for practical graph-based iterative message-passing decoding. Based on the algebraic structure, bounds on the girth and minimum distance of the codes are found, and several possible encoding techniques are described. The performance of the QC LDPC block codes compares favorably with that of randomly constructed LDPC codes for short to moderate block lengths. The performance of the LDPC convolutional codes is superior to that of the QC codes on which they are based; this performance is the limiting performance obtained by increasing the circulant size of the base QC code. Finally, a continuous decoding procedure for the LDPC convolutional codes is described. 相似文献
2.
Sunghwan Kim Jong-Seon No Habong Chung Dong-Joon Shin 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2007,53(8):2885-2891
A quasi-cyclic (QC) low-density parity-check (LDPC) code can be viewed as the protograph code with circulant permutation matrices (or circulants). In this correspondence, we find all the subgraph patterns of protographs of QC LDPC codes having inevitable cycles of length 2i, i = 6, 7, 8, 9,10, i.e., the cycles that always exist regardless of the shift values of circulants. It is also derived that if the girth of the protograph is 2g, g > 2, its protograph code cannot have the inevitable cycles of length smaller than 6g. Based on these subgraph patterns, we propose new combinatorial construction methods of the protographs, whose protograph codes can have girth larger than or equal to 14 or 18. We also propose a couple of shift value assigning rules for circulants of a QC LDPC code guaranteeing the girth 14. 相似文献
3.
Quasi-cyclic LDPC codes for fast encoding 总被引:18,自引:0,他引:18
Myung S. Yang K. Kim J. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2005,51(8):2894-2901
In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices. 相似文献
4.
Efficient encoding of quasi-cyclic low-density parity-check codes 总被引:10,自引:0,他引:10
Zongwang Li Lei Chen Lingqi Zeng Lin S. Fong W.H. 《Communications, IEEE Transactions on》2006,54(1):71-81
Quasi-cyclic (QC) low-density parity-check (LDPC) codes form an important subclass of LDPC codes. These codes have encoding advantage over other types of LDPC codes. This paper addresses the issue of efficient encoding of QC-LDPC codes. Two methods are presented to find the generator matrices of QC-LDPC codes in systematic-circulant (SC) form from their parity-check matrices, given in circulant form. Based on the SC form of the generator matrix of a QC-LDPC code, various types of encoding circuits using simple shift registers are devised. It is shown that the encoding complexity of a QC-LDPC code is linearly proportional to the number of parity bits of the code for serial encoding, and to the length of the code for high-speed parallel encoding. 相似文献
5.
Yongmei Dai Zhiyuan Yan Ning Chen 《Very Large Scale Integration (VLSI) Systems, IEEE Transactions on》2008,16(5):565-578
Efficient hardware implementation of low-density parity-check (LDPC) codes is of great interest since LDPC codes are being considered for a wide range of applications. Recently, overlapped message passing (OMP) decoding has been proposed to improve the throughput and hardware utilization efficiency (HUE) of decoder architectures for LDPC codes. In this paper, we first study the scheduling for the OMP decoding of LDPC codes, and show that maximizing the throughput gain amounts to minimizing the intra- and inter-iteration waiting times. We then focus on the OMP decoding of quasi-cyclic (QC) LDPC codes. We propose a partly parallel OMP decoder architecture and implement it using FPGA. For any QC LDPC code, our OMP decoder achieves the maximum throughput gain and HUE due to overlapping, hence has higher throughput and HUE than previously proposed OMP decoders while maintaining the same hardware requirements. We also show that the maximum throughput gain and HUE achieved by our OMP decoder are ultimately determined by the given code. Thus, we propose a coset-based construction method, which results in QC LDPC codes that allow our optimal OMP decoder to achieve higher throughput and HUE. 相似文献
6.
一种高码率低复杂度准循环LDPC码设计研究 总被引:2,自引:0,他引:2
该文设计了一种特殊的高码率准循环低密度校验(QC-LDPC)码,其校验矩阵以单位矩阵的循环移位阵为基本单元,与随机构造的LDPC码相比可节省大量存储单元。利用该码校验矩阵的近似下三角特性,一种高效的递推编码方法被提出,它使得该码编码复杂度与码长成线性关系。另外,该文提出一种分析QC-LDPC码二分图中短长度环分布情况的方法,并且给出了相应的不含长为4环QC-LDPC码的构造方法。计算机仿真结果表明,新码不但编码简单,而且具有高纠错能力、低误码平层。 相似文献
7.
8.
Kamiya N. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2007,53(4):1444-1459
This paper shows that several attractive classes of quasi-cyclic (QC) low-density parity-check (LDPC) codes can be obtained from affine planes over finite fields. One class of these consists of duals of one-generator QC codes. Presented here for codes contained in this class are the exact minimum distance and a lower bound on the multiplicity of the minimum-weight codewords. Further, it is shown that the minimum Hamming distance of a code in this class is equal to its minimum additive white Gaussian noise (AWGN) pseudoweight. Also discussed is a class consisting of codes from circulant permutation matrices, and an explicit formula for the rank of the parity-check matrix is presented for these codes. Additionally, it is shown that each of these codes can be identified with a code constructed from a constacyclic maximum distance separable code of dimension 2. The construction is similar to the derivation of Reed-Solomon (RS)-based LDPC codes presented by Chen and Djurdjevic Experimental results show that a number of high rate QC-LDPC codes with excellent error performance are contained in these classes 相似文献
9.
He Shanbao Zhao Chunming Jiang Ming 《电子科学学刊(英文版)》2006,23(1):20-22
This paper extends the class of Low-Density Parity-Check (LDPC) codes that can be constructed from shifted identity matrices. To construct regular LDPC codes, a new method is proposed. Two simple inequations are adopted to avoid the short cycles in Tanner graph, which makes the girth of Tanner graphs at least 8. Because their parity-check matrices are made up of circulant matrices, the new codes are quasi-cyclic codes. They perform well with iterative decoding. 相似文献
10.
P. S. Rybin 《Journal of Communications Technology and Electronics》2016,61(12):1432-1439
This paper deals with the irregular binary low-density parity-check (LDPC) codes and two iterative low-complexity decoding algorithms. The first one is the majority error-correcting decoding algorithm, and the second one is iterative erasure-correcting decoding algorithm. The lower bounds on correcting capabilities (the guaranteed corrected error and erasure fraction respectively) of irregular LDPC code under decoding (error and erasure correcting respectively) algorithms with low-complexity were represented. These lower bounds were obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The numerical results, obtained at the end of the paper for proposed lower-bounds achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes. 相似文献
11.
为解决LDPC码的编码复杂度问题,使其更易于硬件实现,提出了一种可快速编码的准循环LDPC码构造方法。该方法以基于循环置换矩阵的准循环LDPC码为基础,通过适当的打孔和行置换操作,使构造码的校验矩阵具有准双对角线结构,可利用校验矩阵直接进行快速编码,有效降低了LDPC码的编码复杂度。仿真结果表明,与IEEE 802.16e中的LDPC码相比,新方法构造的LDPC码在低编码复杂度的基础上获得了更好的纠错性能。 相似文献
12.
针对非合作信号处理中LDPC码(Low-Density Parity-Check)的盲识别问题,提出了一种容错能力较强的开集识别算法.该算法通过对码字矩阵进行高斯约旦消元找到汉明重量较小的"相关列",并根据"相关列"中所包含的约束关系求得LDPC码的校验向量,然后剔除"相关列"中为"1"位置对应的错误码字.若根据高斯约旦消元求校验向量和剔除错误码字进行迭代无法得到更多校验向量,则对得到的这些校验向量进行稀疏化,再进行译码纠错.最后,综合利用校验向量的求解,错误码字的剔除,校验向量稀疏化,LDPC码译码进行迭代,实现LDPC码校验矩阵的有效重建.仿真结果表明,对于IEEE 802.16e标准中的(576,288)LDPC码,在误比特率为0.0022时,本文算法仍可以达到较好的识别效果. 相似文献
13.
在图像处理中,低秩矩阵的冗余信息可用于图像恢复和图像特征提取,而在迭代译码中,校验矩阵的冗余行可以加快译码收敛速度。该文研究一类易于硬件实现的低秩循环矩阵。首先将循环矩阵转换为位置集合,并基于同构理论简化了位置集合的搜索空间,从而基于比特移位方法提出了循环矩阵的构造方法。考虑非零域元素的列赋值与矩阵秩之间的关系,选取Tanner图中没有长度为4的环的循环矩阵,基于非零域元素的列赋值思想提出了不同阶数、不同码率的多元LDPC码构造方法。数值仿真结果表明,与基于PEG算法构造的二元LDPC码比较,所构造的多元LDPC码在BPSK调制方式下在误码字率10–5附近有0.9 dB的增益;在与高阶调制相结合时,有更大的性能提升。此外,所构造的多元LDPC码在迭代5次与50次下的性能几乎一致,这为低时延高可靠通信提供了一种有效的候选编码方案。 相似文献
14.
In this paper low-density parity-check (LDPC) codes are designed for burst erasure channels. Firstly, lower bounds for the maximum length erasure burst that can always be corrected with message-passing decoding are derived as a function of the parity-check matrix properties. We then show how paritycheck matrices for burst erasure correcting LDPC codes can be constructed using superposition, where the burst erasure correcting performance of the resulting codes is derived as a property of the stopping set size of the base matrices and the choice of permutation matrices for the superposition. This result is then used to design both single burst erasure correcting LDPC codes which are also resilient to the presence of random erasures in the received bits and LDPC codes which can correct multiple erasure bursts in the same codeword. 相似文献
15.
Arabaci M. Djordjevic I.B. Saunders R. Marcoccia R.M. 《Lightwave Technology, Journal of》2009,27(23):5261-5267
The parity-check matrix of a nonbinary (NB) low-density parity-check (LDPC) code over Galois field GF(q) is constructed by assigning nonzero elements from GF(q) to the 1s in corresponding binary LDPC code. In this paper, we state and prove a theorem that establishes a necessary and sufficient condition that an NB matrix over GF(q), constructed by assigning nonzero elements from GF(q) to the 1s in the parity-check matrix of a binary quasi-cyclic (QC) LDPC code, must satisfy in order for its null-space to define a nonbinary QC-LDPC (NB-QC-LDPC) code. We also provide a general scheme for constructing NB-QC-LDPC codes along with some other code construction schemes targeting different goals, e.g., a scheme that can be used to construct codes for which the fast-Fourier-transform-based decoding algorithm does not contain any intermediary permutation blocks between bit node processing and check node processing steps. Via Monte Carlo simulations, we demonstrate that NB-QC-LDPC codes can achieve a net effective coding gain of 10.8 dB at an output bit error rate of 10-12. Due to their structural properties that can be exploited during encoding/decoding and impressive error rate performance, NB-QC-LDPC codes are strong candidates for application in optical communications. 相似文献
16.
Software based decoding of low-density parity-check (LDPC) codes frequently takes very long time, thus the general purpose
graphics processing units (GPGPUs) that support massively parallel processing can be very useful for speeding up the simulation.
In LDPC decoding, the parity-check matrix H needs to be accessed at every node updating process, and the size of the matrix is often larger than that of GPU on-chip
memory especially when the code length is long or the weight is high. In this work, the parity-check matrix of cyclic or quasi-cyclic
(QC) LDPC codes is greatly compressed by exploiting the periodic property of the matrix. Also, vacant elements are eliminated
from the sparse message arrays to utilize the coalesced access of global memory supported by GPGPUs. Regular projective geometry
(PG) and irregular QC LDPC codes are used for sum-product algorithm based decoding with the GTX-285 NVIDIA graphics processing
unit (GPU), and considerable speed-up results are obtained. 相似文献
17.
LDPC codes from generalized polygons 总被引:1,自引:0,他引:1
《IEEE transactions on information theory / Professional Technical Group on Information Theory》2005,51(11):3890-3898
We use the theory of finite classical generalized polygons to derive and study low-density parity-check (LDPC) codes. The Tanner graph of a generalized polygon LDPC code is highly symmetric, inherits the diameter size of the parent generalized polygon, and has minimum (one half) diameter-to-girth ratio. We show formally that when the diameter is four or six or eight, all codewords have even Hamming weight. When the generalized polygon has in addition an equal number of points and lines, we see that the nonregular polygon based code construction has minimum distance that is higher at least by two in comparison with the dual regular polygon code of the same rate and length. A new minimum-distance bound is presented for codes from nonregular polygons of even diameter and equal number of points and lines. Finally, we prove that all codes derived from finite classical generalized quadrangles are quasi-cyclic and we give the explicit size of the circulant blocks in the parity-check matrix. Our simulation studies of several generalized polygon LDPC codes demonstrate powerful bit-error-rate (BER) performance when decoding is carried out via low-complexity variants of belief propagation. 相似文献
18.
This paper describes and analyzes low-density parity-check code families that support variety of different rates while maintaining the same fundamental decoder architecture. Such families facilitate the decoding hardware design and implementation for applications that require communication at different rates, for example to adapt to changing channel conditions. Combining rows of the lowest-rate parity-check matrix produces the parity-check matrices for higher rates. An important advantage of this approach is that all effective code rates have the same blocklength. This approach is compatible with well known techniques that allow low-complexity encoding and parallel decoding of these LDPC codes. This technique also allows the design of programmable analog LDPC decoders. The proposed design method maintains good graphical properties and hence low error floors for all rates. 相似文献
19.
光通信中一种基于有限域循环子群的QC-LDPC码构造方法 总被引:1,自引:1,他引:0
基于有限域循环子群方法提出了一种结构简单,可以灵活选择码长、码率,并且编译码复杂度低的准循环低密度奇偶校验(QC-LDPC)码构造方法。利用此方法构造出适合光通信系统传输的规则QC-LDPC(5334,4955)码。仿真结果表明该码型利用和积迭代译码算法在加性高斯白噪声信道中取得了很好的性能,比已广泛应用于光通信中的经典RS(255,239)码具有更好的纠错性能。因此所构造的QC-LDPC(5334,4955)码能较好地适用于高速长距离光通信系统。 相似文献