Lineární kód - Linear code

v teorie kódování, a lineární kód je kód pro opravu chyb pro které vůbec lineární kombinace z kódová slova je také kódové slovo. Lineární kódy jsou tradičně rozděleny do blokové kódy a konvoluční kódy, Ačkoli turbo kódy lze považovat za hybrid těchto dvou typů.^[1] Lineární kódy umožňují efektivnější algoritmy kódování a dekódování než jiné kódy (srov. dekódování syndromu ).^{[Citace je zapotřebí ]}

Lineární kódy se používají v dopředná oprava chyb a jsou používány v metodách přenosu symbolů (např. bity ) na komunikační kanál takže pokud dojde k chybám v komunikaci, některé chyby mohou být opraveny nebo detekovány příjemcem bloku zprávy. Kódová slova v kódu lineárního bloku jsou bloky symbolů, které jsou kódovány pomocí více symbolů, než je původní hodnota, která má být odeslána.^[2] Lineární kód délky n vysílá bloky obsahující n symboly. Například [7,4,3] Hammingův kód je lineární binární kód což představuje 4bitové zprávy používající 7bitová kódová slova. Dvě odlišná kódová slova se liší nejméně třemi bity. V důsledku toho lze detekovat až dvě chyby na každé kódové slovo, zatímco lze opravit jednu chybu.^[3] Tento kód obsahuje 2⁴= 16 kódových slov.

Definice a parametry

A lineární kód délky n a pořadí k je lineární podprostor C s dimenze k z vektorový prostor ${ displaystyle mathbb {F} _ {q} ^ {n}}$ kde ${ displaystyle mathbb {F} _ {q}}$ je konečné pole s q elementy. Takový kód se nazývá a q-ary kód. Li q = 2 nebo q = 3, kód je popsán jako a binární kódnebo ternární kód resp. Vektory v C se nazývají kódová slova. The velikost kódu je počet kódových slov a rovná se q^k.

The hmotnost kódového slova je počet jeho prvků, které jsou nenulové a vzdálenost mezi dvěma kódovými slovy je Hammingova vzdálenost mezi nimi, tedy počet prvků, v nichž se liší. Vzdálenost d lineárního kódu je minimální hmotnost jeho nenulových kódových slov nebo ekvivalentně minimální vzdálenost mezi odlišnými kódovými slovy. Lineární kód délky n, rozměr ka vzdálenost d se nazývá [n,k,d] kód.

Chceme dát ${ displaystyle mathbb {F} _ {q} ^ {n}}$ standardní základ, protože každá souřadnice představuje „bit“, který se přenáší přes „hlučný kanál“ s malou pravděpodobností chyby přenosu ( binární symetrický kanál ). Pokud se použije nějaký jiný základ, pak tento model nelze použít a Hammingova metrika neměří počet chyb v přenosu, jak chceme.

Generátor a zkontrolujte matice

Jako lineární podprostor z ${ displaystyle mathbb {F} _ {q} ^ {n}}$ , celý kód C (který může být velmi velký) může být reprezentován jako rozpětí sady ${ displaystyle k}$ kódová slova (známá jako základ v lineární algebra ). Tato základní kódová slova se často shromažďují v řádcích matice G známé jako a generující matice pro kód C. Když G má formu blokové matice ${ displaystyle { boldsymbol {G}} = [I_ {k} | P]}$ , kde ${ displaystyle I_ {k}}$ označuje ${ displaystyle k krát k}$ matice identity a P je nějaká ${ displaystyle k krát (n-k)}$ matice, pak říkáme, že G je v standardní forma.

