Sens stosowania danych naprawczych

Witam, pracuję nad pewnym projektem którego celem jest przesyłanie paczek danych (transmisja w jedną stronę). Ponieważ większość tego typu projektów posiada mechanizm detekcji i korekcji błędów (mówimy tutaj o kodowaniu FEC lub ECC), postanowiłem też swój projekt w to wyposażyć. Jednak po jakimś czasie pracy nad mechanizmem i kilku testach dochodzę do pewnych wniosków: załóżmy że mam ciąg danych składający się z 8 bitów np 00000111. W tym ciągu pierwsze 5 bitów stanowią dane (czyli zera), natomiast 3 ostatnie bity (jedynki) jest to kod nadmiarowy służący wykryciu i skorygowaniu błędów w tych pierwszych 5 bitach. Jeżeli wystąpi jakieś przekłamanie w ciągu danych to za pomocą 3 dodatkowych bitów te przekłamanie można wykryć i naprawić. Problem pojawią się jednak wtedy, gdy uszkodzeniu ulegną te bity nadmiarowe (któryś z nich zostanie błędnie odczytany) a prawdopodobieństwo wystąpienia takich błędów jest takie same jak w tych pierwszych 5 bitach. Wtedy dobrze odczytana wiadomość zostanie uszkodzona, ponieważ bity nadmiarowe zostaną błędnie odczytane.

Zatem więc jaki jest sens stosowania nadmiarowych bitów, które zwiększają objętość danych, a które same są podatne na uszkodzenia, a w związku z tym uszkadzają dane poprawnie odczytane?

Kod nadmiarowy jest konstruowany w oparciu o wiedzę w jaki sposób w danym typie transmisji mogą nastąpić przekłamania.
Dla algorytmu korygującego, nie ma znaczenia które dane są nadmiarowe, a które prawdziwe. W tych algorytmach zawsze jest dostępny zestaw wzorców, a algorytm zawsze szuka korekcji do najbliższego wzorca. Dopiero po tej korekcji do najbliższego wzorca, wybierane są dane właściwe.
Mówiąc inaczej w opisanym wypadku powinny być naprawione dane nadmiarowe.

@Relax bo widocznie ten twój nadmiarowy kod jest bez sensu zaprojektowany. Jak robić to z sensem? Na przykład przez bit parzystości, albo wielokrotne bity parzystości dla fragmentów danych.
Jeśli masz 8 bitów z czego 7 to dane a ostatni to bit parzystości (tzn mówi czy liczba 1 w pozostałych 7 bitach jest parzysta czy nie) to uszkodzenie dowolnego bitu da się "odtworzyć". A jeśli uszkodzisz bit parzystości to nadal nie ma problemu bo wystarczy policzyć 1 w pozostałych 7 bitach.

Bit parzystości może jedynie sprawdzić czy dane zostały poprawnie odebrane, nie naprawi ich w przypadku uszkodzenia. Poza tym w żaden sposób nie rozwiązuje problemu, załóżmy że liczba jedynek w ciągu jest nieparzysta a dodatkowy bit wskazuje na ich parzystość. I teraz pytanie, uszkodzony jest bit parzystości czy ciąg danych? Jak to sprawdzisz?

@MarekR22 a możesz podać przykład lub przedstawić jakąś koncepcję algorytmu który naprawia dane naprawcze?

Poczytaj np. o kodach algebraicznych. Wybieramy wielomian o współczynnikach 0 i 1 (właściwy wybór nie jest łatwy). Kodowanie polega na mnożeniu wybranego wielomianu przez wiadomość. Odbiornik dzieli otrzymaną wiadomość przez wielomian kodujący. Jeśli reszta jest zerowa, to zakłada transmisje bezbłędną - iloraz jest wiadomością, w przeciwnym razie, kierując się resztą, "poprawia" iloraz.

nie zrozumiałeś dla algorytmu naprawczego nie ma różnicy między danymi właściwymi, a danymi nadmiarowymi. Algorytm ma po prostu odnaleźć najbliższy wzorzec, gdzie odległość do wzorca jest odpowiednio definiowana przez algorytm (definicja powinna uwzględniać możliwe zakłócenia).
Przykład sieć Hopfielda.

Na Wiki jest przykład najprostszego chyba kodu korygującego - przesłanie każdego bitu 3 razy. Po odebraniu dekoder liczy bity w każdej trójce i uznaje, że najpopularniejszy bit jest tym właściwym. Dzięki temu można wykryć i skorygować jeden błąd w każdej trójce, obojętnie w którym miejscu się on pojawi.

Wielokrotne powtarzanie każdego bitu wydaje się najlepszym rozwiązaniem, ale to niestety zwiększa ilość informacji wielokrotnie - więc odpada.

@MarekR22 a co w sytuacji gdy uszkodzony jest wzorzec i algorytm go nie odnajdzie?

Przykład algorytmu (zupełnie z głowy, więc ostrzegam że może być niewydajny albo głupi):

Bajt składający się z 7 bitów danych + 1 bit parzystości.
Po każdych dwóch bajtach danych dodawany jest bajt nadmiarowy, będący sumą (albo xorem) dwóch poprzedzających bajtów danych. Ten bajt musi mieć też 7 bitów danych i bit parzystości wyliczony już po zsumowaniu.

Każdy bajt (danych lub nadmiarowy) można sprawdzić czy doszedł nieuszkodzony, przez sprawdzenie bitu parzystości. Samo to nie wystarczy dla odtworzenia danych, ale...
...wiemy że paczka składa się z dwóch bajtów danych i jednego bajtu nadmiarowego. Mając dwa z trzech (dowolne dwa z tych trzech) można wyliczyć trzeci.

