ERROR-DETECTING CODES AND UNDETECTED ERROR PROBABILITIES

The definition of good codes for error-detection is given. It is proved that a (n, k) linear block code in GF(q) are the good code for error-detection, if and only if its dual code is also. A series of new results about the good codes for error-detection are derived. New lower bounds for undetected error probabilities are obtained, which are relative to n and k only, and not the weight structure of the codes.     

Improved Low-Density Parity-Check Codes Based on Single Parity-Check Block and Their Performance Analysis on the Binary Erasure Channel

Based on some characteristics of the decoding and the error floors of Low-density parity-check （LDPC） codes, an approach of adding single parity-check blocks to original LDPC blocks over GF（2） is proposed, which can correct multiple block errors in a block group. When this approach is set to have correcting capacity of no more than two block errors in a code group, the performance of ensemble C（n, x^l-1,x^r-1） on the Binary erasure channel （BEC） with this approach is analyzed. The simulation results indicate that when the Block error probability （BEP） drops, the performance of the given LDPC codes can be improved exponentially. Also, the error floors of LDPC codes can be suppressed to much lower levels. Therefore, the short-length LDPC codes have a wide range of applications.     

DECODING ALGORITHM BASED QN REVISED SYNDROME FOR THE BINARY (23,12,7) GOLAY CODE

A decoding algorithm based on revised syndromes to decode the binary (23,12,7) Golay code is presented. The algorithm strongly depends on the algebraic properties of the code. For the algorithm, the worst complexity is about 683 mod2 additions, which is less than that of the algorithms available for the code, the average complexity is approximately 319 mod2 additions, which is slightly more than that of Blaum's algorithm for the code.     

HIGH-PERFORMANCE SIMPLE-ENCODING GENERATOR-BASED SYSTEMATIC IRREGULAR LDPC CODES AND RESULTED PRODUCT CODES

Low-Density Parity-Check (LDPC) code is one of the most exciting topics among the coding theory community.It is of great importance in both theory and practical communications over noisy channels.The most advantage of LDPC codes is their relatively lower decoding complexity compared with turbo codes,while the disadvantage is its higher encoding complexity.In this paper,a new ap- proach is first proposed to construct high performance irregular systematic LDPC codes based on sparse generator matrix,which can significantly reduce the encoding complexity under the same de- coding complexity as that of regular or irregular LDPC codes defined by traditional sparse parity-check matrix.Then,the proposed generator-based systematic irregular LDPC codes are adopted as con- stituent block codes in rows and columns to design a new kind of product codes family,which also can be interpreted as irregular LDPC codes characterized by graph and thus decoded iteratively.Finally, the performance of the generator-based LDPC codes and the resultant product codes is investigated over an Additive White Gaussian Noise (AWGN) and also compared with the conventional LDPC codes under the same conditions of decoding complexity and channel noise.     

Layered Dynamic Schedulings for BP Decoding of LDPC Codes over GF（q）

A Layered dynamic scheduling （LDS） for Belief-propagation （BP） decoding of LDPC codes over GF（q） is presented, which is derived from the dynamic scheduling for the BP decoding of binary LDPC codes. In order to restrain the LDS from cycling in certain checknodes, a life-index for each check-node is adopted and the optimal value of the life-index is analyzed. Furthermore, in consideration of hardware implementation and decoding latency, a strategy, which allows many more checknodes to be updated in parallel, is introduced. Simulations show that the LDS with life-index speeds up the convergence rate and greatly improves the performance of the BP decoding at medium to high signal-to-noise ratio value, and the algorithm employing the LDS with life-index and the new strategy offers good trade-off between the performance and the decoding latency.     

Sparse sequence construction of LDPC codes

This letter proposes a novel and simple construction of regular Low-Density Parity-Check （LDPC） codes using sparse binary sequences. It utilizes the cyclic cross correlation function of sparse sequences to generate codes with girth 8. The new codes perform well using the sumproduct decoding. Low encoding complexity can also be achieved due to the inherent quasi-cyclic structure of the codes.     

A CLASS OF LDPC CODE’S CONSTRUCTION BASED ON AN ITERATIVE RANDOM METHOD

This letter gives a random construction for Low Density Parity Check （LDPC） codes, which uses an iterative algorithm to avoid short cycles in the Tanner graph. The construction method has great flexible choice in LDPC code＇s parameters including codelength, code rate, the least girth of the graph, the weight of column and row in the parity check matrix. The method can be applied to the irregular LDPC codes and strict regular LDPC codes. Systemic codes have many applications in digital communication, so this letter proposes a construction of the generator matrix of systemic LDPC codes from the parity check matrix. Simulations show that the method performs well with iterative decoding.     

