Wykład 6 TIK Kodowanie i dekodowanie-Liniowe kody blokowe PDF

Preview

Summary

Wykład 6 TIK Kodowanie i dekodowanie-Liniowe kody blokowe, dr piet...

Description

KODOWANIE I DEKODOWANIE INFORMACJI

KODY NADMIAROWE – LINIOWE KODY BLOKOWE  Kody nadmiarowe są najbardziej efektywnym sposobem zwiększania prawdopodobieństwa poprawnej transmisji informacji przez kanały z większym od dopuszczalnego prawdopodobieństwem przekłamania.  Schemat kodowania wiadomości w kod nadmiarowy, transmisję słów kodowych i ich dekodowanie przedstawiono na poniższym rysunku.

1

v1 v2

x1 x2 ...

...

w1 w2

...

...

xM

u1 u2 ...

x1 x2

uM

wM

vL

xM

2

 W kodach nadmiarowych tylko k z n pozycji wykorzystuje się do kodowania informacji (pozycje informacyjne), pozostałych n-k = m nadmiarowych pozycji wykorzystuje się do kontroli (pozycje kontrolne), tzn. do wykrywania lub korygowania błędów.  Kody nadmiarowe dzielą się na kody: - blokowe, - nieblokowe.

3

Definicja 5: Z kodem blokowym mamy do czynienia wówczas, gdy kodowanie polega na przekształceniu k-pozycyjnego ciągu informacyjnego wi w n-pozycyjny ciąg kodowy (słowa kodowe) wi .  Proces kodowania ciągu informacyjnego ui zamyka się w całości w czasie tworzenia słowa kodowego wi .  Kod blokowy oznaczamy symbolem (n,k) gdzie: n - długość słowa kodowego, k - liczba pozycji informacyjnych w słowie. Definicja 6: Sprawność kodu blokowego

k n

 . 4

Definicja 7: Kod nadmiarowy jest kodem nieblokowym (splotowym), jeśli proces tworzenia itego słowa kodowego wi uzależniony jest od i-tego ciągu informacyjnego ui oraz r -1 poprzednich ciągów informacyjnych, czyli

wi  f ( ui r 1 , ui r  2 , ..., ui 1 ,ui )  Ważną klasą kodów splotowych są kody rekurencyjne. Definicja 8: Kody rekurencyjne są to kody splotowe, w których ciąg informacyjny ui występuje w sposób jawny w słowie w i 5

 Prześledźmy proces transmisji słów kodowych nadmiarowego blokowego kodu binarnego przez kanał transmisyjny (rysunek). Można zbudować M = 2 k różnych słów kodowych tworzących kod C.

6

v2 v3 v4

v k 1 vk  2

vk 3

vi 1

N2

 

vi  w3

w3

v L 1 M  2k

L  2n

vL  wM

N3



vL  2

wM

N1

  

vk  w2

w2

  

v1  w1

w1

NM

 W czasie transmisji przez kanał mogą wystąpić przekłamania na 0,1,...,n pozycjach słowa kodowego. Dlatego na wyjściu kanału można uzyskać L = 2 n różnych ciągów zerojedynkowych o długości n, z których tylko M należy do kodu C, pozostałe L - M do kodu nie należą.  Ponieważ każde z M =2 k słów kodowych może przejść, w wyniku działania zakłóceń, w dowolny ciąg o długości n, to może wystąpić w czasie transmisji wszystkich słów kodowych kodu C, M·L = 2k+n różno prawdopodobnych stanów, w tym: BB=M=2k bezbłędnych transmisji każdego słowa kodowego w siebie, 8

BNW=M(M-1) = 2 k(2 k-1) przekłamań słów kodowych w inne słowa kodowe, są to błędy niewykrywalne, BW=M(L-M) = 2 k(2 n-2k) przejść słów kodowych w ciągi nienależące do C, są to błędy, które mogą być wykryte.  Dzielimy ciągi nienależące do C (jest ich L - M) na M rozłącznych podzbiorów N1 ,...,NM i przyporządkowujemy każdy z nich jednemu słowu kodowemu w ten sposób, że jeśli odebrany ciąg należy do podzbioru Ni to przyjmuje się, że nadano słowo kodowe w i .

9

 Błąd będzie skorygowany poprawnie wtedy, gdy otrzymany ciąg o długości n rzeczywiście powstał ze słowa wi , czyli błąd będzie korygowany poprawnie tylko w BW ( L M ) LM M M M

