Construction of MRD Codes Based on Circular-Shift Operations

Titel: Constructie van MRD-codes gebaseerd op circulaire verschuivingen

Auteurs: Zhe Zhai, Sheng Jin, Qifu Tyler Sun, Zongpeng Li
Affiliaties: Universiteit voor Wetenschap en Technologie Beijing, Tsinghua Universiteit (China)

1. Probleemstelling

Maximum Rank Distance (MRD) codes zijn een belangrijke klasse van foutcorrigerende codes met toepassingen in cryptografie, gedistribueerde opslag en subspace codes. De meest bekende constructies, zoals de (generaliseerde) Gabidulin-codes en de Twisted Gabidulin-codes, zijn gebaseerd op de rekenkunde van uitbreidingsvelden $\mathbb{F}_{q^N}$.

De belangrijkste beperkingen van deze traditionele benaderingen zijn:

• Complexiteit: Naarmate de parameter $N$ (de dimensie van het uitbreidingsveld) groter wordt, wordt de rekenkundige complexiteit van bewerkingen in $\mathbb{F}_{q^N}$ aanzienlijk hoger. Dit hindert de praktische implementatie en de selectie van parameters.
• Basis-selectie: Het efficiënt transformeren van een vector over $\mathbb{F}_{q^N}$ naar een matrix over $\mathbb{F}_q$ vereist een zorgvuldige selectie van een basis, wat vaak niet optimaal is onderzocht voor praktische doeleinden.
• Beperkingen bij $q=2$: Bestaande constructies zoals Twisted Gabidulin-codes zijn niet altijd toepasbaar voor het geval $q=2$.

Het doel van dit werk is het ontwikkelen van een constructie van MRD-codes die volledig werkt over het grondveld $\mathbb{F}_q$, waardoor de complexiteit van uitbreidingsveldrekenkunde wordt vermeden en de implementatie efficiënter wordt.

2. Methodologie

De auteurs stellen een nieuwe constructie voor van MRD-codes die volledig gebaseerd is op circulaire verschuivingen (circular-shift operations) en lineaire bewerkingen over $\mathbb{F}_q$.

Kernconcepten:

• Parameters: Laat $q$ een priemgetal zijn en $L$ een positief geheel getal zodat $\gcd(q, L) = 1$.
  • $m_L$: De multiplicatieve orde van $q$ modulo $L$ (d.w.z. $q^{m_L} \equiv 1 \pmod L$).
  • $J$: De Euler-totientfunctie van $L$ (het aantal gehele getallen kleiner dan $L$ die copriem zijn met $L$).
• Constructie: De code $C$ wordt gedefinieerd als de verzameling van matrices die worden gegenereerd door:
  $$C = \{ \Delta(m(I_k \otimes P)\Psi_{k \times n}(I_n \otimes Q)) : m \in \mathbb{F}_q^{Jk} \}$$
  Waarbij:
  • $\Psi_{k \times n}$ een blokmatrix is bestaande uit circulaire permutatiematrices ($C_L^l$).
  • $P$ en $Q$ specifieke matrices zijn over $\mathbb{F}_q$ (geconstrueerd via Vandermonde-matrices en wortels van eenheid).
  • $\Delta$ een afbeelding is die een rijvector omzet in een $J \times n$ matrix.
• Polynoomkarakterisering: De auteurs karakteriseren zowel de voorgestelde codes als Gabidulin-codes via een set van $q$-lineaire polynomen gedefinieerd over de rijvectorruimte $\mathbb{F}_q^N$ in plaats van over het uitbreidingsveld $\mathbb{F}_{q^N}$. Dit biedt een unificerend raamwerk om de verschillen en overeenkomsten te analyseren.

3. Belangrijkste Bijdragen

1. Efficiënte Constructie zonder Uitbreidingsveld:
   De voorgestelde $(J \times n, q^{Jk}, d)$ MRD-codes worden volledig gegenereerd met bewerkingen over $\mathbb{F}_q$ (opties en circulaire verschuivingen). Dit elimineert de noodzaak voor rekenkunde in $\mathbb{F}_{q^J}$, wat de implementatie aanzienlijk vereenvoudigt.

