od cyfrowego "0" i "1" do podjęcia miękkiej decyzji o wartości stanu binarnego
a to takie libretto do testów, które będę poniżej, tak trochę chronologicznie:
1) kontrola parzytości, CRC Wikipedia: kontrola parzystości
Czyli dodanie do słowa jednego bitu określającego czy więcej "0" czy "1". W kontroli parzystości oraz w kolejnym etapie rozwinięcia algorytmu - CRC (cyclic redundancy check) w celu większej ochrony danych w wykrywaniu błędów.
CRC-32 jest stosowany do weryfikacji poprawności między innymi ramki Ethernet, plików ZIP, USB czy serial ATA.
Rozwinięciem kryptograficznych algorytmów CRC są algorytmy dające cyfrową reprezentację skrótu całego pliku np. MD5
2) wykorzystywanie tylko określonych symboli Wikiepdia: line code
W system 8b na 10b = słowo ośmiobitowe (256) informacja przesyłana jest tylko wybranymi symbolami słowa 10-bitowego (1024). Czyli, wykorzystywane są tylko te stany, które są łatwe do dekodowana, pozostałe 768 możliwych kombinacji jest traktowane jako błąd odczytu.
Czyli takie trochę 2 w 1, bo i warstwa sygnałowa robi się bardziej równomierna, usuwa stany wrażliwe, ale zarazem daje pewną informację o poprawności odczytu.
Np. dodatkowo na płycie CD, tak zostały dobrane symbole, że zawsze wiadomo gdzie rozpoczyna się kolejny symbol oraz wyeliminowano wielokrotne powtórzenia tych samych stanów np. "000000000", aby wyeliminować pomyłkę zliczania stanów oświetlanych przez laser.
Inne zastosowanie tego typu algorytmów Two-out-of-five code (WIKIPEDIA).
10 wybranych kombinacji reprezentujących cyfry od 0 do 9, są zapisywane 5 bitowym słowem (32), ale tak aby powstały kod kreskowy z "0" i "1", składał się tylko z dwóch cienkich (01001) albo jednej podwójnej kreski (01100) w każdym słowie.
Zastosowanie: od kodów kreskowych, przez USB 3.0, HDMI do sieci światłowodowych.
3) Powtarzanie
dane: ABC
wysyłane: AAABBBCC notacja takiego systemu to: (3,1)
~~ "Kody powtórzeniowe oferują słaby kompromis pomiędzy szybkością transmisji danych, a stopą błędów. Stosując inne formy można uzyskać wyższą jakość działania. Główną atrakcyjnością kodu powtórzeniowego jest jego łatwość w wdrożeniu." ~~ Wikipedia: Repetition code
4) wykrywanie i naprawianie błędów
A) Kod Hamminga (8,4) Wikipedia
Jest to jeden z kodów liniowych wymyślony przez Richard Hamminga w 1950 w Bell Telephone Laboratories do zabezpieczenia danych na kartach perforowanych.
Algorytm Hamminga (7,4), czyli 4 bity informacji i 3 bity parzystości Hamminga daje możliwość odczytania prawidłowej informacji, gdy jeden dowolny bit jest błędnie odczytany.
Wersja Hamminga (8,4) z dodatkowym bitem parzystości może wykrywać podwójne błędy i naprawiać pojedyncze.
B) extended binary code Golay [24,12,8]
Rozwinięcie kodu Hamminga jest extended binary code Golay [24,12,8] korygując wszelkie błędy 3-bitowe lub 7-bitowe mogą być wykryte. Trzy bloki Hamminga (8,4) dałyby niby podobną wartość, bo korekcja 3-bitów i 6-bitów wykrywa. Ale w Golay te trzy błędy mogą być nawet bit po bicie obok siebie, a w trzech blokach Hamminga, po maksymalnie jednym błędzie w każdym bloku 8-bitowym.
Inne kolejne nowsze kody operują na coraz większy blokach i są zoptymalizowane na niewielką stopę błędu. W testach systemu FA-LA przy wolnych modach transmisji błędy pojawiały się nawet 5-bitów w 80-bitowej ramce danych.
5) kod Turbo, inne kody LDPC
No i algebra Boole'a nabiera nowego znaczenia po wprowadzeniu terminu: podjęcie miękkiej decyzji o wartości stanu bitowego (soft decision approach).
Gdy nie ma już ani zera, ani jedynki tylko każdemu odebranemu bitowi przypisywana jest waga od: -127 na pewno "0", -100 bardzo prawdopodobne "0" przez 0 - może być "0" lub "1" do 127 co oznacza na pewno "1". Algorytm wykrywający błędy podczas oceny bierze tę wagę. Waga zostaje przypisana każdemu bitowi na przykład w systemach radiowych na podstawie chwilowych parametrów radiowych podczas odczytu tego bitu.
FA-LA MODE40 i HAMMING(8,4)
 |
| TEST - mode40 (3xCHAR=16bit) i Hamming(8,4) |
który otwiera rozszerzoną tablicę dodatkowych 39 znaków np. symbol małpy "/A".
Testowy algorytm koduje trzy znaki "/0A" 47,48,65,
następnie opisuje te znaki liczbami w systemie MODE40 jako: 3,4,14,
te trzy znaki przedstawione w formie jednej liczby 16-bitowej to 4974.
Liczba zapisana w systemie szesnastkowy w postaci czterech bloków po 4 bity: 1-3-6-E.
Każda z tych czterech liczb 4-bitowych (1,3,6,14) zostaje zastąpiona odpowiednim ciągiem Hamminga(8,4):
1-3-6-E w postaci ciągu Hamminga(8,4) - 11010010:10000111:11001100:00101101
test uszkodzenia danych przez zmianie 5 bitu w pierwszym bloku z 11010010 na 11000010
Algorytm automatycznie dokonał korekcji tego bitu i poprawnie zdekodował jako symbol "1":
Algorytm automatycznie dokonał korekcji tego bitu i poprawnie zdekodował jako symbol "1":
1-3-6-E : 10-01-01-01
W drugiej części wyniki 10-01-01-01 zostały zapisane wagi dekodowania:
dla pierwszego bloku została nada waga "10" - pierwszy blok odebrano z błędem,
a drugi, trzeci i czwarty blok ma wagę "01" - zdekodowano poprawnie.
System wag będzie zapisywany w tablicą zdekodowanych części wiadomości, a dla wagi "11", czyli nie udało się zdekodować zostanie zapisany cały ciąg Haminnga dla danego znaku.
Jeżeli dany fragment zostanie odebrany powtórnie z większa wagą, wartość ta zostanie zastąpiona nową.
Brak komentarzy:
Prześlij komentarz