W14 Kodowanie i Kryptografia kody ...

[ Pobierz całość w formacie PDF ]
Kodowanie i kryptografia
Kody cykliczne
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki
pokój 908, C-5
tel. 3203083
e-mail:
robert.borowiec@ita.pwr.wroc.pl
www:
lstwww.ita.pwr.wroc.pl/
~
RB/
Wykład V
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
Robert Borowiec
Kodowanie i kryptografia
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.
Robert Borowiec
Kodowanie i kryptografia
Wykład V, strona 3/62
Przesunięcie cykliczne
ciąg kodowy
v
v
n-1
v
n-2
...
...
v
3
v
2
v
1
v
0
v
(
j
)
przesunięty ciąg kodowy o
j
pozycji w lewo
v
n-j-1
v
n-j-2
...
v
1
v
0
v
n-1
... v
n-1
Robert Borowiec
*
Kodowanie i kryptografia
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
zachodzi
cc
∈
{ }
oraz
j
=
12
,,...,
n
−
1
c
( )
j
∈
{
c
Robert Borowiec
Kodowanie i kryptografia
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
∑
1
n
−
()
F
v
≡
v x
i
i
io
=
v
()
=
v
x
n
−
1
+
v
x
n
−
2
+
⋅
⋅
⋅
+
v
x
1
+
v
x
0
n
−
n
−
2
1
0
Robert Borowiec
*
Kodowanie i kryptografia
Wykład V, strona 6/62
x
1
Interpretacja ciągu kodowego
Robert Borowiec
Kodowanie i kryptografia
Wykład V, strona 7/62
Operacja równoważna do przesunięcia
cyklicznego
Dochodzimy do zależności
x
ν
(
x
)
ν
(
j
)
(
x
)
=
q
(
x
)
+
x
n
+
1
x
n
+
1
z której wynika , że
v
()
() ( )
j
x
=
R
[ ]
j
v
x
x
n
+
przy czym
R
fx
•
()
[]
jest resztą z podziału [•] przez
f
(
x
) modulo
f
(
x
).
Robert Borowiec
Kodowanie i kryptografia
Wykład V, strona 8/62
j
x
Przykład 3.1
Na wyznaczenie przesuniętego ciągu
kodowego
Robert Borowiec
Kodowanie i kryptografia
Wykład V, strona 9/62
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
wielomianu
g
(
x
), a więc
( +
x
n
1
( +
n
1
*
() (
{}
c
(
x
)
=
a
( ) ( )
⋅
g
x
i spełniony jest warunek
R
[
x
n
+
1
=
0
g
(
x
)
Robert Borowiec
Kodowanie i kryptografia
Wykład V, strona 10/62
x
cx cx
∈
x
[ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

diabelki.xlx.pl