Computing coset leaders and leader codewords of binary codes

DOI10.1142/S0219498815501285MaRDI QIDQ5255749zbMATH OpenFDO

Authors Mijail Borges-Quintana, Miguel Angel Borges-Trenard, Irene Márquez-Corbella, E. Martínez-Moro

Publication date 19 June 2015

Published in Journal of Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.5568

zbMATH Keywords

binary codescoset leadersGröbner representationtest set

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Linear codes (general theory) (94B05)

Abstract: In this paper we use the Gr"obner representation of a binary linear code $mathcalC$ to give efficient algorithms for computing the whole set of coset leaders, denoted by $mathrmCL(mathcalC)$ and the set of leader codewords, denoted by $mathrmL(mathcalC)$. The first algorithm could be adapted to provide not only the Newton and the covering radius of $mathcalC$ but also to determine the coset leader weight distribution. Moreover, providing the set of leader codewords we have a test-set for decoding by a gradient-like decoding algorithm. Another contribution of this article is the relation stablished between zero neighbours and leader codewords.

Recommendations

• On the computation of coset leaders with high Hamming weight.
• About the nth-root codes: a Gröbner basis approach to the weight computation
• Gröbner bases and combinatorics for binary codes
• On the weak order ideal associated to linear codes
• A decoding algorithm for binary linear codes using Groebner bases

Cites work

• Algebraic structure of the minimal support codewords set of some linear codes
• Coset analysis of reed muller codes via translates of finite vector spaces
• Error-Correction Capability of Binary Linear Codes
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• On a Gröbner bases structure associated to linear codes
• On Correctable Errors of Binary Linear Codes
• On the computation of coset leaders with high Hamming weight.
• On the inherent intractability of certain coding problems (Corresp.)
• The hardness of decoding linear codes with preprocessing

Cited in

(9)

• On the computation of coset leaders with high Hamming weight.
• On the weak order ideal associated to linear codes
• On coset leader graphs of structured linear codes
• Characteristic vector and weight distribution of a linear code
• Efficient representation of binary nonlinear codes: constructions and minimum distance computation
• On Coset Leader Graphs of LDPC Codes
• The coset leader and list weight enumerator
• Computing an invariant of a linear code
• On those Boolean functions that are coset leaders of first order Reed-Muller codes

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Computing coset leaders and leader codewords of binary codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5255749)