3

Kody cykliczne

3.1. Algebraiczne przedstawienie kodów cyklicznych

Kody cykliczne zostały wprowadzone po raz pierwszy przez Prange'a w roku 1957. Stanowią one najważniejszą klasę blokowych kodów liniowych. Wyodrębnienie ich, spośród innych kodów liniowych, wiąże się ściśle z wprowadzeniem zapisu wielomianowego ciągów oraz z zastosowaniem algebry wielomianów do analizy algorytmów kodowania i dekodowania. Definicja blokowego kodu cyklicznego jest związana z pojęciem cyklicznego przesunięcia ciągu. Niech będzie n-pozycyjnym ciągiem kodowym należącym do blokowego kodu liniowego (n,k). Cyklicznym przesunięciem tego ciągu o jedną pozycję w lewo nazywamy ciąg Ogólnie, cyklicznym przesunięciem n-pozycyjnego ciągu o j pozycji w lewo nazywamy ciąg

(3.1)

Na przykład cyklicznym przesunięciem ciągu

c = 0101100

o dwie pozycje w lewo jest ciąg

c⁽²⁾ = 0110001.

Opierając się na określeniu (3.1) kod cykliczny definiujemy w następujący sposób: zbiór {c} ciągów n-pozycyjnych jest zbiorem ciągów kodowych cyklicznego kodu (n,k), jeśli spełnione są następujące warunki:

(1) zbiór {c} jest grupą abelową względem operacji dodawania n-pozycyjnych ciągów;

(2) dla dowolnego zachodzi

(3.2)

W ogólnej teorii kodów liniowych n-pozycyjne q-narne ciągi traktuje się jako wektory w n-wymiarowej przestrzeni liniowej rozpiętej nad ciałem CG(q). W teorii kodów cyklicznych stosuje się odmienną interpretację. Wprowadza się mianowicie przekształcenie

, (3.3)

które ciągowi v przyporządkowuje w sposób wzajemnie jednoznaczny wielomian

(3.4)

Na przykład ciągowi v = (10111) odpowiada wielomian Istota kodów cyklicznych wiąże się jednak nie tyle z samym zapisem wielomianowym, co z wprowadzeniem nie stosowanych w ogólnej teorii kodów liniowych operacji mnożenia i dzielenia ciągów.

Zbadamy teraz algebraiczne właściwości binarnych kodów cyklicznych. Reprezentacja wielomianowa ciągu v przesuniętego cyklicznie o j pozycji w lewo ma postać

(3.5)

Ekwiwalentną operację cyklicznego przesunięcia możemy uzyskać w następujący sposób. Po pierwsze zauważmy, że wynik mnożenia wielomianu v(x) przez wielomian x^j wyraża się zależnością

, (3.6)

w której pierwsze j składników ma stopień wyższy niż (n - 1), a składniki o stopniu mniejszym niż j w ogóle nie występują. Zapiszmy (n - j) składników z potęgami od (n - 1) do j na początku prawej strony równania i uzupełnijmy je j składnikami o potęgach x od (j - 1) do 0. Równanie (3.6) przyjmie wówczas postać

(3.7)

przy czym

Podzielmy stronami równanie (3.7) przez wielomian

(3.8)

Cyklicznie przesunięty o j pozycji wielomian jest więc resztą z podziału wielomianu przez wielomian , co możemy formalnie zapisać w postaci

(3.9)

przy czym jest resztą z podziału [] przez f(x) modulo f(x).

Oznacza to, że jeżeli wielomian v(x) jest wielomianem kodowym, to jest także wielomianem kodowym dla dowolnego przesunięcia cyklicznego o j pozycji.

Przykład 3.1

Rozpatrzmy wielomian szóstego stopnia reprezentujący siedmiopozycyjne ciągi

Wielomian przesunięty o trzy pozycje w lewo (j = 3)

Iloczyn

możemy - po przekształceniach - sprowadzić do postaci

Iloczyn jest więc sumą ciągu przesuniętego o trzy pozycje w lewo oraz iloczynu wielomianu

Weźmy pod uwagę przykładowy ciąg ν =1011000, któremu odpowiada wielomian . Mamy więc:

Ciąg przesunięty o trzy pozycje w lewo ma postać odpowiada wielomian Ten sam wielomian otrzymamy obliczając resztę z podziału wielomianu przez wielomian

101

1011000000 : 10000001

10000001

11000100

10000001

1000101.

3.2. Kod cykliczny jako ideał wielomianów

Zbiór wielomianów {i(x)}, będący podgrupą addytywną grupy {z(x)} złożonej z wszystkich wielomianów stopnia mniejszego niż n, dla którego jest słuszna zależność

dla dowolnych , nazywamy ideałem wielomianów. W algebrze wielomianów modulo wielomian ideałem jest zbiór {i(x)} wszystkich wielomianów stanowiących wielokrotność pewnego wielomianu , będącego podzielnikiem wielomianu . Inaczej mówiąc, dla dowolnego wielomianu i(x) należącego do ideału zachodzi

(3.10)

przy czym wielomian musi spełniać równanie

(3.11)

Wielomian nazywamy generatorem ideału. W ideale wielomianów modulo wielomian

dowolne cykliczne przesunięcie wielomianu należącego do ideału jest elementem ideału, to znaczy dla dowolnego zachodzi

(3.12)

Korzystając z pojęcia ideału wielomianów, definicję kodu cyklicznego możemy sformułować następująco: zbiór {c(x)} wielomianów stopnia nie większego niż (n-1) o współczynnikach z ciała CG(q) jest równoważny zbiorowi ciągów kodowych q-narnego kodu cyklicznego (n,k), jeżeli dla dowolnego zachodzi

(3.13)

przy czym wielomian jest pewnym wielomianem monicznym, takim że

(3.14)

oraz

(3.15)

Jak widać, zbiór {s(x)} spełnia aksjomaty ideału, mówimy więc, że kod cykliczny jest ideałem w algebrze wielomianów modulo wielomian . Wielomian g(x) nazywamy wielomianem generującym kod cykliczny. Stopień wielomianu g(x) określa liczbę pozycji kontrolnych kodu, ponieważ istnieje dokładnie
wielomianów stopnia nie większego niż
(n - 1), które po podzieleniu przez wielomian g(x) dają w wyniku zbiór wszystkich możliwych wielomianów informacyjnych dla których zachodzi

3.3. Macierzowe przedstawienie kodów cyklicznych

Przyporządkujmy wielomianowi ciąg g; możemy wówczas macierz generującą kodu liniowego, równoważnego kodowi cyklicznemu generowanemu przez wielomian g(x), zapisać w postaci

(3.16)

przy czym oznacza ciąg przesunięty o j pozycji w prawo. Na przykład cyklicznym przesunięciem ciągu c = 0101100 o dwie pozycje w prawo jest ciąg c^(-2) = 0001011.

Kody cykliczne są kodami liniowymi, muszą więc istnieć dualne kody cykliczne. Jeśli {c(x)} jest zbiorem wielomianów kodowych kodu cyklicznego (n,k) generowanego przez wielomian g(x), a {v(x)} jest zbiorem wielomianów kodowych dualnego kodu cyklicznego (n,n-k) generowanego przez wielomian q(x), to warunek ortogonalności wielomianów c(x) i v(x) przybiera postać

(3.17)

Wielomian generujący cykliczny kod dualny określa zależność

(3.18)

a macierz kontrolna H równoważnego kodu liniowego (n,k) ma postać

(3.19)

przy czym q jest ciągiem odpowiadającym wielomianowi a wielomian tworzy się z wielomianu przez odwrócenie kolejności współczynników. Niech wielomian o odwróconej kolejności współczynników

ma postać Na przykład, jeśli Ciąg oznacza ciąg q przesunięty o j pozycji w prawo

Przykład 3.2

Rozpatrzmy kod cykliczny (7,4) generowany przez wielomian Ciąg g odpowiadający wielomianowi ma postać 1011000, stanowi on pierwszy wiersz macierzy generującej ten kod. Pozostałe wiersze znajdujemy dokonując - zgodnie ze wzorem (3.16) - cyklicznych przesunięć tego wiersza w prawo. Ostatecznie otrzymujemy

Wielomian generujący kod dualny obliczamy ze wzoru (3.18)

Wielomian o odwróconej kolejności współczynników

Ciąg q odpowiadający wielomianowi ma postać 1110100, zatem macierz kontrolna

Kod przedstawiony w przykładzie 3.2 nie jest kodem systematycznym. Macierz generującą systematyczny kod cykliczny można uzyskać z macierzy (3.16) przez doprowadzenie jej do postaci kanonicznej. Na przykład macierz z przykładu 3.2 można sprowadzić do postaci kanonicznej umieszczając w pierwszym wierszu sumę: I + II +II + III + IV, w drugim wierszu sumę: I + I + + II + IV i pozostawiając pozostałe wiersze bez zmian (liczby rzymskie oznaczają numery wierszy). Otrzymujemy wówczas

Formalnie macierz generującą systematyczny kod cykliczny możemy zapisać w postaci

przy czym u_i jest ciągiem odpowiadającym wielomianowi Dla kodu cyklicznego (7,4) generowanego przez wielomian mamy:

Otrzymujemy więc taką samą macierz generującą jaką uzyskaliśmy w wyniku dokonania operacji liniowych na wierszach macierzy z przykładu (3.2).

3.4. Skrócony kod cykliczny

Kody cykliczne istnieją tylko dla niektórych wartości n, na przykład:

(3.20) (3.21)

przy czym p jest liczbą pierwszą, a m - liczbą naturalną.

Jeśli dla zadanej długości ciągu kodowego n' nie istnieje kod cykliczny, to można - biorąc pod uwagę najbliższy kod cykliczny (n,k) z n > n' - skonstruować tak zwany kod pseudocykliczny, stosując procedurę skracania kodu (n,k). Polega ona na wybraniu do zbioru ciągów kodowych kodu pseudocyklicznego tylko takich ciągów kodowych kodu (n,k), które na pierwszych n - n' pozycjach mają zera, a następnie na ich usunięciu, nie ma bowiem potrzeby przesyłania zer, których położenie jest znane. Nazwa kodu pseudocyklicznego, zwanego również skróconym kodem cyklicznym, pochodzi stąd, że nie spełnia on warunku (3.2). Kod skrócony mas parametry [n',k-(n-n')] i odległość minimalną nie mniejszą od odległości minimalnej wyjściowego kodu cyklicznego (n,k).

Przykład 3.3

Skonstruujemy skrócony kod cykliczny (5,2) z kodu cyklicznego (7,4), generowanego przez wielomian Z szesnastu ciągów kodowych kodu (7,4) wybieramy cztery, które mają na pierwszych dwóch pozycjach zera. Pomijając te zera otrzymujemy skrócony kod cykliczny (5,2):

Kod (7,4)		Kod (5,2)
0000000	⇒	00000
1011000
0101100
0010110	⇒	10110
0001011	⇒	01011
1110100
1001110
1010011
0111010
0100111
0011101	⇒	11101
1100010
1111111
1000101
0110001
1101001

3.5. Kody BCH

Koncepcja kodów BCH opiera się na teorii ciał skończonych zwanych ciałami Galoisa. Dowolny wielomian stopnia m o współczynnikach z ciała podstawowego CG(p), nierozkładalny w tym ciele, rozkłada się (ma pierwiastki) w ciele rozszerzonym CG(p^m). Wielomian generujący kod (n,k) o długości można przedstawić w postaci iloczynu pewnych wielomianów pierwszych ^*) stopnia nie większego niż m

