ZESTAW B. 1. Określić sposób kodowania zwięzłego źródła trójstanowego. 2. Prawdopodobieństwo błędnej transmisji słowa kodowego posiadającego pozycji j...
7 downloads
26 Views
442KB Size
ZESTAW A. 1. Określić sprawność zwięzłego binarnego kodowania źródła binarnego. 2. Jakie jest prawdopodobieństwo błędnej transmisji słowa kodowego posiadającego n = 512 pozycji, jeżeli znana jest wartość prawdopodobieństwa przekłamania pojedynczej pozycji . 3. Dany jest kod nadmiarowy . Obliczyć prawdopodobieństwo powstawania błędów niewykrywalnych. 4. Obliczyć minimalną odległość Hamminga, dla kodu nadmiarowego o danej macierzy kontrolnej: . 5. Źródło binarne generuje równoprawdopodobne stany nazwane 0 i 1 przez czas T. Obliczyć wielkość pasma przenoszenia kanału transmisyjnego współpracującego ze źródłem. ROZWIĄZANIA. 1. Trochę teorii. Sprawność: . Gdzie: L – średnia długość stanu źródła, H(S) – entropia wyrażana wzorem: Kodowanie zwięzłe zachodzi wtedy, gdy binarnego symetrycznego zwięzłego zachodzi mamy n znaków to dla zwięzłego. Reasumując: Dla zwięzłego źródła binarnego sprawność Dla każdego innego źródła ponieważ
. najbardziej jak to się da, z tym, że . Dla kodowania . Jeżeli prawdopodobieństwa są równe i wynoszą
ponieważ .
oraz
.
21. Mamy podane następujące dane: oraz . Na podstawie tego mamy wyliczyć Korzystamy ze wzoru na prawdopodobieństwo przesłania złego słowa kodowego: Po podstawieniu do wzoru:
.
3. Trochę teorii. Oznakowanie: n – ilość znaków w kodzie k – ilość różnych stanów (ma ich być ) – nadmiar. p – prawdopodobieństwo błędu – minimalna odległość Hamminga. To liczba mówiąca o ile najmniej między sobą mają się różnić dwa kolejne stany. Dla ciągów binarnych a i b odległość Hamminga jest równa ilości jedynek w słowie a XOR b. Przykład. odległość pomiędzy ciągami 10011101 oraz 10111001 wynosi 2 (liczba wystąpień różnych stanów). odległość pomiędzy ciągami zagrabić i zatrąbił wynosi 3 (liczba wystąpień różnych stanów). Właściwości. Odległość Hamminga pozwala określić pewne właściwości kodowania: możliwa liczba korekcji błędów jest mniejsza niż , możliwa liczba detekcji błędów jest mniejsza niż . Następnie można określić, że dla: – nie jest możliwe wykrycie błędów, – jest możliwe wykrycie błędu, jednak niemożliwa jest korekcja, – możliwa jest korekcja.
1
Ogólnie mamy do dyspozycji kilka wzorków na tego typu zadania: Prawdopodobieństwo poprawnej transmisji: Prawdopodobieństwo przesłania złego słowa kodowego: Prawdopodobieństwo wystąpienia k błędów (z rozkładu Bernoulliego):
Błąd niewykrywalny to taki, który spowoduje że dany kod zmieni się w kod innego stanu, np.: z 00000 musimy otrzymać 11111. Dodatkowo można zaobserwować, że jeżeli , to mamy tylko 2 stany, np.: 00 i 11. Rozwiązanie zadania. Mamy do dyspozycji następujące dane: , , , z których wynika, że mamy mieć 2 stany po 3 bity, które na wszystkich 3 mają się różnić. Ilość stanów: (maksymalnie tyle może się różnić). Następnie kodujemy zgodnie z założeniem. Kodowanie: Założenie spełnia para: 000 oraz 111 – prawdopodobieństwo nie wykrycia błędu – prawdopodobieństwo wykrycia błędu i jego korekcji (suma dla każdego stanu sum od innych stanów. Jako, że są jednakowo prawdopodobne mnożymy je przez 1/2). 4. Więcej teorii… W zadaniach, w których podana jest macierz kontrolna można odczytać z niej pewne parametry (n, k, ). A znając te, można policzyć i . Macierz generacyjna ma tyle wierszy, ile jest bitów znaczących (k) oraz posiada tyle kolumn, ile w ogóle bitów. Zaczyna się macierzą jednostkową. Jeżeli transponujemy tą macierz (G) i pomnożymy przez macierz kontrolną (H) to mamy macierz zerową. Dla danego kodu [n,k] otrzymujemy: Macierz generacyjna: Macierzy kontrolna: Ponieważ zachodzi: ; Możemy z macierzy kontrolnej wyznaczyć macierz generacyjną i na odwrót. Aby uzyskać kody generowane przez macierz generacyjną mnożymy tą macierz przez wszystkie możliwe wektory o takiej długości, jak ilość wierszy generacyjnej. Czyli w jednym z tych zadań gdzie mamy macierz dwuwierszową te wektory to [0,0] [0,1] [1,1] [1,0]. Rozwiązanie zadania. Patrzymy na podaną macierz kontrolną. Widzimy, że zawiera macierz jednostkową (4x4) oraz 1 dodatkową kolumnę. Należy to odczytywać jako macierz kodu cyklicznego o parametrach [n,k], gdzie n – liczba kolumn macierzy (długość słowa kodowego); k – kolumny po usunięciu macierzy jednostkowej. (kodujące k bitów informacji) Przykład (o co chodzi…) Postać kanoniczna macierzy kontrolnej kodu (5,2): n
1 1 1 0 0 H 0 1 0 1 0 1 0 0 0 1 k
Macierz jednostkowa wymiaru n-k
Dla naszego zadania: W naszym przypadku jest to kod [5,1], który koduje 1 pozycję informacyjną jako słowo 5-bitowe z 4 bitowym przeniesieniem (nadmiar).
Więc kody jakie możemy zrobić to 0 i 1 + nadmiar. Dla naszego zadania nadmiar wynosi 4 (n-k nadmiar). Dlatego najlepiej jest zrobić 00000 oraz 11111 i w ten sposób otrzymujemy
Otrzymaliśmy następującą ilość stanów:
.
.