Optimal linear identifying codes

Identifying codes can be used to locate malfunctioning processors. We say that a code C of length n is a linear (1,/spl les/l)-identifying code if it is a subspace of F/sub 2//sup n/ and for all X,Y/spl sube/F/sub 2//sup n/ such that |X|, |Y|/spl les/l and X/spl ne/Y, we have /spl cup//sub x/spl isin/X/(B(x)/spl cap/C)/spl ne//spl cup/y/spl isin/Y(B(y)/spl cap/C). Strongly (1,/spl les/l)-identifying codes are a variant of identifying codes. We determine the cardinalities of optimal linear (1,/spl les/l)-identifying and strongly (1,/spl les/l)-identifying codes in Hamming spaces of any dimension for locating any at most l malfunctioning processors.     

New constant weight codes from linear permutation groups

New constant weight codes are found by considering certain linear permutation groups. A code is obtained as a collection of orbits of words under such a group. This leads to a difficult optimization problem, where a stochastic search heuristic, tabu search, is used to find good solutions in a feasible amount of time. Nearly 40 new codes of length at most 28 are presented     

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     

基于分块矩阵变换的线性分组码盲识别

为了解决传统矩阵分析方法存在的误码扩散问题,提出了一种基于分块矩阵变换的线性分组码盲识别方法.首先,将截获序列按照估计码长构造出分析矩阵,将分析矩阵分块后分别进行矩阵下三角变换;然后,以各列列重为度量,根据相关列重量的统计分布特性设置相关列阈值,并统计出符合阈值的相关列的个数,当相关列的个数最大时即为真实码长的情况.该方法还可以识别码字同步点,识别方法简单.理论分析及仿真结果表明,该识别方法的容错性能较好,在误码为5%的条件下,对(15,7)线性分组码的正确识别率依然能达到80%.     

New binary linear codes from algebraic curves

Many new binary linear codes (compared with Brouwer's (2000) table) are found from a construction based on algebraic curves over finite fields     

Optimal space-time constellations from groups

We consider the design of space-time constellations based on group codes for fading channels with multiple transmit and receive antennas. These codes can be viewed as multiantenna extensions of phase-shift keying (PSK), in the sense that all codewords have equal energy, all are rotations of a fixed codeword, and there is a simple differential transmission rule that allows data to be sent without channel estimates at the transmitter or receiver. For coherent detection, we show that all optimal full-rank space-time group codes are unitary (each code matrix has equal-energy, orthogonal rows). This leads to a simpler code design criterion and suggests that unitary codes may play an important role in coherent as well as noncoherent communication. For any number of transmit antennas t, we then use the design criterion to characterize all full-rank unitary space-time group codes of minimum block length (also t) which have 2/sup p/ codewords. These results allow us to characterize all optimal 2/sup p/-ary unitary group codes with square code matrices. This restricted class of block codes matches the class proposed for differential modulation by Hughes (see IEEE Trans. Inform. Theory, vol.46, p.2567-78, Nov. 2000), and by Hochwald and Sweldens (see IEEE Trans. Commun., vol.48, p.2041-2052, Dec. 2000).     

Approaching Shannon performance by iterative decoding of linear codes with low-density generator matrix

We propose the use of linear codes with low density generator matrix to achieve a performance similar to that of turbo and standard low-density parity check codes. The use of iterative decoding techniques - message passing -over the corresponding graph achieves a performance close to the Shannon theoretical limit. As an advantage with respect to turbo and standard low-density parity check codes, the complexity of the decoding and encoding procedures is very low.     

线性等距码与极大投射码

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

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.     

Mixed-Q linear space-time codes

A new modulation method for linear space-time codes is proposed based on using constellations of different sizes for different symbols. It is shown that the proposed method significantly reduces the complexity of the sphere decoding algorithm. The complexity reduction is more pronounced in high-rate codes, where each code matrix carries a large number of symbols. We also show that the choice of constellation size provides a tradeoff between performance and complexity. Using this, some guidelines for choosing constellation size are presented. As one introduces more constellation disparity in the code, the complexity is further reduced, while the performance loss grows. Typically, a complexity reduction of one to two orders of magnitude can be achieved at the expense of about 3 dB coding gain. We suggest a simple modification in our design to reduce this loss to about 2 dB.     

Constructing linear unequal error protection codes from algebraic curves

We show that the concept of "generalized algebraic geometry codes" which was introduced by Xing, Niederreiter, and Lam (see ibid., vol.45, p.2498-2501, Nov. 1999) gives a natural framework for constructing linear unequal error protection codes.     

Secret sharing schemes from three classes of linear codes

Secret sharing has been a subject of study for over 20 years, and has had a number of real-world applications. There are several approaches to the construction of secret sharing schemes. One of them is based on coding theory. In principle, every linear code can be used to construct secret sharing schemes. But determining the access structure is very hard as this requires the complete characterization of the minimal codewords of the underlying linear code, which is a difficult problem in general. In this paper, a sufficient condition for all nonzero codewords of a linear code to be minimal is derived from exponential sums. Some linear codes whose covering structure can be determined are constructed, and then used to construct secret sharing schemes with nice access structures.     

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.     

Linear codes from narrow ray class groups of algebraic curves

By employing the narrow ray class groups of algebraic curves and the Hurwitz genus formula, we construct a class of linear codes over prime fields with reasonable parameters. In particular, we obtain some new codes compared with Brouwer's table.     

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     

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.     

Rate-compatible low-density generator matrix codes

We propose a family of rate-compatible codes based on the concatenation of two linear codes with low-density generator matrix, which are a special class of LDPC codes with low encoding complexity. The proposed scheme is characterized by its simplicity of construction, and does not require optimization of the puncturing pattern.     

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.