Matrice di controllo. Generazione di matrici di codici a blocchi

introduzione

Descrizione del processo di comunicazione digitale

La sorgente fornisce un messaggio che generalmente rappresenta un segnale elettrico. Questo segnale viene convertito in forma digitale, utile per ulteriori elaborazioni.

Successivamente, le informazioni vengono compresse (codifica sorgente), il che riduce al minimo la ridondanza del messaggio. Il codice sorgente riduce i costi di trasmissione e memorizzazione delle informazioni. Successivamente, il messaggio dovrebbe essere trasmesso su un canale rumoroso. Affinché il messaggio raggiunga il consumatore in una forma non distorta, viene utilizzata la codifica delle informazioni immune al rumore (codifica del canale). Dal lato del consumatore, le informazioni vengono decodificate. Il decodificatore di canale corregge gli errori nella parola ricevuta e il decodificatore sorgente converte la parola corretta in una forma conveniente per il consumatore.

Quando si parla di codici che controllano gli errori, occorre distinguere due strategie del loro utilizzo.

1. Correzione diretta degli errori dovuti alla ridondanza (Forward Error Correction - FEC).
2. Rilevamento errori con successive richieste di ritrasmissione di informazioni erroneamente ricevute (Automatic Repeat Request - ARQ).

Quando si scelgono i metodi di codifica e decodifica, sono guidati da molti fattori, la cui relazione è mostrata nella figura.

La complessità totale include i costi hardware e software per l'implementazione dell'encoder e del decoder, il costo di archiviazione e trasmissione delle informazioni, ecc. La velocità del flusso di dati include la trasmissione di informazioni utili, bit di controllo, nonché richieste e ripetizioni per questi richieste di blocchi informativi individuali.

Codifica anti-interferenza

Informazione Generale

I sistemi di trasmissione dati reali non sono perfetti. Applicando la tecnologia dell'informazione, dobbiamo tenere conto della possibilità di errori nella trasmissione e nell'archiviazione delle informazioni. Questo vale principalmente per

• memorizzazione di informazioni su supporti ad alta densità (supporti magnetici, CD-ROM, DVD);
• trasmissione dati con potenza di segnale limitata (comunicazioni satellitari e mobili);
• trasmissione di informazioni attraverso canali altamente rumorosi (comunicazioni mobili, linee di comunicazione su filo ad alta velocità);
• canali di comunicazione con maggiori requisiti per l'affidabilità delle informazioni (reti di computer, linee di trasmissione con compressione dei dati).

In tutti i casi di cui sopra, vengono utilizzati codici di controllo degli errori.

Considera il modello più semplice di trasmissione dei dati utilizzando la codifica a correzione di errori.

Lascia che il codificatore sorgente emetta in sequenza parole di informazioni a lunghezza fissa. L'encoder di canale sostituisce ogni parola di informazione u con una parola di codice v. Il trasmettitore genera i segnali corrispondenti alla parola in codice v e li invia al canale. Il ricevitore esegue la trasformazione inversa, per cui la parola binaria ricevuta r viene inviata al decodificatore. Il decodificatore confronta la parola r ricevuta con tutte le possibili parole del codice del codice utilizzato. Se la parola r coincide con una delle parole in codice, al consumatore viene consegnata la parola informativa corrispondente. Se r differisce da tutti i codici, si è verificato un errore rilevabile sul canale. Lo scopo dell'utilizzo della codifica di canale è di far corrispondere la parola di informazione trasmessa u e la parola di informazione ricevuta u .

Da questa descrizione si possono trarre 2 conclusioni:

• Se, durante la trasmissione su un canale rumoroso, una parola in codice viene mappata in un'altra parola in codice che non corrisponde a quella trasmessa, si verifica un errore non rilevabile. Chiamiamolo errore di decodifica residuo.
• È necessario costruire codici con una certa struttura matematica, che permetta di riconoscere efficacemente e, in alcuni casi, correggere gli errori che si verificano quando l'informazione viene trasmessa su un canale di comunicazione.

Codici a blocchi lineari

I codici a blocchi binari lineari formano un'importante famiglia di codici. Questi codici sono notevoli in quanto, rappresentando informazioni e parole in codice sotto forma di vettori binari, possiamo descrivere i processi di codifica e decodifica utilizzando l'apparato dell'algebra lineare. In questo caso le componenti dei vettori e delle matrici introdotte sono i simboli 0 e 1. Le operazioni sulle componenti binarie vengono eseguite secondo le regole aritmetica modulo 2.

