The algebraic decoding of the (41, 21, 9) quadratic residue code

A new algebraic approach for decoding the quadratic residue (QR) codes, in particular the (41, 21, 9) QR code, is presented. The key ideas behind this decoding technique are a systematic application of the Sylvester resultant method to the Newton identities associated with the syndromes to find the error-locator polynomial, and next a method for determining error locations by solving certain quadratic, cubic, and quartic equations over GF(2^m) in a new way which uses Zech's logarithms for the arithmetic. The logarithms developed for Zech's logarithms save a substantial amount of computer memory by storing only a table of Zech's logarithms. These algorithms are suitable for implementation in a programmable microprocessor or special-purpose VLSI chip. It is expected that the algebraic methods developed can apply generally to other codes such as the BCH and Reed-Solomon codes     

Algebraic decoding of (71, 36, 11), (79, 40, 15), and (97, 49, 15) quadratic residue codes

Recently, a new algebraic decoding algorithm for quadratic residue (QR) codes was proposed by Truong et al. Using that decoding scheme, we now develop three decoders for the QR codes with parameters (71, 36, 11), (79, 40, 15), and (97, 49, 15), which have not been decoded before. To confirm our results, an exhaustive computer simulation has been executed successfully.     

Hard- and soft-decision decoding beyond the half minimum distance---An algorithm for linear codes (Corresp.)

A decoding algorithm for linear codes that uses the minimum weight words of the dual code as parity checks is defined. This algorithm is able to correct beyond the half minimum distance and has the capability of including soft-decision decoding. Results on applying this algorithm to quadratic residue (QR) codes, BCH codes, and the Golay codes (with and without soft-decision decoding) are presented.     

Decoding the (47,24,11) Quadratic Residue Code Using Bit-Error Probability Estimates

A new algorithm is developed to facilitate faster decoding of the (47,24,11) quadratic residue (QR) code. This decoder, based on the idea first developed by Reed in a 1959 MIT Lincoln Laboratory Report, uses real channel data to estimate the individual bit-error probabilities in a received word. The algorithm then sequentially inverts the bits with the highest probability of error until one of the errors is canceled. The remaining errors are then corrected by the use of algebraic decoding techniques. This new algorithm, called the reliability-search algorithm, is a complete decoder that significantly reduces the decoding complexity in terms of CPU time while maintaining the same bit-error rate (BER) performance. In fact, this algorithm is an appropriate modification to the algorithm developed by Chase.     

Turbo encoding and decoding of Reed-Solomon codes through binary decomposition and self-concatenation

This paper presents a two-stage turbo-coding scheme for Reed-Solomon (RS) codes through binary decomposition and self-concatenation. In this scheme, the binary image of an RS code over GF(2/sup m/) is first decomposed into a set of binary component codes with relatively small trellis complexities. Then the RS code is formatted as a self-concatenated code with itself as the outer code and the binary component codes as the inner codes in a turbo-coding arrangement. In decoding, the inner codes are decoded with turbo decoding and the outer code is decoded with either an algebraic decoding algorithm or a reliability-based decoding algorithm. The outer and inner decoders interact during each decoding iteration. For RS codes of lengths up to 255, the proposed two-stage coding scheme is practically implementable and provides a significant coding gain over conventional algebraic and reliability-based decoding algorithms.     

一种(41, 21, 9)平方剩余码的快速代数译码算法

为了降低译码时的计算复杂度以及减少译码时间,该文通过对牛顿恒等式进行推导得到了(41, 21, 9) QR码不需要计算未知校验子就可求得错误位置多项式系数的代数译码算法,同时也针对改善部分客观地给出了计算复杂度的理论分析。此外,为了进一步降低译码时间,提出判定接收码字中出现不同错误个数的更简化的判断条件。仿真结果表明该文提出算法在不降低Lin算法所达到的译码性能的前提下,降低了译码时间。     

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     

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     

Algebraic Decoding of the $(89, 45, 17)$ Quadratic Residue Code

Recently, an algebraic decoding algorithm suggested by Truong (2005) for some quadratic residue codes with irreducible generating polynomials has been designed that uses the inverse-free Berlekamp–Massey (BM) algorithm to determine the error-locator polynomial. In this paper, based on the ideas of the algorithm mentioned above, an algebraic decoder for the $(89, 45, 17)$ binary quadratic residue code, the last one not decoded yet of length less than $100$ , is proposed. It was also verified theoretically for all error patterns within the error-correcting capacity of the code. Moreover, the verification method developed in this paper can be extended for all cyclic codes without checking all error patterns by computer simulations.      

The algebraic decoding of Goppa codes

An interesting class of linear error-correcting codes has been found by Goppa [3], [4]. This paper presents algebraic decoding algorithms for the Goppa codes. These algorithms are only a little more complex than Berlekamp's well-known algorithm for BCH codes and, in fact, make essential use of his procedure. Hence the cost of decoding a Goppa code is similar to the cost of decoding a BCH code of comparable block length.     

Algebraic soft-decision decoding of Reed-Solomon codes

