I. Wstęp

Kod "2 z 5" jest kodem detekcyjnym 5-bitowym. Na 5 bitów w których kodowany jest jeden znak, występują 2 jedynki, jest to zatem kod stałowagowy. Pamiętając o podanych zasadach tworzenia kodu, można w nim zakodować 10 znaków. Minimalna odległość Haminga wynosi 2. 

Zaletą stosowania kodu "2 z 5" jest prosta budowa kodera i dekodera. W ich skład wchodzą bramki NAND i NOT. Koder składa się z dziesięciu wejść (odpowiadającym cyfrom 0-9 ) oraz pięciu wyjść (z których składany jest pięciobitowy kod). Dekoder jest zbudowany odwrotnie do kodera - pięć wejść i dziesięć wyjść.

Kody poszczególnych znaków:

Słowo kodowane

Otrzymany kod

0

11000

1

10100

2

10010

3

10001

4

01100

5

01010

6

01001

7

00110

8

00101

9

00011

II. Analiza działania dekodera

Po zapoznaniu się z działaniem programu postanowiłem przeanalizować działanie dekodera dla cyfry 7, której odpowiada kod: 00110. Zakodowana w ten sposób informacja jest zgodna z później przeprowadzoną symulacją, co potwierdza poprawność budowy kodera. Analizę detekcji przedstawiają poniższe tabelki:

  • Błąd pojedynczy

Otrzymany kod

Odpowiedź dekodera

10110

błąd

01110

błąd

00010

błąd

00100

błąd

00111

błąd

Zmiana jednego bitu powoduje zmianę liczby jedynek w kodzie, która po każdym z błędów jednokrotnych jest różna od 2. Dekoder prawidłowo rozpoznaje otrzymany kod jako błędny. Wszystkie błędy są zatem wykrywane.

  • Błąd podwójny

Otrzymany kod

Odpowiedź dekodera

11110

błąd

10010

2

10100

1

10111

błąd

01010

5

01100

4

01111

błąd

00000

błąd

00011

9

00101

8

W tym wypadku, jeżeli w wyniku zakłócenia kodu na 2 bitach, otrzymamy liczbę jedynek równą 4, bądź 0, błąd zostanie wykryty. Jeżeli jednak przekłamaniu ulegnie jeden bit który jest jedynką, i jeden który nią nie jest, otrzymamy kod 5 bitowy z wagą 2. Zgodnie z logiką dekoder błędnie dekoduje otrzymaną informację, jako inne słowo. W przypadku błędu podwójnego dekoder wychwytuje 40% błędów.

  • Błąd potrójny

Otrzymany kod

Odpowiedź dekodera

11010

błąd

11100

błąd

11111

błąd

10000

błąd

10011

błąd

10101

błąd

01000

błąd

01011

błąd

00001

błąd

10011

błąd

Podobnie jak w przypadku błędu jednokrotnego zmiana trzech bitów powoduje zmianę liczby jedynek w kodzie, która po każdym z błędów potrójnych jest różna od 2. Dekoder prawidłowo rozpoznaje otrzymany kod jako błędny. Wszystkie błędy są zatem wykrywane.

  • Błąd poczwórny

Otrzymany kod

Odpowiedź dekodera

01001

6

10001

3

11101

błąd

11011

błąd

11000

0

Podobnie jak w wypadku błędu podwójnego, jeżeli w wyniku zakłócenia kodu na 4 bitach, otrzymamy liczbę jedynek równą 4, błąd zostanie wykryty. Jeżeli jednak przekłamaniu ulegną 2 bity które są jedynką i 2 które nią nie są, otrzymamy kod 5 bitowy z wagą 2. Zgodnie z logiką dekoder, błędnie dekoduje otrzymaną informację, jako inne słowo. W przypadku błędu podwójnego dekoder wychwytuje 40% błędów.

  • Błąd pięciokrotny

Otrzymany kod

Odpowiedź dekodera

11001

błąd

Zmiana 5 bitów powoduje zmianę liczby jedynek w kodzie, błąd jest zatem wykrywalny.

