Optimal linear codes from matrix groups

New linear codes (sometimes optimal) over the finite field with q elements are constructed. In order to do this, an equivalence between the existence of a linear code with a prescribed minimum distance and the existence of a solution of a certain system of Diophantine linear equations is used. To reduce the size of the system of equations, the search for solutions is restricted to solutions with special symmetry given by matrix groups. This allows to find more than 400 new codes for the case q=2,3,4,5,7,9.     

Optimal quaternary linear codes of dimension five

Let d_q(n,k) be the maximum possible minimum Hamming distance of a q-ary [n,k,d]-code for given values of n and k. It is proved that d₄ (33,5)=22, d₄(49,5)=34, d₄ (131,5)=96, d₄(142,5)=104, d₄(147,5)=108, d ₄(152,5)=112, d₄(158,5)=116, d₄(176,5)⩾129, d₄(180,5)⩾132, d₄(190,5)⩾140, d₄(195,5)=144, d₄(200,5)=148, d₄(205,5)=152, d₄(216,5)=160, d₄(227,5)=168, d₄(232,5)=172, d₄(237,5)=176, d₄(240,5)=178, d₄(242,5)=180, and d₄(247,5)=184. A survey of the results of recent work on bounds for quaternary linear codes in dimensions four and five is made and a table with lower and upper bounds for d₄(n,5) is presented     

Optimal binary linear codes and Z4-linearity

We give necessary and sufficient conditions for a binary linear code to be Z₄-linear. Especially we treat optimal, binary linear codes and determine all such codes with minimum weight less or equal to six which are Z₄-linear     

Sequences of optimal identifying codes

Locating faulty processors in a multiprocessor system gives the motivation for identifying codes. Denote by l the maximum number of simultaneously malfunctioning processors. We show that if l⩾3, then the problem of finding the smallest cardinality of a (1, ⩽l)-identifying code in a binary hypercube is equivalent to the problem of finding the smallest size of a (2l-1)-fold 1-covering. This observation yields infinite sequences of optimal identifying codes for every l (l⩾3)     

On robust and dynamic identifying codes

A subset C of vertices in an undirected graph G=(V,E) is called a 1-identifying code if the sets I(v)={u/spl isin/C:d(u,v)/spl les/1}, v/spl isin/V, are nonempty and no two of them are the same set. It is natural to consider classes of codes that retain the identification property under various conditions, e.g., when the sets I(v) are possibly slightly corrupted. We consider two such classes of robust codes. We also consider dynamic identifying codes, i.e., walks in G whose vertices form an identifying code in G.     

Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)

The general problem of estimating the a posteriori probabilities of the states and transitions of a Markov source observed through a discrete memoryless channel is considered. The decoding of linear block and convolutional codes to minimize symbol error probability is shown to be a special case of this problem. An optimal decoding algorithm is derived.     

线性等距码与极大投射码

本文证明任意有限域上的一个线性等距码等价于一个极大投射码的重复码,从而给出了一般q元线性等距码的全部结构。     

Optimal codes (Corresp.)

Some known results on the nonexistence of linear optimal codes can be very easily proved using results on the weight distribution of such codes.     

The category of linear codes

Slepian (1960) introduced a structure theory for linear, binary codes and proved that every such code was uniquely the sum of indecomposable codes. He had hoped to produce a canonical form for the generator matrix of an indecomposable code so that he might read off the properties of the code from such a matrix, but such a program proved impossible. We here work over an arbitrary field and define a restricted class of indecomposable codes-which we call critical. For these codes there is a quasicanonical form for the generator matrix. Every indecomposable code has a generator matrix that is obtained from the generator matrix of a critical, indecomposable code by augmentation. As an application of the this quasicanonical form we illuminate the perfect linear codes, giving, for example, a “canonical” form for the generator matrix of the ternary Golay (1949) code     

Using linear programming to Decode Binary linear codes

A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric channel. The decoding algorithm is based on a linear programming (LP) relaxation that is defined by a factor graph or parity-check representation of the code. The resulting "LP decoder" generalizes our previous work on turbo-like codes. A precise combinatorial characterization of when the LP decoder succeeds is provided, based on pseudocodewords associated with the factor graph. Our definition of a pseudocodeword unifies other such notions known for iterative algorithms, including "stopping sets," "irreducible closed walks," "trellis cycles," "deviation sets," and "graph covers." The fractional distance d/sub frac/ of a code is introduced, which is a lower bound on the classical distance. It is shown that the efficient LP decoder will correct up to /spl lceil/d/sub frac//2/spl rceil/-1 errors and that there are codes with d/sub frac/=/spl Omega/(n/sup 1-/spl epsi//). An efficient algorithm to compute the fractional distance is presented. Experimental evidence shows a similar performance on low-density parity-check (LDPC) codes between LP decoding and the min-sum and sum-product algorithms. Methods for tightening the LP relaxation to improve performance are also provided.     

