Kody Reed-a Mullera: Korekcja błędów oparta na pseudobielach

Kod zbudowany z funkcji Boole’a, a nie tylko wzorów bitowych

Większość kodów korekcyjnych opisuje błędy jako jedynie zbiory wektorów bitowych. Kody Reed-Mullera, wprowadzone niezależnie przez Mullera w 1954 roku i Reeda tego samego roku, są nietypowe, ponieważ zaczynają się od wielomianów Boole’a. Kod RM(r, m) składa się z każdego ciągu bitowego, który jest tabelą prawdy funkcji logicznej o m zmiennych zapisanej jako wielomian stopnia co najwyżej r – a wkładem Reeda był algorytm dekodowania, dekodowanie oparte na większości, który wykorzystuje tę strukturę wielomianową bezpośrednio.

RM(r, m):  length n = 2^m,  dimension k = sum_(i=0..r) C(m, i),  min distance d = 2^(m-r)
RM(1, m):  the classic case — length 2^m, dimension m+1, distance 2^(m-1)

RM(1, m): kody pierwszego rzędu i połączenie Hadamera

RM(1, m) koduje m+1 bitów wiadomości – jeden bit stały plus m współczynników liniowych – w słowo kodowe o długości 2^m poprzez ocenianie wielomianu Booleowskiego stopnia 1 w każdym z 2^m punktów wejściowych. Każde słowo kodowe, które nie jest zerowe, różni się od każdego innego dokładnie bitami odpowiadającymi 2^(m-1), co czyni RM(1,m) równoważnym rozszerzonym kodem Hadamera. To właśnie kod użył NASA podczas misji Mariner 9 i Mariner deep-space probes na początku lat 70tych: RM(1,5), 32 bity zakodowane 6 bitami wiadomości, wybrane ze względu na ogromną odległość, która pozwalała znieść bardzo wysokie wskaźniki błędów bitowych słabego interplanetarnego połączenia radiowego.

Rekurencyjna struktura: konstrukcja |u|u+v|

Kod Reed-a Muller jest budowany rekurencyjnie z mniejszych, wykorzystując konstrukcję |u|u+v|. Przy danym kodowym słowie u z RM(r, m-1) i kodowym słowie v z RM(r-1, m-1), konkatenacja (u, u+v) stanowi poprawne kodowe słowo RM(r, m). To podwaja długość za każdym razem, gdy przechodzimy od m-1 do m, i to właśnie czyni zarówno enkoding jak i dekodowanie możliwym jako szybkie algorytmy rekurencyjne zamiast przeszukiwania tabeli – ta sama zasada leży u podstaw szybkiego transformacji Hadamard i, kilkadziesiąt lat później, konstrukcji kodów polarnych dla 5G.

Dekodowanie większościowe: głosowanie drogą do właściłego bitu

Oryginalny dekoder Reeda odzyskuje każdy współczynnik wielomianowy poprzez konstrukcję wielu różnych kombinacji liniowych otrzymanych bitów, które wszystkie w bezszumowym kodzie oceniają się do tego samego współczynnika – a następnie dokonuje się głosowania większościowego na wszystkich z nich. Ze względu na wysoką redundancję struktury wielomianu stopnia r w m zmiennych, każdy współczynnik może być sprawdzany przez dziesiątki lub setki niezależnych sum parzystości, i o ile mniej niż połowa tych sum jest uszkodzona, głosowanie większościowe nadal odzyskuje prawidłowy bit. Pozwala to na poprawianie do ⌊(d−1)/2⌋ = 2^(m-r-1) − 1 błędów przez RM(r,m), przy użyciu dekodera opartego o prostą arytmetykę XOR i liczenia zamiast skomplikowanej maszyny algebraicznej wymaganej przez kody Reed-Solomon lub BCH.

corrected bit = majority_vote( parity_sum_1, parity_sum_2, ..., parity_sum_k )
error tolerance:  t = 2^(m-r-1) - 1  bit flips, guaranteed correctable

Dlaczego kody RM wciąż mają znaczenie

Kody Reed-Solomon zostały w dużej mierze zastąpione w aplikacjach kosmicznych i archiwizacyjnych przez kody Reed-Solomon oraz później przez kody LDPC i turbo, które oferują większą liczbę bitów wiadomości na bit przesyłany przy tej samej tolerancji błędów. Jednak RM(1,m) nigdy nie zniknęło – jest matematycznie identyczny z kodem pierwszego rzędu używanym w sekwencjach rozpraszania CDMA, a ogólna rodzina RM(r,m) ponownie pojawiła się w 2016 roku jako blisko-optymalny blok budulcowy dla kodów polarnych, kodów kanałowych znormalizowanych do kanałów sterujących 5G. Rekurencyjny |u|u+v| struktura, która sprawiała, że ​​dekodowanie większości logicznej z lat 1950-tych było praktyczne, jest tą samą strukturą, która sprawia, że ​​nowoczesne dekodery sukcesywno-wyczerpujące są szybkie.

Frequently asked questions

Wypróbuj na żywo

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