A NOVEL LINEAR DIFFERENTIAL SPACE-TIME MODULATION

Based on the Complex Orthogonal Linear Dispersion (COLD) code,a novel linear Differ- ential Space-Time Modulation (DSTM) design is proposed in this paper.Compared with the existing nonlinear DSTM schemes based on group codes,the proposed linear DSTM scheme is easier to design, enjoys full diversity and allows for a simplified differential receiver,which can detect the transmitted symbols separately.Furthermore,compared with the existing linear DSTM based on orthogonal design, our new construction can be applied to any number of transmit antennas.Similar to other algorithms, the proposed scheme also can be demodulated with or without channel estimates at the receiver,but the performance degrades approximately by 3dB when estimates are not available.     

A CLASS OF LDPC CODE''''S CONSTRUCTION BASED ON AN ITERATIVE RANDOM METHOD

This letter gives a random construction for Low Density Parity Check (LDPC) codes, which uses an iterative algorithm to avoid short cycles in the Tanner graph. The construction method has great flexible choice in LDPC code's parameters including codelength, code rate, the least girth of the graph, the weight of column and row in the parity check matrix. The method can be applied to the irregular LDPC codes and strict regular LDPC codes. Systemic codes have many applications in digital communication, so this letter proposes a construction of the generator matrix of systemic LDPC codes from the parity check matrix. Simulations show that the method performs well with iterative decoding.     

TURBO TRELLIS CODE MODULATION USING MQAM

The paper presents a kind of reasonable structure for implementing MQAMT-TCM based on the principles of turbo codes and TCM for the first time.It can also be expanded to PSK T-TCM system,and the corresponding decoding algorithm is derived .By computer simulation,its performance is analyzed .The results show that T-TCM takes the advantages of turbo codes and TCM technology,and is a kind of bandwisth-efficient coded-modulation technique obtaining high coding gain .So,in the future,T-TCM would be applied in many fields.     

Linear codes with Pless structures

Extended Golay codes possess certain two-level structures which are important for decoding the codes. However, these ideal structures are not limited to Golay codes. Here, the structures are generalised to other linear codes. Among which are a binary (20. 9, 7) code, a binary (32, 16, 8) code, a binary (40, 20, 8) code and a ternary (18, 9, 6) code. Similar to the Golay codes, there are also efficient decoding algorithms for these codes, which are sufficiently simple to enable decoding the derived codes by hand calculations     

一类三元线性分组码的译码

Ｐｌｅｓｓ［１］证明了三元（１２，６，６）Ｇｏｌａｙ码具有一种双层结构，并据此给出了该码的快速硬判决译码算法。本文推广了Ｇｏｌａｙ码的Ｐｌｅｓｓ结构，给出了由三元（ｎ，ｋ，ｄ）线性分组码构造的三元（３，ｎ＋ｋ，≥ｍｉｎ（ｎ，２ｄ，６））线性分组码，其中包括（１２，６，６）Ｇｏｌａｙ码和（１８，９，６）码，并以三元（１８，９，６）码为例给出了这类码的最大似然软判决译码算法。     

Maximum likelihood soft decoding of binary block codes and decodersfor the Golay codes

Maximum-likelihood soft-decision decoding of linear block codes is addressed. A binary multiple-check generalization of the Wagner rule is presented, and two methods for its implementation, one of which resembles the suboptimal Forney-Chase algorithms, are described. Besides efficient soft decoding of small codes, the generalized rule enables utilization of subspaces of a wide variety, thereby yielding maximum-likelihood decoders with substantially reduced computational complexity for some larger binary codes. More sophisticated choice and exploitation of the structure of both a subspace and the coset representatives are demonstrated for the (24, 12) Golay code, yielding a computational gain factor of about 2 with respect to previous methods. A ternary single-check version of the Wagner rule is applied for efficient soft decoding of the (12, 6) ternary Golay code     

Nonlinear Product Codes and Their Low Complexity Iterative Decoding

This paper proposes encoding and decoding for nonlinear product codes and investigates the performance of nonlinear product codes. The proposed nonlinear product codes are constructed as N‐dimensional product codes where the constituent codes are nonlinear binary codes derived from the linear codes over higher order alphabets, for example, Preparata or Kerdock codes. The performance and the complexity of the proposed construction are evaluated using the well‐known nonlinear Nordstrom‐Robinson code, which is presented in the generalized array code format with a low complexity trellis. The proposed construction shows the additional coding gain, reduced error floor, and lower implementation complexity. The (64, 24, 12) nonlinear binary product code has an effective gain of about 2.5 dB and 1 dB gain at a BER of 10^?6 when compared to the (64, 15, 16) linear product code and the (64, 24, 10) linear product code, respectively. The (256, 64, 36) nonlinear binary product code composed of two Nordstrom‐Robinson codes has an effective gain of about 0.7 dB at a BER of 10^?5 when compared to the (256, 64, 25) linear product code composed of two (16, 8, 5) quasi‐cyclic codes.     

The Z4-linearity of Kerdock, Preparata, Goethals, andrelated codes

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson (1967), Kerdock (1972), Preparata (1968), Goethals (1974), and Delsarte-Goethals (1975). It is shown here that all these codes can be very simply constructed as binary images under the Gray map of linear codes over Z₄, the integers mod 4 (although this requires a slight modification of the Preparata and Goethals codes). The construction implies that all these binary codes are distance invariant. Duality in the Z₄ domain implies that the binary images have dual weight distributions. The Kerdock and “Preparata” codes are duals over Z₄-and the Nordstrom-Robinson code is self-dual-which explains why their weight distributions are dual to each other. The Kerdock and “Preparata” codes are Z₄-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z₄, which greatly simplifies encoding and decoding. An algebraic hard-decision decoding algorithm is given for the “Preparata” code and a Hadamard-transform soft-decision decoding algorithm for the I(Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z₄ , but extended Hamming codes of length n⩾32 and the Golay code are not. Using Z₄-linearity, a new family of distance regular graphs are constructed on the cosets of the “Preparata” code     

Golay码的快速译码

本文利用Ｇｏｌａｙ码的代数结构给出了二元（２３，１２，７）Ｇｏｌａｙ码及三元（１１，６，５）Ｇｏｌａｙ码新的译码算法。对于二元Ｇｏｌａｙ码，所提的算法的最坏时间复杂性为５３４次ｍｏｄ２加法，比已知的同类译码算法的时间复杂性都小；平均时间复杂性为２２４次ｍｏｄ２加法，比目前已知的最快的译码算法的平均时间复杂性２７９次ｍｏｄ２加法还要小。对于三元Ｇｏｌａｙ码，所提算法的最坏时间复杂性为１２３次ｍｏｄ３加法，平均时间复杂性为８５次ｍｏｄ３加法，比同类的算法都快。此外，这里给出的算法结构简单，易于实现。     

Minimal permutation sets for decoding the binary Golay codes (Corresp.)

For permutation decoding of aneerror-correcting linear code, a set of permutations which move all error vectors of weightleq eout of the information places is needed. A method of finding minimal decoding sets is given, along with minimal sets obtained with this method for the binary Golay codes.     

On high-speed decoding of the (23,12,7) Golay code

An algebraic decoding method for triple-error-correcting binary BCH codes applicable to complete decoding of the (23,12,7) Golay code has been proved by M. Elia (see ibid., vol.IT-33, p.150-1, 1987). A modified step-by-step complete decoding algorithm of this Golay code is introduced which needs fewer shift operations than Kasami's error-trapping decoder. Based on the algorithm, a high-speed hardware decoder of this code is proposed     

A characterization of MMD codes

Let C be a linear [n,k,d]-code over GF(q) with k⩾2. If s=n-k+1-d denotes the defect of C, then by the Griesmer bound, d⩽(s+1)q. Now, for obvious reasons, we are interested in codes of given defect s for which the minimum distance is maximal, i.e., d=(s+1)q. We classify up to formal equivalence all such linear codes over GF(q). Remember that two codes over GF(q) are formally equivalent if they have the same weight distribution. It turns out that for k⩾3 such codes exist only in dimension 3 and 4 with the ternary extended Golay code, the ternary dual Golay code, and the binary even-weight code as exceptions. In dimension 4 they are related to ovoids in PG(3,q) except the binary extended Hamming code, and in dimension 3 to maximal arcs in PG(2,q)     

环Fp+uFp上的Kerdock码和Preparata码

 Kerdock码和Preparata码是两类著名的二元非线性码,它们比相同条件下的线性码含有更多的码字.Hammons等人在1994年发表的文献中证明了这两类码可视为环Z₄上循环码在Gray映射下的像,从而使得这两类码的编码和译码变得非常简单.环F₂+uF₂是介于环Z₄与域F₄之间的一种四元素环,因此分享了环Z₄与域F₄的一些好的性质,此环上的编码理论研究成为一个新的热点.本文首次将Kerdock码和Preparata码的概念引入到环F_p+uF_p上,证明了它们是一对对偶码;并给出Kerdock码的迹表示;当p=2时,建立了环F₂+uF₂上这两类码与域F₂上的Reed-Muller码之间的联系;并证明了二元一阶Reed-Muller码是环F₂+uF₂上Kerdock码的线性子码的Gray像.