2. Cykliczny kod Reeda - Solomona

2.1 Wielomian generujący kodu RS.

Cykliczny kod Reeda-Solomona zaliczamy do podklasy niebinarnych kodów BCH (Bose-Chaudhuri-Hocauenghema), umożliwiają one korekcję błędów grupowych. Błędy grupowe, zwane inaczej seryjnymi, mogą powstać w skutek działania osoby trzeciej lub podczas transmisji informacji w kanałach telekomunikacyjnych. Jednak ten drugi rodzaj błędów występuje bardzo rzadko. Wynika to dużej niezawodności łącz i nośników danych.

Błąd seryjny jest sekwencją błędów obejmującą pewną liczbę kolejnych pozycji, której pierwszy i ostatni element są elementami niezerowymi. Na przykład:

Jeśli wektor błędu ma postać: 00011111001110110000100000000000,

to błąd grupowy ma długość 18 : 00011111001110110000100000000000.

Kody korygujące błędy losowe, stosowane powszechnie w kanałach komunikacyjnych, nie są w stanie skorygować błędów grupowych. Skonstruowano więc kody, które z takim problemem są w stanie sobie poradzić. W kodach tych wymaga się, aby w przypadku, gdy konieczne jest skorygowanie pewnej ilości błędów grupowych b, liczba elementów kontrolnych wektora kodowego kodu (n,k) wynosi przynajmniej 2b.

b - oznacza liczbę błędów,

n - długość wektora kodowego,

k - długość wektora nadmiarowego.

Jeśli liczba elementów kontrolnych wektora kodowego k jest równa 2b, to zostanie i górna granica zdolności korekcyjnej kodu korygującego błędy grupowe. Mamy do czynienia wtedy z tak zwanym kodem optymalnym, a wartość zależności:

Jednak gdy chcemy aby kod wykrywał i korygował b błędów, wymagane jest, aby liczba elementów kontrolnych wektora kodowego wynosiła przynajmniej b + 1. Zalezność zmieni postać na :

Kod Reeda-Solomona należy właśnie do tego typu kodów i wykorzystywany jest do korekcji błędów grupowych oraz losowych zawierających się w długości wektora nadmiarowego. Kod Reeda-Solomona (n,k) nad ciałem GF(q) charakteryzuje się następującymi parametrami:

• Długość wektora kodowego n = q -1

• Liczba pozycji kontrolnych r = n - k

• Odległość minimalna d = r + 1

Zdolność korekcyjną kodu RS określa poniższa zależność:

gdzie t oznacza największą liczbę całkowitą nie większą od
.

W niniejszej pracy dyplomowej kod Reeda-Solomona został skonstruowany nad ciałem GF(256). W tym przypadku każdy z elementów ciała GF(256) odpowiada mu z symboli tablicy kodów ASCII. Długość wektora informacyjnego przyjęto jako W związku z tym, parametry tego kodu są następujące:

• Długość wektora kodowego n = 255,

• Liczba pozycji kontrolnych r = 130,

• Odległość minimalna d = 131,

• Zdolność korekcyjna r = 65.

Wielomian generujący kod g(x) jest takim wielomianem, który dzieli bez reszty każdy wielomian należący do zbioru wektorów kodowych danego kodu. Dodatkowo stopień tego wielomianu jest taki sam, jak liczba elementów kontrolnych wektora kodowego. Wynika z tego, iż wielomianem generującym kod cykliczny (także kod Reeda-Solomona) może być dowolny wielomian, który jest podzielnikiem xⁿ + 1, przy czym n = q^m - 1, a m jest liczbą naturalną.

W przypadku kodów Reeda-Solomona wielomiany generujące kody RS wyznacza się w następujący sposób. Jako element pierwotny ciała GF(q) przyjmuje się α. Zbiór {f(x)} jest zbiorem ciągów kodowych kodu Reeda-Solomona, jeśli pierwiastkami dowolnie wybranego wielomianu f(x) są elementy dała a,a², a³,..., a^r. Wtedy wielomian generujący kod RS nad ciałem charakterystyki dwa ma postać:

Dla kodu RS (255,125) nad ciałem GF(256) - kod ten został zaimplementowany w programie dołączonym do tej pracy dyplomowej - wielomian generujący kod wygląda następująco:

Wielomian g(x) jest stopnia 130, co odpowiada liczbie symboli nadmiarowych k wektora kodowego.

Procedura generowania wygląda następująco:

procedure RSgen(r:Byte);

var

gi, gj, gg, da, db, dc: Byte;

pa, pb, pc: array [0..255] of Byte;

procedure Multpoly(dga, dgb: Byte; var dgc: Byte);

var

im, jm: Byte;

begin

dgc:=dga+dgb;

for im:=0 to dgc do pc[im]:=0;

for im:=dga downto 0 do

for jm:=dgb downto 0 do

begin

pc[im+jm]:=S(pc[im+jm], P(pa[im], pb[jm]))

end

end;

begin

da:=1; pa[1]:=1; pb[0]:=1; db:=0; gg:=1;

for gi:=1 to r do

begin

gg:=P(gg, 2);

pa[0]:=gg;

Multpoly(da, db, dc);

db:=dc;

for gj:=dc downto 0 do pb[gj]:=pc[gj]

end;

for gj:=0 to dc do pg[gj]:=pc[gj]

end; {RSgen}

---