Teoria kodowania

Teoria kodowania – dział matematyki, informatyki i telekomunikacji zajmujący się przedstawianiem informacji za pomocą kodów oraz badaniem ich własności. Obejmuje zarówno metody oszczędnego zapisu danych, jak i sposoby ochrony informacji przed błędami powstającymi podczas transmisji, przechowywania albo odczytu. W zakresie kodowania kanałowego teoria kodowania jest podstawowym narzędziem projektowania łączności cyfrowej, pamięci masowych, nośników optycznych i systemów przetwarzania danych^[1].

W ujęciu teorii informacji wyróżnia się dwa klasyczne problemy kodowania: kodowanie źródłowe, które usuwa nadmiarowość opisu wiadomości i prowadzi do kompresji danych, oraz kodowanie kanałowe, które celowo dodaje kontrolowaną nadmiarowość, aby umożliwić wykrywanie lub korygowanie błędów^[2][3.1]. W węższym, często spotykanym ujęciu matematycznym termin „teoria kodowania” odnosi się przede wszystkim do teorii kodów korekcyjnych. Oba nurty wyrastają z teorii informacji, ale korzystają także z algebry, kombinatoryki, rachunku prawdopodobieństwa i teorii złożoności.

W szerokim ujęciu teoria kodowania obejmuje nie tylko ochronę informacji przed błędami, lecz także granice możliwej kompresji, konstrukcje kodów blokowych i splotowych, metody dekodowania oraz zależność między sprawnością kodu, jego odpornością na błędy i kosztem obliczeniowym^[1][3].

Kod przekształca wiadomości w słowa kodowe utworzone z ustalonego alfabetu, na przykład z bitów albo symboli ciała skończonego. W kodzie blokowym wiadomość dzieli się na bloki, a każdemu blokowi przypisuje słowo o tej samej długości. Jeżeli alfabet ma ${\displaystyle q}$ symboli, długość słowa kodowego wynosi ${\displaystyle n}$, a liczba dozwolonych słów kodowych wynosi ${\displaystyle M}$, to kod opisuje się często parametrami ${\displaystyle (n,M,d)_{q}}$, gdzie ${\displaystyle d}$ jest minimalną odległością między różnymi słowami kodowymi^[1.1][4.1].

W przypadku kodów nad alfabetem dyskretnym podstawową miarą odległości jest odległość Hamminga, czyli liczba pozycji, na których dwa słowa różnią się od siebie. Minimalna odległość kodu określa jego podstawową zdolność ochrony danych: kod o odległości minimalnej ${\displaystyle d}$ może wykryć do ${\displaystyle d-1}$ błędów w słowie oraz, przy standardowym dekodowaniu do najbliższego słowa kodowego, korygować do ${\displaystyle \lfloor (d-1)/2\rfloor }$ błędów^[5]. Zwiększanie odległości wymaga zwykle większej nadmiarowości albo krótszej części informacyjnej słowa kodowego.

Ważnym przypadkiem są kody liniowe. Dla alfabetu będącego ciałem skończonym zbiór słów kodowych tworzy wówczas podprzestrzeń liniową, co pozwala opisywać kod przez macierz generującą lub macierz kontroli parzystości. Taki opis upraszcza obliczanie syndromów błędów, analizę minimalnej odległości i konstrukcję algorytmów dekodowania^[4.2][6.1]. Kody liniowe obejmują wiele klasycznych rodzin, w tym kody Hamminga, Golaya, Reeda-Solomona, BCH i liczne kody używane w praktycznych systemach transmisji.

Matematyczne podstawy teorii kodowania są ściśle związane z pracą Claude’a Shannona z 1948 roku, w której sformułowano ilościową teorię komunikacji i pojęcie granic przepustowości kanału^[2][7]. Shannon wykazał, że w standardowych modelach kanału zaszumionego, przy odpowiednio długich blokach i szybkości kodowania mniejszej od pojemności kanału, istnieją kody pozwalające uzyskać prawdopodobieństwo błędu dowolnie bliskie zeru. Twierdzenie to miało charakter egzystencjalny: nie podawało od razu praktycznych konstrukcji kodów, ale wyznaczyło cel dla późniejszych metod.

Jednym z pierwszych praktycznych osiągnięć były kody Hamminga, zaproponowane przez Richarda Hamminga w 1950 roku do automatycznej detekcji i korekcji pojedynczych błędów w komputerach cyfrowych^[5]. W tym samym okresie Marcel J. E. Golay opisał szczególnie wydajne kody dwójkowe i trójkowe. Doskonały binarny kod Golaya o parametrach liniowych ${\displaystyle [23,12,7]_{2}}$ oraz doskonały trójkowy kod Golaya o parametrach ${\displaystyle [11,6,5]_{3}}$ należą do klasycznych przykładów kodów doskonałych^[8].

