Kodowanie i kryptografia

Kodowanie i kryptografia

Kody cykliczne

Kody cykliczne

dr Robert Borowiec

Politechnika Wrocławska

Instytut Telekomunikacji i Akustyki

pokój 908, C-5

tel. [phone]

e-mail: [e-mail]

www: lstwww.ita.pwr.wroc.pl/

~

RB/

Wykład V

6-godzin

Plan wykładu

Plan wykładu

Historia

Przesunięcie cykliczne

Sposoby kodowania informacji

Tworzenie kodu

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 2/62

Tworzenie kodu

Kody dualne

Metryka przestrzeni

Zdolność korekcyjna kodu

Przykłady wybranych kodów liniowych

Wprowadzenie do kodów cyklicznych

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

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 3/62

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.

Przesunięcie cykliczne

Przesunięcie cykliczne

v

n-1

v

n-2

...

...

v

3

v

2

v

1

v

0

ciąg kodowy

v

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 4/62

v

n-j-1

v

n-j-2

...

v

1

v

0

v

n-1

...

v

n-1

v

(j)

przesunięty ciąg kodowy o j pozycji w lewo

Definicja kodu cyklicznego

Definicja kodu cyklicznego

w oparciu o cykliczne przesunięcie

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

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 5/62

1. zbiór {c} jest grupą abelową względem operacji

dodawania n-pozycyjnych ciągów;

2. dla dowolnego

zachodzi

{ }

c

c

∈

=

−

oraz j

n

1 2

1

, ,...,

( )

{ }

c

c

∈

j

Interpretacja ciągu kodowego

Interpretacja ciągu kodowego

Wprowadza się przekształcenie

(

)

v =

−

−

ν ν

ν ν

n

n

,

..., ,

1

2

1

0

Niech v będzie n-pozycyjnym ciągiem kodowym

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 6/62

( )

F

v x

i

i

i o

n

v ≡

=

−

∑

1

Wprowadza się przekształcenie

( )

0

0

1

1

2

2

1

1

x

v

x

v

x

v

x

v

x

v

n

n

n

n

+

+

⋅

⋅

⋅

+

+

=

−

−

−

−

Interpretacja ciągu kodowego

Interpretacja ciągu kodowego

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 7/62

Operacja równoważna do przesunięcia

Operacja równoważna do przesunięcia

cyklicznego

cyklicznego

1

)

(

)

(

1

)

(

)

(

+

+

=

+

n

j

n

j

x

x

x

q

x

x

x

ν

ν

Dochodzimy do zależności

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 8/62

( )

( )

( )

[

]

x

v

x

R

x

v

j

x

j

n

1

+

=

1

1

+

+

x

x

z której wynika , że

przy czym

jest resztą z podziału [•] przez f(x) modulo

f(x).

( )

[ ]

R

f x

•

Przykład 3.1

Przykład 3.1

Na wyznaczenie przesuniętego ciągu

Na wyznaczenie przesuniętego ciągu

kodowego

kodowego

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 9/62

Kod cykliczny

Kod cykliczny

Wielomian oraz jego składowe odgrywają
istotną rolę w generacji kodów cyklicznych.
W algebrze wielomianów modulo wielomian
zbiór wielomianów {c(x)} może stanowić zbiór
ciągów kodowych, gdy dowolny wielomian

jest wielokrotnością pewnego

)

1

(

+

n

x

)

1

(

+

n

x

( )

( )

{ }

c x

c x

∈

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 10/62

jest wielokrotnością pewnego

wielomianu g(x), a więc

i spełniony jest warunek

( )

( )

{ }

c x

c x

∈

0

]

1

[

)

(

=

+

n

x

g

x

R

( ) ( )

x

g

x

a

x

c

⋅

=

)

(

Wielomian generujący

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
zachodzi

( )

( )

{ }

c x

c x

∈

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 11/62

0

)]

(

[

)

(

=

x

c

R

x

g

( ) ( )

x

g

x

h

x

c

⋅

=

)

(

Wielomian generujący

Wielomian generujący

Właściwości wielomianu g(x)

Wielomian g(x) nazywamy wielomianem
generującym kod cykliczny , Stopień wielomianu g(x)
określa liczbę pozycji kontrolnych kodu.

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 12/62

( )

k

n

r

x

g

−

=

=

deg

0

]

1

[

)

(

=

+

n

x

g

x

R

wielomian g(x) jest
składową wielomianu

)

1

(

+

n

x

Macierzowe przedstawienie kodów

Macierzowe przedstawienie kodów

cyklicznych

cyklicznych

Przyporządkujmy wielomianowi

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

x

g x

k

(

)

( )

−1



 g

-oznacza ciąg

g

(

)

− j

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 13/62

)

1

(

)

(

)

(

































=

+

−

+

−

−

k

k

g

g

g

g

G

2

1

M

-oznacza ciąg

przesunięty o j
pozycji w prawo, np.:
c

= 0101100

c

(-2)

= 0001011

g

(

)

− j

Kod dualny kodu cyklicznego

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ć

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 14/62

postać

0

)]

(

)

(

[

)

1

(

=

+

x

x

c

R

n

x

ν

Macierz generująca kod dualny

Macierz generująca kod dualny

(macierz kontrolna kodu)

(macierz kontrolna kodu)

Wielomian generujący cykliczny kod dualny (n, n-k) określa
zależność

( )

( )

x

g

x

x

q

n

1

+

=



 q

Macierz H generująca kod dualny ma postać

)

(

'

1

x

q

r−

≡ x

q

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 15/62

,

































=

+

−

+

−

−

)

1

(

)

2

(

)

1

(

r

r

q

q

q

q

H

M

)

(

'

1

x

q

r−

≡ x

q

)

(

' x

q

Wielomian q(x) o odwróconej
kolejności współczynników.

Jeżeli q(x)=100100,

to q’(x)=001001.

)

(

j

−

q

oznacza ciąg q przesunięty o
j pozycji w prawo

Przykład 3.2

Przykład 3.2

Kod cykliczny

Kod cykliczny

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 16/62

Macierz generująca systematyczny kod

Macierz generująca systematyczny kod

cykliczny (n, k)

cykliczny (n, k)





















=

−

−

n

n

u

u

u

I

G

2

1

k

M

]

[

)

(

i

x

g

i

x

R

=

u

Przykład:

Dla kodu cyklicznego (7,4)
generowanego przez wielomian

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 17/62









=

−

r

k

n

u

u

u

n 1

6

−

=

⇔

=

+ ⇔

R

x

x

g x

( )

[

]

,

6

2

1

101

,

111

1

]

[

2

5

)

(

5

⇔

+

+

=

⇔

=

−

x

x

x

R

x

g

u

u

2

n

u

u

n 3

−

=

⇔

=

+ ⇔

4

4

2

110

R

x

x

x

g x

( )

[

]

,

u

u

n 4

−

=

⇔

=

+ ⇔

3

3

1

011

R

x

x

g x

( )

[

]

.

generowanego przez wielomian

mamy

g x

x

x

( ) =

+ +

3

1

Skrócony kod cykliczny

Skrócony kod cykliczny

Kody cykliczne istnieją tylko dla niektórych wartości
n, na przykład:

1

−

=

m

p

n

1

2

+

+

=

m

m

p

p

n

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 18/62

przy czym p jest liczbą pierwszą, a m - liczbą
naturalną

1

2

+

+

=

m

m

p

p

n

Skrócony kod cykliczny

Skrócony kod cykliczny

(kod pseudocykliczny)

(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

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 19/62

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)}

Przykład 3.3

Przykład 3.3

Skrócony kod cykliczny

Skrócony kod cykliczny

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 20/62

Skrócony kod cykliczny

Skrócony kod cykliczny

(właściwości)

(właściwości)

1. W skróconych kodach cyklicznych nie jest

spełniony warunek, że dla dowolnego

zachodzi

{ }

1

'

,...,

2

,

1

−

=

∈

n

j

oraz

c

c

( )

{ }

c

c

∈

j

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 21/62

2. Oznaczenie kodu skróconego ma postać [n',k-(n-n')]

3. Jeżeli wyjściowy kod (n, k) ma odległość d

min

, to

odległość minimalna d’

min

kodu skróconego ma

odległość niemniejszą niż d

min

.

Kodowanie za pomocą kodów cyklicznych

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

( ) ( )

x

g

x

h

x

c

⋅

=

)

(

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 22/62

( ) ( )

x

g

x

h

x

c

⋅

=

)

(

2. Uzyskanie systematycznego kodu cyklicznego zapewnia

następująca reguła kodowania

( )

[

]

c x

x h x

R

x h x

r

g z

r

( )

( )

( )

=

−

Przykład 3.11

Przykład 3.11

Przykład wyznaczenia ciągu kodowego

Przykład wyznaczenia ciągu kodowego

systematycznego

systematycznego

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 23/62

Przykład 3.11

Przykład 3.11

1 0 0 0 1 0 0 1 0 1

1 0 0 0 1 0 0 1 0 1

9

x

5

x

+

1

2

x

+

+

( )

x

h

( )

x

h

x

5

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 24/62

1 0 0 0 1 0 0 1 0 1 0 0 0 1 1

14

x

10

x

+

5

x

7

x

+

+

14

x

10

x

+

5

x

7

x

+

+

x

1

+

+

( )

x

c

( )

x

h

x

5

( )

( )

[

]

x

h

x

R

x

g

5

Dzielenie wielomianów

Dzielenie wielomianów

g

r

g

0

g

1

g

r-1

Wyjście

Układ od dzielenia dowolnego wielomianu przez
wielomian

g x

g x

g

x

g x

g

r

r

r

r

( ) =

+

+ +

+

−

−

1

1

1

0

K

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 25/62

Wejście

P

P

P

Przykład dzielenia wielomianów

Przykład dzielenia wielomianów

Układ od dzielenia wielomianu h(x) przez wielomian g(x)

g( ) =

5

x

x

x

x

+

+

+

4

2

1

P

0

P

1

P

2

P

3

P

4

+

+

+

Wej.

Wyj.

1

)

(

2

5

9

+

+

+

=

x

x

x

x

h

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 26/62

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:

5

7

10

14

5

)

