Kod cykliczny - Cyclic code

W teorii kodowania , A kod cykliczny jest kod blokowy , przy czym obrót bitowy każdego słowa kodowego daje innego słowa należącego do kodu. Są to kody korygujące błędy, które mają właściwości algebraiczne, które są wygodne do skutecznego wykrywania i korygowania błędów .

Jeśli 00010111 jest prawidłowym słowem kodowym, zastosowanie przesunięcia kołowego w prawo daje ciąg 10001011. Jeśli kod jest cykliczny, to 10001011 jest ponownie prawidłowym słowem kodowym. Ogólnie rzecz biorąc, zastosowanie przesunięcia kołowego w prawo przesuwa najmniej znaczący bit (LSB) do skrajnej lewej pozycji, tak że staje się on najbardziej znaczącym bitem (MSB); pozostałe pozycje są przesunięte o 1 w prawo.

Definicja

Niech będzie kodem liniowym nad polem skończonym (zwanym również polem Galois ) o długości bloku . jest nazywany kodem cyklicznym, jeżeli dla każdego słowa kodowego z , słowo w otrzymane przez cykliczne przesunięcie w prawo składowych jest ponownie słowem kodowym. Ponieważ jedno cykliczne przesunięcie w prawo jest równe cyklicznym przesunięciom w lewo, kod cykliczny może być również zdefiniowany poprzez cykliczne przesunięcia w lewo. Dlatego kod liniowy jest cykliczny dokładnie wtedy, gdy jest niezmienny we wszystkich przesunięciach cyklicznych. ${\displaystyle {\mathcal {C}}}$${\ Displaystyle GF (q)}$ ${\ Displaystyle n}$${\displaystyle {\mathcal {C}}}$ ${\ Displaystyle c = (c_ {1}, \ ldots, c_ {n})}$${\displaystyle {\mathcal {C}}}$${\ Displaystyle (c_ {n}, c_ {1}, \ ldots, c_ {n-1})}$${\ Displaystyle GF (q) ^ {n}}$${\displaystyle n-1}$${\displaystyle {\mathcal {C}}}$

Kody cykliczne mają pewne dodatkowe ograniczenia strukturalne w kodach. Opierają się na polach Galois, a ze względu na swoje właściwości strukturalne są bardzo przydatne do kontroli błędów. Ich struktura jest silnie związana z polami Galois, przez co algorytmy kodowania i dekodowania kodów cyklicznych są wydajne obliczeniowo.

Struktura algebraiczna

Kody cykliczne można powiązać z ideałami w niektórych kręgach. Niech będzie pierścieniem wielomianowym nad ciałem skończonym . Zidentyfikuj elementy kodu cyklicznego z wielomianami w taki sposób, że mapuje się do wielomianu : w ten sposób mnożenie przez odpowiada przesunięciu cyklicznemu. Wtedy jest ideałem w , a więc głównym , ponieważ jest głównym idealnym pierścieniem . Ideał jest generowany przez unikalny element moniczny w minimalnym stopniu, wielomian generujący . To musi być dzielnik . Wynika z tego, że każdy kod cykliczny jest kodem wielomianowym . Jeśli wielomian generujący ma stopień, to ranga kodu to . ${\ Displaystyle R = A [x] / (x ^ {n}-1)}$${\ Displaystyle A = GF (q)}$${\displaystyle C}$${\ Displaystyle R}$${\ Displaystyle (c_ {0}, \ ldots, c_ {n-1})}$${\ Displaystyle c_ {0}+ c_ {1} x + \ cdots + c_ {n-1} x ^ {n-1}}$${\displaystyle x}$${\displaystyle C}$${\ Displaystyle R}$${\ Displaystyle R}$${\displaystyle C}$ ${\displaystyle g}$${\ Displaystyle x ^ {n} -1}$${\displaystyle g}$${\displaystyle d}$${\displaystyle C}$${\displaystyle nd}$

Idempotent od jest słowo kodowe , tak że (to znaczy jest elementem idempotent z ) i jest kod identyfikacyjny, który jest dla każdego słowa kodu . Jeśli i są względnie pierwsze, takie słowo zawsze istnieje i jest niepowtarzalne; jest to generator kodu. ${\displaystyle C}$${\displaystyle e}$${\ Displaystyle e ^ {2} = e}$${\displaystyle e}$${\displaystyle C}$${\displaystyle e}$${\displaystyle e\cdot c=c}$${\displaystyle c}$${\ Displaystyle n}$${\displaystyle q}$

