Short codes with a given covering radius

The covering radius r of a code is the maximum distance from any vector in the space containing the code to the nearest codeword. The authors introduce a new function l(m,r), called the length function, which equals the smallest length of a binary code of codimension m and covering radius r. They investigate basic properties of the length function. Projective geometries over larger fields are used to construct families of codes which improve significantly the upper bound for l(m,2) obtained by amalgamation of Hamming codes. General methods are developed for ruling out the existence of codes of covering radius 2 with a given codimension and length resulting in lower bounds for l(m,2). A table is presented which gives the best results now known for l(m,r) with m⩽12 and r⩽12     

Bounds for abnormal binary codes with covering radius one

The normality of binary codes is studied. The minimum cardinality of a binary code of length n with covering radius R is denoted by K(n,R). It is assumed that C is an (n,M)R code, that is, a binary code of length n with M codewords and covering radius R. It is shown that if C is an (n,M)1 code, then it is easy to find a normal (n ,M)1 code by changing C in a suitable way, and that all the optimal (n,M)1 codes (i.e. those for which M=K(n,1)) are normal and their every coordinate is acceptable. It is shown that if C is an abnormal (n,M) code, then n⩾9, and an abnormal (9118)1 code which is the smallest abnormal code known at present, is constructed. Lower bounds on the minimum cardinality of a binary abnormal code of length n with covering radius 1 are derived, and it is shown that if an (n,M)1 code is abnormal, then M⩾96     

Some 3-error-correcting BCH codes have covering radius 5 (Corresp.)

The coset leader of greatest weight in the 3-error-correcting BCH code of length2^{m}-1has weight 5, for oddm geq 5.     

On the structure of linear codes with covering radius two and three

We obtain new bounds on l(m,r), the minimum length of a linear code with codimension m and covering radius r. All bounds are derived in a uniform way. We employ results from coding theory, some earlier results on covering codes, and combinatorial arguments. We prove the following bounds: l(6, 2)=13, l(7,2)=19, l(8,2)⩾25, l(9,2)⩾34, l(2m-l,2)⩾2^m+1 for m⩾3, l(14,2)⩾182, l(16,2)⩾363, l(18,2)⩾725, l(20,2)⩾1449, l(22,2)⩾2897, l(24,2)⩾5794, l(9,3)⩾17, l(10,3)⩾21, l(12,3)⩾31, l(13,3)⩾38     

On the least covering radius of binary linear codes with small lengths

Using classification of codes with a certain covering radius it is proved that the least covering radius t[17,6]=5; t[17,8]=4; t[18,7]=5; t[19,7]=5; t[20,8]=5; and t[21,7]=6. As a corollary, four improvements on the length function l(m,R) are found. It is also shown that there exists a unique[14,6] code with covering radius 3.     

Packing radius, covering radius, and dual distance

Tietaivainen (1991) derived an upper bound on the covering radius of codes as a function of the dual distance. This was generalized to the minimum distance, and to Q-polynomial association schemes by Levenshtein and Fazekas. Both proofs use a linear programming approach. In particular, Levenshtein and Fazekas (1990) use linear programming bounds for codes and designs. In this article, proofs relying solely on the orthogonality relations of Krawtchouk (1929), Lloyd, and, more generally, Krawtchouk-adjacent orthogonal polynomials are derived. As a by-product upper bounds on the minimum distance of formally self-dual binary codes are derived     

All binary 3-error-correcting BCH codes of length2^m-ihave covering radius 5 (Corresp.)

Van der Horst and Berger have conjectured that the covering radius of the binary 3-error-correcting Bose-Chaudhuri-Hocquenghem (BCH) code of length2^{m} - l, m geq 4is 5. Their conjecture was proved earlier whenm equiv 0, 1, or 3 (mod 4). Their conjecture is proved whenm equiv 2(mod 4).     

投影几何LDPC码的构造及其在MIMO-OFDM系统中的性能分析

简要介绍低密度奇偶校验码（LDPC码）的发展历史及其码结构，重点研究基于投影几何的LDPC码的系统化构造方法，并将其作为信道编码加入基于IEEE802．16d标准的MIMO-OFDM系统中进行仿真，与级联RS-CC码进行性能对比与分析。最后得出结论，投影几何LDPC码将有可能作为下一代无线通信系统的一项关键技术被广泛采用。     

Weight distribution of translates, covering radius, and perfect codes correcting errors of given weights

LetVbed binary linear(n,k)code defined by a check matrixHand leth(x)be the characteristic function for the set of columns ofH. Connections between the Walsh transform ofh(x)and the weight distributions of all translates of the code are obtained. Explicit formulas for the weight distributions of translates are given for small weightsi(i<8). The computation of the weight distribution of all translates (including the code itself) fori<8requires at most7(n-k)2^{n-k}additions and subtractions,6 cdot 2^{n-k}multiplications and2^{n-k+l}memory cells. This method may be very effective if there is an analytic expression forh(x). A simple method for computing the covering radius of the code by the Walsh transform ofh(x)is described. The implementation of this method requires for largenat most2^{n-k}(n-k) log_{2}(n-k)arithmetical operations and2^{n-k+1}memory cells. We define the conceptL-perfect for codes, whereLis a set of weights. After describing several linear and nonlinearL-perfect codes, necessary and sufficient conditions for a code to beL-perfect in terms of the Walsh transform ofh(x)are established. An analog of the Lloyd theorem for such codes is proved.     

Constructions, families, and tables of binary linear covering codes

Presents constructions and infinite families of binary linear covering codes with covering radii R=2,3,4. Using these codes, the authors obtain a table of constructive upper bounds on the length function l(r,R) for r⩽64 and R=2,3,4, where l(r, R) is the smallest length of a binary linear code with given codimension r and covering radius R. They obtain also upper bounds on l(r, R) for r=21, 28, R=5. Parameters of the constructed codes are better than parameters of previously known codes     

