W1 kodyNwww, TELEKOMUNIKACJA
[ Pobierz całość w formacie PDF ]
//-->Kody blokoweWykład 1,3 III 2011Literatura1. R.M. Roth,Introduction to Coding Theory,20062. W.C. Huffman, V. Pless,Fundamentals of Error-Correcting Codes,20033. D.R. Hankerson et al.,Coding Theory and Cryptography. Essentials,20001Konstrukcja ciała GaloisCiało Galois rzęduqoznaczane jest symbolamiFq=GF(q)i istnieje do-kładnie dlaq=pm, gdziep∈ {2,3, 5, 7, 11,...}– to liczba pierwsza orazm∈N={1,2, 3,...}.CiałoFqjest jedyne z dokładnością do izomorfizmu. Może mieć wiele reprezen-tacji, ale wszystkie reprezentacje ciała ustalonego rzęduqsą nawzajem izomor-ficzne.Z punktu widzenia reprezentacji ciał najprostszymi ciałami Galois są ciałaFp,w których liczba elementów jest liczbą pierwsząp.Nadto właśnie ciałoFpjestciałem prostymw każdym ciele rzęduq=pm, tzn.Fpjest najmniejszym wsensie inkluzji podciałem ciała GF(pm).Przykład 3.Fp=GF(p) =Zp, gdziepjest liczbą pierwszą. Wtedy ciało Galois, a raczejzbiór jego elementów, ma postaćFp={0,1,..., p−1},gdzie elementy0, 1,. . .oznaczają klasy reszt modulop:0 klasę [0], 1 klasę [1], i ogólnie[i]oznacza klasęwszystkich liczb całkowitych (ze zbioruZ),dla których reszta z dzielenia przezpjesti, i= 0, 1,. . . , p−1.ZatemFp={[0],[1],...,[p−1]}.Działania wFp, czyli dodawanie i mnożenie modulop,oznaczamy symbolami⊕pi⊗p.2Kanał transmisyjny binarny powinien być BSC (binary symmetric channel),tzn.•dwójkowy (binarny)•rozpoczęcie i zakończenie transmisji jest wykrywane, a kanał ma być•bezpamięciowy•symetryczny, tzn. prawdopodobieństwo poprawności jest takie samo dlaobu symboli•addytywny – nie ma wymazywania ani wprowadzania nowych symboli;błąd może polegać na zmianie 0 w 1 lub 1 w 0.Tę ostatnią własność można wyrazić addytywnie w następujący sposób. Jeśliwysłanov∈Ci otrzymano słowow, w=v(np.w∈C),to istnieje wektorebłędów w słowiew,taki żew=v⊕2elub równoważnie:w⊕2e=v.Symbol1 na dowolnej pozycji w słowie błędóweoznacza, że na tej pozycji nastąpiłoprzeinaczenie w kanale przesyłowym.Niechpoznacza prawdopodobieństwo przekłamania,≤p≤1,(albonie-zawodności– zgodnie z umową).1Kanał jest bezużyteczny, gdyp≈2, ponieważ wtedy nie da się określićinterpretacji symboli wyjściowych.Wnioskiem jest, że kanał transmisyjny nazywamy dobrym, jeżeli spełniawarunek≤p≤1∧ ¬(p ≈1).23Kodowanie informacjiNiechubędzie słowem informacyjnym (u∈ Ak), zaśCzbiorem słów kodującychorazvsłowem przesyłanym (v∈C⊆ An).Kodowaniemnazywamy bijekcjęKpostaciK:Aku→v=K(u)∈C⊆ An.Kody linioweJeżeli alfabetAma strukturę ciała skończonego, wówczas zbiórAnwszystkichn-literowychsłów dających się zapisać za pomocą alfabetuA,ma strukturęn-wymiarowej przestrzeni wektorowej nad ciałemA.Wtedykodem liniowymdługościnnazywamy podprzestrzeń wektorowąCprzestrzeniAn.4MetrykaNiechXbędzie dowolnym zbiorem niepustym.Metrykąna zbiorzeXnazywamyfunkcjęd:X×X→[0,∞),która dla dowolnych elementówx, y, znależących dozbioruX,spełnia następujące warunki:1. nieujemność,d(x, y)≥0,i nieosobliwość,d(x, y)= 0⇐⇒x=y,2. symetrię,d(x, y)=d(y, x),3. nierówność trójkąta,d(x, y)≤d(x, z)+d(z, y).Metryka HammingaMetryką Hamminganazywamy funkcjędH, która parom słów ustalonej dłu-gości przypisuje odległość równą liczbie pozycji, na których te dwa słowa sięróżnią. Formalnie, jeżelix, y∈ An, todH(x,y)=l,gdyxi=yidla dokładnielwskaźnikówispośródi= 1, 2,..., n.Dość łatwo można udowodnić, że metryka Hamminga jest metryką, tzn. matrzy powyższe własności.5 [ Pobierz całość w formacie PDF ] |