przypadkach.  Można zauważyć, że Liczba różnych błędów, które mogą być wykryte Liczba możliwych stanów



M (L  M ) ( L  M ) 2n  2k  1  M  LM L 2n

10

oraz Liczba różnych błędów, korygowalnych Liczba różnych błędów, które mogą być wykryte



(L  M ) 1  M (L  M) M

11

Kody liniowe  Najważniejszą klasą kodów nadmiarowych (blokowych i splotowych) są kody liniowe. Zajmiemy się tylko binarnymi kodami liniowymi, w których wydzielono pozycje informacyjne i kontrolne, tzn. przyjmuje się, że pewne pozycje są traktowane jako pozycje informacyjne (równe co do wartości wartościom pozycji kodowanej informacji) a pewne pozycje traktowane są jako pozycje kontrolne, wykorzystywane do oceny poprawności odebranej informacji.  Taki kod ma następujące właściwości: 1. Wciągu kodowym są wydzielone pozycje informacyjne i kontrolne. W pozycje informacyjne wpisujemy kolejno cyfry binarne tworzące ciąg stanowiący informację. 12

2. Jest określonych Nk zespołów

Z j, j =1,2,…, Nk , pozycji obejmujących

zarówno pozycje informacyjne, jak i kontrolne, zwanych zespołami kontrolnymi. Na ogół zakłada się, że każdy zespół kontrolny Z j zawiera tylko jedną pozycję kontrolną. Umożliwia to obliczenie sygnału bezpośrednio w tej pozycji bez rozwiązywania układu równań, co byłoby konieczne, gdyby zespoły kontrolne zawierały po kilka pozycji kontrolnych. 3. Wszystkie ciągi o długości N, różniące się w pozycjach informacyjnych, wraz z pozycjami kontrolnymi posiadającymi właściwość 2 są stosowane jako ciągi kodowe.

13

 W przypadku szczególnym, gdy w każdym zespole kontrolnym jest tylko jedna pozycja kontrolna, właściwość 3 oznacza, iż informacji, a zatem ciągów kodowych ma być tyle, ile jest możliwych kombinacji sygnałów binarnych w pozycjach informacyjnych.  Każdy zespół kontrolny w tym ostatnim przypadku może zostać zdefiniowany poprzez podanie numeru pozycji kontrolnej (1,2, itd.) oraz zbioru numerów pozycji informacyjnych, służących do wyliczenia wartości danej pozycji kontrolnej.

14

Przykład 1 Dany jest kod z ciągami kodowymi o długości N = 7 z 3 zespołami kontrolnymi (7,3) takimi, że:  do zespołu kontrolnego Z 1 należą pozycje 1, 3, 5, 7, pozycja kontrolna zespołu – 1,  do zespołu kontrolnego Z 2 należą pozycje 2, 3, 6, 7, pozycja kontrolna zespołu – 2,  do zespołu kontrolnego Z 3 należą pozycje 4, 5, 6, 7, pozycja kontrolna zespołu – 4, Pozycjami informacyjnymi są pozycje 3, 5, 6, 7.

15

1 1

K

1

2

3

4

2

3

4

5

2

K

3

4

I

K

  

6

5

I

7

6

I

7

I

w1  w 3  w 5  w 7 w1  0  w2  1 w3  0  w4  1 w5  0  w6  1 w7 1 w1  0  w2  1 w3  0  w4  1 w5  0  w6  1  w7  0 [1 0 1 0 1 0 1 ] w2  w3  w6  w7 w2  0 w1  1 w3  0  w4  0  w5  1 w6  1 w7 0  w1  1  w2  1  w3  0  w4  0  w5  1  w6  1  w7  0 [0 1 1 0 0 1 1 ] w4  w5  w6  w7 w4  0  w1  0  w2  0  w3  1 w5  1 w6  1 w7 0  w1  0  w2  0  w3  1 w4  1 w5  1  w6  1  w7  0 [0 0 0 1 1 1 1 ] 17

Powyższe równania w notacji macierzowej mają postać:

1 0  0

 w1  w   2 0 1 0 1 0 1  w3   0   1 1 0 0 1 1   w4   0     0 0 1 1 1 1  w5  0     w6   w7 

18

