W13_Kodowanie%20i%20Kryptografia_kody%20liniowe_cale_6g.pdf

(829 KB) Pobierz
Microsoft PowerPoint - W13_Kodowanie i Kryptografia_kody liniowe_cale_6g.ppt
Kodowanie i kryptografia
Blokowe kody liniowe
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 IV
Plan wykładu
Definicja blokowego kodu liniowego
Parametry kodu blokowego
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 IV, strona 2/54
317372546.036.png 317372546.037.png 317372546.038.png 317372546.039.png 317372546.001.png 317372546.002.png 317372546.003.png
Definicja blokowego kodu liniowego
¾ Kodowanie blokowe polega na przekształceniu k -pozycyjnych
q -narnych ciągów informacyjnych h =( h 1 , h 2 ,.., h k )w n -pozycyjne
q -narne ciągi kodowe c =( c 1 , c 2 ,.., c n )
h 1 , h 2 , ...,h k
Kodowanie
c 1 , c 2 , ...,c n
Słowo informacyjne
Słowo kodowe
¾ Formalnie proces kodowania blokowego można zapisać:
h
∧
∈
{} {}
h
c
∨
∈
c
f
:
h
i
→
c
i
, przy czym
f
:
h ⇔
c
i
i
Robert Borowiec
Kodowanie i kryptografia
Wykład IV, strona 3/54
Proces kodowania blokowego
( i - 1 )
kodowania
-szy takt
i
kodowania
-ty takt
+ -szy takt
kodowania
)
k
h
( i - 1)
h
( i
)
h
( i + 1
)
c
( i - 1 )
c
( i
)
c
( i + 1
)
n
Robert Borowiec
Kodowanie i kryptografia
Wykład IV, strona 4/54
( i 1
317372546.004.png 317372546.005.png 317372546.006.png 317372546.007.png 317372546.008.png 317372546.009.png 317372546.010.png 317372546.011.png 317372546.012.png 317372546.013.png
Parametry kodu blokowego
¾ Blokowy kod nadmiarowy oznaczamy symbolem ( n , k ).
Jednoznaczne określenie kodu ( n, k ) wymaga podania
zbiorów { h }i { c } oraz funkcji f , a więc
( ) { } { }
nk
,
≡ hc
( )
, , .
f
¾ Parametry kodu blokowego
Nadmiar kodowy
Sprawność
ρ
= 1
−
k
=
−
k
η −
= 1
k
=
ρ
k
n
n
k
n
k
Robert Borowiec
Kodowanie i kryptografia
Wykład IV, strona 5/54
Podział kodów
ze względu sposób transmisji bitów informacyjnych
Kod systematyczny rozdzielny
h 1
h 2
h 3
...
h k
f
h 1
h 2
h 3
...
h k
b 1
... b n-k
b 1
... b n-k
h 1
h 2
h 3
...
h k
Kody systematyczny nierozdzielny
h 1
h 2
h 3
...
h k
f
b 1
h 1
h 2
...
h 3
... b n-k
h k
Kod niesystematyczny
h 1
h 2
h 3
...
h k
f
c 1
c 2
c 3
c 4
c 5
c 5
... c n
Robert Borowiec
Kodowanie i kryptografia
Wykład IV, strona 6/54
n
317372546.014.png 317372546.015.png 317372546.016.png 317372546.017.png 317372546.018.png 317372546.019.png 317372546.020.png 317372546.021.png
Blokowe kody liniowe
Podejście ogólne
{ h }
{ c }
funkcja liniowa f
k –pozycyjne
q-narne ciągi
informacyjne
n–pozycyjne
q-narne ciągi
kodowe
{ z }
Funkcja f jest liniowa, jeżeli
dla dowolnych i
dowolnych liczb
(
wszystkie możliwe
q-narne ciągi
n-pozycyjne
h ∈
j
i ,
h
{ h
( )
a ∈
2
1 ,
a
CG
q
) ( ) ( )
f
a
1
⋅
h
i
+
a
2
⋅
h
j
=
a
1
⋅
f
h
i
+
a
2
⋅
f
h
j
Robert Borowiec
Kodowanie i kryptografia
Wykład IV, strona 7/54
Blokowe kody liniowe
Podejście szczególne
Struktura słowa kodu
c 1
c 2
...
c i-1
c i
c i+1
... c n
c
=
h
i
i
=
21
...,
k
i
b
i
=
k
+
1
k
+
2
,...,
n
i
−
k
h 1
h 2
h 3
...
h k
b 1
... b n-k
wszystkie (n-k) bitów parzystości są liniowymi sumami bitów
informacyjnych:
b
=
p
⋅
h
+
p
⋅
h
+
...
+
p
⋅
h
i
1
i
1
2
,
2
k
,
i
k
gdzie:
p
=
1
jeśli
b
i
zależy
od
h
i
ij
0
w
przypadku
przeciwnym
Robert Borowiec
Kodowanie i kryptografia
Wykład IV, strona 8/54
i
317372546.022.png 317372546.023.png 317372546.024.png 317372546.025.png 317372546.026.png 317372546.027.png 317372546.028.png
Blokowe kody liniowe
Tworzenie kodu-podejście szczególne
Zapiszmy równania w postaci macierzowej
h =[ h 1 , h 2 , ..., h k ]
b =[ b 1 , b 2 , ..., b n-k ]
b = hP
p
11
p
12
...
p
1
n
−
k
c =[ c 1 , c 2 , ..., c n ]
p
p
...
p
P
≡
21
22
2
,
n
−
k
...
...
...
...
p
p
...
p
Ponieważ wektor c jest złożeniem
wektora h oraz b to: c=[h|b]
k
1
k
2
k
,
n
−
k
1
0
...
0
0
1
...
0
Stąd: c = h[I k |P]
I
≡
k
...
...
...
...
G = [P|I k ] ,
0
0
...
1
Robert Borowiec
Kodowanie i kryptografia
Wykład IV, strona 9/54
Blokowe kody liniowe
Tworzenie kodu-podejście szczególne
I w efekcie możemy zapisać:
c = hG
gdzie:
G = [I k |P]
Macierz G jest nazywana macierzą generującą kod liniowy
( n , k )
...
...
... ... ... ...
...
g
11
12
1
n
G ≡
gg
22
g
n
gg
g
k
1
k
2
kn
Robert Borowiec
Kodowanie i kryptografia
Wykład IV, strona 10/54
gg
21
2
317372546.029.png 317372546.030.png 317372546.031.png 317372546.032.png 317372546.033.png 317372546.034.png 317372546.035.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin