Source-linked AI summary
The Dimension and Minimum Distance of Two Classes of Primitive BCH Codes
Cunsheng Ding, Cuiling Fan, Zhengchun Zhou
TL;DR
The dimensions and minimum distances of narrow-sense primitive BCH codes are not known in general, despite their importance as a code family. This paper determines parameters for two classes of design distances, using coset-leader results and code-specific arguments. It establishes parameter and weight-distribution results for primitive BCH codes in these classes, with some examples optimal or almost optimal.
Problem
The dimensions and minimum distances of narrow-sense primitive BCH codes remain unknown in general, and determining their Bose distance is also difficult.
Source: §I · p. 2, §II · p. 3Method
The paper determines the relevant coset leaders and derives code parameters and weight distributions through direct proofs or links to cyclic codes with known weight distributions.
Source: §II · p. 3, §V · p. 16Results
The paper establishes dimensions, minimum distances, and weight distributions for ˜C(q,m,δ2) and ˜C(q,m,δ3), and settles dimensions and minimum distances for C(q,m,δ2) and C(q,m,δ3) when q is an odd prime.
Source: §V · p. 16Takeaways & Limitations
Examples are often optimal or almost optimal, and the codes’ parameters and minimum-weight words may be used to obtain secret-sharing schemes and t-designs.
Source: §V · pp. 16–17
Abstract
from arXiv · showhide
Reed-Solomon codes, a type of BCH codes, are widely employed in communication systems, storage devices and consumer electronics. This fact demonstrates the importance of BCH codes -- a family of cyclic codes -- in practice. In theory, BCH codes are among the best cyclic codes in terms of their error-correcting capability. A subclass of BCH codes are the narrow-sense primitive BCH codes. However, the dimension and minimum distance of these codes are not known in general. The objective of this paper is to determine the dimension and minimum distances of two classes of narrow-sense primitive BCH codes with design distances $\delta=(q-1)q^{m-1}-1-q^{\lfloor (m-1)/2\rfloor}$ and $\delta=(q-1)q^{m-1}-1-q^{\lfloor (m+1)/2\rfloor}$. The weight distributions of some of these BCH codes are also reported. As will be seen, the two classes of BCH codes are sometimes optimal and sometimes among the best linear codes known.
I. INTRODUCTION
The introduction frames narrow-sense primitive BCH codes as an important but incompletely understood family of cyclic codes. This paper targets two design-distance classes, determining their dimensions and minimum distances and reporting some weight distributions.
I. INTRODUCTION
- Narrow-sense primitive BCH codes are cyclic codes, but their dimensions and minimum distances remain unknown in general.The paper notes that dimension is known for small design distances, while minimum distance is known only in a few cases.Source: §I · pp. 1–2
- The introduction identifies determining primitive BCH minimum distances as a well-known hard problem, with little progress reported over the preceding sixteen years.The cited overview of known BCH results points readers to,,,.Source: §I · p. 2
- The paper targets C(q,m,δi) and ˜C(q,m,δi) for δ2=(q−1)q^(m−1)−1−q^⌊(m−1)/2⌋ and δ3=(q−1)q^(m−1)−1−q^⌊(m+1)/2⌋.It also reports weight distributions for some of these BCH codes.Source: §I · p. 2
- The paper assesses code optimality against Grassl’s database of best known linear codes and sometimes against tables of best cyclic codes.It calls parameters optimal when they meet a bound, and almost optimal when either [n,k+1,d] or [n,k,d+1] meets a bound.Source: §I · p. 2
II. SOME AUXILIARY RESULTS
This section motivates determining the Bose distance because it may be closer to minimum distance than the design distance. It proposes choosing design distances that are coset leaders, for which the Bose distance equals the design distance.
II. SOME AUXILIARY RESULTS
- The section introduces q-cyclotomic cosets and their sizes and coset leaders as auxiliary concepts for the BCH-code analysis.The size of a coset is the smallest positive ℓi for which q^ℓi i≡i (mod n).Source: §II · p. 2
- In many cases, the gap between minimum distance and design distance is large, while the Bose distance may be close to minimum distance.Charpin’s conjecture states that narrow-sense primitive BCH codes satisfy d≤dB+4.Source: §II · p. 3
- A design distance that is a coset leader has Bose distance equal to that design distance.The paper says choosing such design distances is its strategy for the following code classes.Source: §II · p. 3
III. THE PARAMETERS OF THE BCH CODES C(q,m,δ2) AND ˜C(q,m,δ2), WHERE
This section studies BCH codes with design distance δ₂, deriving dimension and minimum-distance results and reporting weight-distribution findings. It also presents parameter examples for both code families and the dual of ˜C(2,m,δ₂).
III. THE PARAMETERS OF THE BCH CODES C(q,m,δ2) AND ˜C(q,m,δ2), WHERE
- The second-largest coset leader is δ2 = (q−1)q^(m−1) −1−q^⌊(m−1)/2⌋, with coset size m for odd m and m/2 for even m.The proof establishes the coset-leader result separately for odd and even m.Source: §III · p. 3, Subcase I.2, i.e., q > 2 · p. 4, Subcase II.2, i.e., q > 2 · p. 5
- For ˜C(q,m,δ2), Theorem 4 gives minimum distance at least δ2 + 1 and dimension 2m when m is odd or 3m/2 when m is even.Source: Subcase II.2, i.e., q > 2 · p. 5
Case 1: q is an odd prime and m ≥3 is odd
- For odd m, code ˜Cδ2 has three nonzero weights; wt(c(0,b))=(q−1)q^(m−1) when a=0 and b≠0, and w3=(q−1)q^(m−1)+q^((m−1)/2).Source: Table III · p. 5, Case 1.3: Let a = 0 and b̸ = 0 · p. 8
Case 2: q is an odd prime and m ≥4 is even
- For even m and odd prime q, ˜Cδ2 also has three nonzero weights, with the distribution reported in Table IV.The proof derives the weight counts from the first three Pless power moments.Source: Table IV · p. 6, Case 2.4: Let a = 0 and b̸ = 0 · p. 10
- Theorem 4’s proof characterizes all minimum-weight codewords of ˜Cδ2, a characterization that may be used to derive t-designs.The paper notes that extending the conclusions to odd prime powers would first require generalizing results in.Source: Case 2.4: Let a = 0 and b̸ = 0 · p. 10
- Examples of ˜C(q,m,δ2) are either optimal or have the same parameters as the best linear codes in the Database.The examples are summarized in Table V.Source: Table V · p. 10, Case 2.4: Let a = 0 and b̸ = 0 · p. 11
- The dual of ˜C(2,m,δ2) has minimum distance 5 for odd m ≥ 5 and 3 for even m ≥ 4.Theorem 6 is stated as proved in,.Source: Case 2.4: Let a = 0 and b̸ = 0 · p. 11
- For C(q,m,δ2), d ≥ δ2, and d = δ2 when q is prime; the theorem also specifies the code’s parameters [n, k, d].The supplied parameter formula is incomplete in the extracted text, so no dimension formula is stated.Source: Case 2.4: Let a = 0 and b̸ = 0 · p. 11
- The examples of C(q,m,δ2) are sometimes optimal or match the best-known linear-code parameters; (2,6) gives [63,10,27] and (3,3) gives, both stated best possible.The examples are summarized in Table VI.Source: Case 2.4: Let a = 0 and b̸ = 0 · p. 11, Table VI · p. 11
IV. THE PARAMETERS OF THE BCH CODES C(q,m,δ3) AND ˜C(q,m,δ3), WHERE
For m≥4, δ3 is the third-largest q-cyclotomic coset leader, and the section establishes parameters and distance results for the corresponding primitive BCH codes. It also reports weight distributions and examples, while the q>2, m=3 minimum distances remain conjectural.
IV. THE PARAMETERS OF THE BCH CODES C(q,m,δ3) AND ˜C(q,m,δ3), WHERE
- For m≥4, δ3 is the third-largest q-cyclotomic coset leader and its q-cyclotomic coset has size m.The even-m conclusion is stated with omitted details.Source: §IV · pp. 11, 13
- For m≥4, ˜C(q,m,δ3) has ˜d≥δ3+1, with equality for q=2 and for odd-prime q when m≥4 is even or m≥5 is odd.The binary weight distributions are reported separately for odd and even m; odd-prime distributions are also reported for both parities.Source: §IV · p. 13
- Theorems 9 and 11 establish the dimensions of ˜C(q,m,δ3) and C(q,m,δ3) for m≥4.The proofs derive the dimension conclusions from the coset-leader lemmas.Source: §IV · pp. 13, 15
- For binary codes with m≥5 odd or m≥6 even, the dual minimum distances are 7 and 5 for ˜C, and 8 and 6 for C, respectively.Source: §IV · pp. 15–16
- Examples of both codes are sometimes optimal and sometimes match the parameters of the best linear codes known.The section lists examples for ˜C in Table XI and for C in Table XII.Source: §IV · pp. 15–16, Table XI · p. 15, Table XII · p. 16
- For m≥4, the parameters of C(q,m,δ3) are established, and its minimum distance is exactly d=δ3.The proof of the exact distance is described as refining earlier proofs; its lengthy details are omitted.Source: §IV · pp. 15–16
- For q>2 and m=3, the two codes have stated lower bounds on minimum distance, but equality with those bounds is conjectured rather than established.The conjectured distances are q^3−q^2−q−1 for ˜C and q^3−q^2−q−2 for C.Source: §IV · p. 16
V. SUMMARY AND CONCLUDING REMARKS
The concluding remarks gather the paper’s results on coset leaders, BCH-code parameters, weight distributions, and minimum-weight codewords. They also describe applications and relationships to other code classes.
V. SUMMARY AND CONCLUDING REMARKS
- The paper determines the second and third largest q-cyclotomic coset leaders and establishes dimensions, minimum distances, and some weight distributions for the associated primitive BCH codes.For the narrow-sense codes, dimensions and minimum distances are settled for odd-prime q.Source: §V · p. 16
- The paper characterizes all minimum-weight codewords of ˜C(q,m,δ2), a result that may be used to derive t-designs.The authors note that characterizing all minimum-weight codewords is generally very difficult.Source: §V · p. 16
- The paper proves equivalences between ˜C(q,m,δ3) and subclasses of nonbinary Kasami codes and cyclic codes treated in.Source: §V · p. 16
- For m≥5, ˜C(q,m,δ2) and ˜C(q,m,δ3) satisfy the paper’s inequality in (12) and can be used to obtain secret-sharing schemes with interesting access structures.The cited framework is documented in,,,.Source: §V · p. 17