Najczęściej mamy do czynienia z sytuacją, kiedy pozycje kontrolne są umieszczone za pozycjami informacyjnymi. Przykład 2 Dany jest kod z ciągami kodowymi o długości N = 7 z 3 zespołami kontrolnymi (7,3) takimi, że:  do zespołu kontrolnego Z 1 należą pozycje 1, 2, 4, 5 pozycja kontrolna zespołu – 5,  do zespołu kontrolnego Z 2 należą pozycje 1, 3, 4, 6 pozycja kontrolna zespołu – 6,  do zespołu kontrolnego Z 3 należą pozycje 2, 3, 4, 7, pozycja kontrolna zespołu – 7, Pozycjami informacyjnymi są pozycje 1, 2, 3, 4. 19

 



Dla przykładu 2 zapisz równania i ich postać macierzową jak dla przykładu 1.

21

Definicja 9: Binarnym kodem liniowym nazywamy kod określony układem m liniowo niezależnych równań w postaci: n

T

jl

wl  0

j  1,2, ..., m

l 1

(1)

gdzie: - wieloargumentowa suma modulo 2, a l = w l - l-ta pozycja słowa kodowego w

1 jeśli l-ta pozycja ciągu kodowego wchodzi do j-tego równania T jl   0 w przeciwnym przypadku

22

lub w postaci macierzowej T w t = 0 tm gdzie:

(2)

T – macierz tworząca kodu liniowego, macierz parzystości,

w t – transponowany wiersz słowa (ciągu) kodowego w , 0 tm – wektor kolumnowy złożony z m zer, 0 m – wektor wierszowy złożony z m zer,

 Równanie 2 można zapisać również w równoważnej postaci:

w  Tt = 0 m Równania (1), (2) są testami parzystości kodu, a pozycje ciągu kodowego objęte j-tym równaniem nazywane są j-tym zespołem kontrolnym.

Przykład 3 (kontynuacja) Macierze T dla powyższych przykładów mają postacie:  1 0 1 0 1 0 1 1) kod nierozdzielny T   0 1 1 0 0 1 1  0 0 0 1 1 1 1

2) kod rozdzielny

 1 1 0 1 1 0 0 T   1 0 1 1 0 1 0  0 1 1 1 0 0 1



24

Przykład 4 (kontynuacja) Wyznaczenie wartości pozycji kontrolnych dla ciągu informacyjnego u = (1,0,1,1) dla obu powyższych macierzy.  1 0 1 0 1 0 1 1) kod nierozdzielny T   0 1 1 0 0 1 1  0 0 0 1 1 1 1 1  w1  0  w2  1  w3  0  w4 1  w5  0  w6 1  w7  0 1 w1  0  w2  1 1  0  w4  1  0  0 1 1 1  0 w1  0  1  0  0  0  1  0 w1  0  0 w1  0 25

0  w1 1  w2 1  w3 0  w4 0  w5 1  w6 1  w7  0 0  w1 1  w2 1 1  0  w4  0  0  1  1  1  1  0 0  w2  1  0  0  1  1  0 w2 1  0 w2  1 0  w1  0  w2  0  w3 1  w4 1  w5 1  w6 1  w7  0 0  w1  0  w2  0  1  1 w4  1 0  1 1  1 1  0 0  0  0  w4  0  1  1  0 w4  0  0 w4  0

26

Powyższe równania mają następującą postać macierzową:

 w1  w   2 1 0 1 0 1 0 1    1   0  0 1 1 0 0 1 1   w    0    4    0 0 0 1 1 1 1  0   0   1  1  Ciąg kodowy ma następującą postać:

w = (0,1,1,0,0,1,1)

27

 1 1 0 1 1 0 0 2) kod rozdzielny T  1 0 1 1 0 1 0  0 1 1 1 0 0 1

1 w1  1  w2  0  w3  1  w4  1  w5  0  w6  0  w7  0 1 1 0  0  1 1 0  1  1 w5  0  w6  0  w7  0 1 0  1 0  w5  0  0  0 w5  0  0 w5  0

28

1  w1  0  w2  1  w3  1  w4  0  w5  1  w6  0  w7  0 1 1 0 0  1 1 1 1 0  w5  1 w6  0 w7  0 1 0  1 1 0  w6  0  0 w6 1  0 w6  1 0  w1  1 w2  1  w3  1  w4  0  w5  0  w6 1  w7  0 0 1 1 0 1 1 1 1 0 w5  0  w6  1 w7  0 0  0  1 1 0  0  w7  0 w7  0  0 w7  0 29

Powyższe równania mają następującą postać macierzową:

1 0   1 1 0 1 1 0 0   1  1 0 1 1 0 1 0    1       0 1 1 1 0 0 1   w5     w6   w7 

0  0    0 

