Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek dla www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Korekcja błędów transmisji danych za pomocą kodu Hamminga - BASCOM

Duch__ 22 Lis 2016 22:26 6570 26
  • Korekcja błędów transmisji danych za pomocą kodu Hamminga - BASCOM

    Witam.

    Dzisiaj znowu troszkę odmienne DIY od pozostałych.

    Mianowicie przedstawiam prosty, ale jakże skuteczny algorytm do korekcji błędów przesyłanych drogą np. radiową pomiędzy dwoma procesorami.

    Kod oparty jest o algorytm Richarda Hamminga, wynaleziony w roku 1950.
    Powoduje on wykrycie i korektę w przypadku zmiany jednego bitu w odebranym słowie binarnym.

    Co tutaj dużo pisać, oto kod dla potomnych napisany w języku BASCOM.


    UWAGA!

    Zaprezentowany algorytm nie szyfruje przesyłanych danych. Dalej można je zdekodować w przypadku nieautoryzowanego odebrania.


    Kod: vbnet
    Zaloguj się, aby zobaczyć kod


    W programie posiadamy kilka istotnych zmiennych:

    Dane_tx jest to zmienna typu BYTE (8 bitów) danej którą chcemy przesłać;
    Dana_hamm_tx jest to zakodowana zmienna typu WORD (12 bitów) którą wysyłamy przez medium;
    Dana_hamm_rx jest to zakodowana zmienna typu WORD (12 bitów) którą odbieramy przez medium;
    Dane_rx jest to zmienna typu BYTE (8 bitów) danej którą odebraliśmy po ewentualnej korekcie.

    W programie znaleźć można fragment w którym możemy przetestować działanie kodu i zasymulować zakłócenie - wystarczy zmienić jeden przesyłany bit z 1 na 0 lub 0 na 1 i program wyliczy, wskaże miejsce błędu i dokona korekty dzięki któremu otrzymamy ponownie prawidłowy wynik.

    Zachęcam do testowania.

    Fajne! Ranking DIY
    Potrafisz napisać podobny artykuł? Wyślij do mnie a otrzymasz kartę SD 64GB.
    O autorze
    Duch__
    Poziom 31  
    Offline 
    Unitrez elektronik
    WWW.UNITREZ.PL
    SYSTEMY ALARMOWE, TELEWIZJA DOZOROWA,
    KONTROLA DOSTĘPU, AUTOMATYKA BRAMOWA.
    INTELIGENTNE BUDYNKI
    Specjalizuje się w: bascom, avr, alarmy, telewizja, monitoring, kontrola dostępu
    Duch__ napisał 2267 postów o ocenie 1502, pomógł 33 razy. Mieszka w mieście Opole. Jest z nami od 2004 roku.
  • #3
    Duch__
    Poziom 31  
    Algorytm działa w sposób prawidłowy. Koduje daną rzeczywistą 8-bitową na 12-bitową Hamminga która ma być przesyłana. Odbiornik odbiera daną Hamminga 12-bitową która jest sprawdzana pod względem poprawności. W przypadku zakłócenia 1 z 12 bitów dokonuje obliczeń i korekty błędnego bitu na prawidłowy.
    Jeśli w wyniku zakłócenia zostanie zmienionych więcej niż 1 bit to program dokona obliczeń, które spowodują rzekome wykrycie błędnego bitu - wynik wtedy będzie zły - należy wtedy sprawdzić całą transmisję jeszcze za pomocą np. sumy kontrolnej.

    Ogólnie ujmując:

    Chce przesłać 10101010 -> Koduje do Hamminga i otrzymuje 101001011000 -> zakłócenie -> 111001011000 -> wyliczenie prawidłowego kodu -> 101001011000 -> Dekodowanie do słowa 10101010

    Kod jest skuteczny dla powstałego jednego błędu. W testach na nadajniku i odbiorniku korekcja błędów pozwoliła zwiększyć zasięg o około 15 metrów przy dotychczasowych 20 metrach w budynku.
  • #4
    Użytkownik usunął konto
    Użytkownik usunął konto  
  • #5
    Duch__
    Poziom 31  
    Twierdzisz że mój kod posiada za mało komentarzy? Zaznaczyłem w nim tyle by każdy mógł go sobie samodzielnie przetestować, a dodatkowo by nie wprowadzać zbędnego zamieszania.
  • #6
    Użytkownik usunął konto
    Użytkownik usunął konto  
  • #7
    chudybyk
    Poziom 29  
    Testowanie przekłamań w programie nie ma sensu. Równie dobrze można testować, czy 2 razy 2 jest 4.
    Kod Hamminga skoryguje pojedyncze bity, natomiast użycie go w rzeczywistym torze transmisji nie jest takie różowe. Przekłamania na dwóch bitach będą niekorygowalne lub co gorsza nierozpoznawalne. Zakłócenia impulsowe pochodzące np. od styków, przekaźników, komutatorów silników mają często charakter paczek impulsów - co spowoduje przekłamania np. na dwóch sąsiednich bitach. Są odmiany kodu Hamminga, które korygują dwa lub nawet trzy bity, ale to z kolei wydłuża zakodowany bajt o dużą ilość bitów (z 8 do 12 to już jest sporo).
    W praktyce najczęściej stosuje się obliczanie sumy CRC paczki danych - i w razie wykrytego zakłócenia, retransmisję.
    Jedyne uzasadnienie dla kodu Hamminga ma transmisja jednokierunkowa bez kanału zwrotnego - kiedy trzeba odebrać potencjalnie zakłócone dane bez możliwości retransmisji.
    Ten kod może się nadać tylko do specyficznych zastosowań, więc dyskusję należałoby poprowadzić bardziej w kierunku obszaru implementacji, a nie w kierunku testowania.
  • #8
    krisRaba
    Poziom 30  
    Co do komentarzy, to istnieje pewna teza, że lepiej pisać kod, który sam się "komentuje", niż dodawać rozległe komentarze tekstowe. Powód jest oczywisty - komentarze tekstowe nie zawsze się skrupulatnie koryguje przy debugowaniu i wprowadzaniu modyfikacji, więc po kilku iteracjach może bardziej mylić niż pomagać. Kiedyś przykładowo dostałem do modyfikacji kod, gdzie na końcach linii były piękne komentarze cóż ta linia robi... ale nieaktualne! :-)
    Więc wg mnie lepiej opisać przy deklaracji funkcję jako taką, co robi, co przyjmuje i zwraca, a w środku pisać w samodefiniujący się sposób, używając odpowiednich nazw zmiennych, zdefiniowanych wartości wpisywanych do rejestrów (typu TIM0_CR_PRESCALER_64) itp.
  • #9
    Duch__
    Poziom 31  
    chudybyk napisał:
    Są odmiany kodu Hamminga, które korygują dwa lub nawet trzy bity, ale to z kolei wydłuża zakodowany bajt o dużą ilość bitów (z 8 do 12 to już jest sporo).


    Zaproponuj proszę taki algorytm lub wskaż gdzie można o nim poczytać.
  • #10
    Użytkownik usunął konto
    Użytkownik usunął konto  
  • #11
    djfarad02
    Poziom 18  
    Samokomentujący kod jest bardzo czytelny, jeśli nie przesadzi się z długością "przyjaznych nazw" jak to słusznie zauważył R-MIK.
    Osobiście zamiast pisać Get_Maximum_Text_Number(); piszę getMaxTxtNum(); co też jest czytelne

    Do tego parę komentarzy przy warunkach, switch'ach co robią oraz przy nietypowych zagrywkach optymalizujących kod
  • #12
    Użytkownik usunął konto
    Użytkownik usunął konto  
  • #13
    chudybyk
    Poziom 29  
    Duch__ napisał:
    chudybyk napisał:
    Są odmiany kodu Hamminga, które korygują dwa lub nawet trzy bity, ale to z kolei wydłuża zakodowany bajt o dużą ilość bitów (z 8 do 12 to już jest sporo).


    Zaproponuj proszę taki algorytm lub wskaż gdzie można o nim poczytać.


    Musiałem, troche pogrzebać. Teorię informacji i kodowania miałem dawno temu.
    Na przykład kod korekcyjny Reeda-Solomona lub kod BCH, które są używane np. do korekcji błędów odczytu z płyt CD/DVD
    Znalazłem nawet stronę z kawałkami kodów jak również teorią, niestety po angielsku: http://www.eccpage.com/
  • #14
    krisRaba
    Poziom 30  
    R-MIK napisał:
    Wszystko fajnie ale wywołanie funkcji może zająć kilka szerokości ekranu. Czy taki kod jest czytelny? Z autopsji wiem, że zwolennicy "samokomentującego się" kodu, wpadają w pół łapkę, waracając po długiej przerwie do modyfikacji kodu.

    Linię zawsze można podzielić na kilka wierszy ;) Choć bardziej się to przydaje np. przy warunkach, bo jeśli do funkcji miałbyś przekazać wiele parametrów, to lepiej przekazać wskaźnik do struktury, jeśli się da ;)
    A co do pułapek, to kiedyś dostałem fragment kodu, gdzie zmienne to były nazwane s1, s2, lrc, sdfp, b2s2, vlt itp. No ja Was proszę.. ;) Powodzenia w analizie :)

    djfarad02 napisał:
    Samokomentujący kod jest bardzo czytelny, jeśli nie przesadzi się z długością "przyjaznych nazw" jak to słusznie zauważył R-MIK.
    Osobiście zamiast pisać Get_Maximum_Text_Number(); piszę getMaxTxtNum(); co też jest czytelne

    Do tego parę komentarzy przy warunkach, switch'ach co robią oraz przy nietypowych zagrywkach optymalizujących kod

    R-MIK napisał:
    Cyferki 2 i 4 też pomagają: wait4char zamiast wait_to_char
    no i wielkie litery: waitToChar zamiast wait_to_char.

    Dokładnie, jest to potem kwestia utrzymania nazewnictwa w ryzach i odpowiedniej optymalizacji.

    chudybyk napisał:
    są używane np. do korekcji błędów odczytu z płyt CD/DVD

    W takich zastosowaniach, jeśli właśnie nie ma możliwości retransmisji przy błędach CRC itp., to tego typu mechanizmy świetnie się sprawdzają. Trochę więcej danych na nośniku trzeba upchnąć ze względu na nadmiarowe dane, ale dzięki temu można odzyskać uszkodzone fragmenty.
    Na Elektrodzie był też kiedyś ciekawy artykuł o RAID i jeśli dobrze kojarzę była tam szersza wzmianka o odzyskiwaniu danych ze straconego dysku będącego częścią macierzy. Czyli nie było tak, że kilka dysków posiada te same dane, tylko każdy zawierał część danych wymaganych do odtworzenia innego dysku...
  • #15
    Użytkownik usunął konto
    Użytkownik usunął konto  
  • #16
    krisRaba
    Poziom 30  
    No tak, ale to jest właśnie mechanizm korekcji/odzyskiwania oparty o nadmiarowe dane, więc jakby w temacie. Bo ktoś tu pytał o zastosowania :)
  • #17
    funak
    Poziom 23  
    R-MIK napisał:
    krisRaba napisał:

    Na Elektrodzie był też kiedyś ciekawy artykuł o RAID i jeśli dobrze kojarzę była tam szersza wzmianka o odzyskiwaniu danych ze straconego dysku będącego częścią macierzy. Czyli nie było tak, że kilka dysków posiada te same dane, tylko każdy zawierał część danych wymaganych do odtworzenia innego dysku...

    Taka jest idea macierzy RAID. Przy RAID 5 (jak dobrze pamiętam) złożonym z 3 dysków, tracimy 33% pojemności a nie 50%. Jeden dysk może byc uszkodzony i można odzyskać dane.
    W RAID (5 dysków) aż dwa mogą być uszkodzone i da się odzyskać 100% danych.


    RAID5 - umożliwia dalsze działanie w przypadku uszkodzenia 1 dysku
    RAID6 - umożliwia dalsze działanie w przypadku uszkodzenia 2 dysków

    RAID6 stworzono po to, by udoskonalić RAID5. W przypadku uszkodzenia dysku, po włożeniu nowego następuje odtwarzanie danych i często w tym czasie pozostałe dyski nie wytrzymywały(w końcu czekała ich spora praca). Dlatego wiele razy macierz "padała" w trakcie odtwarzania danych.

    RAID5 - posiada kodowanie XOR. Znając wiedzę, który dysk się uszkodził, można na podstawie odczytu pozostałych zrekonstruować brakujące dane z dysku
    RAID6 - posiada XOR, oraz Reed-Solomon.

    Przykładowo - ja posiadam wpięte 6 dysków 2TB w macierzy RAID6. Wynik: Patrycja 8TB. Możliwość uszkodzenia 2 dysków i dalej dane będą dostępne.
  • #18
    katakrowa
    Poziom 21  
    R-MIK napisał:
    Przeglądając kod widzę, że wiesz co to komentarz. Zastanawia mnie dlaczego ich praktycznie nie ma?


    Bez przesady masz w sumie 8 linijek kodu który rzeczywiście wymaga odrobiny skupienia, żeby zobaczyć, że mamy pętlę w pętli reszta to deklaracje. Tej pierwszej pętli nie liczę bo co tu komentować. W tytyle posta masz napisane czego dotyczy program a zmienne są nazwane wystarczająco czytelnie.

    Jeśli ktoś nie rozumie tego kodu to dla mnie nie jest programistą i lepiej niech zacznie się uczyć programowania zanim zacznie wypowiadać się na temat sposobów i metod komentowania kodu.

    Ja spojrzałem na kod i po 30 sekundach ogarnąłem ideę działania więc wygląda na to, że jest to jednak czytelne i nie wymaga dodatkowych komentarzy.
  • #19
    miszczo997
    Poziom 28  
    Duch__ napisał:
    Zaproponuj proszę taki algorytm lub wskaż gdzie można o nim poczytać.

    Rozszerzony kod hamminga z dodatkowym bitem parzystości pozwala wykryć i skorygować 2 błędy. Jeżeli chcesz jeszcze więcej rzuć okiem na kod Reda-Solomona.
  • #21
    TechEkspert
    Redaktor
    krisRaba napisał:

    Na Elektrodzie był też kiedyś ciekawy artykuł o RAID i jeśli dobrze kojarzę była tam szersza wzmianka o odzyskiwaniu danych ze straconego dysku będącego częścią macierzy. Czyli nie było tak, że kilka dysków posiada te same dane, tylko każdy zawierał część danych wymaganych do odtworzenia innego dysku...


    Być może chodzi o ten materiał: Nie tylko RAID, metody zapewniania bezpieczeństwa przechowywania danych.

    Co do kodowania określonej liczby bitów na większej liczbie bitów to w LoRa korzysta np. z kodowania 4na5 i 4na8 co daje nawet 100% narzutu na transmisji (4B8B ), z tego co pamiętam kodowanie 4B5B wykorzystywane było od początkowych wersjach Ethernet, ale tam chodziło o polepszenie parametrów transmisji przez wykorzystanie określonych ciągów bitowych. Ciekawe czy ktoś posiada bardziej szczegółowe informacje na ten temat.
  • #22
    krisRaba
    Poziom 30  
    TechEkspert napisał:
    Być może chodzi o ten materiał: Nie tylko RAID, metody zapewniania bezpieczeństwa przechowywania danych.

    Tak, dokładnie o ten materiał mi chodziło :)
  • #23
    Duch__
    Poziom 31  
    chudybyk napisał:
    Są odmiany kodu Hamminga, które korygują dwa lub nawet trzy bity, ale to z kolei wydłuża zakodowany bajt o dużą ilość bitów (z 8 do 12 to już jest sporo).


    Nie umiem znaleźć nigdzie informacji o korekcji 2 lub 3 bitów przez algorytm Hamminga :|
  • #24
    chudybyk
    Poziom 29  
    Duch__ napisał:
    chudybyk napisał:
    Są odmiany kodu Hamminga, które korygują dwa lub nawet trzy bity, ale to z kolei wydłuża zakodowany bajt o dużą ilość bitów (z 8 do 12 to już jest sporo).


    Nie umiem znaleźć nigdzie informacji o korekcji 2 lub 3 bitów przez algorytm Hamminga :|


    Już odniosłem się do tego w #13
    Chodziło mi o rozwinięcie kodu Hamminga, czyli Reed-Solomon i BCH, o których później już koledzy pisali.
  • #25
    _jta_
    Specjalista elektronik
    Sam kod Hamminga działał na takiej zasadzie, że do N bitów danych dodawano K o takich wartościach, że różnym danym wejściowym odpowiadały dane wyjściowe różniące się co najmniej 3-ma bitami, co opisywano jako kod z d_min=3; w przypadku 1 przekłamania można ustalić, jaki kod różni się od odebranego tylko jednym bitem, i przyjąć, że taki został wysłany, w przypadku 2 przekłamań jest możliwe, i nawet dość prawdopodobne, że jakiś kod różny od wysłanego będzie się różnił od odebranego tylko jednym bitem, i wtedy rekonstrukcja danych będzie błędna i nie zostanie to wykryte.

    Dodanie do takiego kodu bitu parzystości pozwala odróżnić przekłamanie dwóch bitów od przekłamania jednego bitu (bo przy przekłamaniu jednego bitu wystąpi błąd parzystości, a przy przekłamaniu dwóch nie), więc w razie przekłamania dwóch bitów zostanie to wykryte (jakkolwiek przekłamanie bitu danych i bitu parzystości zostanie rozpoznane jako przekłamanie niekorygowalne, choć akurat same dane dałyby się odczytać poprawnie - ale nie ma jak tego sprawdzić).

    Nie pamiętam, jak to jest z ilością dodatkowych bitów w kodowaniu Hamminga - czy na 2^N bitów danych oryginalnych potrzeba N bitów dodatkowych, czy raczej np. na 2^N bitów kodu Hamminga jest 2^N-N bitów danych? Chyba to drugie - to by oznaczało, że przesyłanie 5-ciu bitów danych wymaga kodów 8-bitowych (albo 9-bitowych, jeśli doda się bit parzystości), a dane 8-bitowe wymagają 12-bitowego kodu Hamminga, nie licząc bitu parzystości. Ale to można policzyć tak: mamy dane 8-bitowe, co daje 256 możliwych wartości bez przekłamań + 2048 możliwych wartości z jednym przekłamaniem, do tego są jeszcze możliwe przekłamania w bitach dodatkowych, to wszystko muszą być różne wartości, więc tego nie można zmieścić w 11-tu bitach. A jak z kodami 8-bitowymi do danych 5-bitowych?

    Reed-Solomon to chyba trochę co innego, niż Hamming: kody Hamminga naprawiają błędy w bajtach, czy "słowach", kiedy nie dysponujemy informacją, który bit uległ przekłamaniu; kodowanie Reeda-Solomona pozwala wygenerować dodatkowe bloki danych i odzyskać dane, jeśli zniekształcony, bądź utracony został jeden, czy nawet kilka bloków, ale wiadomo, które bloki zostały utracone - nadaje się do nadmiarowego zapisu danych na dyskach, można zrobić dowolną kombinację N+K dysków, które system widzi jako dysk o pojemności N dysków i w razie utraty nie więcej, niż K dysków wszystkie dane można odczytać.
  • #26
    md5crypt
    Poziom 9  
    Jeżeli masz czas, cierpliwość i solidny podstawy z algebry abstrakcyjnej, to na Politechnice Wrocławskiej uczą studentów z tego: http://www.dbc.wroc.pl/Content/442/mochnacki_kody.pdf ale z góry ostrzegam, że pełne dekodery kodów RS i BCH są na tyle skomplikowane, że implementowanie ich na małych uC jest niepraktyczne. Poza tym jak ktoś już wspomniał, "burst errors" blokowy kod korekcyjny nie koryguję. Kody korekcyjne stosuję się najczęściej tam gdzie retransmisja jest niemożliwa, bo polityka CRC+retransmisja jest całkiem dobra i skuteczna.