A polynomial-time soft-decision decoding algorithm for Reed-Solomon codes is developed. This list-decoding algorithm is algebraic in nature and builds upon the interpolation procedure proposed by Guruswami and Sudan(see ibid., vol.45, p.1757-67, Sept. 1999) for hard-decision decoding. Algebraic soft-decision decoding is achieved by means of converting the probabilistic reliability information into a set of interpolation points, along with their multiplicities. The proposed conversion procedure is shown to be asymptotically optimal for a certain probabilistic model. The resulting soft-decoding algorithm significantly outperforms both the Guruswami-Sudan decoding and the generalized minimum distance (GMD) decoding of Reed-Solomon codes, while maintaining a complexity that is polynomial in the length of the code. Asymptotic analysis for alarge number of interpolation points is presented, leading to a geo- metric characterization of the decoding regions of the proposed algorithm. It is then shown that the asymptotic performance can be approached as closely as desired with a list size that does not depend on the length of the code.     

关于Justesen代数几何码

本文通过建立保持Hamming距离的同构,给出了研究Justesen等(1989)所构造的代数几何码的一般方法,并取得一些新的结果。本文在进行译码研究时,首次把同类型的较小的代数几何码的码字与错误位置多项式的值相对应,从而清晰地揭示了译码过程,以及纠错能力。本文还得到一般代数几何码维数的上界和下界。最后给出了一个容易理解的译码算法。此算法类似于RS码的Peterson译码算法。     

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     

On Justesen’s algebraic geometry codes

An isomorphism preserving Hamming distance between two algebraic geometry (AG) codes is presented to obtain the main parameters of Justesen’s algebraic geometry (JAG) codes. To deduce a simple approach to the decoding algorithm, a code word in a “small” JAG code is used to correspond to error-locator polynomial. By this means, a simple decoding procedure and its ability of error correcting are explored obviously. The lower and upper bounds of the dimension of AG codes are also obtained.     

A new high rate code scheme with highly parallel and low complexity decoding algorithm

A new high rate code scheme is proposed in this paper. It consists of serial concatenated recursive systematic ordinary (nonpunctured) convolutional codes with only 8 states in the trellis of the corresponding reciprocal dual codes. With a low complexity and highly parallel decoding algorithm, over additive white Gaussian noise channels, the proposed codes can achieve good bit error rate (BER) performance comparable to that of turbo codes and low density parity check (LDPC) codes. At code rate R=16/17, the overall decoding complexity of the proposed code scheme is almost half that of the LDPC codes.     

Probabilistic construction of large constraint length trellis codesfor sequential decoding

Probabilistic algorithms are given for constructing good large constraint length trellis codes for use with sequential decoding that can achieve the channel cutoff rate bound at a bit error rate (BER) of 10^-5-10^-6. The algorithms are motivated by the random coding principle that an arbitrary selection of code symbols will produce a good code with high probability. One algorithm begins by choosing a relatively small set of codes randomly. The error performance of each of these codes is evaluated using sequential decoding and the code with the best performance among the chosen set is retained. Another algorithm treats the code construction as a combinatorial optimization problem and uses simulated annealing to direct the code search. Trellis codes for 8 PSK and 16 QAM constellations with constraint lengths v up to 20 are obtained. Simulation results with sequential decoding show that these codes reach the channel cutoff rate bound at a BER of 10^-5-10^-6 and achieve 5.0-6.35 dB real coding gains over uncoded systems with the same spectral efficiency and up to 2.0 dB real coding gains over 64 state trellis codes using Viterbi decoding     

Closest coset decoding of |u|u+v| codes

The general concept of closest coset decoding (CCD) is presented, and a soft-decoding technique for block codes that is based on partitioning a code into a subcode and its cosets is described. The computational complexity of the CCD algorithm is significantly less than that required if a maximum-likelihood detector (MLD) is used. A set-partitioning procedure and details of the CCD algorithm for soft decoding of |u|u+v| codes are presented. Upper bounds on the bit-error-rate (BER) performance of the proposed algorithm are combined, and numerical results and computer simulation tests for the BER performance of second-order Reed-Muller codes of length 16 and 32 are presented. The algorithm is a suboptimum decoding scheme and, in the range of signal-to-noise-power-density ratios of interest, its BER performance is only a few tenths of a dB inferior to the performance of the MLD for the codes examined     

On the Search for High-Rate Quasi-Orthogonal Space–Time Block Code

A Quasi-Orthogonal Space–Time Block Code (QO-STBC) is attractive because it achieves higher code rate than orthogonal STBC and lower decoding complexity than non-orthogonal STBC. In this paper, we first derive the algebraic structure of QO-STBC, then we apply it in a novel graph-based search algorithm to find high-rate QO-STBCs with code rates greater than 1. From the four-antenna codes found using this approach, it is found that the maximum code rate is limited to 5/4 with symbolwise diversity level of four, and 4 with symbolwise diversity level of two. The maximum likelihood decoding of these high-rate QO-STBCs can be performed on two separate sub-groups of symbols. The rate-5/4 codes are the first known QO-STBCs with code rate greater 1 that has full symbolwise diversity level.This is the work done when Chau Yuen was with the Nanyang Technological University