Ciąg kodowy ma następującą postać:

w = (1,0,1,1,0,1,0)

30

 Waga słowa kodowego w i , jest równa liczbie jedynek w słowie i oznaczona jest przez W( wi ). Definicja 10 Odległość 2 słów kodowych wi oraz w j (odległość Hamminga) oznaczana przez d ( w i , w j ) jest równa liczbie pozycji, na których się te słowa różnią.  Natomiast minimalna odległość słów kodowych kodu C o liczności M oznaczana przez d min jest równa Definicja 11

d min 

min

i, j 1,2 ,..., M i j

d (wi , w j )

31

 Można pokazać, że dla liniowych kodów blokowych minimalna odległość Hamminga równa się minimalnej wadze niezerowych słów kodowych, tzn.

d min  min W ( wi ) , wi  0n

gdzie 0n - słowo kodowe o długości n złożone z samych zer.  Dla kodu jednoznacznie dekodowalnego dmin 1.

32

 W kodzie nadmiarowym zachodzą następujące zależności: -

wykrywającym błędy o krotności l,...,t0 d min  t0 + 1 → t0 ≤ dmin – 1

-

korygującym błędy o krotności 1 ,...tk dmin  2tk + 1 → t k ≤ (dmin – 1)/2

-

wykrywającym błędy o krotności l,...,t0 i korygującym błędy o krotności 1,...,tk (t0  tk ) d min  t 0 + t k +1

33

{ w1 ,w2 ,w3 ,w4 , w5 } 

w1

d ( w1, w5 )

d( w3 , w5 )

wi , wj

d (w1 , w 2 )

d (w1 , w4 ) w5

d (wi , wj )

d ( w2 , w5 )

d ( w1 , w3 ) w2

d ( w2 , w4 )

d (w 2 , w 3 )

d ( w4 , w5 )

d ( wi , w j )  4

d ( w3 , w4 ) w4

w3

Ilustracja odległości Hamminga między ciągami kodowymi (dmin = 4) 34

v1 ,v 2 ,v 3  - ciągi kodowe odebrane

w1 , w2 , w3 , w4 , w5 

Korekcja błędu Tylko detekcja błędu

Korekcja błędu

v2

w1

- ciągi kodowe nadane

v3 v1

d ( w1, w5 )

d ( w1, w 4)

d ( w1, w2 ) d ( w1, w3)

w5

w2

d (w 2 , w5 )

d (w2 , w3 )

d (w 4 , w5 )

d ( w2 , w4 ) w4

d ( w3 , w5 )

d (w3 , w4 )

w3

Ilustracja detekcji i korekcji błędów 35

w1

v1

w2

w1

d min  2  1  1

v2 v4

v1

v2

v3

dmin  4  2  1  1

v2

w2

dmin 3  2 1 1

w1

w1

v1

w2

v1

v3

w2

d min  5  2  2  1 36

 Optymalizację kodu nadmiarowego można przeprowadzić na podstawie jednego z kryteriów: KR1: przy zadanej długości słowa n i liczbie pozycji informacyjnych k (kod (n,k)) poszukuje się kodu o największej wartości odległości minimalnej dmin, lub KR2: przy zadanej długości słowa kodowego i odległości minimalnej d min poszukuje się kodu o największej liczbie pozycji informacyjnych k.

37

 Właściwości graniczne kodów nadmiarowych określa: - kres dolny Warszamowa-Gilberta

 n  1   1 2m i 1  i 

 

 n 1    2m i 0  i 

d 2

d 2

lub

 

tzn., jeśli spełniona jest powyższa nierówność, to istnieje kod (n,k) o dmin

(3)



d,

- kres górny Hamminga

n i 0  i  tk

    2m

(4)

gdzie: m - liczba pozycji kontrolnych, tk - największa krotność błędów korygowanych przez kod. 38

Wnioski dotyczące kresu górnego Hamminga.

Zadanie projektowe Wyznaczyć niezbędną (minimalną) liczbę pozycji kontrolnych (m) dla kodu korygującego błędy pojedyncze (t k=1) w zależności od liczby

pozycji

informacyjnych (k). Korzystając z (4) możemy napisać:

39

 n   n   2m  0  1  n! n!   2m 0!n! 1!(n  1)! 1 n 2 m 1m k 2 m k  2m  m  1 Poniżej wyliczono wartość prawej strony nierówności. m

1

2

3

4

5

2m-m-1

0

1

4

11

26

40

Stąd otrzymujemy rozwiązanie problemu dla kolejnych wartości k: k

1

2

3

4

5

6

7

m

2

3

3

3

4

4

4

Podobnie możemy rozwiązać zadanie konstrukcji kodu korygującego błędy podwójne (tk=2).

41

 n    n   n   2 m 0  1   2  n! n! n!    2m 0! n! 1!(n  1)! 2!(n  2)! 1 n 

n (n  1) m 2 2

2 2n  n 2  n  2m 1 2  n  n 2  2 m 1 n  n 2  2m 1  2 n (n  1) 2m1  2 n (n 1)  2n k 1  2 L P L  n (n 1) P  2 n k1  2

k 1 L  n (n 1) P  2 n 11  2  2 n  2 n L P

1 2 0 L>P

2 6 2 L>P

3 12 6 L>P

4 20 14 L>P

5 30 30 LP

6 42 62 LP

7 56 126 LP

8 72 254 LP

9 90 510 LP

n=5 Stąd m=n-k=4

43

k2 L  n (n 1) P  2 n  21  2  2 n 1  2 n L P

2 6 0 L>P

3 12 2 L>P

4 20 6 L>P

5 30 14 L>P

6 42 30 L>P

7 56 62 LP

8 72 126 LP

9 90 254 LP

n=7. Stąd m=n-k=5.

44

k3 L  n (n 1) P  2n  3 1  2  2n  2  2 n L P

3 12 0 L>P

4 20 2 L>P

5 30 6 L>P

6 42 14 L>P

7 56 30 L>P

8 72 62 L>P

9 90 126 LP

10 110 254 LP

n=9. Stąd m=n-k=6.

45

k4 L  n (n 1) P  2 n 4 1  2  2 n 3  2 n L P

4 20 0 L>P

5 30 2 L>P

6 42 6 L>P

7 56 14 L>P

8 72 30 L>P

9 90 62 L>P

10 110 126 LP

11 132 254 LP

n=10. Stąd m=n-k=6.

46

 Kres górny Hamminga osiągają tylko kody absolutnie optymalne. Pozostałe nadmiarowe kody optymalne mieszczą się wewnątrz obszaru wyznaczonego przez kres dolny i górny. Z (4) dla dmin = 3 otrzymamy (t0=1 i t k=1): 1 m  log 2   n   log 2  n   n   log2 (n  1) i  0   1  i 0 

47

 W tablicy podano minimalną liczbę pozycji kontrolnych m = n - k zapewniających, przy zadanej liczbie pozycji informacyjnych k, wymaganą minimalną odległość słów kodowych dmin (w oparciu o nierówność Warszamowa-Gilberta) dmin = 2 3 4 5

1 1 2 3 4

2 1 3 5 7

3 1 3 5 8

4 1 3 6 8

5 1 4 6 8

k= 6 1 4 7 9

7 1 4 7 10

8 1 4 7 10

9 10 1 1 4 4 7 8 10 11

m

48

W

kodzie,

w

którym

pozycje

kontrolne

występują

po

pozycjach

informacyjnych, zwanym kodem rozdzielnym, w każdym zespole kontrolnym występuje tylko jedna pozycja kontrolna, a jej wartość wyznacza się z równania

 więc macierz tworząca przyjmuje postać T11 T12 T21 T12 T= … … T m-1,1 Tm -1,2 Tm 1 T m2

… T 1k … T 1k … … … Tm-1,k … Tmk

1 … … … …

… 1 … … …

… … … … …

… … … 1 …

… … … … 1

= [Tm,k|E m]

49

 Macierz taką będziemy nazywać macierzą testów o postaci kanonicznej. Zakładając, że pozycje kontrolne występują za pozycjami informacyjnymi ciągu kodowego, ciąg ten możemy zapisać w postaci:

w = ( u , w k ), przy czym w k oznacza ciąg sygnałów ciągu kodowego w na pozycjach kontrolnych.

50

Na rysunku powyżej wprowadzono macierz T m,k:

 T11  T21  . Tm, k    .  . Tm1

... ... . . . ...

T1k  T2k  .   .  .  Tmk 

o m  k elementach. Macierz T można wówczas zapisać jako macierz blokową T = [Tm,k |Em], przy czym Em jest macierzą jednostkową.

51

Przykład 5 (kontynuacja) Macierz Tm,k dla przykładu kodu rozdzielnego macierzy T: 1 1 0 1 1 0 0 T  1 0 1 1 0 1 0  0 1 1 1 0 0 1 

ma pos...