Irreducible kod jest kodem cyklicznym, w którym kod, jako ideał jest nieredukowalne, czyli jest minimalny w , tak że jej wielomian check jest wielomian nierozkładalny . ${\ Displaystyle R}$

Przykłady

Na przykład, jeśli i , zbiór słów kodowych zawartych w kodzie cyklicznym generowanym przez jest dokładnie ${\ Displaystyle A = \ mathbb {F} _ {2}}$${\displaystyle n=3}$${\ Displaystyle (1,1,0)}$

${\ Displaystyle ((0,0,0), (1,1,0), (0,1,1), (1,0,1))}$.

Odpowiada ideałowi generowanemu przez . ${\ Displaystyle \ mathbb {F} _ {2} [x] / (x ^ {3}-1)}$${\ Displaystyle (1+x)}$

Wielomian jest nieredukowalny w pierścieniu wielomianowym, a zatem kod jest kodem nieredukowalnym. ${\ Displaystyle (1+x)}$

Idempotentem tego kodu jest wielomian odpowiadający słowu kodowemu . ${\displaystyle x+x^{2}}$${\ Displaystyle (0,1,1)}$

Trywialne przykłady

Trywialne przykłady kodów cyklicznych to sam kod oraz kod zawierający tylko zerowe słowo kodowe. Odpowiadają one generatorom i odpowiednio: te dwa wielomiany muszą zawsze być czynnikami . ${\ Displaystyle A ^ {n}}$${\ Displaystyle 1}$${\ Displaystyle x ^ {n} -1}$${\ Displaystyle x ^ {n} -1}$

Powyżej na bit parzystości kodu, składający się z wszystkich słów nawet wagi odpowiada generatora . Znowu nad tym zawsze musi być czynnik . ${\ Displaystyle GF(2)}$${\displaystyle x+1}$${\ Displaystyle GF(2)}$${\ Displaystyle x ^ {n} -1}$

Kody quasi-cykliczne i kody skrócone

Zanim zagłębimy się w szczegóły dotyczące kodów cyklicznych najpierw omówimy kody quasi-cykliczne i skrócone, które są ściśle związane z kodami cyklicznymi i wszystkie mogą być konwertowane na siebie.

Definicja

Kody quasi-cykliczne:

Pseudo-kod cykliczny jest liniowym kod blokowy, że dla niektórych który jest względnie pierwsze do , wielomian JeSt kodowym wielomian gdy to słowo wielomianu. ${\displaystyle (n,k)}$ ${\displaystyle b}$${\ Displaystyle n}$${\ Displaystyle x ^ {b} c (x) {\ pmod {x ^ {n} -1}}}$${\displaystyle c(x)}$

W tym przypadku wielomian słowa kodowego jest elementem kodu liniowego, którego słowa kodowe są wielomianami podzielnymi przez wielomian o krótszej długości, zwany wielomianem generującym . Każdy wielomian słowa kodowego może być wyrażony w postaci , gdzie jest wielomianem generującym. Każde słowo kodowe kodu cyklicznego może być powiązane z wielomianem słowa kodowego, a mianowicie . Kod quasi-cykliczny z równym to kod cykliczny. ${\ Displaystyle c (x) = a (x) g (x)}$${\displaystyle g(x)}$${\ Displaystyle (c_ {0}, .., c_ {n-1})}$${\displaystyle C}$${\ Displaystyle \ suma _ {i = 0} ^ {n-1} c_ {i} * x ^ {i}}$${\displaystyle b}$${\ Displaystyle 1}$

Definicja

Skrócone kody:

Kod liniowy zwany właściwego skrócony kod cykliczny , czy może być otrzymany przez usunięcie pozycji z kodem cyklicznej. ${\displaystyle [n,k]}$${\displaystyle b}$${\displaystyle (nb,kb)}$

W skróconych kodach symbole informacyjne są usuwane w celu uzyskania pożądanej długości bloku mniejszej niż projektowana długość bloku. Symbole brakujących informacji są zwykle wyobrażane jako znajdujące się na początku słowa kodowego i traktowane są jako 0. Dlatego − jest stałe, a następnie zmniejszane, które ostatecznie maleje . Nie jest konieczne usuwanie symboli początkowych. W zależności od aplikacji czasami kolejne pozycje są traktowane jako 0 i są usuwane. ${\ Displaystyle n}$${\displaystyle k}$${\displaystyle k}$${\ Displaystyle n}$

