Dekodowanie listy

W teorii kodowania dekodowanie listy jest alternatywą dla unikalnego dekodowania kodów korekcji błędów dla dużych współczynników błędów. Pojęcie to zostało zaproponowane przez Eliasa w latach pięćdziesiątych XX wieku. Główną ideą dekodowania listy jest to, że algorytm dekodowania zamiast generowania pojedynczego możliwego komunikatu wyświetla listę możliwości, z których jedna jest poprawna. Pozwala to na obsługę większej liczby błędów niż pozwala na to unikalne dekodowanie.

Unikalny model dekodowania w teorii kodowania , który jest ograniczony do wyprowadzenia pojedynczego ważnego słowa kodowego z odebranego słowa, nie mógł tolerować większej części błędów. Doprowadziło to do powstania luki między wydajnością korekcji błędów dla stochastycznych modeli szumu (zaproponowanych przez Shannona ) a przeciwstawnym modelem szumu (rozważanym przez Richarda Hamminga ). Od połowy lat 90. znaczny postęp algorytmiczny dokonany przez społeczność zajmującą się teorią kodowania wypełnił tę lukę. Znaczna część tego postępu opiera się na swobodnym modelu korekcji błędów zwanym dekodowaniem listowym, w którym dekoder wysyła listę słów kodowych dla najgorszych wzorców błędów patologicznych, gdzie faktycznie przesłane słowo kodowe jest zawarte w wyjściowej liście. Jednak w przypadku typowych wzorców błędów dekoder wyprowadza unikalne pojedyncze słowo kodowe, biorąc pod uwagę otrzymane słowo, co prawie zawsze ma miejsce (jednak nie wiadomo, czy jest to prawdziwe dla wszystkich kodów). Poprawa tutaj jest znacząca, ponieważ wydajność korekcji błędów podwaja się. Dzieje się tak, ponieważ teraz dekoder nie jest ograniczony przez barierę połowy minimalnej odległości. Ten model jest bardzo atrakcyjny, ponieważ posiadanie listy słów kodowych jest z pewnością lepsze niż rezygnacja. Pojęcie dekodowania list ma wiele interesujących zastosowań teoria złożoności .

Sposób modelowania szumu kanału odgrywa kluczową rolę, ponieważ reguluje szybkość, z jaką możliwa jest niezawodna komunikacja. Istnieją dwie główne szkoły myślenia w modelowaniu zachowania kanału:

• Probabilistyczny model szumu badany przez Shannona, w którym szum kanału jest modelowany dokładnie w tym sensie, że probabilistyczne zachowanie kanału jest dobrze znane, a prawdopodobieństwo wystąpienia zbyt wielu lub zbyt małych błędów jest niskie
• Najgorszy przypadek lub model szumu przeciwnika rozważany przez Hamminga, w którym kanał działa jako przeciwnik, który arbitralnie psuje słowo kodowe z zastrzeżeniem ograniczenia całkowitej liczby błędów.

Najważniejszym punktem dekodowania list jest to, że nawet w przeciwstawnych warunkach szumu możliwe jest osiągnięcie optymalnego z punktu widzenia teorii informacji kompromisu między szybkością a ułamkiem błędów, które można poprawić. W pewnym sensie jest to więc jak poprawa wydajności korekcji błędów do poziomu możliwego w przypadku słabszego, stochastycznego modelu szumowego.

Sformułowanie matematyczne