Reasumując kod "2 z 5" posiada dość dużą skuteczność: pozwala na całkowite wyeliminowanie błędów nieparzystych oraz 40% błędów parzystych. Wysoką skuteczność opisywany kod zawdzięcza temu, że jest stałowagowy.

Możemy obliczyć prawdopodobieństwo niewykrycia błędu przez dekoder. Zgodnie z przeprowadzoną analizą działania dekodera wnioskuję, że błąd może nie zostać wykryty jedynie w dwóch wypadkach:

  • zakłócenie wystąpiło na 2 bitach, przy czym wynik ograniczamy do wyboru jednego bitu spośród dwóch jedynek oraz jednego bitu spośród trzech zer
  • zakłócenie wystąpiło na 4 bitach, przy czym wynik ograniczamy do wyboru dwóch bitów spośród dwóch jedynek oraz dwóch bitów spośród trzech zer

Korzystając ze schematu Bernoulliego otrzymałem następujący wynik:

00028953.gif 

Zakładając, że prawdopodobieństwo przekłamania jednego bitu jest równe p=½, otrzymujemy następujące rezultaty:

  • prawdopodobieństwo niewykrycia błędu wynosi P = 28,1%
  • prawdopodobieństwo wykrycia błędu wynosi P'=71,9%

Prawdopodobieństwo wykrycia błędu nieparzystego jest zawsze równe 100%. Prawdopodobieństwo, że w kodzie wystąpi konkretna liczba zakłóceń również otrzymamy ze schematu Bernoulliego, np. prawdopodobieństwo dokładnie dwóch przekłamań wynosi:

00028954.gif 

III. Analiza kodu "3 z 7"

Kod "3 z 7" jest kodem analogicznie do kodu "2 z 5" jest kodem stałowagowym, z wagą 3, w którym do kodowania użyto 7 bitów. Chcąc policzyć ilość możliwych do zakodowania znaków używam kombinacji 3 z 7 (miejsc na których można postawić jedynkę), otrzymując wynik 35. 

Będę starał się porównać oba kody pod względem prawdopodobieństwa niewykrycia błędu. Kod "3 z 7" można wykorzystać zarówno dla wszystkich 35 możliwych do zakodowania słów lub do zakodowania 10 cyfr, podobnie jak w kodzie "2 z 5". 

  • Wykorzystane jest wszystkie 35 znaków

Podobnie jak w kodzie "2 z 5" rozpatrzę możliwości przekłamań, oraz skuteczności wykrywania błędów w zależności od liczby zakłóconych bitów:

    • wszystkie nieparzyste błędy są wychwytywane
    • 2 bity można zakłócić na 21 sposobów, z czego 9 posiada przekłamanie liczby jedynek, skuteczność wykrywania błędów wynosi zatem 42,8%
    • 4 bity można zakłócić na 35 sposobów, z czego 17 posiada przekłamanie liczby jedynek, skuteczność wykrywania błędów wynosi zatem 48,6%
    • 6 bitów można zakłócić na 7 sposobów, z czego 3 posiada przekłamanie liczby jedynek, czyli skuteczność wykrywania błędów wynosi 42,8%

Analogicznie jak w przypadku kodu "2 z 5" korzystając ze schematu Bernoulliego wyliczam wzór na prawdopodobieństwo niewykrycia błędu:

00028955.gif 

Zakładając, że prawdopodobieństwo przekłamania jednego bitu jest równe p=½, otrzymujemy następujące rezultaty:

  • prawdopodobieństwo niewykrycia błędu wynosi P = 25,8%
  • prawdopodobieństwo wykrycia błędu wynosi P'=74,2%
  • Wykorzystane jest 10 znaków