Il codice di linea più famoso è il codice di Hamming a blocchi. Inoltre, la descrizione dei codici a blocchi lineari verrà effettuata utilizzando questo codice come esempio. In particolare verrà preso in considerazione il codice (7,4) di Hamming.

Il codificatore di codice binario (n, k) mappa un insieme di 2 k possibili parole di informazioni binarie in un insieme di 2 k parole di codice n -dimensionali. Nella teoria dei codici, c'è sempre una corrispondenza biunivoca tra questi insiemi.

Invece di k bit del vettore di informazione, al canale vengono trasmessi n bit del vettore di codice. In questo caso si parla di codifica ridondante ad una velocità: R = n ⁄ k.

Minore è la velocità, maggiore è la ridondanza del codice e maggiori sono le possibilità di protezione dagli errori che ha. Tuttavia, va tenuto presente che con un aumento della ridondanza aumenta anche il costo del trasferimento delle informazioni.

Descrizione dei processi di codifica e decodifica

Il materiale iniziale per la costruzione di costruzioni di codice è uno spazio vettoriale binario n-dimensionale, in cui sono specificate le operazioni aritmetiche modulo 2. In esso è incorporato uno spazio lineare k-dimensionale contenente 2 k parole del codice. Il codice C è formato utilizzando 2 k combinazioni di k vettori base linearmente indipendenti (g 1, ..., g k).

Questi vettori formano le righe della matrice generatrice del codice C.

Per un codice C esiste un codice duale C d tale che il prodotto scalare di una qualsiasi coppia di vettori, uno dei quali appartiene allo spazio C e l'altro allo spazio C d, è sempre zero. Ciò significa che i vettori del codice C d sono ortogonali ai vettori del codice C. Se invece qualche vettore è ortogonale a tutti i vettori del codice C, allora appartiene al codice C d e viceversa . Il sottospazio vettoriale duale è "spalmato" da n - k vettori base linearmente indipendenti (h 1,…, h n - k). Questi vettori formano le righe della matrice del controllo di parità.

Consideriamo un esempio di matrice di generazione e controllo di parità per un codice di Hamming (7,4):

Da notare una proprietà importante: sia la matrice generatrice che quella di parità contengono la matrice identità. Questa proprietà viene utilizzata nei processi di codifica e decodifica.

codifica

La parola di codice v e la parola di informazione u sono legate dal rapporto:

dove G è la matrice generatrice, la cui struttura è stata descritta sopra.

Ad esempio, il vettore di informazioni u = (1010) è mappato al vettore di codice come segue:

È facile vedere che gli ultimi quattro bit del vettore di codice coincidono con il vettore di informazione. Questa proprietà è chiamata coerenza del codice.

I codici in cui una parola d'informazione può essere estratta direttamente dal vettore di codice corrispondente sono chiamati sistematici. La matrice generatrice di un qualunque codice sistematico può sempre essere ridotta alla seguente forma riordinando le colonne:

G k × n = (P k × (n - k) I k),

dove I k è la matrice identità k × k.

Pertanto, è sempre possibile individuare informazioni e controllare i simboli nel vettore di codice del codice sistematico.

Il ruolo dei caratteri di controllo e il loro utilizzo verranno spiegati in dettaglio di seguito.

decodifica

Il compito del decodificatore è quello di ripristinare il vettore dell'informazione trasmessa utilizzando la struttura del codice, basata sulla parola ricevuta r. Per il codice di Hamming (7, 4) considerato sopra, può essere proposto il seguente algoritmo di rilevamento degli errori. Poiché il codice considerato è sistematico, esprimiamo ciascuno dei tre simboli di parità in termini di simboli del vettore di informazione:

V 0 = v 3 ⊕ v 5 ⊕ v 6
v 1 = v 3 ⊕ v 4 ⊕ v 5
v 2 = v 4 ⊕ v 5 ⊕ v 6

Se si verifica un errore nel canale, nel vettore ricevuto r almeno una delle uguaglianze non sarà soddisfatta. Scriviamo le relazioni di prova ottenute sotto forma di un sistema di equazioni per le componenti del vettore r:

R 0 ⊕ r 3 ⊕ r 5 ⊕ r 6 = s 0
r 1 ⊕ r 3 ⊕ r 4 ⊕ r 5 = s 1
r 2 ⊕ r 4 ⊕ r 5 ⊕ r 6 = s 2

