Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

1.Wstęp

Koniec dwudziestego wieku cechuje się dynamicznym rozwojem techniki, a w szczególności techniki komputerowej, oraz spokrewnionych z nią systemów teleinformatycznych, takich jak np. telefonia komórkowa, czy też telewizja satelitarna. Jednakże największy rozwój technologiczny dotyczy Intemetu. Obecnie każdego dnia ludzkość przesyła siecią miliony bajtów informacji, zarówno tej ważnej jak i całkowicie bezużytecznej.

Dlatego też, bardzo ważną rzeczą jest, aby te informacje były chronione zarówno przed błędami mogącymi powstać podczas transmisji danych, magazynowania w bankach informacji, czy też przed nieuprawnionym dostępem innych osób do informacji dla nich nie przeznaczonych. Metodami i zagadnieniami związanymi z ochroną danych zajmuje się teoria kodowania i kryptografii.

Dziedzina ta ma już dość długą historię, gdyż pierwsze prace związane z teorią kodowania i kryptografii zostały przedstawione pod koniec lat 40 dwudziestego wieku, przez Claude'a Shannona, uważanego obecnie za iniq'atora teorii informacji. W swojej pracy pt. „Teoria informacji" wykazał w sposób teoretyczny, iż jeśli w dowolnym kanale transmisyjnym szybkość transmisji jest mniejsza od pojemności tego kanału to można tak zakodować informację, aby możliwe było przesłanie jej z dowolnie małym prawdopodobieństwem wystąpienia błędów. Wkrótce potem Hamming skonstruował swój kod, który umożliwiał korekcję pojedynczych błędów. Kod ten był nie tylko piawszy, który mógł korygować błędy, ale i też pierwszym kodem blokowym (tzn. kodem, który operował na /(-elementowych blokach, na które dzielono informację). W latach 1959 i 1960 doszło do kolejnego postępu w dziedzinie kodowania informacji. Wtedy właśnie, niezależnie od siebie najpierw Hocquenghem, a wkrótce potem Bose i

Strona 4

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

Ray Chaudhuri, odkryli klasę kodów blokowych (BCH) umożliwiających korygowanie wielu błędów. Do wyżej wymienionej trójki dołączyli także Reed i Solomon, którzy skonstruowali swój kod należący do podklasy kodów BCH. Kod Reeda-Solomona w przeciwieństwie jednak do kodu BCH operuje na symbolach nie binarnych.

Prawdziwy rozwój nastąpił jednak dopiero około roku 1980, kiedy to pojawiły się komputery osobiste dostępne dla powszechnego użytku. Dzięki szybkiemu rozwojowi sprzętu komputerowego możliwy stał się szybki rozwój nowoczesnych metod kryptograficznych oraz korekcyjnych. W pierwszym przypadku wykorzystuje się teorię liczb, natomiast w przypadku kodów korekcyjnych wszystko opiera się na algebrze ciał skończonych. W związku z tym konieczne są duże nakłady obliczeniowe, którym może podołać jedynie szybki komputer.

Obecnie, nie tylko w wojsku, ale praktycznie w każdej sieci teleinformatycznej stosuje się systemy kryptograficzne. Podobnie jest z resztą z teorią kodów korekcyjnych. Stosowanie kodów korekcyjnych w procesie nagrywania płyt kompaktowych, aby jak najbardziej zminimalizować występujący szum i zakłócenia, czy też w transferze danych pomiędzy komputerami lub satelitami jest przykładem na to, iż dziedzina kodowania i kryptografii w najbliższej przyszłości jeszcze bardziej się rozwinie i znajdzie zastosowanie w wielu innych dziedzinach życia. Kody korekcyjne nie są może jeszcze stosowane w takim stopniu jak metody kryptograficzne, ale z pewnością wkrótce to się zmieni. Stanie się tak między innymi, dlatego, iż kody korekcyjne umożliwiają zwiększenie niezawodności i odporności systemów informatycznych na wszelkiego rodzaju zakłócenia, błędy, które mogą się pojawić podczas transmisji. Co prawda stosowanie kodów korekcyjnych wiąże się ze wzrostem objętości danych, jednakże możliwość korekcji ewentualnie powstałych błędów warta jest takiego zabiegu, tym bardziej, iż obecnie następuje szybki rozwój nośników danych, pamięci, a także zwiększa się przepustowość kanałów transmisyjnych. W związku z tym szybkie przesyłanie nawet dużych pakietów informacji, już wkrótce nie powinno być problemem.

Strona 5

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

2. Temat i cel pracy dyplomowej

Niniejsza praca dyplomowa składa się z dwóch części, części teoretycznej i części praktycznej. W pierwszej części zawarta została krótka charakterystyka kodów korekcyjnych, a w szczególności kodów Reeda-Sotomona. Opisany został sposób tworzenia ciała rozszerzonego GF(256), wyznaczania tablic mnożenia i dodawania w dele rozszerzonym GF(256), konstrukcji wielomianu generującego kod jak również przedstawiony został algorytm kodowania oraz dekodowania dla kodów cyklicznych.

Na część praktyczną pracy składa się program, przy pomocy, którego można zakodować i zdekodować dowolną informację. Aplikacja wykorzystuje do tego celu kod Reeda-Solomona, który pozwala wykryć i skorygować ewentualnie powstałe błędy czy przekłamania.

Program ten został napisany z myślą, aby można go było wykorzystać jako pomoc dydaktyczną do wykładów z przedmiotów związanych z teorią kodowania. Dzięki temu studenci będą mogli zaobserwować na przykładzie cyklicznego kodu Reeda-Solomona działanie kodów korekcyjnych, ich mocne i słabe strony.

Sama „sucha" teoria z wykładów na pewno nie przyniesie takiego skutku jak dodatkowe zobrazowanie jej przykładami oraz ukazanie jej praktycznego zastosowania. Studenci oraz inne osoby zainteresowane teorią kodowania informacji będą mogły wykorzystać program stworzony na potrzeby niniejszej pracy dyplomowej do pogłębienia swojej wiedzy o korekcyjnych kodach cyklicznych, a w szczególności ladach Reeda-Sotomona.

Strona 6

l realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

W rozdziale zatytułowanym „Kody korekcyjne" przedstawiona została krótka tefystyka tego typu kodów. Opisane zostały rodzaje na jakie dzielą się kody flne, struktura kodu blokowego oraz najczęściej stosowane obecnie w (rafii kody cykliczne.

Rozdział „Kod Reeda-Solomona nad GF(256)' zawiera ogólne informacje o ;h Reeda-Solomona, omawia sposoby tworzenia ciała rozszerzonego GF(256),

dodawania i mnożenia w tym ciele oraz wyznaczania wielomianu generującego zny kod Reeda-Solomona. W rozdziale tym opisane zostały także algorytmy wania i korekcji błędów.

W rozdziale opisującym program, przedstawiony został sposób w jaki nentowano poszczególne procedury wchodzące w skład aplikacji. Od procedur dzialnych za utworzenie ciała rozszerzonego GF(256) po procedury realizujące i kodowania i dekodowania.

Ostatni rozdział stanowią wnioski wynikłe z realizacji pracy, spostrzeżenia oraz b podsumowanie przebiegu pracy dyplomowej.

W dodatku A znajduje się instrukcja obsługi aplikacji wchodzącej w skład pracy ^ oraz krótki opis poszczególnych funkcji zawartych w programie.

Strona 7

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

3. Kody korekcyjne

3.1. Wstęp

Kodowanie informacji jest to wzajemnie jednoznaczne przyporządkowanie elementów zbioru informacyjnego elementom zbioru sygnałów. Dzięki temu możliwa jest transmisja informacji poprzez kanał transmisyjny lub też zapisanie jej w pamięciach. Tak, wiec, kodowanie jest niczym innym jak tylko zbiorem zakodowanych informacji, wykorzystywanych do kompresji, szyfrowania bądź przedstawienia informacji w formie odpornej na błędy.

Kody korekcyjne są kodami, które stosuje się w przypadkach, gdy wymagane jest, aby przesyłana informacja była odporna na wszelkiego rodzaju błędy, jakie mogą wystąpić w systemach transmisyjnych bądź też w pamięciach. Dzięki zastosowaniu kodów korekcyjnych umożliwiających wykrycie, a także korekcję błędów zwiększa się niezawodność systemów informatycznych.