Matice H představující lineární funkci ${ displaystyle phi: mathbb {F} _ {q} ^ {n} do mathbb {F} _ {q} ^ {n-k}}$ jehož jádro je C se nazývá a zkontrolovat matici z C (nebo někdy matice kontroly parity). Ekvivalentně H je matice, jejíž prázdný prostor je C. Li C je kód s generující maticí G ve standardní formě, ${ displaystyle { boldsymbol {G}} = [I_ {k} | P]}$ , pak ${ displaystyle { boldsymbol {H}} = [- P ^ {T} | I_ {n-k}]}$ je kontrolní matice pro C. Kód generovaný H se nazývá duální kód C. Lze ověřit, že G je a ${ displaystyle k krát n}$ matice, zatímco H je a ${ displaystyle (n-k) krát n}$ matice.

Linearita zaručuje, že minimum Hammingova vzdálenost d mezi kódovým slovem C₀ a jakékoli další kódové slovo C ≠ C₀ je nezávislý na C₀. To vyplývá z vlastnosti, že rozdíl C − C₀ dvou kódových slov v C je také kódové slovo (tj živel podprostoru C) a vlastnost, která d(C, c₀) = d(C − C₀, 0). Tyto vlastnosti to naznačují

{ displaystyle min _ {c v C, c neq c_ {0}} d (c, c_ {0}) = min _ {c v C, c neq c_ {0}} d ( c-c_ {0}, 0) = min _ {c v C, c neq 0} d (c, 0) = d.}

Jinými slovy, aby bylo možné zjistit minimální vzdálenost mezi kódovými slovy lineárního kódu, stačí se podívat na nenulová kódová slova. Nenulové kódové slovo s nejmenší váhou má pak minimální vzdálenost od nulového kódového slova, a proto určuje minimální vzdálenost kódu.

Vzdálenost d lineárního kódu C Rovná se také minimální počet lineárně závislých sloupců kontrolní matice H.

