[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/kodeks-reed-mulor-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/kodeks-reed-mulor-wikipedia\/","headline":"Kodeks Reed-Mulor-Wikipedia","name":"Kodeks Reed-Mulor-Wikipedia","description":"before-content-x4 . Kody de Reed-Muller s\u0105 liniowymi kodami korekcyjnymi. Ta rodzina kod\u00f3w, pocz\u0105tkowo binarna, zawdzi\u0119cza swoj\u0105 nazw\u0119 dzie\u0142 Davida E.","datePublished":"2022-05-24","dateModified":"2022-05-24","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/0d1ecb613aa2984f0576f70f86650b7c2a132538","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/0d1ecb613aa2984f0576f70f86650b7c2a132538","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/kodeks-reed-mulor-wikipedia\/","wordCount":15372,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4. Kody de Reed-Muller s\u0105 liniowymi kodami korekcyjnymi. Ta rodzina kod\u00f3w, pocz\u0105tkowo binarna, zawdzi\u0119cza swoj\u0105 nazw\u0119 dzie\u0142 Davida E. Mullera, kt\u00f3ry zaproponowa\u0142 zasad\u0119 kodeksu i Irvingowi S. Reedowi, kt\u00f3ra zaproponowa\u0142a technik\u0119 dekodowania, opublikowan\u0105 w 1954 r. Od tego czasu ta rodzina jest szeroko badane i uog\u00f3lnione na gotowe cia\u0142a ponad 2 element\u00f3w. Historycznie, kod trzciny z rz\u0119du 1 na 5 zmiennych, kt\u00f3ry ma 64 s\u0142owa o d\u0142ugo\u015bci 32 i koryguje 7 b\u0142\u0119d\u00f3w, sondy u\u017cy\u0142 Marynarz Uruchomione przez NASA w latach 1969\u20131973, aby zapewni\u0107 poprawn\u0105 (cyfrow\u0105) transmisj\u0119 zdj\u0119\u0107 Marsa.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Kod tej rodziny jest zidentyfikowana przy u\u017cyciu dw\u00f3ch parametr\u00f3w, og\u00f3lnie odnotowano R {DisplayStyle r} I M {DisplayStyle M} , nazywany odpowiednio zam\u00f3wieniem i liczb\u0105 zmiennych. Te parametry interweniuj\u0105 wOpis za pomoc\u0105 funkcji logicznych: kod binarny trzciny-mullera        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4R {DisplayStyle r} W M {DisplayStyle M} , kt\u00f3re zauwa\u017camy R M ( R W M ) {DisplayStyle Mathrm {rm} (r, m)} , jest zbiorem tabel prawdy funkcji logicznych w M {DisplayStyle M} zmienne, kt\u00f3rych normalna posta\u0107 algebraiczna (ANF) jest najwy\u017cej stopnie        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4R {DisplayStyle r} .Kiedy alfabet jest gotowym cia\u0142em Q {DisplayStyle Q} elementy, po prostu rozwa\u017c funkcje Q {DisplayStyle Q} -Aires.   Table of ContentsProsta konstrukcja [[[ modyfikator |. Modyfikator i kod ] Przyk\u0142ad 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 ] Prosta konstrukcja [[[ modyfikator |. Modyfikator i kod ] Wybieramy dowolne zam\u00f3wienie na elementach F 2 M = { z 0 W . . . W z 2m– Pierwszy } {DisplayStyle Mathbb {f} _ {2}^{m} = {z_ {0}, …, z_ {2^{m} -1}}} . Funkcja Boolana F {DisplayStyle f} W M {DisplayStyle M} Zmienne s\u0105 nast\u0119pnie identyfikowane z s\u0142owem binarnym zdefiniowanym przez C f= ( f(z0),...,f(z2m\u22121)) {DisplayStyle C_ {f} = lewy (f (z_ {0}), …, f (z_ {2^{m} -1}) right)} Innymi s\u0142owy, C F {DisplayStyle C_ {f}} to lista warto\u015bci pobranych przez F {DisplayStyle f} w dowolnej kolejno\u015bci, ale naprawiono.Nast\u0119pnie mo\u017cemy zdefiniowa\u0107 R M ( R W M ) = { C f: D ( F ) \u2264 R } {DisplayStyle Mathrm {rm} (r, m) = {c_ {f}: d (f) leq r}} Lub D ( F ) {DisplayStyle d (f)} jest stopniem ANF F {DisplayStyle f} . Przyk\u0142ad 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 ] W przyk\u0142adzie podanym we wst\u0119pie kod Reeda-Mullera zam\u00f3wienia 1 na 5 zmiennych, M {DisplayStyle M} dlatego warto 5 {DisplayStyle 5}  F25= { z 0= ( 0 W 0 W 0 W 0 W 0 ) W . . . W z 31= ( Pierwszy W Pierwszy W Pierwszy W Pierwszy W Pierwszy ) } {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\u0105 identyfikowane z binarnym s\u0142owem d\u0142ugo\u015bci 32 C f= ( f(z0),...,f(z31)) {DisplayStyle C_ {f} = lewy (f (z_ {0}), …, f (z_ {31}) right)} Wszystkie s\u0142owa kodu s\u0105 R M ( Pierwszy W 5 ) = { C f: \u2203 A \u2208 F6|. F ( ( X 0W . . . W X 4) ) = A 0X 0+ A 1X 1+ A 2X 2+ A 3X 3+ A 4X 4+ A 5} {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\u00f3w w 5 zmiennych, tabela prawdy F {DisplayStyle f} Bycie po prostu wektorem C F {DisplayStyle C_ {f}} . Kolejna konstrukcja [[[ modyfikator |. Modyfikator i kod ] Opisujemy, jak zbudowa\u0107 matryc\u0119 generuj\u0105c\u0105 kod d\u0142ugo\u015bci N = 2 M {DisplayStyle n = 2^{m}} . Zapytajmy: F2m= { z 0W … W z 2m\u22121} {DisplayStyle Mathbb {f} _ {2}^{m} = {z_ {0}, ldots, z_ {2^{m} -1}}} W kosmosie F 2 N {DisplayStyle Mathbb {f} _ {2}^{n}} Definiujemy dla dowolnej cz\u0119\u015bci A \u2282 F 2 M {DisplayStyle AsubSet Mathbb {f} _ {2}^{m}} , wektory I A \u2208 F 2 N {DisplayStyle Mathbb {i} _ {A} w Mathbb {f} _ {2}^{n}} o (IA)i= {1\u00a0si\u00a0zi\u2208A0\u00a0sinon{displayStyle lewy (mathbb {i} _ {a} right) _ {i} = {begin {case} 1 & {mbox {si}} z_ {i} w \\ 0 & {mbox {sinon}}} \\ end {case}}} }} Definiujemy r\u00f3wnie\u017c F 2 N {DisplayStyle Mathbb {f} _ {2}^{n}} Operacja binarna: w \u2227 I = ( w 1\u22c5 I 1W … W w n\u22c5 I n) {DisplayStyle WWEDED Y = (W_ {1} CDOT y_ {1}, ldots, w_ {n} cdot y_ {n})} nazywany produktem zewn\u0119trznym. F 2 M {DisplayStyle Mathbb {f} _ {2}^{m}} jest wektorow\u0105 przestrzeni\u0105 w M {DisplayStyle M} Wymiary cia\u0142a F 2 {DisplayStyle Mathbb {f} _ {2}} , wi\u0119c piszemy ( F 2 ) M = { ( X 0 W … W X M – Pierwszy ) |. X I \u2208 F 2 } {displayStyle (Mathbb {f} _ {2})^{m} = {(x_ {0}, ldots, x_ {m-1}) | x_ {i} w mathbb {f} _ {2}}}}  W kosmosie F 2 N {DisplayStyle Mathbb {f} _ {2}^{n}} , definiujemy wektory d\u0142ugo\u015bci N {DisplayStyle n} nast\u0119pny: W 0 = ( Pierwszy W Pierwszy W Pierwszy W Pierwszy W Pierwszy W Pierwszy W Pierwszy W Pierwszy ) {DisplayStyle v_ {0} = (1,1,1,1,1,1,1,1)} I W i= IHi{DisplayStyle v_ {i} = mathbb {i} _ {h_ {i}}} Lub H I {DisplayStyle H_ {i}} s\u0105 hiperplanami ( F 2 ) M {displayStyle (Mathbb {f} _ {2})^{m}} (rozmiar N = 2 M – Pierwszy {DisplayStyle n = 2^{m} -1} ): H i= { X \u2208 ( F2) m\u2223 X i= 0 } {DisplayStyle H_ {i} = {xin (mathbb {f} _ {2})^{m} mid x_ {i} = 0}} Kod Reed-Muller ( R W M ) {displayStyle (r, m)} uporz\u0105dkowany R {DisplayStyle r} i d\u0142ugo\u015b\u0107 N = 2 M {DisplayStyle n = 2^{m}} to kod generowany przez W 0 {DisplayStyle v_ {0}} i produkt zewn\u0119trzny od wi\u0119kszo\u015bci R {DisplayStyle r} z W I {DisplayStyle v_ {i}} (Zgodnie z porozumieniem, je\u015bli istnieje mniej ni\u017c jeden wektor, produkt zewn\u0119trzny jest stosowany jako to\u017csamo\u015b\u0107). W rzeczywisto\u015bci kryje si\u0119 za t\u0105 konstrukcj\u0105, podawane przez funkcje logiczne. Rzeczywi\u015bcie, je\u015bli F {DisplayStyle f} jest funkcj\u0105 logiczn\u0105 w M {DisplayStyle M} zmienne, na IAf= C f{DisplayStyle Mathbb {i} _ {a_ {f}} = c_ {f}} na stawianiu A f= { z \u2208 F2m: F ( z ) = Pierwszy } {DisplayStyle A_ {f} = {Zin Mathbb {f} _ {2}^{m}: f (z) = 1}} Lub C F {DisplayStyle C_ {f}} jest wektorem zdefiniowanym w sekcji kodu binarnego. Wtedy \u0142atwo to sprawdzi\u0107 IAf\u2227 IAg= IAf\u22c5g= C f\u22c5g{DisplayStyle Mathbb {i} _ {a_ {f}} klin mathbb {i} _ {a_ {g}} = mathbb {i} _ {a_ {fcdot g}} = c_ {fcdot g}} Na koniec zauwa\u017c to H I = A ei+ Pierwszy {DisplayStyle H_ {i} = a_ {e_ {i} +1}} , Lub To jest I {DisplayStyle e_ {i}} jest koordynowany, tj.: To jest i( X 0W . . . W X m\u22121) = X i{DisplayStyle e_ {i} (x_ {0}, …, x_ {m-1}) = x_ {i}} Wektor W I {DisplayStyle v_ {i}} jest zatem r\u00f3wne C ei+ Pierwszy {DisplayStyle C_ {e_ {i} +1}} . Rodzina produkt\u00f3w na \u015bwie\u017cym powietrzu R {DisplayStyle r} wektory W I {DisplayStyle v_ {i}} , sk\u0142ada si\u0119 zatem z wektor\u00f3w formy W i0\u2227 . . . \u2227 W il= C (ei0+1)...(eil+1){DisplayStyle v_ {i_ {0}} klin … klin v_ {i_ {l}} = c _ {(e_ {i_ {0}}+1) … (e_ {i_ {l}}+1)} } z L \u2264 R {DisplayStyle lleq r} . Oczywi\u015bcie ( To jest i0+ Pierwszy ) . . . ( To jest il+ Pierwszy ) {DisplayStyle {(e_ {i_ {0}}+1) … (e_ {i_ {l}}+1)}} s\u0105 funkcjami logicznymi w M {DisplayStyle M} zmienne, kt\u00f3rych stopie\u0144 jest dok\u0142adnie L {displayStyle l} I dla wszystkich ( I 0 W . . . W I L ) {displayStyle (i_ {0}, …, i_ {l})} W L \u2264 R {DisplayStyle lleq r} , tworz\u0105 co najwy\u017cej funkcje generowania rodziny R {DisplayStyle r} . Mo\u017cemy to pokaza\u0107, kiedy H = A F {DisplayStyle H = A_ {f}} jest hiperplanem, funkcj\u0105 F {DisplayStyle f} jest rafina. Dlatego wystarczy rozwa\u017cy\u0107 hiperplany spowodowane niezale\u017cnymi funkcjami liniowymi w celu uzyskania w ten spos\u00f3b kod\u00f3w trzciny-mullera. Ustawienia [[[ modyfikator |. Modyfikator i kod ] Wszystkie logiczne funkcje stopnia co najwy\u017cej R {DisplayStyle r} jest przestrzeni\u0105 wektorow\u0105, ten kod jest zatem liniowy. Z definicji jego d\u0142ugo\u015b\u0107 jest 2 M {DisplayStyle 2^{m}} . Rodzina monom\u00f3w stopnia R {DisplayStyle r} b\u0119d\u0105c baz\u0105 tej przestrzeni i posiadanie k = (m0)+ (m1)+ . . . + (mr){DisplayStyle k = {m wybierz 0}+{m wybierz 1}+…+{m wybierz r}} elementy, jego wymiar to k {DisplayStyle K} . Minimalna waga kodu R M ( R W M ) {DisplayStyle Mathrm {rm} (r, m)} jest uzyskiwana mi\u0119dzy innymi przez monoma stopnia R {DisplayStyle r} i warto 2 M – R {DisplayStyle 2^{M-R}} . Gdy R = Pierwszy {DisplayStyle r = 1} , kod R M ( R W M ) {DisplayStyle Mathrm {rm} (r, m)} sk\u0142ada si\u0119 z funkcji afektu, to znaczy funkcje formy F ( X 0W . . . W X m\u22121) = A 0X 0+ . . . + A m\u22121X m\u22121+ A m{DisplayStyle f (x_ {0}, …, x_ {m-1}) = a_ {0} x_ {0}+…+a_ {m-1} x_ {m-1}+a_ {m {m {m {m }} gdzie A I {DisplayStyle A_ {i}} s\u0105 elementami F 2 {DisplayStyle Mathbb {f} _ {2}} . Minimalna odleg\u0142o\u015b\u0107 od kodu Reed-Muller rz\u0119du 1 to 2 M – Pierwszy {DisplayStyle 2^{m-1}} , co czyni go optymalnym kodem zgodnie z terminalem Griesmer: kod o co najmniej tyle s\u0142\u00f3w i minimalna odleg\u0142o\u015b\u0107 co najmniej tak du\u017canie mo\u017ce by\u0107 kr\u00f3tszy ni\u017c R M ( Pierwszy W M ) {DisplayStyle Mathrm {rm} (1, m)} . Mo\u017cesz nawet \u0142atwo by\u0107 bardziej precyzyjnym. Rzeczywi\u015bcie, po prostu obliczany jest wielomianowy wyliczenie wag:: W ( X W I ) = \u2211 c\u2208RM(1,m)X w(c)I 2m\u2212w(c)= I 2m+ ( 2 m+1– 2 ) X2m\u22121Y2m\u22121+ X 2m{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 w ( C ) {DisplayStyle w (c)} okre\u015bla ci\u0119\u017car uderzenia C {DisplayStyle C} . Oznacza to, \u017ce istniej\u0105 3 mo\u017cliwe wagi dla s\u0142\u00f3w kodowych, b\u0105d\u017a 0 {DisplayStyle 0} za szlachetne s\u0142owo, b\u0105d\u017a 2 M {DisplayStyle 2^{m}} Za s\u0142owo wszystko o Pierwszy {DisplayStyle 1} , albo 2 M – Pierwszy {DisplayStyle 2^{m-1}} Dla wszystkich innych s\u0142\u00f3w. Aby udowodni\u0107 ten wynik, po prostu rozwa\u017c kszta\u0142t funkcji afinicznej podanej powy\u017cej. Je\u015bli A I {DisplayStyle A_ {i}} s\u0105 zero dla I \u2208 { Pierwszy W . . . W M – Pierwszy } {DisplayStyle iin {1, …, m-1}} , jedyna warto\u015b\u0107 przyj\u0119ta przez F {DisplayStyle f} Wsch\u00f3d A M {DisplayStyle A_ {M}} i otrzymujemy s\u0142owo od zera lub na jeden w zale\u017cno\u015bci od warto\u015bci A M {DisplayStyle A_ {M}} Dlatego odpowiednio warunki I 2m{DisplayStyle y^{2^{m}}} I X 2m{DisplayStyle x^{2^{m}}} . Je\u015bli jeden z A I {DisplayStyle A_ {i}} przynajmniej nie jest zero dla I \u2208 { Pierwszy W . . . W M – Pierwszy } {DisplayStyle iin {1, …, m-1}} , potem elementy X {DisplayStyle x} Jak na przyk\u0142ad F ( X ) = 0 {DisplayStyle f (x) = 0} tworzy\u0107 przestrze\u0144 do udoskonalania wymiar\u00f3w M – Pierwszy {DisplayStyle M-1} . Kardyna\u0142 tej przestrzeni jest zatem 2 M – Pierwszy {DisplayStyle 2^{m-1}} . Wywniosujemy to wszystko X {DisplayStyle x} Jak na przyk\u0142ad F ( X ) = Pierwszy {DisplayStyle f (x) = 1} Kardyna\u0142 2 M – 2 M – Pierwszy = 2 M – Pierwszy {DisplayStyle 2^{m} -2^{m-1} = 2^{m-1}} . S\u0142owo powi\u0105zane z F {DisplayStyle f} Podobnie jak waga 2 M – Pierwszy {DisplayStyle 2^{m-1}} . . ( 2 M + Pierwszy – 2 ) {DisplayStyle (2^{m+1} -2)} funkcje, dla kt\u00f3rych jedna z A I {DisplayStyle A_ {i}} przynajmniej jest to niezerowe, dlatego podaje termin ( 2 M + Pierwszy – 2 ) X 2m\u22121I 2m\u22121{displayStyle (2^{m+1} -2) {x^{2^{m-1}} y^{2^{m-1}}}}} . Artyku\u0142 Od E.F. assmus na temat kod\u00f3w Reed i Mullera, szczeg\u00f3\u0142owo opisuj\u0105c wiele w\u0142a\u015bciwo\u015bci tych kod\u00f3w.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/kodeks-reed-mulor-wikipedia\/#breadcrumbitem","name":"Kodeks Reed-Mulor-Wikipedia"}}]}]