(

x

x

x

x

x

h

x

+

+

+

=

⋅

Przykład dzielenia wielomianów

Przykład dzielenia wielomianów

Takt

Wejście

Zawartość rejestru

Wyjście Wielomian

P

0

P

1

P

2

P

3

P

4

1

1

0

0

0

0

0

0

x

14

2

0

1

0

0

0

0

0

x

13

3

0

0

1

0

0

0

0

x

12

4

0

0

0

1

0

0

0

x

11

5

1

0

0

0

1

0

0

x

10

6

0

1

0

0

0

1

1

x

9

7

0

1

1

1

0

1

1

x

8

8

1

1

1

0

1

1

1

x

7

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 27/62

8

1

1

1

0

1

1

1

x

7

9

0

0

1

0

0

0

0

x

6

10

1

0

0

1

0

0

0

x

5

11

0

1

0

0

1

0

0

x

4

12

0

0

1

0

0

1

1

x

3

13

0

1

0

0

0

1

1

x

2

14

0

1

1

1

0

1

1

x

1

15

0

1

1

0

1

1

1

x

0

Reszta

1

1

0

0

0

Wielomian

x

0

x

1

x

2

x

3

x

4

Schemat ogólny kodera cyklicznego

Schemat ogólny kodera cyklicznego

g

r

g

0

g

r-2

g

r-1

1

2

K

2

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 28/62

g

0

g

r-2

g

r-1

P

r-1

P

0

P

r-2

1

2

K

1

Wejście

Wyjście

2

Schemat kodera systematycznego

Schemat kodera systematycznego

(15,10)

(15,10)

http://www.ee.uwa.edu.au/~roberto/teach/it
c314/java/CRC/crc.html

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 29/62

lub z dyskietki Koder cykliczny\Koder cykliczny.htm

Dekodowanie kodów cyklicznych

Dekodowanie kodów cyklicznych

Metody detekcji błędów

 wyznaczenie syndromu S(y) za pomocą macierzy H

T

 wyznaczenie reszty z dzielenia

( )

( )

( )

[

]

x

y

R

x

r

x

g

=

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 30/62

 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

( )

( )

( )

[

]

x

y

R

x

r

x

g

=

Metoda polowania na błędy

Metoda polowania na błędy

Wprowadzenie

Wprowadzenie

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 31/62

Metoda polowania na błędy

Metoda polowania na błędy

Wyznaczamy resztę z dzielenia

Obliczamy wagę Hamminga wektora r

( )

( )

( )

[

]

r

⇒

=

x

y

R

x

r

x

g

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 32/62

 jeżeli , to ilość błędów jest większa niż

zdolność korekcyjna lub błędy nie leżą w obszarze
bitów parzystości

 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

( )

t

w

H

>

r

( )

t

w

H

≤

r

Metoda polowania na błędy

Metoda polowania na błędy

na przykładzie kodu BCH(15, 7, 2)

na przykładzie kodu BCH(15, 7, 2)

1 1 1 1 0 0 1 0 1 1 0 1 0 1 0

1 0 1 1 0 1 1 0 1 1 0 1 0 1 0

c

y

(6)

r

0 0 0 0 0 0 0 0

Transmisja

r

0 0 0 0 0 1 1 1

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 33/62

1 0 1 1 0 1 0 1 0 1 0 1 1 0 1

y

(6)

r

0 0 0 1 0 0 0 1

0 0 0 1 0 0 0 1

1 0 1 1 0 1 0 1 0 1 1 1 1 0 0

c*

(6)

1 1 1 1 0 0 1 0 1 1 0 1 0 1 0

c*

Przykład cd..

Przykład cd..

g x

x

x

x

x

( )

.

=

+

+

+

+

8

7

6

4

1

Parametry kodu BCH (15, 7, 2), to

n=15, k=7, t=2

Wielomian generujący kod BCH (15, 7, 2)

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 34/62

g x

x

x

x

x

( )

.

=

+

+

+

+ 1

Dekoder z sieci lub z dyskietki

Przegląd kodów cyklicznych

Przegląd kodów cyklicznych

Kody BCH

 Binarne kody BCH
 Niebinarne kody BCH
 Wielowartościowe kody BCH

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 35/62

 Wielowartościowe kody BCH
 Kody BCH generowane przez elementy niepierwotne

rozszerzonego ciała Galoisa

Kody HAMMINGA

Kody REEDA-SOLOMONA

Kody FIRE'A

KODY CYKLICZNE

KODY CYKLICZNE

Wielomian generujący kod cykliczny (n, k)
o długości n=p

m

-1 można przedstawić w

postaci iloczynu pewnych wielomianów
pierwszych stopnia nie większego niż m

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 36/62

pierwszych stopnia nie większego niż m

g x

x

x

( )

( )

( )

.

=

⋅

⋅

µ

µ

1

2

L

Przykład 3.4

Przykład 3.4

Związek między ciałem Galoisa, a

Związek między ciałem Galoisa, a

pierwiastkami wielomianu

pierwiastkami wielomianu

generującego

generującego

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 37/62

Przykład 3.4 cd..

Przykład 3.4 cd..

Reprezentacja ciała CG(2

3

) generowanego przez

wielomian pierwotny

p x

x

x

( ) =

+ +

3

1

Element

ciała

Reprezentacja

potęgowa

Reprezentacja

wielomianowa

Reprezentacja

binarna

a

α

x

010

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 38/62

a

1

α

x

010

a

2

α

2

x

2

100

a

3

α

3

x + 1

011

a

4

α

4

x

2

+ x

110

a

5

α

5

x

2

+ x + 1

111

a

6

α

6

x

2

+ 1

101

a

7

α

7

=

α

0

=1

1

001

a

8

nie istnieje

0

000

Definicja kodu BCH

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, m

0

i d będą liczbami naturalnymi, takimi

że:

1

,

1

0

0

−

≤

−

≤

≤

m

m

p

d

p

m

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 39/62

Jeśli wielomian c(x)∈{c(x)} ma jako kolejne pierwiastki d - 1
elementów ciała CG(p

m

):

to zbiór {c(x)} jest zbiorem wielomianów kodowych

p-narnego kodu BCH, którego odległość minimalna

α

α

α

m

m

m

d

0

0

0

1

2

,

,

,

,

+

+ −

K

d

d

=

min

Konstruowanie wielomianu generującego kodu BCH

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(p

m

), które stanowią jego pierwiastki.

Jeśli

więc

przez

oznaczymy

wielomian

minimalny

i-tego elementu a

i

ciała CG(p

m

), to

( )

x

i

ψ

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 40/62

( )

( )

( )

( )

[

]

x

x

x

x

g

d

m

m

m

2

1

0

0

0

,....,

,

NWW

−

+

+

=

ψ

ψ

ψ

Dla przypomnienia elementy a

i

ciała CG(p

m

) powstają

poprzez podniesienie do potęgi i-tej elementu pierwotnego

α

, tak więc a

i

=

α

i

.

Wielomiany minimalne

Wielomiany minimalne--przypomnienie

przypomnienie

Wielomiany minimalne elementów

α

i

ciała wyznacza się z

zależności

( )

( )













>

−

−

=

∏

.

1

dla

)

