Metody dekodowania - Decoding methods

W teorii kodowania , dekodowania jest procesem tłumaczenia odebrane wiadomości do słów kodowych danego kodu . Istnieje wiele powszechnych metod odwzorowywania wiadomości na słowa kodowe. Są one często używane do odzyskiwania wiadomości wysyłanych przez zaszumiony kanał , taki jak binarny kanał symetryczny .

Notacja

${\ Displaystyle C \ podzbiór \ mathbb {F} _ {2} ^ {n}}$ jest uważany za kod binarny z długością ; będą elementami ; i jest odległością między tymi elementami. ${\ displaystyle n}$ ${\ displaystyle x, y}$ ${\ displaystyle \ mathbb {F} _ {2} ^ {n}}$ ${\ Displaystyle d (x, y)}$

Idealne dekodowanie obserwatora

Można otrzymać wiadomość , a następnie dekodowanie idealnego obserwatora generuje słowo kodowe . Proces prowadzi do takiego rozwiązania: ${\ Displaystyle x \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ Displaystyle y \ w C}$

{\ Displaystyle \ mathbb {P} (y {\ mbox {wysłany}} \ mid x {\ mbox {odebrane}})}

Na przykład osoba może wybrać słowo kodowe, które najprawdopodobniej zostanie odebrane jako wiadomość po transmisji. ${\ displaystyle y}$ ${\ displaystyle x}$

Konwencje dekodowania

Każde słowo kodowe nie ma oczekiwanej możliwości: może istnieć więcej niż jedno słowo kodowe z równym prawdopodobieństwem mutacji w odebranej wiadomości. W takim przypadku nadawca i odbiorca (y) muszą z wyprzedzeniem uzgodnić konwencję dekodowania. Popularne konwencje obejmują:

Poproś o ponowne wysłanie słowa kodowego - automatyczne żądanie powtórzenia .
Wybierz dowolne losowe słowo kodowe z zestawu najbardziej prawdopodobnych słów kodowych, które jest bliższe temu.
Jeśli nastąpi inny kod , oznacz niejednoznaczne bity słowa kodowego jako wymazania i miej nadzieję, że zewnętrzny kod je ujednoznaczni

Dekodowanie z maksymalnym prawdopodobieństwem

Biorąc pod uwagę otrzymany wektor, dekodowanie z maksymalnym prawdopodobieństwem wybiera słowo kodowe, które maksymalizuje ${\ Displaystyle x \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ Displaystyle y \ w C}$

{\ displaystyle \ mathbb {P} (x {\ mbox {odebrane}} \ mid y {\ mbox {wysłany}})}

,

to znaczy słowo kodowe, które maksymalizuje prawdopodobieństwo, że zostało odebrane, biorąc pod uwagę, że zostało wysłane. Jeżeli prawdopodobieństwo wysłania wszystkich słów kodowych jest równe, wówczas schemat ten jest równoważny dekodowaniu idealnego obserwatora. W rzeczywistości, według twierdzenia Bayesa , ${\ displaystyle y}$ ${\ displaystyle x}$ ${\ displaystyle y}$

{\ Displaystyle {\ rozpocząć {wyrównane} \ mathbb {P} (x {\ mbox {odebrane}} \ mid y {\ mbox {wysłany}}) & {} = {\ Frac {\ mathbb {P} (x { \ mbox {odebrane}}, y {\ mbox {sent}})} {\ mathbb {P} (y {\ mbox {sent}})}} \\ & {} = \ mathbb {P} (y {\ mbox {wysłane}} \ mid x {\ mbox {odebrane}}) \ cdot {\ frac {\ mathbb {P} (x {\ mbox {odebrane}})} {\ mathbb {P} (y {\ mbox { wysłane}})}}. \ end {aligned}}}

Po ustaleniu , jest odnowiony i jest stała, ponieważ wszystkie słowa kodowe są jednakowo prawdopodobne, aby być wysłana. Dlatego jest zmaksymalizowana jako funkcja zmiennej dokładnie wtedy, gdy jest zmaksymalizowana, a roszczenie następuje. ${\ displaystyle \ mathbb {P} (x {\ mbox {odebrane}})}$ ${\ displaystyle x}$ ${\ displaystyle \ mathbb {P} (y {\ mbox {wysłany}})}$ ${\ displaystyle \ mathbb {P} (x {\ mbox {odebrane}} \ mid y {\ mbox {wysłany}})}$ ${\ displaystyle y}$ ${\ Displaystyle \ mathbb {P} (y {\ mbox {wysłany}} \ mid x {\ mbox {odebrane}})}$