(3.22)

Wielomiany rozkładają się w odpowiednich ciałach CG(p^m'), przy czym a ponieważ ciała są podciałami ciał to dla dowolnego kodu cyklicznego (n,k) istnieje zawsze takie ciało Galoisa, które zawiera jako swoje elementy wszystkie pierwiastki wielomianu generującego g(x).

Przykład 3.4

Wielomian generujący kod cykliczny (7,4), rozkłada się całkowicie w ciele CG(2³), którego elementami są klasy reszt modulo wielomian Niezerowe elementy ciała CG(2³) tworzą grupę multiplikatywną, to znaczy mogą być przedstawione w postaci odpowiednich potęg pewnego elementu α, zwanego elementem pierwotnym. Przez podstawienie sprawdzamy, że α = x i α = x + 1 są elementami wielomianu p(x). Reprezentację omawianego ciała dla α = x przedstawiono w tabeli 3.1.

Tabela 3.1

Reprezentacja ciała CG(2³) generowanego przez wielomian pierwotny

Element ciała	Reprezentacja potęgowa	Reprezentacja wielomianowa					Reprezentacja binarna
a1	α			x			010
a2	α^2	x^2					100
a3	α^3			x	+	1	011
a4	α^4	x^2	+	x			110
a5	α^5	x^2	+	x	+	1	111
a6	α^6	x^2			+	1	101
a7	α^7 = α^0 =1					1	001
a8	nie istnieje					0	000

Przez podstawienie sprawdzamy, że Pozostałe pierwiastki g(x) znajdujemy biorąc pod uwagę fakt, że w ciałach o charakterystyce p dla dowolnego wielomianu zachodzi

(3.22)

*)Przez wielomian pierwszy rozumie się wielomian nierozkładalny w ciele CG(p)

Dla p = 2 słuszna jest zatem równość co oznacza, że pierwiastkami wielomianu generującego rozważany kod cykliczny są wielomiany:

Niech oznacza j-ty pierwiastek wielomianu g(x). Zbiór wszystkich pierwiastków jednoznacznie określa wielomian g(x), a więc i kod (z dokładnością do kodu ściśle równoważnego). Na podstawie znajomości zbioru można znaleźć macierz kontrolną H równoważnego kodu liniowego w następujący sposób. Z definicji a ponieważ ciągi kodowe są podzielne przez g(x), to dla dowolnego jest spełniony układ r równań liniowych

przy czym j = 1, 2, ..., r, (3.23)

kontrolnych kodu liniowego, danych zależnościami (2.34) i (2.35), testy kontrolne kodu cyklicznego różnią się tym, że ich wyniki są elementami ciała CG(p^m), a nie ciała CG(p). Każdy test typu (3.23) odpowiada więc de facto nie jednemu, lecz grupie m pojedynczych testów kontrolnych. Jednakże z sumarycznej liczby mr testów zadanych wyrażeniem (3.23) tylko r testów jest liniowo niezależnych, pozostałe (m - 1)r testów stanowią testy powtarzające się.

Macierzowy zapis równań (3.23) ma postać

(3.24)

przy czym

(3.25)

Po uwzględnieniu zależności (3.24) oraz faktu istnienia liniowych związków między niektórymi kolumnami macierzy A możemy napisać zależność

A ⇔ H^T (3.26)

Macierz H^T znajdujemy wykreślając w macierzy A kolumny liniowo zależne.

Przykład 3.5

Pierwiastkami wielomianu generującego rozważanego w przykładzie 3.4, są: macierz A ma zatem postać

Sprawdzamy, że kolumny IV - IX są liniowymi kombinacjami pierwszych trzech kolumn:

IV, VIII ⇔ I + II,

V ⇔ I,

VI, IX ⇔ III,

VII ⇔ II.

Po wykreśleniu tych kolumn otrzymujemy

Analizując przykład 3.5 łatwo spostrzec, że w przypadku rozpatrywanego kodu transponowana macierz kontrolna H^T jest zbudowana z potęg tylko jednego z pierwiastków wielomianu g(x), a mianowicie z potęg pierwiastka Prawidłowość tę można uogólnić w następujący sposób. Jeśli wielomian g(x) ma postać (3.22) i jednocześnie wszystkie wielomiany są różne, to do macierzy H^T należy włączyć tylko po jednym pierwiastku każdego wielomianu Podana zasada umożliwia skonstruowanie macierzy kontrolnej kodu cyklicznego na podstawie znajomości pierwiastków wielomianu generującego g(x). Zwraca uwagę fakt, że jeśli wielomian g(x) jest iloczynem co najmniej dwóch różnych wielomianów , to macierz H ma postać niekanoniczną.

