Binary Goppa codes minimum distances extended for more cases
On True Minimum Distances of Goppa Codes
Information Theory
Summary
Binary Goppa codes are used to detect and correct errors in digital communication and cryptography. While their minimum error-correcting capability was known to be at least certain values, the exact minimum distances were only known for very large cases before. The authors provide clear conditions to know exactly when these codes reach certain minimum distances and construct many new examples across different parameters. They also extend these results to a broader class of Goppa codes over other alphabets.
What this means in practice
- •For cryptography engineers: Design error-correcting codes with guaranteed minimum distances for stronger cryptographic schemes using explicit polynomial constructions.
- •For communication system developers: Use new families of binary Goppa codes with known minimum distances to improve data transmission reliability in noisy environments.
Authors
Yaqi Chen, Hao Chen, Chao Liu, Huimin Lao
Abstract
Binary Goppa codes are important in coding theory and cryptography. It is well-known that the minimum distance of a binary Goppa code defined by a squarefree polynomial of degree $r$ is at least $2r+1$. Though from the classical results of C. J. Moreno, O. Moreno, F. Levy-dit-Vehel and S. Litsyn that the true minimum distances of binary Goppa codes are $2r+1$, when the extension field degree $m$ is larger than $(r-1)^{4r}$. There have only very few families of binary Goppa codes with determined true minimum distances. In this paper, we give necessary and sufficient conditions for binary Goppa codes such that their minimum distances are $2r+1$ and $2r+2$. Infinitely many infinite families of binary Goppa codes with minimum distance $2r+1$ are given. In particular, we construct such codes for every Goppa degree $r$ in the range $2^{h-1}<r<2^h$ over $\mathbb F_{2^{2h}}$. For every $2\le r\le\lfloor2^m/3\rfloor$, we also obtain at least $2^m-3r+1$ distinct monic squarefree Goppa polynomials of degree $r$ over $\mathbb F_{2^m}$, such that their related binary Goppa codes have minimum distance $2r+1$. We extend a criterion for $q$-ary Goppa codes to split auxiliary polynomials and obtain some infinite families of $q$-ary Goppa codes attaining their designed distances $r+1$. We also construct infinite families of binary Goppa codes with minimum distance exactly $2r+2$.