Podobnie jak w przypadku dekodowania idealnego obserwatora, należy uzgodnić konwencję dekodowania nieunikalnego.

Problem dekodowania z maksymalnym prawdopodobieństwem można również modelować jako problem programowania liczb całkowitych .

Algorytm dekodowania z maksymalnym prawdopodobieństwem jest przykładem problemu „marginalizacji funkcji produktu”, który jest rozwiązywany przez zastosowanie uogólnionego prawa dystrybucji .

Dekodowanie minimalnej odległości

Biorąc pod uwagę odebrane słowo kodowe , dekodowanie minimalnej odległości wybiera słowo kodowe, aby zminimalizować odległość Hamminga : ${\ Displaystyle x \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ Displaystyle y \ w C}$

{\ Displaystyle d (x, y) = \ # \ {i: x_ {i} \ nie = y_ {i} \}}

tzn. wybierz słowo kodowe, które jest jak najbardziej zbliżone do . ${\ displaystyle y}$ ${\ displaystyle x}$

Należy zauważyć, że jeśli prawdopodobieństwo błędu w dyskretnym kanale bez pamięci jest ściśle mniejsze niż połowa, to dekodowanie na minimalną odległość jest równoważne dekodowaniu z maksymalnym prawdopodobieństwem , ponieważ jeśli ${\ displaystyle p}$

{\ Displaystyle d (x, y) = d, \,}

następnie:

{\ Displaystyle {\ rozpocząć {wyrównane} \ mathbb {P} (y {\ mbox {odebrane}} \ mid x {\ mbox {wysłany}}) & {} = (1-p) ^ {nd} \ cdot p ^ {d} \\ & {} = (1-p) ^ {n} \ cdot \ left ({\ frac {p} {1-p}} \ right) ^ {d} \\\ end {aligned} }}

która (ponieważ p jest mniejsze niż połowa) jest maksymalizowana przez zminimalizowanie d .

Dekodowanie z minimalną odległością jest również znane jako dekodowanie najbliższego sąsiada . Może być wspomagany lub zautomatyzowany przy użyciu standardowej tablicy . Dekodowanie z minimalną odległością jest rozsądną metodą dekodowania, gdy spełnione są następujące warunki:

Prawdopodobieństwo wystąpienia błędu jest niezależne od pozycji symbolu. ${\ displaystyle p}$
Błędy są zdarzeniami niezależnymi - błąd na jednej pozycji w komunikacie nie wpływa na inne pozycje.

Te założenia mogą być uzasadnione w przypadku transmisji w binarnym kanale symetrycznym . Mogą być nieracjonalne w przypadku innych nośników, takich jak DVD, gdzie pojedyncza rysa na dysku może spowodować błąd w wielu sąsiednich symbolach lub słowach kodowych.

Podobnie jak w przypadku innych metod dekodowania, należy uzgodnić konwencję dotyczącą nieunikalnego dekodowania.

Dekodowanie zespołu

Dekodowanie syndromowe jest wysoce wydajną metodą dekodowania kodu liniowego w hałaśliwym kanale , tj. Takim , na którym popełniane są błędy. Zasadniczo dekodowanie syndromu to dekodowanie z minimalną odległością przy użyciu zredukowanej tabeli przeglądowej. Pozwala na to liniowość kodu.

Załóżmy, że jest to kod liniowy długości i minimalnej odległości z macierzą kontroli parzystości . Wtedy wyraźnie jest w stanie poprawić do ${\ Displaystyle C \ podzbiór \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle n}$ ${\ displaystyle d}$ ${\ displaystyle H}$ ${\ displaystyle C}$

{\ Displaystyle t = \ lewo \ lfloor {\ Frac {d-1} {2}} \ prawo \ rfloor}

błędy popełnione przez kanał (ponieważ jeśli nie zostanie popełnionych więcej niż błędy, dekodowanie z minimalną odległością będzie nadal poprawnie dekodować niepoprawnie przesłane słowo kodowe). ${\ displaystyle t}$

Teraz przypuśćmy, że przez kanał przesyłane jest słowo kodowe i pojawia się wzorzec błędu . Następnie zostaje odebrany. Zwykłe dekodowanie odległości minimalnej szukałoby wektora w tabeli rozmiaru pod kątem najbliższego dopasowania - tj. Elementu (niekoniecznie unikalnego) z ${\ Displaystyle x \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle e \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle z = x + e}$ ${\ displaystyle z}$ ${\ displaystyle | C |}$ ${\ displaystyle c \ w C}$

{\ Displaystyle d (c, z) \ równoważnik d (r, z)}

dla wszystkich . Dekodowanie syndromu wykorzystuje właściwość macierzy parzystości, która: ${\ Displaystyle y \ w C}$

{\ displaystyle Hx = 0}

dla wszystkich . Zespół odbieranego określa się: ${\ Displaystyle x \ w C}$ ${\ displaystyle z = x + e}$

{\ Displaystyle Hz = H (x + e) ​​= Hx + He = 0 + He = He}

Aby wykonać dekodowanie ML w binarnym kanale symetrycznym , należy odszukać wstępnie obliczoną tabelę o rozmiarze , mapowanym na . ${\ displaystyle 2 ^ {nk}}$ ${\ displaystyle He}$ ${\ displaystyle e}$

Zauważ, że jest to już znacznie mniej skomplikowane niż w przypadku standardowego dekodowania tablicowego .

Jednak przy założeniu, że podczas transmisji nie popełniono więcej niż błędów, odbiornik może sprawdzić wartość w dalszej zmniejszonej tabeli rozmiarów ${\ displaystyle t}$ ${\ displaystyle He}$

{\ displaystyle {\ begin {matrix} \ sum _ {i = 0} ^ {t} {\ binom {n} {i}} \\\ end {matrix}}}

Dekodowanie listy

Dekodowanie zbioru informacji

Jest to rodzina metod probabilistycznych z Las Vegas , opartych na obserwacji, że łatwiej jest odgadnąć wystarczającą liczbę wolnych od błędów pozycji, niż zgadnąć wszystkie błędne pozycje.

Najprostszą formą jest Prange: Niech będzie macierzą generatora używaną do kodowania. Wybierz kolumny losowo i oznacz odpowiednią podmacierz . Z rozsądnym prawdopodobieństwem będą miały pełną rangę, co oznacza, że jeśli pozwalał nas być sub-wektor dla odpowiednich stanowisk dowolnego słowa kodowego z do wiadomości , możemy odzyskać jak . Stąd, jeśli mieliśmy szczęście, że te pozycje otrzymanego słowa nie zawierały błędów, a zatem były równe pozycjom wysłanego słowa kodowego, możemy zdekodować. ${\ displaystyle G}$ ${\ displaystyle k \ razy n}$ ${\ displaystyle C}$ ${\ displaystyle k}$ ${\ displaystyle G}$ ${\ displaystyle G '}$ ${\ displaystyle G}$ ${\ displaystyle G '}$ ${\ displaystyle c '}$ ${\ displaystyle c = mG}$ ${\ displaystyle C}$ ${\ displaystyle m}$ ${\ displaystyle m}$ ${\ displaystyle m = c'G '^ {- 1}}$ ${\ displaystyle k}$ ${\ displaystyle y}$

Jeśli wystąpiły błędy, prawdopodobieństwo tak szczęśliwego doboru kolumn podaje . ${\ displaystyle t}$ ${\ displaystyle \ textstyle {\ binom {nt} {k}} / {\ binom {n} {k}}}$

Ta metoda została ulepszona na różne sposoby, np. Przez Sterna i Canteauta oraz Sendriera.

Maksymalne prawdopodobieństwo częściowej odpowiedzi

Maksymalne prawdopodobieństwo częściowej odpowiedzi ( PRML ) to metoda konwersji słabego sygnału analogowego z głowicy dysku magnetycznego lub napędu taśmowego na sygnał cyfrowy.

Dekoder Viterbiego

Dekoder Viterbiego wykorzystuje algorytm Viterbiego do dekodowania strumienia bitów, który został zakodowany przy użyciu korekcji błędów w przód w oparciu o kod splotowy. Odległość Hamminga jest używany jako metryki dla trudna decyzja Viterbiego dekoderów. Kwadrat odległości euklidesowej jest używany jako metryki dla miękkich dekoderów decyzyjnych.

Zobacz też

Bibliografia

Dalsza lektura

Hill, Raymond (1986). Pierwszy kurs z teorii kodowania . Seria Oxford Applied Mathematics and Computing Science. Oxford University Press . ISBN 978-0-19-853803-5 .
Pless, Vera (1982). Wprowadzenie do teorii kodów korygujących błędy . Seria Wiley-Interscience w matematyce dyskretnej. John Wiley & Sons . ISBN 978-0-471-08684-0 .
van Lint, Jacobus H. (1992). Wprowadzenie do teorii kodowania . Graduate Texts in Mathematics (GTM). 86 (2 wyd.). Springer-Verlag . ISBN 978-3-540-54894-2 .

Languages

In other projects