Zastosowanie algebry wielomianów umożliwia konstruowanie takich efektywnych kodów cyklicznych jakimi są kody BCH. Kod BCH przekształca k-pozycyjne ciągi informacyjne (źródłowe) na n-pozycyjne ciągi kodowe. Możliwa jest konstrukcja kodu o zadanych parametrach. Kod korygujący t błędów oznaczamy symbolem BCH(n,k,t). Największe praktyczne znaczenie mają kody BCH zdefiniowane następująco.

Niech stanowi zbiór wielomianów stopnia nie większego niż n - 1 o współczynnikach z ciała podstawowego CG(p) oraz niech m, d i m₀ będą liczbami naturalnymi, takimi że: Jeśli wielomian ma jako kolejne pierwiastki d - 1 elementów ciała CG(p^m): to zbiór jest zbiorem ciągów kodowych p-narnego kodu BCH, którego odległość minimalna

Wielomian generujący kod BCH jest najmniejszą wspólną wielokrotnością (NWW) wielomianów minimalnych tych elementów ciała CG(p^m), które stanowią jego pierwiastki. Jeśli więc przez oznaczymy wielomian minimalny i-tego elementu ciała CG(p^m), to

(3.27)

Wielomiany minimalne wyznacza się z zależności

(3.28)

przy czym:

p(x) - wielomian pierwotny generujący ciało CG(p^m),

α - element pierwotny ciała CG(p^m),

λ_i - rząd i-tego elementu ciała CG(p^m).

Przykład 3.6

Znajdziemy wielomiany minimalne elementów ciała CG(2³) przedstawionego w tabeli 3.1. Wielomian ma jako pierwiastek więc

Wielomian jest tożsamościowo równy wielomianowi pierwotnemu, tzn. Pierwiastkami są: (na mocy zależności 3.22). Wielomiany i , jako wielomiany minimalne elementów i , są identyczne z .

Wielomian minimalny elementu ma jako pierwiastki również elementy i zatem

Wiadomo jednak, że wielomian ma trzy pierwiastki i musi być trzeciego stopnia, więc

Wielomiany i są identyczne z wielomianem .

3.5.1. Binarne kody BCH

Z binarnym kodem BCH mamy do czynienia wówczas, gdy symbole są określone w ciele pierwotnym CG(2), to znaczy mogą przyjmować wartości 0 lub 1. Długość ciągu kodowego n, zgodnie z zależnością (3.20) wynosi bitów. Liczba bitów ciągu kodowym określa ciało rozszerzone , którego elementami są pierwiastki wielomianu generującego kod. Wielomian generujący kod g(x) jest więc wielomianem o współczynnikach z ciała CG(2), mającym pierwiastki w ciele .

Oszacujemy liczbę r₁ pozycji kontrolnych binarnego kodu BCH z m₀ = 1. Kod taki ma nieparzystą odległość minimalną, wynoszącą przy czym t jest maksymalną krotnością błędów korygowanych przez kod. Wielomian generujący binarny kod BCH z m₀ = 1 ma postać

(3.29)

Dla binarnych kodów BCH zachodzi związek zatem wielomian jest iloczynem co najwyżej t różnych wielomianów minimalnych stopnia nie większego niż m. Prawdziwa jest więc nierówność

(3.30)

Podobne rozważania dla binarnego kodu BCH z prowadzą do następujących wyników:

(3.31)

oraz

(3.32)

Przykład 3.7

Skonstruujemy kod BCH korygujący dwa błędy (t = 2), przyjmując m = 4, to znaczy, że ciągi kodowe mają 15 pozycji (n = 15). Wielomian generujący g(x) ma pierwiastki w ciele Wielomiany minimalne elementów ciała CG(16) podano w tabeli D-1.9.

Stosownie do zależności (3.27), wielomian generujący kod korygujący dwa błędy musi mieć cztery kolejne pierwiastki w ciele CG(16), przyjmując , otrzymujemy

(3.33)

Wielomian generujący jest wielomianem ósmego stopnia, to znaczy r = n - k = 8, a więc
k = 7. Skonstruowany kod odwzorowuje zatem 7-pozycyjne ciągi informacyjne na 15-pozycyjne ciągi kodowe i może korygować do dwóch błędów. Kod ten oznacza się symbolem BCH(15,7,2).

Przykład 3.8

Skonstruujemy kod BCH korygujący trzy błędy. Podobnie jak w przykładzie 3.7 przyjmiemy 15-pozycyjne ciągi kodowe (m = 4) i m₀ = 1. Wielomian generujący kod ma - zgodnie ze wzorem (3.31) - postać

(3.34)

Wielomian generujący jest wielomianem dziesiątego stopnia, tak więc ciąg kodowy zawiera dziesięć pozycji kontrolnych, co umożliwia korekcję trzech błędów. Liczba pozycji informacyjnych wynosi 5. Skonstruowany kod oznaczymy symbolem BCH(15,5,3).

3.5.2. Niebinarne kody BCH

W przypadku niebinarnych kodów BCH symbole pochodzą z ciała CG(p), przy czym p > 2. Współczynniki wielomianu generującego są również niebinarne i są elementami ciała CG(p). Długość bloku, zgodnie z zależnością (3.20) wynosi symboli i liczba ta określa ciało rozszerzone . Wielomian generujący kodu jest określony nad ciałem CG(p) i ma pierwiastki w ciele rozszerzonym .

Przykład 3.9

Skonstruujemy ternarny kod BCH, dla którego m = 2 i d = 6. Biorąc pod uwagę, że p = 3, otrzymujemy

