Recursive error correction for general Reed-Muller codes

Reed-Muller (RM) codes of growing length n and distance d are considered over a binary symmetric channel. A recursive decoding algorithm is designed that has complexity of order nlogn and corrects most error patterns of weight (dlnd)/2. The presented algorithm outperforms other algorithms with nonexponential decoding complexity, which are known for RM codes. We evaluate code performance using a new probabilistic technique that disintegrates decoding into a sequence of recursive steps. This allows us to define the most error-prone information symbols and find the highest transition error probability p, which yields a vanishing output error probability on long codes.     

Redundancies of correction capability optimized Reed-Muller codes

This article is focused on some variations of Reed-Muller codes that yield improvements to the rate for a prescribed decoding performance under the Berlekamp-Massey-Sakata algorithm with majority voting. Explicit formulas for the redundancies of the new codes are given.     

Dynamic Programming in Digital Communications: Viterbi Decoding to Turbo Multiuser Detection

Many important signal processing tasks in digital communications are based on integer programming problems whose raw complexity is extremely high. Such problems include the decoding of convolutional codes, channel equalization, multiuser detection, and the joint performance of these tasks. In each of these problems, the high complexity arises from the need to perform simultaneous processing on long sequences of finite-valued symbols in order to optimally detect or decode them. Fortunately, the complexity of these optimization problems can often be greatly reduced through the use of dynamic programming, which efficiently finds optimal [e.g., maximum likelihood (ML) or maximum a posteriori probability (MAP)] decisions in long sequences of symbols. This paper reviews four decades of progress in this area: the Viterbi algorithm for ML decoding of convolutional codes of the 1960s; the ML sequence detectors for channel equalization and the BCJR algorithm for MAP decoding of convolutional codes of the 1970s; the ML and MAP multiuser detectors of the 1980s; and combinations of these through the turbo processing of the 1990s.     

Bounds for the Multicovering Radii of Reed-Muller Codes with Applications to Stream Ciphers

The multicovering radii of a code are recentgeneralizations of the covering radius of a code. For positivem, the m-covering radius of C is the leastradius t such that everym-tuple of vectors is contained in at least one ball of radiust centered at some codeword. In this paper upper bounds arefound for the multicovering radii of first order Reed-Muller codes. These bounds generalize the well-known Norse bounds for the classicalcovering radii of first order Reed-Muller codes. They are exactin some cases. These bounds are then used to prove the existence of secure families of keystreams against a general class of cryptanalytic attacks. This solves the open question that gave rise to the study ofmulticovering radii of codes.     

Partial permutation decoding for the first-order Reed-Muller codes

Partial permutation decoding is shown to apply to the first-order Reed-Muller codes R(1,m), where m>4 by finding s-PD-sets for these codes for 2≤s≤4.     

Reed-Muller codes and permutation decoding

We show that the first- and second-order Reed-Muller codes, R(1,m) and R(2,m), can be used for permutation decoding by finding, within the translation group, (m−1)- and (m+1)-PD-sets for R(1,m) for m≥5,6, respectively, and (m−3)-PD-sets for R(2,m) for m≥8. We extend the results of Seneviratne [P. Seneviratne, Partial permutation decoding for the first-order Reed-Muller codes, Discrete Math., 309 (2009), 1967-1970].     

Characterizations of pseudo-codewords of (low-density) parity-check codes

An important property of low-density parity-check codes is the existence of highly efficient algorithms for their decoding. Many of the most efficient, recent graph-based algorithms, e.g. message-passing iterative decoding and linear programming decoding, crucially depend on the efficient representation of a code in a graphical model. In order to understand the performance of these algorithms, we argue for the characterization of codes in terms of a so-called fundamental cone in Euclidean space. This cone depends upon a given parity-check matrix of a code, rather than on the code itself. We give a number of properties of this fundamental cone derived from its connection to unramified covers of the graphical models on which the decoding algorithms operate. For the class of cycle codes, these developments naturally lead to a characterization of the fundamental cone as the Newton polyhedron of the Hashimoto edge zeta function of the underlying graph.     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

New advances in permutation decoding of first-order Reed-Muller codes

In this paper we describe a variation of the classical permutation decoding algorithm that can be applied to any affine-invariant code with respect to certain type of information sets. In particular, we can apply it to the family of first-order Reed-Muller codes with respect to the information sets introduced in [2]. Using this algorithm we improve considerably the number of errors we can correct in comparison with the known results in this topic.     

