W15_Kodowanie%20i%20Kryptografia_kody%20splotowe_cale.pdf

(1097 KB) Pobierz

Microsoft PowerPoint - W15_Kodowanie i Kryptografia_kody splotowe_cale.ppt

Kodowanie i kryptografia

Kody splotowe

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 VI

6-godzin

Plan wykładu

¾ Historia

¾ Definicja kodu splotowego

¾ Sposoby kodowania informacji

¾ Tworzenie kodu

¾ Metody dekodowania kodów splotowych

algorytm Vitterbiego

9 twardo decyzyjny

9 miękko decyzyjny

Robert Borowiec

Kodowanie i kryptografia

Wykład VI, strona 2/62

317372547.165.png

317372547.176.png

317372547.187.png

317372547.198.png

317372547.001.png

317372547.012.png

317372547.023.png

Historia

Kody splotowe wprowadził P. Elias w roku 1955.

Sekwencyjny algorytm dekodowania kodów

splotowych przedstawił w roku 1957 J. M. Wozencraft,

a jego implementację opisali niezależnie R. M. Fano i J.

L. Massey w roku 1963.

W roku 1967 A. J. Viterbi przedstawił algorytm

dekodowania kodów splotowych, opierający się na

zasadzie największego prawdopodobieństwa, który

zapewnił lepsze właściwości korekcyjne i mniejsze

opóźnienie dekodowania niż algorytm sekwencyjny.

Robert Borowiec

Kodowanie i kryptografia

Wykład VI, strona 3/62

Definicja kodu splotowego

¾ Kod splotowy jest to kod drzewiasty, dla którego

ciąg c ( i ) zależy od ciągu h ( i ) oraz od skończonej

liczby ( N -1)wcześniejszych ciągów

informacyjnych za pośrednictwem pewnej funkcji

f , będącej przekształceniem liniowym

c

(

i

)

=

f

