Minimal vectors in linear codes
- 1 September 1998
- journal article
- letter
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 44 (5), 2010-2017
- https://doi.org/10.1109/18.705584
Abstract
Minimal vectors in linear codes arise in numerous applications, particularly, in constructing decoding algorithms and studying linear secret sharing schemes. However, properties and structure of minimal vectors have been largely unknown. We prove basic properties of minimal vectors in general linear codes. Then we characterize minimal vectors of a given weight and compute their number in several classes of codes, including the Hamming codes and second-order Reed-Muller codes. Further, we extend the concept of minimal vectors to codes over rings and compute them for several examples. Turning to applications, we introduce a general gradient-like decoding algorithm of which minimal-vectors decoding is an example. The complexity of minimal-vectors decoding for long codes is determined by the size of the set of minimal vectors. Therefore, we compute this size for long randomly chosen codes. Another example of algorithms in this class is given by zero-neighbors decoding. We discuss relations between the two decoding methods. In particular, we show that for even codes the set of zero neighbors is strictly optimal in this class of algorithms. This also implies that general asymptotic improvements of the zero-neighbors algorithm in the frame of gradient-like approach are impossible. We also discuss a link to secret-sharing schemes.Keywords
This publication has 16 references indexed in Scilit:
- Voronoi regions for binary linear block codesIEEE Transactions on Information Theory, 1996
- On near-MDS codesJournal of Geometry, 1995
- Universally ideal secret-sharing schemesIEEE Transactions on Information Theory, 1994
- The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codesIEEE Transactions on Information Theory, 1994
- Kerdock code in a cyclic formDiscrete Mathematics and Applications, 1991
- Linear intersecting codesDiscrete Mathematics, 1985
- A new approach to the general minimum distance decoding problem: The zero-neighbors algorithmIEEE Transactions on Information Theory, 1985
- On the original Steiner SystemsDiscrete Mathematics, 1984
- Decoding linear block codes for minimizing word error rate (Corresp.)IEEE Transactions on Information Theory, 1979
- Combinatorische Aufgaben.Journal für die reine und angewandte Mathematik (Crelles Journal), 1853