PL 
EnglishDomyślny
Українська💻 Kody Reeda-Mullera
Interaktywna wizualizacja kodów korekcyjnych Reeda-Mullera stosowanych w łączności dalekiego zasięgu w kosmosie.
O kodach Reeda-Mullera
Kody Reeda-Mullera, wprowadzone niezależnie przez Davida Mullera (1954) i Irvinga Reeda (1954), to rodzina liniowych kodów korekcyjnych o wyjątkowo dużych minimalnych odległościach Hamminga, co czyni je jednymi z najpotężniejszych kodów dla kanałów o wysokim poziomie szumu. Kod Reeda-Mullera pierwszego rzędu R(1, m) koduje k = m + 1 bitów informacji w n = 2ᵐ bitów słowa kodowego, używając macierzy generującej (2ᵐ) × (m+1), której kolumny reprezentują wszystkie 2ᵐ wektory binarne; minimalna odległość między dowolnymi dwoma słowami kodowymi wynosi dokładnie 2^(m−1), co oznacza, że kod może skorygować do 2^(m−2) − 1 błędów. Ich najsłynniejszym praktycznym zastosowaniem była transmisja pierwszych kolorowych fotografii Marsa przez sondę Mariner 9 NASA w 1972 roku, przy użyciu R(1, 5): 32-bitowego słowa kodowego przenoszącego 6 bitów danych obrazu przez zaszumione łącze radiowe dalekiego kosmosu.
Ten symulator wizualizuje pełen potok kodowania: wybierz m (2 do 5), wprowadź wiadomość, obserwuj mnożenie przez macierz generującą nad GF(2), a następnie wprowadź losowe błędy bitowe lub błędy seryjne i obserwuj, jak dekoder logiki większościowej odtwarza oryginalną wiadomość. Wyświetlacz odległości Hamminga pokazuje, jak daleko odebrane słowo jest od każdego prawidłowego słowa kodowego, a krzywa BER (współczynnika błędów bitowych) przedstawia zdolność korekcji w zależności od liczby błędów.
Najczęściej zadawane pytania
Jaka jest minimalna odległość Hamminga R(1, m) i ile błędów może skorygować?
Kod Reeda-Mullera pierwszego rzędu R(1, m) ma minimalną odległość Hamminga d = 2^(m−1). Kod o minimalnej odległości d może wykryć do d − 1 błędów i skorygować do ⌊(d−1)/2⌋ błędów. Dla R(1, 5): d = 16, więc może skorygować do 7 błędów bitowych w dowolnym odebranym 32-bitowym słowie. Dla R(1, 4): d = 8, korygując do 3 błędów w 16-bitowym słowie. Ta duża odległość względem długości bloku jest wyjątkowa — wiele popularnych kodów osiąga znacznie mniejsze stosunki odległości do długości.
Jak działa dekodowanie logiki większościowej dla R(1, m)?
Dekoder logiki większościowej Reeda z 1954 roku oblicza m+1 niezależnych równań kontroli parzystości dla każdego z m+1 bitów wiadomości, przy czym każde równanie obejmuje 2^(m−1) pozycji odebranego słowa. Jeśli więcej niż połowa z 2^(m−1) estymat jest zgodna (głosowanie większościowe), ten bit jest dekodowany jako wartość większościowa. Ponieważ minimalna odległość wynosi 2^(m−1), do 2^(m−2) − 1 błędów nie może przechylić większości przeciw poprawnemu bitowi. To dekodowanie działa w O(m · 2ᵐ) operacji — liniowo względem długości bloku dla stałego m — i jest wystarczająco proste, by zaimplementować je w sprzęcie sondy kosmicznej z początku lat 70.
Jakie są parametry (n, k, d) popularnych kodów Reeda-Mullera?
Dla R(1, m): długość bloku n = 2ᵐ, wymiar k = m + 1, minimalna odległość d = 2^(m−1). Przykłady: R(1,2) = (4, 3, 2) — pojedynczy kod kontroli parzystości; R(1,3) = (8, 4, 4) — równoważny rozszerzonemu kodowi Hamminga; R(1,4) = (16, 5, 8); R(1,5) = (32, 6, 16) — kod Marinera. Współczynnik kodowania k/n = (m+1)/2ᵐ szybko maleje wraz z m: R(1,5) ma współczynnik 6/32 ≈ 0,19, co oznacza, że 81% przesyłanych bitów to redundancja dla korekcji błędów.
Jak kody Reeda-Mullera były wykorzystane przez sondę Mariner 9?
Mariner 9, wystrzelony w 1971 roku, pierwsza sonda kosmiczna na orbicie innej planety, używał R(1, 5) do transmisji obrazów 64×64 pikseli z 64 poziomami szarości (6 bitów na piksel) na dystansie 100 milionów kilometrów. Każdy piksel był kodowany jako 32-bitowe słowo kodowe; łącze zstępujące 37,5 kb/s z jego wrodzonym szumem i odwróceniami bitów było korygowane na Ziemi przed rekonstrukcją obrazu. Bez korekcji błędów odebrane obrazy byłyby poważnie zdegradowane; dzięki zdolności korekcyjnej R(1,5) naukowcy otrzymali wystarczająco wyraźne obrazy, by zmapować ponad 7000 marsjańskich formacji.
Jaka jest pełna hierarchia kodów Reeda-Mullera R(r, m)?
Ogólny kod Reeda-Mullera R(r, m) ma parametry: n = 2ᵐ, k = Σᵢ₌₀ʳ C(m, i), d = 2^(m−r). Parametr r to „rząd”: R(0, m) to prosty kod powtórzeniowy (1 bit, współczynnik 1/2ᵐ, maksymalna odległość), R(1, m) to rząd pierwszy (omówiony wyżej), R(m−1, m) to rozszerzony kod Hamminga (współczynnik (2ᵐ − 1)/2ᵐ, odległość 4), R(m, m) to trywialny kod bez redundancji. Każde R(r, m) zawiera R(r−1, m) jako podkod. Ta zagnieżdżona struktura jest wykorzystywana w rekurencyjnych algorytmach dekodowania oraz w konstrukcji kodów polarnych (Arıkan, 2009), używanych w standardach 5G.
Czy kody Reeda-Mullera są wykorzystywane we współczesnych systemach komunikacyjnych?
Klasyczne kody Reeda-Mullera nie są szeroko stosowane we współczesnych łączach o wysokiej przepustowości, ponieważ ich niski współczynnik kodowania (zwłaszcza pierwszego rzędu) marnuje zbyt dużo pasma. Jednak ich struktura matematyczna jest fundamentalna. Kody polarne — używane w kanałach kontrolnych 5G NR (TS 38.212) — są dowiedlnie powiązane z kodami Reeda-Mullera i dzielą ich rekurencyjną strukturę; w rzeczywistości R(1, m) jest szczególnym przypadkiem kodu polarnego. Kody Reeda-Mullera drugiego rzędu są używane w niektórych sekwencjach rozpraszających CDMA, a RM(1, 5) pozostaje punktem odniesienia w akademickich badaniach nad kodowaniem kanału.
Jak błąd seryjny wpływa na dekodowanie Reeda-Mullera?
Dekodowanie logiki większościowej dla R(1, m) zakłada, że błędy są rozłożone niezależnie — koryguje dowolny wzorzec do t = 2^(m−2) − 1 błędów niezależnie od pozycji. Błąd seryjny (kolejne odwrócone bity) o długości b wpływa na b pozycji w odebranym słowie; jeśli b ≤ t, jest korygowany normalnie. Jeśli b > t, ale seria jest skoncentrowana w pojedynczym równaniu kontroli parzystości, a nie rozłożona na wszystkie równania, głosowanie większościowe może się nadal powieść. Jednak długie błędy seryjne obejmujące wiele równań mogą przechylić większość, powodując niepowodzenie dekodowania. Przeplatanie (tasowanie bitów słowa kodowego między transmisjami) to standardowe środek zaradczy dla kanałów seryjnych.
Jaki jest związek między kodami Reeda-Mullera a funkcjami boolowskimi?
Istnieje bezpośrednia bijekcja: każde słowo kodowe R(r, m) odpowiada tablicy prawdy funkcji boolowskiej m zmiennych o stopniu algebraicznym co najwyżej r. Kod pierwszego rzędu R(1, m) odpowiada afinicznym funkcjom boolowskim (funkcjom liniowym plus stała). To powiązanie oznacza, że dekodowanie R(1, m) jest równoważne aproksymacji dowolnej funkcji boolowskiej najbliższą funkcją afiniczną — problemowi centralnemu dla teorii uczenia się (twierdzenie Goldreicha-Levina) i kryptoanalizy (ataki na transformatę Walsha-Hadamarda na szyfry strumieniowe).
Jak działa kodowanie za pomocą macierzy generującej?
Dla R(1, m) macierz generująca G o wymiarach (m+1) × 2ᵐ ma pierwszy wiersz złożony z samych jedynek (wektor jedynkowy) oraz m dodatkowych wierszy, gdzie wiersz i+1 to binarna reprezentacja indeksu kolumny j na pozycji bitowej i (wiersze „maski bitowej”). Aby zakodować (m+1)-bitowy wektor wiadomości u, oblicz słowo kodowe c = u · G nad GF(2) (arytmetyka binarnego ciała — dodawanie to XOR, mnożenie to AND). Wynikowe 2ᵐ-bitowe słowo kodowe jest superpozycją samych zer, samych jedynek i kombinacji XOR m wierszy „masek” wybranych przez bity wiadomości.
Jaki jest związek między kodami Reeda-Mullera a kodami Hadamarda?
Kod Reeda-Mullera pierwszego rzędu R(1, m) i kod Hadamarda o długości 2ᵐ są blisko powiązane: R(1, m) składa się dokładnie z tych wierszy (i ich dopełnień) macierzy Hadamarda 2ᵐ × 2ᵐ. Kod Hadamarda to zbiór wszystkich 2^(m+1) wektorów ±1 z wierszy macierzy, co odpowiada 2^(m+1) słowom kodowym R(1, m) (ponieważ każda wiadomość ma jedno słowo kodowe i jego dopełnienie). Dekodowanie logiki większościowej R(1, m) jest równoważne obliczeniu szybkiej transformaty Walsha-Hadamarda, osiągalnej w O(2ᵐ · m) = O(n log n) operacjach.
Czy kody Reeda-Mullera mogą osiągnąć granicę pojemności Shannona?
Kody Reeda-Mullera pierwszego rzędu nie osiągają pojemności Shannona: ich współczynnik (m+1)/2ᵐ maleje do zera wraz ze wzrostem m, podczas gdy kody osiągające pojemność utrzymują niezerowy współczynnik. Jednak Reeves i Pfister (2021) udowodnili, że kody Reeda-Mullera wyższego rzędu R(r, m) z r/m → stała zbliżają się do pojemności Shannona na binarnym kanale wymazywania, gdy m → ∞. Kody polarne (rodzina powiązana z RM) były pierwszymi jawnie skonstruowanymi kodami dowiedzionymi jako osiągające pojemność Shannona na wszystkich symetrycznych kanałach binarnych. Kody Reeda-Solomona (inna rodzina) zbliżają się do pojemności na kanałach q-arnych.