Weight enumerator for second-order Reed-Muller codes

In this paper, we establish the following result. Theorem:A_i, the number of codewords of weightiin the second-order binary Reed-Muller code of length2^mis given byA_i = 0unlessi = 2^{m-1}or2^{m-1} pm 2^{m-l-j}, for somej, 0 leq j leq [m/2], A_0 = A_{2^m} = 1, and begin{equation} begin{split} A_{2^{m-1} pm 2^{m-1-j}} = 2^{j(j+1)} &{frac{(2^m - 1) (2^{m-1} - 1 )}{4-1} } \ .&{frac{(2^{m-2} - 1)(2^{m-3} -1)}{4^2 - 1} } cdots \ .&{frac{(2^{m-2j+2} -1)(2^{m-2j+1} -1)}{4^j -1} } , \ & 1 leq j leq [m/2] \ end{split} end{equation} begin{equation} A_{2^{m-1}} = 2 { 2^{m(m+1)/2} - sum_{j=0}^{[m/2]} A_{2^{m-1} - 2^{m-1-j}} }. end{equation}     

The weight hierarchies of some product codes

We determine the weight hierarchies of the product of an n-tuple space and an arbitrary code, the product of an m-dimensional even-weight code and the [24,12,8] extended Golay code, and the product of an m-dimensional even-weight code and the [8,4,4] extended Hamming code. The conjecture d_r=d*_r is proven for all three cases     

Some results on the weight distribution of linear codes

By studying the algebraic structure of the parity check matrix of a linear code we show that the weight distribution is a function only of the quantitiesN_{upsilon}^{u}, the number ofupsiloncolumns of the parity check matrix with ranku. We apply this to obtain a new formula for the weight distribution of the distance3 s-ary Hamming code and for the distance4 s-ary conic code. We give the definition of a conic code and some of its properties.     

On the input-output weight enumerators of product accumulate codes

In this letter, a generalized MacWilliams transform that relates the input-redundancy weight enumerator of a systematic binary linear block code to that of its dual code is first presented. Based on this transform, the input-output weight enumerators of direct-product single-parity-check codes and the type-II product-accumulate codes are then derived, and used to analyze the asymptotic bit error performance of these codes.     

An average weight-distance enumerator for binary expansions ofReed-Solomon codes

An average Hamming weight enumerator is derived for the codewords at each Hamming distance from a received pattern in the set of all possible binary expansions of a Reed-Solomon code. Since these codes may be decoded by list decoders, such as those studied by Sudan (1997), the enumerator can be used to estimate the average number of codewords in the list returned by such a decoder     

Asymptotically Gaussian weight distribution and performance of multicomponent turbo block codes and product codes

It was suggested by Battail that a good long linear code should have a weight distribution close to that of random coding, rather than a large minimum distance, and a turbo code should be also designed using a random-like criterion. In this paper, we first show that the weight distribution of a high-rate linear block code is approximately Gaussian if the code rate is close enough to one, and then proceed to construct a low-rate linear block code with approximately Gaussian weight distribution by using the turbo-coding technique. We give a sufficient condition under which the weight distribution of multicomponent turbo block (MCTB) codes (multicomponent product (MCP) codes, respectively) can approach asymptotically that of random codes, and further develop two classes of MCTB codes (MCP codes) satisfying this condition. Simulation results show that MCTB codes (MCP codes) having asymptotically Gaussian weight distribution can asymptotically approach Shannon's capacity limit. MCTB codes based on single parity-check (SPC) codes have a far poorer minimum distance than MCP codes based on SPC codes, but we show by simulation that when the bit-error rate is in the important range of 10/sup -1/-10/sup -5/, these codes can still offer similar performance for the additive white Gaussian noise channel, as long as the code length of the SPC codes is not very short. These facts confirm in a more precise way Battail's inference about the "nonimportance" of the minimum distance for a long code.     

More on the distance distribution of BCH codes

We derive a new estimate for the error term in the binomial approximation to the distance distribution of BCH codes. This is an improvement on the earlier bounds by Kasami-Fujiwara-Lin (1985), Vladuts-Skorobogatov (1991), and Krasikov-Litsyn (1995)     

More on the minimum distance of cyclic codes

It was recently shown that the so-called Jensen bound is generally weaker than the product method and the shifting method introduced by van Lint and Wilson (1986). It is shown that the minimum distance of the two cyclic codes of length 65 (for which it is known that the product method does not produce the desired result) can be proved using Jensen's method (1985) with some adaptations     

New classes of binary codes constructed on the basis of concatenated codes and product codes

We present new classes of binary codes that are constructed on the basis of concatenated codes and product codes. We discuss the random-error-correction capabilities of these codes. Some examples of the codes for the correction of random errors are given which have at least as many codewords as the best codes previously known (to the authors) with the same minimum distance and same number of check symbols. The burst-error-correction capabilities of the codes are also discussed. Several examples of the codes for the correction of both random errors and burst errors are given. A decoding algorithm for the codes is also described.     

Some results on the norm of codes

Two upper bounds for the norm N(C) of a binary linear code C with minimal weight d and covering radius R are given. The second of these bounds implies that C is normal if R=3     

More on the decoder error probability for Reed-Solomon codes

A combinatorial technique similar to the principle of inclusion and exclusion is used to obtain an exact formula for P_E (u), the decoder error probability for Reed-Solomon codes. The P_E(u) for the (255, 223) Reed-Solomon code used by NASA and for the (31, 15) Reed-Solomon code (JTIDS code) are calculated using the exact formula and are observed to approach the Qs of the codes rapidly as u gets large. An upper bound for the expression |P_E(u)/ Q-1| is derived and shown to decrease nearly exponentially as u increases     