Reed-Muller codes and Barnes-Wall lattices: Generalized multilevel constructions and representation over GF(2<Superscript><Emphasis Type="Italic">q</Emphasis></Superscript>)

Generalized multilevel constructions for binary RM(r,m) codes using projections onto GF(2 ^q ) are presented. These constructions exploit component codes over GF(2), GF(4),..., GF(2 ^q ) that are based on shorter Reed-Muller codes and set partitioning using partition chains of length-2 ^l codes. Using these constructions we derive multilevel constructions for the Barnes-Wall Λ(r,m) family of lattices which also use component codes over GF(2), GF(4),..., GF(2 ^q ) and set partitioning based on partition chains of length-2 ^l lattices. These constructions of Reed-Muller codes and Barnes-Wall lattices are readily applicable for their efficient decoding.      

Maximal Weight Divisors of Projective Reed-Muller Codes

Projective Reed-Muller (PRM) codes, as the name suggests, are the projective analogues of generalized Reed-Muller codes. The parameters are known, and small steps have been taken towards pinning down the codeword weights that occur in any PRM code. We determine, for any PRM code, the greatest common divisor of its codeword weights.     

A note on Reed-Muller codes

In this paper we study linear codes that are obtained by annexing some vectors to the basis vectors of a Reed-Muller code of order r.     

Hartmann–Tzeng bound and skew cyclic codes of designed Hamming distance

The use of skew polynomial rings allows to endow linear codes with cyclic structures which are not cyclic in the classical (commutative) sense. Whenever these skew cyclic structures are carefully chosen, some control over the Hamming distance is gained, and it is possible to design efficient decoding algorithms. In this paper, we give a version of the Hartmann–Tzeng bound that works for a wide class of skew cyclic codes. We also provide a practical method for constructing them with designed distance. For skew BCH codes, which are covered by our constructions, we discuss decoding algorithms. Detailed examples illustrate both the theory as the constructive methods it supports.     

The New Minimum Distance Bounds of Goppa Codes and Their Decoding

A couple of new lower bounds of the minimum distance of Goppa codes is derived, using an extended field code for a Goppa code which contains the Goppa code as its subfield-subcode. Also presented are procedures for both error-only and error-and-erasure decoding for Goppa codes up to the new lower bounds, based on the Berlekamp-Massey algorithm and the Feng-Tzeng multisequence shift-register synthesis algorithms which have been used for decoding cyclic codes up to the BCH and HT(Hartmann-Tzeng) bounds.     

多址可加信道分组码的唯一可译性

本文对多址可加信道分组编码进行了研究，得出了唯一可译性的充要条件及有关判别准则，并对译码算法进行了探讨．     

Bounds on collaborative decoding of interleaved Hermitian codes and virtual extension

We derive the maximum decoding radius for interleaved Hermitian (IH) codes if a collaborative decoding scheme is used. A decoding algorithm that achieves this bound, which is based on a division decoding algorithm, is given. Based on the decoding radius for the interleaved codes, we derive a bound on the code rate below which virtual extension of non-interleaved Hermitian codes can improve the decoding capabilities.     

On the enumeration of self-dual codes

We give the complete classification of all binary, self-dual, doubly-even (32, 16) codes. There are 85 non-equivalent, self-dual, doubly-even (32, 16) codes. Five of these have minimum weight 8, namely, a quadratic residue code and a Reed-Muller code, and three new codes. A set of generators is given for a code in each equivalence class together with its entire weight distribution and the order of its entire group with other information facilitating the computation of permutation generators. From this list it is possible to identify all self-dual codes of length less than 32 and the numbers of these are included.     

Weight enumeration of codes from finite spaces

We study the generalized and extended weight enumerator of the q-ary Simplex code and the q-ary first order Reed-Muller code. For our calculations we use that these codes correspond to a projective system containing all the points in a finite projective or affine space. As a result from the geometric method we use for the weight enumeration, we also completely determine the set of supports of subcodes and words in an extension code.     

The weight distributions of some cyclic codes with three or four nonzeros over \mathbb F _3

Because of efficient encoding and decoding algorithms comparing with linear block codes, cyclic codes form an important family and have applications in communications and storage systems. However, their weight distributions are known only for a few cases mainly on the codes with no more than three nonzeros. In this paper, the weight distributions of two classes of cyclic codes with three or four nonzeros are determined.