Niech będzie kodem korygującym błędy za ${q}}$$Displaystyle (n, k, d)$ innymi słowy, $Displaystyle$$} displaystyle \ Sigma }$ długości $C$ wymiaru i minimalnej odległości nad alfabetem. ${\ mathcal {$$}$ o rozmiarze ${\ displaystyle q}$ . Problem z dekodowaniem listy można teraz sformułować w następujący sposób:

${$ : Otrzymane słowo błędem mi $\ displaystyle e$

Dane wyjściowe: Lista wszystkich słów kodowych ${\ Displaystyle x_ {1}, x_ {2}, \ ldots, x_ {m} \ in {\ mathcal {C}}}$ których odległość Hamminga od jest ${\ displaystyle e$ najwyżej $}$ .

Motywacja do dekodowania listy

Biorąc pod uwagę odebrane słowo $y$ które jest zaszumioną wersją jakiegoś przesłanego słowa kodowego $}$ dekoder próbuje wyprowadzić przesłane słowo kodowe, stawiając zakład na słowo kodowe, które jest „najbliższe” odebranemu do {\ displaystyle słowo. Odległość Hamminga między dwoma słowami kodowymi jest używana jako miara w znalezieniu najbliższego słowa kodowego, biorąc pod uwagę otrzymane słowo przez dekoder. Jeśli $\$ minimalną odległością Hamminga kodu , to istnieją dwa słowa kodowe $displaystyle {\ mathcal {C}}}$${\ displaystyle c_ {1}$$}$$które$ różnią dokładnie . Teraz, w przypadku, gdy odebrane słowo $,$ w równej odległości od słów kodowych $\$ do $Displaystyle c_ {2}} , jednoznaczne dekodowanie staje się niemożliwe$ ponieważ dekoder nie zdecydować, który z nich do $\ displaystyle c_ {1}}$ i ${\ displaystyle c_ {2}}$ do wyprowadzenia jako oryginalne przesłane słowo kodowe. W rezultacie połowa minimalnej odległości działa jak bariera kombinatoryczna, poza którą jednoznaczna korekcja błędów jest niemożliwa, jeśli tylko nalegamy na unikalne dekodowanie. Jednak otrzymane słowa, takie jak $rozważane$ powyżej, występują tylko w najgorszym przypadku i jeśli spojrzy się na sposób, w jaki piłki Hamminga są upakowane w przestrzeni wielowymiarowej, nawet dla wzorców błędów połowę ${\ displaystyle y}$ - minimalna odległość, jest tylko jedno słowo kodowe do $\ displaystyle c}$ w odległości Hamminga $otrzymanego$ słowa. Wykazano, że to twierdzenie jest słuszne w przypadku losowego kodu wybranego z naturalnego zespołu, a bardziej w przypadku kodów Reeda-Solomona , który jest dobrze zbadany i dość wszechobecny w zastosowaniach w świecie rzeczywistym. W rzeczywistości dowód twierdzenia Shannona o pojemności dla q -ary symetrycznych kanałów można rozpatrywać w świetle powyższego twierdzenia dotyczącego losowych kodów.

Zgodnie z mandatem dekodowania list, w przypadku błędów najgorszych, dekoder może wyprowadzić małą listę słów kodowych. Przy pewnych informacjach specyficznych dla kontekstu lub dodatkowych może być możliwe wyczyszczenie listy i odzyskanie pierwotnie przesłanego słowa kodowego. Dlatego ogólnie wydaje się, że jest to silniejszy model odzyskiwania błędów niż unikalne dekodowanie.

Potencjał dekodowania listy

Aby istniał algorytm dekodowania listy w czasie wielomianowym, potrzebujemy kombinatorycznej gwarancji, że dowolna kula Hamminga o promieniu $słowa$ ( gdzie jest $}$${\ displaystyle p$ ułamek błędów pod względem długości bloku $.$ niewielką liczbę słów kodowych Dzieje się tak, ponieważ sam rozmiar listy jest wyraźnie dolną granicą czasu działania algorytmu. Dlatego wymagamy, aby rozmiar listy był wielomianem o długości bloku ${\ displaystyle n}$ kodu. Kombinatoryczną konsekwencją tego wymogu jest to, że nakłada on górną granicę szybkości kodu. Dekodowanie listy obiecuje spełnić tę górną granicę. Wykazano niekonstruktywnie, że istnieją kody szybkości, które można zdekodować listą do ułamka błędów zbliżających się do $1$$displaystyle 1-R}$ . Ilość ${\ Displaystyle 1-R}$ jest określany w literaturze jako zdolność dekodowania listy. Jest to znaczny zysk w porównaniu z unikalnym modelem dekodowania, ponieważ mamy teraz potencjał do poprawienia dwukrotnie większej liczby błędów. Oczywiście musimy mieć co najmniej ułamek ${\ displaystyle R}$ przesłanych symboli, aby były poprawne, w celu odzyskania wiadomości. Jest to informacyjno-teoretyczna dolna granica liczby poprawnych symboli wymaganych do wykonania dekodowania, a dzięki dekodowaniu list możemy potencjalnie osiągnąć ten teoretyczny limit informacyjny. Aby jednak wykorzystać ten potencjał, potrzebujemy jawnych kodów (kodów, które można skonstruować w czasie wielomianowym) i wydajnych algorytmów do wykonywania kodowania i dekodowania.

