Kodowanie i kryptografia
Kody splotowe
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki
pokój 908, C-5
tel. [phone]
Wykład VI
e-mail: [e-mail]
www: lstwww.ita.pwr.wroc.pl/~RB/
6-godzin
Plan wykładu
Historia
Definicja kodu splotowego
Sposoby kodowania informacji
Tworzenie kodu
Metody dekodowania kodów splotowych
algorytm Vitterbiego
twardo decyzyjny
miękko decyzyjny
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 2/62
Historia
Kody splotowe wprowadził P. Elias w roku 1955.
Sekwencyjny algorytm dekodowania kodów
splotowych przedstawił w roku 1957 J. M. Wozencraft,
a jego implementację opisali niezależnie R. M. Fano i J.
L. Massey w roku 1963.
W roku 1967 A. J. Viterbi przedstawił algorytm
dekodowania kodów splotowych, opierający się na
zasadzie największego prawdopodobieństwa, który
zapewnił lepsze właściwości korekcyjne i mniejsze
opóz
nienie dekodowania niż algorytm sekwencyjny.
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 3/62
Definicja kodu splotowego
Kod splotowy jest to kod drzewiasty, dla którego
ciąg c(i) zależy od ciągu h(i) oraz od skończonej
liczby (N - 1) wcześniejszych ciągów
informacyjnych za pośrednictwem pewnej funkcji
f, będącej przekształceniem liniowym
c(i) = f (h(i-N +1), h(i-N ), K , h(i))
lub
c(i) = f ( �(i),h(i))
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 4/62
Koder kodu splotowego
Nk-komórkowy rejestr przesuwający (N-sekcji po k-komórek)
Symbol wej. �(i)-stan modulatora (pamięć)
h(i) h(i-1) h(i-N+1) h(i-N)
k ... 2 1 k ... 2 1 k ... 2 1 k ... 2 1
Wejście
k-bitowe
symbole
informacyjne
n ... 2 1
Ciąg n-bitowych
n ... 2 1
Wyjście
symboli kodowych
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 5/62
Macierz generująca
Macierz generująca jest macierzą półnieskończoną
G1 G2 L GN 0 0 0 0
�ł łł
�ł śł
0 G1 G2 L GN 0 0 0
�ł śł
G" = �ł 0 0 G1 G2 L GN 0 0 śł,
c = h �" G"
�ł śł
0 0 0 G1 G2 L GN 0
�ł śł
�ł śł
0 0 0 0 L L L L�ł
�ł
w której:
Podmacierz Gi opisuje połączenie k komórek i-tego
segmentu rejestru wejściowego z n komórkami rejestru
wyjściowego
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 6/62
Przykład 4.1
Koder splotowy
(2,1,3)
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 7/62
Koder binarnego kodu splotowego
(2, 1, 3) Koder
y
ródło binarneWejście
h(i) h(i-1) h(i-2)
1 1 1 0 1 1 0 1 0 1 0 0 0
9 8 7 6 5 4 3 2 1 0
Czas
0 0
Kanał telekomunikacyjny �!Wyjście
C1(i) C2(i)
0 0
0 -1
Czas
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 8/62
Koder binarnego kodu splotowego
(2, 1, 3) Koder
y
ródło binarneWejście
h(i) h(i-1) h(i-2)
... 1 1 1 0 1 1 0 1 0 1 0 0
10 9 8 7 6 5 4 3 2 1
Czas
1 1
Kanał telekomunikacyjny �!Wyjście
C1(i) C2(i)
1 1
1 0
Czas
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 9/62
Koder binarnego kodu splotowego
(2, 1, 3) Koder
y
ródło binarneWejście
h(i) h(i-1) h(i-2)
... ... 1 1 1 0 1 1 0 1 0 1 0
10 9 8 7 6 5 4 3 2
Czas
1 0
Kanał telekomunikacyjny �!Wyjście
C1(i) C2(i)
1 0 1 1
2 1 0
Czas
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 10/62
Koder binarnego kodu splotowego
(2, 1, 3) Koder
y
ródło binarneWejście
h(i) h(i-1) h(i-2)
... ... ... 1 1 1 0 1 1 0 1 0 1
10 9 8 7 6 5 4 3
Czas
0 0
Kanał telekomunikacyjny �!Wyjście
C1(i) C2(i)
0 0 1 0 1 1
3 2 1 0
Czas
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 11/62
Koder binarnego kodu splotowego
(2, 1, 3) Koder
y
ródło binarneWejście
h(i) h(i-1) h(i-2)
... ... ... ... 1 1 1 0 1 1 0 1 0
10 9 8 7 6 5 4
Czas
1 0
Kanał telekomunikacyjny �!Wyjście
C1(i) C2(i)
1 0 0 0 1 0 1 1
4 3 2 1 0
Czas
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 12/62
Koder binarnego kodu splotowego
(2, 1, 3) Koder
y
ródło binarneWejście
h(i) h(i-1) h(i-2)
... ... ... ... ... 1 1 1 0 1 1 0 1
10 9 8 7 6 5
Czas
0 0
Kanał telekomunikacyjny �!Wyjście
C1(i) C2(i)
0 0 1 0 0 0 1 0 1 1
5 4 3 2 1 0
Czas
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 13/62
Koder binarnego kodu splotowego
(2, 1, 3) Koder
y
ródło binarneWejście
h(i) h(i-1) h(i-2)
... ... ... ... ... ... 1 1 1 0 1 1 0
10 9 8 7 6
Czas
0 1
Kanał telekomunikacyjny �!Wyjście
C1(i) C2(i)
0 1 0 0 1 0 0 0 1 0 1 1
6 5 4 3 2 1 0
Czas
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 14/62
Koder binarnego kodu splotowego
(2, 1, 3) Koder
y
ródło binarneWejście
h(i) h(i-1) h(i-2)
... ... ... ... ... ... ... 1 1 1 0 1 1
10 9 8 7
Czas
0 1
Kanał telekomunikacyjny �!Wyjście
C1(i) C2(i)
0 1 0 1 0 0 1 0 0 0 1 0 1 1
7 6 5 4 3 2 1 0
Czas
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 15/62
Koder binarnego kodu splotowego
(2, 1, 3) Koder
y
ródło binarneWejście
h(i) h(i-1) h(i-2)
... ... ... ... ... ... ... ... 1 1 1 0 1
10 9 8
Czas
0 0
Kanał telekomunikacyjny �!Wyjście
C1(i) C2(i)
0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1
8 7 6 5 4 3 2 1 0
Czas
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 16/62
Koder binarnego kodu splotowego
(2, 1, 3) Koder
y
ródło binarneWejście
h(i) h(i-1) h(i-2)
... ... ... ... ... ... ... ... ... 1 1 1 0
10 9
Czas
0 1
Kanał telekomunikacyjny �!Wyjście
C1(i) C2(i)
0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1
9 8 7 6 5 4 3 2 1 0
Czas
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 17/62
Koder binarnego kodu splotowego
(2, 1, 3) Koder
y
ródło binarneWejście
h(i) h(i-1) h(i-2)
... ... ... ... ... ... ... ... ... ... 1 1 1
10
Czas
1 0
Kanał telekomunikacyjny �!Wyjście
C1(i) C2(i)
1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1
10 9 8 7 6 5 4 3 2 1 0
Czas
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 18/62
Diagram stanów
automatu
Stan d
11
Stan b Stan c
10 01
Stan a
00
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 19/62
Przykład 3.1
Na wyznaczenie przesuniętego ciągu
kodowego
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 20/62
Kod cykliczny
(xn +1)
Wielomian oraz jego składowe odgrywają
istotną rolę w generacji kodów cyklicznych.
W algebrze wielomianów modulo wielomian (xn +1)
zbiór wielomianów {c(x)} może stanowić zbiór
ciągów kodowych, gdy dowolny wielomian

( ) ( ) jest wielokrotnością pewnego
c x "{c x }
wielomianu g(x), a więc
c(x) = a(x)�" g(x)
i spełniony jest warunek
Rg ( x)[xn +1] = 0
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 21/62
Wielomian generujący
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 q-narnego kodu
cyklicznego (n, k), gdy dla dowolnego ( ) ( )
c x "{c x }
zachodzi
Rg ( x)[c(x)] = 0
c(x) = h(x)�" g(x)
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 22/62
Wielomian generujący
Wielomian g(x) nazywamy wielomianem
generującym kod cykliczny, Stopień wielomianu g(x)
określa liczbę pozycji kontrolnych kodu.
Właściwości wielomianu g(x)
wielomian g(x) jest
Rg ( x)[xn +1] = 0
składową wielomianu
(xn +1)
deg g(x) = r = n - k
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 23/62
Macierzowe przedstawienie kodów
cyklicznych
Przyporządkujmy wielomianowi x(k-1)g(x) ciąg g; możemy
wówczas macierz G generującą kod liniowy, równoważny
kodowi cyklicznemu generowanemu przez wielomian g(x),
zapisać w postaci
g
�ł łł
g( - j ) -oznacza ciąg
�ł śł
g(-1)
przesunięty o j
�ł śł
M
G =
�ł śł pozycji w prawo, np.:
�łg(-k +2)śł
c = 0101100
�ł śł
(-k+1)
c(-2) = 0001011
�ł śł
�łg �ł
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 24/62
Kod dualny kodu cyklicznego
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ć
R( xn +1)[c(x)� (x)] = 0
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 25/62
Macierz generująca kod dualny
(macierz kontrolna kodu)
Wielomian generujący cykliczny kod dualny (n, n-k) określa
zależność
xn +1
q(x)=
g(x)
Macierz H generująca kod dualny ma postać
q q a" xr-1q'(x)
�ł łł
�ł śł
q(-1)
q(- j) oznacza ciąg q przesunięty o
�ł śł j pozycji w prawo
M
H =
�ł śł ,
Wielomian q(x) o odwróconej
�łq(-r+2)śł
q'(x)
kolejności współczynników.
�ł śł
(-r+1)
�ł śł
�łq �ł
Jeżeli q(x)=100100,
to q (x)=001001.
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 26/62
Przykład 3.2
Kod cykliczny
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 27/62
Macierz generująca systematyczny kod
cykliczny (n, k)
ui = Rg ( x)[xi ]
un-1
�ł łł
�ł śł
Przykład:
�łIk un-2 śł
G =
�ł M śł
Dla kodu cyklicznego (7,4)
�ł
generowanego przez wielomian
un-k =r śł
�ł �ł
g(x) = x3 + x +1 mamy
un-1 = u6 �! Rg( x )[x6 ] = x2 + 1 �! 101,
un-2 = u5 �! Rg ( x )[x5] = x2 + x +1 �! 111,
un-3 = u4 �! Rg( x )[x4 ] = x2 + x �! 110,
un-4 = u3 �! Rg( x )[x3] = x + 1 �! 011.
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 28/62
Skrócony kod cykliczny
Kody cykliczne istnieją tylko dla niektórych wartości
n, na przykład:
n = pm -1
n = p2m + pm +1
przy czym p jest liczbą pierwszą, a m - liczbą
naturalną
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 29/62
Skrócony kod cykliczny
(kod pseudocykliczny)
Procedura skracania kodu (n, k) do kodu (n , k ), gdzie n > n' :
1. Znajdujemy kod o długości ciągów najbliższej naszego
projektowanego kodu.
2. Ze zbioru ciągów kodowych wybieramy ciągi, które na
pierwszych n - n' pozycjach mają zera.
3. Z wybranych ciągów usuwamy n - n' pierwszych zer
4. Wybrane i skrócone ciągi tworzą nowy zbiór ciągów
kodowych {c (x)}
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 30/62
Przykład 3.3
Skrócony kod cykliczny
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 31/62
Skrócony kod cykliczny
(właściwości)
1. W skróconych kodach cyklicznych nie jest
spełniony warunek, że dla dowolnego
c "{c} oraz j = 1,2,..., n'-1 zachodzi
c( j) "{c}
2. Oznaczenie kodu skróconego ma postać [n',k-(n-n')]
3. Jeżeli wyjściowy kod (n, k) ma odległość dmin , to
odległość minimalna d min kodu skróconego ma
odległość niemniejszą niż dmin.
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 32/62
Kodowanie za pomocą kodów cyklicznych
1. Prosta reguła kodowania-daje w wyniku kod
niesystematyczny
Jeżeli h(x) jest wielomianem informacyjnym, a g(x) jest
wielomian generującym kod , to wielomian kodowy
jest równy
c(x) = h(x)�" g(x)
2. Uzyskanie systematycznego kodu cyklicznego zapewnia
następująca reguła kodowania
c(x) = xrh(x) - Rg( z) xrh(x)
[ ]
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 33/62
Przykład 3.11
Przykład wyznaczenia ciągu kodowego
systematycznego
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 34/62
Przykład 3.11
x9 + x5 + x2 + 1
h(x)
1 0 0 0 1 0 0 1 0 1
x5h(x)
1 0 0 0 1 0 0 1 0 1
x14 + x10 + x7 + x5
c(x)
1 0 0 0 1 0 0 1 0 1 0 0 0 1 1
x 1
x14 + x10 + x7 + x5 + +
x5h(x) Rg(x)[x5h(x)]
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 35/62
Dzielenie wielomianów
Układ od dzielenia dowolnego wielomianu przez
wielomian g(x) = gr xr + gr-1xr-1+K+g1x + g0
Wyjście
g0 g1 gr-1 gr
Wejście
P P P
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 36/62
Przykład dzielenia wielomianów
Układ od dzielenia wielomianu h(x) przez wielomian g(x)
g(x) = x5 + x4 + x2 + 1
h(x) = x9 + x5 + x2 +1
Wej. Wyj.
+ P0 P1 + P2 P3 + P4
Zasadnicze dzielenie w tym wypadku odbywa się po 5
taktach (po dojściu bitu informacji do pętli sprzężenia),
gdyż wcześniej informacja jest wpisywana do rejestrów.
W istocie sam proces dzielenia odbywa się na
wielomianie:
x5 �" h(x) = x14 + x10 + x7 + x5
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 37/62
Przykład dzielenia wielomianów
Zawartość rejestru
Takt Wejście Wyjście Wielomian
P0 P1 P2 P3 P4
1 1 0 0 0 0 0 0 x14
2 0 1 0 0 0 0 0 x13
3 0 0 1 0 0 0 0 x12
4 0 0 0 1 0 0 0 x11
5 1 0 0 0 1 0 0 x10
6 0 1 0 0 0 1 1 x9
7 0 1 1 1 0 1 1 x8
8 1 1 1 0 1 1 1 x7
9 0 0 1 0 0 0 0 x6
10 1 0 0 1 0 0 0 x5
11 0 1 0 0 1 0 0 x4
12 0 0 1 0 0 1 1 x3
13 0 1 0 0 0 1 1 x2
14 0 1 1 1 0 1 1 x1
15 0 1 1 0 1 1 1 x0
Reszta 1 1 0 0 0
Wielomian x0 x1 x2 x3 x4
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 38/62
Schemat ogólny kodera cyklicznego
gr
1 2
K2
g0 gr-2 gr-1
2
P0 Pr-2 Pr-1
Wyjście
1
K1
Wejście
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 39/62
Schemat kodera systematycznego
(15,10)
http://www.ee.uwa.edu.au/~roberto/teach/it
c314/java/CRC/crc.html
lub z dyskietki Koder cykliczny\Koder cykliczny.htm
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 40/62
Dekodowanie kodów cyklicznych
Metody detekcji błędów
wyznaczenie syndromu S(y) za pomocą macierzy HT
wyznaczenie reszty z dzielenia
r(x)= Rg(x)[y(x)]
dla r`"0 �! wektor y nie jest wektorem kodowym -
nastąpił błąd transmisji!
Wybrane metody korekcji błędów w kodach
cyklicznych
tablica dekodowania
polowanie na błędy
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 41/62
Metoda polowania na błędy
Wprowadzenie

Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 42/62
Metoda polowania na błędy
Wyznaczamy resztę z dzielenia
r(x)= Rg(x)[y(x)] �! r
Obliczamy wagę Hamminga wektora r
jeżeli wH (r)> t , to ilość błędów jest większa niż
zdolność korekcyjna lub błędy nie leżą w obszarze
bitów parzystości
wH (r)d" t
jeżeli , to błąd można skorygować-błędy leżą
w obszarze bitów parzystości, a ich ilość jest mniejsza
od zdolności korekcyjnej kodu
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 43/62
Metoda polowania na błędy
na przykładzie kodu BCH(15, 7, 2)
c 1 1 1 1 0 0 1 0 1 1 0 1 0 1 0 r 0 0 0 0 0 0 0 0
Transmisja
y
1 0 1 1 0 1 1 0 1 1 0 1 0 1 0 r 0 0 0 0 0 1 1 1
y(6) 1 0 1 1 0 1 0 1 0 1 0 1 1 0 1 r 0 0 0 1 0 0 0 1
0 0 0 1 0 0 0 1
c*(6) 1 0 1 1 0 1 0 1 0 1 1 1 1 0 0
c* 1 1 1 1 0 0 1 0 1 1 0 1 0 1 0
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 44/62
Przykład cd..
Parametry kodu BCH (15, 7, 2), to
n=15, k=7, t=2
Wielomian generujący kod BCH (15, 7, 2)
g(x) = x8 + x7 + x6 + x4 + 1.
Dekoder z sieci lub z dyskietki
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 45/62
Przegląd kodów cyklicznych
Kody BCH
Binarne kody BCH
Niebinarne kody BCH
Wielowartościowe kody BCH
Kody BCH generowane przez elementy niepierwotne
rozszerzonego ciała Galoisa
Kody HAMMINGA
Kody REEDA-SOLOMONA
Kody FIRE'A
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 46/62
KODY CYKLICZNE
Wielomian generujący kod cykliczny (n, k)
o długości n=pm-1 można przedstawić w
postaci iloczynu pewnych wielomianów
pierwszych stopnia nie większego niż m
g(x) = �1(x) �" �2(x) �" L.
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 47/62
Przykład 3.4
Związek między ciałem Galoisa, a
pierwiastkami wielomianu
generującego
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 48/62
Przykład 3.4 cd..
Reprezentacja ciała CG(23) generowanego przez
p(x) = x3 + x + 1
wielomian pierwotny
Element Reprezentacja Reprezentacja Reprezentacja
ciała potęgowa wielomianowa binarna
a1 x 010
ą
a2 x2 100
ą2
a3 x + 1 011
ą3
a4 x2 + x 110
ą4
a5 x2 + x + 1 111
ą5
a6 x2 + 1 101
ą6
1 001
a7 ą7 = ą0 =1
a8 nie istnieje 0 000
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 49/62
Definicja kodu BCH
Niech {c(x)} stanowi zbiór wielomianów stopnia nie
większego niż n - 1 o współczynnikach z ciała podstawowego
CG(p) oraz niech m, m0 i d będą liczbami naturalnymi, takimi
że:
0 d" m0 d" pm -1, d d" pm -1
Jeśli wielomian c(x)"{c(x)} ma jako kolejne pierwiastki d - 1
m0 m0 +1 m0 +d -2
elementów ciała CG(pm):
ą , ą , K, ą ,
to zbiór {c(x)} jest zbiorem wielomianów kodowych
p-narnego kodu BCH, którego odległość minimalna
dmin = d
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 50/62
Konstruowanie wielomianu generującego kodu BCH
Wielomian generujący kod BCH jest najmniejszą
wspólną wielokrotnością (NWW) wielomianów minimalnych
tych elementów ciała CG(pm), które stanowią jego pierwiastki.
� (x)
Jeśli więc przez oznaczymy wielomian minimalny
i
i-tego elementu ai ciała CG(pm), to
g(x) = NWW[ (x),� (x),....,� (x)]
�
m0 m0 +1 m0 +d -2
Dla przypomnienia elementy ai ciała CG(pm) powstają
poprzez podniesienie do potęgi i-tej elementu pierwotnego
ą, tak więc ai=ąi .
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 51/62
Wielomiany minimalne-przypomnienie
Wielomiany minimalne elementów ąi ciała wyznacza się z
zależności
ńł
�ł
x -1 dla i = 0,
�ł
� (x) = p(x) dla i = 1,
�ł
i
i
j
�ł
p
i
)
�ł"(x -(ą ) dla i > 1.
j=0
ół
p(x) wielomian pierwotny generujący ciało CG(pm),
ą element pierwotny ciała CG(pm),
i rząd i-tego elementu ciała CG(pm).
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 52/62
Przykład 3.6
Wielomiany minimalne
ciała CG(23)
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 53/62
Przykład 3.6
Wielomiany minimalne
ciała CG(23)
Wielomian
Element ciała
minimalny
0
x + 1
ą
2 4
ą1, ą , ą x3 + x + 1
3
ą , ą5 , ą6 x2 + x
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 54/62
Binarne kody BCH
konstrukcja kodu (n, k, t)
1. Symbole są określone w ciele pierwotnym CG(2).
2. Liczba bitów n=(2m-1) określa ciało rozszerzone CG(2m), z
którego będą pochodziły wielomiany minimalne.
3. Wybieramy m0.
4. Jeśli m0=1, to d jest nieparzyste i wynosi d=dmin=2�t+1, gdy
m0=0, to d jest parzyste.
0 d" m0 d" pm -1, d d" pm -1
5. Pamiętamy, że
6. Wyznaczamy wielomian g(x) i odczytujemy jego stopień r
7. Wyznaczamy długość ciągów informacyjnych k=(n-r)
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 55/62
Przykład 3.7
Wielomian generujący kod
BCH (15, 7,2)
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 56/62
Przykład 3.7
Tablica 9. Wielomiany minimalne elementów ciała CG(24)
Pierwiastki Wielomian
sprzężone minimalny
0 x
ą0
x+1
ą1, ą2, ą4, ą8
x4+x+1
ą3, ą6, ą9, ą12
x4+x3+x2+x+1
ą5, ą10
x2+x+1
ą7, ą11, ą13, ą14
x4+x3+1
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 57/62
Przykład 3.8
Wielomian generujący kod
BCH (15, 5, 3)
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 58/62
Kody Hamminga
Kod cykliczny nazywamy kodem Hamminga, jeżeli jego
wielomian generujący jest wielomianem pierwotnym ciała
CG(pm)
g(x) = p(x)
Cykliczny kod Hamminga generowany przez wielomian
stopnia m ma następujące parametry
n = 2m -1
d = dmin = 3
t = 1
k = 2m - m -1
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 59/62
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 kod są również niebinarne i są
elementami ciała CG(p). Długość bloku wynosi
n=pm-1 [symboli]
Wielomian generujący kod jest określony nad ciałem CG(p) i
ma pierwiastki w ciele rozszerzonym CG(pm).
W istocie sposób tworzenia jest taki sam jak kodu binarnego
BCH. Należy jednak zwrócić uwagę, że operacje na
współczynnikach odbywają się modulo p, a nie modulo 2.
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 60/62
Przykład 3.9
Niebinarny kod BCH (8, 2, 2)
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 61/62
Przykład 3.9
Reprezentacja ciała CG(32) generowanego przez wielomian
p(x) = x2 + x + 2
Reprezentacja Reprezentacja Reprez.
Wielomiany minimalne
Element
potęgowa wielomianowa tetrarna
ciała
�1(x) = x2 + x + 2 = p(x)
a1 x 10
ą
2 6 2
a2 2x + 1 21 � (x) = (x - ą )(x - ą ) = x + 1
ą2 2
a3 2x + 2 22
ą3 �3(x) =�1(x)
4
a4 2 02
ą4 �4(x) = x - ą = x + 1
5 7
� (x) = (x - ą )( x - ą ) = x2 + 2x + 2
a5 2x 20
ą5 5
a6 x + 2 12
ą6 �6(x) =� (x)
2
a7 x + 1 11
ą7 �3(x) =�1(x)
a8 ą8 = ą0 =1
1 01 � (x) =� (x) = x -1 = x + 2.
8 0
a9 nie istnieje 00
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 62/62
Przykład 3.9
Macierz kontrolna i generująca BCH (8,2,2,)
1 0 1 1 2 0 2 2
�ł łł
G = [I2P2,6]
�ł0 1 1 2 0 2 2 1śł =
�ł �ł
1 1 1 0 0 0 0 0
�ł łł
�ł1 2 0 1 0 0 0 0śł
�ł śł
�ł2 0 0 0 1 0 0 0śł
T
H = [P2,6I6]=
�ł0 2 0 0 0 1 0 0śł
�ł śł
�ł śł
2 2 0 0 0 0 1 0
�ł śł
�ł2 1 0 0 0 0 0 1�ł
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 63/62
Przykład 3.9
Macierz kontrolna i generująca BCH (8, 2, 2)
Ciągi
Ciągi kodowe BCH (8, 2, 2)
informacyjne
0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 1 2 0 2 2
0 1 0 1 1 2 0 2 2 1
2 0 2 0 2 2 1 0 1 1
0 2 0 2 2 1 0 1 1 2
2 1 2 1 0 1 1 2 0 2
2 2 2 2 1 0 1 1 2 0
1 2 1 2 0 2 2 1 0 1
1 1 1 1 2 0 2 2 1 0
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 64/62
Wielowartościowe kody BCH
definicja
Niech {c(x)} stanowi zbiór wielomianów stopnia nie
większego niż n - 1 o współczynnikach z ciała oraz niech: m,
d i m0 będą pewnymi liczbami naturalnymi, takimi że:
0 d" m0 d" qm -1
q = pc
c - liczba naturalna;
d d" qm -1
Jeśli dowolny wielomian c(x)"{c(x)} ma jako
m0 m0 +1 m0 +d -2
pierwiastki kolejne d - 1 elementów ciała : ą , ą , K , ą ,
to zbiór {c(x)} jest zbiorem wielomianów kodowych
q-narnego kodu BCH o długości n=qm-1.
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 65/62
Wielowartościowe kody BCH
definicja
Przedstawiona definicja wielowartościowego kodu
BCH różni się od podanej definicji p-narnego kodu BCH tylko
różnym sposobem zdefiniowania elementu pierwotnego ą,
który jest bądz
elementem pierwotnym ciała CG(pm), bądz

ciała CG(qm). 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
n-1
li
m0 d" l d" m0 + d - 2
"cą = 0,
i
i=0
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 66/62
Przykład 3.10
Wielomiany minimalne elementów ciała CG(16)
Pierwiastki
Wielomiany minimalne
sprzężone
0 x
x + 1
ą0
x2 + x + 2
ą1, ą4
x2 + x + 3
ą2, ą8
x2 + 3x + 1
ą3, ą12
x + 2
ą5
x2 + 2x + 1
ą6, ą9
x2 + 2x + 2
ą7, ą13
x + 3
ą10
x2 + 3x + 3
ą11, ą14
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 67/62
Realizacja kodów wielowartościowych
Elementy ciała rozszerzonego mają postać potęg
elementu pierwotnego i w tej postaci nie nadają się
do transmisji przez kanał telekomunikacyjny. Aby to
zapewnić nalezy przyjąć odwzorowanie zbioru
elementów ciała CG (q) na q-elementowy zbiór liczb
całkowitych dodatnich:
2 q-2
� :{0,1,ą,ą ,...,ą } {0,1,2,3,...,q -1}
x
ńł
x + 1 dla ą `" 0
x
�(ą )=
�ł
x
0 dla ą = 0
ół
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 68/62
Wielowartościowe kody BCH ..
k symboli n-k symboli
ą 1 ą2 0 0 ą ą2 0 1 1 ą ą ą2 0 1
k symboli n-k symboli
2 1 3 0 0 1 3 0 1 1 2 2 3 0 1
k symboli po c bitów
n-k symboli
10 01 11 00 00 10 11 00 01 01 10 10 11 00 01
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 69/62
Kody BCH generowane przez
elementy niepierwotne rozszerzonego
ciała Galoisa
Kody te, zwane kodami BCH generowanymi przez
niepierwotne elementy rozszerzonego ciała Galoisa,
są zdefiniowane równaniami:
 -1