Wszystkie symbole, które zostały usunięte, nie muszą być przesyłane, a po stronie odbiorczej mogą być ponownie wstawione. Aby przekonwertować kod cykliczny na kod skrócony, ustaw symbole na zero i usuń je z każdego słowa kodowego. Dowolny kod cykliczny można przekonwertować na kody quasi-cykliczne przez upuszczenie co th symbolu, gdzie jest współczynnikiem . Jeżeli upuszczone symbole nie są symbolami kontrolnymi, wtedy ten kod cykliczny jest również kodem skróconym. ${\displaystyle (n,k)}$${\displaystyle (nb,kb)}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$${\ Displaystyle n}$

Cykliczne kody do korygowania błędów

Teraz rozpoczniemy omówienie kodów cyklicznych bezpośrednio od wykrywania i korekcji błędów . Kody cykliczne mogą być używane do korygowania błędów, podobnie jak kody Hamminga, ponieważ kody cykliczne mogą być używane do korygowania pojedynczego błędu. Podobnie są one również używane do korygowania podwójnych błędów i błędów seryjnych. Wszystkie rodzaje korekcji błędów zostały krótko omówione w dalszych podrozdziałach.

Kod Hamminga (7,4) ma wielomian generujący . Ten wielomian ma zero w polu rozszerzenia Galois w elemencie pierwotnym i wszystkie słowa kodowe spełniają . Kody cykliczne mogą być również używane do korygowania podwójnych błędów w polu . Długość bloku będzie równa elementom pierwotnym i jako zera w tym, ponieważ rozważamy przypadek dwóch błędów, więc każdy będzie reprezentował jeden błąd. ${\ Displaystyle g (x) = x ^ {3} + x + 1}$ ${\ Displaystyle GF (8)}$${\ Displaystyle \ alfa}$${\ Displaystyle {\ mathcal {C}} (\ alfa) = 0}$${\ Displaystyle GF(2)}$${\ Displaystyle n}$${\ Displaystyle 2 ^ {m} -1}$${\ Displaystyle \ alfa}$${\ Displaystyle \ alfa ^ {3}}$${\ Displaystyle GF (2 ^ {m})}$

Otrzymane słowo jest wielomianem stopnia podanego jako ${\displaystyle n-1}$${\ Displaystyle v (x) = a (x) g (x) + e (x)}$

gdzie może mieć co najwyżej dwa niezerowe współczynniki odpowiadające dwóm błędom. ${\displaystyle e(x)}$

Definiujemy Syndrome Polynomial , jako resztę wielomianu podzielonego przez wielomian generujący, tj. ${\ Displaystyle S (x)}$${\displaystyle v(x)}$${\displaystyle g(x)}$

${\ Displaystyle S (x) \ równoważne v (x) \ równoważne (a (x) g (x) + e (x)) \ równoważne e (x) \ mod g (x)}$jak . ${\ Displaystyle (a (x) g (x)) \ równoważnik 0 \ mod g (x)}$

Za poprawienie dwóch błędów

Niech elementy pola i będą dwoma numerami lokalizacji błędu. Jeśli wystąpi tylko jeden błąd, to jest równy zero, a jeśli żaden nie wystąpi, oba są zerowe. ${\displaystyle X_{1}}$${\displaystyle X_{2}}$${\displaystyle X_{2}}$

Niech i . ${\displaystyle S_{1}={v}(\alfa)}$${\ Displaystyle S_ {3} = {v} (\ alfa ^ {3})}$

Te elementy pola nazywane są „syndromami”. Teraz ponieważ na elementach pierwotnych wynosi zero i , więc możemy pisać i . Jeśli powiedzmy, że wystąpią dwa błędy, to ${\displaystyle g(x)}$${\ Displaystyle \ alfa}$${\ Displaystyle \ alfa ^ {3}}$${\displaystyle S_{1}=e(\alfa)}$${\displaystyle S_{3}=e(\alfa ^{3})}$

${\ Displaystyle S_ {1} = \ alfa ^ {i} + \ alfa ^ {i'}}$i . ${\ Displaystyle S_ {3} = \ alfa ^ {3i} + \ alfa ^ {3i'}}$

I te dwa można uznać za dwie pary równań z dwiema niewiadomymi i stąd możemy napisać ${\ Displaystyle GF (2 ^ {m})}$

${\displaystyle S_{1}=X_{1}+X_{2}}$i . ${\displaystyle S_{3}=(X_{1})^{3}+(X_{2})^{3}}$

Stąd, jeśli dwie pary równań nieliniowych mogą zostać rozwiązane, kody cykliczne mogą zostać użyte do skorygowania dwóch błędów.

Kod Hamminga

