Codice lineare

Nella teoria dei codici, un codice lineare è un codice a blocchi speciale in cui le parole del codice sono elementi di uno spazio vettoriale a dimensione finita su un corpo finito . Un codice è lineare se e solo se è un sottospazio di . ${\ displaystyle \ mathbb {F} _ {q} ^ {n}}$ ${\ displaystyle \ mathbb {F} _ {q}}$${\ displaystyle \ mathbb {F} _ {q} ^ {n}}$

I codici lineari hanno il vantaggio di poter utilizzare metodi di algebra lineare . Sono quindi facili da codificare e decodificare. La maggior parte dei codici importanti sono lineari: codice di Hamming , codice di controllo di parità a bassa densità , codice Reed-Muller , codice Hadamard , tutti i codici ciclici (inclusi BCH , codici Reed-Solomon , codici Golay e Goppa Codici ).

È la dimensione spazio vettoriale del codice lineare è uguale , viene chiamato un codice o una distanza di Hamming di anche codice . ${\ displaystyle C}$${\ displaystyle k}$${\ displaystyle C}$${\ displaystyle [n, k]}$${\ displaystyle d}$${\ displaystyle [n, k, d]}$

caratteristiche

Poiché è un sottospazio di , esiste una base di . Se riassumi questa base in una matrice${\ displaystyle C}$${\ displaystyle V}$${\ displaystyle g_ {1}, \ dots, g_ {k}}$${\ displaystyle C}$

${\ displaystyle G = {\ begin {pmatrix} g_ {1} \\\ vdots \\ g_ {k} \ end {pmatrix}}}$

insieme, si ottiene una matrice del produttore . Il codice ha anche una matrice di controllo . Si applica a loro se e solo se è una parola in codice. Il grado di è , che è di . La distanza di Hamming è il numero minimo di colonne dipendenti linearmente nella matrice di controllo. ${\ displaystyle H}$${\ displaystyle Hc ^ {T} = 0}$${\ displaystyle c}$${\ displaystyle G}$${\ displaystyle k}$${\ displaystyle H}$${\ displaystyle nk}$${\ displaystyle C}$

Il peso di Hamming di una parola in codice è uguale al numero di quelli che sono diversi da zero. Ad esempio, la parola in codice ha un peso di Hamming di 4. La distanza di Hamming del codice è uguale al peso di Hamming più piccolo di tutte le parole in codice ad eccezione della parola zero. ${\ displaystyle c = (c_ {1}, \ dots, c_ {n})}$${\ displaystyle c_ {i}}$${\ displaystyle (430540)}$${\ displaystyle \ mathbb {F} _ {7} ^ {6}}$

Se le singole coordinate delle parole del codice sono permutate, si ottiene un cosiddetto codice equivalente . Con questo e per mezzo dell'algebra lineare si può trovare un equivalente per ogni codice lineare, che ha una matrice generatrice della forma . Dov'è la matrice - identità , ed è una matrice. Quindi si chiama matrice del produttore in una forma ridotta. Le prime coordinate possono essere interpretate come simboli di informazione e le ultime come simboli di controllo. È una matrice del generatore in forma ridotta, una matrice di controllo può essere trovata immediatamente . Un codice lineare è già determinato dalla sua matrice generatore o dalla sua matrice di controllo. ${\ displaystyle G = (\ mathbb {E} _ {k} | P)}$${\ displaystyle \ mathbb {E} _ {k}}$${\ displaystyle (k \ times k)}$${\ displaystyle P}$${\ displaystyle (k \ times (nk))}$${\ displaystyle G}$${\ displaystyle k}$${\ displaystyle nk}$${\ displaystyle G}$${\ displaystyle H}$${\ displaystyle H = (- P ^ {T} | \ mathbb {E} _ {nk})}$

esempio

Il codice binario - Hamming ha la seguente matrice generatore in forma ridotta e la matrice di controllo associata: ${\ displaystyle [7,4,3]}$

