Teoria informacji
i kodowanie
Wykład nr 10
prof. dr hab. inż. Andrzej Pach
Plan wykładu
Istotne twierdzenia
Pierścień wielomianów
Wykrywanie błędów za pomocą kodów
cyklicznych  kody CRC
Korekcja błędów pojedynczych 
cykliczny kod Hamminga
Teoria informacji i kodowanie
Wykład nr 9 2
Podstawowe definicje
Niech x = (x1, x2,.... Xn-1, xn) będzie ciągiem kodowym, wówczas ciąg
x = (xn, x1 ,x2,...., Xn-1) określamy cyklicznym przesunięciem
ciągu o jedną pozycje w prawo
Kod blokowy K o parametrach (n,k) jest kodem cyklicznym,
jeśli:
1. Jest kodem liniowym
2. Dla każdego ciągu kodowego jego cykliczne przesunięcie w
prawo jest ciągiem kodowym
Teoria informacji i kodowanie
Wykład nr 9 3
Kod cykliczny  Istotne twierdzenie
Twierdzenie: wielomian generujący g(x)
stopnia minimalnego n  k kodu
cyklicznego o parametrach (n,k) jest
dzielnikiem wielomianu xn + 1:
g(x)k(x) = xn +1 lub (xn +1) mod g(x) = 0
Przykład:
g(x) = x3 + x2 +1
Kod o parametrach (7,4) i wielomianie generującym
jest kodem cyklicznym, gdyż:
(x7 +1) : (x3 + x2 +1) = x4 + x3 + x2 +1 = k(x)
Teoria informacji i kodowanie
Wykład nr 9 4
Twierdzenie 1
c
Wielomian
x2 -1 +1 jest podzielny przez:
1. Każdy wielomian pierwotny stopnia c
2. Każdy wielomian pierwszy stopnia c
3. Każdy wielomian pierwszy, którego stopień jest dzielnikiem liczby c
Zatem, to jest dla długości ciągów kodowych n=1,3,7,15,31,63,127,...
Przez wielomian pierwszy stopnia c rozumiemy wielomian, który nie jest podzielny
przez żaden wielomian niższego stopnia, za wyjątkiem wielomianu stopnia 0, jakim jest
wielomian równy 1.
Wielomian pierwotny stopnia c to taki wielomian pierwszy, którego rząd jest równy 2c-
1
.
Rzędem wielomianu g(x) nazywamy najmniejszą liczbę c taką, że wielomian x + 1 jest
podzielny przez g(x).
Teoria informacji i kodowanie
Wykład nr 9 5
Pierścień
Pierścieniem nazywamy zbiór R, na którym określone są dwa działania:
dodawanie (#) i mnożenie (*), przy czym :
1) # i * są działaniami łącznymi
2) istnieje element neutralny (moduł) należący do R
3) istnieje element symetryczny należący do R
4) obowiązuje rozdzielność, tzn. dla dowolnych a, b, c " U zachodzi:
a * (b # c) = a * b # a * c
(a # b) * c = a * c # b * c
5) istnieje operacja odwrotna do dodawania  odejmowanie
Jeżeli # i * są przemienne, to pierścień nazywamy przemiennym.
Teoria informacji i kodowanie
Wykład nr 9 6
Iloczyn wielomianów
Iloczyn dwóch wielomianów tworzymy w sposób
następujący:
1) mnożymy wielomiany w sposób określony poprzednio i jeśli stopień
otrzymanego wielomianu nie jest większy od n-1, to otrzymamy wynik
przyjmiemy za ostateczny;
2) Jeśli stopień otrzymanego wielomianu jest równy lub większy od n,
to otrzymany rezultat dzielimy przez wielomian xn+1 i resztę
(stopnia d" n -1
) uważamy za wynik mnożenia
Teoria informacji i kodowanie
Wykład nr 9 7
Przykład mnożenia wielomianów
Niech długość ciągu kodowego wynosi cztery (n=4):
1 0 1 1 Zatem dzielimy: 1 1 1 0 1 0 : 1 0 0 0 1 = 1 1
*0 1 1 0 1 0 0 0 1
0 0 0 0 1 1 0 0 0
1 0 1 1 1 0 0 0 1
1 0 1 1 1 0 0 1  reszta
1 1 1 0 1 0 - za duży stopień !
Czyli: (1 0 1 1) * (0 1 1 0) = 1 0 0 1
Teoria informacji i kodowanie
Wykład nr 9 8
Przykład
Mamy dany kod cykliczny (7,4) o wielomianie generującym
g(x) = x3 + x2 +1
df df
u1(x) =1101 , x1(x) =(1101) �" (1101) = 1010001
df df
u2 (x) =1110 , x2(x) =(1110) �" (1101) = 1000110
x1(x)�" x2(x)
Pomnóżmy zgodnie z ostatnio podaną definicją mnożenia:
1 0 1 0 0 0 1
1 0 0 0 1 1 0
1 0 1 0 0 0 1 0
1 0 1 0 0 0 1
1 0 1 0 0 0 1 _______
1 0 1 0 1 1 0 1 0 0 1 1 0
Teoria informacji i kodowanie
Wykład nr 9 9
Przykład cd.
i podzielmy 1 0 1 0 1 1 0 1 0 0 1 1 0 : 1 0 0 0 0 0 0 1 = 1 0 1 0 1 1
1 0 0 0 0 0 0 1
0 1 0 1 1 0 0 0 0 1 1 0
1 0 0 0 0 0 0 1
0 1 1 0 0 0 1 1 1 0
1 0 0 0 0 0 0 1
1 0 0 0 1 1 0 0
1 0 0 0 0 0 0 1
0 0 0 1 1 0 1
df
czyli
x1(x) �" x2 (x) = 0001101
Iloczyn powyższy jest także ciągiem kodowym, gdyż:
.
x1(x)* x2 (x)
= 1
g(x)
Teoria informacji i kodowanie
Wykład nr 9 10
Twierdzenie 2
Zbiór słów kodowych {X} dowolnego kodu cyklicznego
wraz z określonymi poprzednio operacjami # i * tworzy
pierścień przemienny
Teoria informacji i kodowanie
Wykład nr 9 11
Ideał
Ideałem nazywamy podzbiór pierścienia wszystkich wielomianów, które
są krotnościami pewnego wielomianu g(x)
, który nazywamy wielomianem
generującym kod.
W szczególnym przypadku, gdy przyjmiemy:
1) g(x) a" 0 , to ideał składa się tylko z jednego wielomianu równego 0,
2) , to ideał składa się ze wszystkich elementów pierścienia
g(x) a" 1
Można udowodnić że:
Jeżeli deg[g(x)] = n - k to ideał składa się dokładnie z 2k elementów
Teoria informacji i kodowanie
Wykład nr 9 12
Rozkład pierścienia wielomianów
na klasy reszt względem ideału
Pierwszy wiersz stanowi ideał, a element pierwszy jest elementem zerowym.
Maksymalna liczba reszt może wystąpić jedynie w przypadku, gdy wielomian
g(x)
jest nierozkładalny, czyli jest podzielny jedynie przez siebie i
Teoria informacji i kodowanie
wielomian równy 1.
Wykład nr 9 13
Przykład
g(x) = x2 +1
Niech k=2 i . Ponieważ deg[g(x)] = 2 , stąd.
n e" 4
Dla n=4 mamy kod cykliczny, gdyż
(x4 +1) : (x2 +1) = x2 +1
W praktyce jednak kodowanie :
( )
w x, x = xn-ku(x)+ r(x)
gdzie r(x) jest resztą z dzielenia xn-ku(x) przez g(x).
Teoria informacji i kodowanie
Wykład nr 9 14
Wykrywanie błędów przez
kody cykliczne
Reguła dekodowania:
z(x)= 0
w(x, x)
y(x)= dla
z(x)`" 0
?
Teoria informacji i kodowanie
Wykład nr 9 15
Dekoder dla kodu systematycznego
wydzielanie reszty z dzielenia y( )/g( ),
x x
porównywanie pozycja po pozycji z odebraną resztą - porównanie reszt
następuje w sumatorze S1
Teoria informacji i kodowanie
Wykład nr 9 16
Wykrywanie błędów pojedynczych
Jeśli wystąpił błąd pojedynczy, to wielomian
z(x) = xi-1,i = 1,2,& n,
nie powinien być podzielny przez wielomian generujący g(x).
Można udowodnić, że g(x) = x + 1 jest wielomianem
najniższego stopnia, spełniającym ten warunek. W tym
przypadku mamy, że
r(x)=0 or r(x)=1
Zatem pierścień wielomianu składa się z:
" ideału
" zbioru wielomianów, które podczas dzielenia przez
g(x) dają resztę r(x) = 1
Teoria informacji i kodowanie
Wykład nr 9 17
Przykład
Niech k = 2, wtedy g(x) = x + 1 i n = 3; kod (3,2)
Teoria informacji i kodowanie
Wykład nr 9 18
Kody CRC
Cyclic Redundancy Check
Kody cykliczne są nadzwyczaj dobrze przystosowane do
wykrywania błędów ponieważ:
1. Mogą być zaprojektowane w taki sposób, aby można
było wykryć kombinacje najbardziej
prawdopodobnych.
2. Techniczna realizacja koderów i dekoderów jest
stosunkowo łatwa.
Kod cykliczny używany do wykrywania błedów jest
określany często jako kod CRC (cyclic redundancy
check).
Teoria informacji i kodowanie
Wykład nr 9 19
Definicja paczki błedów
Przez paczkę błędów (error burst) o długości l
w odebranym n-bitowym ciągu rozumiemy
sekwencję l bitów, z których pierwszy i ostani
oraz dowolna liczba bitów pomiędzy nimi
została odebrana z błędami.
Na przykład, w telekomunikacji bezprzewodowej, błędy
powstałe na skutek wielościeżkowej propagacji, nie są
niezależne i pojawiają się w paczkach.
Teoria informacji i kodowanie
Wykład nr 9 20
Właściwości kodów CRC
Binarne kody CRC o parametrach (n,k) mają zdolności do
wykrywania następujących typów błędów:
1. Wszystkich paczek błędów o długości n  k lub mniejszej.
2. Części paczek błędów o długości równej n  k +1.
3. Części paczek błędów o długości większej niż n  k +1.
4. Wszystkich kombinacji dmin  1 (lub mniej) błędów.
5. Wszystkich typów błędów o krotności nieparzystej, jeśli wielomian
generujący g(x) kodu ma parzystą liczbę niezerowych
współczynników.
Teoria informacji i kodowanie
Wykład nr 9 21
Przykłady kodów CRC
Teoria informacji i kodowanie
Wykład nr 9 22
Korekcja błędów
pojedynczych
Istnieje cycliczny kod Hamminga o parametrach
(2c-1, 2c -c -1) i dmin = 3, gdzie c jest liczbą całkowitą.
Jest on generowany przez wielomian pierwotny stopnia
generated c.
c g(x) n k
2 x2+x+1 3 1
3 x3+x+1 7 4
4 x4+x+1 15 11
5 x5+x+1 31 26
Istnieje także wydłużony kod Hamminga o
parametrach (2c-1, 2c-c-1) i dmin = 4.
Teoria informacji i kodowanie
Wykład nr 9 23
Przykład: dekoder dla kodu
Hamminga (7,4)
Teoria informacji i kodowanie
Wykład nr 9 24
Przykład: dekoder dla kodu
Hamminga (7,4), cd.
Teoria informacji i kodowanie
Wykład nr 9 25
Przykład: dekoder dla kodu
Hamminga (7,4), cd.
Teoria informacji i kodowanie
Wykład nr 9 26
Kody o maksymalnej długości
Dla każdej liczby całkowitej c e" 3, istnieje kod o maksymalnej
długości o następujących parametrach:
" Długość ciągu kodowego: n = 2c -1
" Liczba bitów informacyjnych: k = c
" Minimalna odległość Hamminga: dmin = 2c -1
Kody o maksymalnej długości są generowane przez
wielomiany o postaci
gdzie g(x) jest wielomianem pierwotnym stopnia c.
Teoria informacji i kodowanie
Wykład nr 9 27
Przykład
Znalez
ć kod o dmin = 8 i k =4.
8=2c-1 �! c  1 = 3 �! c =4=k
n =2c  1 = 16 1=15
Kod ma zatem parametry (15,4) i wielomian:
Zatem wielomian generujący dla tego kodu ma postać:
Teoria informacji i kodowanie
Wykład nr 9 28