Kod Hamminga(7,4) można zapisać jako kod cykliczny przez GF(2) z generatorem . W rzeczywistości każdy binarny kod Hamminga postaci Ham(r, 2) jest równoważny kodowi cyklicznemu, a każdy kod Hamminga postaci Ham(r,q) z r i q-1 względnie pierwszym jest również równoważny kod. Mając kod Hamminga w postaci Ham(r,2) z , zbiór parzystych słów kodowych tworzy kod cykliczny . ${\ Displaystyle 1 + x + x ^ {3}}$${\displaystyle r\geq 3}$${\ Displaystyle [2 ^ {r} -1,2 ^ {r} -r-2,4]}$

Kod Hamminga do poprawiania pojedynczych błędów

Kod, którego minimalna odległość wynosi co najmniej 3, ma macierz kontrolną, której wszystkie kolumny są różne i niezerowe. Jeśli macierz kontrolna kodu binarnego zawiera wiersze, to każda kolumna jest -bitową liczbą binarną. Istnieją możliwe kolumny. Dlatego jeśli macierz kontrolna kodu binarnego z co najmniej 3 wierszami ma wiersze, to może mieć tylko kolumny, nie więcej. To definiuje kod zwany kodem Hamminga. ${\ Displaystyle m}$${\ Displaystyle m}$${\ Displaystyle 2 ^ {m} -1}$${\displaystyle d_{min}}$${\ Displaystyle m}$${\ Displaystyle 2 ^ {m} -1}$${\ Displaystyle (2 ^ {m} -1,2 ^ {m} -1-m)}$

Łatwo jest zdefiniować kody Hamminga dla dużych alfabetów . Musimy zdefiniować jedną macierz z liniowo niezależnymi kolumnami. Dla każdego słowa o wielkości będą kolumny, które są wielokrotnościami siebie. Tak więc, aby uzyskać liniową niezależność, wszystkie niezerowe krotki z jedynką jako najwyższym niezerowym elementem zostaną wybrane jako kolumny. Wtedy dwie kolumny nigdy nie będą zależne liniowo, ponieważ trzy kolumny mogą być zależne liniowo przy minimalnej odległości kodu równej 3. ${\displaystyle q}$${\ Displaystyle H}$${\displaystyle q}$${\ Displaystyle m}$

Tak więc istnieją niezerowe kolumny z jednym jako najwyższym niezerowym elementem. Dlatego kod Hamminga jest kodem. ${\ Displaystyle (q ^ {m}-1) / (q-1)}$${\ Displaystyle [(q ^ {m} -1) / (q-1), (q ^ {m} -1) / (q-1) -m]}$

Teraz, dla kodów cyklicznych, niech będzie elementem pierwotnym w , i niech . Wtedy i tak jest zerem wielomianu i jest wielomianem generującym dla kodu cyklicznego o długości bloku . ${\ Displaystyle \ alfa}$${\ Displaystyle GF (q ^ {m})}$${\ Displaystyle \ beta = \ alfa ^ {q-1}}$${\ Displaystyle \ beta ^ {(q ^ {m}-1) / (q-1)} = 1}$${\ Displaystyle \ beta}$${\ Displaystyle x ^ {(q ^ {m} -1) / (q-1)} -1}$${\ Displaystyle n = (q ^ {m} -1) / (q-1)}$

Ale dla , . A otrzymane słowo jest wielomianem stopnia podanego jako ${\displaystyle q=2}$${\displaystyle \alfa =\beta}$${\displaystyle n-1}$

${\ Displaystyle v (x) = a (x) g (x) + e (x)}$

gdzie lub gdzie reprezentuje lokalizacje błędów. ${\ Displaystyle e (x) = 0}$${\ Displaystyle x ^ {i}}$${\displaystyle i}$

Ale możemy również użyć jako elementu do indeksowania lokalizacji błędu. Ponieważ mamy i wszystkie uprawnienia od do są różne. Dlatego możemy łatwo określić lokalizację błędu ze chyba co stanowi żadnego błędu. Tak więc kod Hamminga jest pojedynczym kodem korygującym błąd za pomocą i . ${\ Displaystyle \ alfa ^ {i}}$${\ Displaystyle GF (2 ^ {m})}$${\ Displaystyle g (\ alfa ) = 0}$${\ Displaystyle V (\ alfa) = \ alfa ^ {i}}$${\ Displaystyle \ alfa}$${\ Displaystyle 0}$${\ Displaystyle 2 ^ {m} -2}$${\displaystyle i}$${\ Displaystyle \ alfa ^ {i}}$${\ Displaystyle V (\ alfa ) = 0}$${\ Displaystyle GF(2)}$${\ Displaystyle n = 2 ^ {m} -1}$${\ Displaystyle k = nm}$