Generalized tensor product codes

A class of binary error-correcting codes, called generalized tensor product codes, is presented with their decoding algorithm. These codes are constructed by combining a number of codes on various extension fields with shorter binary codes. A general algorithm is provided to do bounded distance decoding for these codes. Simply decodable codes such as Wolf's tensor product codes are shown to be special cases of this class of codes. Simply decodable and more efficient codes than Wolf's codes are also included as special cases.     

基于校验子的Turbo乘积码仿真研究

针对Turbo乘积码译码延时的问题,提出一种基于校验子的Turbo乘积码译码算法(S-TPC),该算法根据校验子的值采取不同方式对每行(列)进行译码,节省了一部分校验子为0的码字的硬判决译码运算量。仿真结果表明,S-TPC(32,26)在迭代4次时,能在不降低译码性能的情况下,减少近50%的计算量。     

Near-optimum decoding of product codes: block turbo codes

This paper describes an iterative decoding algorithm for any product code built using linear block codes. It is based on soft-input/soft-output decoders for decoding the component codes so that near-optimum performance is obtained at each iteration. This soft-input/soft-output decoder is a Chase decoder which delivers soft outputs instead of binary decisions. The soft output of the decoder is an estimation of the log-likelihood ratio (LLR) of the binary decisions given by the Chase decoder. The theoretical justifications of this algorithm are developed and the method used for computing the soft output is fully described. The iterative decoding of product codes is also known as the block turbo code (BTC) because the concept is quite similar to turbo codes based on iterative decoding of concatenated recursive convolutional codes. The performance of different Bose-Chaudhuri-Hocquenghem (BCH)-BTCs are given for the Gaussian and the Rayleigh channel. Performance on the Gaussian channel indicates that data transmission at 0.8 dB of Shannon's limit or more than 98% (R/C>0.98) of channel capacity can be achieved with high-code-rate BTC using only four iterations. For the Rayleigh channel, the slope of the bit-error rate (BER) curve is as steep as for the Gaussian channel without using channel state information     

On the weight distribution of linear block codes formed fromconvolutional codes

We explain how to obtain the weight enumerator and the performance of linear block codes formed in several distinct ways from a convolutional code     

Further results on the covering radius of codes

A number of upper and lower bounds are obtained forK(n, R), the minimal number of codewords in any binary code of lengthnand covering radiusR. Several new constructions are used to derive the upper bounds, including an amalgamated direct sum construction for nonlinear codes. This construction works best when applied to normal codes, and we give some new and stronger conditions which imply that a linear code is normal. An upper bound is given for the density of a covering code over any alphabet, and it is shown thatK(n + 2, R + 1) leq K(n, R)holds for sufficiently largen.     

On the weight structure of Reed-Muller codes

The following theorem is proved. Letf(x_1,cdots, x_m)be a binary nonzero polynomial ofmvariables of degreenu. H the number of binarym-tuples(a_1,cdots, a_m)withf(a_1, cdots, a_m)= 1 is less than2^{m-nu+1}, thenfcan be reduced by an invertible affme transformation of its variables to one of the following forms. begin{equation} f = y_1 cdots y_{nu - mu} (y_{nu-mu+1} cdots y_{nu} + y_{nu+1} cdots y_{nu+mu}), end{equation} wherem geq nu+muandnu geq mu geq 3. begin{equation} f = y_1 cdots y_{nu-2}(y_{nu-1} y_{nu} + y_{nu+1} y_{nu+2} + cdots + y_{nu+2mu -3} y_{nu+2mu-2}), end{equation} This theorem completely characterizes the codewords of thenuth-order Reed-Muller code whose weights are less than twice the minimum weight and leads to the weight enumerators for those codewords. These weight formulas are extensions of Berlekamp and Sloane's results.     

Single parity check product codes

This paper considers the performance of iteratively decoded single parity check (SPC) multidimensional product codes in an additive white Gaussian noise channel. Asymptotic performance bounds are compared to simulation results. A new code structure based on SPC product codes is introduced. This structure involves interleaving between the encoding of each dimension in the product code. An analysis of the weight distribution is used to explain the good performance results for these randomly interleaved SPC product codes     

Shadow codes and weight enumerators

The technique of using shadow codes to build larger self-dual codes is extended to codes over arbitrary fields. It is shown how to build the codes and how to determine the new weight enumerator as well. For codes over fields equipped with a square root of -1 and not of characteristic 2, a self-dual code of length n+2 can be built from a self-dual code of length n; for codes over a field without a square root of -1 and not of characteristic 2 a self-dual code of length n+4 is built from a self-dual code of length n; and for codes over fields of characteristic 2 the length of the new self-dual code depends on the presence of the all-one vector in the subcode chosen. In certain cases using the subcode of vectors orthogonal to the all-one vector, the new weight enumerator can be calculated directly from the original weight enumerator. Specific examples of the technique are illustrated for codes over F₃, F₄, and F₅     

Some results on the covering radii of Reed-Muller codes

Let R(r,m) be the rth-order Reed-Muller code of length 2^m and let ρ(r,m ) be its covering radius. R(2,7), R(2,8), R (3,7), and R(4,8) are among those smallest Reed-Muller codes whose covering radii are not known. New bounds for the covering radii of these four codes are obtained. The results are ρ(2,7)⩾40, ρ(2,8)⩾84, 20⩽ρ(3,7)⩽23, and ρ(4,8)⩾22. Noncomputer proofs for the known results that ρ(2,6)=18 and that R(1,5) is normal are given