New Constructions of Binary Cyclic Codes with Both Relatively Large Minimum Distance and Dual Distance

Titel

Nieuwe constructies van binaire cyclische codes met zowel een relatief grote minimale afstand als een grote duale afstand.

1. Probleemstelling

Binaire cyclische codes zijn van groot theoretisch belang en hebben brede toepassingen. Een fundamenteel probleem in de coderingstheorie is het construeren van een oneindige familie van cyclische codes met lengte $n = 2^m - 1$ en dimensie $k \approx n/2$, die zowel een grote minimale afstand ($d$) als een grote duale minimale afstand ($d^\perp$) bezitten.

Er bestaat een bekende trade-off: naarmate de minimale afstand $d$ van een code toeneemt, neigt de duale afstand $d^\perp$ vaak af te nemen. Bestaande constructies, zoals de punctured Reed-Muller codes, bereiken een bepaalde ondergrens voor het product $d \cdot d^\perp$, maar vaak ten koste van de andere parameter. Het doel van dit onderzoek is het vinden van nieuwe constructies die deze trade-off doorbreken en codes produceren waarbij het product $d \cdot d^\perp$ asymptotisch dicht bij $n$ of zelfs $2n$ komt, wat aanzienlijk beter is dan eerdere resultaten.

2. Methodologie

De auteurs gebruiken algebraïsche methoden gebaseerd op de theorie van cyclische codes over het eindige lichaam $\mathbb{F}_2$. De kern van de methode ligt in het zorgvuldig ontwerpen van de definiërende verzameling (defining set) $Z$ van de code.

• Cyclotomische Cosets: De auteurs werken met 2-cyclotomische cosets modulo $n$. Een code wordt gedefinieerd door de wortels van zijn generatorpolynoom, die corresponderen met elementen in een specifieke verzameling $Z \subseteq \mathbb{Z}_n$.
• Symmetrie en Rotatie: Een cruciale techniek is het gebruik van rotatiesymmetrie. Een verzameling $Z$ is een geldige definiërende verzameling voor een cyclische code dan en slechts dan als deze gesloten is onder de actie van de vermenigvuldiging met 2 modulo $n$. De auteurs gebruiken een afbeelding $\pi$ die gehele getallen naar binaire vectoren mapt en analyseren de rotatie $\rho$ van deze vectoren.
• BCH-ondergrens: De minimale afstand $d$ en de duale afstand $d^\perp$ worden afgeleid met behulp van de bekende BCH-ondergrens (BCH bound). Als de definiërende verzameling een opeenvolgende reeks van elementen bevat, garandeert dit een minimale afstand.
• Drie specifieke gevallen: De constructies worden onderverdeeld op basis van de eigenschappen van $m$ (waarbij $n=2^m-1$):
  1. $m$ is even.
  2. $m$ is het product van twee verschillende priemgetallen ($m = p_1 p_2$).
  3. $m$ is oneven.

3. Belangrijkste Bijdragen en Resultaten

De paper presenteert drie hoofdfamilies van nieuwe codes:

A. Geval: $m$ is even

• Constructie: De auteurs introduceren een nieuwe methode om de definiërende verzameling te construeren, geïnspireerd door rotatiesymmetrische Boolese functies. Ze definiëren verzamelingen gebaseerd op het gewicht van binaire vectoren en hun rotaties.
• Resultaat: Ze construeren twee families van codes met parameters $[2^m-1, 2^{m-1} \pm 1, d]$.
  • Minimale afstand: $d \ge 2^{m/2} - 1$.
  • Duale afstand: $d^\perp \ge 2^{m/2}$.
• Vergelijking: Deze waarden zijn significant beter dan eerdere resultaten (zoals die van Tang et al. [26]), waarbij zowel $d$ als $d^\perp$ groter zijn. Het product $d \cdot d^\perp$ benadert asymptotisch $n$.

B. Geval: $m = p_1 p_2$ (Product van twee verschillende priemgetallen)

• Constructie: Hier wordt gebruik gemaakt van de structuur van cyclotomische cosets wanneer de orde een product van priemgetallen is. De auteurs analyseren de grootte van deze cosets ($p_1$, $p_2$ of $p_1 p_2$) en selecteren specifieke coset-leiders om de definiërende verzameling op te bouwen.
• Resultaat: Er worden codes geconstrueerd met dimensie $k = 2^{m-1}$ en een minimale afstand die veel groter is dan de vierkantswortelgrens ($\sqrt{n}$) en zelfs groter dan $n / \log_2 n$.
  • De ondergrens voor $d$ wordt expliciet berekend en is aanzienlijk hoger dan die van de punctured Reed-Muller codes.
  • De duale afstand $d^\perp$ wordt ook bepaald en is van de orde $2^{\lfloor \log_2 m \rfloor + 1}$.
• Significantie: Dit is een van de eerste constructies die een zo hoge minimale afstand bereikt voor deze specifieke lengte en dimensie, terwijl de duale afstand behouden blijft.

C. Geval: $m$ is oneven

• Constructie 1: Gebaseerd op de eigenschap dat voor oneven $m$, de gewichten van een vector en zijn negatie (modulo $n$) verschillend zijn. Dit stelt de auteurs in staat om disjuncte verzamelingen te vormen.
  • Parameters: $d \ge 2^{(m+1)/2} - 1$ en $d^\perp \ge 2^{(m+1)/2}$.
  • Dit presteert beter dan of gelijk aan de punctured Reed-Muller codes.
• Constructie 2: Een geavanceerde constructie die gebruikmaakt van verzamelingen gebaseerd op het gewicht van elementen modulo 2.
  • Parameters: $d \ge 4 \cdot (2^{(m-1)/2} - 4) + 1$ en $d^\perp \ge 2^{(m-1)/2}$.
  • Voordeel: Deze code heeft een grotere minimale afstand dan de codes uit referentie [28], terwijl de duale afstand gelijk blijft.
• Algemene prestatie: Voor beide families in dit geval geldt dat het product $d \cdot d^\perp$ asymptotisch benadert tot $2n$. Dit is een uitzonderlijk resultaat, aangezien de meeste bekende codes een product rond de $n$ hebben.

4. Significatie en Impact

• Doorbreken van de Trade-off: De belangrijkste bijdrage is het aantonen dat het mogelijk is om zowel $d$ als $d^\perp$ tegelijkertijd te maximaliseren, waardoor het product $d \cdot d^\perp$ de grens van $n$ overschrijdt en in sommige gevallen $2n$ benadert.
• Verbetering boven Bestaande Codes: De geconstrueerde codes supereren de bekende punctured Reed-Muller codes en eerdere cyclische code-constructies (zoals die van Sun et al. en Tang et al.) op het gebied van minimale afstand, zonder in te leveren op de duale afstand.
• Open Probleem: De auteurs stellen een nieuw open probleem: bestaat er een oneindige familie van binaire cyclische codes waarbij $\limsup_{n \to \infty} \frac{d \cdot d^\perp}{n} > 2$? Hun resultaten suggereren dat de bovengrens van deze verhouding mogelijk hoger ligt dan eerder gedacht.

Conclusie

Dit artikel levert een significante bijdrage aan de theorie van binaire cyclische codes door nieuwe, geoptimaliseerde families te presenteren die de bekende ondergrenzen voor minimale en duale afstand doorbreken. Door slimme algebraïsche constructies van definiërende verzamelingen te gebruiken, slagen de auteurs erin om codes te creëren die asymptotisch de beste bekende parameters bereiken, wat van groot belang is voor de ontwikkeling van efficiënte en robuuste foutcorrigerende codes.