a ze względu na parzystość d

m₀=0 ^*).

Postać wielomianu generującego określamy na podstawie zależności (3.27)

Reprezentację ciała CG(3²) generowanego przez wielomian pierwotny przedstawiono w tabeli 3.2.

Tabela 3.2

Reprezentacja ciała CG(3²) generowanego przez wielomian

Element ciała	Reprezentacja potęgowa	Reprezentacja wielomianowa			Reprezentacja ternarna
a1	α	x			10
a2	α^2	2x	+	1	21
a3	α^3	2x	+	2	22
a4	α^4			2	02
a5	α^5	2x			20
a6	α^6	x	+	2	12
a7	α^7	x	+	1	11
a8	α^8 = α^0 =1			1	01
a9	nie istnieje			0	00

Zgodnie z zależnością (3.28) poszczególne wielomiany minimalne mają jako pierwiastki następujące elementy ciała CG(3²):

:

:

:

:

:

*) Dla wielomianów o współczynnikach z ciała CG(p) słuszne jest twierdzenie: wielomian o parzystej liczbie składników jest podzielny przez wielomian x - 1; stąd kody BCH o parzystej odległości minimalnej muszą mieć m₀=0

Wielomiany minimalne:

Wielomian generujący omawiany kod ma więc postać

a kod oznaczamy symbolem BCH(8,2,2).

Macierz generująca i macierz kontrolna równoważnego kodu liniowego mają postać:

Zbiór ciągów kodowych:

Wszystkie ciągi niezerowe mają wagę sześć, kod ma zatem rzeczywiście odległość minimalną
d_min = 6 i może skorygować dwa błędy.

3.5.3. Wielowartościowe kody BCH

Gorenstein i Zierler podali uogólnienie p-narnych (p - liczba pierwsza) kodów BCH na przypadek q-narny, przy czym a c jest liczbą naturalną. Słowna definicja q-narnego kodu BCH jest następująca:

Niech stanowi zbiór wielomianów stopnia nie większego niż n - 1 o współczynnikach z ciała oraz niech m, d i m₀ będą pewnymi liczbami naturalnymi, takimi że:

Jeśli dowolny wielomian ma jako pierwiastki kolejne d - 1 elementów ciała : , to zbiór jest zbiorem wielomianów kodowych
q-narnego kodu BCH o długości . Przedstawiona definicja wielowartościowego kodu BCH różni się od podanej w p. 3.5 definicji p-narnego kodu BCH tylko różnym sposobem zdefiniowania elementu pierwotnego α, który jest bądź elementem pierwotnym ciała ,

bądź ciała . Wspólną definicję p-narnych i q-narnych kodów BCH można więc przedstawić w postaci układu d - 1 równań liniowych

(3.35)

Przykład 3.10

Skonstruujemy wielowartościowy kod BCH, którego czterowartościowe symbole są określone w ciele CG(4), tzn. p = 2, c = 2, q = 4. Wybierzmy m = 2, a więc ciągi kodowe mają długość Wielomian generujący ten kod, określony nad ciałem CG(4), ma pierwiastki w ciele rozszerzonym CG(4²) = CG(16). W tabeli 3.3 pokazano decymalną reprezentację operacji dodawania i mnożenia w ciele CG(4); odpowiada ona tablicom dodawania i odejmowania przedstawionym w D-1.1.4.

Tabela 3.3

Tablice arytmetyczne dla ciała CG(4) - reprezentacja decymalna

+	0	1	2	3			•	0	1	2	3
0	0	1	2	3			0	0	0	0	0
1	1	0	3	2			1	0	1	2	3
2	2	3	0	1			2	0	2	3	1
3	3	2	1	0			3	0	3	1	2

Wielomiany minimalne nad ciałem CG(4) wszystkich elementów ciała CG(16) podano
w tabeli 3.5.

Tabela 3.4

Wielomiany minimalne elementów ciała CG(16)

Pierwiastki sprzężone	Wielomiany minimalne
0			x
α^0			x	+	1
α^1, α^4	x^2	+	x	+	2
α^2, α^8	x^2	+	x	+	3
α^3, α^12	x^2	+	3x	+	1
α^5			x	+	2
α^6, α^9	x^2	+	2x	+	1
α^7, α^13	x^2	+	2x	+	2
α^10			x	+	3
α^11, α^14	x^2	+	3x	+	3

Określimy w pierwszej kolejności wielomian generujący kod korygujący dwa błędy. Wielomian ten musi mieć cztery kolejne pierwiastki w ciele CG(16), to znaczy

Wielomian generujący jest wielomianem szóstego stopnia, tzn. w ciągu kodowym jest sześć symboli kontrolnych i dziewięć symboli informacyjnych. Skonstruowaliśmy więc

wielowartościowy kod BCH (15,9,2). Kod może skorygować do dwóch czterowartościowych błędów w ciągu kodowym o długości 15 czterowartościowych symboli.

Zbadamy teraz jak zmieni się postać wielomianu generującego, jeśli zażyczymy sobie, aby kod korygował trzy błędy. Wielomian generujący musi mieć więc sześć kolejnych pierwiastków w ciele CG(16), a zatem

Ten wielomian generuje wielowartościowy kod BCH o parametrach (15,6,3). Kod umożliwia korekcję do trzech czterowartościowych błędów w ciągu kodowym o długości 15 czterowartościowych symboli.

3.5.4. Kody BCH generowane przez elementy niepierwotne rozszerzonego ciała Galoisa