( p , L ) -dekodowalność listy

Dla dowolnego ułamka błędu $,$$\ subseteq \ Sigma ^ {n}}$ całkowitej $\ Displaystyle L \ geqslant 1}$ do $}} Mówi$$lub$ można dekodować listę do ułamka błędów z rozmiarem listy co najwyżej $Displaystyle$ p $(p, L)}$ -list-dekodowalna, jeśli dla każdej $Sigma$ kodowych w odległości Hamminga do ∈ do {\ Displaystyle c \ w C} n {\ $}$ y ${$ od ${\ displaystyle y}$ jest co najwyżej ${\ Displaystyle L.}$

Kombinatoryka dekodowania list

Relacja między dekodowalnością listy kodu a innymi podstawowymi parametrami, takimi jak minimalna odległość i szybkość, została dość dobrze zbadana. Wykazano, że każdy kod można zdekodować listą przy użyciu małych list poza połową minimalnej odległości do granicy zwanej promieniem Johnsona. $,$ ponieważ dowodzi istnienia kodów dekodowalnych z listą dekodowania listy znacznie większym niż ${\ displaystyle {\ tfrac {d} {2}}.}$ Innymi słowy, Johnson związany wyklucza możliwość posiadania dużej liczby słów kodowych w kuli Hamminga o promieniu nieco większym niż $displaystyle {\ tfrac {d} {2}}}$ \ .

Zdolność dekodowania listy

Twierdzenie (zdolność dekodowania listy). Niech ${\ Displaystyle q \ geqslant 2,0 \ leqslant p \ leqslant 1- {\ tfrac {1} {q}}}$ i ${\ Displaystyle \ epsilon \ geqslant 0.}$ Poniższe dwa stwierdzenia obowiązują dla wystarczająco dużej długości bloku ${\ displaystyle n}$ .

i) Jeśli ${\ Displaystyle R \ leqslant 1-H_ {q} (p) - \ epsilon}$ , wtedy istnieje za ${\ Displaystyle (p, O (1 / \ epsilon))}$ - lista dekodowalnego kodu.

ii) Jeśli ${\ Displaystyle R \ geqslant 1-H_ {q} (p) + \ epsilon}$ , to każdy ${\ Displaystyle (p, L)}$ -list-dekodowalny kod ma ${\ Displaystyle L = q ^ {\ Omega (n)}}$ .

gdzie

${\ Displaystyle H_ {q} (p) = p \ log _{q}(q-1)-p\log _{q}p-(1-p)\log _{q}(1-p)}$

jest $entropii$ zdefiniowaną dla ${\ Displaystyle p \ in (0,1)}$ i rozszerzoną o ciągłość do ${\ Displaystyle [0,1]}$

Oznacza to, że dla szybkości zbliżających się do pojemności kanału istnieje dekodowalna lista kodów z listami o rozmiarach wielomianowych, umożliwiających wydajne algorytmy dekodowania, podczas gdy dla szybkości przekraczających pojemność kanału, wielkość listy staje się wykładnicza, co wyklucza istnienie wydajnych algorytmów dekodowania.

${\ displaystyle qSC_ {p}$ dekodowania listy jest znaczący, ponieważ dokładnie odpowiada pojemności -ary symetrycznego kanału $}$ . W rzeczywistości termin „zdolność dekodowania listy” powinien być właściwie odczytywany jako pojemność kanału kontradyktoryjnego w ramach dekodowania listy. Również dowód na zdolność dekodowania listy jest ważnym wynikiem, który wskazuje optymalny kompromis między szybkością kodu a ułamkiem błędów, które można poprawić w ramach dekodowania listy.

