Macierz generatora - Generator matrix

W teorii kodowania , A macierz generatora jest macierzą , której rzędy tworzą podstawę dla kodu liniowego . Słowa kodowe to wszystkie liniowe kombinacje wierszy tej macierzy, to znaczy kod liniowy jest przestrzenią wierszy swojej macierzy generatora.

Terminologia

Jeśli G jest macierzą, generuje słowa kodowe kodu liniowego C przez

${\displaystyle w=sG}$

gdzie w jest słowem kodowym kodu liniowego C , a s jest dowolnym wektorem wejściowym. Zakłada się, że zarówno w, jak i s są wektorami wierszowymi. Macierz generatora kodu liniowego ma format , gdzie n to długość słowa kodowego, k to liczba bitów informacyjnych (wymiar C jako podprzestrzeni wektorowej), d to minimalna odległość kodu, a q to wielkość pola skończonego , czyli ilość symboli w alfabecie (zatem q = 2 oznacza kod binarny itd.). Liczba nadmiarowych bitów jest oznaczona przez . ${\displaystyle [n,k,d]_{q}}$${\displaystyle k\razy n}$${\displaystyle r=nk}$

Standardowy formularz matrycy generatora jest

${\ Displaystyle G = {\ zacząć {bmatrix} I_ {k} | P \ koniec {bmatrix}}}$,

gdzie jest macierzą jednostkową, a P jest macierzą. Gdy macierz generatora jest w postaci standardowej, kod C jest systematyczny w swoich pierwszych k współrzędnych pozycji. ${\ Displaystyle I_ {k}}$${\displaystyle k\razy k}$ ${\displaystyle k\times (nk)}$

Macierz generatora może być użyta do skonstruowania macierzy kontroli parzystości dla kodu (i odwrotnie). Jeżeli macierz generatora G jest w postaci standardowej , to macierz kontroli parzystości dla C jest ${\ Displaystyle G = {\ zacząć {bmatrix} I_ {k} | P \ koniec {bmatrix}}}$

${\ Displaystyle H = {\ zacząć {bmatrix}-P ^ {\ top} | I_ {nk} \ koniec {bmatrix}}}$,

gdzie jest transpozycja macierzy . Wynika to z faktu, że macierz kontroli parzystości jest macierzą generatora kodu dualnego . ${\ Displaystyle P ^ {\ top}}$${\displaystyle P}$${\ Displaystyle C}$ ${\ Displaystyle C ^ {\ sprawca}}$

G jest macierzą, a H jest macierzą. ${\displaystyle k\razy n}$${\displaystyle (nk)\razy n}$

Równoważne kody

Kody C ₁ i C ₂ są równoważne (oznaczone jako C ₁ ~ C ₂ ), jeśli jeden kod można uzyskać z drugiego za pomocą następujących dwóch przekształceń:

1. arbitralnie permutuj komponenty i
2. niezależnie skalować o niezerowy element dowolne komponenty.

Równoważne kody mają taką samą minimalną odległość.

Macierze generatorów kodów równoważnych można uzyskać od siebie za pomocą następujących podstawowych operacji :

1. permutuj wiersze
2. skaluj wiersze niezerowym skalarem
3. dodaj wiersze do innych wierszy
4. kolumny permutacyjne i
5. skalować kolumny przez niezerową wartość skalarną.

W ten sposób możemy wykonać eliminację Gaussa na G . W rzeczywistości pozwala nam to założyć, że macierz generatora ma postać standardową. Dokładniej, dla dowolnej macierzy G możemy znaleźć macierz odwracalną U taką, że , gdzie G i generować równoważne kody. ${\ Displaystyle UG = {\ zacząć {bmatrix} I_ {k} | P \ koniec {bmatrix}}}$${\ Displaystyle {\ zacząć {bmatrix} I_ {k} | P \ koniec {bmatrix}}}$

Zobacz też

• Kod Hamminga (7,4)

Uwagi

Bibliografia

• Ling, San; Xing, Chaoping (2004), Teoria kodowania / pierwszy kurs , Cambridge University Press, ISBN 0-521-52923-9
• Pless, Vera (1998), Wprowadzenie do teorii kodów korekcji błędów (3rd ed.), Wiley Interscience, ISBN 0-471-19047-0
• Roman Steven (1992), Teoria kodowania i informacji , GTM , 134 , Springer-Verlag, ISBN 0-387-97812-7
• Walijski, Dominic (1988), Kody i kryptografia , Oxford University Press, ISBN 0-19-853287-3

Dalsza lektura

• MacWilliams, FJ ; Sloane, NJA (1977), Teoria kodów korekcji błędów , North-Holland, ISBN 0-444-85193-3

Linki zewnętrzne

• Macierz generatorów w MathWorld