Polynomkod

I kodningsteorin är en polynomkod en typ av linjär kod vars uppsättning giltiga kodord består av de polynom (vanligtvis av någon fast längd) som är delbara med ett givet fast polynom (av kortare längd, kallat generatorpolynom ) .

Definition

Fixa ett ändligt fält $GF(q)$ , vars element vi kallar symboler . I syfte att konstruera polynomkoder identifierar vi en sträng av $n$ symboler $a_{n-1}\ldots a_{0}$ med polynomet

a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}.\,

Fixa heltal $m\leq n$ och låt $g(x)$ vara något fast polynom av graden $m$ , kallat generatorpolynomet . Polynomkoden som genereras av $g(x)$ är koden vars kodord är exakt de polynom med grad mindre än $n$ som är delbara (utan rest) med $g(x)$ .

Exempel

Betrakta polynomkoden över $GF(2)=\{0,1\}$ med $n=5$ , $m =2$ , och generatorpolynomet $g(x)=x^{2}+x+1$ . Denna kod består av följande kodord:

0\cdot g(x),\quad 1\cdot g(x) ),\quad x\cdot g(x),\quad (x+1)\cdot g(x),

x^{2}\cdot g(x),\quad (x^{2}+1)\cdot g(x),\quad (x^{2}+x)\cdot g(x) ,\quad (x^{2}+x+1)\cdot g(x).

Eller uttryckligen skrivet:

0,\quad x^{2}+x+1,\quad x^{ 3}+x^{2}+x,\quad x^{3}+2x^{2}+2x+1,

x^{4}+x^{3}+x^{ 2},\quad x^{4}+x^{3}+2x^{2}+x+1,\quad x^{4}+2x^{3}+2x^{2}+x,\ quad x^{4}+2x^{3}+3x^{2}+2x+1.

Eftersom polynomkoden definieras över det binära galoisfältet $GF(2)=\{0,1\}$ representeras polynomelement som en modulo -2 summa och slutliga polynom är:

0,\quad x^{2}+x+1,\quad x^{3}+x^{2 }+x,\quad x^{3}+1,

x^{4}+x^{3}+x^{2},\quad x^{4}+x^{3}+x+1,\quad x^{4}+x,\quad x^ {4}+x^{2}+1.

På motsvarande sätt, uttryckt som strängar av binära siffror, är kodorden:

{\displaystyle 00000,\quad 00111,\quad 01110,\quad 01001,} 11100 , 11011 , 10011 , 10010 1, 1010 1, 01 , 1 011

quad

Detta, som varje polynomkod, är verkligen en linjär kod , dvs linjära kombinationer av kodord är återigen kodord. I ett fall som detta där fältet är GF(2), hittas linjära kombinationer genom att ta XOR för kodorden uttryckta i binär form (t.ex. 00111 XOR 10010 = 10101).

Kodning

I en polynomkod över $GF(q)$ kodlängd $n$ och generatorpolynomet $g(x)$ av graden $m$ , kommer det att finnas exakt $q^{nm}$ kodord. Faktiskt, per definition $p(x)$ ett kodord om och endast om det har formen $p(x) )=g(x)\cdot q(x)$ , där $q(x)$ (kvoten ) har en grad mindre än $nm$ . Eftersom det finns $q^{nm}$ sådana kvoter tillgängliga, finns det samma antal möjliga kodord. Vanliga (okodade) dataord bör därför ha längden $nm$

Vissa författare, som (Lidl & Pilz, 1999), diskuterar bara mappningen $q(x)\mapsto g(x)\cdot q(x)$ som tilldelningen från dataord till kodord. Detta har emellertid nackdelen att dataordet inte förekommer som en del av kodordet.

Istället används ofta följande metod för att skapa en $d(x)$ kod : givet ett dataord $d(x)$ med längden $nm$ , multiplicera först med $x^{m}$ , vilket har effekten av att flytta $d(x)$ med $m$ platser till vänster. I allmänhet $x^{m}d(x)$ inte att vara delbart med $g(x)$ , dvs det kommer inte att vara ett giltigt kodord . Det finns dock ett unikt kodord som kan erhållas genom att justera de $m$ symbolerna längst till höger av $x^{m}d(x)$ . För att beräkna det, beräkna resten av att dividera $x^{m}d(x)$ med $g(x)$ :