Szkic dowodu

Idea dowodu jest podobna do dowodu Shannona na pojemność binarnego ${$ , w $displaystyle (p,L)}$ losowany kod jest wybierany i pokazuje, że jest on -list-dekodowalna z dużym prawdopodobieństwem, o ile szybkość ${\ Displaystyle R \ leqslant 1-H_ {q} (p) - {\ tfrac {1} {L}}.}$ Dla stawek przekraczających powyższą wielkość można wykazać, że rozmiar listy $staje$ bardzo wielomianowy.

${\ Displaystyle m_ {0}, \ ldots, m_ {L} \ in [q] ^ {k},}$$wiadomości$ definiuje się jako takie, w którym, biorąc pod uwagę otrzymane słowo + { $+ 1$ tak się składa, że ${\ Displaystyle {\ mathcal {C}} (m_ {i}) \ w B (y, pn)}$$\ Displaystyle 0 \ leqslant i \ leqslant L}$ ja gdzie ${\ displaystyle displaystyle p} to ułamek$$błędów$$promieniu$ chcemy poprawić, a kula Hamminga o $pn$ słowem $\displaystyle y}$ jako środek.

Teraz prawdopodobieństwo, że słowo kodowe $[q] ^ {k}}$$z$ wiadomością ${\ Displaystyle m_ {i}$ leży w kuli Hamminga ${\ Displaystyle B (y, pn)}$ jest podane przez

${\ Displaystyle \ Pr \ lewo [C(m_{i})\in B(y,pn)\right]={\frac {\mathrm {tom} _{q}(y,pn)}{q^{n}}}\leqslant q ^{-n(1-H_{q}(p))},}$

${\ Displaystyle Vol_ {q} (y, pn)}$$displaystyle$ objętość kuli Hamminga o promieniu odebranym słowem $y}$${\$ jako środek. Nierówność w powyższej relacji wynika z górnej granicy objętości kuli Hamminga. q $}}$ daje bardzo dobre oszacowanie objętości kuli Hamminga o promieniu $na$ dowolnym słowie w ${\ Displaystyle [q] ^ {n}.}$ Innymi słowy, objętość piłki Hamminga jest niezmienna w tłumaczeniu. Kontynuując szkic dowodowy, wyczarujemy sumę związaną z teorią prawdopodobieństwa, która mówi nam, że prawdopodobieństwo wystąpienia złego zdarzenia dla danego ${\ Displaystyle (y, m_ {0}, \ kropki, m_ {L})}$ jest górna ograniczona przez ilość ${\ Displaystyle q ^ {- n(L+1)(1-H_{q}(p))}}$ .

Mając powyższe na uwadze, można wykazać, że prawdopodobieństwo wystąpienia „dowolnego” złego zdarzenia jest mniejsze niż ${\ displaystyle 1}$ . Aby to $możliwymi$ , pracujemy nad wszystkimi $.$ i ${\ displaystyle [q] ^ {k}.}$ w

Przechodząc teraz do dowodu części (ii), musimy pokazać, że istnieje superwielomianowo wiele słów kodowych wokół każdego, ${\ Displaystyle y \ in [q] ^ {n}}$ szybkość przekracza y zdolność dekodowania list. Musimy to pokazać ${\ Displaystyle | {\ mathcal {C}} \ cap B (y, pn) |}$ jest super wielomianem dużym, jeśli współczynnik ${\ Displaystyle R \ geqslant 1-H_ {q} (p) + \ epsilon}$ . Napraw słowo kodowe ${\ displaystyle c \ in {\ mathcal {C}}}$ . Teraz dla każdego losowo wybranego mamy ${\ Displaystyle y \ in [q] ^ {n}}$

${\ Displaystyle \ Pr [c \ w B (y, pn)] = \ Pr [y \ w B ( c,pn)]}$