Stacking techniques for linear codes

A procedure for subspace stacking is proposed, and it is proved that the technique is equally successful for both linear codes and anticodes. It is demonstrated that families of errorcorrecting codes may be constructed using the proposed technique for stacking linear codes. Examples of such codes are given with rates better than the best known codes of identical Hamming distance and the same number of information digits.     

Optimal quaternary linear rate-1/2 codes of length /spl les/18

We classify all optimal linear [n,n/2,d] codes over F/sub 4/ up to length 18. In particular, we show that there is a unique optimal [12,6,6] code and three optimal [16,8,7] codes, up to equivalence.     

Generalized threshold decoding of linear codes

It is proved that every linear code of dimensionkcan be decoded by a threshold decoding circuit that is guaranteed to correcteerrors ife leq (d - 1)/2wheredis the minimum distance of the code. Moreover it is demonstrated that the number of levels of threshold logic is less than or equal tokby giving an algorithm for generating the decoding logic employingklevels.     

Binary linear quasi-perfect codes are normal

Whether quasi-perfect codes are normal is addressed. Let C be a code of length n, dimension k, covering radius R, and minimal distance d. It is proved that C is normal if d⩾2R-1. Hence all quasi-perfect codes are normal. Consequently, any [n,k ]R binary linear code with minimal distance d⩾2R-1 is normal     

Partial-optimal piecewise decoding of linear codes

LetAandBbe matrices over a finite fieldGF(q), with same column size n, having linearly independent rows. The problem is to find an optimal estimate of the "information"uB^{T}from the partial "syndrome"vA^{T}, with the conditionuA^{T} = 0, for a transmissionu rightarrow vofn-tuples on aq-ary totally symmetric memoryless channel. The best estimate has the formvB^{T}-f(vA^{T}), wheref(x)is the value ofymaximizing a so-called decision functionDelta (x,y). Explicit expressions are obtained forDelta; they allow computation of the critical probabilities of the channel. The theory is applied to multidimensional orthogonal check set decoding.     

Computerised search for linear binary codes

A computerised search procedure is described for finding new binary codes The method involves the extension of a given known code by annexing a number of parity-check digits to it in such a way that the minimum Hamming distance of the given code is improved. A number of codes found by this procedure have better rates than the best known codes of identical Hamming distance and the same number of information digits; a table of these codes is presented.     

Generalized Hamming weights of linear codes

The generalized Hamming weight, d_r(C), of a binary linear code C is the size of the smallest support of any r-dimensional subcode of C. The parameter d_r(C) determines the code's performance on the wire-tap channel of Type II. Bounds on d_r(C), and in some cases exact expressions, are derived. In particular, a generalized Griesmer bound for d_r(C) is presented and examples are given of codes meeting this bound with equality     

On binary linear codes supporting t-designs

In this paper, we present classification results on self-orthogonal binary codes supporting designs, Therefore, we use special linear forms on the intersection numbers. In particular, one shows that a binary self-orthogonal code of distance d⩽18 whose set of minimal-weight codewords supports a 5-design has to be self-dual. We also prove that the codewords of any fixed weight in a [24m+22, 12m+11, 4m+6] Type I code support a 3-design     

Error-correction capability of binary linear codes

The monotone structure of correctable and uncorrectable errors given by the complete decoding for a binary linear code is investigated. New bounds on the error-correction capability of linear codes beyond half the minimum distance are presented, both for the best codes and for arbitrary codes under some restrictions on their parameters. It is proved that some known codes of low rate are as good as the best codes in an asymptotic sense.     

Rectangular information lossless linear dispersion codes

This paper extends square Μ×Μ linear dispersion codes (LDC) proposed by Hassibi and Hochwald to Τ x Μ non-square linear dispersion codes of the same rate Μ, termed uniform LDC, or U-LDC. This paper establishes a unitary property of arbitrary rectangular U-LDC encoding matrices and determines their connection to the traceless minimal nonorthogonality criterion for space-time codes. The U-LDC are then applied to rapid fading channels by constructing traceorthonormal versions, or TON-U-LDC for 2L and 4L input symbols, where L is a positive integer. Compared to a variety of state-of-the-art codes, the proposed codes are found to perform well in both block and rapid fading channels. In rapid fading, the symbol-wise time diversity order of a Τ x Μ, TON-U-LDC for 2L input symbols is shown to be min(Τ,2Μ).