Kod wielomianu

W teorii kodowania kod wielomianowy jest rodzajem kodu liniowego , którego zestaw prawidłowych słów kodowych składa się z tych wielomianów (zwykle o pewnej ustalonej długości), które są podzielne przez dany ustalony wielomian (o krótszej długości, zwany wielomianem generatora ).

Definicja

Napraw pole $_$ , elementy _ W celu konstruowania kodów wielomianowych identyfikujemy ciąg symboli $a_ {n-1} \ ldots a_ {0}}$$Displaystyle$ wielomianem

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

Ustal $niech$ i $pewnym$ ustalonym $wielomianem$ zwanym _ _ Kod wielomianowy generowany przez $to$ kod, którego słowa kodowe są dokładnie podzielnymi wielomianami stopnia niż { $}$ (bez reszty) przez ${\ Displaystyle g (x)}$ .

Przykład

Rozważ kod wielomianu nad ${\ Displaystyle GF (2) = \ {0,1 \}}$ z ${\ Displaystyle n = 5}$ , ${\ Displaystyle m = 2}$ i wielomian generatora sol $\ Displaystyle g (x) = x ^ {2} + x + 1}$ . Kod ten składa się z następujących słów kodowych:

${\ Displaystyle 0 \ cdot g (x), \ quad 1 \ cdot g (x ),\quad x\cdot g(x),\quad (x+1)\cdot g(x),}$

${\ Displaystyle 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).}$

Lub wyraźnie napisane:

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

${\ Displaystyle 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.}$

Ponieważ kod wielomianu jest zdefiniowany w binarnym polu Galois $a$ jako , modulo końcowe wielomiany to:

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

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

Równoważnie, wyrażone jako ciągi cyfr binarnych, słowa kodowe to:

${\ Displaystyle 00000, \ quad 00111, \ quad 01110, \ quad 01001,}$

${\ Displaystyle 11100, \ quad 11011,\quad 10010,\quad 10101 .}$

To, jak każdy kod wielomianowy, jest rzeczywiście kodem liniowym , tj. liniowe kombinacje słów kodowych są ponownie słowami kodowymi. W przypadku takim jak ten, gdzie polem jest GF(2), kombinacje liniowe są znajdowane poprzez XOR słów kodowych wyrażonych w postaci binarnej (np. 00111 XOR 10010 = 10101).

Kodowanie

W kodzie wielomianowym nad $m$$Displaystyle$ i wielomianem generatora $( x )$$(x)}$ m , będzie dokładnie ${\ displaystyle q ^ {nm}}$ słów kodowych. Rzeczywiście, z definicji ${\ Displaystyle p (x)}$ jest słowem kodowym wtedy i tylko wtedy, gdy ma postać ${\ Displaystyle p (x) = g (x) \ cdot q (x)}$ , gdzie ${\ Displaystyle q (x)}$ ( iloraz ) ma stopień mniejszy niż ${\ Displaystyle nm}$ . Ponieważ istnieje ${\ displaystyle q ^ {nm}}$ takich ilorazów jest taka sama liczba możliwych słów kodowych. Zwykłe (niekodowane) słowa danych powinny zatem mieć długość ${\ displaystyle nm}$

Niektórzy autorzy, na przykład (Lidl i Pilz, 1999), omawiają tylko mapowanie ${\ Displaystyle q (x) \ mapsto g (x) \ cdot q (x) }$ jako przypisanie słów danych do słów kodowych. Ma to jednak tę wadę, że słowo danych nie pojawia się jako część słowa kodowego.

$,$ systematycznego kodu często używana jest następująca metoda : biorąc $displaystyle d (x)}$ uwagę słowo danych długości ${\ displaystyle nm}$ najpierw pomnóż przez ${\ Displaystyle x ^ {m}}$ , co skutkuje przesunięciem ${\ Displaystyle d (x)}$ o ${\ Displaystyle m}$ miejsca po lewej stronie. Ogólnie rzecz biorąc, nie będzie podzielna przez ${\ Displaystyle g (x)} sol$$Displaystyle g (x)} sol ( x ) {\$ g ( x)} . Istnieje jednak unikalne słowo kodowe, które można uzyskać, dostosowując skrajne prawe $^ {m} d (x)$ ( $)$ . Aby to obliczyć, oblicz resztę z dzielenia ${\ Displaystyle x ^ {m} d (x)}$ przez ${\ Displaystyle g (x)}$ :

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