W systemach informatycznych informacje są przesyłane jako sygnały cyfrowe w lpeqalnych kanałach zwanych kanałami transmisji danych. Na sygnał przesyłany kanałami telekomunikacyjnymi oddziaływują różne zakłócenia, które mogą spowodować pizektemania i błędy w przesyłanej informacji. Aby tego uniknąć lub chociażby zminimalizować skutki zakłóceń stosuje się kody korekcyjne.

Do zwykłego systemu transmisji danych, dodaje się wtedy koder i dekoder. ptoder oczywiście odpowiada za przekształcenie przesyłanej informacji w dag kodowy, będzie zawierał dodatkową informację umożliwiającą późniejsze skorygowanie ^ch błędów. Umieszcza się go pomiędzy źródłem danych a łączem riyrn. Rolą dekodera jest natomiast odebranie transmitowanego ciągu

Strona 8

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania__

kodowego, wykrycie i skorygowanie ewentualnie powstałych podczas transmisji błędów, a następnie przekazanie do wyjścia danych, skorygowanej informacji.

Schemat ogólny cyfrowego systemu komunikacyjnego przedstawiony jest

poniżej.

Informacja nadana (źródło danych)

KODER

Kanał transmisji danych

Modulator

Zakłócenia Kanał transmisyjny

Demodulator

DEKODER

Informacja odebrana (ujście danych)

Rys. 1. Schemat blokowy systemu transmisyjnego z podsystemem korekcyjnym

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

3.2. Rodzaje kodów korekcyjnych

Podstawowym kryterium podziału kodów korekcyjnych na poszczególne typy, jaki się stosuje do ich rozróżnienia, jest podział według sposobu kodowania informacji. Można rozróżnić dwa typy kodów korekcyjnych: kody blokowe i kody rekurencyjne, zwane również kodami splotowymi.

Kody blokowe wymagają, aby dag informacyjny został podzielony na k-etementowe bloki. Liczba bloków na które dzielona jest informacja zależy od przyjętej wielkości bloku, a także rozmiaru informacji. Następnie na każdym bloku, niezależnie od innych bloków dokonuje się operacji kodowania. Podczas kodowania do każdego bloku informacji dołączana jest sekwencja kontrolna, umożliwiająca późniejsze wykrycie i korekcję ewentualnych błędów.

W przypadku kodów splotowych (rekurencyjnych), nie dzieli się informacji na bloki, a kodowanie odbywa się na bieżąco, w takt napływania informacji. Elementy kodu są uzależnione od bieżącego elementu informacji oraz od pewnej liczby elementów poprzednich.

Innym sposobem podziału kodów korekcyjnych na klasy, jest podział na kody liniowe i kody cykliczne. Zarówno kody liniowe jak i cykliczne spełniają warunek liniowości, tzn. suma dwóch dowolnych wektorów kodowych daje wektor należący do zbioru wektorów kodowych tego kodu. Kody te jednak różnią się od siebie konstrukcją i strukturą matematyczną. Do budowy kodów liniowych wykorzystuje się grupy adoytywne i wektorowe przestrzenie liniowe, natomiast do konstrukcji kodów cyklicznych stosuje się pierścienie wielomianów nad datami skończonymi.

Obecnie najczęściej wykorzystywanymi w praktyce typami kodów są kody cykliczne. Wynika to miedzy innymi z faktu, iż skonstruowanie tego typu kodów w porównaniu z innymi, jest stosunkowo nie skomplikowane, a do tego daje całkiem dobre efekty.

Strona 10

Programowa realizacja kodu Reeda-Sotomona nad GF(256) z uproszczoną metodą dekodowania

3.3. Struktura kodu blokowego

Zastosowanie kodu blokowego do operacji kodowania informacji, wymaga podziału tejże informacji na bloki /("elementowe. Powstaje w ten sposób ciąg n-elementowy, gdzie n > k. Ciąg ten nazywa się wektorem kodowym lub słowem kodowym, a n oznacza długość kodu.

W przypadku kodów blokowych stosuje się oznaczenie (n,k), gdzie n jest długością wektora kodowego, a k liczbą elementów bloku. Wektor kodowy zawiera k elementów informacyjnych i n-k elementów kontrolnych, zwanych inaczej nadmiarowymi. Na rysunku nr 2 przedstawiona jest struktura wektora kodowego.

k

n

-k

n Rys. 2. Wektor kodu blokowego (n,k)

W części nadmiarowej wektora kodowego przechowywana jest dodatkowa informacja, która umożliwia późniejszą korekcję błędów transmisyjnych. Niestety wiąże aę z tym pewne utrudnienie, a mianowicie wzrost objętości przesyłanej informacji. W związku z tym stosuje się współczynnik zwany sprawnością kodu (code ratę), który umożliwia ocenę względnej długości części informacyjnej wektora kodowego. Współczynnik ów wyraża się wzorem:

R=k/n

Jest to stosunek liczby znaków wprowadzonych do kodera k do liczby znaków wyjściowych kodera n.

Kody blokowe, w których elementy informacyjne są możliwe do odróżnienia od lllimontów kontrolnych są kodami systematycznymi.

Strona 11

Programowa realizaqa kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

3.4. Kody cykliczne

Kody cykliczne dzięki swoim właściwością stały się kodami, które są obecnie najczęściej wykorzystywanymi w praktyce. Głównymi cechami, które przesądziły o dużej popularności kodów cyklicznych są: stosunkowo prosta realizacja koderów i dekoderów za pomocą rejestrów przesuwnych ze sprzężeniem zwrotnym oraz możliwość ich konstrukcji z wykorzystaniem do tego metod algebraicznych.

Ciągi informacyjne oraz ciągi kodowe przedstawiane są w postaci wielomianów, a właściwości kodów opisuje się za pomocą pierścieni wielomianów i ciał Galois.

Główną cechą kodów cyklicznych jest możliwość przesunięcia ich cyklicznie. Kod (n,k) jest kodem cyklicznym, gdy każdy z wektorów kodowych

^c = k-i^-a.-.^o]

po Mym przesunięciu cyklicznym da wektor

^c. = [^a»-^-i^,^-„...^a^a,_„a^...,a^}

któiy także będzie należał do zbioru wektorów kodowych tego kodu.

Wektor kodowy c przedstawia się w postaci wielomianu

c{x} = a^x"~¹ + a^x"~² +... + a^x + a^x

Jeśli c(x) jest wielomianem kodowym stopnia n-1, to reszta z dzielenia x'c(x) przez wielomian x"-1 jest również wektorem kodowym tego kodu.

