Kodeks Reed-Mulor-Wikipedia

Posted on May 24, 2022 by lordneo

before-content-x4

. 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.

after-content-x4

Kod tej rodziny jest zidentyfikowana przy użyciu dwóch parametrów, ogólnie odnotowano

{DisplayStyle r}

$r$ I

{DisplayStyle M}

$m$ , nazywany odpowiednio zamówieniem i liczbą zmiennych. Te parametry interweniują w
Opis za pomocą funkcji logicznych: kod binarny trzciny-mullera

{DisplayStyle r}

$r$ W

{DisplayStyle M}

$m$ , które zauważamy

{DisplayStyle Mathrm {rm} (r, m)}

${mathrm {RM}}(r,m)$ , jest zbiorem tabel prawdy funkcji logicznych w

{DisplayStyle M}

$m$ zmienne, których normalna postać algebraiczna (ANF) jest najwyżej stopnie

after-content-x4

{DisplayStyle r}

$r$ .
Kiedy alfabet jest gotowym ciałem

{DisplayStyle Q}

$q$ elementy, po prostu rozważ funkcje

{DisplayStyle Q}

$q$ -Aires.

Table of Contents

Prosta konstrukcja [[[ modyfikator |. Modyfikator i kod ]

Wybieramy dowolne zamówienie na elementach

{DisplayStyle Mathbb {f} _ {2}^{m} = {z_ {0}, …, z_ {2^{m} -1}}}

${mathbb {F}}_{2}^{m}={z_{0},...,z_{{2^{m}-1}}}$ . Funkcja Boolana

{DisplayStyle f}

$f$ W

{DisplayStyle M}

$m$ Zmienne są następnie identyfikowane z słowem binarnym zdefiniowanym przez

{DisplayStyle C_ {f} = lewy (f (z_ {0}), …, f (z_ {2^{m} -1}) right)}

Innymi słowy,

{DisplayStyle C_ {f}}

$c_{f}$ to lista wartości pobranych przez

{DisplayStyle f}

$f$ w dowolnej kolejności, ale naprawiono.
Następnie możemy zdefiniować

{DisplayStyle Mathrm {rm} (r, m) = {c_ {f}: d (f) leq r}}

Lub

{DisplayStyle d (f)}

$d(f)$ jest stopniem ANF

{DisplayStyle f}

$f$ .

Przykład ${DisplayStyle Mathrm {rm} (1,5)}$

W przykładzie podanym we wstępie kod Reeda-Mullera zamówienia 1 na 5 zmiennych,

{DisplayStyle M}

$m$ dlatego warto

{DisplayStyle 5}

$5$

{DisplayStyle Mathbb {f} _ {2}^{5} = {z_ {0} = (0,0,0,0,0), …, Z_ {31} = (1,1,1,1 , 1)}}

Funkcje logiczne w 5 zmiennych są identyfikowane z binarnym słowem długości 32

{DisplayStyle C_ {f} = lewy (f (z_ {0}), …, f (z_ {31}) right)}

Wszystkie słowa kodu są

{DisplayStyle Mathrm {rm} (1,5) = {c_ {f}: istnieje ain mathbb {f} ^{6} | f ((x_ {0}, …, x_ {4})) = a_ {{ 0} x_ {0}+a_ {1} x_ {1}+a_ {2} x_ {2}+a_ {3} x_ {3}+a_ {4} x_ {4}+a_ {5}}}}

Zatem kod jest zbiorem prawd funkcji logicznych afektów w 5 zmiennych, tabela prawdy

{DisplayStyle f}

$f$ Bycie po prostu wektorem

{DisplayStyle C_ {f}}

$c_{f}$ .

Kolejna konstrukcja [[[ modyfikator |. Modyfikator i kod ]

Opisujemy, jak zbudować matrycę generującą kod długości

{DisplayStyle n = 2^{m}}

$n=2^{m}$ . Zapytajmy:

{DisplayStyle Mathbb {f} _ {2}^{m} = {z_ {0}, ldots, z_ {2^{m} -1}}}

W kosmosie

{DisplayStyle Mathbb {f} _ {2}^{n}}

${mathbb {F}}_{2}^{n}$ Definiujemy dla dowolnej części

{DisplayStyle AsubSet Mathbb {f} _ {2}^{m}}

$Asubset {mathbb {F}}_{2}^{m}$ , wektory

{DisplayStyle Mathbb {i} _ {A} w Mathbb {f} _ {2}^{n}}

${mathbb {I}}_{A}in {mathbb {F}}_{2}^{n}$ o

{displayStyle lewy (mathbb {i} _ {a} right) _ {i} = {begin {case} 1 & {mbox {si}} z_ {i} w \ 0 & {mbox {sinon}}} \ end {case}}} }}

Definiujemy również

{DisplayStyle Mathbb {f} _ {2}^{n}}

${mathbb {F}}_{2}^{n}$ Operacja binarna:

{DisplayStyle WWEDED Y = (W_ {1} CDOT y_ {1}, ldots, w_ {n} cdot y_ {n})}

nazywany produktem zewnętrznym.

{DisplayStyle Mathbb {f} _ {2}^{m}}

${mathbb {F}}_{2}^{m}$ jest wektorową przestrzenią w

{DisplayStyle M}

$m$ Wymiary ciała

{DisplayStyle Mathbb {f} _ {2}}

${mathbb {F}}_{2}$ , więc piszemy

{displayStyle (Mathbb {f} _ {2})^{m} = {(x_ {0}, ldots, x_ {m-1}) | x_ {i} w mathbb {f} _ {2}}}}

$({mathbb {F}}_{2})^{m}={(x_{0},ldots ,x_{{m-1}})|x_{i}in {mathbb {F}}_{2}}$

W kosmosie

{DisplayStyle Mathbb {f} _ {2}^{n}}

${mathbb {F}}_{2}^{n}$ , definiujemy wektory długości

{DisplayStyle n}

$n$ następny:

{DisplayStyle v_ {0} = (1,1,1,1,1,1,1,1)}

$v_{0}=(1,1,1,1,1,1,1,1)$ I

{DisplayStyle v_ {i} = mathbb {i} _ {h_ {i}}}

Lub

{DisplayStyle H_ {i}}

$H_i$ są hiperplanami

{displayStyle (Mathbb {f} _ {2})^{m}}

$({mathbb {F}}_{2})^{m}$ (rozmiar

{DisplayStyle n = 2^{m} -1}

$n=2^{m}-1$ ):

{DisplayStyle H_ {i} = {xin (mathbb {f} _ {2})^{m} mid x_ {i} = 0}}

Kod Reed-Muller

{displayStyle (r, m)}

$(r,m)$ uporządkowany

{DisplayStyle r}

$r$ i długość

{DisplayStyle n = 2^{m}}

$n=2^{m}$ to kod generowany przez

{DisplayStyle v_ {0}}

$v_0$ i produkt zewnętrzny od większości

{DisplayStyle r}

$r$ z

{DisplayStyle v_ {i}}

$v_{i}$ (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

{DisplayStyle f}

$f$ jest funkcją logiczną w

{DisplayStyle M}

$m$ zmienne, na

{DisplayStyle Mathbb {i} _ {a_ {f}} = c_ {f}}

Lub

{DisplayStyle C_ {f}}

$c_{f}$ jest wektorem zdefiniowanym w sekcji kodu binarnego. Wtedy łatwo to sprawdzić

{DisplayStyle Mathbb {i} _ {a_ {f}} klin mathbb {i} _ {a_ {g}} = mathbb {i} _ {a_ {fcdot g}} = c_ {fcdot g}}

Na koniec zauważ to

{DisplayStyle H_ {i} = a_ {e_ {i} +1}}

$H_{i}=A_{{e_{i}+1}}$ , Lub

{DisplayStyle e_ {i}}

$e_i$ jest koordynowany, tj.:

{DisplayStyle e_ {i} (x_ {0}, …, x_ {m-1}) = x_ {i}}

Wektor

{DisplayStyle v_ {i}}

$v_{i}$ jest zatem równe

{DisplayStyle C_ {e_ {i} +1}}

$c_{{e_{i}+1}}$ . Rodzina produktów na świeżym powietrzu

{DisplayStyle r}

$r$ wektory

{DisplayStyle v_ {i}}

$v_{i}$ , składa się zatem z wektorów formy

{DisplayStyle v_ {i_ {0}} klin … klin v_ {i_ {l}} = c _ {(e_ {i_ {0}}+1) … (e_ {i_ {l}}+1)} }

Oczywiście

{DisplayStyle {(e_ {i_ {0}}+1) … (e_ {i_ {l}}+1)}}

${(e_{{i_{0}}}+1)...(e_{{i_{l}}}+1)}$ są funkcjami logicznymi w

{DisplayStyle M}

$m$ zmienne, których stopień jest dokładnie

{displayStyle l}

$l$ I dla wszystkich

{displayStyle (i_ {0}, …, i_ {l})}

$(i_{0},...,i_{l})$ W

{DisplayStyle lleq r}

$lleq r$ , tworzą co najwyżej funkcje generowania rodziny

{DisplayStyle r}

$r$ .

Możemy to pokazać, kiedy

{DisplayStyle H = A_ {f}}

$H=A_{f}$ jest hiperplanem, funkcją

{DisplayStyle f}

$f$ 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

{DisplayStyle r}

$r$ jest przestrzenią wektorową, ten kod jest zatem liniowy. Z definicji jego długość jest

{DisplayStyle 2^{m}}

$2^{m}$ . Rodzina monomów stopnia

{DisplayStyle r}

$r$ będąc bazą tej przestrzeni i posiadanie

{DisplayStyle k = {m wybierz 0}+{m wybierz 1}+…+{m wybierz r}}

elementy, jego wymiar to

{DisplayStyle K}

$k$ .

Minimalna waga kodu

{DisplayStyle Mathrm {rm} (r, m)}

${mathrm {RM}}(r,m)$ jest uzyskiwana między innymi przez monoma stopnia

{DisplayStyle r}

$r$ i warto

{DisplayStyle 2^{M-R}}

$2^{{m-r}}$ .

Gdy

{DisplayStyle r = 1}

$r=1$ , kod

{DisplayStyle Mathrm {rm} (r, m)}

${mathrm {RM}}(r,m)$ składa się z funkcji afektu, to znaczy funkcje formy

{DisplayStyle f (x_ {0}, …, x_ {m-1}) = a_ {0} x_ {0}+…+a_ {m-1} x_ {m-1}+a_ {m {m {m {m }}

gdzie

{DisplayStyle A_ {i}}

$a_{i}$ są elementami

{DisplayStyle Mathbb {f} _ {2}}

${mathbb {F}}_{2}$ .

Minimalna odległość od kodu Reed-Muller rzędu 1 to

{DisplayStyle 2^{m-1}}

$2^{{m-1}}$ , 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ż

{DisplayStyle Mathrm {rm} (1, m)}

${mathrm {RM}}(1,m)$ .

Możesz nawet łatwo być bardziej precyzyjnym. Rzeczywiście, po prostu obliczany jest wielomianowy wyliczenie wag::

{DisplayStyle w (x, y) = sum _ {cin mathrm {rm} (1, m)} x^{w (c)} y^{2^{m} -w (c)} = y^{2 ^{m}}+(2^{m+1} -2) {x^{2^{m-1}} y^{2^{m-1}}}+x^{2^{m} }}

Lub

{DisplayStyle w (c)}

$w(c)$ określa ciężar uderzenia

{DisplayStyle C}

$c$ . Oznacza to, że istnieją 3 możliwe wagi dla słów kodowych, bądź

{DisplayStyle 0}

${displaystyle 0}$ za szlachetne słowo, bądź

{DisplayStyle 2^{m}}

$2^{m}$ Za słowo wszystko o

{DisplayStyle 1}

$1$ , albo

{DisplayStyle 2^{m-1}}

$2^{{m-1}}$ Dla wszystkich innych słów. Aby udowodnić ten wynik, po prostu rozważ kształt funkcji afinicznej podanej powyżej. Jeśli

{DisplayStyle A_ {i}}

$a_{i}$ są zero dla

{DisplayStyle iin {1, …, m-1}}

$iin {1,...,m-1}$ , jedyna wartość przyjęta przez

{DisplayStyle f}

$f$ Wschód

{DisplayStyle A_ {M}}

$a_{m}$ i otrzymujemy słowo od zera lub na jeden w zależności od wartości

{DisplayStyle A_ {M}}

$a_{m}$ Dlatego odpowiednio warunki

{DisplayStyle y^{2^{m}}}

${displaystyle Y^{2^{m}}}$ I

{DisplayStyle x^{2^{m}}}

$X^{{2^{m}}}$ . Jeśli jeden z

{DisplayStyle A_ {i}}

$a_{i}$ przynajmniej nie jest zero dla

{DisplayStyle iin {1, …, m-1}}

$iin {1,...,m-1}$ , potem elementy

{DisplayStyle x}

$x$ Jak na przykład

{DisplayStyle f (x) = 0}

$f(x)=0$ tworzyć przestrzeń do udoskonalania wymiarów

{DisplayStyle M-1}

$m-1$ . Kardynał tej przestrzeni jest zatem

{DisplayStyle 2^{m-1}}

$2^{{m-1}}$ . Wywniosujemy to wszystko

{DisplayStyle x}

$x$ Jak na przykład

{DisplayStyle f (x) = 1}

$f(x)=1$ Kardynał

{DisplayStyle 2^{m} -2^{m-1} = 2^{m-1}}

$2^{m}-2^{{m-1}}=2^{{m-1}}$ . Słowo powiązane z

{DisplayStyle f}

$f$ Podobnie jak waga

{DisplayStyle 2^{m-1}}

$2^{{m-1}}$ . .

{DisplayStyle (2^{m+1} -2)}

$(2^{{m+1}}-2)$ funkcje, dla których jedna z

{DisplayStyle A_ {i}}

$a_{i}$ przynajmniej jest to niezerowe, dlatego podaje termin

{displayStyle (2^{m+1} -2) {x^{2^{m-1}} y^{2^{m-1}}}}}

$(2^{{m+1}}-2){X^{{2^{{m-1}}}}Y^{{2^{{m-1}}}}}$ .

Artykuł Od E.F. assmus na temat kodów Reed i Mullera, szczegółowo opisując wiele właściwości tych kodów.

after-content-x4

Kodeks Reed-Mulor-Wikipedia

Prosta konstrukcja [[[ modyfikator |. Modyfikator i kod ]

Przykład ${DisplayStyle Mathrm {rm} (1,5)}$

Kolejna konstrukcja [[[ modyfikator |. Modyfikator i kod ]

Ustawienia [[[ modyfikator |. Modyfikator i kod ]

Recent Posts

Recent Comments

Archives

Categories

Meta

Prosta konstrukcja [[[ modyfikator |. Modyfikator i kod ]

Przykład RM( Pierwszy W 5 ) {DisplayStyle Mathrm {rm} (1,5)} [[[ R M ( Pierwszy W 5 ) {DisplayStyle Mathrm {rm} (1,5)} “> modyfikator |. R M ( Pierwszy W 5 ) {DisplayStyle Mathrm {rm} (1,5)} “> Modyfikator i kod ]

Kolejna konstrukcja [[[ modyfikator |. Modyfikator i kod ]

Ustawienia [[[ modyfikator |. Modyfikator i kod ]

Recent Posts

Recent Comments

Archives

Categories

Meta

Przykład ${DisplayStyle Mathrm {rm} (1,5)}$