The Newton radius of codes

DOI10.1109/18.641548MaRDI QIDQ4392383zbMATH OpenOpenAlexFDO

Authors Tor Helleseth, Torleiv Kløve

Publication date 14 January 1999

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/18.641548

zbMATH Keywords

covering radiuserror correctionNewton radiusReed-Muller codessimplex codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Cyclic codes (94B15) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Review text

Let \(C\) be a binary linear \([n,k,d]\) code. For a vector \(x \in \text{GF} (2)^n\), a false neighbor is a \(0 \neq c\in C\) such that \(d_H(x,c)\leq d_H(x,0)=w_H(x)\), where \(d_H(x,y)\) denotes the Hamming distance of the vectors \(x,y \in \text{GF} (2)^n\). An error is called uniquely correctable if it has no false neighbors. It is well known that if \(w_H(e) \leq (d-1)/2\), then the error \(e\) is uniquely correctable. On the other hand the inequality \(w_H(e)> (d-1)/2\) is only a necessary condition for an error \(e\) to be uncorrectable. In this paper there are studied the following natural questions: What are the errors which are uniquely correctable? How many are these of a given weight \(t\)? What is the largest weight, \(\nu (C)\), of a uniquely correctable error? The number \(\nu (C)\) is called the Newton radius of \(C\). Let \(r(C)\) denote the covering radius of \(C\), i.e. the maximal distance of a vector from the code \(C\). The first result of the paper is that \(0 \leq r(C)- \nu (C) \leq k\). Both bounds are sharp; \(r(C)=\nu (C)\) holds for the perfect codes, while \(r(C)=\nu (C)+k\) holds for some equidistant codes. The second assertion is the combination of Theorems 5 and 6 of the present paper. The difference \(r(C)-\nu (C)\) is studied for the first-order Reed-Muller codes extensively. Let \(N_t(C)\) denotes the cardinality of the set of uncorrectable errors of weight \(t\). If the weight distribution of \(C\) is \(A_0,A_1, \dots A_n\), then the authors prove \[ N_t(C) \leq \sum_{i=d}^{2t} A_i \sum_{a=\lceil i/2 \rceil}^{\min \{i,t \} } {i \choose a} {n-i \choose t-a}. \] The function \(N_t(C)\) is studied in detail for equidistributed and for first-order Reed-Muller codes.

Recommendations

• On the Newton and covering radii of linear codes
• A note on the Newton radius
• Relations between the covering and Newton radii of binary codes
• On the computation of coset leaders with high Hamming weight.

Cited in

(8)

• On the computation of coset leaders with high Hamming weight.
• Centered error-correcting codes
• On planes through points off the twisted cubic in \(\mathrm{PG}(3,q)\) and multiple covering codes
• A note on the Newton radius
• Relations between the covering and Newton radii of binary codes
• On those Boolean functions that are coset leaders of first order Reed-Muller codes
• Coset leaders of the first order Reed-Muller codes in the classes of Niho functions and threshold functions
• Coset leaders of the first-order Reed-Muller codes in four new classes of Boolean functions

This page was built for publication: The Newton radius of codes

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