Kody cykliczne do korygowania błędów serii

Od koncepcji odległości Hamminga kod z minimalną odległością może skorygować wszelkie błędy. Jednak w wielu kanałach wzorzec błędów nie jest zbyt arbitralny, występuje w bardzo krótkim odcinku wiadomości. Tego rodzaju błędy nazywane są błędami seryjnymi . Tak więc, aby poprawić takie błędy, otrzymamy bardziej wydajny kod o wyższej szybkości ze względu na mniej ograniczeń. Kody cykliczne są używane do korekcji błędów serii. W rzeczywistości, kody cykliczne mogą również korygować cykliczne błędy serii wraz z błędami serii. Cykliczne błędy burst są definiowane jako ${\displaystyle 2t+1}$${\displaystyle t}$

Cykliczny impuls długości to wektor, którego niezerowe składowe należą do (cyklicznie) kolejnych składowych, z których pierwsza i ostatnia są niezerowe. ${\displaystyle t}$${\displaystyle t}$

W postaci wielomianu cyklicznego rozerwanie długości można opisać w postaci wielomianu stopnia z niezerowym współczynniku . Tutaj definiuje wzorzec i definiuje punkt wyjścia błędu. Długość wzoru podana jest w stopniach . Wielomian syndromu jest unikalny dla każdego wzoru i jest podawany przez ${\displaystyle t}$${\ Displaystyle e (x) = x ^ {i} b (x) \ mod (x ^ {n} -1)}$${\displaystyle b(x)}$${\displaystyle t-1}$${\displaystyle b_{0}}$${\displaystyle b(x)}$${\ Displaystyle x ^ {i}}$${\displaystyle b(x)+1}$

${\ Displaystyle s (x) = e (x) \ mod g (x)}$

Liniowy kod blokowy, który koryguje wszystkie błędy serii o długości lub mniejszej, musi mieć przynajmniej symbole kontrolne. Dowód: Ponieważ każdy kod liniowy, który może poprawić wzorzec burst o długości lub mniejszej, nie może mieć jako słowa kodowego sekwencji o długości lub mniejszej, ponieważ gdyby tak było, to seria długości mogłaby zmienić słowo kodowe na wzorzec burst o długości , co również można uzyskać wykonując błąd serii o długości we wszystkich zerowych słowach kodowych. Teraz dowolne dwa wektory, które są niezerowe w pierwszych składnikach, muszą pochodzić z różnych zestawów tablicy, aby uniknąć ich różnicy będącej słowem kodowym serii o długości . Dlatego liczba takich zbiorów jest równa liczbie takich wektorów, które są . Stąd przynajmniej co-sets, a więc przynajmniej check symbol. ${\displaystyle t}$${\displaystyle 2t}$${\displaystyle t}$${\displaystyle 2t}$${\displaystyle t}$${\displaystyle t}$${\displaystyle t}$${\displaystyle 2t}$${\displaystyle 2t}$${\displaystyle q^{2t}}$${\displaystyle q^{2t}}$${\displaystyle 2t}$

Ta właściwość jest również znana jako powiązanie Riegera i jest podobna do powiązania Singletona dla losowego korygowania błędów.

Kody przeciwpożarowe jako ograniczenia cykliczne

W 1959 Philip Fire przedstawił konstrukcję kodów cyklicznych generowanych przez iloczyn dwumianu i prymitywnego wielomianu. Dwumian ma postać jakiejś dodatniej nieparzystej liczby całkowitej . Kod pożarowy to cykliczny kod korygujący błąd rozerwania nad wielomianem generatora ${\ Displaystyle x ^ {c} + 1}$${\displaystyle c}$${\ Displaystyle GF (q)}$

${\ Displaystyle g (x) = (x ^ {2t-1}-1) p (x)}$

gdzie jest wielomianem liczby pierwszej o stopniu nie mniejszym niż i nie podlega dzieleniu . Długość bloku kodu pożarowego jest najmniejszą liczbą całkowitą , która dzieli . ${\displaystyle p(x)}$${\ Displaystyle m}$${\displaystyle t}$${\displaystyle p(x)}$${\ Displaystyle x ^ {2t-1}-1}$${\ Displaystyle n}$${\displaystyle g(x)}$${\ Displaystyle x ^ {n} -1}$