a Wielomianem generującym kod cykliczny może być każdy wielomian, który jest zielnikiem )("+•!, gdzie /?=</"-1, a m jest liczbą naturalną.

Strona 12

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

4. Kod Reeda-Solomona nad GF(256)

4.1. Charakterystyka kodów Reeda-Solomona

Kody Reeda-Solomona należą do podklasy niebinarnych kodów BCH (Bose-Chaudhuri-Hocauenghema) umożliwiających korekcję błędów grupowych. Błędy grupowe, zwane inaczej seryjnymi, mogą powstać podczas transmisji informacji w kanałach informacyjnych na skutek zakłóceń impulsowych, a także w pamięciach, gdzie przyczyną może być uszkodzenie nośnika magnetycznego.

Błąd grupowy jest sekwencją błędów obejmującą b kolejnych pozycji, której pierwszy i ostatni element są elementami niezerowymi. W przypadku wektora błędu (0011101100110000] błąd grupowy jest długości 10. Kody korygujące błędy losowe 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 b błędów grupowych, liczba elementów kontrolnych wektora kodowego kodu (n,k) wynosNa przynajmniej 2b.

n-k>2b \ b oznacza liczbę błędów grupowych.

Jeśli liczba elementów kontrolnych wektora kodowego jest równa 2b, to zostanie i górna granica zdolności korekcyjnej kodu korygującego błędy grupowe.

Strona 13

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

Wtedy kod taki nazywa się kodem optymalnym gdyż z = 1, a wynika to z zależności:

2b

n-k

Jeśli jednak kod powinien poza korygowaniem b błędów, także wykrywać / błędów, wymagane jest, aby liczba elementów kontrolnych wektora kodowego wynosiła przynajmniej b + f

n-k^b+l

Kod Reeda-Solomona należy właśnie do tego typu kodów i wykorzystywany jest do korekcji błędów grupowych i losowych.

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ść:

/=

d-\

2

d-\

oznacza największą liczbę całkowitą nie większą od (d - 1) / 2.

W niniejszej pracy dyplomowej kod Reeda-Solomona został skonstruowany nad l GP[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 /?= 255

Strona 14

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

• Liczba pozycji kontrolnych r= 130

• Odległość minimalna d = 131

• Zdolność korekcyjna r = 65

4.2. Wykonywanie działań w ciele 256-elementowym

Do konstrukcji kodów cyklicznych, a co się z tym wiąże także kodów Reeda-Solomona stosuje się pierścienie wielomianów nad ciałami skończonymi. Wielomian stopnia m nad ciałem GF(q) ma ogólną postać

p(x) = ^a,x' = a^x"' + a^"-¹ +... +a,x + a, ;»o

przy czym a, e GF(q).

Dozwolone jest jednak zapisywanie wielomianu w postaci ciągu współczynników. Taki sposób zapisywania wielomianu jest bardzo wygodny, dzięki czemu jest bardzo często wykorzystywany w praktyce. Zapisany w ten sposób wielomian nad ciałem GF(256) może mieć np. postać jak poniżej:

1 O O a³⁴ a¹²⁵ a¹⁹ 11 a⁶ gdzie a jest elementem algebraicznym tego ciała. l Odpowiada on wielomianowi x⁸ + a³^⁵ + a¹²^⁴ + a¹^³ + x² + x + a⁶

Ciała skończone nad którymi konstruuje się kody cykliczne, w tym kody Reeda-są rozszerzeniami stopnia m ciał prostych GF(p). Liczba elementów q ciała iego GF(q) nad ciałem prostym GF(p) wynosi q = ff" . Parametr m jest to '. Stopień rozszerzenia. W przypadku ciała GF(256) użytego do konstrukcji kodu te-Sotomona w niniejszej pracy dyplomowej wartość owego parametru m wynosi 8, dato GF(256) jest rozszerzeniem 8 stopnia ciała GF(2).

Strona 15

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

Do skonstruowania ciała GF(256), które wykorzystane zostanie później do wyznaczenia tabliczek mnożenia i dodawania, stosuje się wielomiany pierwotne. Dzięki temu niezerowe elementy ciała rozszerzonego można przedstawić jako potęgi elementu pierwotnego a. Dla ciała rozszerzonego GF(256) będą one następujące:

254

0,1, a,'a², a³,a⁴,a⁵,a⁶,..., a'

Element pierwotny a jest pierwiastkiem wielomianu pierwotnego.

Aby wyznaczyć tablicę mnożenia dała GF(256) należy obliczyć dla kolejnych elementów ciała ich iloczyny. Do tego celu należy wykorzystać postać multiplikatywną elementów ciała skończonego i wyznaczyć iloczyn korzystając ze wzoru

a'-^ ^a'^^^

^iSK^i^l;

aa

m.

w&

iii

im

liii

lii

B"'S

Iii

iiti

il||t

^

^

^

0

0

0

0

0

0

0

0

0

0

0

0

0

Ifr®

0

1

a

a^2

a^3

a^4

a^5

a^249

a^250

a^251

a^252

a^

a^254

0

a

a^2

a^3

a^4

a^5

a^6

a^260

a^251

a^262

a^253

a^

1

SK^^w^

0

a^2

a^3

a^4

a^5

a"

^

a^251

a^252

a^263

a^254

1

a

vS»iiiS'f^

0

a^3

a^4

a^5

a^6

a^7

a^8

a^252

a^253

a^264

1

a

a^2

B

0

a^4

a^5

a^6

a^7

a^8

a^9

a^283

a^254

1

a

a^2

a^3

0

a^5

a^6

a^7

a^8

a^6

a^10

a^254

1

a

a^2

a^3

a^4

0

a^249

„250

a^261

a^252

a^

a^254

...

a^

a^244

a^

a^246

a^2^

a^24"

0

^

a^251

a^252

a^253

a^254

1

a^244

a^245

a^24"

a^247

a^248

a^2^

0

a^251

a^252

a^255

a^254

1

a

a^245

a^246

a^2^

a^248

a^249

a^250

l °

a^262

a^253

a^254

1

a

a^2

a^246

a^2^

a^248

a^249

a^260

a^261

I °

a^

a^254

1

a

a^2

a^3

a^247

a^248

a^

a^^0

a^261

a^252

I °

a^254-

1

a

a^2

a^3

a^4

a^248 .

a^249

a^250

a^251

a^252 . .. .- -

a^

Rys. 3. Fragment tablicy mnożenia ciała GF(256)

Strona 16

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

Na rys. 3 pokazano fragment tablicy mnożenia ciała GF(256).

Z tablicą dodawania ciała GF(256) sprawa Jest już dużo bardziej skomplikowana i złożona. Pierwszym krokiem w skonstruowaniu takiej tablicy jest przedstawienie poszczególnych elementów ciała GF(256) w postaci addytywnej. Elementy te można przedstawić w postaci wektorowej, wielomianowej lub macierzowej.

Najbardziej wygodną metodą przedstawienia elementów ciała GF(256), biorąc pod uwagę konstruowanie ciała rozszerzonego metodami programowymi jest metoda wektorowa. W tym wypadku, aby skonstruować wektorową postać elementów ciała skończonego GF(256) wykorzystuje się sekwencję pseudolosową generowaną przez wielomian pierwotny służący do konstrukcji ciała rozszerzonego.

Wielomiany pierwotne należą do klasy wielomianów nierozkładalnych, czyli takich które nie dzielą się przez żaden wielomian o stopniu większym od zera i mniejszym od m. Niestety odróżnienie wielomianów rozkładalnych od nierozkładalnych nad danym ciałem jest dość trudne, dlatego najczęściej znajduje się takie wielomiany w odpowiednich tablicach. Dla ciała GF(256) jednym z takich wielomianów pierwotnych | JBBtwfetomian postaci:

P(

x)=x^s+x⁴+x³+x²+l.

Znając wielomian pierwotny wyznacza się z zależności rekurencyjnej sekwencję wą. Wzór na zależność rekurencyjną, stowarzyszoną z wielomianem i p(x), w przypadku tej pracy dyplomowej ma postać:

^sj+& ^{= S}J• ^{+ S}J-^2 ^{+ s}j+3 ^{+ s}j+4

W związku z tym, iż wielomian pierwotny jest stopnia 8, każdy wektor będzie ił się z 8 współrzędnych. Za wektor zerowy przyjmuje się wektor składający się z . Następnie przyjmując za wektor początkowy wektor postaci f 1 O O O O O O O ] i z zależności rekurencyjnej wyznacza się kolejne wektory. W ten sposób

Strona 17

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

wyznaczamy wszystkie elementy rozszerzenia ciała w postaci wektorowej. Poniżej przedstawione są wszystkie wektory (256) wchodzące w skład ciała GF(256).

0=(00000000] a³³=['^ 1 1 001 00] a⁶⁷ = [ O 1 00 00 1 1 ] a¹⁰¹ = [ 0 1 0 0 0 1 0 0 ]

1 =[10000000] a³⁴ =[01110010] a⁶⁸ =[10011001] a¹⁰² =[00100010]

a=[01000000] a^tOOI 1 1 001 ] a⁶⁹ = t 1 1 1 1 0 1 0 0 ] a^o3= [000 1 000 1 ]

a² =(00 100000] a³⁶ =[10100100] a⁷⁰ =[01111010] a¹⁰⁴ =[10110000]

a^IOOOlOOOO] a^tOI 01 001 0] a⁷¹ = [ 00 1 1 1 1 0 1 ] a^^ [O 1 0 1 1 000]

a⁴ =[000 01000] a³⁸ =[00101001] a⁷² =[10100110] a¹⁰⁶ =[00101100]

a''=t00000100] a^UOI 01 1 00] a⁷³ = [01 0 1 00 1 1 ] 0"= [000 1 0 1 1 0]

a'^00000010] a^tOI 01 01 1 0] a⁷⁴ = [ 1 00 1 000 1 ] a¹⁰^ (0000 1 0 1 1 ]

