Matice generátoru - Generator matrix - Wikipedia

v teorie kódování, a matice generátoru je matice jehož řádky tvoří a základ pro lineární kód. Kódová slova jsou všechna lineární kombinace řádků této matice, to znamená, že lineární kód je řádkový prostor jeho generátorové matice.

Terminologie

Li G je matice, generuje kódová slova lineárního kódu C podle

{ displaystyle w = sG}

kde w je kódové slovo lineárního kódu C, a s je jakýkoli vstupní vektor. Oba w a s se považují za řádkové vektory.^[1] Matice generátoru pro lineární ${ displaystyle [n, k, d] _ {q}}$ -kód má formát ${ displaystyle k krát n}$ , kde n je délka kódového slova, k je počet informačních bitů (rozměr C jako vektorový podprostor), d je minimální vzdálenost kódu a q je velikost konečné pole, tj. počet symbolů v abecedě (tedy q = 2 označuje a binární kód, atd.). Počet nadbytečné bity je označen ${ displaystyle r = n-k}$ .

The Standard forma pro matici generátoru je,^[2]

{ displaystyle G = { begin {bmatrix} I_ {k} | P end {bmatrix}}}

,

kde ${ displaystyle I_ {k}}$ je ${ displaystyle k krát k}$ matice identity a P je a ${ displaystyle k krát (n-k)}$ matice. Když je matice generátoru ve standardní formě, kód C je systematický ve své první k polohy souřadnic.^[3]

Generátorovou matici lze použít ke konstrukci paritní kontrolní matice pro kód (a naopak). Pokud je matice generátoru G je ve standardní formě, ${ displaystyle G = { begin {bmatrix} I_ {k} | P end {bmatrix}}}$ , pak matice kontroly parity pro C je^[4]

{ displaystyle H = { begin {bmatrix} -P ^ { top} | I_ {n-k} end {bmatrix}}}

,

kde ${ displaystyle P ^ { top}}$ je přemístit matice ${ displaystyle P}$ . To je důsledek skutečnosti, že matice kontroly parity z ${ displaystyle C}$ je generátorová matice duální kód ${ displaystyle C ^ { perp}}$ .

G je a ${ displaystyle k krát n}$ matice, zatímco H je a ${ displaystyle (n-k) krát n}$ matice.

Ekvivalentní kódy

Kódy C₁ a C₂ jsou ekvivalent (označeno C₁ ~ C₂) pokud lze jeden kód získat od druhého pomocí následujících dvou transformací:^[5]

svévolně permutovat komponenty a
nezávisle měřítko nenulovým prvkem libovolné komponenty.

Ekvivalentní kódy mají stejnou minimální vzdálenost.

Matice generátorů ekvivalentních kódů lze navzájem získat pomocí následujícího základní operace:^[6]

permutovat řádky
škálovat řádky nenulovým skalárem
přidat řádky do dalších řádků
permutovat sloupce a
měřítko sloupců nenulovým skalárem.

Můžeme tedy hrát Gaussova eliminace na G. To nám umožňuje předpokládat, že matice generátoru je ve standardní formě. Přesněji řečeno, pro jakoukoli matici G můžeme najít invertibilní matice U takhle ${ displaystyle UG = { begin {bmatrix} I_ {k} | P end {bmatrix}}}$ , kde G a ${ displaystyle { begin {bmatrix} I_ {k} | P end {bmatrix}}}$ generovat ekvivalentní kódy.

Viz také

Hammingův kód (7,4)

Poznámky

^ MacKay, David, J.C. (2003). Informační teorie, odvození a výukové algoritmy (PDF). Cambridge University Press. str. 9. ISBN 9780521642989. Vzhledem k tomu, že Hammingův kód je lineární kód, lze jej napsat kompaktně, pokud jde o matice, následovně. Přenesené kódové slovo ${ displaystyle mathbf {t}}$ se získá ze zdrojové sekvence ${ displaystyle mathbf {s}}$ lineární operací,
${ displaystyle mathbf {t} = mathbf {G} ^ { intercal} mathbf {s}}$
kde ${ displaystyle mathbf {G}}$ je matice generátoru kódu ... předpokládal jsem to ${ displaystyle mathbf {s}}$ a ${ displaystyle mathbf {t}}$ jsou sloupcové vektory. Pokud jsou místo toho řádkovými vektory, je tato rovnice nahrazena
${ displaystyle mathbf {t} = mathbf {sG}}$
... považuji za jednodušší vztahovat se k multiplikaci vpravo (...) než k multiplikaci vlevo (...). Mnoho textů teorie kódování však používá konvence násobení levice (...). ... Řádky matice generátoru lze chápat jako definující základní vektory.
^ Ling & Xing 2004, str. 52
^ Roman 1992, str. 198
^ Roman 1992, str. 200
^ Pless 1998, str. 8
^ Velština 1988, str. 54-55

Reference

Ling, San; Xing, Chaoping (2004), Teorie kódování / První kurz, Cambridge University Press, ISBN 0-521-52923-9
Pless, Vero (1998), Úvod do teorie chybových kódů (3. vyd.), Wiley Interscience, ISBN 0-471-19047-0
Roman, Steven (1992), Kódování a informační teorie, GTM, 134, Springer-Verlag, ISBN 0-387-97812-7
Welsh, Dominic (1988), Kódy a kryptografie, Oxford University Press, ISBN 0-19-853287-3

Další čtení

MacWilliams, F.J.; Sloane, N.J.A. (1977), Teorie kódů pro opravu chyb, Severní Holandsko, ISBN 0-444-85193-3

externí odkazy

Generator Matrix ve společnosti MathWorld

[DrMacKayECC-1] MacKay, David, J.C. (2003). Informační teorie, odvození a výukové algoritmy (PDF). Cambridge University Press. str. 9. ISBN 9780521642989. Vzhledem k tomu, že Hammingův kód je lineární kód, lze jej napsat kompaktně, pokud jde o matice, následovně. Přenesené kódové slovo ${ displaystyle mathbf {t}}$ se získá ze zdrojové sekvence ${ displaystyle mathbf {s}}$ lineární operací,
${ displaystyle mathbf {t} = mathbf {G} ^ { intercal} mathbf {s}}$
kde ${ displaystyle mathbf {G}}$ je matice generátoru kódu ... předpokládal jsem to ${ displaystyle mathbf {s}}$ a ${ displaystyle mathbf {t}}$ jsou sloupcové vektory. Pokud jsou místo toho řádkovými vektory, je tato rovnice nahrazena
${ displaystyle mathbf {t} = mathbf {sG}}$
... považuji za jednodušší vztahovat se k multiplikaci vpravo (...) než k multiplikaci vlevo (...). Mnoho textů teorie kódování však používá konvence násobení levice (...). ... Řádky matice generátoru lze chápat jako definující základní vektory.

[2] Ling & Xing 2004, str. 52

[3] Roman 1992, str. 198

[4] Roman 1992, str. 200

[5] Pless 1998, str. 8

[6] Velština 1988, str. 54-55

[1]

[2]

[3]

[4]

[5]

[6]