(

h

(

i

−

N

+

1

,

h

(

i

−

N

)

,

K

,

h

(

i

)

)

lub

c

(

i

)

=

f

(

σ

( )

i

,

h

(

i

)

)

Robert Borowiec

*

Kodowanie i kryptografia

Wykład VI, strona 4/62

317372547.034.png

317372547.045.png

317372547.056.png

317372547.067.png

317372547.078.png

317372547.089.png

317372547.100.png

Koder kodu splotowego

Nk- komórkowy rejestr przesuwający (N-sekcji po k-komórek )

Symbol wej.

σ ( i ) -stan modulatora (pamięć)

h ( i )

h ( i-1 )

h ( i-N+1 )

h ( i-N )

Wejście

k-bitowe

symbole

informacyjne

k

...

2

1

k

...

2

1

k

...

2

1

k

...

2

1

n

...

2

1

n

...

2

1

Wyjście

Ciąg n-bitowych

symboli kodowych

Robert Borowiec

Kodowanie i kryptografia

Wykład VI, strona 5/62

Macierz generująca

Macierz generująca jest macierzą półnieskończoną



G

1

G

2

L

G

N

0

0

0

0









0

G

1

G

2

L

G

N

0

0

0



G

=



0

0

G

G

L

G

0

0



,

c

= G

h

⋅

∞

1

2

N

∞





0

0

0

G

G

L

G

0



1

2

N





0

0

0

0

L

L

L

L







w której:

Podmacierz G i opisuje połączenie k komórek i -tego

segmentu rejestru wejściowego z n komórkami rejestru

wyjściowego

Robert Borowiec

Kodowanie i kryptografia

Wykład VI, strona 6/62

317372547.111.png

317372547.122.png

317372547.127.png

317372547.128.png

317372547.129.png

317372547.130.png

317372547.131.png

317372547.132.png

317372547.133.png

317372547.134.png

317372547.135.png

317372547.136.png

Przykład 4.1

Koder splotowy

(2,1,3)

Robert Borowiec

Kodowanie i kryptografia

Wykład VI, strona 7/62

Koder binarnego kodu splotowego

(2, 1, 3)

Koder

Źródło binarne→Wejście

h ( i ) h ( i- 1) h ( i- 2)

1

1

1

0

1

1

0

101

0

0

0

Czas

9

8

7

6

5

4

3

2

1

0

Kanał telekomunikacyjny ←Wyjście

0

0

C 1 ( i )

C 2 ( i )

00

Czas 0

-1

Robert Borowiec

Kodowanie i kryptografia

Wykład VI, strona 8/62

317372547.137.png

317372547.138.png

317372547.139.png

317372547.140.png

317372547.141.png

317372547.142.png

317372547.143.png

317372547.144.png

317372547.145.png

317372547.146.png

317372547.147.png

317372547.148.png

317372547.149.png

317372547.150.png

317372547.151.png

317372547.152.png

317372547.153.png

317372547.154.png

317372547.155.png

317372547.156.png

317372547.157.png

317372547.158.png

317372547.159.png

317372547.160.png

317372547.161.png

317372547.162.png

317372547.163.png

317372547.164.png

317372547.166.png

317372547.167.png

317372547.168.png

317372547.169.png

317372547.170.png

317372547.171.png

317372547.172.png

317372547.173.png

317372547.174.png

317372547.175.png

317372547.177.png

317372547.178.png

317372547.179.png

317372547.180.png

317372547.181.png

317372547.182.png

317372547.183.png

317372547.184.png

317372547.185.png

317372547.186.png

317372547.188.png

317372547.189.png

317372547.190.png

317372547.191.png

317372547.192.png

317372547.193.png

317372547.194.png

317372547.195.png

317372547.196.png

317372547.197.png

317372547.199.png

317372547.200.png

317372547.201.png

317372547.202.png

317372547.203.png

317372547.204.png

317372547.205.png

317372547.206.png

317372547.207.png

317372547.208.png

317372547.002.png

317372547.003.png

317372547.004.png

317372547.005.png

317372547.006.png

317372547.007.png

317372547.008.png

317372547.009.png

317372547.010.png

317372547.011.png

317372547.013.png

317372547.014.png

317372547.015.png

317372547.016.png

317372547.017.png

317372547.018.png

317372547.019.png

317372547.020.png

317372547.021.png

317372547.022.png

317372547.024.png

317372547.025.png

317372547.026.png

317372547.027.png

317372547.028.png

317372547.029.png

317372547.030.png

317372547.031.png

317372547.032.png

317372547.033.png

317372547.035.png

317372547.036.png

317372547.037.png

317372547.038.png

317372547.039.png

317372547.040.png

317372547.041.png

317372547.042.png

317372547.043.png

317372547.044.png

317372547.046.png

317372547.047.png

317372547.048.png

317372547.049.png

317372547.050.png

317372547.051.png

317372547.052.png

317372547.053.png

317372547.054.png

317372547.055.png

317372547.057.png

317372547.058.png

317372547.059.png

317372547.060.png

317372547.061.png

317372547.062.png

317372547.063.png

317372547.064.png

317372547.065.png

317372547.066.png

317372547.068.png

317372547.069.png

317372547.070.png

317372547.071.png

317372547.072.png

317372547.073.png

317372547.074.png

317372547.075.png

317372547.076.png

317372547.077.png

317372547.079.png

317372547.080.png

317372547.081.png

317372547.082.png

317372547.083.png

317372547.084.png

317372547.085.png

317372547.086.png

317372547.087.png

317372547.088.png

317372547.090.png

317372547.091.png

317372547.092.png

317372547.093.png

317372547.094.png

317372547.095.png

317372547.096.png

317372547.097.png

317372547.098.png

317372547.099.png

317372547.101.png

317372547.102.png

317372547.103.png

317372547.104.png

317372547.105.png

317372547.106.png

317372547.107.png

317372547.108.png

317372547.109.png

317372547.110.png

317372547.112.png

317372547.113.png

317372547.114.png

317372547.115.png

Koder binarnego kodu splotowego

(2, 1, 3)

Koder

Źródło binarne→Wejście

h ( i ) h ( i- 1) h ( i- 2)

...

1

1

1

0

1

1

010

1

0

0

Czas

10

9

8

7

6

5

4

3

2

1

Kanał telekomunikacyjny ←Wyjście

1

1

C 1 ( i )

C 2 ( i )

11

Czas

1

0

Robert Borowiec

Kodowanie i kryptografia

Wykład VI, strona 9/62

Koder binarnego kodu splotowego

(2, 1, 3)

Koder

Źródło binarne→Wejście

h ( i ) h ( i- 1) h ( i- 2)

...

...

1

1

1

0

1

101

0

1

0

Czas

10

9

8

7

6

5

4

3

2

Kanał telekomunikacyjny ←Wyjście

1

0

C 1 ( i )

C 2 ( i )

1011

Czas

2

1

0

Robert Borowiec

Kodowanie i kryptografia

Wykład VI, strona 10/62

317372547.116.png

317372547.117.png

317372547.118.png

317372547.119.png

317372547.120.png

317372547.121.png

317372547.123.png

317372547.124.png

317372547.125.png

317372547.126.png

Plik z chomika:

Inne pliki z tego folderu:

W6_Kodowanie i Kryptografia_Kody klasyczne_kryptoanaliza_1g.pdf (418 KB)
kodowanie testy.rar (2767 KB)
W10_Kodowanie i Kryptografia_Funkcje jednokierunkowe_15minut.pdf (265 KB)
Kodowanie_zbior_pytan.doc (101 KB)
W13_Kodowanie i Kryptografia_kody liniowe_cale_6g.pdf (829 KB)

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin