Reed-Mullerův kód - Reed–Muller code
Reed-Mullerův kód RM (r, m) | |
---|---|
Pojmenoval podle | Irving S. Reed a David E. Muller |
Klasifikace | |
Typ | Lineární kód bloku |
Délka bloku | |
Délka zprávy | |
Hodnotit | |
Vzdálenost | |
Velikost abecedy | |
Zápis | -kód |
Reed-Mullerovy kódy jsou kódy opravující chyby které se používají v aplikacích bezdrátové komunikace, zejména v komunikaci v hlubokém vesmíru[1]. Navíc navrhované 5G standard[2] spoléhá na úzce související polární kódy[3] pro opravu chyb v řídicím kanálu. Díky svým příznivým teoretickým a matematickým vlastnostem byly kódy Reed – Muller také rozsáhle studovány v roce teoretická informatika.
Reed-Mullerovy kódy zobecňují Reed-Solomon kódy a Walsh – Hadamardův kód. Kódy Reed – Muller jsou lineární blokové kódy to jsou místně testovatelné, lokálně dekódovatelné, a seznam dekódovatelný. Díky těmto vlastnostem jsou zvláště užitečné při navrhování pravděpodobnostně ověřitelné důkazy.
Tradiční Reed – Mullerovy kódy jsou binární kódy, což znamená, že zprávy a kódová slova jsou binární řetězce. Když r a m jsou celá čísla s 0 ≤ r ≤ m, Reed-Mullerův kód s parametry r a m je označen jako RM (r, m). Když se zobrazí výzva k zakódování zprávy skládající se z k bity, kde drží, RM (r, m) kód vytvoří kódové slovo skládající se z 2m bity.
Kódy Reed – Muller jsou pojmenovány po David E. Muller, který objevil kódy v roce 1954[4], a Irving S. Reed, který navrhl první efektivní dekódovací algoritmus[5].
Popis pomocí polynomů nízkého stupně
Reed – Mullerovy kódy lze popsat několika různými (ale nakonec rovnocennými) způsoby. Popis, který je založen na polynomech nízkého stupně, je docela elegantní a zvláště vhodný pro jejich použití jako místně testovatelné kódy a lokálně dekódovatelné kódy.[6]
Kodér
A blokovat kód může mít jednu nebo více funkcí kódování že mapové zprávy na kódová slova . Reed-Mullerův kód RM (r, m) má délka zprávy a délka bloku . Jeden způsob, jak definovat kódování pro tento kód, je založen na vyhodnocení multilineární polynomy s m proměnné a celkový stupeň r. Každý multilineární polynom nad konečné pole se dvěma prvky lze zapsat takto:
Skutečnost, že kódové slovo stačí k jedinečné rekonstrukci vyplývá z Lagrangeova interpolace, který uvádí, že koeficienty polynomu jsou jednoznačně určeny, když je zadáno dostatečně mnoho hodnotících bodů. Od té doby a platí pro všechny zprávy , funkce je lineární mapa. Reed-Mullerův kód je tedy a lineární kód.
Příklad
Pro kód RM (2, 4), parametry jsou následující:
Nechat být právě definovanou funkcí kódování. Pro kódování řetězce x = 1 1010 010101 o délce 11 kodér nejprve vytvoří polynom ve 4 proměnných:
Dekodér
![]() | Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Srpna 2018) |
Jak již bylo zmíněno, Lagrangeovu interpolaci lze použít k efektivnímu načtení zprávy z kódového slova. Dekodér však musí pracovat, i když bylo kódové slovo poškozeno na několika pozicích, tj. Když se přijaté slovo liší od jakéhokoli kódového slova. V tomto případě může pomoci místní postup dekódování.
Zobecnění na větší abecedy pomocí polynomů nízkého stupně
Použití polynomů nízkého stupně přes konečné pole velikosti , je možné rozšířit definici Reed – Mullerových kódů na abecedy velikosti . Nechat a být kladná celá čísla, kde by měl být považován za větší než . K zakódování zprávy z s , zpráva je znovu interpretována a - variační polynom celkového stupně nanejvýš as koeficientem od . Takový polynom skutečně má koeficienty. Reed-Mullerovo kódování je seznam všech hodnocení nade vše . Délka bloku je tedy .
Popis pomocí matice generátoru
![]() | Tato sekce možná matoucí nebo nejasné čtenářům. Zejména tato část používá hustou notaci, která není pro většinu čtenářů dobře vysvětlena.Březen 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
A matice generátoru pro kód Reed – Muller RM (r, m) délky N = 2m lze zkonstruovat následovně. Napíšeme množinu všech m-dimenzionální binární vektory jako:
Definujeme v N-rozměrný prostor the vektory indikátorů
na podmnožiny podle:
společně s, také v , binární operace
označované jako klínový produkt (nezaměňovat s klínový produkt definované ve vnější algebře). Tady, a jsou body v (N-dimenzionální binární vektory) a operace je obvyklé násobení v terénu .
je m-dimenzionální vektorový prostor nad polem , takže je možné psát
Definujeme v N-rozměrný prostor následující vektory s délkou a
kde 1 ≤ i ≤ m a Hi jsou hyperplanes v (s rozměrem m − 1):
Matice generátoru
Reed-Muller RM (r, m) kód objednávky r a délka N = 2m je kód generovaný proti0 a klínové výrobky až r z protii, 1 ≤ i ≤ m (kde podle konvence je klínový produkt menší než jeden vektor identitou operace). Jinými slovy, můžeme vytvořit matici generátoru pro RM (r, m) kód pomocí vektorů a jejich permutací klínového produktu až do r včas , jako řádky matice generátoru, kde 1 ≤ ik ≤ m.
Příklad 1
Nechat m = 3. Potom N = 8 a
a
Kód RM (1,3) je generován sadou
nebo přesněji podle řádků matice:
Příklad 2
Kód RM (2,3) je generován sadou:
nebo přesněji podle řádků matice:
Vlastnosti
Následující vlastnosti platí:
- Sada všech možných klínových produktů až m z protii tvoří základ pro .
- RM (r, m) kód má hodnost
- RM (r, m) = RM (r, m - 1) | RM (r − 1, m − 1) kde '|' označuje barový produkt dvou kódů.
- RM (r, m) má minimum Hammingova hmotnost 2m − r.
Důkaz
- Existují
takové vektory a mít rozměr N stačí tedy zkontrolovat, zda N rozpětí vektorů; ekvivalentně to stačí zkontrolovat .
Nechat X být binárním vektorem délky m, prvek X. Nechť (X)i označit ith prvek X. Definovat
kde 1 ≤ i ≤m.
Pak
Expanze díky distribuci klínového produktu dává . Pak od vektorů rozpětí my máme . - Podle 1, všechny takové klínové produkty musí být lineárně nezávislé, takže hodnost RM (r, m) musí být jednoduše počet takových vektorů.
- Vynecháno.
- Indukcí.
- The RM (0,m) code je opakovací kód délky N =2m a hmotnost N = 2m−0 = 2m−r. Podle 1 a má váhu 1 = 20 = 2m−r.
- Pokud 0 < r < m a pokud
- RM (r,m − 1) má váhu 2m−1−r
- RM (r − 1,m − 1) má váhu 2m−1−(r−1) = 2m−r
- pak má tyčový výrobek váhu
Dekódování RM kódů
RM (r, m) kódy lze dekódovat pomocí většinové logické dekódování. Základní myšlenkou většinového logického dekódování je vytvořit několik kontrolních součtů pro každý přijatý prvek kódového slova. Jelikož každý z různých kontrolních součtů musí mít stejnou hodnotu (tj. Hodnotu hmotnosti prvku zprávy), můžeme k dešifrování hodnoty prvku zprávy slovo použít většinové logické dekódování. Jakmile je dekódováno každé pořadí polynomu, je přijímané slovo upraveno podle toho odstraněním odpovídajících kódových slov vážených příspěvky dekódovaných zpráv, až do současné fáze. rPři objednávce RM kódu musíme iterativně dekódovat r + 1, než dorazíme ke konečnému přijatému kódovému slovu. Hodnoty bitů zpráv se také počítají prostřednictvím tohoto schématu; Nakonec můžeme vypočítat kódové slovo vynásobením slova zprávy (právě dekódovaného) maticí generátoru.
Jedním vodítkem, pokud dekódování proběhlo úspěšně, je mít na konci (upraveno přijaté slovo s nulovou hodnotou)r + 1) - fázové dekódování prostřednictvím většinového logického dekódování. Tuto techniku navrhl Irving S.Reed a je obecnější, když se použije na jiné kódy konečné geometrie.
Popis pomocí rekurzivní konstrukce
Reed-Mullerův kód RM (r, m) existuje pro všechna celá čísla a . RM (m, m) je definován jako vesmír () kód. RM (−1, m) je definován jako triviální kód (). Zbývající RM kódy mohou být vytvořeny z těchto základních kódů pomocí konstrukce zdvojnásobení délky
Z této konstrukce RM (r, m) je binární lineární blokový kód (n, k, d) s délkou n = 2m, rozměr a minimální vzdálenost pro . The duální kód do RM (r, m) je RM (m-r-1,m). To ukazuje, že opakovací a SPC kódy jsou duální, biortogonální a rozšířené Hammingovy kódy jsou duální a že kódy s k = n/2 jsou sebe-duální.
Zvláštní případy kódů Reed – Muller
Tabulka všech kódů RM (r, m) pro m≤5
Všechno RM (r, m) kódy s a abeceda velikost 2 jsou zde zobrazeny, anotované standardem [n, k, d] notace teorie kódování pro blokové kódy. Kód RM (r, m) je -kód, to znamená, že je lineární kód přes binární abeceda, má délka bloku , délka zprávy (nebo rozměr) k, a minimální vzdálenost .
RM (m, m) (2m, 2m, 1) | kódy vesmíru | ||||||
RM (5,5) (32,32,1) | |||||||
RM (4,4) (16,16,1) | RM (m − 1, m) (2m, 2m−1, 2) | SPC kódy | |||||
RM (3,3) (8,8,1) | RM (4,5) (32,31,2) | ||||||
RM (2,2) (4,4,1) | RM (3,4) (16,15,2) | RM (m − 2, m) (2m, 2m−m−1, 4) | ext. Hammingovy kódy | ||||
RM (1,1) (2,2,1) | RM (2,3) (8,7,2) | RM (3,5) (32,26,4) | |||||
RM (0,0) (1,1,1) | RM (1,2) (4,3,2) | RM (2,4) (16,11,4) | |||||
RM (0,1) (2,1,2) | RM (1,3) (8,4,4) | RM (2,5) (32,16,8) | vlastní duální kódy | ||||
RM (-1,0) (1,0,) | RM (0,2) (4,1,4) | RM (1,4) (16,5,8) | |||||
RM (-1,1) (2,0,) | RM (0,3) (8,1,8) | RM (1,5) (32,6,16) | |||||
RM (-1,2) (4,0,) | RM (0,4) (16,1,16) | RM (1,m) (2m, m+1, 2m−1) | Proražený hadamardské kódy | ||||
RM (-1,3) (8,0,) | RM (0,5) (32,1,32) | ||||||
RM (-1,4) (16,0,) | RM (0,m) (2m, 1, 2m) | opakovací kódy | |||||
RM (-1,5) (32,0,) | |||||||
RM (-1,m) (2m, 0, ∞) | triviální kódy |
Vlastnosti kódů RM (r, m) pro r≤1 nebo r≥m-1
- RM (0,m) kódy jsou opakovací kódy délky N = 2m, hodnotit a minimální vzdálenost .
- RM (1,m) kódy jsou paritní kontrolní kódy délky N = 2m, sazba a minimální vzdálenost .
- RM (m − 1, m) kódy jsou kódy pro kontrolu jedné parity délky N = 2m, sazba a minimální vzdálenost .
- RM (m − 2, m) kódy jsou rodinou rozšířené Hammingovy kódy délky N = 2m s minimální vzdáleností .[7]
Reference
- ^ Massey, James L. (1992), „Komunikace a kódování v hlubokém vesmíru: sňatek uzavřený v nebi“, Pokročilé metody pro satelitní a hlubokou vesmírnou komunikaci, Přednášky z řídících a informačních věd, 182, Springer-Verlag, str. 1–17, CiteSeerX 10.1.1.36.4265, doi:10.1007 / bfb0036046, ISBN 978-3540558514pdf
- ^ „Závěrečná zpráva setkání 3GPP RAN1 # 87“. 3GPP. Citováno 31. srpna 2017.
- ^ Arikan, Erdal (2009). „Channel Polarization: A Method for Construction Capacity-Achieving Codes for Symetric Binary-Input Memoryless Channels - IEEE Journals & Magazine“. Transakce IEEE na teorii informací. 55 (7): 3051–3073. arXiv:0807.3917. doi:10.1109 / TIT.2009.2021379. hdl:11693/11695.
- ^ Muller, David E. (1954). "Aplikace booleovské algebry na návrh spínacího obvodu a na detekci chyb". Transakce I.R.E. Profesionální skupina pro elektronické počítače. EC-3 (3): 6–12. doi:10.1109 / irepgelc.1954,6499441. ISSN 2168-1740.
- ^ Reed, Irving S. (1954). Msgstr "Třída kódů opravujících více chyb a dekódovací schéma". Transakce profesionální skupiny IRE o teorii informací. 4 (4): 38–49. doi:10.1109 / tit.1954.1057465. hdl:10338.dmlcz / 143797. ISSN 2168-2690.
- ^ Prahladh Harsha et al., Limity aproximačních algoritmů: PCP a jedinečné hry (poznámky k přednášce DIMACS), Oddíl 5.2.1.
- ^ Trellis a Turbo Coding, C. Schlegel a L. Perez, Wiley Interscience, 2004, s. 149.
Další čtení
- Shu Lin; Daniel Costello (2005). Kódování kontroly chyb (2. vyd.). Pearson. ISBN 978-0-13-017973-9. Kapitola 4.
- J.H. van Lint (1992). Úvod do teorie kódování. GTM. 86 (2. vyd.). Springer-Verlag. ISBN 978-3-540-54894-2. Kapitola 4.5.
externí odkazy
- MIT OpenCourseWare, 6.451 Principy digitální komunikace II, Poznámky k přednášce část 6.4
- GPL Matlab - implementace RM kódů
- Zdroj GPL Matlab - implementace RM kódů
- Weiss, E. (září 1962). "Zobecněné kódy Reed-Muller". Informace a kontrola. 5 (3): 213–222. doi:10.1016 / s0019-9958 (62) 90555-7. ISSN 0019-9958.