Zakładam że dekoder potrafi rozpoznać 10 spośród 35 wykorzystanych przez nas możliwości i jeżeli otrzyma liczbę odpowiadającą np. 17, uzna ją za błąd. Rozpatruję możliwości przekłamań, oraz skuteczności wykrywania błędów w zależności od liczby zakłóconych bitów:

  • wszystkie nieparzyste błędy są wychwytywane
  • 2 bity można zakłócić na 21 sposobów, z czego 9 posiada przekłamanie liczby jedynek, czyli 42,8%. Z pozostałych 12 możliwości tylko 9 może przechowywać jakąś cyfrę, minimalna skuteczność kodu wynosi zatem 57,1%, a maksymalna 100%, średnia skuteczność wynosi 78,5%
  • 4 bity można zakłócić na 35 sposobów, z czego 17 posiada przekłamanie liczby jedynek, czyli 48,6%. Z pozostałych 18 możliwości tylko 9 może przechowywać jakąś cyfrę, minimalna skuteczność kodu wynosi zatem 74,2%, a maksymalna 100%, średnia skuteczność wynosi około 87,1%
  • 6 bitów można zakłócić na 7 sposobów, z czego 3 posiada przekłamanie liczby jedynek, czyli 42,8%. Ponieważ kodujemy tylko 10 cyfr spośród 35 możliwych, więc skuteczność kodu jest zmienna - od 42,8% do 100%, średnia skuteczność wynosi 71,4%

Analogicznie jak w przypadku kodu "2 z 5" korzystając ze schematu Bernoulliego wyliczam wzór na prawdopodobieństwo niewykrycia błędu:

00028956.gif 

Zakładając, że prawdopodobieństwo przekłamania jednego bitu jest równe p=½, otrzymujemy następujące rezultaty:

  • prawdopodobieństwo niewykrycia błędu wynosi P = 17,2%
  • minimalne prawdopodobieństwo wykrycia błędu wynosi P'=82,8%
  • średnie prawdopodobieństwo wykrycia błędu wynosi około P'= 91,4%

IV. Wnioski

Zastosowanie kodu umożliwiającego wykrycie błędnej transmisji pociąga za sobą zarówno konsekwencje pozytywne (bardzo wysokie prawdopodobieństwo wykrycia błędu w przypadku kodu "3 z 7"), jak i negatywne (zwiększenie ilości bitów na słowo co pociąga za sobą zmniejszenie istotnej szybkości przesyłania danych).

Zestawienie wyników dla obu kodów przedstawia poniższa tabelka:

Użyty kod

2 z 5

3 z 7

3 z 7

Ilość wykorzystanych znaków

10

10

35

Ilość bitów w kodzie

5

7

7

Wykrywalność błędów

71,9%

91,4%

74,2%

Przy korzystaniu z maksymalnej możliwej ilości znaków dla poszczególnych kodów, nieznacznie lepiej wykrywa błędy kod "3 z 7", jednak ze względu na większą ilość bitów na słowo (aż o 2) jest znacznie wolniejszy. Kod "2 z 5"pozwala zapisać 10 pozycji co idealnie pasuje do kodowania cyfr z kodu dziesiętnego. Jeżeli jednak użyjemy 10 znaków w przypadku kodu "3 z 7", to średnia wykrywalność błędów rośnie zauważalnie. Kod "3 z 7" posiada również tę istotną zaletę, iż umożliwia zakodowanie znaków popularnego kodu szesnastkowego, czego kod "2 z 5" nie jest w stanie nam zapewnić.

Kod "2 z 5" (w licznych odmianach) jest wykorzystywany np. w kodach kreskowych:

00028957.gif Pięć elementów, z których składa się kod "2 z 5 Datalogic" to trzy ciemne i 2 jasne paski. Dwa z nich są szerokie, a trzy wąskie. Cyfra kontrolna może, ale nie musi być dodawana. Graficzne obrazy cyfr przeplatają się Przy pomocy tego kodu można kodować cyfry 0-9.

00028958.gif Kod kreskowy "2 z 5 IATA" jest bardzo popularny. Został zaprojektowany po to by zwiększyć gęstości kodu 2 z 5. Format ten koduje cyfry 0-9. Każda para cyfr reprezentowana jest przez 5 ciemnych i 5 jasnych kresek. Znak startu w tym kodzie to dwa wąskie paski, natomiast znak stopu - jeden szeroki jeden wąski pasek.