${\ displaystyle G = (\ mathbb {E} _ {k} | P)}$		${\ displaystyle H = (- P ^ {T} | \ mathbb {E} _ {nk})}$
${\ displaystyle G = {\ begin {pmatrix} {\ color {Brown} 1} & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & {\ color {Brown} 1} & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & \ color {Brown} {1} & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & {\ color {Brown} 1} & 0 & 1 & 1 \\\ end {pmatrix}} \ qquad}$		${\ displaystyle H = {\ begin {pmatrix} 1 & 1 & 1 & 0 & {\ color {Brown} 1} & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & {\ color {Brown} 1} & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & {\ color {Brown} 1} \\\ end {pmatrix }}}$

Codifica

Una parola dallo spazio viene codificata formando il prodotto . La codifica della parola con il codice - Hamming ha illustrato un esempio, la seguente dichiarazione. ${\ displaystyle x = (x_ {1}, \ dots, x_ {k})}$${\ displaystyle \ mathbb {F} _ {q} ^ {k}}$${\ displaystyle xG}$${\ displaystyle (0,0,1,1)}$${\ displaystyle [7,4,3]}$

${\ displaystyle {\ begin {align} x \ cdot G & = c \\ {\ begin {pmatrix} 0,0,1,1 \ end {pmatrix}} \ cdot {\ begin {pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\\ end {pmatrix}} & = {\ begin {pmatrix} 0,0,1,1,1,0,0 \ end {pmatrix}} \ end {align}}}$

Poiché l'aggiunta avviene qui, si applica quanto segue${\ displaystyle \ mathbb {F} _ {2}}$${\ displaystyle 1 + 1 = 0}$

Decodifica

Con la decodifica l' associazione viene chiamata vettore di ingresso ricevuto, possibilmente difettoso,  a un vettore di codice  . La decodifica non è la funzione inversa della codifica, che assegna un vettore a un vettore di codice . ${\ displaystyle x}$${\ displaystyle c '}$${\ displaystyle \ mathbb {F} _ {q} ^ {k}}$

Nella teoria dei codici, il metodo di massima verosimiglianza (inglese: decodifica della massima verosimiglianza ) viene solitamente utilizzato come metodo di decodifica . Un vettore ricevuto viene decodificato nel vettore codice che è molto probabilmente identico al vettore  codice  effettivamente inviato  . Il vettore per il quale è necessario correggere il minor numero di posizioni (errori) è spesso considerato il più probabile. In termini matematici, ciò significa cercare il vettore del codice  con la più piccola distanza di Hamming dal vettore ricevuto  . Questo caso è anche un metodo dei vicini più vicini (inglese: decodifica del vicino più vicino ), rispettivamente. Conoscendo il tipo di dati inviati o il canale utilizzato, è possibile utilizzare altre informazioni per determinare la probabilità di determinati vettori di codice. ${\ displaystyle x}$${\ displaystyle c '}$${\ displaystyle c}$${\ displaystyle c '}$${\ displaystyle x}$