Kod przeciwpożarowy może skorygować wszystkie błędy serii o długości t lub mniejszej, jeśli nie ma dwóch serii i nie występują w tym samym zbiorze. Można to udowodnić poprzez sprzeczność. Załóżmy, że istnieją dwa wybuchy niezerowe i długości lub mniej, a w tym samym wspólnie zestaw kodu. Tak więc ich różnica jest słowem kodowym. Ponieważ różnica jest wielokrotnością , jest również wielokrotnością . W związku z tym, ${\displaystyle b(x)}$${\ Displaystyle x ^ {j} b '(x)}$${\displaystyle b(x)}$${\ Displaystyle x ^ {j} b '(x)}$${\displaystyle t}$${\displaystyle g(x)}$${\ Displaystyle x ^ {2t-1}-1}$

${\ Displaystyle b (x) = x ^ {j} b '(x) \ mod (x ^ {2t-1}-1)}$.

To pokazuje, że jest to wielokrotność , So ${\displaystyle j}$${\displaystyle 2t-1}$

${\ Displaystyle b (x) = x ^ {l (2t-1)} b '(x)}$

dla niektórych . Teraz, gdy jest mniej niż i jest mniejsze niż to jest słowo kodowe. W związku z tym, ${\displaystyle l}$${\ Displaystyle l(2t-1)}$${\displaystyle t}$${\displaystyle l}$${\ Displaystyle q ^ {m} -1}$${\ Displaystyle (x ^ {l (2t-1)}-1) b (x)}$

${\ Displaystyle (x ^ {l (2t-1)}-1) b (x) = a (x) (x ^ {2t-1}-1) p (x)}$.

Ponieważ stopień jest mniejszy niż stopień , nie można dzielić . Jeśli nie jest zero, to również nie może dzielić, ponieważ jest mniejsze niż iz definicji , dzieli na nie mniejsze niż . Dlatego i równa się zero. Oznacza to, że oba wybuchy są takie same, wbrew założeniu. ${\displaystyle b(x)}$${\displaystyle p(x)}$${\displaystyle p(x)}$${\displaystyle b(x)}$${\displaystyle l}$${\displaystyle p(x)}$${\ Displaystyle x ^ {l (2t-1)} -1}$${\displaystyle l}$${\ Displaystyle q ^ {m} -1}$${\ Displaystyle m}$${\displaystyle p(x)}$${\ Displaystyle x ^ {l (2t-1)} -1}$${\displaystyle l}$${\ Displaystyle q ^ {m} -1}$${\displaystyle l}$${\displaystyle j}$

Kody przeciwpożarowe to najlepsze kody korygujące pojedyncze serie o dużej szybkości i są konstruowane analitycznie. Są one bardzo wysokie, a gdy i są równe, redundancja jest najmniejsza i równa . Używając wielu kodów pożarowych, można również skorygować dłuższe błędy serii. ${\ Displaystyle m}$${\displaystyle t}$${\displaystyle 3t-1}$

Do wykrywania błędów szeroko stosowane są kody cykliczne, nazywane cyklicznymi kodami nadmiarowymi . ${\displaystyle t-1}$

Kody cykliczne na transformacie Fouriera

Zastosowania transformacji Fouriera są szeroko rozpowszechnione w przetwarzaniu sygnałów. Ale ich zastosowania nie ograniczają się tylko do złożonych dziedzin; Przekształcenia Fouriera istnieją również w polu Galois . Kody cykliczne wykorzystujące transformację Fouriera można opisać w ustawieniu bliższym przetwarzaniu sygnału. ${\ Displaystyle GF (q)}$

Transformata Fouriera nad polami skończonymi

Transformata Fouriera nad polami skończonymi

Dyskretna transformata Fouriera wektora jest dana przez wektor gdzie: ${\displaystyle v=v_{0},v_{1},....,v_{n-1}}$${\ Displaystyle V = V_ {0}, V_ {1}, ....., V_ {n-1}}$

${\ Displaystyle V_ {k}}$= gdzie, ${\ Displaystyle \ Sigma _ {i = 0} ^ {n-1} e ^ {-j2 \ pi n ^ {-1} ik} V_ {i}}$

${\displaystyle k=0,.....,n-1}$

gdzie exp( ) jest pierwiastkiem jedności. Podobnie w skończonym polu pierwiastek jedności jest elementem porządku . W związku z tym ${\displaystyle -j2\pi/n}$${\ Displaystyle n}$${\ Displaystyle n}$${\ Displaystyle \ omega}$${\ Displaystyle n}$

Jeśli jest wektorem nad , i jest elementem porządku , to transformata Fouriera wektora jest wektorem a składowe są podane przez${\ Displaystyle v = (v_ {0}, v_ {1}, ...., v_ {n-1})}$${\ Displaystyle GF (q)}$${\ Displaystyle \ omega}$${\ Displaystyle GF (q)}$${\ Displaystyle n}$${\displaystyle v}$${\ Displaystyle V = (V_ {0}, V_ {1}, ....., V_ {n-1})}$

${\ Displaystyle V_ {j}}$= gdzie, ${\ Displaystyle \ Sigma _ {i = 0} ^ {n-1} \ omega ^ {ij} v_ {i}}$

${\displaystyle k=0,.....,n-1}$

Tu jest czas indeks, jest częstotliwość i jest widmo . Jedną ważną różnicą między transformatą Fouriera w polu zespolonym a polem Galois jest to, że pole zespolone istnieje dla każdej wartości, podczas gdy w polu Galois istnieje tylko wtedy, gdy dzieli . W przypadku pól rozszerzeń, jeśli dzielimy przez niektóre , w polu rozszerzenia będzie transformata Fouriera . W polu Galois wektor w dziedzinie czasu jest nad polem, ale widmo może być nad polem rozszerzenia . ${\displaystyle i}$${\displaystyle j}$${\ Displaystyle V}$${\ Displaystyle \ omega}$${\ Displaystyle n}$${\ Displaystyle \ omega}$${\ Displaystyle n}$${\displaystyle q-1}$${\ Displaystyle GF (q ^ {m})}$${\ Displaystyle n}$${\ Displaystyle q ^ {m} -1}$${\ Displaystyle m}$${\displaystyle v}$${\ Displaystyle GF (q)}$${\ Displaystyle V}$${\ Displaystyle GF (q ^ {m})}$

Widmowy opis kodów cyklicznych

Każde słowo kodowe kodu cyklicznego o długości bloku może być co najwyżej reprezentowane przez wielomian stopnia . Jego koder można zapisać jako . Dlatego w dziedzinie częstotliwości koder można zapisać jako . Tutaj widmo słowa kodowego ma wartość w, ale wszystkie składniki w dziedzinie czasu pochodzą z . Ponieważ spektrum danych jest arbitralne, rolą jest określenie tych, w których będzie zero. ${\ Displaystyle n}$${\displaystyle c(x)}$${\displaystyle n-1}$${\ Displaystyle c (x) = a (x) g (x)}$${\ Displaystyle C_ {j} = A_ {j} G_ {j}}$ ${\displaystyle C_{j}}$${\ Displaystyle GF (q ^ {m})}$${\ Displaystyle GF (q)}$${\ Displaystyle A_ {j}}$${\ Displaystyle G_ {j}}$${\displaystyle j}$${\displaystyle C_{j}}$

Zatem kody cykliczne można również zdefiniować jako

Mając zestaw indeksów widmowych , których elementy nazywamy częstotliwościami kontrolnymi, kod cykliczny jest zbiorem słów, których widmo wynosi zero w składowych indeksowanych przez . Każde takie widmo będzie miało składowe postaci . ${\ Displaystyle A = (j_ {1}, ...., j_ {nk})}$ ${\displaystyle C}$ ${\ Displaystyle GF (q)}$ ${\displaystyle j_{1},...,j_{nk}}$ ${\displaystyle C}$ ${\ Displaystyle A_ {j} G_ {j}}$

Tak więc kody cykliczne są wektorami w polu, a widmo podane przez jego odwrotną transformatę Fouriera znajduje się nad polem i jest ograniczone do zera w pewnych składowych. Ale każde widmo w polu i zero na niektórych składnikach mogą nie mieć odwrotnych transformacji ze składnikami w polu . Takie widmo nie może być wykorzystywane jako kody cykliczne. ${\ Displaystyle GF (q)}$${\ Displaystyle GF (q ^ {m})}$${\ Displaystyle GF (q ^ {m})}$${\ Displaystyle GF (q)}$

Oto kilka ograniczeń w spektrum kodów cyklicznych.

BCH związany

Jeśli będzie czynnikiem dla niektórych . Jedynym wektorem o masie lub mniejszej, który ma kolejne składowe widma równe zero, jest wektor całkowicie zerowy. ${\ Displaystyle n}$${\ Displaystyle (q ^ {m}-1)}$${\ Displaystyle m}$${\ Displaystyle GF (q) ^ {n}}$${\displaystyle d-1}$${\displaystyle d-1}$

Hartmann-Tzeng związany

Jeśli być współczynnikiem dla niektórych i liczbą całkowitą, która jest względnie pierwsza z . Jedyny wektor z masy lub mniej, którego składowe widmowe są równe zero , w których a jest wektorem wszystkie zera. ${\ Displaystyle n}$${\ Displaystyle (q ^ {m}-1)}$${\ Displaystyle m}$${\displaystyle b}$${\ Displaystyle n}$${\displaystyle v}$${\ Displaystyle GF (q) ^ {n}}$${\displaystyle d-1}$${\ Displaystyle V_ {j}}$${\displaystyle j=\ell_{1}+\ell_{2}b(\mod n)}$${\displaystyle \ell_{1}=0,....,ds-1}$${\displaystyle \ell_{2}=0,....,s-1}$

Roos związany

Jeśli być czynnikiem dla niektórych i . Jedynym wektorem o masie lub mniejszej, którego składowe widmowe są równe zero dla , gdzie i przyjmuje co najmniej wartości z zakresu , jest wektorem całkowicie zerowym. ${\ Displaystyle n}$${\ Displaystyle q ^ {m} -1}$${\ Displaystyle m}$${\ Displaystyle GCD (n, b) = 1}$${\ Displaystyle GF (q) ^ {n}}$${\displaystyle d-1}$${\ Displaystyle V_ {j}}$${\displaystyle j=l_{1}+l_{2}b(\mod n)}$${\displaystyle l_{1}=0,...,ds-2}$${\displaystyle l_{2}}$${\displaystyle s+1}$${\displaystyle 0,....,d-2}$

Kwadratowe kody pozostałości

Gdy prim jest kwadratową resztą modulo prim, występuje kwadratowy kod reszty, który jest kodem cyklicznym o długości , wymiarach i minimalnej wadze co najmniej powyżej . ${\displaystyle l}$${\displaystyle p}$${\displaystyle p}$${\ Displaystyle (p + 1) / 2}$${\displaystyle {\sqrt {p}}}$${\ Displaystyle GF(l)}$

Uogólnienia

Constacyclic kod jest kodem liniowy właściwości, że dla pewnej stałej Î czy ( c ₁ , c ₂ , ..., c _n ), to słowo to tak jest (λ c _n c ₁ , ..., c _{n -1} ). Negacyclic kod jest constacyclic kod z λ = -1. Quasi cykliczny kod ma tę właściwość, że w przypadku niektórych s , każde przesunięcie cykliczne słowa kodowego przez y miejsc jest ponownie kodowym. Dwukrotnie kod circulant quasi-cykliczny kod nawet długości z S = 2.

Zobacz też

• Cykliczna kontrola nadmiarowości
• Kod BCH
• Reed-Muller kod
• Kod binarny Golay
• Trójskładnikowy kod Golay
• Eugeniusz Prange

Uwagi

Bibliografia

• Blahut, Richard E. (2003), Algebraic Codes for Data Transmission (2nd ed.), Cambridge University Press , ISBN 0-521-55374-1
• Hill, Raymond (1988), pierwszy kurs teorii kodowania , Oxford University Press , ISBN 0-19-853803-0
• MacWilliams, FJ ; Sloane, NJA (1977), Teoria kodów korekcji błędów , New York: North-Holland Publishing, ISBN 0-444-85011-2
• Van Lint, JH (1998), Wprowadzenie do teorii kodowania , Graduate Texts in Mathematics 86 (3rd ed.), Springer Verlag , ISBN 3-540-64133-5

Dalsza lektura

• Ranjan Bose , Teoria informacji, kodowanie i kryptografia , ISBN  0-07-048297-7
• Irving S. Reed i Xuemin Chen, Kodowanie kontroli błędów dla sieci danych , Boston: Kluwer Academic Publishers, 1999, ISBN  0-7923-8528-4 .
• Scott A. Vanstone , Paul C. Van Oorschot , Wprowadzenie do kodów korekcji błędów z aplikacjami , ISBN  0-7923-9017-2

Zewnętrzne linki

• Notatki z zajęć Johna Gilla (Stanford) – Notatki #3, 8 października, Handout #9 , EE 387.
• Notatki Jonathana Halla (MSU) – Rozdział 8. Kody cykliczne - s. 100 - 123
• David Terr. „Kod cykliczny” . MatematykaŚwiat .

Ten artykuł zawiera materiał z kodu cyklicznego na PlanetMath , który jest objęty licencją Creative Commons Attribution/Share-Alike License .