a^lOOOOOOOI] a^lOOI 01 01 1] a⁷⁵ = [ 1 1 1 1 0000] a⁰⁹^ [ 1 0 1 1 1 1 0 1 ]

a^llOI 1 1000] a^=[1 01 01 1 01 ] a⁷⁶ = [0 1 1 1 1 000] 0.^°= [ 1 1 1 00 1 1 0 ]

^=101011100] a⁴³=[) 1 1 01 1 1 0] (/^[OO-I 1 1 1 00] a¹¹¹ =[0 1 1 1 00 1 1 ]

a'^100101 1 10] a^l4=[0^ 1 101 1 1 ] a⁷⁸ = (000 1 1 1 1 0] a"^ [ 1 0 00000 1 ]

a"=(000101 1 1) a^n 000001 1 } a⁷⁹ = [0000 1 1 1 1 ] a¹¹^ [ 1 1 1 1 1 000]

a^'1101 1001 1 ] a^M 1 1 1 1 001 ] a⁸⁰=['^ 01 1 1 1 1 1 ] a^= [ 0 1 1 1 1 1 0 0 ]

a"=t11100001] a⁴⁷^ 1 0001 00] a⁸¹ = [ 1 1 1 00 1 1 1 ] a¹¹⁵ = [00 1 1 1 1 1 0]

iy^ii 1001000] a⁴⁸ =[01100010] a⁸² =[11001011] a¹¹⁶ = [ O 00 1 1 1 1 1 ]

|a"=(01100100] a^tOOI 10001] a⁸³ = [ 1 1 0 1 1 1 0 1 ] a¹"^ [ 1 0 1 1 0 1 1 1 ]

Sa^tOOllOOlO] a⁵⁰=[1 01 00000] a⁸⁴^ [ 1 1 0 1 0 1 1 0 ] a^⁸ = (1 1 1 000 1 1 ]

S^lOOOllOOll a^IOlOlOOOO] a⁸⁵ = [O 1 1 O 1 O 1 1 ] a^lllOOlOOI}

|il''=(10110100] a^tOOI 01 000] a⁸⁶=[1 0001 1 01 ] a^ = [ 1 1 0 1 1 1 0 0 ]

p^stOlOI 1010] a^IOOOI 01 00] a⁸⁷ = [ 1 1 1 1 1 1 1 0] a¹²¹ = [ 0 1 1 0 1 1 1 0]

'•100101101] a^tOOOOI 01 0] a⁸⁸ = (0 1 1 1 1 1 1 1 ] a²²= [O O 1 1 0 1 1 1 ]

*»(10101 1 10] a^tOOOOOI 01 ] a⁸⁹ = [ 1 0 00 0 1 1 1 ] a¹²³ = [ 1 0 1 0 0 0 1 1 ]

'"[0101011 1] a^nOI 1 101 0] a^H 1 1 1 101 1 ] a²⁴ = [ 1 1 1 0 1 00 1 ]

""(1001001 1] a^rOI 01 1 1 01 ] a^M 1 0001 01 ] a¹²¹^ (1 1 00 1 1 00]

|«l111 1 0 0 0 1 ] a⁵⁸ = [ 1 0 0 1 0 1 1 0 ] a⁹² = [ 1 1 0 1 1 0 1 0 ] a¹²⁶ =[ 0 1 1 0 0 1 1 0 ]

|«(11000000] a^IOl 001 01 1 ] a⁹³ = [0 1 1 0 1 1 0 1 ] a¹²⁷^ [00 1 1 0 0 1 1 ]

|«(01100000] a^MOOI 1 1 01 ] a^ [ 1 000 1 1 1 0] a¹²¹^ [ 1 0 1 00 00 1 ]

|r(00110000] ot⁶¹^ 1 1 1 01 1 0] a^^OI 0001 1 1 ] a¹²^ [ 1 1 1 0 1 000]

»(00011000] a^tOI 1 1 101 1] a^H 001 1 01 1 ] a¹³^ [ O 1 1 1 0 1 00 ]

K[fl0001100] a^tl 00001 01 ] a⁹⁷ = [ 1 1 1 1 0 1 0 1 ] a¹³¹ = [ 0 0 1 1 1 0 1 0 ]

KIOOOOOHO] a^M 1 1 1 101 0] a^ [ 1 1 0000 1 0] a¹³^ [000 1 1 1 0 1 ]

||0000001 1] a^tOI 1 1 1 1 01 ] a"=[01 1 00001 ] a¹³³ = [ 1 0 1 1 0 1 1 0 ]

|10111001] a⁶⁶ =[10000110] a¹⁰⁰ =[10001000] a¹³^ [O 1 0 1 1 0 1 1 ]

Strona 18

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

i¹³⁵ =[10010101] a¹⁶⁵ =[10001001] a¹⁹⁵ =[00100110] a²²⁵ =[00100100]

a

J36

t¹³⁶ =[11110010] a¹⁶⁶ =[11111100] a¹⁹⁶ =[00010011] a²²⁶ =[00010010]

(^[Ol 1 1 1001 ] a^tOI 1 1 1 1 1 0] a^MOI 10001] a²²^ [ 0 0 0 0 1 0 0 1 ]

a¹³⁷ = l u i i l i u u i J a

a¹³⁸ =[10000100] a¹⁶⁸ =(00111111] a¹⁹⁸ =[11100000] a²²⁸ =[10111100]

a¹³⁹ =[01000010] a¹⁶⁹ =[10100111] a¹⁹⁹ =[01110000] a²²⁹ =[01011110]

a¹⁴⁰ =[00100001] a¹⁷⁰ =[11101011] a²⁰⁰ =[00111000] a²³⁰ =[00101111]

a¹⁴¹ =[10101000] a¹⁷¹ =[11001101] a²⁰¹ =[00011100] a²³¹ =[10101111]

a^w=[ 01010100] a¹⁷²^ 1 01 1 1 1 0] a²⁰² = [0000 1 1 1 0] a²³^ [ 1 1 1 0 1 1 1 1 ]

a¹⁴³ =[00101010] a¹⁷³ =[01101111] a²⁰³ =[00000111] a²³^ [ 1 1 00 1 1 1 1 ]

(^[OOOI 01 01 ] a¹⁷⁴^! 0001 1 1 1 ] a²⁰^ [ 1 0 1 1 1 0 1 1 ] a²³^ [ 1 1 0 1 1 1 1 1 ]

a¹⁴⁵^ 101 10010] a⁷⁵=l'^ 1 1 1 1 1 1 1 ] a²⁰⁵ = (1 1 1 00 1 0 1 ] a²³⁵^ 1 1 0 1 0 1 1 1 ]

(^[O 101 1001 ] a¹⁷⁶^ 1 0001 1 1 ] a²⁰^ [ 1 1 0 0 1 0 1 0 ] a²³^ [ 1 1 0 1 0 0 1 1 ]

a^tlOOI 01 00] a¹⁷⁷^ 1 01 1 01 1 ] a²⁰⁷ = [0 1 1 00 1 0 1 ] a²³¹^ [ 1 1 0 1 000 1 ]

a^OlOOI 01 0] a¹⁷⁸^ 1 01 01 01 ] a²⁰^ [ 1 0 00 1 0 1 0] a²³⁸ = [ 1 1 0 1 00 0 0]

a'^ [ 00100101 ] a¹⁷⁹^ 1 01 001 0] a²⁰⁹ = [O 1 000 1 0 1 ] 0^= [0 1 1 0 1 000]

a¹⁸⁰ =[ 0 1 1 0 1 0 0 1 ] a²¹⁰ =[10011010] a²⁴⁰ =[00110100]

a¹⁸¹ =[10001100] a²¹¹ =[01001101] a²⁴¹ =[00011010]

a¹⁸² =[ 0 1 0 0 0 1 1 0 ] a²¹² =[10011110] a²⁴² =[ 0 0 0 0 1 1 0 1 ]

a¹⁸³ = [ 0 0 1 0 0 0 1 1 ] a²¹³ =[01001111] a²⁴³ =[ 1 0 1 1 1 1 1 0 ]

a¹⁸⁴ =( 1 0 1 0 1 0 0 1 ] a²¹⁴ =[10011111] a²⁴⁴ =[ O 1 0 1 1 1 1 1 ]