Lascia che sia il vettore (codice) effettivamente inviato e il vettore ricevuto. La decodifica cerca il vettore oi vettori del codice che molto probabilmente sono stati inviati da tutti i vettori del codice . ${\ displaystyle c}$${\ displaystyle x}$${\ displaystyle q ^ {n}}$${\ displaystyle c '}$

${\ Displaystyle c '= \ operatorname {argmax} _ {y \ in C} \ left \ {\ operatorname {P} \ left [y = c \ right] \ right \}}$

Con la decodifica del vicino più vicino :

${\ Displaystyle c '= \ operatorname {argmin} _ {y \ in C} \ left \ {wt (xy) \ right \}}$

Va notato che questa assegnazione non è univoca per la maggior parte dei codici per tutti i vettori di errore. Ci sono poi alcuni vettori di errore che non possono essere assegnati perché hanno più di un vicino più prossimo. Se è possibile una decodifica univoca per ogni vettore di errore, il codice viene definito perfetto .

Decodifica della sindrome

Un metodo più efficiente per la decodifica è la cosiddetta decodifica della sindrome, la sindrome di un vettore si ottiene moltiplicando la matrice di controllo  con . ${\ displaystyle s_ {x}}$${\ displaystyle x}$${\ displaystyle H}$${\ displaystyle x ^ {T}}$

${\ displaystyle s_ {x} ^ {T} = Hx ^ {T}}$

Lascia che sia il vettore di errore di . In sono precisamente quelle coordinate non uguali a zero, per le quali si sono verificati errori durante il trasferimento. ${\ displaystyle e = xc}$${\ displaystyle x}$${\ displaystyle e}$

A causa della linearità del codice, quanto segue si applica alla sindrome di : ${\ displaystyle x}$

${\ displaystyle s_ {x} ^ {T} = Hx ^ {T} = Hc ^ {T} + He ^ {T}}$

Poiché la sindrome dei vettori di codice senza errori è sempre zero, segue:

${\ displaystyle s_ {x} ^ {T} = Lui ^ {T} = s_ {e} ^ {T}}$

Tutte le parole (errate) con lo stesso vettore di errore si trovano nello stesso sottospazio affine , ovvero la sindrome è costante per tali parole . ${\ displaystyle s_ {e} ^ {T} = Lui ^ {T}}$

Tutti i vettori che sono emerse da qualsiasi vettore fisso sottraendo qualsiasi vettore di codice formano una classe controllata della il sottogruppo di . Il vettore con il peso minimo in questa classe è chiamato leader della classe secondaria (inglese: coset leader ). Questo è il motivo per cui il termine "decodifica coset leader" è ampiamente utilizzato. ${\ displaystyle C}$${\ displaystyle \ mathbb {F} _ {q} ^ {n}}$

Al fine di decodifica, si cerca il vettore errore di  cui sindrome è identica alla sindrome di e il cui peso Hamming è minimo. Questo vettore di errore viene utilizzato per calcolare il vettore di codice più vicino  . Quindi puoi impostare una tabella con un massimo di righe che contiene il vettore di errore corrispondente con un peso di Hamming minimo per ciascuna sindrome di un vettore ricevuto. Se la sindrome è 0, non è necessario correggere nulla, altrimenti la decodifica è limitata alla ricerca del vettore di errore in questa tabella e alla correzione degli errori rilevati in questo modo. ${\ displaystyle x}$${\ displaystyle c '}$${\ displaystyle e '}$${\ displaystyle x}$${\ displaystyle c '= x-e'}$${\ displaystyle c '}$${\ displaystyle q ^ {nk}}$

Interpretata diversamente, le classi secondari sono appunto le classi di equivalenza della relazione di equivalenza. I capi sono rappresentanti delle classi di equivalenza, uno sceglie uno con un peso di Hamming minima. I codici perfetti sono caratterizzati dal fatto che i leader sono chiaramente stabiliti. ${\ Displaystyle x \ equiv y \ Leftrightarrow s_ {x} ^ {T} = s_ {y} ^ {T}}$

La decodifica dei codici lineari è generalmente NP-completa , cioè non sono noti algoritmi con un tempo di esecuzione polinomiale. I codici lineari noti, ad esempio i codici di Hamming, si distinguono per il fatto che sono noti algoritmi di decodifica efficienti. La complessità della decodifica lineare è alla base del sistema crittografico McEliece , che è considerato sicuro, ma finora è stato utilizzato raramente a causa delle sue chiavi relativamente lunghe.

esempio

Vuoi decodificare il codice Hamming (dall'alto), veniamo dal presupposto che si verificano solo - errori di bit . I possibili vettori di errore sono quindi ${\ displaystyle [7,4,3]}$${\ displaystyle 1}$${\ displaystyle e}$

${\ displaystyle (1,0,0,0,0,0,0)}$

${\ displaystyle (0,1,0,0,0,0,0)}$

${\ displaystyle (0,0,1,0,0,0,0)}$

${\ displaystyle (0,0,0,1,0,0,0)}$

${\ displaystyle (0,0,0,0,1,0,0)}$

${\ displaystyle (0,0,0,0,0,1,0)}$

${\ displaystyle (0,0,0,0,0,0,1)}$

La sindrome viene ora calcolata per ciascuno di questi vettori di errore . Questo risulta in ${\ displaystyle s ^ {T} = Lui ^ {T}}$

${\ displaystyle e}$	${\ displaystyle s}$
${\ displaystyle (1,0,0,0,0,0,0)}$	${\ displaystyle (1,1,0)}$
${\ displaystyle (0,1,0,0,0,0,0)}$	${\ displaystyle (1,0,1)}$
${\ displaystyle (0,0,1,0,0,0,0)}$	${\ displaystyle (1,1,1)}$
${\ displaystyle (0,0,0,1,0,0,0)}$	${\ displaystyle (0,1,1)}$
${\ displaystyle (0,0,0,0,1,0,0)}$	${\ displaystyle (1,0,0)}$
${\ displaystyle (0,0,0,0,0,1,0)}$	${\ displaystyle (0,1,0)}$
${\ displaystyle (0,0,0,0,0,0,1)}$	${\ displaystyle (0,0,1)}$

Se viene ricevuta la parola sbagliata , i risultati . Ciò si traduce nel vettore di errore e viene quindi decodificato. La parola in chiaro è quindi . ${\ displaystyle x = (0,1,1,1,1,0,0)}$${\ displaystyle s ^ {T} = Hx ^ {T} = (1,0,1) ^ {T}}$${\ Displaystyle e = e ((1,0,1)) = (0,1,0,0,0,0,0)}$${\ displaystyle x}$${\ Displaystyle c (x) = (0,1,1,1,1,0,0) - (0,1,0,0,0,0,0) = (0,0,1,1,1 , 0.0)}$${\ displaystyle (0,0,1,1)}$

Esempio con decodifica incompleta

Viene fornito il codice di ripetizione ternario ( ) di lunghezza 3: ${\ displaystyle q = 3}$

${\ displaystyle G = {\ begin {pmatrix} 1 & 1 & 1 \ end {pmatrix}} \ qquad}$

${\ displaystyle H = {\ begin {pmatrix} 2 & 1 & 0 \\ 2 & 0 & 1 \\\ end {pmatrix}}}$

Ogni due colonne di sono linearmente indipendenti, mentre tutte e tre sono linearmente dipendenti. La distanza di Hamming minima del codice viene calcolata come il numero minimo di colonne dipendenti linearmente in 3. Ciò significa che è possibile correggere al massimo un errore di carattere. La tabella della sindrome ha questo aspetto: ${\ displaystyle H}$${\ displaystyle H}$

${\ displaystyle e}$	${\ displaystyle s}$
${\ displaystyle (1,0,0)}$	${\ displaystyle (2.2)}$
${\ displaystyle (2,0,0)}$	${\ displaystyle (1,1)}$
${\ displaystyle (0,1,0)}$	${\ displaystyle (1,0)}$
${\ displaystyle (0,2,0)}$	${\ displaystyle (2.0)}$
${\ displaystyle (0,0,1)}$	${\ displaystyle (0,1)}$
${\ displaystyle (0,0,2)}$	${\ displaystyle (0.2)}$

Utilizzando le linearità, il numero di righe potrebbe essere dimezzato, ma poi è necessario verificare se nella tabella è presente una sindrome dipendente in modo lineare.

Consideriamo ora , . Quando la sindrome è , la correzione è: . Il calcolo della sindrome di risultati: . Questo valore non è nella tabella della sindrome, quindi la parola non può essere corretta. ${\ displaystyle x = (1,1,0)}$${\ displaystyle y = (1,2,0)}$${\ displaystyle x}$${\ displaystyle Hx ^ {t} = (0.2) ^ {t}}$${\ displaystyle (1,1,0) - (0,0,2) = (1,1,1)}$${\ displaystyle y}$${\ displaystyle Hy ^ {t} = (1,2) ^ {t}}$

applicazione

La codifica e la decodifica, come descritto sopra, è relativamente complessa. Durante la codifica, la matrice del generatore deve essere mantenuta in memoria, cosa problematica nei sistemi con risorse limitate (es. Dispositivi mobili o sonde spaziali). Per la decodifica è necessaria una grande tabella, a seconda del tasso di correzione; il consumo di memoria è corrispondentemente grande. Per questo motivo, vengono solitamente utilizzate proprietà aggiuntive del codice per codificarli e decodificarli in modo efficiente. I codici binari ciclici possono essere implementati molto facilmente utilizzando i registri a scorrimento e le porte esclusive o , ad esempio .

Doppio codice

Per ogni codice (lineare) esiste un doppio codice (o anche doppio codice) , che è esso stesso un codice lineare. Le parole in codice del doppio codice sono tutte parole che sono doppie rispetto alle parole in codice : ${\ displaystyle C}$${\ displaystyle C ^ {\ perp}}$${\ displaystyle \ mathbb {F} _ {q} ^ {n}}$${\ displaystyle C}$

Un prodotto interno è definito per questo:

${\ displaystyle \ langle \ cdot; \ cdot \ rangle \ ,: \; \ mathbb {F} _ {q} ^ {n} \ times \ mathbb {F} _ {q} ^ {n} \ to \ mathbb { F} _ {q}}$

che mappa i vettori come segue: ${\ displaystyle x = (x_ {1}, x_ {2}, \ dots, x_ {n}), y = (y_ {1}, y_ {2}, \ dots, y_ {n})}$

${\ Displaystyle \ langle x; y \ rangle = \ sum _ {i = 1} ^ {n} x_ {i} y_ {i}}$

Nonostante la definizione simile, questo non è un prodotto scalare perché questa forma bilineare non è definita positiva . A causa delle proprietà dei campi finiti ci sono principalmente vettori che non sono uguali al vettore zero e per i quali il prodotto interno è 0. Pensa al vettore binario, per esempio . ${\ displaystyle (1,1)}$

Con l'aiuto di questa definizione, il doppio codice risulta come:

${\ Displaystyle C ^ {\ perp} = \ {x \ in \ mathbb {F} _ {q} ^ {n} \ mid \ langle x, c \ rangle = 0 \; \ mathrm {f {\ ddot {u }} r \; all} \; c \ in C \}}$

Una matrice generatore del doppio codice è una matrice di controllo del codice sorgente e viceversa.

Il doppio codice gioca un ruolo importante nell'analisi delle proprietà dei codici.

I cosiddetti codici auto-duali sono un caso speciale. Questi sono codici identici al loro doppio codice. Per ragioni dimensionali, questi hanno sempre la dimensione . L'esempio più importante di un codice auto-duale è il codice Hamming esteso, in cui il codice binario [7,4,3] Hamming è esteso di un bit di parità fino alla parità pari: ${\ displaystyle k = n / 2}$

${\ displaystyle G = H = {\ begin {pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\\ end {pmatrix}}}$

letteratura

• Werner Lütkebohmert : Teoria dei codici. Nozioni e algoritmi algebrico-geometrici. Vieweg Verlag, Braunschweig et al. 2003, ISBN 3-528-03197-2 ( corso Vieweg - corso avanzato di matematica ).
• JH van Lint : Introduzione alla teoria dei codici. 3a edizione rivista e ampliata. Springer Verlag, Heidelberg et al. 1999, ISBN 3-540-64133-5 ( Testi di laurea in matematica 86).
• Florence J. MacWilliams , Neil J. Sloane : The Theory of Error-Correcting Codes. 2. Stampa. Casa editrice North-Holland, Amsterdam 1978, ISBN 0-444-85009-0 ( biblioteca matematica North Holland 16).

Prove individuali

1. ^ ER Berlekamp, ​​RJ McEliece, HCA von Tilburg: sull'intrattabilità di alcuni problemi di codifica . In: Transazioni IEEE sulla teoria dell'informazione 24 . 1978.