Důkaz: Protože ${ displaystyle { boldsymbol {H}} cdot { boldsymbol {c}} ^ {T} = { boldsymbol {0}}}$ , což odpovídá ${ displaystyle sum _ {i = 1} ^ {n} (c_ {i} cdot { boldsymbol {H_ {i}}}) = { boldsymbol {0}}}$ , kde ${ displaystyle { boldsymbol {H_ {i}}}}$ je ${ displaystyle i ^ {th}}$ sloupec ${ displaystyle { boldsymbol {H}}}$ . Odeberte tyto položky pomocí ${ displaystyle c_ {i} = 0}$ , ty ${ displaystyle { boldsymbol {H_ {i}}}}$ s ${ displaystyle c_ {i} neq 0}$ jsou lineárně závislé. Proto, ${ displaystyle d}$ je alespoň minimální počet lineárně závislých sloupců. Na druhou stranu zvažte minimální sadu lineárně závislých sloupců ${ displaystyle {{ boldsymbol {H_ {j}}} | j v S }}$ kde ${ displaystyle S}$ je sada indexů sloupců. ${ displaystyle sum _ {i = 1} ^ {n} (c_ {i} cdot { boldsymbol {H_ {i}}}) = sum _ {j v S} (c_ {j} cdot { boldsymbol {H_ {j}}}) + sum _ {j notin S} (c_ {j} cdot { boldsymbol {H_ {j}}}) = { boldsymbol {0}}}$ . Nyní zvažte vektor ${ displaystyle { boldsymbol {c '}}}$ takhle ${ displaystyle c_ {j} ^ {'} = 0}$ -li ${ displaystyle j notin S}$ . Poznámka ${ displaystyle { boldsymbol {c '}} v C}$ protože ${ displaystyle { boldsymbol {H}} cdot { boldsymbol {c '}} ^ {T} = { boldsymbol {0}}}$ . Proto máme ${ displaystyle d leq wt ({ boldsymbol {c '}})}$ , což je minimální počet lineárně závislých sloupců v ${ displaystyle { boldsymbol {H}}}$ . Reklamovaný majetek je tedy prokázán.

Příklad: Hammingovy kódy

Jako první třída lineárních kódů vyvinutých pro účely opravy chyb Hammingovy kódy byly široce používány v systémech digitální komunikace. Pro jakékoli kladné celé číslo ${ displaystyle r geq 2}$ , existuje a ${ displaystyle [2 ^ {r} -1,2 ^ {r} -r-1,3] _ {2}}$ Hammingův kód. Od té doby ${ displaystyle d = 3}$ , tento Hammingův kód může opravit 1-bitovou chybu.

Příklad: Lineární blokový kód s následující maticí generátoru a maticí kontroly parity je a ${ displaystyle [7,4,3] _ {2}}$ Hammingův kód.

{ displaystyle { boldsymbol {G}} = { začátek {pmatrix} 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 end {pmatrix}},}

{ displaystyle { boldsymbol {H}} = { začátek {pmatrix} 1 0 1 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 end {pmatrix}}}

Příklad: Hadamardovy kódy

Hadamardův kód je ${ displaystyle [2 ^ {r}, r, 2 ^ {r-1}] _ {2}}$ lineární kód a je schopen opravit mnoho chyb. Hadamardův kód lze sestavit sloupec po sloupci: ${ displaystyle i ^ {th}}$ sloupec jsou bity binární reprezentace celého čísla ${ displaystyle i}$ , jak ukazuje následující příklad. Hadamardův kód má minimální vzdálenost ${ displaystyle 2 ^ {r-1}}$ a proto může opravit ${ displaystyle 2 ^ {r-2} -1}$ chyby.

Příklad: Lineární blokový kód s následující maticí generátoru je a ${ displaystyle [8,3,4] _ {2}}$ Hadamardův kód: ${ displaystyle { boldsymbol {G}} _ {Had} = { začít {pmatrix} 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 konec {pmatrix}}}$ .

Hadamardův kód je zvláštní případ Reed-Mullerův kód. Pokud vezmeme první sloupec (sloupec s nulovou hodnotou) z ${ displaystyle { boldsymbol {G}} _ {Had}}$ , dostaneme ${ displaystyle [7,3,4] _ {2}}$ simplexní kód, který je duální kód Hammingova kódu.

Algoritmus nejbližšího souseda

Parametr d úzce souvisí se schopností kódu opravovat chyby. Ilustruje to následující konstrukce / algoritmus (tzv. Dekódovací algoritmus nejbližšího souseda):

Vstup: A přijatý vektor v ${ displaystyle mathbb {F} _ {q} ^ {n}}$ .

Výstup: kódové slovo ${ displaystyle w}$ v ${ displaystyle C}$ nejblíže k ${ displaystyle v}$ , jestli nějaký.

Začínání s ${ displaystyle t = 0}$ , opakujte následující dva kroky.
Vyjmenujte prvky koule o (Hammingově) poloměru ${ displaystyle t}$ $t$ kolem přijatého slova ${ displaystyle v}$ $proti$ , označeno ${ displaystyle B_ {t} (v)}$ ${ displaystyle B_ {t} (v)}$ .
- Pro každého ${ displaystyle w}$ v ${ displaystyle B_ {t} (v)}$ , zkontrolujte, zda ${ displaystyle w}$ v ${ displaystyle C}$ . Pokud ano, vraťte se ${ displaystyle w}$ jako řešení.
Přírůstek ${ displaystyle t}$ . Selhat, pouze když ${ displaystyle t> (d-1) / 2}$ výčet je tedy kompletní a nebylo nalezeno žádné řešení.

Říkáme, že lineární ${ displaystyle C}$ je ${ displaystyle t}$ - oprava chyby, pokud je v něm maximálně jedno kódové slovo ${ displaystyle B_ {t} (v)}$ , pro každého ${ displaystyle v}$ v ${ displaystyle mathbb {F} _ {q} ^ {n}}$ .

Populární notace

Kódy obecně jsou často označovány písmenem Ca kód délky n a ze dne hodnost k (tj. mít k kódová slova na jejím základě a k řádky v jeho generující matice) se obecně označuje jako (n, k) kód. Lineární blokové kódy jsou často označovány jako [n, k, d] kódy, kde d označuje minimální Hammingovu vzdálenost kódu mezi jakýmikoli dvěma kódovými slovy.

([n, k, d] notace by neměla být zaměňována s (n, M, d) zápis používaný k označení a nelineární kód délky n, velikost M (tj. mít M kódová slova) a minimální Hammingova vzdálenost d.)

Singleton vázán

Lemma (Singleton vázán ): Každý lineární [n, k, d] kód C vyhovuje ${ displaystyle k + d leq n + 1}$ .

Volá se kód C, jehož parametry splňují k + d = n + 1 maximální vzdálenost oddělitelná nebo MDS. Takové kódy, pokud existují, jsou v jistém smyslu nejlepší možné.

Pokud C₁ a C.₂ jsou dva kódy délky n a pokud existuje permutace p v symetrická skupina S_n pro které (c₁,...,C_n) v C.₁ jen tehdy, když (c_{p (1)},...,C_{p (n)}) v C.₂, pak řekneme C.₁ a C.₂ jsou ekvivalent permutace. Obecněji, pokud existuje ${ displaystyle n krát n}$ monomiální matice ${ displaystyle M colon mathbb {F} _ {q} ^ {n} to mathbb {F} _ {q} ^ {n}}$ který pošle C.₁ izomorfně k C₂ pak řekneme C.₁ a C.₂ jsou ekvivalent.

Lemma: Libovolný lineární kód je permutace ekvivalentní kódu, který je ve standardní formě.

Bonisoliho věta

Kód je definován jako stejně vzdálený právě když existuje nějaká konstanta d taková, že vzdálenost mezi libovolnými dvěma odlišnými kódovými slovy kódu je rovna d.^[4] V roce 1984 Arrigo Bonisoli určil strukturu lineárních jednodílných kódů nad konečnými poli a dokázal, že každý lineární kód ve stejné vzdálenosti je posloupností dvojí Hammingovy kódy.^[5]

Příklady

Mezi příklady lineárních kódů patří:

Opakovací kódy
Paritní kódy
Cyklické kódy
Hammingovy kódy
Golay kód, oba binární a trojice verze
Polynomiální kódy, z toho BCH kódy jsou příkladem
Reed-Solomon kódy
Reed-Mullerovy kódy
Kódy Goppa
Kódy kontroly parity s nízkou hustotou
Expander kódy
Vícerozměrné kódy kontroly parity
Torické kódy
Turbo kódy

Zobecnění

Hammingovy prostory byly také zvažovány nadpolní abecedy, zvláště nad konečné kroužky (především Z₄ ) vznikající moduly místo vektorových prostorů a kruhové lineární kódy (identifikováno s podmoduly ) místo lineárních kódů. Typická metrika použitá v tomto případě je Lee vzdálenost. Existují a Šedá izometrie mezi ${ displaystyle mathbb {Z} _ {2} ^ {2m}}$ (tj. GF (2^{2 m})) s Hammingovou vzdáleností a ${ displaystyle mathbb {Z} _ {4} ^ {m}}$ (označovaný také jako GR (4, m)) s Leeho vzdáleností; jeho hlavním lákadlem je, že navazuje korespondenci mezi některými „dobrými“ kódy, které nejsou lineární ${ displaystyle mathbb {Z} _ {2} ^ {2m}}$ jako obrázky kruhových lineárních kódů z ${ displaystyle mathbb {Z} _ {4} ^ {m}}$ .^[6]^[7]^[8]

Poslední dobou,^{[když? ]} někteří autoři také tyto kódy označili jednoduše jako lineární kódy.^[9]

Viz také

Dekódovací metody

Reference

^ William E. Ryan a Shu Lin (2009). Kódy kanálu: Klasické a moderní. Cambridge University Press. p.4. ISBN 978-0-521-84868-8.
^ MacKay, David, J.C. (2003). Informační teorie, odvození a výukové algoritmy (PDF). Cambridge University Press. p. 9. Bibcode:2003itil.book ..... M. ISBN 9780521642989. V lineární blokový kód, navíc ${ displaystyle N-K}$ bity jsou lineární funkce originálu ${ displaystyle K}$ bity; tyto další bity se nazývají bity pro kontrolu parity
^ Thomas M. Cover a Joy A. Thomas (1991). Základy teorie informace. John Wiley & Sons, Inc. str.210–211. ISBN 978-0-471-06259-2.
^ Etzion, Tuvi; Raviv, Netanel (2013). "Equidistant kódy v Grassmannian". arXiv:1308.6231 [math.CO ].
^ Bonisoli, A. (1984). "Každý ekvidistantní lineární kód je posloupností duálních Hammingových kódů". Ars Combinatoria. 18: 181–186.
^ Marcus Greferath (2009). „Úvod do teorie prstencového lineárního kódování“. V Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso (eds.). Gröbnerovy báze, kódování a kryptografie. Springer Science & Business Media. ISBN 978-3-540-93806-4.
^ „Encyklopedie matematiky“. www.encyclopediaofmath.org.
^ J.H. van Lint (1999). Úvod do teorie kódování (3. vyd.). Springer. Kapitola 8: Kódy přes ℤ₄. ISBN 978-3-540-64133-9.
^ SVATÝ. Dougherty; J.-L. Kim; P. Sole (2015). „Otevřené problémy v teorii kódování“. V Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (eds.). Nekomutativní prsteny a jejich aplikace. American Mathematical Soc. p. 80. ISBN 978-1-4704-1032-2.

Bibliografie

J. F. Humphreys; M. Y. Perst (2004). Čísla, skupiny a kódy (2. vyd.). Cambridge University Press. ISBN 978-0-511-19420-7. Kapitola 5 obsahuje jemnější úvod (než tento článek) k předmětu lineárních kódů.

externí odkazy

q- program generátoru kódů
Tabulky kódů: Vazby na parametry různých typů kódů, IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)]. Online, aktuální tabulka optimálních binárních kódů, obsahuje nebinární kódy.
Databáze kódů Z4 Online, aktuální databáze optimálních kódů Z4.

[1] William E. Ryan a Shu Lin (2009). Kódy kanálu: Klasické a moderní. Cambridge University Press. p.4. ISBN 978-0-521-84868-8.

[DrMacKayECC-2] MacKay, David, J.C. (2003). Informační teorie, odvození a výukové algoritmy (PDF). Cambridge University Press. p. 9. Bibcode:2003itil.book ..... M. ISBN 9780521642989. V lineární blokový kód, navíc ${ displaystyle N-K}$ bity jsou lineární funkce originálu ${ displaystyle K}$ bity; tyto další bity se nazývají bity pro kontrolu parity

[Cover_and_Thomas-3] Thomas M. Cover a Joy A. Thomas (1991). Základy teorie informace. John Wiley & Sons, Inc. str.210–211. ISBN 978-0-471-06259-2.

[4] Etzion, Tuvi; Raviv, Netanel (2013). "Equidistant kódy v Grassmannian". arXiv:1308.6231 [math.CO ].

[5] Bonisoli, A. (1984). "Každý ekvidistantní lineární kód je posloupností duálních Hammingových kódů". Ars Combinatoria. 18: 181–186.

[Greferath2009-6] Marcus Greferath (2009). „Úvod do teorie prstencového lineárního kódování“. V Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso (eds.). Gröbnerovy báze, kódování a kryptografie. Springer Science & Business Media. ISBN 978-3-540-93806-4.

[7] „Encyklopedie matematiky“. www.encyclopediaofmath.org.

[Lint1999-8] J.H. van Lint (1999). Úvod do teorie kódování (3. vyd.). Springer. Kapitola 8: Kódy přes ℤ₄. ISBN 978-3-540-64133-9.

[DoughertyFacchini2015-9] SVATÝ. Dougherty; J.-L. Kim; P. Sole (2015). „Otevřené problémy v teorii kódování“. V Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (eds.). Nekomutativní prsteny a jejich aplikace. American Mathematical Soc. p. 80. ISBN 978-1-4704-1032-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]