a¹⁸⁵ = [ 1 1 1 0 1 1 0 0 ] a²¹⁵ =[11110111] a²⁴⁵ =[ 1 0 0 1 0 1 1 1 ]

a¹⁸⁶ =[ 0 1 1 1 0 1 1 0 ] a²¹⁶ =[11000011] a²⁴⁶ =[11110011]

a¹⁸⁷ =[001 1 101 1 ] a^w=[^ 1 01 1 001 ] a²" •=- [ 1 1 00000 1 ]

a¹⁸⁸ =[ 1 0 1 0 0 1 0 1 ] a²¹⁸ =[11010100] a²⁴⁸ =[11011000]

a⁸⁹ = [ 1 1 1 0 1 0 1 0 ] a²¹⁹ = [ O O 1 1 O 1 O 1 ] a²⁴⁹ =[ O 1 1 O 1 1 O O ]

a⁹⁰ =[01110101] a²²⁰ =[00110101] a²⁵⁰ =[00110110]

a¹⁹¹ =[10000010] a²²¹ =[10100010] a²⁵¹ =[00011011]

a¹⁹² =[01000001] a²²² =[01010001] a²⁵² =[10110101]

a¹⁹³ =[10011000] a²²³ =[10010000] a²⁵³ =[11100010]

a^tOI 001 1 00] a²²⁴ =[01001000] a²⁵⁴ =[01110001]

f wyznaczone są już wszystkie elementy ciate w postaci wektorowej,
się tablicę dodawania. Robi się to poprzez zsumowanie kolejnych elementów

34

Ct^+a¹⁰ =[01011100]+[00101110]=[01110010]=a

Strona 19

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

Następnie sprawdza się jakiemu elementowi dała odpowiada dany wektor i zapisuje się go w odpowiednie miejsce w tabeli. W ten sposób tworzy się całą tablicę dodawania.

