Ad esempio, abbiamo appena considerato i codici di correzione più semplici: un codice con un semplice controllo di parità che rileva un singolo errore nella sequenza ricevuta, nonché un codice iterativo a blocchi e un codice cloud che correggono un singolo errore utilizzando un insieme 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 tabella dei codici risulta essere troppo grande per essere utilizzato nella pratica.
Un altro modo per definire i codici a blocchi lineari consiste nell'utilizzare il cosiddetto sistemi di generazione di equazioni, definire la regola secondo la quale i caratteri della sequenza informativa vengono convertiti in caratteri in 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.
Nei sistemi di comunicazione sono possibili diverse strategie per affrontare gli errori:
- rilevamento di errori nei blocchi di dati e richiesta di ritrasmissione automatica blocchi danneggiati: questo approccio viene utilizzato principalmente a livello di collegamento e trasporto;
- rilevare gli errori nei blocchi di dati e scartare i blocchi danneggiati: questo approccio è talvolta utilizzato nei sistemi di streaming multimediale in cui il ritardo di trasmissione è importante e non c'è tempo per la ritrasmissione;
- Correzione dell'errore(ing. correzione degli errori in avanti) si applica a livello fisico.
Rilevamento degli errori e codici di correzione
I codici di correzione sono codici utilizzati per rilevare o correggere errori che si verificano durante la trasmissione di informazioni sotto l'influenza di interferenze, nonché durante la sua memorizzazione.
Per fare ciò, durante la scrittura (trasferimento), aggiungi al payload in modo speciale strutturato eccesso informazioni e durante la lettura (ricezione) viene utilizzato per rilevare o correggere errori. Naturalmente il numero di errori che possono essere corretti è limitato e dipende dallo specifico codice utilizzato.
CON codici di correzione degli errori, strettamente connesso codici di rilevamento degli errori... A differenza del primo, quest'ultimo può solo stabilire il fatto che c'è un errore nei dati trasmessi, ma non correggerlo.
Infatti, i codici di rilevamento degli errori utilizzati appartengono alle stesse classi di codici dei codici di correzione degli errori. In effetti, qualsiasi codice correttore di errori può essere utilizzato anche per rilevare errori (in tal modo sarà in grado di rilevare Di più errori di quelli che è stato in grado di correggere).
A proposito di lavorare con i dati, i codici che correggono gli errori sono suddivisi in blocco dividere le informazioni in frammenti di lunghezza costante ed elaborare ciascuno di essi separatamente, e convolutivo che trattano i dati come un flusso continuo.
Codici di blocco
Lascia che le informazioni codificate siano divise in frammenti di lunghezza K bit che vengono convertiti in parole in codice la lunghezza n morso. Quindi il codice del blocco corrispondente è solitamente indicato ( n,K). In questo caso, il numero viene chiamato velocità del codice.
Se l'originale K bit il codice lascia invariato e aggiunge n − K verifica, questo codice si chiama sistematico, altrimenti non sistematico.
Puoi impostare il codice del blocco in diversi modi, inclusa una tabella, in cui ogni set di K i bit di informazione sono mappati n bit della parola in codice. Ma, buon codice deve soddisfare almeno i seguenti criteri:
- la capacità di correggere il maggior numero possibile di errori,
- minor ridondanza possibile,
- facilità di codifica e decodifica.
È facile vedere che i requisiti dati si contraddicono a vicenda. Ecco perché c'è un gran numero di codici, ciascuno dei quali è adatto alla propria gamma di compiti.
Quasi tutti i codici utilizzati sono lineari. Ciò è dovuto al fatto che i codici non lineari sono molto più difficili da studiare ed è difficile per loro fornire una facilità accettabile di codifica e decodifica.
Spazi lineari
matrice generativa
Questa relazione stabilisce una relazione tra i vettori dei coefficienti 
e vettori. Enumerando tutti i vettori dei coefficienti si ottengono tutti i vettori. In altre parole, la matrice G genera spazio lineare.
Controlla matrice
Ciò significa che l'operazione di codifica corrisponde alla moltiplicazione dell'originale K-bit vettore a una matrice non degenere G chiamato matrice generatrice.
Sia un sottospazio ortogonale rispetto a C, un h- matrice che definisce la base di questo sottospazio. Allora per ogni vettore è vero:
.
Proprietà e teoremi importanti
Distanza minima e capacità di correzione
Frontiera di Hamming e codici perfetti
Sia un blocco binario ( n,K) codice con capacità di correzione T... Allora la disuguaglianza (chiamata confine di Hamming):
.
I codici che soddisfano questo confine con l'uguaglianza sono chiamati Perfetto... I codici perfetti includono, ad esempio, i codici di Hamming. I codici con un grande potere correttivo (come i codici Reed-Solomon), che sono spesso usati nella pratica, non sono perfetti.
Guadagno di energia
Quando si trasmettono informazioni su un canale di comunicazione, la probabilità di errore dipende dal rapporto segnale-rumore all'ingresso del demodulatore, quindi, a livello di rumore costante, la potenza del trasmettitore è di importanza decisiva. Nei sistemi satellitari e mobili, così come in altri tipi di comunicazione, il problema del risparmio energetico è acuto. Inoltre, in certi sistemi comunicazione (ad esempio, telefono) per aumentare la potenza del segnale senza limiti non sono dati da restrizioni tecniche.
Poiché la codifica a correzione di errori consente di correggere gli errori, durante l'utilizzo è possibile ridurre la potenza del trasmettitore, lasciando invariata la velocità di trasmissione delle informazioni. Il guadagno di energia è definito come la differenza tra il SNR in presenza e assenza di codifica.
Applicazione matrice di controllo di parità- - [L.G. Sumenko. Il dizionario inglese russo di tecnologia dell'informazione. M .: GP TsNIIS, 2003.] Argomenti tecnologie dell'informazione in generale EN check matrix ... Guida tecnica per traduttori
Nel campo della matematica e della teoria dell'informazione, il codice di linea è un tipo importante di codice a blocchi utilizzato negli schemi di rilevamento e correzione degli errori. I codici lineari, rispetto ad altri codici, consentono di implementare algoritmi più efficienti ... ... Wikipedia
Per migliorare questo articolo, è auspicabile?: Trova e disponi sotto forma di note a piè di pagina collegamenti a fonti autorevoli che confermano quanto scritto. Codice ciclico ... Wikipedia
Il codice ciclico è un codice lineare con la proprietà della ciclicità, ovvero ogni permutazione ciclica di una parola in codice è anche una parola in codice. Utilizzato per trasformare le informazioni per proteggerle da errori (vedi Rilevamento e ... ... Wikipedia
- (Codice LDPC dall'inglese Codice di controllo di parità a bassa densità, codice LDPC, codice a bassa densità) codice utilizzato nella trasmissione di informazioni, un caso speciale di codice lineare a blocchi con controllo di parità. Una caratteristica è la bassa densità di significativi ... ... Wikipedia
Codice di controllo di parità a bassa densità (codice LDPC, codice LDPC) codice utilizzato nella trasmissione di informazioni, un caso speciale di codice di linea di blocco con controllo di parità. Caratteristica ... ... Wikipedia
I codici Reed-Solomon sono codici ciclici non binari che consentono di correggere gli errori nei blocchi di dati. Gli elementi del vettore di codice non sono bit, ma gruppi di bit (blocchi). I codici Reed Solomon sono molto comuni, ... ... Wikipedia
introduzione
Descrizione del processo di comunicazione digitale
La fonte emette un messaggio che rappresenta in caso generale alcuni segnale elettrico... Questo segnale viene convertito in modulo digitale, che è conveniente 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.
- Correzione diretta degli errori dovuti alla ridondanza (Forward Error Correction - FEC).
- 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 del segnale limitata (satellite e connessione mobile);
- trasmissione di informazioni attraverso canali molto rumorosi (comunicazioni mobili, alta velocità linee di filo comunicazione);
- canali di comunicazione con maggiori requisiti di affidabilità delle informazioni ( reti di computer, linee di trasmissione con compressione dati).
In tutti i casi di cui sopra, vengono utilizzati codici di controllo degli errori.
Tenere conto modello più semplice trasmissione dei dati mediante 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 produce 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 del canale è di ottenere una corrispondenza tra quanto trasmesso parola d'informazione u e la parola informativa ricevuta u ′.
A partire dal di 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 consenta di riconoscere in modo efficiente e, in alcuni casi, correggere gli errori che si verificano quando le informazioni vengono trasmesse 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 le operazioni aritmetiche sono date modulo 2. Contiene un k -dimensionale spazio lineare contenente 2 k parole di 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 verifica in vista 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, in parola in codice c'era un singolo errore alla quarta posizione (r = (0010010)), quindi la quarta riga della matrice di controllo trasposta è la sindrome.
Dopo aver esaminato tutte le possibili posizioni di un singolo errore, otteniamo tabella completa sindromi di errore singolo - una tabella di corrispondenze del numero della cifra errata alla sindrome risultante.
| Scarico errato | r 0 | r 1 | r 2 | r 3 | r 4 | r 5 | r 6 |
|---|---|---|---|---|---|---|---|
| Sindrome s | 100 | 010 | 001 | 110 | 011 | 111 | 101 |
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:
- 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
- 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.
- 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. A scelta pratica di un codice correttore di errori specifico, è anche necessario tenere conto della velocità della sua decodifica e della complessità della sua implementazione tecnica.
Letteratura
- Werner M. Fondamenti di codifica. - M.: Tecnosfera, 2004.
- 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. Molto contento di essermi imbattuto questo materiale, mi sono chiarito una cosa.
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 costruire la 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.
Siano x1, x2, ..., xk una parola di k bit di informazione all'ingresso dell'encoder, codificata in una parola di codice C di dimensione n bit:
ingresso encoder: X=[X 1, X 2, ...,xk]
uscita encoder: C=[C 1, C 2, ..., cn]
Sia data una matrice generatrice speciale G n, k,
collocamento codice di blocco (n,K).
Righe matrice G n, k deve essere linearmente indipendente.
Quindi la combinazione di codici consentita è C corrispondente alla parola in codice X:
C=X 1 G 1 + X 2 G 2 + ... + x k g k.
La forma sistematica (canonica) della matrice generatrice G la dimensione K X n :
La matrice generativa di un codice sistematico crea un codice a blocchi lineare in cui il primo K i bit di qualsiasi parola di codice sono identici ai bit di informazione e il resto R=n-K i bit di qualsiasi parola in codice sono combinazioni lineari K bit di informazione.
Controlla matrice H n, k Esso ha R X n elementi, ed è vero:
C X H T = 0.
Questa espressione viene utilizzata per verificare il codice ricevuto. Se l'uguaglianza a zero non è soddisfatta, otteniamo la matrice riga || C 1 , C 2 , ..., c r|| chiamato sindrome di errore.
Codice Hamming. Capacità correttive e di rilevamento. Regole per la scelta della relazione tra la lunghezza della parola di codice e il numero di bit di informazione. Formazione delle matrici generatrici e di parità del codice di Hamming. Interpretazione della sindrome dell'errore
Considera un codice di Hamming con distanza di codice D= 3, che consente di correggere singoli errori ( D=2q max+1).
Il numero di combinazioni di codici consentite per un codice con D= 3, per il codice di Hamming è strettamente uguale a 2 n/(n+1). Il primo K bit di combinazioni di codice del codice vengono utilizzati come informazioni e il loro numero è uguale a
K= log 2 (2 n/(n+1)] = n- registro 2 ( n+1).
Questa equazione ha soluzioni intere K= 0, 1, 4, 11, 26, che determinano i corrispondenti codici di Hamming: (3,1) -codice, (7,4) -codice, (15,11) -codice, ecc. (sempre n=2w‑1).
Controlla matrice h Codice di Hamming ( R=n-k linee e n colonne): per un codice binario (n, k) n = 2 w -1 le colonne sono costituite da tutti i possibili vettori binari con r = n-k elementi, escludendo un vettore con tutti gli elementi zero.
È facile verificarlo G X H T= 0 (matrice di dimensione zero K X R elementi).
Esempio. Controlliamo il funzionamento del codice durante l'invio di un messaggio X= 1011. Il codice trasmesso sarà formato nella forma combinazione lineare(addizione modulo 2) righe n. 1, 3, 4 della matrice G 7,4:
Supponiamo che il codice trasmesso C l'errore 0000100 è stato interessato, che ha portato alla ricevuta su lato ricevente le parole C"=10111 10.
Quindi, moltiplicando C "per la matrice del controllo di parità H T otteniamo la matrice riga della sindrome di errore, che corrisponde a quella colonna della matrice di controllo h con il numero del bit contenente l'errore.
Confrontando la sindrome risultante con le stringhe h T, otteniamo che il bit n. 5 a sinistra è sbagliato.
Il decoder Hamming può funzionare in due si escludono a vicenda modalità:
Modalità di correzione degli errori (correzione) (da D min = 3, quindi permette di correggere i singoli errori);
Modalità di rilevamento degli errori (da D min = 3, quindi rileva gli errori di molteplicità Q£ 2). Se la sindrome non è uguale a 0, il decoder emette un segnale di errore.
Se ci sono 2 errori nel codice ricevuto e il decodificatore funziona in modalità di correzione, non sarà in grado di determinare dalla sindrome se si sono verificati uno o due errori ed eseguirà una correzione errata del codice.
Codice Hamming esteso. Modalità operative del decodificatore, capacità di correzione e rilevamento. Formazione di una parola in codice. Formazione della matrice di controllo di parità del codice di Hamming esteso. Interpretazione della sindrome dell'errore
L'estensione del codice di Hamming consiste nell'integrare i vettori di codice con un bit binario complementare in modo che il numero di quelli contenuti in ciascuna parola di codice sia pari. A causa di ciò, i codici di Hamming con controllo di parità hanno seguenti vantaggi:
Le lunghezze dei codici aumentano da 2 w da -1 a 2 w, conveniente dal punto di vista del trasferimento e dell'archiviazione delle informazioni;
Distanza minima D il minimo di codici Hamming estesi è 4, il che rende possibile rilevare (!) errori tripli.
Un ulteriore bit di parità consente di utilizzare il decoder in un nuovo modalità ibrida- rilevamento e correzione degli errori.
Consideriamo un'estensione del codice (7,4,3) di Hamming.
Ogni vettore di codice C a si ottiene da un vettore di codice c aggiungendo un bit di parità extra C un = ( C 1 , ..., C 7, C 8), dove.
Controlla matrice h Il codice (8,4) si ottiene dalla matrice di controllo di parità del codice (7,4) in due passaggi:
La colonna zero è aggiunta alla matrice (7,4) -code;
La matrice risultante è completata da una riga composta interamente da un'unità.
Noi abbiamo:
Con decodifica sindromica
S" = C"Ä h T,
inoltre, tutte le componenti di s "devono essere uguali a 0.
Con un solo errore s "(4) = 1. Per il valore della sindrome (3 bit meno significativi), troviamo e correggiamo (invertire) il bit errato.
A doppio errore componente s "(4) = 0, e la sindrome è diversa da zero. Diversamente codice standard La situazione di Hamming è già stato scoperto, ma non viene corretto (viene inviata una richiesta di ritrasmissione di una parola, ecc.).
Pertanto, il decodificatore Hamming esteso può essere utilizzato in una delle due modalità che si escludono a vicenda:
Per correggere errori singoli e doppi;
Per rilevare errori tripli.