ponieważ kule Hamminga są niezmienne w translacji. Z definicji objętości kuli Hamminga i faktu, że jest wybierany równomiernie losowo z ${\ displaystyle [q] ^ {n}}$$\ displaystyle y }$ mamy również y

${\ Displaystyle \ Pr [c \ w B (y, pn)] = \ Pr [y \ w B (c, pn)] = {\ Frac {\ operatorname {tom} (y, pn)} {q ^{n}}}\geqslant q^{-n(1-H_{q}(p))-o(n)}}$

Zdefiniujmy teraz zmienną wskaźnikową taką, że ${\ displaystyle X_ {c}}$

${\ Displaystyle X_ {c} = {\ rozpocząć {przypadki} 1 & c \ w B (y, pn) \\ 0 & {\ tekst {inaczej}} \$

Biorąc pod uwagę oczekiwaną objętość kuli Hamminga, jaką mamy

${\ Displaystyle {\ rozpocząć {wyrównane} E [| B (y, pn) |] & = \ suma _{c\in {\mathcal {C}}}E[X_{c}]\\[4pt]&=\sum _{c\in {\mathcal {C}}}\Pr[X_{c}= 1]\\[4pt]&\geqslant \sum q^{-n(1-H_{q}(p)+o(n))}\\[4pt]&=\sum q^{n(R- 1+H_{q}(p)+o(1)}}\\[4pt]&\geqslant q^{\Omega (n)}\end{wyrównane}}}$

Dlatego metodą probabilistyczną pokazaliśmy, że jeśli szybkość przekracza zdolność dekodowania listy, to rozmiar listy staje się super wielomianem. To kończy szkic dowodowy dla możliwości dekodowania listy.

Algorytmy dekodowania list

W latach 1995-2007 społeczność zajmująca się teorią kodowania rozwijała coraz bardziej wydajne algorytmy dekodowania list. Algorytmy dla kodów Reeda-Solomona , które mogą dekodować do promienia Johnsona, który wynosi ${\ Displaystyle 1- {\ sqrt {1- \ delta}}}$ istnieją, gdzie jest znormalizowaną odległością ${\ displaystyle \ delta}$ lub odległość względna. Jednak dla kodów Reeda-Solomona, co oznacza ułamek $-R}$${\ displaystyle 1- {\ sqrt {R}}}$ błędów można poprawić. Oto niektóre z najbardziej znanych algorytmów dekodowania list:

• Sudan '95 - Pierwszy znany nietrywialny algorytm dekodowania list dla kodów Reeda-Solomona, który osiągnął wydajne dekodowanie list $do$ przez Sudan .
• Guruswami-Sudan '98 - Ulepszenie powyższego algorytmu dekodowania list kodów Reeda-Solomona do $autorstwa$ Madhu Sudana i jego ówczesnego Guruswami .
• $}$$.$ W przełomowym artykule Farzad Parvaresh i Alexander Vardy przedstawili $,$ które można zdekodować na liście promieniem dla niskich stawek . Ich kody są wariantami kodów Reeda-Solomona $.$ które uzyskuje się przez obliczenie $wielomianów$ po prostu, w przypadku zwykłych kodów Reeda-Solomona
• Guruswami – Rudra '06 - W kolejnym przełomie, Venkatesan Guruswami i Atri Rudra podają wyraźne kody, które osiągają zdolność dekodowania list, to znaczy, że można je dekodować aż do promienia. ${\ Displaystyle 1-R- \ epsilon}$ dla dowolnego ${\ Displaystyle \ epsilon > 0}$ . Innymi słowy, jest to korekcja błędów z optymalną redundancją. To odpowiedziało na pytanie, które było otwarte przez około 50 lat. Ta praca została zaproszona do sekcji Research Highlights w Communications of the ACM (która jest „poświęcona najważniejszym wynikom badań opublikowanych w informatyce w ostatnich latach”) i została wspomniana w artykule zatytułowanym „Coding and Computing Join Forces” w wydaniu magazynu Science z 21 września 2007 r. Kody, które im nadano, nazywane są złożonymi kodami Reeda-Solomona , które są niczym innym jak zwykłymi kodami Reeda-Solomona, ale są postrzegane jako kod w większym alfabecie dzięki starannemu łączeniu symboli słów kodowych.