4.3. Obliczanie wielomianu generującego kod RS

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 = (f - 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ę a. 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'. Wtedy wielomian flenerujący kod RS nad dałem charakterystyki dwa ma postać

g(x)=Y[{x+a')^{x+a\x+a²\..(x+a^{^}) 1=1

Dla kodu RS (255,125) nad ciałem GF(256) - kod ten został zaprogramowany w qi wchodzącej w skład tej pracy dyplomowej - wielomian generujący kod wygląda ujaco:

130

_____ g(x)=Y\(x+aⁱ)=(x+a)(x+a²)...(x+a^w)

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

Strona 20

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

4.4. Algorytm kodowania

Do kodowania informacji za pomocą kodu Reeda-Solomona wykorzystuje się taki sam 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ć,

m(x) = w^_iJC*"¹ + m^_^x^t~² +... + m^x + m^

natomiast wielomian generujący kod wyznacza się ze wzoru:

g(x)=Y^(x+aⁱ)=(x+a)(x+a²)...(x+a^r)

Wielomian taki jest stopnia r, gdzie r = n - k. Po wyznaczeniu owego wielomianu, •by obliczyć wektor kodowy kodu Reeda-Solomona (n,k) konieczne jest wykonanie kilku operacji.

• W pierwszym kroku algorytmu kodowania mnożymy wielomian informacyjny m(x) przez wielomian x"'¹' otrzymując w ten sposób wielomian postaci

x"~^lcm(x)

^ Drugi krok, to podzielenie wyznaczonego wielomianu xⁿ'^km(x) przez wyznaczony

p wcześniej wielomian generujący kod Reeda-Solomona g(x) i wyznaczenie reszty

fc f(x) z tego dzielenia. Dzielenie to można przedstawić w formie algorytmu

| Euklidesa

Strona 21 |

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

xⁿ-^tm(x)=q(x)g(x)+r(x),

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

r(x)=r„^x"~'^c~^l+...+r,x+^

• W trzecim kroku algorytmu wyznaczamy wielomian Cx(x), który jest wektorem kodowym kodu Reeda-Solomona. Wektor ten otrzymujemy poprzez dodanie wielomianów x^{^}~^l<m(x) i r(x).

C^x)=x''-^km^x)+r(x)

Wektor kodowy Cx(x) kodu Reeda-Sofomona przybiera, więc formę:

^CX = [^-P-^-t^-A-r-^o]

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

• Wszystkie kroki algorytmu powtarzamy tak długo, aż dla każdego bloku informacyjnego wyznaczymy kolejne wektory kodowe Cx(x). Liczba kroków zależy od rozmiaru kodowanej informacji oraz od wielkości bloków, na które dzielona jest kodowana informacja.

W przypadku niniejszej pracy dyplomowej wielomian informacyjny m(x) jest (Ha 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 Cx(x) będzie miał rozmiar 255, z czego pierwsze 125 /będzie informacją a pozostałe 130 będzie elementami kontrolnymi.

Strona 22

Programowa realizacja kodu Reeda-Sotomona nad GF(256) z uproszczoną metodą dekodowania

4.5. Uproszczony algorytm dekodowania

Uproszczony algorytm dekodowania jest algorytmem uniwersalnym, który może być stosowany do korekcji błędów w każdym z kodów cynicznych. Co prawda dla, każdego kodu cyklicznego istnieje jego własny algorytm dekodowania, ale w praktyce najczęściej stosuje się algorytm uproszczony, który jest dość prosty do zaimplementowania, a przy tym daje dość dobre efekty.

Metoda uproszczona umożliwia wykrycie oraz skorygowanie wszystkich błędów znajdujących się na n-k sąsiadujących ze sobą pozycjach wektora kodowego.

Podstawą wszystkich algorytmów dekodowania jest syndrom. W przypadku kodów cyklicznych, a więc i kodów Reeda-Solomona syndrom jest resztą z dzielenia wielomianu odpowiadającego wektorowi odebranemu Cy(x) oraz wielomianu generującego dany kod g(x). Dzielenie to można przestawić jak poniżej:

C,(x)=q(x)q(x)+s(x)

pdzte q(x) jest częścią całkowitą, g(x) jest wielomianem generującym kod, a s(x) jest l z tego dzielenia, czyli syndromem.

Syndrom s(x) jest wielomianem stopnia n - k - 1 pozwalającym stwierdzić, czy wiy wektor jest wektorem kodowym, czy też występują w nim błędy. W przypadku, obliczony syndrom ma wartość O, odebrany wektor nie posiada błędów i jest

wi kodowym, a w czasie transmisji nie doszło do jakichkolwiek przekłamań.

liast, jeśli wartość syndromu jest różna od zera, oznacza to, iż podczas transmisji

»do powstania błędów i konieczna będzie ich korekcfa.

Poniższy rysunek przedstawia schemat blokowy uproszczonego algorytmu

Strona 23

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

Wektor odebrany Co

Wyzerowanie licznika przesunięć i:=0

i •= i + 1

Cykliczne przesunięcie c, w prawo o jedną pozycję

Obliczenie syndromu i jego wagi Hamminga

s,:=c,(modg(x));

W,:=Wi(S,);

NIE

Korekcja błędów (dodanie do wektora odebranego obliczonego syndromu)

Q :=C,*+Si

Strona 24

Cykliczne przesunięcie d w lewo i razy

Wektor skorygowany mo

Rys. 4. Schemat blokowy uproszczonego algorytmu dekodowania

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

Procedura dekodowania za pomocą uproszczonego algorytmu dekodowania rozpoczyna się od odebrania wektora kodowego, a następnie wyzerowania licznika przesunięć.

W drugim etapie dekodowania następuje obliczenie syndromu dla danego wektora odebranego. Syndrom jest resztą z dzielenia wielomianu odpowiadającego wektorowi błędów przez wielomian generujący kod g(x). Po wyliczeniu syndromu następuje wyznaczenie wagi Hamminga w(s) dla tego syndromu. Waga Hamminga jest liczbą niezerowycn składowych wektora.

W trzecim kroku algorytmu dekodowania, w zależności od tego, jaka jest obliczona waga Hamminga możliwe są dwa przypadki.

W przypadku pierwszym waga syndromu jest mniejsza lub równa zdolności korekcyjnej kodu w(s) $ /, i oznacza to, iż w wektorze kodowym Cy wystąpiło nie więcej niż / błędów i leżą one w części nadmiarowej (kontrolnej) owego wektora. W tej sytuacji,

i?

laby skorygować błędny wektor, konieczne jest dodanie do tego wektora, obliczonego j wcześniej syndromu. W wyniku tej operacji otrzymany zostanie nowy wektor wyjściowy

^.

cd ^=: Cy ⁺ S • Co, w swojej części informacyjnej zawiera skorygowaną informację m.

W przypadku drugim, waga syndromu jest większa od zdolności korekcyjnej w(s) > t. Oznacza to, że błędy znajdują się w części informacyjnej wektora mego, w części informacyjnej i kontrolnej lub ich liczba jest większa od zdolności syjnej kodu /. W tym wypadku należy dokonać przesunięcia cyklicznego wektora mego, w taki sposób, aby błędy znalazły się w części nadmiarowej, poczym f je skorygować.

Całą operację rozpoczynamy od przesunięcia wektora odebranego o jedną i w wybranym kierunku (np. w prawo), aby błędy z części informacyjnej wektora

Strona 25

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

kodowego znalazły się w Jego części nadmiarowej. Następnie obliczamy syndrom oraz wagę tego syndromu. W kolejnym etapie sprawdzamy, czy został spełniony warunek pierwszy (w(s) śt), czy też warunek drugi (w(s) > t).

Jeżeli waga syndromu jest mniejsza bądź równa zdolności korekcyjnej kodu, to należy dokonać korekcji wektora odebranego tak jak w przypadku pierwszym, a następnie skorygowany wektor przesunąć cyklicznie w odwrotną stronę, aby odtworzyć jego pierwotną postać.

W sytuacji, gdy waga syndromu w dalszym ciągu jest większa od zdolności korekcyjnej kodu przesuwamy wektor odebrany ponownie o jedna pozycję. Obliczamy jeszcze raz syndrom i jego wagę oraz sprawdzamy warunki. Operacie powtarzamy tak (Hugo, aż waga syndromu będzie mniejsza od zdolności korekcyjnej kodu. Wtedy korygujemy wektor odebrany i przesuwamy go z powrotem o tyle pozycji, o ile przesunęliśmy go wcześniej.

Strona 26

Programowa realizacja kodu Reeda-Sotomona nad GF(256) z uproszczoną metodą dekodowania

5. Opis programu

5.1. Ogólna charakterystyka programu

Program wchodzący w skład niniejszej pracy dyplomowej umożliwia zakodowanie dowolnej informaqi wykorzystując przy tym kod Reeda-Solomona, a następnie zdekodowanie tej informacji.

Kod Reeda-Solomona wykorzystany w tej aplikacji jest kodem RS(255,125). Oznacza to, iż informacja podczas kodowania jest dzielona na bloki zawierające po 125 (tementów informacyjnych. W procesie kodowania utworzony zostaje 255 elementowy wektor kodowy, który składa się ze 125 elementów informacyjnych i dodatkowo ze 130 , ttementów kontrolnych, służących do wykrycia i korekcji ewentualnie powstałych tptelięj błędów i przekłamań.

ti':

Aplikacja umożliwia wykrycie i korekcję do 65 powstałych błędów. Wynika to z i zaprogramowanego kodu Reeda-Solomona. Zgodnie ze wzorem:

t=E\

d-\

2

i d oznacza odległość minimalną a E oznacza największą liczbę całkowitą nie ,od (d - 1 ) / 2, po podstawieniu do wzoru parametrów kodu RS(255,125)

t=E

131-1

Strona 27

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania ,a stąd wynika, iż zdolność korekcyjna kodu / wynosi 65.

Program został napisany w Delphi, obiektowej odmianie języka programowania Pascal. Aplikacja została stworzona do działania w środowisku Windows 95/98. Wymagania sprzętowe nie są wygórowane. Wystarczy jakikolwiek procesor klasy Pentium i 16 MB RAM. W związku jednak z dość złożonymi operacjami matematycznymi i obliczeniowymi wskazane jest posiadanie większej ilości pamięci operacyjnej. Pozwoli to na przyspieszenie działania programu i bardziej komfortową pracę.

Program przeznaczony jest do celów edukacyjnych i prezentacji możliwości korekcyjnych jednego z blokowych kodów korekcyjnych, jakim jest kod Reeda-Sotomona. Program skierowany jest nie tylko dla studentów kierunków związanych z toyptografią, ale także do osób chcących tylko zapoznać się z możliwościami korekcyjnymi kodu Reeda-Solomona.

5.2. Tworzenie ciała GF(256)

W procedurze odpowiedzialnej za utworzenie rozszerzonego ciała GF(256) »na została tablica 256 x 8. W tablicy tej zapisane jest 256 wektorów ających poszczególnym elementom ciała rozszerzonego GF(256). Pojedynczy

składa się z 8 elementów, dzięki czemu każdy z wektorów odpowiada jakiemuś

towi z tablicy kodów ASCII.

Pierwsza część procedury „tworz_GF256" tworzy wektor zerowy 0=f000000 oraz osiem początkowych: 1 =[10000000], a =[01000000], a² =[0 0000],a³ =[00010000], a⁴ =[00001000], a⁵ =[00000100], 00000010 ], a⁷ =[00000001].

Pozostałe wektory wyliczane są w drugiej części procedury, korzystając z stowarzyszonej z wielomianem pierwotnym p(x) 8 stopnia nad ciałem GF(2). ta została opisana w p. 4.2. Poniżej procedura tworząca ciało rozszerzone

Strona 28

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

//tworzenie ciała GF(256) //

procedurę TForm1.tworz_6F256;

vardegGF:integer;

i,k:integer;

// pierwsze 9 wektorów //

for i:=0 to 8 do begin

for k:=0 to 7 do

begin GF256[i,k]:=0;

end;

end;

for i:=0 to 7 do GF256[i+1 ,i]:=1;

//tworzenie kolejnych wektorów //

<tegGF:=256;

fori:=1to(degGF-1-8)do bogiń fork:=0to7do begin

^; ^^B GF256(i+8,k]:=GF256ti,k] xor GF256[i+2,k] xor GF256[i+3,k] xor GF256[i+4,kJ;

S¹ l ""d.

W

l, Dodatkowo po skonstruowaniu ciała GF(256), tworzona jest tablica GF_DEC, do zapisane zostają elementy ciała w postaci dziesiętnej. Tablica ta w stwie do tablicy GF256 jest tablicą jednowymiarową składającą się z 256 ' odpowiadającym poszczególnym elementom dała. Taka operacja umożliwia szybsze wyszukiwanie dowolnego elementu ciała GF(256) bez przeliczania elementu z postaci wektorowej do postaci dziesiętnej.

Strona 29

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

Dzięki temu cały proces kodowania l dekodowania informacji przebiega zauważalnie szybciej.

W procedurze „GFJ3EC", każdy z wektorów ciała GF(256) jest konwertowany z postaci binarnej na dziesiętną. Np. wektor a¹⁴ = [ 1 1 O O 1 O O O ] po zamianie do postaci dziesiętnej zostaje zapisany w tablicy jako wartość 200.

//tworzenie tablicy wartości dziesiętnych ciała GF(256) //

procedurę TForm1.GF_to_DEC;

var i,k,l,potega:integer;

begin

//konwersja wektora z postaci binarnej na dziesiętna //

fcfi:=0to255do begin

forlc=0to7do begin

forl:=0to6-kdo

begin potega:=2*potega;

end;

2nakD:=znal<D+(GF256fi,k]*potega);

potega:=1;

wd;

F.DEC[i]:=znal<D;

Strona 30

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

5.3. Tablice mnożenia i dodawania w ciele GF(256)

Tablice działań ciał rozszerzonych są bardzo istotne w konstruowaniu kodów korekcyjnych. Praktycznie cała procedura kodowania jak i dekodowania opiera się na mnożeniu i sumowaniu odpowiednich elementów ciała GF(256). Dlatego też, poprawne wyznaczenie obu tablic jest jednym z najważniejszych etapów w programowym konstruowaniu kodu Reeda-Solomona.

Za utworzenie tablic dodawania i mnożenia ciała GF(256) w programie wchodzącym w skład niniejszej pracy odpowiedzialne są dwie procedury:

• GF_mnozenie

• GF_dodawanie

W obu przypadkach utworzone zostają tablice dwuwymiarowe o rozmiarach 256 x 256. Następnie w odpowiednie miejsca w tablicy zapisuje się iloczyn dwóch elementów ciała (tablica mnożenia) tub sumę (tablica dodawania).

W procedurze ,GF_mnozenie" do wyznaczenia iloczynu dwóch dowolnych elementów stosowany jest wzór;

a'-^ =a'⁺-^/<^mo(lł-^l)

1—tomiast w procedurze ,GF_dodawanie¹' sumę elementów dała GF(256) wyznacza się ująć postać wektorową poszczególnych elementów ciała np,

a^a^tlOIIIOOOl+IIIOOlOOOl^OII-lOOOOl

Tak wyliczony element ciała w postaci wektorowej jest zamieniany na postać ?tną i zapisywany do tablicy dodawania.

Poniżej przedstawione są obie procedury, za pomocą których tworzone są •mnożenia i dodawania ciała GF(256).

Strona 31

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania //tworzenie tablicy mnożenia w ciele GF(256) //

procedurę TForm1.GF_mnozenie;

var i,j:integer;

for i:=0 to 255 do GF_mnoz[0,i]:=0;

for i:=0 to 255 do GF_mnozfi,OJ:=0;

for i:=1 to 255 do forj:=1 to 255 do begin

if(i+j)<=256 then GF_mnozfi,J]:=((i+j)-1)

else GF_mnozri,j]:=((i+J) mód 256);

//tworzenie tablicy dodawania w ciele GF(256) //

procedurę TForm1.GF_dodawanie;

^wij.fcinteger;

|beflin

, fcr i:=0 to 255 do GF_dod[0,i]:=i;

*iri:=0 to 255 do GF_dod[i,0]:=i;

l3ri:s1to255do IDr pito 255 do Mgin tork:=0to7do

tablica(k]:=GF256[i,k] xor GF256[j,k];

bin2dec(tablica);

rtorlc=0to255do

|iGF_DEC[k]=znakD then GF_dodfiJ]:=k;