Zauważ że algorytm ma jakby dwie warstwy: co innego możliwość sprawdzenia poprawności danych, a co innego naprawienie uszkodzenia.

Może warto poczytać o kodach Hamminga: http://pl.wikipedia.org/wiki/Kod_Hamminga

@Azarien Twój algorytm jest dobry, ale odzyska maksymalnie jeden bit danych z 14 bitów. W przypadku uszkodzenia 2 bitów w tym samym ciągu kontrola parzystości da wynik prawdziwy czyli program to zrozumie jako brak błędów. W przypadku uszkodzenia po jednym bicie w każdym ciągu danych suma kontrolna będzie niewłaściwa w obu przypadkach, więc nie będzie wiadomo który ciąg mnożyć przez bajt nadmiarowy. Zatem dla 14 bitów mamy 10 bitów nadmiarowych i możliwość wyszukania i naprawienia tylko jednego błędu.

Kod Hamminga ma ten sam problem co kod w moim pierwszym poście.

jeśli przewidujesz, że uszkodzeniu może ulec procentowo niewielka ilość danych wg mnie zdecydowanie lepszym sposobem są sumy kontrolne i ew. ponowna transmisja pakietu, który nie odpowiada swojej sumie

Kod Hamminga ma ten sam problem co kod w moim pierwszym poście.

Nie ma. Kod Hamminga jest w stanie wykrywać przekłamania w bitach parzystości tak samo skutecznie jak w pozostałych bitach:

The key thing about Hamming Codes that can be seen from visual inspection is that any given bit is included in a unique set of parity bits. To check for errors, check all of the parity bits. The pattern of errors, called the error syndrome, identifies the bit in error. If all parity bits are correct, there is no error. Otherwise, the sum of the positions of the erroneous parity bits identifies the erroneous bit. For example, if the parity bits in positions 1, 2 and 8 indicate an error, then bit 1+2+8=11 is in error. If only one parity bit indicates an error, the parity bit itself is in error.

Tak, ale w takim przypadku kod Hamminga jest w stanie naprawić tylko jeden bit. To za mało. Chcę uzyskać stopień korekcji minimum 50% (naprawa 4 bitów w bajcie).

Nie ma możliwości ponownej transmisji danych.

http://en.wikipedia.org/wiki/Turbo_code
http://en.wikipedia.org/wiki/Reed–Solomon_error_correction

Ale poważnie 50% error rate? Co ty niby transmitujesz? Nadajesz z ciemnej strony księżyca za pomocą krótkofalówki? Przecież sondy kosmiczne latające do zewnętrznych planet mają error rate na poziomie 1 na 10^6...

Na 50% error rate to chyba niewiele pomoże :P A jeśli już to coś super-wolnego. No chyba, że te błędy występowałyby w dość długich ciągach. Ale takiego założenia nie widziałem w tym wątku.

Gdyby error rate był na poziomie np 40% to jeszcze dałoby się to łatwo przeskoczyć, np transmitując każdy bit milion razy :) Ale przy error rate na poziomie 50% i to nie pomoże :P

To nie mój pomysł, ale po prostu doprowadź error rate do 100% i odwróć bity.

Właśnie się zorientowałem, że przecież error rate na poziomie 50% to totalny random, tzn jeśli będę miał strumień danych wejściowych oraz strumień danych losowych o takich samych rozmiarach to właśnie około 50% bitów powinno się różnić. Dobrze myślę?

@Shalom uwierz że i na ziemi niektóre metody transmisji mają większy stopień zakłóceń niż sygnał sondy kosmicznej. Na przykład kody kreskowe. O ile dla skanera proste jest odczytanie typowego kodu kreskowego, o tyle sprawa komplikuje się w przypadku złożonych kodów kreskowych, gdzie jest do przekazania dużo informacji (np kody kreskowe 2D). Załóżmy teraz że chcemy jeszcze bardziej zwiększyć ilość informacji nie zwiększając powierzchni nadruku. Prawdopodobieństwo wystąpienia błędów odczytu przez skaner, jak nawet "zamazania" przez drukarkę czy innych zanieczyszczeń rośnie bardzo szybko. Póki chipy będą droższe niż farba do nadruku na opakowaniu produktu, póty kody kreskowe będą potrzebne. Ja zajmuje się właśnie podobną transmisją danych: postać cyfrowa -> postać analogowa -> pierwotna postać cyfrowa. W takich transmisjach prawdopodobieństwo wystąpienia błędów jest duże.

Zastanawiałem się nad algorytmem Reeda-Solomona, niestety pomimo szczerych chęci nie udało mi się go zrozumieć. Nie znalazłem też żadnych porządnych źródeł w języku polskim opisujących jego konstrukcję. Jeżeli 50% to zbyt dużo możemy przyjąć 30%.

@Relax, kod Hamminga potrafi naprawić dowolny procent uszkodzonych bitów. Poczytaj bardziej wnikliwie niż obejrzenie prostego przykładu w wikipedii.

Nie rozumiem... PKP używa gigantycznych kodów (w sumie cały czas się zastanawiałem po co, tam są chyba wszystkie informacje z biletu zakodowane), masa ludzi używa QR kodów, albo np. kodów AZTEC. Te kody mogą przenosić dużo danych, a i algorytmy dekodujące nie są jakieś mega wybitne. Jeśli dostajesz gigantyczny error rate to może po prostu format kodu jest źle zaprojektowany, albo używasz jakiś nieprzystosowanych czytników? Użyj jakiegoś sprawdzonego kodu i kup sobie od chińczyków skaner do tego, problem solved.