Ze względu na ich wszechobecność i dobre właściwości algebraiczne, które posiadają, algorytmy dekodowania list dla kodów Reeda-Solomona były głównym przedmiotem zainteresowania badaczy. Problem z dekodowaniem listy dla kodów Reeda-Solomona można sformułować w następujący sposób:

$Displaystyle ($ wejściowe : Dla $alfa _ {i}, y_ {i})}$ parę dla ${\ Displaystyle 1 \ równoważnik i \ równoważnik n}$$\ Displaystyle y_ {i}}$ ja jest tym bitem ${\ displaystyle i}$ odebranego słowa i ${\ displaystyle \ alpha _ {i}}$ 's są odrębnymi punktami w polu skończonym $nt}$${$ t .

Wyjście : Celem jest znalezienie wszystkich wielomianów o stopniu co najwyżej ${\ Displaystyle P (X) \ in F_ {q} [X$$}$$,$ wiadomości taka ​​dla $\$$i$ _ Tutaj chcielibyśmy mieć ${\ displaystyle t}$ tak małe, jak to możliwe, aby można było tolerować większą liczbę błędów.

Przy powyższym sformułowaniu ogólna struktura algorytmów dekodowania list dla kodów Reeda-Solomona jest następująca:

Krok 1 $}, y_ {i}) = 0}$ niezerowy wielomian dwuwymiarowy $Displaystyle$ ja $\ alpha _ {i$ dla ${\ Displaystyle 1 \ równoważnik i \ równoważnik n}$ .

Krok 2 : (znalezienie pierwiastka / faktoryzacja) wyprowadź wszystkie wielomiany stopnia p $\$$Displaystyle p (X)}$ takie, że $Displaystyle Yp (X)}$ jest czynnikiem Q ${\ Displaystyle Q (X, Y)}$ tj. $Displaystyle Q (X, p (X)) = 0}$ . Dla każdego z tych wielomianów sprawdź, czy przynajmniej dla $Displaystyle$ ja ${\ Displaystyle i \ w [n]}$$p (\ alfa _ {i}) = y_ {i}$ . Jeśli tak $umieść$ taki wielomian liście

Biorąc pod uwagę fakt, że wielomiany dwuwymiarowe można skutecznie rozłożyć na czynniki, powyższy algorytm działa w czasie wielomianowym.

Zastosowania w teorii złożoności i kryptografii

Algorytmy opracowane do dekodowania list kilku interesujących rodzin kodów znalazły interesujące zastosowania w złożoności obliczeniowej i kryptografii . Poniżej znajduje się przykładowa lista aplikacji poza teorią kodowania:

• Konstruowanie twardych predykatów z permutacji jednokierunkowych .
• Przewidywanie świadków dla problemów z wyszukiwaniem NP.
• Wzmacnianie twardości funkcji boolowskich.
• Średnia twardość przypadku trwałych macierzy losowych.
• Ekstraktory i generatory pseudolosowe .
• Skuteczne śledzenie zdrajców.

Linki zewnętrzne

• Ankieta dotycząca dekodowania list przeprowadzona przez Madhu Sudan
• Notatki z kursu prowadzonego przez Madhu Sudana
• Notatki z kursu prowadzonego przez Lucę Trevisana
• Notatki z kursu prowadzonego przez Venkatesan Guruswami
• Notatki z kursu prowadzonego przez Atri Rudrę
• P. Elias, „Dekodowanie listy dla hałaśliwych kanałów”, Raport techniczny 335, Research Laboratory of Electronics, MIT, 1957.
• P. Elias, „Kody korygujące błędy do dekodowania list”, IEEE Transactions on Information Theory, tom. 37, s. 5–12, 1991.
• JM Wozencraft, „Dekodowanie listy”, kwartalny raport z postępów, Research Laboratory of Electronics, MIT, tom. 48, s. 90–95, 1958.
• Praca doktorska Venkatesana Guruswamiego
• Wyniki algorytmiczne w dekodowaniu list
• Składany kod Reeda-Solomona