Strona 32

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

5.4. Tworzenie wielomianu generującego kod

Wielomian generujący kod wyznacza się w celu obliczenia wektorów kodowych. Dla kodu Reeda-Solomona o długości wektora kodowego 255 i wektorze informacyjnym o rozmiarze 125, wektor ten będzie zawierał 130 elementów. Dlatego też, w procedurze ,tworz_WGEN" odpowiedzialnej za skonstruowanie wielomianu generującego kod, zadeklarowana została tablica GF_WGENo 130 polach.

Wielomian generujący kod RS(255,125) wyznaczany jest zgodnie ze wzorem postaci:

130

g{x) = Y[(x+a') =(x+a)(x+a²)...(x+a^l30) 1=1

W procedurze „tworzJ/YGEN" wykonywane są operacje na obliczonych wcześniej tablicach mnożenia (GF_mnoz) oraz dodawania (GF__dod).

otworzenie wielomianu generującego kod RS(255,125) //

l ||rocedure TForm1.tworz_WGEN;

par wiel_2;airay[0.. 1 ] of integer;

wieli ,brłp_iloczyn, iloczyn2: arrayfO.. 129]of integer;

i,j,k,w,deg_w1, deg_w2, m: integer;

nie wielomianu 1// ri:=0to129dowiel1[i]:=0;

w wartości początkowych wielomianu 1 [1 2] // 1|0]:=1;

11(1]:=2;

nie tablic pomocniczych// ) to 129 do tmp_iloczyn[i]:=0;

)to129doiloczynfi]:=0;

Strona 33

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

// ustalanie współczynników wielomianu 2 // for i:=0 to 1 do wiel_2[i]:=0;

wiel_2[OJ:=1;

wiel_2f1]:=3;

deg_w2:=1;

i:=129;

licznik: =3;

//mnożenie wielomianów // repeat

for k:=deg_w2 downto O do begin

for m := i downto O do

begin

tmp_iloczynfmJ:=GF_mnoztwiel_2[k],wiel1[m]];

end;

forj:=129 downto O do tmp_iloczyn(]]:=GF_dod(iloczyn[i],tmp_iloczyn[)]J;

forj:=0 to 129 do iloczyn2(j]:=tmp_iloczyn[(];

iloczynf0]:=0;

forj:=1 to 129 do iloczyn[J]:=tmp_iloczyn[j-1];

forw:=0 to 129 do tmpJloczyn[w]:=0;

end;

for i:=0 to 129 do wiel1[i]:=iloczyn2fiJ;

licznik:=licznik+1;

wiel_2[1]:=licznik;

untillicznik=131;

5.5. Algorytm kodowania

|, Procedura kodowania składa się z trzech kroków. W pierwszym kroku algorytmu jest wektor XMX. Wektor ten powstaje poprzez pomnożenie wielomianu m(x) przez wielomian xⁿ'^k. Jako, że wielomian informacyjny jest stopnia

Strona 34

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

125, a wielomian x""* jest stopnia 130 to w związku z tym obliczony wielomian XMX będzie stopnia 254.

W drugim etapie kodowania wyznaczony w pierwszym kroku wielomian XMX dzielimy przez wielomian generujący kod GF__WGEN. Wyliczamy w ten sposób resztę zdzielenia.

W trzecim kroku obliczamy wektor kodowy CX przez dodanie wektora XMX i wyliczonej w punkcie drugim reszty z dzielenia. Następnie wektor CX zapisujemy do pliku i powtarzamy całą operację tak długo, aż cała informacja zostanie zakodowana.

//algorytm kodowania //

procedurę TFormI .kodowanie;

wij,w:integer;

begin

// l.krok algorytmu - tworzenie wektora XMX // fcr i:=0 to 124 do XMX[i]:=INF[i], tor i:=125 to 254 do XMX[i]:=0;

//Zhrok algorytmu - XMX podzielić przez W_GEN // Wel_dziel(XMX,GF_WGEN);

ff3.krok algorytmu - dodanie XMX i reszty z dzielenia//

|<Bfi:=0 to 125 do CX[i]:=XMX[i];

ynrcsOto 128 do CX(i+126]:=syndcomfi];

•pis do pliku// rj:«0to254do

-DEC[w];

P1,Ch);

Strona 35

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

5.6. Algorytm dekodowania

W programie został zaimplementowany uproszczony algorytm dekodowania. Algorytm ten pozwala na wykrycie i skorygowanie wszystkich błędów znajdujących się na n - k pozycjach wektora kodowego.

Po odebraniu wektora kodowego INF_DEK obliczany jest Jego syndrom. Syndrom wylicza się poprzez podzielenie wektora odebranego przez wielomian generujący dany kod GF_WGEN. Syndrom jest równy reszcie z dzielenia.

W kolejnym etapie sprawdza się czy syndrom ma wartość zerową czy też jego wartość jest różna od zera. W przypadku gdy wartość jest zerowa oznacza to, iż wektor odebrany jest wektorem kodowym i nie wystąpiły w nim żadne błędy wykrywalne przez kodRS(255,125).

Jeśli wartość syndromu nie jest zerowa oblicza się jego wagę Hamminga ,waga_Hamm". W zależności od tego, czy waga syndromu jest mniejsza od zdolności | korekcyjnej kodu, czy też jest większa dalszy proces dekodowania przebiega trochę

W przypadku gdy waga syndromu jest mniejsza lub równa zdolności korekcyjnej / (dla kodu Reeda-Solomona (255,125) wartość ta wynosi 65) do wektora anego dodaje się wyliczony syndrom. W wyniku tej operacji powstanie wektor owy INF_KOR, w którym wszystkie błędy znajdujące się w części kontrolnej ra kodowego zostaną skorygowane. Pierwsze 125 elementów tego wektora w przesyłaną informację.