W kolejnych dekadach rozwinięto teorię kodów blokowych, cyklicznych, BCH, Reeda-Solomona i splotowych, a także metody algebraiczne oraz grafowe. Od lat 90. duże znaczenie uzyskały kody turbo, ponownie odkryte i rozwinięte kody LDPC (ang. low-density parity-check) oraz kody polarne. Te konstrukcje pozwoliły w wielu zastosowaniach osiągać parametry bliskie granicom przewidywanym przez teorię informacji^[9.1].

Projektowanie kodu jest kompromisem między szybkością przesyłania informacji, odpornością na błędy, złożonością kodowania i dekodowania oraz długością opóźnienia. Szybkość kodu blokowego opisuje część słowa kodowego niosącą informację. Im więcej symboli kontrolnych dodaje kod, tym większa może być odporność na błędy, ale tym mniejsza jest efektywna szybkość transmisji^[1.2][4].

Twierdzenia Shannona wyznaczają granice asymptotyczne: poniżej pojemności kanału można teoretycznie osiągać dowolnie małe prawdopodobieństwo błędu, powyżej niej niezawodna transmisja nie jest możliwa w danym modelu kanału^[2][3.2]. W teorii kodów skończonych stosuje się natomiast różne oszacowania ograniczające jednocześnie długość, liczbę słów i minimalną odległość kodu, m.in. ograniczenie Hamminga, ograniczenie Singletona i oszacowania Gilberta-Varshamova^[1.3][6].

Odrębnym problemem jest dekodowanie. Kod o dobrych parametrach teoretycznych nie musi być użyteczny, jeśli brak dla niego szybkiego algorytmu dekodowania albo jeśli algorytm wymaga zbyt dużej pamięci i energii. Z tego powodu nowoczesna teoria kodowania bada nie tylko istnienie kodów o dobrych parametrach, lecz także ich konstruktywność, strukturę algebraiczną lub grafową oraz podatność na dekodowanie w warunkach rzeczywistych^[9.1].

Kodowanie źródłowe opisuje metody reprezentowania wiadomości przy możliwie małej liczbie symboli lub bitów. W wersji bezstratnej pozwala odtworzyć dane dokładnie, natomiast w kompresji stratnej dopuszcza kontrolowaną utratę informacji, jeśli jest ona akceptowalna dla odbiorcy. Granicą efektywnej kompresji bezstratnej jest entropia źródła: im bardziej przewidywalne są komunikaty, tym więcej nadmiarowości można usunąć^[3.3].

Klasyczne przykłady metod bezstratnych obejmują kody prefiksowe, kodowanie Huffmana i kodowanie arytmetyczne. Historycznie szczególne znaczenie miało kodowanie Huffmana, które dało optymalny kod prefiksowy dla znanych prawdopodobieństw symboli i stało się punktem odniesienia dla bezstratnej kompresji danych^[10].

W kompresji stratnej obrazu, dźwięku i wideo ważną rolę odgrywa kodowanie transformacyjne oraz modele percepcyjne. Jednym z podstawowych narzędzi stała się dyskretna transformacja kosinusowa, opisana w latach 70. jako przekształcenie wygodne do zwartej reprezentacji sygnałów^[11]. Teoria kodowania źródłowego nie sprowadza się jednak do samych formatów plików. W ujęciu teorii szybkości–zniekształcenia praktyczna kompresja (w tym bezstratna) jest szczególnym przypadkiem ogólnej teorii wiążącej rozkład źródła z minimalną długością opisu przy zadanym zniekształceniu^[3.4].

Kodowanie kanałowe dodaje do wiadomości dodatkowe symbole kontrolne, aby odbiorca mógł wykryć, a często także poprawić błędy. Prosty kod parzystości pozwala wykryć każdy pojedynczy błąd, a ogólniej nieparzystą liczbę przekłamań, ale nie wskazuje jednoznacznie ich położenia. Bardziej zaawansowane kody projektuje się tak, aby różne dozwolone słowa kodowe były od siebie odpowiednio odległe w sensie Hamminga^[5].

W kodach blokowych wiadomość dzieli się na słowa o ustalonej długości. Kody liniowe pozwalają wykorzystywać metody algebry liniowej: macierz generująca opisuje tworzenie słów kodowych z danych, a macierz kontroli parzystości umożliwia wyznaczanie syndromu błędu. Syndrom wskazuje klasę możliwego błędu i może prowadzić do jego korekcji, jeżeli liczba przekłamanych pozycji mieści się w zdolności korekcyjnej kodu^[4.3].

Szczególnie ważne są kody algebraiczne. Kody cykliczne i BCH wykorzystują własności wielomianów nad ciałami skończonymi, co daje efektywne konstrukcje o kontrolowanej odległości minimalnej. Kody Reeda-Solomona, opisane pierwotnie jako kody wielomianowe nad ciałami skończonymi, pozwalają korygować wielokrotne błędy symbolowe i są stosowane m.in. w nośnikach optycznych, transmisji cyfrowej i systemach przechowywania danych^[12][9]. Klasycznymi podręcznikowymi ujęciami algebraicznej teorii kodów stały się m.in. prace Berlekampa oraz Pless^[13.1][6].