gdzie ${\ displaystyle r (x)}$ ma stopień mniejszy niż ${\ displaystyle m}$ . Słowo kodowe odpowiadające słowu danych ${\ Displaystyle d (x)}$ następnie definiowane jako re

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

Zwróć uwagę na następujące właściwości:

1. ${\ Displaystyle p (x) = g (x) \ cdot q (x)}$ , który jest podzielny przez ${\ Displaystyle g (x)}$ . W szczególności ${\ displaystyle p (x)}$ jest prawidłowym słowem kodowym.
2. Ponieważ $r (x)}$$Displaystyle$ ma stopień mniejszy niż $\ Displaystyle$ skrajne lewe p $p (x)} zgadzają się r ( x ) {\ Displaystyle r ($ ) z odpowiednimi symbolami ${\ Displaystyle x ^ {m} d (x)}$ . Innymi słowy, pierwszy ${\ displaystyle nm}$ symbole słowa kodowego są takie same jak oryginalne słowo danych. Pozostałe $lub$ nazywane są cyframi sumy kontrolnej bitami kontrolnymi .

Przykład

Dla powyższego kodu z ${\ Displaystyle n = 5}$ , ${\ Displaystyle m = 2}$ i wielomian generatora sol $\ Displaystyle g (x) = x ^{2}+x+1}$ , otrzymujemy następujące przyporządkowanie słów danych do słów kodowych:

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

Rozszyfrowanie

Błędną wiadomość można wykryć w prosty sposób poprzez dzielenie wielomianu przez wielomian generatora, co daje niezerową resztę.

$,$ że słowo kodowe jest wolne od błędów, systematyczny kod można zdekodować po prostu usuwając sumy kontrolnej.

Jeśli występują błędy, przed dekodowaniem należy przeprowadzić korekcję błędów. Istnieją wydajne algorytmy dekodowania dla określonych kodów wielomianowych, takich jak kody BCH .

Własności kodów wielomianowych

Podobnie jak w przypadku wszystkich kodów cyfrowych, możliwości wykrywania i korygowania błędów kodów wielomianowych są określone przez minimalną odległość Hamminga kodu. Ponieważ kody wielomianowe są kodami liniowymi, minimalna odległość Hamminga jest równa minimalnej wadze dowolnego niezerowego słowa kodowego. W powyższym przykładzie minimalna odległość Hamminga wynosi 2, ponieważ 01001 jest słowem kodowym i nie ma niezerowego słowa kodowego z ustawionym tylko jednym bitem.

Bardziej szczegółowe właściwości kodu wielomianowego często zależą od określonych właściwości algebraicznych jego wielomianu generatora. Oto kilka przykładów takich właściwości:

• Kod wielomianu jest cykliczny wtedy i tylko wtedy, gdy wielomian generatora dzieli . ${\ displaystyle x ^ {n} -1}$ .
• Jeśli wielomian generatora jest prymitywny , to wynikowy kod ma odległość Hamminga co najmniej 3, pod warunkiem, że ${\ Displaystyle n \ równoważnik 2 ^ {m} -1}$ .
• W kodach BCH wielomian generatora jest wybierany tak, aby miał określone pierwiastki w polu rozszerzenia, w sposób zapewniający dużą odległość Hamminga.

Algebraiczny charakter kodów wielomianowych, ze sprytnie dobranymi wielomianami generującymi, często można również wykorzystać do znalezienia wydajnych algorytmów korekcji błędów. Tak jest w przypadku kodów BCH .

Konkretne rodziny kodów wielomianowych

• Kody cykliczne – każdy kod cykliczny jest jednocześnie kodem wielomianowym; popularnym przykładem jest CRC .
• Kody BCH – rodzina kodów cyklicznych o dużej odległości Hamminga i wydajnych algorytmach algebraicznej korekcji błędów.
• Kody Reeda-Solomona - ważny podzbiór kodów BCH o szczególnie wydajnej strukturze.

• WJ Gilbert i WK Nicholson: Nowoczesna algebra z aplikacjami , wydanie 2, Wiley, 2004.
• R. Lidla i G. Pilza. Applied Abstract Algebra, wydanie 2. Wiley, 1999.