2.2 Procedura kodowania kodu RS

Algorytm kodowania za pomocą kodu Reeda-Solomona jest taki sam jak inne algorytm kodowania jak dla innych kodów cyklicznych. Istnieją dwie możliwości kodowania. Pierwszą jest wykorzystanie wielomianu generującego kod, natomiast drugą jest macierz generująca kod. W niniejszej pracy dyplomowej została zastosowana pierwsza z metod tzn. wielomian generujący kod.

Wielomian informacyjny m(x) przyjmuje postać,

natomiast wielomian generujący kod jest stopnia r, gdzie r = n - k, wyznacza się ze wzoru:

Poszczególne operacje algorytmu wyglądają następująco:

1. Na wstępie obliczamy wielomian generujący kodu:

,

2. Odczytujemy wektor zawierający tekst jawny do zakodowania,

3. Następnie mnożymy wielomian informacyjny m(x) przez wielomian x^n-k otrzymując w ten sposób wielomian postaci

x^n-k m(x)

4. Kolejno dzielimy wyznaczonego wielomianu x^n-k m(x) przez wyznaczony wcześniej wielomian generujący kod Reeda-Solomona g(x) i wyznaczenie reszty r(x) z tego dzielenia.

Resztę oblicza się ze wzoru:

gdzie q(x) jest częścią całkowitą, natomiast r(x) jest resztą z tego dzielenia,

Wielomian reszty to ma postać:

5. Ostatnim krokiem jest wyznaczenie wektora kodowego kodu RS:

Wektor kodowy ma postać:

gdzie współrzędne m, są elementami informacyjnymi, natomiast współrzędne r, są elementami kontrolnymi.

Algorytmu powtarzamy tak długo, aż dla wszystkich odebranych bloków informacyjnych wyznaczymy kolejne wektory kodowe C_x(x). Liczba kroków zależy od rozmiaru kodowanej informacji oraz od wielkości bloków, na które dzielona jest kodowana informacja. Jeżeli ostatni blok informacyjny jest krótszy od założonej wielkości k, uzupełniany jest do odpowiedniej wielkości.

W przypadku niniejszej pracy dyplomowej wielomian informacyjny m(x) jest stopnia 125, a wielomian generujący kod g(x) jest stopnia 130. W związku z tym każdy .informacji, na który będzie dzielona kodowana informacja będzie miał rozmiar 125, każdy wektor kodowy C_x(x) będzie miał rozmiar 255, z czego pierwsze 125 elementów będzie informacją a pozostałe 130 będzie elementami kontrolnymi.

Schemat poglądowy algorytmu:

Procedura wykonująca kodowanie :

Obliczenie wielomianu generującego kod RS

Odczyt wektora wiadomości

Wyznaczamy wektor nadmiarowy, na podstawie wielomianu generującego

Sumujemy wektor wiadomości i wektor nadmiarowy

Otrzymujemy wektor o sumie długości obu wektorów

Tu następuje proces szyfrowania, który będzie omówiony dalej.

procedure Encode(n, r: Byte);

var

i, j, vv: Integer;

begin

for j:=-1 to r-1 do v[j]:=0;

for i:=n downto r do

begin

vv:=S(v[i], v[r-1]);

for j:=r-1 downto 0 do

v[j]:=S(v[j-1], P(pg[j], vv))

end

end; {Encode}

---