Innym typem są kody splotowe, w których symbole kontrolne zależą nie tylko od bieżącego fragmentu wiadomości, lecz także od poprzednich stanów kodera. Ich dekodowanie jest często wiązane z algorytmem Viterbiego, który wybiera najbardziej prawdopodobną ścieżkę w grafie stanów^[14].

Od lat 90. duże znaczenie uzyskały konstrukcje oparte na iteracyjnym dekodowaniu. Kody turbo wykorzystują współpracę kilku prostszych dekoderów i w wielu przypadkach osiągają parametry bliskie granicy Shannona^[15]. Kody LDPC zostały zaproponowane przez Roberta Gallagera już w 1962 roku, a po ponownym odkryciu i rozwoju metod grafowych stały się jedną z głównych rodzin współczesnych kodów kanałowych^[16][9.2].

Istotne znaczenie teoretyczne mają również kody polarne. Erdal Arıkan wykazał w 2009 roku, że dla binarnych kanałów dyskretnych bez pamięci mogą one konstrukcyjnie osiągać pojemność symetryczną kanału^[17].

Wybrane rodziny kodów korekcyjnych

Rodzina	Charakter	Rok	Główna własność
Kody Hamminga	blokowe liniowe	1950	korekcja pojedynczych błędów[5]
Kody Golaya	blokowe doskonałe	1949	kody doskonałe o parametrach ${\displaystyle [23,12,7]_{2}}$ i ${\displaystyle [11,6,5]_{3}}$[8]
Kody Reeda-Solomona	blokowe algebraiczne	1960	korekcja wielokrotnych błędów symbolowych[12]
Kody splotowe	splotowe	–	dekodowanie algorytmem Viterbiego[14]
Kody turbo	iteracyjnie dekodowane	1993	parametry bliskie granicy Shannona[15]
Kody LDPC	grafowe, iteracyjnie dekodowane	1962	iteracyjne dekodowanie metodami grafowymi[16]
Kody polarne	blokowe	2009	konstrukcyjne osiąganie pojemności kanału[17]

Dekodowanie może korzystać z twardych decyzji, w których odbiornik sprowadza każdy symbol do najbardziej prawdopodobnej wartości, albo z informacji miękkiej, zachowującej miary wiarygodności poszczególnych symboli. Informacja miękka zwykle poprawia skuteczność korekcji, ale zwiększa wymagania obliczeniowe i pamięciowe^[9.3].

Dla prostych kodów liniowych wystarcza często dekodowanie syndromowe. W bardziej złożonych rodzinach stosuje się wyspecjalizowane algorytmy algebraiczne, dynamiczne albo iteracyjne. Dekodowanie algebraiczne ma szczególne znaczenie dla kodów Reeda-Solomona i pokrewnych kodów cyklicznych. Dekodowanie dynamiczne jest typowe dla kodów splotowych, a metody iteracyjne dominują w kodach turbo i LDPC^[4][9.4].

Analiza błędów zależy od modelu kanału. Inne kody są optymalne dla kanału, w którym błędy bitów są niezależne, inne dla kanałów z zanikami, błędami seryjnymi albo utratą całych symboli. W praktycznych systemach kodowanie łączy się z przeplotem, modulacją, detekcją błędów, protokołami retransmisji i warstwą sprzętową odbiornika^[4][9].

Teoria kodowania znajduje zastosowanie m.in. w telekomunikacji przewodowej i bezprzewodowej, transmisji satelitarnej, sieciach komputerowych, pamięciach półprzewodnikowych, kodach kreskowych, płytach optycznych i archiwizacji danych. Kody korekcyjne ograniczają skutki zakłóceń, szumów, uszkodzeń nośnika albo utraty fragmentów sygnału, często bez konieczności ponownej transmisji^[1][9].

W systemach przechowywania danych kody korekcyjne chronią przed błędami odczytu i stopniową degradacją nośnika. W transmisji radiowej i satelitarnej pozwalają utrzymać łączność mimo szumu, tłumienia i zaników sygnału. W sieciach cyfrowych mogą współdziałać z mechanizmami detekcji błędów i retransmisji, a w zastosowaniach multimedialnych kodowanie źródłowe umożliwia zmniejszenie objętości obrazu, dźwięku i wideo^[3.5][11].

Metody kodowania pojawiają się także w kryptografii, informatyce teoretycznej i kombinatoryce. Nie są jednak tym samym co szyfrowanie: kod korekcyjny ma zwykle zapewnić poprawność odczytu informacji w obecności błędów, natomiast system kryptograficzny ma chronić poufność, integralność lub autentyczność informacji przed przeciwnikiem. Pokrewieństwo dotyczy raczej wspólnego aparatu matematycznego, w tym ciał skończonych, losowości, złożoności obliczeniowej i konstrukcji dyskretnych^[13][6.2].