j
li
cią , m0 d" l d" m0 + d - 2,
"
j
i=0
przy czym:
j
ą = ą - niepierwotny element ciała rozszerzonego,
j
- rząd elementu .

j
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 70/62
Kody Reeda-Solomona cd..
Kody Reeda-Solomona stanowią szczególny przypadek
niebinarnych kodów BCH. Definicję kodu Reeda-Solomona (RS),
j
generowanego przez element ą ciała CG(q) możemy sprowadzić
do równań o postaci
n-1
li
= 0, m0 d" l d" m0 + dmin - 2
"cą j
i
i=0
przy czym dmin jest odległością minimalną kodu, a n - długością
ciągów kodowych.
Wartość n określa zależność:
q -1
n =
NWP(q -1, j)
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 71/62
Kody Reeda-Solomona cd..
Kod RS przystosowany do korekcji t błędów ma następujące
parametry:
n = 2m -1[syboli]= m(2m -1)[bitów]
Długość bloku:
Długość wiadomości: k [syboli]= mk [bitów]
Liczba symboli kontrolnych:
r [syboli]= n - k [symboli]
d [syboli]= 2t +1
Minimalna odległość
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 72/62
Kody Fire'a
Kod Fire'a jest to kod cykliczny generowany przez
wielomian o postaci:
g(x) = (xc +1) p(x)
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( 2m).
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 73/62
Kody Fire'a
Parametry kodu Fire a:
-długość ciągu kodowego n = NWW(,c)
-ilość pozycji informacyjnych
k = n - m - c
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 l1 i l2, spełniających warunki:
l1 d" l2, l1 d" m, l1 + l2 d" c +1;
koryguje krótszą z tych serii.
Kodowanie i kryptografia
Robert Borowiec
Wykład VI, strona 74/62