. Kody de Reed-Muller są liniowymi kodami korekcyjnymi. Ta rodzina kodów, początkowo binarna, zawdzięcza swoją nazwę dzieł Davida E. Mullera, który zaproponował zasadę kodeksu i Irvingowi S. Reedowi, która zaproponowała technikę dekodowania, opublikowaną w 1954 r. Od tego czasu ta rodzina jest szeroko badane i uogólnione na gotowe ciała ponad 2 elementów. Historycznie, kod trzciny z rzędu 1 na 5 zmiennych, który ma 64 słowa o długości 32 i koryguje 7 błędów, sondy użył Marynarz Uruchomione przez NASA w latach 1969–1973, aby zapewnić poprawną (cyfrową) transmisję zdjęć Marsa.
Kod tej rodziny jest zidentyfikowana przy użyciu dwóch parametrów, ogólnie odnotowano
I
, nazywany odpowiednio zamówieniem i liczbą zmiennych. Te parametry interweniują w
Opis za pomocą funkcji logicznych: kod binarny trzciny-mullera
W
, które zauważamy
, jest zbiorem tabel prawdy funkcji logicznych w
zmienne, których normalna postać algebraiczna (ANF) jest najwyżej stopnie
.
Kiedy alfabet jest gotowym ciałem
elementy, po prostu rozważ funkcje
-Aires.
Prosta konstrukcja [[[ modyfikator |. Modyfikator i kod ]
Wybieramy dowolne zamówienie na elementach
. Funkcja Boolana
W
Zmienne są następnie identyfikowane z słowem binarnym zdefiniowanym przez
-
Innymi słowy,
to lista wartości pobranych przez
w dowolnej kolejności, ale naprawiono.
Następnie możemy zdefiniować
-
Lub
jest stopniem ANF
.
Przykład
[[[
“> modyfikator |.
“> Modyfikator i kod ]
W przykładzie podanym we wstępie kod Reeda-Mullera zamówienia 1 na 5 zmiennych,
dlatego warto
-
.
Funkcje logiczne w 5 zmiennych są identyfikowane z binarnym słowem długości 32
-
Wszystkie słowa kodu są
-
Zatem kod jest zbiorem prawd funkcji logicznych afektów w 5 zmiennych, tabela prawdy
Bycie po prostu wektorem
.
Kolejna konstrukcja [[[ modyfikator |. Modyfikator i kod ]
Opisujemy, jak zbudować matrycę generującą kod długości
. Zapytajmy:
-
W kosmosie
Definiujemy dla dowolnej części
, wektory
o
-
Definiujemy również
Operacja binarna:
-
nazywany produktem zewnętrznym.
jest wektorową przestrzenią w
Wymiary ciała
, więc piszemy
W kosmosie
, definiujemy wektory długości
następny:
I
-
Lub
są hiperplanami
(rozmiar
):
-
Kod Reed-Muller
uporządkowany
i długość
to kod generowany przez
i produkt zewnętrzny od większości
z
(Zgodnie z porozumieniem, jeśli istnieje mniej niż jeden wektor, produkt zewnętrzny jest stosowany jako tożsamość).
W rzeczywistości kryje się za tą konstrukcją, podawane przez funkcje logiczne. Rzeczywiście, jeśli
jest funkcją logiczną w
zmienne, na
-
na stawianiu
Lub
jest wektorem zdefiniowanym w sekcji kodu binarnego. Wtedy łatwo to sprawdzić
-
Na koniec zauważ to
, Lub
jest koordynowany, tj.:
-
Wektor
jest zatem równe
. Rodzina produktów na świeżym powietrzu
wektory
, składa się zatem z wektorów formy
-
z
.
Oczywiście
są funkcjami logicznymi w
zmienne, których stopień jest dokładnie
I dla wszystkich
W
, tworzą co najwyżej funkcje generowania rodziny
.
Możemy to pokazać, kiedy
jest hiperplanem, funkcją
jest rafina. Dlatego wystarczy rozważyć hiperplany spowodowane niezależnymi funkcjami liniowymi w celu uzyskania w ten sposób kodów trzciny-mullera.
Ustawienia [[[ modyfikator |. Modyfikator i kod ]
Wszystkie logiczne funkcje stopnia co najwyżej
jest przestrzenią wektorową, ten kod jest zatem liniowy. Z definicji jego długość jest
. Rodzina monomów stopnia
będąc bazą tej przestrzeni i posiadanie
-
elementy, jego wymiar to
.
Minimalna waga kodu
jest uzyskiwana między innymi przez monoma stopnia
i warto
.
Gdy
, kod
składa się z funkcji afektu, to znaczy funkcje formy
-
gdzie
są elementami
.
Minimalna odległość od kodu Reed-Muller rzędu 1 to
, co czyni go optymalnym kodem zgodnie z terminalem Griesmer: kod o co najmniej tyle słów i minimalna odległość co najmniej tak duża
nie może być krótszy niż
.
Możesz nawet łatwo być bardziej precyzyjnym. Rzeczywiście, po prostu obliczany jest wielomianowy wyliczenie wag::
-
Lub
określa ciężar uderzenia
. Oznacza to, że istnieją 3 możliwe wagi dla słów kodowych, bądź
za szlachetne słowo, bądź
Za słowo wszystko o
, albo
Dla wszystkich innych słów. Aby udowodnić ten wynik, po prostu rozważ kształt funkcji afinicznej podanej powyżej. Jeśli
są zero dla
, jedyna wartość przyjęta przez
Wschód
i otrzymujemy słowo od zera lub na jeden w zależności od wartości
Dlatego odpowiednio warunki
I
. Jeśli jeden z
przynajmniej nie jest zero dla
, potem elementy
Jak na przykład
tworzyć przestrzeń do udoskonalania wymiarów
. Kardynał tej przestrzeni jest zatem
. Wywniosujemy to wszystko
Jak na przykład
Kardynał
. Słowo powiązane z
Podobnie jak waga
. .
funkcje, dla których jedna z
przynajmniej jest to niezerowe, dlatego podaje termin
.
Artykuł Od E.F. assmus na temat kodów Reed i Mullera, szczegółowo opisując wiele właściwości tych kodów.
Recent Comments