Kodowanie i kryptografia
Kody cykliczne
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki
pokój 908, C-5
tel. [phone]
Wykład V
e-mail: [e-mail]
www: lstwww.ita.pwr.wroc.pl/~RB/
6-godzin
Plan wykładu
Historia
Przesunięcie cykliczne
Sposoby kodowania informacji
Tworzenie kodu
Kody dualne
Metryka przestrzeni
Zdolność korekcyjna kodu
Przykłady wybranych kodów liniowych
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 2/62
Wprowadzenie do 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.
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 3/62
Przesunięcie cykliczne
ciÄ…g kodowy v
vn-1 vn-2 ... ... v3 v2 v1 v0
v(j) przesunięty ciąg kodowy o j pozycji w lewo
vn-j-1 vn-j-2 ... v1 v0 vn-1 ... vn-1
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 4/62
Definicja kodu cyklicznego
w oparciu o cykliczne przesunięcie
Zbiór {c} n-pozycyjnych ciągów q-narnych 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 c " c oraz j = 12,..., n - 1
zachodzi
c( j) "{c}
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 5/62
Interpretacja ciÄ…gu kodowego
Niech v będzie n-pozycyjnym ciągiem kodowym
v = ½n-1,½n-2...,½1,½0
( )
Wprowadza się przekształcenie
n-1
F(v) a" vixi
"
i=o
v(x) = vn-1xn-1 + vn-2xn-2 + Å"Å"Å" + v1x1 + v0x0
Kodowanie i kryptografia

Robert Borowiec
Wykład V, strona 6/62
Interpretacja ciÄ…gu kodowego
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 7/62
Operacja równoważna do przesunięcia
cyklicznego
Dochodzimy do zależności
j ( j)
x ½ (x) ½ (x)
= q(x) +
xn +1 xn +1
z której wynika , że
j
v( j)(x)= Rx +1[x v(x)]
n
przy czym jest resztą z podziału [" ] przez f(x) modulo
Rf ( x)[" ]
f(x).
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 8/62
Przykład 3.1
Na wyznaczenie przesuniętego ciągu
kodowego
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 9/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 V, strona 10/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 V, strona 11/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 V, strona 12/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 V, strona 13/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 V, strona 14/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 V, strona 15/62
Przykład 3.2
Kod cykliczny
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 16/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 V, strona 17/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 V, strona 18/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 V, strona 19/62
Przykład 3.3
Skrócony kod cykliczny
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 20/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 V, strona 21/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 V, strona 22/62
Przykład 3.11
Przykład wyznaczenia ciągu kodowego
systematycznego
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 23/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 V, strona 24/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 V, strona 25/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 V, strona 26/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 V, strona 27/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 V, strona 28/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 V, strona 29/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 V, strona 30/62
Metoda polowania na błędy
Wprowadzenie

Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 31/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 V, strona 32/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 V, strona 33/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 V, strona 34/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 V, strona 35/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 V, strona 36/62
Przykład 3.4
Związek między ciałem Galoisa, a
pierwiastkami wielomianu
generujÄ…cego
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 37/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 V, strona 38/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 V, strona 39/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 V, strona 40/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 V, strona 41/62
Przykład 3.6
Wielomiany minimalne
ciała CG(23)
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 42/62
Przykład 3.6
Wielomiany minimalne
ciała CG(23)
Wielomian
Element ciała
minimalny
x + 1
Ä…0
2 4
Ä…1, Ä… , Ä… x3 + x + 1
Ä…3 , Ä…5 , Ä…6 x3 + x2 + 1
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 43/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 V, strona 44/62
Przykład 3.7
Wielomian generujÄ…cy kod
BCH (15, 7,2)
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 45/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 V, strona 46/62
Przykład 3.8
Wielomian generujÄ…cy kod
BCH (15, 5, 3)
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 47/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 V, strona 48/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 V, strona 49/62
Przykład 3.9
Niebinarny kod BCH (8, 2, 2)
Kodowanie i kryptografia
Robert Borowiec
Wykład V, strona 50/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
È (x) = (x - Ä… )(x - Ä… ) = x + 1
a2 2x + 1 21
Ä…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 V, strona 51/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 V, strona 52/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 V, strona 53/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 V, strona 54/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 V, strona 55/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 V, strona 56/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 V, strona 57/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 V, strona 58/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 V, strona 59/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 V, strona 60/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 V, strona 61/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 V, strona 62/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 V, strona 63/62