Minimal Codewords in Linear Codes

2000 Mathematics Subject Classification: 94B05, 94B15.

Construction of Optimal Linear Codes by Geometric Puncturing

Dedicated to the memory of S.M. Dodunekov (1945–2012)Abstract. Geometric puncturing is a method to construct new codes. ACM Computing Classification System (1998): E.4.

The Treewidth of MDS and Reed-Muller Codes

The constraint complexity of a graphical realization of a linear code is the maximum dimension of the local constraint codes in the realization. The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical realizations. This notion provides a useful parameterization of the maximum-likelihood decoding complexity for linear codes. In this paper, we show the surprising fact that for maximum distance separable codes and Reed-Muller codes, treewidth equals trelliswidth, which, for a code, is defined to be the least constraint complexity (or branch complexity) of any of its trellis realizations. From this, we obtain exact expressions for the treewidth of these codes, which constitute the only known explicit expressions for the treewidth of algebraic codes.

On the treewidth of MDS and Reed-Muller codes

The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical realizations. This notion provides a useful parametrization of the maximum-likelihood decoding complexity for linear codes. In this paper, we compute exact expressions for the treewidth of maximum distance separable codes, and first- and second-order Reed-Muller codes. These results constitute the only known explicit expressions for the treewidth of algebraic codes.

On t-designs and bounds relating query complexity to error resilience in locally correctable codes

An n-length block code C is said to be r-query locally correctable, if for any codeword x ∈ C, one can probabilistically recover any one of the n coordinates of the codeword x by querying at most r coordinates of a possibly corrupted version of x. It is known that linear codes whose duals contain 2-designs are locally correctable. In this article, we consider linear codes whose duals contain t-designs for larger t. It is shown here that for such codes, for a given number of queries r, under linear decoding, one can, in general, handle a larger number of corrupted bits. We exhibit to our knowledge, for the first time, a finite length code, whose dual contains 4-designs, which can tolerate a fraction of up to 0.567/r corrupted symbols as against a maximum of 0.5/r in prior constructions. We also present an upper bound that shows that 0.567 is the best possible for this code length and query complexity over this symbol alphabet thereby establishing optimality of this code in this respect. A second result in the article is a finite-length bound which relates the number of queries r and the fraction of errors that can be tolerated, for a locally correctable code that employs a randomized algorithm in which each instance of the algorithm involves t-error correction.

Optimum linear coding for additive noise systems using information feedback

The feedback coding problem for Gaussian systems in which the noise is neither white nor statistically independent between channels is formulated in terms of arbitrary linear codes at the transmitter and at the receiver. This new formulation is used to determine a number of feedback communication systems. In particular, the optimum linear code that satisfies an average power constraint on the transmitted signals is derived for a system with noiseless feedback and forward noise of arbitrary covariance. The noisy feedback problem is considered and signal sets for the forward and feedback channels are obtained with an average power constraint on each. The general formulation and results are valid for non-Gaussian systems in which the second order statistics are known, the results being applicable to the determination of error bounds via the Chebychev inequality.

CYCLIC CODES THROUGH B[X], B[X; 1/kp Z(0)] and B[X; 1/p(k) Z(0)]: A COMPARISON

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Geometrically uniform hyperbolic codes

In this paper we generalize the concept of geometrically uniform codes, formerly employed in Euclidean spaces, to hyperbolic spaces. We also show a characterization of generalized coset codes through the concept of G-linear codes.

Special subsets and optimum codes based on lattices and cosets

This paper introduces the concept of special subsets when applied to generator matrices based on lattices and cosets as presented by Calder-bank and Sloane. By using the special subsets we propose a non exhaustive code search for optimum codes. Although non exhaustive, the search always results in optimum codes for given (k1, V, Λ/Λ′). Tables with binary and ternary optimum codes to partitions of lattices with 8, 9 e 16 cosets, were obtained.

Lattice constellations and codes from quadratic number fields

We propose new classes of linear codes over integer rings of quadratic extensions of Q, the field of rational numbers. The codes are considered with respect to a Mannheim metric, which is a Manhattan metric modulo a two-dimensional (2-D) grid. In particular, codes over Gaussian integers and Eisenstein-Jacobi integers are extensively studied. Decoding algorithms are proposed for these codes when up to two coordinates of a transmitted code vector are affected by errors of arbitrary Mannheim weight. Moreover, we show that the proposed codes are maximum-distance separable (MDS), with respect to the Hamming distance. The practical interest in such Mannheim-metric codes is their use in coded modulation schemes based on quadrature amplitude modulation (QAM)-type constellations, for which neither the Hamming nor the Lee metric is appropriate.

Spectrum Distribution in Cognitive Radio: Error Correcting Codes Perspective

Cognitive radio is a growing zone in wireless communication which offers an opening in complete utilization of incompetently used frequency spectrum: deprived of crafting interference for the primary (authorized) user, the secondary user is indorsed to use the frequency band. Though, scheming a model with the least interference produced by the secondary user for primary user is a perplexing job. In this study we proposed a transmission model based on error correcting codes dealing with a countable number of pairs of primary and secondary users. However, we obtain an effective utilization of spectrum by the transmission of the pairs of primary and secondary users' data through the linear codes with different given lengths. Due to the techniques of error correcting codes we developed a number of schemes regarding an appropriate bandwidth distribution in cognitive radio.

Aplicações de ágebra linear aos códigos corretos de erros e ao ensino médio

Pós-graduação em Matemática em Rede Nacional - IBILCE

Statistical mechanics of broadcast channels using low-density parity-check codes

We investigate the use of Gallager's low-density parity-check (LDPC) codes in a degraded broadcast channel, one of the fundamental models in network information theory. Combining linear codes is a standard technique in practical network communication schemes and is known to provide better performance than simple time sharing methods when algebraic codes are used. The statistical physics based analysis shows that the practical performance of the suggested method, achieved by employing the belief propagation algorithm, is superior to that of LDPC based time sharing codes while the best performance, when received transmissions are optimally decoded, is bounded by the time sharing limit.

Algebraic geometric codes over rings

The techniques of algebraic geometry have been widely and successfully applied to the study of linear codes over finite fields since the early 1980's. Recently, there has been an increased interest in the study of linear codes over finite rings. In this thesis, we combine these two approaches to coding theory by introducing and studying algebraic geometric codes over rings.

Dembowski-Ostrom型完全非线性函数构造的线性码权分布

Dembowski-Ostrom型完全非线性函数是目前最主要的完全非线性函数类,已发现的完全非线性函数中只有一种不属于Dembowski-Ostrom型.为此,该文首先给出Dembowski-Ostrom型完全非线性函数的定义,将已有的线性码构造推广到这一类型函数上.进而给出此类函数构造的线性码的码字与有限域上非退化二次型之间的关系,并得到相应二次型的原像分布的一些性质.通过有限域上的二次型以及指数和理论,用统一的方法完全确定了基于所有Dembowski-Ostrom型完全非线性函数构造的两类线性码的权分布.