Jeśli jednak waga Hamminga syndromu jest większa od zdolności korekcyjnej i oznacza to, iż błędy występują w części informacyjnej wektora kodowego. W tym u należy przesunąć cyklicznie wektor odebrany o jedną pozycję i ponownie ^{. syndrom oraz jego wagę.

Strona 36

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

Jeśli waga syndromu Jest mniejsza od zdolności korekcyjnej kodu, to do wektora odebranego dodajemy syndrom, a następnie tak powstały wektor przesuwamy cyklicznie o jedna pozycję w odwrotnym kierunku.

W przypadku, gdy w dalszym ciągu waga syndromu jest większa od / wektor odebrany jest przesuwany cyklicznie o jedną pożycie do momentu, aż waga syndromu będzie mniejsza lub równa zdolności korekcyjnej kodu. Wtedy wektor odebrany zostaje skorygowany i przesunięty cyklicznie o tyte pozycji o ite był wcześniej przesunięty.

Po wykryciu i skorygowaniu błędów, elementy wektora INF_KOR zostają zamienione na odpowiadające im symbole, i zapisane do pliku „skoryg.txt". Następnie pobrany zostaje kolejny wektor kodowy i procedura dekodowania zostaje powtórzona. Operacja ta przebiega tak długo, aż wszystkie wektory kodowe zostaną zdekodowane.

//algorytm dekodowania //

procedurę TFormI.dekodowanie;

wi,j,w,k,licznik:integer;

OKboolean;

wybor=2;

OK.=false;

•J II obliczanie syndromu // 1:1 Wel_dziel(INF_DEK,GF_WGEN);

f Obliczanie wagi Hamminga syndromu // w®a_Hamm(syndrom);

h»fla.H<=65then Nin |bri:»0 to 125 do lNF_KORfi]:=INF_DEKriJ;

rfcsOto 128 do INFJ<OR[i+126J:=GF_dodflNF_DEKfi+126],syndromfiJJ;

Opis do pliku// rj:"0to254do

Strona 37

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

w:=INF_KOR[j],

Ch:=GF_DEC[w];

Write(F1,Cri);

end;

//koniec zapisu//

end else begin

licznik: =0;

repeat // przesuniecie wektora odebranego o jedna pozycje w prawo //

forj:=0 to 253 do łNF_TMP(J+1J:=INF_DEK[jJ;

INF_TMPfO]:=tNF_DEKI254];

forj:=0 to 254 do INF_DEK[jJ-=INF_TMP[)j;

wybór: =3;

// obliczenie syndromu i wagi Hamminga // Wiel_dziel(INF_TMP, GF_WGEN);

waga_Hamm(syndrom);

ifwaga_H<=65then begin

forj:=0to 125 do INF_KOR(jJ:=INF_TMP[j];

forj:=0 to 128 do (NF_KORD+126]:=GF_dodflNF_TMP[j+126],syndrom[(]J;

fork:=1 tolicznik+1 do

begin

// przesuniecie wektora odebranego o jedna pozycje w lewo // forj:=1 to 254 do INF_DEKD-1J:=INF_KORtiJ;

INF_DEKp54J:=INF_KORfOJ;

for w:=0 to 254 do INF_KORtw]:=INF_DEKfwJ;

licznik:=licznik+1;

itii (licznik=255) or (OK=true);

Strona 38

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

//zapis do pliku// for j: =0 to 254 do begin

w:=INF_KORb],

Ch:=GF_DEC[w];

Write(F1,Ch);

end;

//koniec zapisu//

Strona 39

Programowa realizacja kodu Reeda-Sotomona nad GF(256) z uproszczoną metodą dekodowania

6. Wnioski

W obecnych czasach, gdy fntemet staje się powoli najważniejszym medium informacyjnym na świecie, gdy codziennie miliony zwykłych użytkowników komputerów, wielkie koncerny, instytucje rządowe i naukowe przesyłają miliony bajtów informacji ochrona tych danych staje się bardzo ważna, l nie chodzi tu tylko o ochronę przed niepowołanym dostępem osób nieuprawnionych do naszych prywatnych danych, ale także o ochronę informacji przed różnego rodzaju zakłóceniami, przekłamaniami występującymi często podczas transmisji, czy też podczas przechowywania danych na różnego rodzaju nośnikach (płyty CD, taśmy, a także pamięci komputerowe).

Właśnie do ochrony danych przed błędami transmisyjnymi bardzo dobrze nadają

vą kody korekcyjne, których przedstawicielem jest cykliczny kod Reeda-Solomona. Kod i;

l ten jest obecnie jednym z najczęściej stosowanych kodów korekcyjnych. Ogromną jego

ttetą jest fakt, iż jest to kod blokowy, czyli potrafiący wykryć i skorygować błędy iHpowe. Sam fakt, iż jest to kod blokowy nie zadecydował jednak o jego obecnej Dpulamośd. Kod Reeda-Solomona jest kodem, który daje się stosunkowo łatwo implementować programowo, a dodatkowo szybkość kodowania i dekodowania aoji jest całkiem przyzwoita.

W niniejszej pracy dyplomowej został przedstawiony kod Reeda-Sotomona 5,125) nad ciałem GF(256). Kod ten podobnie jak inne kody Reeda-Sotomona Jest m cyklicznym, potrafiącym wykrywać i korygować błędy grupowe. Przy pomocy kodu możliwe jest skorygowanie do 65 błędów. Decyduje o tym zdolność flna t, która dla kodu RS o długości wektora informacyjnego 125 i 130 kontrolnych wynosi właśnie 65.

Strona 40

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

W skład pracy wchodzi także program, który umożliwia zakodowanie i zdekodowanie dowolnej informacji wykorzystując do tego celu właśnie kod Reeda-Solomona (255,125) oraz uproszczoną metodę dekodowania, która jest metodą bardzo szybką i niezłe radzącą sobie z błędami grupowymi.

Przy pomocy tego programu możliwe jest zapoznanie się z jednym z cyklicznych kodów korekcyjnych, który obecnie zyskuje coraz większą popularność i w przyszłości może stać się jednym z najczęściej wykorzystywanych do ochrony danych kodów.

Program umożliwia w łatwy sposób dokonywanie modyfikacji zakodowanej informacji np. poprzez wprowadzenie pewnej liczby błędów, następnie zdekodowanie błędnej informacji i obserwację jak zachowuje się kod Reeda-Solomona na wprowadzane zakłócenia.

Aplikacja ta może być doskonałym narzędziem pokazującym zalety jak i wady kodów korekcyjnych, a w szczególności kodów Reeda-Solomona. Program może być wykorzystany podczas zajęć laboratoryjnych ze studentami w celu uzupełnienia | wiadomości teoretycznych z wykładów. Pokazanie praktycznego działania kodów ; korekcyjnych pozwoli na lepsze zrozumienie ich specyfiki oraz sposobu działania.

Jednakże nie tylko studenci mogą wykorzystywać ten program do własnych jcelow. Osoby, które zainteresowane są sposobami ochrony danych przed błędami, a i orientującymi się w teorii kodowania i kryptografii mogą również z niego korzystać. fowanie praktycznego działania kodów korekcyjnych umożliwi im późniejsze • zrozumienie teorii związanej z kodowaniem korekcyjnym.

Dużym utrudnieniem przy pisaniu pracy dyplomowej okazały się działania na ch ciała GF(256) oraz utworzenie wielomianu generującego kod. W teorii, potrzebne do skonstruowania tabel mnożenia i dodawania oraz wielomianu o kod nie wyglądają zbyt skomplikowanie, jednakże w praktyce ile ich w postaci zrozumiałej dla komputera jest czynnością o wiele bardziej

Strona 41

Programowa realizacja kodu Reeda-Solomona nad GF(256) z uproszczoną metodą dekodowania

Fakt, i'ź na polskim rynku wydawniczym brakuje pozycji traktujących o teorii kodowania i kryptografii, a jeśli już są to są to na ogół pozycje w Języku angielskim również nie ułatwiał sprawy.

W Intemecie sytuacja wygląda podobnie. Stron WWW, na których można dowiedzieć się czegoś o kodach Reeda-Sołomona nie ma zbyt wiele. Oczywiście są strony takie jak np. http://www.4i2i.com/reed sołomon codes.htm". gdzie można znaleźć dość dużo informacji na temat kodów RS, jednakże ogólnie dostęp do tego typu informacji jest dość utrudniony.

Mimo tych utrudnień ostatecznie jednak, program udało się ukończyć, aby działał poprawnie. Dzięki temu może on być doskonałym uzupełnieniem wykładów oraz służyć do prezentacji możliwości kodów korekcyjnych.

Strona 42

---