Quindi, dalle prime tre colonne della matrice generatrice G, abbiamo ottenuto un sistema di tre equazioni di controllo. Se nel sistema di equazioni ottenuto almeno uno dei componenti (s 0, s 1, s 2) non è uguale a zero, si è verificato un errore nel canale.

Scriviamo il sistema di equazioni di prova in forma generale. Per qualsiasi codice sistematico con una matrice generatrice G, la matrice del controllo di parità è definita come segue:

H (n - k) × n = (I n - k P T k × (n - k)).

Quindi il sistema di equazioni di prova può essere scritto nella forma

Il vettore s è comunemente chiamato sindrome. Pertanto, verrà rilevato un errore se almeno uno dei componenti s non è zero.

Ad esempio, si consideri la decodifica sindromica del codice (7, 4) di Hamming. Quando si trasmette una parola d'informazione u = (1010) su un canale senza rumore, r = v = (0011010). Possiamo assicurarci che in questo caso la sindrome sia uguale a 0.

Se, ad esempio, si verifica un singolo errore nel codice alla quarta posizione (r = (0010010)), la quarta riga della matrice di controllo trasposta è la sindrome.

Dopo aver esaminato tutte le possibili posizioni di un singolo errore, otteniamo una tabella completa di sindromi di errore singolo - una tabella di corrispondenze del numero della cifra errata alla sindrome risultante.

Si può notare che un errore nella i-esima posizione della parola in codice corrisponde alla sindrome formata dalla i-esima colonna della matrice H. Poiché tutte le colonne della matrice sono diverse, possiamo utilizzare la tabella delle sindromi per correggere un singolo errore introdotto dal canale.

Varietà di errori

I codici a blocchi lineari hanno 3 tipi di errori:

1. Errore riconosciuto e correggibile
   • La sindrome è presente nella tabella delle sindromi
   • Il decoder riconosce e corregge l'errore, quindi trasmette la parola corretta al ricevitore
2. Errore riconosciuto
   • La parola ricevuta non corrisponde a nessuna delle parole in codice
   • La sindrome non è presente nella tabella delle sindromi
   • Il decoder riconosce l'errore e invia una richiesta di ritrasmissione della parola dati.
3. Errore irriconoscibile
   • La parola ricevuta corrisponde a una delle parole in codice (non corrisponde alla parola in codice originale)
   • La sindrome è 0
   • Il decoder non riconosce l'errore ed emette un messaggio informativo errato al consumatore

Conclusione

Va notato che l'efficacia di un determinato codice dipende dall'area della sua applicazione e, in particolare, dal canale di comunicazione. Se il rapporto segnale-rumore nel canale è sufficientemente grande, la probabilità di un singolo errore è molte volte superiore alla probabilità di errori di ordine superiore, quindi l'uso del codice di Hamming con la correzione di un singolo errore in un tale canale può essere molto efficace. D'altra parte, nei canali in cui predominano più errori (ad esempio, canali con dissolvenza), la correzione di singoli errori non ha senso. Nella scelta pratica di uno specifico codice correttore di errori, è anche necessario tenere conto della velocità della sua decodifica e della complessità della sua implementazione tecnica.

Letteratura

1. Werner M. Fondamenti di codifica. - M.: Tecnosfera, 2004.
2. Bleihut R. Teoria e pratica dei codici di controllo degli errori. - M.: Mir, 1986.

Oleg Rybaki

In effetti, è difficile trovare una spiegazione adeguata. Molto spesso, gli autori presumono che il lettore sappia molto in anticipo e non cercano di spiegare punti apparentemente semplici che contengono l'essenza. Sono molto contento di essermi imbattuto in questo materiale e di aver chiarito qualcosa per me stesso.

I codici lineari hanno la seguente proprietà:

Di tutta la moltitudine 2 K di parole in codice consentite che formano un gruppo lineare, i sottoinsiemi possono essere distinti da K parole che hanno la proprietà di indipendenza lineare.