Kody BCH, dla których są spełnione równania (3.35), noszą nazwę kodów generownych przez elementy pierwotne rozszerzonego ciała Galoisa. Nazwa pochodzi stąd, że pośród elementów
znajduje się zawsze przynajmniej jeden element pierwotny.

Istnieją również kody, w których pierwiastkami wielomianu generującego są wyłącznie elementy niepierwotne. Kody te, zwane kodami BCH generowanymi przez niepierwotne elementy rozszerzonego ciała Galoisa, są zdefiniowane równaniami:

(3.36)

przy czym:

- niepierwotny element ciała rozszerzonego,

- rząd elementu
.

Przykładem binarnego kodu BCH generowanego przez niepierwotne elementy rozszerzonego ciała
jest kod Golaya. Niech oznacza element pierwotny ciała
, wówczas
, a ponieważ
, to również
. Wprowadźmy oznaczenie
, otrzymujemy wówczas cykliczną multiplikatywną podgrupę ciała
, złożoną z następujących 23 elementów:
. Kod Golaya otrzymuje się biorąc jako wielomian generujący g(x) wielomian minimalny elementu
, to znaczy
. W zależności od wyboru wielomianu p(x), generującego ciało
, otrzymuje się dwie alternatywne postacie wielomianu generującego kod Golaya:

, (3.37a)

. (3.37b)

Oba wielomiany są jedenastego stopnia, tzn. że liczba pozycji kontrolnych (r) w kodzie Golaya wynosi 11. Oba wielomiany generują kod Golaya o parametrach (23,12).

Pierwiastkami wielomianów generujących kod Golaya są cztery kolejne potęgi elementu , a mianowicie:
. Stosując kryteria przyjęte do oceny odległości minimalnej kodów BCH, można by sadzić, że kod Golaya ma odległość minimalną . Okazuje się jednak, że przypadku kodu Golaya oszacowanie to jest pesymistyczne. Kod Golaya osiąga bowiem kres górny Hamminga dla t = 3, co oznacza, że jego odległość minimalna wynosi . Jest to jedyny istniejący kod liniowy o , który jest kodem idealnym.

Zauważmy, że kody BCH generowane przez elementy pierwotne mogą być formalnie traktowane jako szczególny przypadek kodów BCH generowanych przez elementy niepierwotne, gdyż po podstawieniu w równaniach (3.36) j = 1, otrzymujemy równania (3.35).

3.5.5. Kody Reeda-Solomona

Kody Reeda-Solomona stanowią szczególny przypadek niebinarnych kodów BCH. Definicję kodu Reeda-Solomona (RS), generowanego przez element ciała CG(q) możemy sprowadzić do równań o postaci

(3.38)

przy czym d_min jest odległością minimalną kodu, a n - długością ciągów kodowych.

Wartość n określa zależność

(3.39) w której NWP(a,b) jest największym wspólnym podzielnikiem liczb a i b.

Inaczej mówiąc, n jest rzędem elementu będącego (podobnie jak elementy z nim sprzężone) pierwiastkiem wielomianu generującego kod RS. Dla j = 1 spełniona jest równość n = q -1, dlatego kody RS istnieją tylko dla q > 2. Liczba elementów kontrolnych w ciągu kodowym RS wynosi r = d_min - 1.

Przykład 3.11

Dla q = 4 istnieje ciało CG(4), w którym operacje dodawania i mnożenia są zadane następującymi tablicami (α - jest elementem pierwotnym tego ciała):

+	0	1	α	α^2			•	0	1	α	α^2
0	0	1	α	α^2			0	0	0	0	0
1	1	0	α^2	α			1	0	1	α	α^2
α	α	α^2	0	1			α	0	α	α^2	1
α^2	α^2	α	1	0			α^2	0	α^2	1	α

Skonstruujemy systematyczny kod RS przyjmując: Dla tego kodu:
n = 3 i r = 2. Równania kodu mają postać

l = 0, 1.

Jawna postać równań kodu jest następująca:

(l = 0);

(l = 1).

Po rozwiązaniu tych równań względem pozycji kontrolnych c₁ i c₂, otrzymujemy:

Pełny zbiór ciągów kodowych skonstruowanego kodu RS(3,1) przedstawia się następująco:

0 0 0 1 α² α α 1 α² α² α 1.

W reprezentacji decymalnej α = 2, α² = 3. Ciągi kodowe mają zatem postać:

0 0 0 1 3 2 2 3 1 3 2 1.

Zauważmy, że wszystkie niezerowe ciągi kodowe są cyklicznymi przesunięciami jednego ciągu, skonstruowany kod RS jest więc rzeczywiście kodem cyklicznym.

Określimy jeszcze postać wielomianu generującego omawiany kod. Zgodnie z definicją, pierwiastkami g(x) muszą być następujące elementy ciała CG(4): α⁰ = 1 oraz α, zatem

3.6. Kody Fire'a

Kod Fire'a jest to kod cykliczny generowany przez wielomian o postaci

(3.40)

przy czym p(x) jest wielomianem pierwotnym stopnia m, a c - liczbą naturalną nie podzielną przez rząd λ pierwiastków rozkładu wielomianu p(x) w ciele CG( 2^m).

Długość ciągu kodowego jest najmniejszą wspólną wielokrotnością liczb λ i c

n = NWW(λ, c), (3.41)

a liczba pozycji informacyjnych wynosi

k = n - m - c. (3.42)