Binary sequence sets with favorable correlations from differencesets and MDS codes

We propose new families of pseudorandom binary sequences based on Hadamard difference sets and MDS codes. We obtain, for p=4k-1 prime and t an integer with 1⩽t⩽(p-1)/2, a set of p^t binary sequences of period p² whose peak correlation is bounded by 1+2t(p+1). The sequences are balanced, have high linear complexity, and are easily generated     

Linear codes in generalized construction of resilient functions with very high nonlinearity

We provide a new generalized construction method for highly nonlinear t-resilient functions, F:F/sub 2//sup n//spl rarr/ F/sub 2//sup m/. The construction is based on the use of linear error-correcting codes together with highly nonlinear multiple output functions. Given a linear [u, m, t+1] code we show that it is possible to construct n-variable, m-output, t-resilient functions with very high nonlinearity for n>u. The method provides the currently best known nonlinearity results for most of the cases.     

Entropy/length profiles, bounds on the minimal covering ofbipartite graphs, and trellis complexity of nonlinear codes

The trellis representation of nonlinear codes is studied from a new perspective. We introduce the new concept of entropy/length profile (ELP). This profile can be considered as an extension of the dimension/length profile (DLP) to nonlinear codes. This elaboration of the DLP, the entropy/length profiles, appears to be suitable to the analysis of nonlinear codes. Additionally and independently, we use well-known information-theoretic measures to derive novel bounds on the minimal covering of a bipartite graph by complete subgraphs. We use these bounds in conjunction with the ELP notion to derive both lower and upper bounds on the state complexity and branch complexity profiles of (nonlinear) block codes represented by any trellis diagram. We lay down no restrictions on the trellis structure, and we do not confine the scope of our results to proper or one-to-one trellises only. The basic lower bound on the state complexity profile implies that the state complexity at any given level cannot be smaller than the mutual information between the past and the future portions of the code at this level under a uniform distribution of the codewords. We also devise a different probabilistic model to prove that the minimum achievable state complexity over all possible trellises is not larger than the maximum value of the above mutual information over all possible probability distributions of the codewords. This approach is pursued further to derive similar bounds on the branch complexity profile. To the best of our knowledge, the proposed upper bounds are the only upper bounds that address nonlinear codes. The novel lower bounds are tighter than the existing bounds. The new quantities and bounds reduce to well-known results when applied to linear codes     

Linear codes for sources and source networks: Error exponents, universal coding

For Slepian-Wolf source networks, the error exponents obtained by Körner,Marton, and the author are shown to be universally attainable by linear codes also. Improved exponents are derived for linear codes with "large rates." Specializing the results to simple discrete memoryless sources reveals their relationship to the random coding and expurgated bounds for channels with additive noise. One corollary is that there are universal linear codes for this class of channels which attain the random coding error exponent for each channel in the class. The combinatorial approach of Csiszár-Körner-Marton is used. In particular, all results are derived from a lemma specifying good encoders in terms of purely combinatorial properties.     

Construction of nonbinary cyclic, quasi-cyclic and regular LDPC codes: a finite geometry approach

This paper presents five methods for constructing nonbinary LDPC codes based on finite geometries. These methods result in five classes of nonbinary LDPC codes, one class of cyclic LDPC codes, three classes of quasi-cyclic LDPC codes and one class of structured regular LDPC codes. Experimental results show that constructed codes in these classes decoded with iterative decoding based on belief propagation perform very well over the AWGN channel and they achieve significant coding gains over Reed-Solomon codes of the same lengths and rates with either algebraic hard-decision decoding or Kotter-Vardy algebraic soft-decision decoding at the expense of a larger decoding computational complexity.     

Short binary convolutional codes with maximal free distance for rates 2/3 and 3/4 (Corresp.)

A search procedure is developed to find good short binary(N,N - 1)convolutional codes. It uses simple rules to discard from the complete ensemble of codes a large fraction whose free distanced_{free}either cannot achieve the maximum value or is equal tod_{free}of some code in the remaining set. Farther, the search among the remaining codes is started in a subset in which we expect the possibility of finding codes with large values ofd_{free}to be good. A number of short, optimum (in the sense of maximizingd_{free}), rate-2/3 and 3/4 codes found by the search procedure are listed.     

Short convolutional codes with maximal free distance for rates 1/2, 1/3, and 1/4 (Corresp.)

This paper gives a tabulation of binary convolutional codes with maximum free distance for ratesfrac{1}{2}, frac{1}{3}, andfrac{1}{4}for all constraint lengths (measured in information digits)nuup to and includingnu = 14. These codes should be of practical interest in connection with Viterbi decoders.     

Power spectra of 6B4T and 3B2T codes

By means of a successive approximation approach, it is possible to calculate the power spectral density of unbounded block codes, 6B4T and 3B2T, using previously developed Line Code programs.     

Quantum codes [[6, 2, 3]]/sub p/ and [[7, 3, 3]]/sub p/ (p /spl ges/ 3) exist

We prove that nonbinary quantum stabilizer codes with parameters [[n, k, d]]/sub p/ = [[6, 2, 3]]/sub p/ and [[7, 3, 3]]/sub p/ exist for all odd primes p by using graph machinery, given by Schlingemann and Werner(see Phys. Rev. A, vol.65, no.012308, 2001), with a little number theory and combinatorics.     

Optimal free distance convolutional codes for rates 1/2, 1/3 and1/4

Optimum distance profile (ODP) codes are good codes for convolutional codes. These codes can be determined using sieve techniques and the improved Cedervall-Johannesson algorithm. The authors present extensive lists of OFD codes containing rates R=1/2, 1/3 and 1/4