(

1,

=

i

dla

)

(

0,

=

i

dla

1

i

x

x

p

x

x

i

j

p

i

i

λ

α

ψ

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 41/62

( )







>

−

∏

=

.

1

dla

)

(

0

i

x

j

p

i

α

p(x) wielomian pierwotny generujący ciało CG(p

m

),

α

element pierwotny ciała CG(p

m

),

λ

i

rząd i-tego elementu ciała CG(p

m

).

Przykład 3.6

Przykład 3.6

Wielomiany minimalne

Wielomiany minimalne

ciała CG(2

ciała CG(2

3

3

))

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 42/62

Przykład 3.6

Przykład 3.6

Wielomiany minimalne

Wielomiany minimalne

ciała CG(2

ciała CG(2

3

3

))

Element ciała

Wielomian

minimalny

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 43/62

0

α

1

+

x

1

α

,

2

α

,

4

α

1

3

+

+ x

x

3

α

,

5

α

,

6

α

1

2

3

+

+ x

x

Binarne kody BCH

Binarne kody BCH

konstrukcja kodu (

konstrukcja kodu (n

n

,

, k

k

,

, tt))

1.

Symbole są określone w ciele pierwotnym CG(2).

2.

Liczba bitów n=(2

m

-1) określa ciało rozszerzone CG(2

m

), z

którego będą pochodziły wielomiany minimalne.

3.

Wybieramy m

0

.

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 44/62

0

4.

Jeśli m

0

=1, to d jest nieparzyste i wynosi d=d

min

=2·t+1, gdy

m

0

=0, to d jest parzyste.

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)

1

,

1

0

0

−

≤

−

≤

≤

m

m

p

d

p

m

Przykład 3.7

Przykład 3.7

Wielomian generujący kod

Wielomian generujący kod

BCH (15, 7,2)

BCH (15, 7,2)

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 45/62

Przykład 3.7

Przykład 3.7

Pierwiastki

sprzężone

Wielomian

minimalny

0

x

Tablica 9. Wielomiany minimalne elementów ciała CG(2

4

)

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 46/62

0

x

α

α

α

α

0000

x+1

α

α

α

α

1111

, α

, α

, α

, α

2222

, α

, α

, α

, α

4444

, α

, α

, α

, α

8888

x

4

+x+1

α

α

α

α

3333

, α

, α

, α

, α

6666

, α

, α

, α

, α

9999

, α

, α

, α

, α

12

12

12

12

x

4

+x

3

+x

2

+x+1

α

α

α

α

5555

, α

, α

, α

, α

10

10

10

10

x

2

+x+1

α

α

α

α

7777

, α

, α

, α

, α

11

11

11

11

, α

, α

, α

, α

13

13

13

13

, α

, α

, α

, α

14

14

14

14

x

4

+x

3

+1

Przykład 3.8

Przykład 3.8

Wielomian generujący kod

Wielomian generujący kod

BCH (15, 5, 3)

BCH (15, 5, 3)

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 47/62

Kody Hamminga

Kody Hamminga

Kod cykliczny nazywamy kodem Hamminga, jeżeli jego
wielomian generujący jest wielomianem pierwotnym ciała
CG(p

m

)

( )

( )

x

p

x

g

=

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 48/62

Cykliczny kod Hamminga generowany przez wielomian
stopnia m ma następujące parametry

1

2 −

=

m

n

1

2

−

−

=

m

k

m

3

min

=

= d

d

1

=

t

Niebinarne kody BCH

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=p

m

-1 [symboli]

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 49/62

n=p -1 [symboli]

Wielomian generujący kod jest określony nad ciałem CG(p) i
ma pierwiastki w ciele rozszerzonym CG(p

m

).

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.

Przykład 3.9

Przykład 3.9

Niebinarny kod BCH (8, 2, 2)

Niebinarny kod BCH (8, 2, 2)

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 50/62

Przykład 3.9

Przykład 3.9

Reprezentacja ciała CG(3

2

) generowanego przez wielomian

p x

x

x

( ) =

+ +

2

2

Element

ciała

Reprezentacja

potęgowa

Reprezentacja

wielomianowa

Reprez.

tetrarna

Wielomiany minimalne

a

1

α

x

10

)

(

2

)

(

2

1

x

p

x

x

x

=

+

+

=

ψ

a

α

2

2x

+

1

21

1

)

)(

(

)

(

2

6

2

+

=

−

−

=

x

x

x

x

α

α

ψ

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 51/62

a

2

α

2

2x

+

1

21

1

)

)(

(

)

(

2

6

2

2

+

=

−

−

=

x

x

x

x

α

α

ψ

a

3

α

3

2x

+

2

22

)

(

)

(

1

3

x

x

ψ

ψ

=

a

4

α

4

2

02

1

)

(

4

4

+

=

−

=

x

x

x

α

ψ

a

5

α

5

2x

20

2

2

)

)(

(

)

(

2

7

5

5

+

+

=

−

−

=

x

x

x

x

x

α

α

ψ

a

6

α

6

x

+

2

12

)

(

)

(

2

6

x

x

ψ

ψ

=

a

7

α

7

x

+

1

11

)

(

)

(

1

3

x

x

ψ

ψ

=

a

8

α

8

=

α

0

=1

1

01

.

2

1

)

(

)

(

0

8

+

=

−

=

=

x

x

x

x

ψ

ψ

a

9

nie istnieje

00

Przykład 3.9

Przykład 3.9

Macierz kontrolna i generująca BCH (8,2,2,)

[

]

6

2

2

P

I

G

,

1

2

2

0

2

1

1

0

2

2

0

2

1

1

0

1

=













=









0

0

0

0

0

1

1

1

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 52/62

[

]

































=

=

1

0

0

0

0

0

1

2

0

1

0

0

0

0

2

2

0

0

1

0

0

0

2

0

0

0

0

1

0

0

0

2

0

0

0

0

1

0

2

1

,

6

T

6

2

I

P

H

Przykład 3.9

Przykład 3.9

Macierz kontrolna i generująca BCH (8, 2, 2)

Ciągi

informacyjne

Ciągi kodowe BCH (8, 2, 2)

0

2

1

0

0

1

0

0

1

1

0

1

2

2

0

2

1

2

2

0

2

1

1

0

2

2

0

2

1

1

0

1

0

0

0

0

0

0

0

0

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 53/62

1

1

2

1

2

2

1

2

2

0

0

2

0

1

2

2

0

2

1

1

1

0

1

2

2

0

2

1

0

2

1

1

0

1

2

2

2

0

2

1

1

0

1

2

2

1

1

0

1

2

2

0

1

1

0

1

2

2

0

2

Wielowartościowe kody BCH

Wielowartościowe kody BCH

definicja

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 m

0

będą pewnymi liczbami naturalnymi, takimi że:

1

0

0

−

≤

≤

m

q

m

1

−

≤

m

q

d

c

p

q =

c - liczba naturalna;

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 54/62

1

−

≤

m

q

d

Jeśli dowolny wielomian c(x)∈{c(x)} ma jako

pierwiastki kolejne d - 1 elementów ciała :
to zbiór {c(x)} jest zbiorem wielomianów kodowych
q-narnego kodu BCH o długości n=q

m

-1.

,

,

,

2

1

0

0

0

−

+

+

d

m

m

m

α

α

α

,

K

c - liczba naturalna;

Wielowartościowe kody BCH

Wielowartościowe kody BCH

definicja

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ądź elementem pierwotnym ciała CG(p

m

), bądź

ciała CG(q

m

). Wspólną definicję p-narnych i q-narnych kodów

BCH można więc przedstawić w postaci układu d - 1 równań

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 55/62

BCH można więc przedstawić w postaci układu d - 1 równań
liniowych

2

,

0

0

0

1

0

−

+

≤

≤

=

∑

−

=

d

m

l

m

c

n

i

li

i

α

Przykład 3.10

Przykład 3.10

Pierwiastki

sprzężone

Wielomiany minimalne

0

x

α

0

x

+

1

α

1

,

α

4

x

2

+

x

+

2

α

2

,

α

8

x

2

+

x

+

3

Wielomiany minimalne elementów ciała CG(16)

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 56/62

α

2

,

α

8

x

2

+

x

+

3

α

3

,

α

12

x

2

+

3x

+

1

α

5

x

+

2

α

6

,

α

9

x

2

+

2x

+

1

α

7

,

α

13

x

2

+

2x

+

2

α

10

x

+

3

α

11

,

α

14

x

2

+

3x

+

3

Realizacja kodów wielowartościowych

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:

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 57/62

całkowitych dodatnich:

{

}

{

}

1

,...,

3

,

2

,

1

,

0

,...,

,

,

1

,

0

:

2

2

−

→

−

q

q

α

α

α

σ

( )







=

≠

+

=

0

0

0

1

x

x

x

dla

dla

x

α

α

α

σ

Wielowartościowe kody BCH ..

Wielowartościowe kody BCH ..

α 1 α

2

0 0 α

α

2

0 1

1

α α α

2

0

1

k symboli

n-k symboli

k symboli

n-k symboli

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 58/62

10 01 11 00 00 10 11 00 01 01 10 10 11 00 01

2 1 3 0 0 1 3 0 1 1 2

2 3 0 1

k symboli po c bitów

n-k symboli

Kody BCH generowane przez

Kody BCH generowane przez

elementy niepierwotne rozszerzonego

elementy niepierwotne rozszerzonego

ciała Galoisa

ciała Galoisa

Kody te, zwane kodami BCH generowanymi przez

niepierwotne elementy rozszerzonego ciała Galoisa,
są zdefiniowane równaniami:

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 59/62

są zdefiniowane równaniami:

przy czym:

- niepierwotny element ciała rozszerzonego,
- rząd elementu .

c

m

l

m

d

i

j

li

i

j

α

λ

=

−

∑

≤ ≤

+ −

0

1

0

0

2

,

,

α

α

j

j

=

λ

j

Kody Reeda

Kody Reeda--Solomona cd..

Solomona cd..

Kody Reeda-Solomona stanowią szczególny przypadek
niebinarnych kodów BCH. Definicję kodu Reeda-Solomona (RS),
generowanego przez element

ciała CG(q) możemy sprowadzić

do równań o postaci

α

j

2

,

0

min

0

0

1

−

+

≤

≤

=

∑

−

d

m

l

m

c

n

li

j

i

α

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 60/62

przy czym d

min

jest odległością minimalną kodu, a n - długością

ciągów kodowych.
Wartość n określa zależność:

2

,

0

min

0

0

0

−

+

≤

≤

=

∑

=

d

m

l

m

c

i

j

i

α

)

,

1

(

1

j

q

q

n

−

−

=

NWP

Kody Reeda

Kody Reeda--Solomona cd..

Solomona cd..

Kod RS przystosowany do korekcji t błędów ma następujące
parametry:

Długość bloku:

Długość wiadomości:

[

]

(

)

[

]

bitów

m

syboli

n

m

m

1

2

1

2

−

=

−

=

[

]

[

]

bitów

syboli

mk

k

=

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 61/62

Długość wiadomości:

Liczba symboli kontrolnych:

Minimalna odległość

[

]

[

]

bitów

syboli

mk

k

=

[

]

[

]

symboli

syboli

k

n

r

−

=

[

]

1

2 +

= t

d syboli

Kody Fire'a

Kody Fire'a

)

(

)

1

(

)

(

x

p

x

x

g

c

+

=

Kod Fire'a jest to kod cykliczny generowany przez
wielomian o postaci:

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 62/62

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( 2

m

).

Kody Fire'a

Kody Fire'a

Parametry kodu Fire’a:

-długość ciągu kodowego

-ilość pozycji informacyjnych

( )

c

NWW

n

,

λ

=

c

m

n

k

−

−

=

Robert Borowiec

Kodowanie i kryptografia

Wykład V, strona 63/62

-ilość pozycji informacyjnych

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 l

1

i l

2

, spełniających warunki:

koryguje krótszą z tych serii.

c

m

n

k

−

−

=

l

l

l

m l

l

c

1

2

1

1

2

1

≤

≤

+ ≤ +

,

,

;