x^{m}d(x)=g(x)\cdot q(x)+r(x) ,\,

där $r(x)$ är av grad mindre än $m$ . Kodordet som motsvarar dataordet $d(x)$ definieras då till att vara

p(x):=x^{m}d(x)-r(x),\,

Observera följande egenskaper:

${\displaystyle p(x)=g(x)\cdot q(x)} ,$ som är delbart med $g(x)$ . I synnerhet $p(x)$ ett giltigt kodord.
Eftersom $r(x)$ är av grad mindre än ${\displaystyle m} stämmer$ de $nm$ symbolerna längst till vänster i $p(x)$ ( med motsvarande symboler för $x^{m}d(x)$ . Med andra ord, de första $nm$ symbolerna i kodordet är desamma som det ursprungliga dataordet. De återstående $m$ -symbolerna kallas kontrollsiffror eller kontrollbitar .

Exempel

För ovanstående kod med $n=5$ , $m=2$ och generatorpolynomet $g(x)=x ^{2}+x+1$ får vi följande tilldelning från dataord till kodord:

000 ↦ 000 00
001 ↦ 001 11
010 ↦ 010 01
011 ↦ 011 10
100 ↦ 100 10
101 ↦ 101 01
110 ↦ 110 11
111 ↦ 111 00

Avkodning

Ett felaktigt meddelande kan upptäckas på ett enkelt sätt genom polynomdelning av generatorpolynomet vilket resulterar i en rest som inte är noll.

Om man antar att kodordet är fritt från fel, kan en systematisk kod avkodas helt enkelt genom att ta bort m {\ $m}$ kontrollsummesiffror.

Om det finns fel, bör felkorrigering utföras före avkodning. Effektiva avkodningsalgoritmer finns för specifika polynomkoder, såsom BCH-koder .

Egenskaper för polynomkoder

Som för alla digitala koder, bestäms feldetekterings- och korrigeringsförmågan hos polynomkoder av kodens minsta Hamming-avstånd . Eftersom polynomkoder är linjära koder, är det minsta Hamming-avståndet lika med minimivikten för ett kodord som inte är noll. I exemplet ovan är det minsta Hamming-avståndet 2, eftersom 01001 är ett kodord, och det finns inget kodord som inte är noll med bara en bit inställd.

Mer specifika egenskaper hos en polynomkod beror ofta på särskilda algebraiska egenskaper hos dess generatorpolynom. Här är några exempel på sådana egenskaper:

En polynomkod är cyklisk om och endast om generatorpolynomet delar $x^{n}-1$ .
Om generatorpolynomet är primitivt har den resulterande koden Hamming-avståndet minst 3, förutsatt att $n\leq 2^{m}-1$ .
I BCH-koder är generatorpolynomet valt att ha specifika rötter i ett förlängningsfält, på ett sätt som uppnår högt Hamming-avstånd.

Den algebraiska naturen hos polynomkoder, med smart utvalda generatorpolynom, kan också ofta utnyttjas för att hitta effektiva felkorrigeringsalgoritmer. Detta är fallet för BCH-koder .

Specifika familjer av polynomkoder

Cykliska koder – varje cyklisk kod är också en polynomkod; ett populärt exempel är CRC -koden.
BCH-koder – en familj av cykliska koder med högt Hamming-avstånd och effektiva algebraiska felkorrigeringsalgoritmer.
Reed–Solomon-koder – en viktig delmängd av BCH-koder med särskilt effektiv struktur.

WJ Gilbert och WK Nicholson: Modern Algebra with Applications , 2:a upplagan, Wiley, 2004.
R. Lidl och G. Pilz. Tillämpad abstrakt algebra, 2:a upplagan. Wiley, 1999.