2. Analyse van Relaties met Gabidulin-codes:
   De auteurs onderzoeken de inherente relatie tussen hun nieuwe codes en Gabidulin-codes:

   • Geval $J \neq m_L$: Onder specifieke parameterinstellingen (waarbij de exponenten een bepaalde lineaire relatie hebben) zijn de voorgestelde codes niet equivalent aan enige Gabidulin-code of Twisted Gabidulin-code. Dit betekent dat ze nieuwe families van MRD-codes introduceren.
   • Geval $J = m_L$: In dit specifieke geval blijken de voorgestelde codes equivalent te zijn aan Gabidulin-codes. Echter, de constructie biedt een nieuwe, efficiëntere manier om Gabidulin-codes te bouwen die direct over $\mathbb{F}_q$ werkt, in plaats van via $\mathbb{F}_{q^J}$.

3. Generalisatie van Gabidulin-codes:
   De auteurs tonen aan dat de voorgestelde codes, onder bepaalde keuzes van matrices $P$ en $Q, equivalent zijn aan een generalisatie van Gabidulin-codes. Deze generalisatie wordt gevormd door het sommeren en concateneren van meerdere $(m_L \times n, q^{m_L k}, d)$ Gabidulin-codes. Dit concept is volgens de auteurs nog niet eerder in de literatuur onderzocht.

4. Complexiteitsanalyse:
   Voor het geval $q=2$, $L$ priem is en $n \leq m_L$, wordt een theoretische analyse uitgevoerd:

   • Het genereren van een codewoord van de voorgestelde circulaire-shift-code vereist $O(nkL)$ XOR-bewerkingen.
   • Het genereren van een codewoord van een traditionele Gabidulin-code (gebaseerd op $\mathbb{F}_{2^{L-1}}$) vereist $O(nkL^2)$ XOR-bewerkingen (vanwege de complexe vermenigvuldiging in het uitbreidingsveld).

4. Resultaten

• MRD Eigenschap: De auteurs bewijzen dat de constructie voldoet aan de Singleton-bound en dus een MRD-code is met minimum afstand $d = n - k + 1$.
• Verschil met Bestaande Codes: Voor $J \neq m_L$ en specifieke parameters zijn de codes uniek en niet equivalent aan bekende Gabidulin- of Twisted Gabidulin-codes.
• Equivalentie bij $J = m_L$: Hoewel de codes in dit geval equivalent zijn aan Gabidulin-codes, biedt de circulaire-shift-methode een superieure implementatiebenadering.
• Berekeningscomplexiteit: De analyse bevestigt dat de nieuwe methode een lineaire complexiteit heeft ten opzichte van $L$, terwijl traditionele methoden kwadratisch zijn. Dit leidt tot een significant snelheidsvoordeel, vooral voor grotere waarden van $L$.

5. Betekenis en Toekomstperspectief

Deze studie is significant omdat het een brug slaat tussen de theorie van rank-metric codes en praktische implementatie-efficiëntie. Door de afhankelijkheid van uitbreidingsveldrekenkunde te elimineren, maken de auteurs MRD-codes toegankelijker voor toepassingen waar lage latentie en hoge snelheid cruciaal zijn (zoals in gedistribueerde opslagsystemen en netwerkcodering).

Toekomstig werk omvat:

• Het verder karakteriseren van de relatie tussen circulaire-shift-codes en Gabidulin-codes voor parameters die niet voldoen aan de specifieke voorwaarden.
• Het ontwikkelen van efficiënte decoderingsalgoritmen voor deze nieuwe codes.
• Het onderzoeken van verdere toepassingen in subspace codering.

Samenvattend biedt dit papier een krachtige, nieuwe methode voor het construeren van MRD-codes die zowel theoretisch interessant is (door nieuwe families en generalisaties te onthullen) als praktisch waardevol (door een drastische reductie in rekencomplexiteit).