Kod Fire'a jest typowym kodem zabezpieczającym przed błędami seryjnymi o następujących właściwościach detekcyjno-korekcyjnych:

• wykrywa wszystkie pojedyncze serie błędów o długości nie większej niż m + c;

• wykrywa dwie serie błędów o długościach l₁ i l₂, spełniających warunki:

koryguje krótszą z tych serii.

Kod Fire'a z parametrem c = 0 staje się cyklicznym kodem Hamminga (kodem BCH z m₀ = 1 i t = 1).

Przykład 3.12

Rozpatrzmy kod Fire'a generowany przez wielomian
Mamy: c = 13, m = 6, λ = 63, n = cλ =819, r = m + c = 19.

Kod może korygować serię błędów o długości l₁ nie przekraczającej 6 i jednocześnie wykrywać drugą serią błędów o długości lub wykrywać pojedyncze serie błędów o długości nie przekraczającej 19.

3.7. Kodowanie za pomocą kodów cyklicznych

Reguła kodowania za pomocą kodów cyklicznych jest bardzo prosta, wielomian kodowy s(x) uzyskuje się w wyniku przemnożenia wielomianu informacyjnego h(x) przez wielomian generujący kod g(x):

(3.43)

Ta reguła kodowania daje w wyniku kod niesystematyczny. Uzyskanie systematycznego kodu cyklicznego zapewnia następująca reguła kodowania

. (3.44)

Zasadność tej reguły z następującego rozumowania. Podzielmy przez g(x)

(3.45)

przy czym r(x) jest resztą z dzielenia przez g(x).

Po pomnożeniu stronami równania (3.45) przez g(x) otrzymujemy

(3.46)

stąd

. (3.47)

Wielomian kodowy musi być podzielny przez wielomian generujący kod g(x). Iloczyn
a(x) g(x) jest - oczywiście - podzielny przez g(x), może zatem reprezentować ciąg kodowy c przyporządkowany ciągowi informacyjnemu h.

W przypadku kodów binarnych reguła (3.44) przyjmuje postać

(3.48)

Przykład 3.11

Znajdziemy ciąg kodowy kodu (15,10), generowanego przez wielomian odpowiadający ciągowi informacyjnemu h = 1000100101.

Wielomian informacyjny ma postać . Zgodnie z wzorem (3.48) mnożymy ten wielomian przez , uzyskujemy wówczas , otrzymany iloczyn dzielimy przez wielomian generujący g(x):

1110001111

100010010100000 : 110101

110101

101110

110101

110111

110101

100100

110101

100010

110101

101110

110101

110110

110101

11 (reszta).

Po dodaniu uzyskanej reszty x + 1 do iloczynu otrzymujemy wielomian kodowy

,

której odpowiada ciąg kodowy

c = 100010010100011.

Operację kodowania przedstawiono graficznie na rysunku 3.1.

Rys. 3.1. Przykład tworzenia ciągu kodowego systematycznego kodu cyklicznego:

ciąg informacyjny h(x) przesuwa się o pięć pozycji w lewo, co odpowiada mnożeniu

wielomianu informacyjnego przez x^r = x⁵, a następnie dopisuje ciąg 00011

odpowiadający reszcie z podziału wielomianu przez wielomian generujący kod

3.8. Koder kodów cyklicznych

Algorytm kodowania kodem cyklicznym opiera się na dzieleniu wielomianów. Do dzielenia dowolnego wielomianu (dzielna) przez ustalony wielomian (dzielnik) stosuje się rejestr przesuwający ze sprzężeniem zwrotnym. Schemat ogólny układu do dzielenia przez wielomian pokazano na rysunku 3.2.

Rys. 3.2. Układ do dzielenia dowolnego wielomianu przez wielomian g(x); współczynniki dzielnika

są zaszyte w układzie sprzężenia zwrotnego.

Działanie układu do dzielenia wielomianów wyjaśnimy na przykładzie układu do dzielenia dowolnego wielomianu przez wielomian , którego schemat pokazano na rysunku 3.3.

Rys. 3.3. Układ do dzielenia dowolnego wielomianu przez wielomian

Niech dzielna ma postać Kolejne etapy dzielenia przedstawiono w tabeli 3.1.

Na początku rejestr jest wyzerowany, a na wejście podaje się najbardziej znaczący element dzielnej. Po impulsie taktującym wartość ta zostanie wpisana do pierwszej komórki rejestru P₀ rejestru przesuwającego, a na wejściu pojawi się drugi element dzielnej. W następnych taktach układ działa podobnie. Po pięciu taktach rozpoczyna się właściwy proces dzielenia. W kolejnych taktach stan wyjścia rejestru jest sumowany z zawartością drugiej (P₁) i czwartej (P₃) komórki rejestru i przesuwany o jedną komórkę w prawo. Po piętnastu taktach dzielenie jest zakończone. W taktach od 6. do 15. na wyjściu układu pojawiają się kolejne elementy ilorazu. W omawianym przykładzie jest to ciąg 1110001111, któremu odpowiada wielomian W rejestrze znajduje się reszta z dzielenia 00011, której odpowiada wielomian x + 1. Zauważmy, że ciąg w rejestrze jest zapisany w odwrotnej kolejności. Uzyskany rezultat jest identyczny z wynikiem dzielenia na papierze przedstawionym w przykładzie 3.11.

Tabela 3.1.

Działanie układu dzielącego z rysunku 3.3

