Matrice del generatore - Generator matrix

Nella teoria dei codici , una matrice generatrice è una matrice le cui righe costituiscono una base per un codice lineare . Le parole di codice sono tutte le combinazioni lineari delle righe di questa matrice, ovvero il codice lineare è lo spazio righe della sua matrice generatrice.

Terminologia

Se G è una matrice, genera le parole di codice di un codice lineare C di

${\displaystyle w=sG}$

dove w è una parola in codice del codice lineare C e s è un qualsiasi vettore di input. Si presume che sia w che s siano vettori riga. Una matrice generatore per un codice lineare ha formato , dove n è la lunghezza di una parola di codice, k è il numero di bit di informazione (la dimensione di C come sottospazio vettoriale), d è la distanza minima del codice e q è dimensione del campo finito , cioè il numero di simboli dell'alfabeto (quindi q = 2 indica un codice binario , ecc.). Il numero di bit ridondanti è indicato con . ${\displaystyle [n,k,d]_{q}}$${\displaystyle k\times n}$${\displaystyle r=nk}$

La forma standard per una matrice generatore è,

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

dove è la matrice identità e P è una matrice. Quando la matrice generatrice è in forma standard, il codice C è sistematico nelle sue prime k coordinate. ${\displaystyle I_{k}}$${\displaystyle k\times k}$ ${\displaystyle k\times (nk)}$

Una matrice generatore può essere utilizzata per costruire la matrice di controllo di parità per un codice (e viceversa). Se la matrice del generatore G è in forma standard, , allora la matrice del controllo di parità per C è ${\displaystyle G={\begin{bmatrix}I_{k}|P\end{bmatrix}}}$

${\displaystyle H={\begin{bmatrix}-P^{\top }|I_{nk}\end{bmatrix}}}$,

dove è la trasposta della matrice . Questa è una conseguenza del fatto che una matrice di controllo di parità di è una matrice generatrice del codice duale . ${\displaystyle P^{\top }}$${\displaystyle P}$${\displaystyle C}$ ${\displaystyle C^{\perp }}$

G è una matrice, mentre H è una matrice. ${\displaystyle k\times n}$${\displaystyle (nk)\times n}$

Codici equivalenti

I codici C ₁ e C ₂ sono equivalenti (indicati con C ₁ ~ C ₂ ) se un codice può essere ottenuto dall'altro tramite le due seguenti trasformazioni:

1. permutare arbitrariamente i componenti, e
2. ridimensiona indipendentemente da un elemento diverso da zero qualsiasi componente.

I codici equivalenti hanno la stessa distanza minima.

Le matrici generatrici di codici equivalenti possono essere ricavate l'una dall'altra mediante le seguenti operazioni elementari :

1. permutare le righe
2. scala le righe di uno scalare diverso da zero
3. aggiungi righe ad altre righe
4. permuta colonne, e
5. scala le colonne di uno scalare diverso da zero.

Quindi, possiamo eseguire l' eliminazione gaussiana su G . In effetti, questo ci permette di assumere che la matrice del generatore sia nella forma standard. Più precisamente, per ogni matrice G possiamo trovare una matrice U invertibile tale che , dove G e genera codici equivalenti. ${\displaystyle UG={\begin{bmatrix}I_{k}|P\end{bmatrix}}}$${\displaystyle {\begin{bmatrix}I_{k}|P\end{bmatrix}}}$

Guarda anche

• Codice Hamming (7,4)

Appunti

Riferimenti

• Ling, San; Xing, Chaoping (2004), Teoria dei codici / A First Course , Cambridge University Press, ISBN 0-521-52923-9
• Pless, Vera (1998), Introduzione alla teoria dei codici di correzione degli errori (3a ed.), Wiley Interscience, ISBN 0-471-19047-0
• Roman, Steven (1992), Teoria della codifica e dell'informazione , GTM , 134 , Springer-Verlag, ISBN 0-387-97812-7
• Welsh, Dominic (1988), Codici e crittografia , Oxford University Press, ISBN 0-19-853287-3

Ulteriori letture

• MacWilliams, FJ ; Sloane, NJA (1977), La teoria dei codici di correzione degli errori , North-Holland, ISBN 0-444-85193-3

link esterno

• Matrice del generatore a MathWorld