Indipendenza lineare significa che nessuna delle parole incluse nel sottoinsieme di parole di codice linearmente indipendenti può essere ottenuta sommando (usando un'espressione lineare) qualsiasi altra parola inclusa in questo sottoinsieme.

Allo stesso tempo, una qualsiasi delle parole in codice consentite può essere ottenuta sommando alcune parole linearmente indipendenti.

Pertanto, la costruzione di combinazioni di codici di un codice lineare è associata a operazioni lineari. Per eseguire tali operazioni, è conveniente utilizzare un apparato di calcolo a matrice ben sviluppato.

Per l'istruzione n Le parole in codice a -bit da parole codificate a k-bit (codifica) utilizzano una matrice, che viene chiamata generazione (generazione).

La matrice generatrice si ottiene scrivendo k parole linearmente indipendenti in una colonna.

Indichiamo la sequenza di informazioni codificate X e lo scriveremo sotto forma di matrice riga || X || dimensione 1* K, Per esempio:

|| X || = || 11001 ||, dove k = 5.

Uno dei modi per costruire una matrice generatrice (generatrice) è la seguente: è costruita dalla matrice identità || Io || dimensione k * k e la matrice di cifre aggiuntive (ridondanti) ad essa assegnate a destra || MDR || dimensioni k * r.

dove a K=4

Questa struttura di OM fornisce un codice sistematico.

La procedura per la costruzione della matrice MDS sarà discussa di seguito.

7.4 Ordine di codifica

Il codice KS si ottiene moltiplicando la matrice della sequenza delle informazioni || X || sulla matrice generatrice || ОМ ||:

La moltiplicazione viene eseguita secondo le regole della moltiplicazione matriciale: (SO su SO)

Devi solo ricordare che l'addizione qui è modulo 2.

per esempio, la matrice generatrice

|| ОМ || = 0010 011

e il vettore riga della sequenza di informazioni

Poiché la matrice da moltiplicare ha una sola riga, la moltiplicazione è semplificata. In questo caso, si dovrebbero assegnare le righe della matrice generatrice (generatrice) || OM || bit della matrice della sequenza di informazioni || X || e aggiungi quelle righe della matrice generatrice (generatrice) che corrispondono alle cifre unitarie della matrice ||X||.

notare che || KC || = || X, ||,

dove || X || - sequenza di informazioni (poiché moltiplicata per la matrice identità || Io ||),

un || DR ||- cifre aggiuntive, a seconda della matrice delle cifre aggiuntive || MDR ||:

|| DR || = || X || * || MDR ||

7.5 Ordine di decodifica

A causa della trasmissione della parola in codice attraverso il canale, può essere distorta da interferenze. Ciò causerà il codeword accettato || PKS || potrebbe non corrispondere all'originale || COP ||.

La distorsione può essere descritta utilizzando la seguente formula:

|| PKS || = || KS || + || IN ||,

dove || IN ||- vettore di errore - riga di matrice con dimensione 1* n, Con 1 in quelle posizioni in cui si è verificata la distorsione.

La decodifica si basa sulla ricerca del cosiddetto identificatore o sindrome della riga matrice di errore || OP || la lunghezza R cifre ( R- il numero di bit aggiuntivi o ridondanti nella parola di codice).

L'identificatore viene utilizzato per trovare il vettore di errore stimato.

L'identificatore si trova con la seguente formula:

|| OP || = || PC || * || TPM ||,

dove || PC || - codice ricevuto ed eventualmente corrotto;

|| TPM ||, - la matrice di parità trasposta che si ottiene dalla matrice di riempimento || MDR || assegnandogli la matrice unitaria dal basso:

Esempio || TPM ||:

Nella misura in cui || PKS || = || KS || + || BO ||, l'ultima formula può essere scritta come:

|| OP || = || KS || * || TPM || + || VO || * || TPM ||.

Considera il primo termine.

|| KC ||è una matrice riga, e la prima K cifre - informativo.

Dimostriamo ora che il prodotto della parola in codice || COP || sul || TPM || risulta in una matrice zero ||0||.

Nella misura in cui || COP ||- matrice-riga, è possibile un ordine semplificato di moltiplicazione delle matrici sopra considerate.

Pertanto, il primo termine in

|| OP || = || KS || * || TPM || + || IN || * || TPM ||

sempre uguale a zero e l'identificatore è completamente dipendente dal vettore di errore || IN ||.

Se ora scegliamo una tale matrice di controllo di parità TPM e quindi MDR in modo che vettori di errore diversi corrispondano a identificatori diversi OPERAZIONE, quindi da questi identificatori sarà possibile trovare il vettore di errore IN, e quindi correggere questi errori.

La corrispondenza degli identificatori ai vettori di errore si trova in anticipo moltiplicando i vettori degli errori correggibili per TPM;

Pertanto, la capacità di un codice di correggere gli errori è interamente determinata da || MDR ||. Per costruire MDR per i codici che correggono errori singoli, è necessario in ogni riga MDR avere almeno 2 unità. Anche in questo caso è necessario avere almeno una differenza tra due righe qualsiasi MDR.

Il codice che abbiamo ricevuto è scomodo in quanto l'identificatore, sebbene sia inequivocabilmente associato al numero del bit distorto, in quanto un numero non è uguale ad esso. Per cercare un bit distorto, è necessario utilizzare una tabella di corrispondenza aggiuntiva tra l'identificatore e questo numero. Sono stati trovati codici in cui l'identificatore come numero determina la posizione della cifra distorta e hanno ricevuto il nome Codici di hamming.

Edificio MDR per il caso di correggere più errori diventa molto più complicato. Diversi autori hanno trovato diversi algoritmi per la costruzione || MDR || per questo caso, ei codici corrispondenti sono nominati con i nomi dei loro autori.

A titolo di esempio, abbiamo considerato i codici di correzione più semplici: un semplice codice di controllo di parità che rileva un singolo errore in una sequenza ricevuta e un codice iterativo a blocchi e un codice cloud che correggono un singolo errore utilizzando una serie di controlli di parità. In tutti i codici, nel processo di codifica di correzione degli errori, sono stati formati bit aggiuntivi, aggiunti alla combinazione di codice originale.

Fissiamo le regole formali (generative) in base alle quali viene eseguita la codifica, ad es. convertire la sequenza di informazioni in una parola in codice.

Il modo più semplice per descrivere o assegnare codici di correzione è modo tabellare, in cui a ciascuna sequenza di informazioni viene semplicemente assegnata una parola in codice dalla tabella dei codici. Ad esempio, per il codice più semplice con controllo di parità, la tabella di corrispondenza tra combinazioni di codice sorgente e codice sarà la seguente:

Questo modo di descrivere i codici è applicabile a qualsiasi codice, non solo lineare. Tuttavia, per grandi a la dimensione della tabella dei codici risulta essere troppo grande per essere utilizzata in pratica.

Un altro modo per definire i codici a blocchi lineari consiste nell'utilizzare il cosiddetto sistemi di generazione di equazioni, definendo la regola secondo la quale i simboli della sequenza informativa vengono convertiti in simboli di codice. Per lo stesso esempio, il sistema di generazione delle equazioni sarà simile a questo:

Tuttavia, il modo più comodo e intuitivo per descrivere i codici a blocchi lineari è definirli utilizzando matrice generatrice, che è una forma compatta di rappresentazione del sistema di equazioni di prova.

Blocco lineare(l, / s) -il codice è completamente determinato dalla matrice G con dimensione a X P con elementi di matrice binaria. Inoltre, ogni parola di codice è una combinazione lineare delle righe della matrice G, e ogni combinazione lineare delle righe di G è una parola di codice.

Verranno chiamati codici a blocchi lineari definiti generando matrici codici a matrice. La consueta rappresentazione (canonica) della matrice generatrice si presenta così:

Ad esempio, per il codice di controllo di parità più semplice (4, 3), la matrice di generazione sarà simile a:

Permettere T -(t 1; t 2, ..., t a) sarà il blocco di messaggi che deve essere codificato utilizzando questo codice.

Quindi la parola in codice corrispondente tu volere

Tenendo conto della struttura della matrice G caratteri del codice e sarà così:

In altre parole, a i simboli più a sinistra della parola in codice coincidono con i simboli della sequenza di informazioni codificate e il resto (n - A) i caratteri sono combinazioni lineari di caratteri di sequenza di informazioni.

Ad esempio, se la sequenza di input dell'encoder t == (10 1), quindi utilizzando la matrice generatrice il codice sarà costruito come segue:

8 Il comandante mandò tre esploratori lungo la prima strada, tre lungo la seconda, due lungo la terza, e percorse lui stesso la quarta. Creare una matrice generatrice per tale codice.

Risposta: Secondo la trama dell'attività, il messaggio ricevuto personalmente dal comandante non può essere distorto. Pertanto, ci limiteremo allo studio delle informazioni trasmesse dai combattenti. In un gruppo che si avvia lungo una delle strade, ogni soldato deve riferire al comandante o sul rilevamento di un oggetto (designiamo tale rapporto come "1") o sull'assenza di un oggetto ("0" ). In assenza di distorsioni, i rapporti di ciascun combattente dello stesso gruppo devono essere gli stessi. Quindi:

La matrice può essere portata alla forma canonica rinumerando i combattenti, ad es. sulla prima strada, inviando la prima, la quarta e la quinta, sulla seconda strada - la seconda, la sesta e la settima, sulla terza strada - il terzo e l'ottavo combattente. Otteniamo la seguente matrice generatrice:

Il codice così definito si chiama sistematico a blocchi lineari(P,/ codice cj con controlli di parità generalizzati.

La matrice generativa il codice lineare è chiamato matrice di dimensioni, le cui righe sono i suoi vettori di base.

Ad esempio,

è la matrice generatrice del codice a due parole (000, 011).

è il generatore per il codice B dell'esempio 6.3.

Sappiamo che le parole in codice sono combinazioni lineari di vettori di base, ad es. righe della matrice. Ciò significa che le parole possono essere ottenute moltiplicando un vettore per una matrice. Quindi, il messaggio è scritto come un vettore e la parola in codice corrispondente al messaggio è calcolata dalla formula

Pertanto, il vettore di bit viene convertito in una sequenza di simboli binari trasmessi sul canale o scritti nella memoria del dispositivo di memorizzazione.

Passiamo al problema della decodifica.

Supponiamo che per qualche vettore binario tutte le codeword del codice , soddisfare l'identità

in cui denota il prodotto scalare di vettori e.

Diciamo di un tale vettore che è ortogonale. Avendo trovato un tale vettore, potremmo verificare, utilizzando identity (6.2), se la sequenza ricevuta dal canale è una codeword.

Si noti che (6.2) è valido per tutti i codici se è valido per i vettori di base, ad es. Se

dove l'apice T denota la trasposizione.

Più "controlli" troviamo, più errori saremo in grado di rilevare e correggere.

Esercizio 6.4... Dimostrare che i controlli formano uno spazio lineare.

Questo spazio sarà chiamato spazio ortogonale a un codice lineare o spazio di verifica.

Esercizio 6.5... Trova la dimensione dello spazio lineare degli assegni.

Per completare l'ultimo esercizio, è necessario notare che la matrice ha colonne esattamente linearmente indipendenti. Non più (perché?) E non meno (perché?). Fissiamo l'elenco dei numeri di queste colonne e chiamiamo questo insieme di numeri set di informazioni... Un po 'più tardi, il significato di questo nome diventerà più chiaro. Scegliamo arbitrariamente i valori del vettore in posizioni che non sono incluse nel set di informazioni. Quali dovrebbero essere i valori nelle posizioni delle informazioni impostate per (6.3) da soddisfare? Per rispondere a questa domanda, è necessario risolvere un sistema di equazioni lineari e il sistema ha una soluzione unica.

Una conseguenza di questo ragionamento è il teorema

Teorema. La dimensione dello spazio di controllo di un codice lineare è uguale a.

Scriviamo la base dello spazio test sotto forma di matrice

chiamato controlla matrice codice.

Le matrici di controllo e generatore sono legate dalla relazione

Da questa relazione vediamo che per ogni parola in codice esiste

Questa identità può essere utilizzata come criterio affinché una sequenza arbitraria appartenga a un codice, ad es. per rilevare errori.

Sapendo, si può trovare. Per capire come fare, si noti che lo stesso codice può essere specificato da diverse matrici generatrici, scegliendo in modi diversi la base dello spazio. Inoltre, sostituendo in qualsiasi stringa con qualsiasi combinazione lineare di questa stringa con altre stringhe, si ottiene una nuova matrice generatrice dello stesso codice.

La permutazione delle colonne della matrice, in generale, porta a un codice diverso, ma quest'altro codice non differisce nelle sue caratteristiche da quello originale. Vengono chiamati codici che differiscono solo per la numerazione delle posizioni equivalente.

È chiaro che per ogni codice ce n'è uno equivalente per cui le prime posizioni formano un insieme di informazioni, es. le prime colonne formano una matrice di dimensioni non degenere. Sostituendo le righe con combinazioni lineari di righe (metodo di Gauss), la matrice risultante può essere ridotta alla forma

dove è la matrice dell'ordine delle unità ed è una matrice di dimensioni.

Una matrice della forma (6.6) è detta matrice generatrice ridotta a modo sistematico e viene chiamato il codice corrispondente sistematico... La codifica per il codice sistematico è un po' più semplice rispetto al codice generale:

, (6.7)

quelli. nel codice, le prime posizioni sono solo una copia della sequenza di informazioni e le restanti posizioni (di controllo) sono ottenute moltiplicando il vettore di informazioni per una matrice di dimensioni, che a volte è significativamente inferiore a. Di conseguenza, le informazioni sul codice sistematico occupano molta meno memoria rispetto alle informazioni sul codice lineare generale.

Per un codice sistematico con una matrice generatrice nella forma (6.6), la matrice del controllo di parità può essere calcolata con la formula

Esercizio 6.6... Controllare (6.7). Suggerimento: per questo è necessario sostituire (6.8) e (6.6) in (6.4).

Come trovo una matrice di controllo per un codice non sistematico?

Molto semplice. È necessario portare la matrice ad una forma sistematica e utilizzare (6.7). Se le prime colonne della matrice generatrice formano una sottomatrice non degenere (le prime posizioni formano un insieme di informazioni), sono sufficienti operazioni come la permutazione di riga e la sostituzione di righe con combinazioni lineari di righe per portarla a una forma sistematica. In caso contrario, dovrai prima trovare il set di informazioni e rinumerare le posizioni in modo che le prime posizioni diventino informative.

Poiché, secondo la definizione, il codice lineare (l, / c) di lunghezza P sopra GF (q)è un sottospazio GF k (q) spazio vettoriale GF n (q), allora deve esserci un complemento ortogonale del sottospazio GF k (q) codice di linea (cfr. punto 1.7.1).

Sia Н una matrice le cui righe corrispondono ai vettori di base del complemento ortogonale di un codice lineare g-ario C di lunghezza P. Allora, per ogni vettore c appartenente al codice, è vero:

La condizione (2.10) permette di verificare l'appartenenza di una n-sequenza arbitraria di elementi GF (q) un certo codice lineare g-ary.

Se un vettore di un codice lineare ha un peso di Hamming sho, allora ciò significa che ci sono simboli sho diversi da zero nel codice (secondo la definizione di un peso di Hamming, vedere la sottosezione 2.1.4). Quindi, secondo le regole della moltiplicazione matriciale, il prodotto di un vettore di valore w0 del peso di Hamming per la matrice H t corrisponde a una combinazione lineare di colonne sho della matrice N. Inoltre, l'uguaglianza (2.10) vale ovviamente se e solo se non ci sono colonne della matrice n sono linearmente dipendenti.

Quindi, la condizione per l'esistenza nell'insieme delle parole di codice di un codice lineare di una parola di codice con il peso di Hamming sho è la presenza nella matrice n colonne linearmente dipendenti nel numero di sho. Ne consegue anche che un codice lineare ha un peso minimo (vedi Sottosezione 2.1.4) almeno un valore w0 se e solo se alcune colonne w0 - 1 della matrice H sono linearmente indipendenti. Quindi, per la disuguaglianza (2.6), per trovare un codice lineare con peso minimo w0, correggendo T errori, basta trovare la matrice H, con almeno sho - 1 = 2 -T tutte le colonne erano linearmente indipendenti.

Diamo un'occhiata più da vicino alla matrice N. Come accennato in precedenza, le righe della matrice n sono i vettori base del complemento ortogonale del codice lineare. Se l'insieme di n-sequenze forma un sottospazio di dimensione A, allora il complemento ortogonale di questo sottospazio avrà la dimensione PC(cfr. punti 1.7.1 e 1.7.2). Dimensione del sottospazio P- a per molti PC vettori di base. Pertanto la matrice n dovrebbe contenere PC linee linearmente indipendenti.

Poiché le matrici G e n appartengono allo stesso spazio di n-sequenze, quindi il numero di colonne della matrice nè uguale al numero di colonne della matrice G. Pertanto, la matrice n ha dimensioni (l - A) x l. Tutte le colonne della matrice H, come già accennato, formano gruppi linearmente indipendenti rispetto a 2t colonne.

Secondo la relazione (2.2), qualsiasi parola di codice di un codice lineare è una combinazione lineare di righe della matrice generatrice G del codice. In questo caso, ovviamente, ogni riga della matrice G corrisponde a qualche parola in codice. Pertanto, la relazione (2.10) può essere riscritta come segue:

Il prodotto di matrici G di dimensione A* se H t taglia l x (PC)è la matrice delle dimensioni a x (l- A), costituito da zero elementi.

Matrice n dimensione ( n-k) x l, le cui rette sono i vettori base del complemento ortogonale del sottospazio del codice lineare, si chiama controlla matrice codice lineare.

Per la relazione (2.4), la matrice generatrice del codice lineare sistematico è costituita dalla matrice identità di ordine a e matrici di simboli di controllo di dimensione a x (l- A), che, a sua volta, è un'estensione della matrice identità. Come mostrato nell'Appendice 1, la moltiplicazione di due matrici può essere eseguita dividendo le matrici moltiplicate in matrici (blocchi) più piccole e quindi moltiplicando i singoli blocchi delle matrici moltiplicate. Allora per le matrici G e n tu puoi scrivere:

Numero di colonne in blocchi A e B matrici n 7 deve corrispondere al numero di righe in blocchi Ek e R matrici G (secondo le regole della moltiplicazione matriciale). La matrice risultante deve avere dimensione / s * (l - A). Ovviamente, se mettiamo UN = -R e V= El_ / s, quindi la matrice n soddisferà l'equazione (2.11).

Quindi la matrice H tè un'estensione della matrice -R e oltre alla matrice - R matrice n contiene la matrice identità di ordine P - A. Matrice H tè il risultato della trasposizione della matrice N.

Il risultato della trasposizione ripetuta della matrice è la matrice originale. Pertanto la matrice n si ottiene trasponendo la matrice Nt. Poiché per ogni elemento a, i campi GF [ 2) a = - a è vero, quindi per un codice lineare binario è vero R - R.

Matrice n il codice della linea binaria sarà simile a questo:

Matrice R, incluso nella matrice G e contenente i simboli di spunta, si ottiene trasponendo la matrice pt, incluso nella matrice N.

Quindi, la costruzione di un codice lineare si riduce a trovare la matrice N. Per una data matrice nè facile trovare la matrice G.

Esempio 2.1.4. Considera la costruzione di un codice lineare binario - un codice su GF (2) che corregge un errore di una parola di codice con una sequenza di informazioni di dimensioni a= 3 bit.

Secondo la relazione (2.9), per il codice con la massima distanza r = 2-t == 2. Allora n = fc + r = 3 + 2 = 5. Tuttavia, come verrà mostrato nel prossimo paragrafo, un codice binario (5,3) lineare non è in grado di correggere un singolo errore di codeword. In questo caso, il numero minimo di simboli ridondanti per questo caso è G= 3, e il codice in esame è un codice binario lineare (6,3).

Quindi, in questo caso, la matrice n contiene una matrice di controllo di dimensione / cx (n- / c) = 3 * 3 e una matrice identità di ordine n-k = 3.

Tutte le colonne della matrice n devono formare gruppi linearmente indipendenti di due colonne e gruppi linearmente dipendenti di tre colonne. Questa condizione è soddisfatta, ad esempio, dalle sequenze 101, 110 e 011 su GF (2). Le sequenze specificate formano le colonne della matrice pt, incluso nella matrice N. Il resto degli elementi della matrice n corrispondono alla matrice identità di ordine 3:

Sommando alla matrice identità di ordine 3 la matrice P ottenuta trasponendo la matrice pt, otteniamo la matrice G:

Consideriamo ora il processo di formazione e la struttura di una parola in codice di un codice binario lineare (6, 3) con una matrice generatrice della forma (2.12):

I primi tre caratteri della parola in codice (ci - Cs) contengono simboli di informazione (/ 1 - g "s), formati come risultato della moltiplicazione della matrice della sequenza di informazioni io sulla matrice identità di ordine 3, che fa parte della matrice G. I restanti simboli del codice (C4 - Cb) contengono simboli di spunta (t^ - tz), ottenuto come risultato della moltiplicazione della matrice della sequenza di informazioni per la matrice dei simboli di controllo R, incluso anche nella matrice G.

È facile verificare che nel caso del codice (6, 3) dell'Esempio 2.1.4, il numero minimo di simboli diversi da zero tra tutte le parole di codice è tre (parole di codice 001101, 010011,100110 e 111000). In questo modo, D *= 3 e, secondo la relazione (2.5), il codice deve correggere un errore di codeword. Come verrà mostrato nel prossimo comma, questo è effettivamente il caso.