Kody Polarnie, Osiąganie Pojemności Szannona

Problem, który Shannon pozostawił otwarty

Teoria kodowania kanałów szumnych Claude'a Shennona z 1948 roku wykazała, że każdy kanał komunikacyjny ma maksymalną niezawodną prędkość, swoją pojemność, i że istnieją kody, które w miarę zbliżają się do niej arbitralnie blisko z zanikającym prawdopodobieństwem błędów. To, czego nie dostarczyła teoria Shennona, to praktyczny sposób na budowę takich kodów – była to dowód istnienia poprzez losowe kodowanie, a nie konstrukcja. Przez ponad półwiecze inżynierowie wykorzystywali kody (konwolucyjny, turbo, LDPC), które w praktyce bardzo zbliżały się do pojemności, ale bez dowodu na ich rzeczywiste osiągnięcie oraz bez prostego, jawnego konstruowania.

Rdzeń Arikan i polaryzacja kanału

W 2009 roku Ercdal Arikan zmienił to zaskakująco prostym pomysłem: połączyć dwie niezależne kopie tego samego kanału za pomocą małej transformacji 2x2, a następnie rekurencyjnie łączyć 2 w 4, 4 w 8 i tak dalej. Elementem budującym jest:

F = [ 1 0 ] G_N = F^(kron n), N = 2^n [ 1 1 ]

gdzie: N=1: łączenie 2 użyć kanału -> 2 syntetyczne kanały N=2: łączenie 4 użyć kanału -> 4 syntetyczne kanały ...

Wraz ze wzrostem N, pojemność syntetycznych kanałów rozdziela się: przybliżnie C% z nich zbliża się do pojemności 1 (w pełni niezawodny) pozostałe zbliżają się do pojemności 0 (przydatne) — bardzo niewiele pozostaje pomiędzy nimi

Rozdzielanie to jest polaryzacją kanału, a to jest cała sztuczka: gdy N staje się bardzo duże, ułamek syntetycznych kanałów, które stają się prawie bezszumowe, zbliża się dokładnie do oryginalnej pojemności Szannona C. Nic nie zmieniło się w podrzędnym kanale fizycznym — polaryzacja jest wyłącznie właściwością interakcji rekurencyjnego łączenia z statystykami kanału.

F = [ 1  0 ]        G_N = F^(kron n),   N = 2^n
    [ 1  1 ]

n=1: combine 2 uses of the channel  -> 2 synthetic channels
n=2: combine 4 uses of the channel  -> 4 synthetic channels
...
As N grows, the synthetic channel capacities spread apart:
a fraction ~C of them approach capacity 1 (perfectly reliable)
the rest approach capacity 0 (useless) — very few stay in between

Zamrażanie słabych kanałów

Budowa kodu polarnego polega na: klasyfikacji N syntetycznych kanałów pod względem niezawodności, umieszczeniu rzeczywistych bitów informacji na około N·C najbardziej niezawodnych kanałach, oraz zamrożeniu pozostałych – ustaleniu ich na znaną wartość, zwykle zero, uzgodnioną z góry przez nadajcę i odbiorcę. Ponieważ zamrożone pozycje nie przenoszą żadnej informacji, ale są znane dekoderowi, działają jako wbudowana redundancja dokładnie tam, gdzie kanał jest najsłabszy, a informacja przesyła się tylko wtedy, gdy może ona przetrwać. Obliczenie, które kanały są niezawodne (ewolucja gęstości lub prostsza przybliżona metoda Gaussa i granice parametru Bhattachary’ego używane w praktyce) jest samo w sobie dobrze ugruntowaną i efektywną operacją wykonywaną offline.

Dekodowanie przez sukcesywną anulację

Dekomponator, zwanym dekodowaniem przez sukcesywną anulację (SC), wykorzystuje tę samą rekurencyjną strukturę: dekoduje bity po kolei w ustalonej kolejności, a każda decyzja jest warunkowana na podstawie wszystkich wcześniej rozkodowanych bitów, dokładnie tak jak enkoder łączy kanały. Dekodowanie SC ma złożoność O(N log N), odpowiadającą kosztowi kodowania rekurencyjnego rdzenia – ale samo w sobie dekodowanie SC zbiega się do pojemności tylko wtedy, gdy N rośnie bardzo dużym. Przy praktycznych długościach bloków i błędach rawowych ustępuje sprawdzonym kodom. Rozwiązaniem szeroko stosowanym w implementacji jest dekodowanie SC-List: śledzi kilka kandydackich ścieżek dekodowania równolegle zamiast jednej, a dodany CRC wybiera przeżywającą ścieżkę, która spełnia kryterium. To połączenie uczyniło kody polarnie konkurencyjnymi w praktyce, nie tylko w dowowodzie asymptotycznym.

Od twierdzenia do normy

W 2016 roku 3GPP wybrał kod polarów na kanały sterujące w 5G New Radio, czyniąc go pierwszym kodem osiągającym pojemność z wyraźną konstrukcją i formalnym dowodem, który ma zostać wdrożony w globalnym standardzie komunikacyjnym – niezwykle szybka podróż od artykułu teoretycznego do miliardów telefonów oraz bezpośrednie korzyści płynące z konstrukcyjnego, rekurencyjnego projektu, który sprawił, że zarówno enkoder, jak i dekodery listy SC były wystarczająco wydajne, aby zaimplementować je w krzemie.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Polar Codes i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.