(We + P₄ → P₀; P₀ → P₁; P₁ + P₄→ P₂; P₂ → P₃; P₃ + P₄→ P₄)

Takt	Wejście	Zawartość rejestru					Wyjście
		P0	P1	P2	P3	P4
1	1	0	0	0	0	0	0
2	0	1	0	0	0	0	0
3	0	0	1	0	0	0	0
4	0	0	0	1	0	0	0
5	1	0	0	0	1	0	0
6	0	1	0	0	0	1	1
7	0	1	1	1	0	1	1
8	1	1	1	0	1	1	1
9	0	0	1	0	0	0	0
10	1	0	0	1	0	0	0
11	0	1	0	0	1	0	0
12	0	0	1	0	0	1	1
13	0	1	0	0	0	1	1
14	0	1	1	1	0	1	1
15	0	1	1	0	1	1	1
		1	1	0	0	0

Ogólny schemat kodera systematycznego kodu cyklicznego pokazano na rysunku 3.4. Koder zawiera r-komórkowy rejestr przesuwające. W układzie sprzężenia zwrotnego zaszyte są współczynniki z ciała CG(q) wielomianu generującego kod : Przed rozpoczęciem procesu kodowania rejestr jest wyzerowany. W pierwszych k taktach kodowania klucze K₁ i K₂ są w pozycji1. Ciąg informacyjny (k symboli) jest przekazywany wprost na wyjście kodera, tworząc pierwszych k pozycji ciągu kodowego.

Pierwszy symbol ciągu informacyjnego jest sumowany z zawartością komórki P_r-1, mnożony w ciele CG(q^m) przez współczynnik i umieszczany w rejestrze P. Zawartość tego rejestru mnoży się przez współczynnik , dodaje w ciele CG(q^m) do zawartości komórki P_r-2 i umieszcza w komórce P_r-1. Nową zawartość komórki P_r-2 stanowi suma iloczynu zawartości rejestru P przez współczynnik i zawartości komórki P_r-3. Podobne mnożenia i dodawania przeprowadza się w celu uzyskania nowych zawartości komórek od P_r-3 do P₀. Po wprowadzeniu na wejście kodera drugiego symbolu informacyjnego powtarza się cykl mnożeń i sumowań w celu uzyskania nowego zbioru symboli kontrolnych. Tak się postępuje aż do k-tego kroku kodowania. Po tym kroku klucze K₁ i K₂ zostają przełączone do pozycji 2. Dane z wejścia nie przedostają się już na wyjście kodera, zostaje również przerwane sprzężenie zwrotne. Zawartość rejestru przesuwającego (symbole kontrolne) jest podawana na wyjście kodera.

Rys. 3.4. Ogólny schemat kodera systematycznego kodu cyklicznego

generowanego przez wielomian

Przykład 3.12

Pokażemy przykładowo działanie kodera systematycznego kodu cyklicznego (15,10), generowanego przez wielomian . Schemat kodera pokazano na rysunku 3.5. Na początku klucze K₁ i K₂ są w pozycji 1. Załóżmy, że ciąg informacyjny ma postać h = 1000100101, której odpowiada wielomian informacyjny . W pierwszym takcie współczynnik 1 przy x⁹ wielomianu informacyjnego jest wprowadzany na wejście kodera. Odpowiada on współczynnikowi przy
wielomianu kodowego kodu systematycznego, jest więc z jednej strony bezpośrednio przekazywany na wyjście kodera. Z drugiej strony jest on sumowany modulo dwa z zawartością komórki
(0) rejestru przesuwającego; wynik sumowania (1) jest zapamiętywany w komórce P. Zawartość komórki P jest sumowana z zawartością komórek
i przesuwana o jedną komórkę w prawo oraz podawana na wejście rejestru (komórka
). W kolejnych taktach cykl ten powtarza się. Po dziesięciu taktach w rejestrze znajduje się reszta z podziału wielomianu
przez wielomian generujący
. Następuje teraz przełączenie kluczy
i
do pozycji 2, co powoduje przerwanie sprzężenia zwrotnego i wyprowadzenie zawartości rejestru na wyjście kodera. W ten sposób w ciągu piętnastu taktów na wyjściu kodera pojawia się ciąg kodowy. Rejestr zostaje wyzerowany i koder jest przygotowany do przyjęcia następnego ciągu informacyjnego. Pracę kodera podczas kodowania ciągu informacyjnego h = 1000100101 pokazano w tabeli 3.6.

Rys. 3.5. Schemat kodera systematycznego kodu cyklicznego (15,10), generowanego przez

wielomian

Tabela 3.6

Stany rejestru kodera systematycznego kodu cyklicznego (15,10),
generowanego przez wielomian

Takt	Wejście	Stan komórek rejestru											Wyjście
		P	P	P	P	P	P
		0	0	0	0	0	0
1	1	1	1	0	1	0	1	1
2	0	1	1	1	1	1	1	0
3	0	1	1	1	0	1	0	0
4	0	0	0	1	1	0	1	0
5	1	0	0	0	1	1	0	1
6	0	0	0	0	0	1	1	0
7	0	1	1	0	1	0	0	0
8	1	1	1	1	1	1	1	1
9	0	1	1	1	0	1	0	0
10	1	1	1	1	0	0	0	1
11			0	1	1	0	0	0
12			0	0	1	1	0	0
13			0	0	0	1	1	0
14			0	0	0	0	1	1
15			0	0	0	0	0	1

D. J. Bem, Kody cykliczne 2

Daniel Józef Bem, Kody cykliczne 48

---