Un codice ciclico è un codice lineare, ovvero un insieme finito chiuso rispetto all'operazione di spostamento ciclico dei vettori di codice che lo compongono. Lascia che sia dato n vettore dimensionale v = un 0 un 1 …un-1 con coordinate dal campo di destinazione F. Il suo spostamento ciclico è chiamato vettore v"= un n-1 a 0 a 1 ... un -2 .

Ritenere n spazio aritmetico bidimensionale su un campo di Galois GF(2). Ogni vettore un 0 un 1 …un-1 di GF(2) si può associare un polinomio biunivoco un 0 +un 1 X+…+un -1 x n-1 con coefficienti da GF(2). La somma di due vettori un 0 un 1 …un-1 e b 0 b 1 …b n-1 corrisponde alla somma dei polinomi ad essi corrispondenti, al prodotto degli elementi del campo per il vettore - il prodotto del polinomio corrispondente a questo vettore per l'elemento.

Considera un polinomio g(X) dallo spazio lineare descritto. L'insieme di tutti i polinomi di questo sottospazio che sono divisibili senza resto per g(X) forma un sottospazio lineare. Un sottospazio lineare definisce un codice lineare.

Codice lineare formato da una classe di polinomi C(g(X)), multipli di un polinomio g(X), detto polinomio generatore, si dice polinomio.

Mostriamo come sono correlati i codici polinomiali C(g(X)) e codici ciclici. Permettere un = un 0 …un-1 è una parola in codice e il corrispondente polinomio in codice un(X) = un 0 +...+un -1 x n-uno . spostamento ciclico un" corrisponde al polinomio di codice un"(X) = un -1 +un 0 X+…+un -2 X n -1 , che può essere espresso in termini dell'originale:

Poiché il codice polinomiale deve essere divisibile per g(X), quindi affinché sia ​​ciclico, il polinomio un"(X) deve essere divisibile per g(X). Da questa considerazione possiamo formulare il seguente teorema. Un codice polinomiale è ciclico se e solo se il polinomio g(X) è un divisore del polinomio x n-uno. In questo caso il polinomio g(X) è detto polinomio generatore di un codice ciclico.

Nella teoria dei codici si dimostra il seguente teorema: se un polinomio g(X) ha una laurea n–K ed è un divisore x n-1, quindi C(g(X)) è ciclico lineare ( n, K)-codice.

Polinomio x n-1 fattorizzare x n–1 = (X–1)(x n -1 +x n-1+…+1). Pertanto, esistono codici ciclici per qualsiasi n. Numero di ciclico n codici a -bit è uguale al numero di divisori del polinomio x n-uno. Per costruire codici ciclici sono state sviluppate tabelle di scomposizione di polinomi x n-1 per polinomi irriducibili, cioè divisibili solo per 1 e per se stesso.

Considera, ad esempio, quali codici possono essere costruiti in base al polinomio X 7-1 sul campo GF(2). La scomposizione di un polinomio in fattori irriducibili ha la forma

Poiché è possibile formare sei divisori del polinomio X 7-1, combinando divisori irriducibili, ci sono sei codici ciclici binari. ( n, K)-code è determinato, in primo luogo, dal valore n, e in secondo luogo, il valore K = n – S, Sè il grado del polinomio divisore x n-1 che definisce il codice. Di seguito sono riportati i divisori del polinomio e i loro valori corrispondenti K:

X – 1, S=1, K=6;

X 3 +x 2 +1, S=3, K=4;

X 3 +x+1, S=3, K=4;

(X–1)(X 3 +x 2 +1)=X 4+x2+x+1, S=4, K=3;

(X–1)(X 3 +x+1)=X 4+x3+x2+1, S=4, K=3;

(X 3 +x 2 +1)(X 3 +x+1)=X 6 +X 5 +X 4 +X 3 +X 2 +X, S=6, K=1.

Il codice (7, 6) ha un solo simbolo di spunta e il codice (7, 1) ha un solo simbolo di informazione. Sono, rispettivamente, un codice di controllo della parità e un codice di ripetizione.

Come un normale codice lineare, un codice ciclico può essere dato da una matrice generatrice. Pertanto, il compito è trovare una tale matrice, cioè trovare K combinazioni di codici linearmente indipendenti che lo compongono. Per questo usiamo la proprietà della chiusura di un codice ciclico rispetto all'operazione di uno spostamento ciclico. Si noti che uno spostamento ciclico a destra di una cifra equivale a moltiplicare il polinomio g(X) sul X. Allora la matrice generatrice può essere costruita prendendo come righe il polinomio generatore and K i suoi spostamenti ciclici:

Consideriamo ora come, utilizzando il polinomio generatore g(X) = 1+X+X 3 è codificato dal codice (7, 4). Prendiamo, ad esempio, una parola di 4 bit (0101), che corrisponde al polinomio f(X) = X + X 3 . Moltiplicando questi due polinomi

I codici ciclici sono una sorta di codici di gruppo lineari e appartengono a codici sistematici. Sono stati originariamente creati per semplificare la procedura di decodifica. Tuttavia, l'elevata efficienza di rilevamento degli errori di tali codici ha assicurato la loro ampia applicazione nella pratica. È conveniente considerare un vettore binario di un codice ciclico non come una combinazione di zeri e uno, ma come un polinomio di un certo grado

dove x è la base del sistema numerico, i coefficienti appartenenti all'insieme nel caso del sistema numerico binario.

Esempio. Un vettore binario può essere rappresentato come un polinomio come segue:

La rappresentazione dei vettori binari come polinomi permette di ridurre l'operazione sui vettori alle operazioni sui polinomi. In cui:

l'addizione di polinomi si riduce alla somma modulo 2 dei coefficienti a pari potenza della variabile

la moltiplicazione viene eseguita secondo la consueta regola di moltiplicazione delle funzioni di potenza, tuttavia i coefficienti ottenuti a un dato grado vengono aggiunti modulo 2;

la divisione è effettuata secondo le regole della divisione delle funzioni potenza, mentre l'operazione di sottrazione è sostituita dalla sommatoria modulo 2.

Esempio. Trova la somma dei polinomi

Trova il prodotto di polinomi

Eseguire la divisione polinomiale

La proprietà principale dei codici ciclici è la seguente: se un vettore appartiene a un codice ciclico, allora anche qualsiasi vettore ottenuto da quello in esame con l'ausilio di spostamenti ciclici appartiene al codice ciclico.

L'idea di costruire codici ciclici si basa sul concetto di polinomio irriducibile. Un polinomio si dice irriducibile se è divisibile solo per se stesso e per 1, e non è divisibile per nessun altro polinomio. In altre parole, un polinomio irriducibile non può essere rappresentato come prodotto di polinomi di grado inferiore. Un polinomio irriducibile divide un polinomio senza resto. I polinomi irriducibili svolgono il ruolo di generare polinomi nella teoria dei codici ciclici. Sono riportati i tipi di polinomi irriducibili di vari gradi

Esempi di polinomi irriducibili:

I vettori di codice ciclico sono costruiti secondo le seguenti regole. Sia qualsiasi vettore binario di qualche codice naturale; - grado monomio irriducibile grado polinomiale Quindi qualsiasi vettore di un codice ciclico è formato usando la relazione

dove è il resto della divisione

Pertanto, qualsiasi vettore di un codice ciclico può essere formato moltiplicando un vettore di naturale codice binario di un monomio di grado con l'aggiunta del resto della divisione al prodotto risultante Quando si costruiscono codici ciclici in questo modo, la posizione dei bit di informazione in ciascun vettore di codice è rigorosamente ordinata: occupano i bit più alti del vettore di codice, e i bit rimanenti sono bit di controllo.

Esempio. Il vettore di codice binario naturale ha la forma

Rappresentiamo il vettore come un polinomio

Come risultato della divisione di un polinomio per un polinomio, otteniamo il resto. Ecco perchè

Un codice ciclico, come qualsiasi codice sistematico, può essere opportunamente specificato in forma matriciale utilizzando una matrice generatrice della forma

dove è l'unità trasposta yatrix del formato - la matrice dei bit di parità formata dal resto della divisione

Impostiamo la matrice generatrice del codice ciclico con la lunghezza dei bit di informazione e il polinomio generatore.

Ovviamente, lo spazio vuoto per la matrice generatrice ha la forma

Per trovare le righe di bit di controllo della matrice, calcoliamo e scriviamo sotto forma di polinomio ogni vettore della matrice identità

La lunghezza del vettore di codice ciclico è quindi

(vedi scansione)

Di conseguenza, otteniamo la matrice generatrice C:

Qualsiasi vettore di un codice ciclico è ottenuto come somma modulo dei vettori della sua matrice generatrice. Poiché il codice ciclico è un codice di gruppo, il vettore zero è sempre assegnato al codice ciclico come elemento di identità del gruppo.

Tabella 13.5

Esempio. Costruisci tutti i vettori del codice ciclico dato dalla matrice generatrice

Il codice è presentato in tabella. 13.5.

Si noti che ogni codice ciclico dato da una certa matrice generatrice può essere rappresentato in più versioni, differenti tra loro per lunghezza e numero di bit di informazione (a parità di capacità di rilevazione). Queste versioni dei cosiddetti codici ciclici abbreviati si ottengono cancellando le ultime righe e altrettante colonne a sinistra nella matrice generatrice del codice ciclico. In questo caso, il numero di cifre di controllo rimane invariato e la lunghezza del codice e il numero delle sue cifre informative vengono ridotte, rispettivamente, di un importo pari al numero di righe e colonne barrate della matrice generatrice.

Esempio, Un codice ciclico è dato dalla sua matrice generatrice

Cancelliamo le ultime sei righe e le prime sei colonne da sinistra. Otteniamo la matrice generatrice

Le caratteristiche (in termini di rilevamento degli errori) del codice risultante sono le stesse del codice ciclico rappresentato dalla matrice del generatore

Costruzione di codici ciclici con parametri datiè legato alla scelta del generatore del polinomio irriducibile. Il polinomio generatore viene selezionato in base alla seguente condizione: il grado del polinomio deve essere uguale al numero di bit di controllo del codice ciclico.

In pratica si pone spesso il problema di costruire un codice ciclico di una data potenza e di una data capacità rilevativa e correttiva.

1. Poiché viene data la potenza del codice ciclico, il numero dei suoi bit di informazione viene determinato secondo la formula

2. Il numero ottimale di cifre di controllo del codice ciclico è determinato da tabelle speciali.

3. Secondo le directory, vengono trovati tutti i polinomi di grado irriducibili

4. Per uno dei polinomi non conduttivi (si dovrebbe scegliere un polinomio con il numero massimo di termini) di grado, si costruisce una matrice generatrice di un codice ciclico. Ogni vettore di codice è calcolato dalla formula

dove è il polinomio del vettore di informazioni della matrice generatrice; - monomio di grado - resto della divisione

5. La matrice generatrice costruita viene verificata per le seguenti condizioni:

a) il peso nel senso di Hamming di un qualsiasi vettore della matrice generatrice deve soddisfare la relazione dove è la distanza minima, nel senso di Hamming, del codice ciclico considerato;

b) il peso nel senso di Hamming del vettore di controllo, che è la somma modulo 2 di due vettori di controllo qualsiasi della matrice generatrice, deve soddisfare la relazione

6. Se la matrice generatrice del codice ciclico soddisfa tutte le condizioni di cui sopra, tutti i vettori del codice ciclico vengono scritti e determinati secondo le regole note per i codici di gruppo lineari. Se il codice non soddisfa i requisiti, viene scelto un altro polinomio generatore dello stesso grado e la procedura per generare un codice ciclico viene ripetuta per un nuovo polinomio.

Costruiamo un codice ciclico con una potenza di 16 e un codice correttivo con la capacità

Per determinare il valore di

3 "Dai libri di riferimento troviamo tutti i polinomi irriducibili di grado Esistono due di questi polinomi:

4. Scegliamo come polinomio generatore Lo spazio vuoto della matrice generatrice del codice ciclico ha la forma

Ogni vettore di informazioni dalla matrice è rappresentato da un polinomio

Determiniamo completamente tutti i vettori della matrice generatrice usando la formula

Poiché la lunghezza del vettore del codice ciclico (vedi il formato della matrice generatrice, quindi

Allo stesso modo, troviamo tutti gli altri vettori della matrice generatrice

Tabella 13.6

Il risultato è una matrice generatrice C? codice ciclico

5. La matrice generatrice risultante soddisfa tutte le condizioni necessarie. Pertanto, costruiamo un codice ciclico completamente (Tabella 13.6). Come risulta dalla tabella, il codice ha, cioè soddisfa i requisiti dell'attività.

Osservazioni. Quando si utilizza un polinomio irriducibile come generatore, si ottiene un codice che soddisfa anche i requisiti del problema. La sua matrice generatrice ha la forma

Il rilevamento degli errori mediante codici ciclici viene eseguito come segue. Qualsiasi vettore di un codice ciclico è divisibile per un polinomio generatore senza resto. Pertanto, il criterio per la presenza di un errore nel vettore del codice ciclico è la comparsa di un resto diverso da zero dalla divisione del vettore del codice ciclico per il polinomio generatore. Il resto diverso da zero è l'identità dell'errore nel vettore del codice ciclico, ma il suo aspetto non indica la posizione dell'errore nel vettore del codice. La correzione degli errori si basa sul seguente algoritmo:

1. Dividere il vettore di codice ricevuto in un polinomio generatore.

Se il numero di unità non supera la capacità correttiva del codice, aggiungere il vettore ricevuto modulo 2 con il resto risultante. Il risultato della somma darà il vettore di codice corretto. Se il numero di unità del resto è maggiore della capacità correttiva del codice, eseguire uno spostamento ciclico del vettore distorto a sinistra di un bit, quindi dividere per un polinomio generatore. Se il resto ricevuto contiene unità non superiori alla capacità correttiva del codice ciclico, sommare il vettore spostato ciclicamente con il resto. Il risultato della sommatoria viene spostato ciclicamente di una cifra a destra. Il vettore risultante non contiene più errori ed è un vettore di codice ciclico.

3. Se, dopo il primo shift ciclico e la successiva divisione, il resto contiene più unità della capacità correttiva del codice, allora ripetere la procedura dell'algoritmo fino a ottenere un resto con un numero di unità non superiore alla capacità correttiva del codice ottenuto. In questo caso, il risultato dell'ultimo spostamento ciclico viene sommato con il resto e il vettore risultante viene spostato ciclicamente a destra di tanti bit quanti sono stati spostati a sinistra il vettore originale ricevuto con un errore. Il risultato è un vettore di codice corretto.

Sia dato il codice ciclico dalla sua matrice generatrice С e dal polinomio generatore , dove

Il codice ha un valore di 3, cioè corregge gli errori di molteplicità Lascia che venga preso il vettore 0011101 invece del vettore 0001101. Per correggere l'errore, eseguiamo le seguenti azioni. Scriviamo il vettore ricevuto come un polinomio: quindi dividiamo per

Il resto ottenuto come risultato della divisione contiene tre unità, che è più della capacità correttiva del codice. Pertanto, effettuiamo uno spostamento ciclico a sinistra di un bit del vettore di codice ricevuto. Di conseguenza, abbiamo

Dividiamo per

Il resto risultante contiene due unità, che è più della capacità correttiva del codice. Pertanto, eseguiamo un altro spostamento ciclico a sinistra di un bit del vettore di codice ricevuto. Di conseguenza, abbiamo

Dividiamo per

Il resto risultante contiene di nuovo due unità, quindi facciamo un altro spostamento ciclico a sinistra di un bit e otteniamo Dividi per

Una classe di codici lineari, che sono chiamati codici cinesi. Il nome deriva dalla proprietà principale di questi codici: se qualche combinazione di codice appartiene a un codice ciclico, allora anche la combinazione ottenuta dalla permutazione ciclica della combinazione originale (spostamento ciclico) appartiene a questo codice:

La seconda proprietà di tutte le combinazioni consentite di codici ciclici è la loro divisibilità senza resto per un polinomio selezionato, chiamato generatore.

Queste proprietà vengono utilizzate nella costruzione di codici codificatore e decodificatore, nonché nel rilevamento e nella correzione degli errori.

I codici ciclici sono un'intera famiglia di codici di correzione degli errori (una delle varietà dei quali sono i codici di Hamming), che offre una grande flessibilità in termini di possibilità di implementare codici con la capacità necessaria per rilevare e correggere gli errori che si verificano durante la trasmissione di combinazioni di codici su un canale di comunicazione. Il codice ciclico si riferisce a codici a blocchi sistematici (n, &), in cui a i primi bit sono una combinazione del codice primario e il successivo (l - a) le cifre sono test.

La costruzione dei codici ciclici si basa sull'operazione di dividere la combinazione di codice trasmessa per il polinomio irriducibile di grado che genera G. Il resto della divisione viene utilizzato nella formazione dei bit di controllo. In questo caso, l'operazione di divisione è preceduta dall'operazione di moltiplicazione, che sposta a sinistra la combinazione del codice informativo ^-bit di G scarichi.

Quando si decodifica la combinazione di codice n bit ricevuta, viene nuovamente eseguita la divisione in un polinomio generatore (produttore, formato).

La sindrome dell'errore in questi codici è la presenza del resto dalla divisione della combinazione di codice ricevuta per il polinomio generatore. Se la sindrome è zero, si considera che non ci siano errori. Altrimenti, utilizzando la sindrome ricevuta, è possibile determinare il numero di bit della combinazione di codice ricevuta in cui si è verificato un errore e correggerlo.

Tuttavia, non è esclusa la possibilità di errori multipli nelle combinazioni di codici, che possono portare a false correzioni e (o) al mancato rilevamento di errori durante la trasformazione di una combinazione consentita in un'altra.

Sia i il numero totale di bit nel blocco, di cui informazioni utili trasportare t bit, quindi in caso di errore è possibile correggere j bit. Dipendenza 5 su P e t per i codici può essere determinato dalla tabella. 2.6.

Tabella 2.6

Dipendenza del numero totale di cifre delle combinazioni dal numero di informazioni e cifre correggibili

Aumentare la differenza (n-t),è possibile non solo aumentare il numero di bit correggibili S, ma anche per rilevare più errori. Le percentuali di errori multipli rilevati sono riportate in Tabella. 2.7.

Tabella 2.7

Percentuale di più errori rilevati

È conveniente descrivere codici ciclici e costruirli utilizzando polinomi (o polinomi). Il record di combinazione come polinomio viene utilizzato per visualizzare in modo formalizzato l'operazione di spostamento ciclico della combinazione di codice originale. Quindi, la parola in codice "-elemento può essere descritta dal polinomio (P- 1) laurea:

dovea„_j =(0, 1), eun „_, =0 corrisponde a zero elementi della combinazione, d„_, = 1 - diverso da zero;io- il numero della cifra della combinazione di codice.

Presentiamo i polinomi per specifiche combinazioni di 4 elementi:

Le operazioni di addizione e sottrazione sono equivalenti e associative e vengono eseguite modulo 2:

Esempi di operazioni:

L'operazione di divisione è la solita divisione di polinomi, ma al posto della sottrazione viene utilizzata l'addizione modulo 2:

Lo spostamento ciclico di una combinazione di codice è il movimento dei suoi elementi da destra a sinistra senza disturbarne l'ordine, in modo che l'elemento più a sinistra prenda il posto di quello più a destra.

Le proprietà principali e il nome dei codici ciclici sono legati al fatto che tutte le combinazioni consentite di bit nel messaggio trasmesso (parole di codice) possono essere ottenute mediante l'operazione di spostamento ciclico di alcune parole di codice sorgente.

Diciamo che la combinazione di codice iniziale e il polinomio corrispondente sono dati:

Moltiplichiamo Oh) sul X:

Dal massimo grado X in una combinazione di codici di lunghezza P non supera (n - 1), quindi dal lato destro dell'espressione risultante per ottenere il polinomio originale, è necessario sottrarre Oh"- uno). Sottrazione Oh"- 1) si dice prendendo il resto modulo (x pag - 1).

Lo spostamento della combinazione originale di / misure può essere rappresentato come segue: ascia)? U- Oh"- 1), cioè moltiplicazione Oh) nah" e prendendo il resto modulo (x" - 1). Prendere il resto è necessario quando si ottiene un polinomio di grado maggiore o uguale a P.

L'idea di costruire codici ciclici si basa sull'uso polinomi irriducibili. Un polinomio irriducibile è un polinomio che non può essere rappresentato come prodotto di polinomi di grado inferiore, cioè è divisibile solo per se stesso o per 1 e non divisibile per nessun altro polinomio. Un binomio (x" + 1) è divisibile per un tale polinomio senza resto. I polinomi irriducibili nella teoria dei codici ciclici svolgono il ruolo di generare polinomi.

Tornando alla definizione di codice ciclico e tenendo conto della notazione delle operazioni di spostamento ciclico delle combinazioni di codice, possiamo scrivere la matrice generatrice di un codice ciclico nella seguente forma:

doveP(x)- la combinazione di codice originaria, in base alla quale si ottengono tutte le altre(t- 1) combinazioni di base;

C, = 0 oCg =1 ("O" se il grado risultante del polinomioP(x)-x'non supera (l - 1), o "1" - se supera).

Combinazione P(x)è chiamata combinazione generatrice (generatore). Per costruire un codice ciclico è sufficiente scegliere correttamente P(x). Quindi tutte le altre combinazioni di codici sono le stesse del codice di gruppo.

Il polinomio generatore deve soddisfare i seguenti requisiti:

• P(x) deve essere diverso da zero;
• il peso P(x) non deve essere inferiore alla distanza minima del codice: V(P(x)) > d mm ;
• P(x) avrebbe dovuto grado massimo k (k- il numero di elementi ridondanti nel codice);
• P(x) deve essere un divisore del polinomio (x" - 1).

L'adempimento dell'ultima condizione porta al fatto che tutte le combinazioni di codici di lavoro del codice ciclico acquisiscono la proprietà di divisibilità per P(x) senza traccia. Con questo in mente, si può dare un'altra definizione di codice ciclico: un codice ciclico è un codice le cui combinazioni di lavoro sono divisibili per un polinomio generatore senza resto.

Per determinare il grado del polinomio generatore, è possibile utilizzare l'espressione r > log 2 (e + 1), dove P- la dimensione del pacchetto trasmesso alla volta, ad es. la lunghezza del codice ciclico che si sta costruendo.

Esempi di generazione di polinomi sono riportati in Tabella. 2.8.

Tabella 2.8

Esempi di generazione di polinomi

L'algoritmo per ottenere una combinazione di codice consentita di un codice ciclico da una combinazione di un codice semplice è il seguente.

Sia dato il polinomio P (x) \u003d a g _ ( x g + a g _ 2 x r ~ 1 + ... + 1, che determina la capacità correttiva del codice e il numero di cifre di controllo a, così come la combinazione originale di un semplice codice da elemento e bit di informazioni sotto forma di un polinomio A t (x).

È necessario determinare la combinazione di codici consentita del codice ciclico (e, a).

• 1. Rappresentiamo la combinazione di codice originale come un polinomio A t (x). Moltiplichiamo il polinomio della combinazione di codice originale per x z: A t (x) x g. Grado del polinomio generatore G pari al valore della cifra più significativa della combinazione di codice originaria.
• 2. Determiniamo i bit di controllo che integrano la combinazione di informazioni originaria a quella consentita, come il resto della divisione del prodotto ottenuto nel paragrafo precedente dalla generazione

polinomio:

Il resto della divisione è indicato come R(x).

3. La parola in codice finalmente consentita del ciclico

codice è definito come = E t (x)? x r + R(x).

Per determinare gli errori nella combinazione di codice ricevuta, è sufficiente dividerla in un polinomio generatore. Se la combinazione accettata è consentita, il resto della divisione sarà zero. Un resto diverso da zero indica che la combinazione ricevuta contiene errori. A seconda del tipo di residuo (sindrome), in alcuni casi è anche possibile trarre una conclusione sulla natura dell'errore e sulla sua localizzazione e correggere l'errore.

L'algoritmo di rilevamento degli errori è il seguente.

Lasciate "combinazioni di elementi ( n = k+t).

• 1. Riveliamo il fatto della presenza di un errore. Otteniamo il resto dividendo la combinazione accettata A n - (x) al polinomio generatore P(x): A(X)
• --- = Rq(x). Presenza di un equilibrio R0(x) a (L 0 (x) f 0) testimonia P(x)

su un errore.

2. Dividi il polinomio risultante # (x) \u003d L„_,(X) 0 Rq (x) sulla generatrice Rg(h): W-1 = R(x), dove R(x)- bilancio corrente.

3. Confronta LDx) e R(x). Se sono uguali, l'errore si è verificato nel bit più significativo. In caso contrario, aumentare di x il grado del polinomio accettato e dividere nuovamente:

4. Confronta il resto risultante con Rq(x). Se sono uguali, l'errore si è verificato nel secondo bit. Se non sono uguali, moltiplica Wx) x 2 e ripetere queste operazioni finché non otteniamo

R(x) = inferno.

L'errore sarà nella categoria corrispondente al numero di cui il grado è aumentato Wh), più 1. Ad esempio, nel caso dell'uguaglianza R(x) e LDh)

Il codice ciclico più semplice c consente di rilevare errori singoli ed errori di molteplicità dispari. Il polinomio generatore di questo codice ha la forma Tra i polinomi irriducibili inclusi nella decomposizione, questo polinomio è il polinomio di grado minore, quindi per qualsiasi numero di bit di informazione è necessario un solo bit di controllo. Il valore simbolico di questo bit garantisce la parità del numero di uno in qualsiasi parola di codice consentita. Il codice di parità ciclica risultante è in grado di rilevare non solo errori di bit singoli, ma anche errori in qualsiasi numero dispari di bit.

Esempio. Costruire un codice ciclico per Poiché il polinomio generatore è un polinomio di 1° grado, il numero di cifre di controllo Pertanto, per costruire un codice ciclico, costruiamo una matrice generatrice

Per costruire una matrice aggiuntiva, troviamo i resti della divisione dell'ultima riga della matrice trasposta unitaria, riempita di zeri, per il polinomio selezionato:

Pertanto, la matrice aggiuntiva C, k ha la forma

Ora costruiamo la matrice generatrice

Le righe di questa matrice sono le prime tre combinazioni del codice. Il resto delle combinazioni consentite può essere ottenuto dalla somma modulo due di tutte le possibili combinazioni di righe di matrice.Le combinazioni di codici distrutti risultanti sono riportate in Tabella. 39.

Tabella 39 (vedi scansione)

Di noto interesse è la considerazione del seguente codice semplicissimo formato con l'ausilio di un polinomio irriducibile di secondo grado

La vista generale della matrice generatrice del codice ciclico formato dal polinomio differisce nella struttura della matrice aggiuntiva a due colonne.

È facile vedere che, dividendo per un dato polinomio generatore, i monomi che esprimono le stringhe

matrice identità (per trovare una matrice aggiuntiva, si formano tre tipi di residui: 11, 01 e 10. Pertanto, il peso di ciascuna combinazione del codice risultante sarà almeno due. Anche la distanza minima del codice tra due combinazioni qualsiasi è uguale a 2. Ma il codice più semplice con un controllo di parità formato da un binomio di primo grado Tuttavia, la capacità correttiva di entrambi i codici non è la stessa.Il codice in esame ha una grande ridondanza e consente di rilevare non solo eventuali errori di molteplicità dispari, ma anche eventuali errori adiacenti accoppiati, nonché tutti gli errori separati da un elemento non distorto.

6. Correzione degli errori con codici ciclici

Nella Sezione 3 è stato mostrato che per decodificare una parola di codice correttamente ricevuta, cioè per trovare la corrispondente parola di informazione, è sufficiente dividere il polinomio corrispondente alla parola di codice ricevuta per il polinomio generatore del codice. Tuttavia, se si verificano errori durante la trasmissione, questi errori devono essere corretti durante il processo di decodifica.

Poiché i codici ciclici sono lineari, il processo di rilevamento e correzione degli errori è correlato alla ricerca della sindrome del vettore ricevuto. Ricordiamo che la sindrome del vettore tuè calcolato come il prodotto del vettore e la matrice di controllo trasposta del codice, cioè tu= uH T. Nel caso di un codice ciclico, la sindrome è uguale al resto della divisione del polinomio corrispondente per il polinomio generatore del codice, se la matrice di controllo è costruita in un certo modo. In altre parole, se g(X) è un polinomio di codice generatore, quindi la sindrome del vettore tu pari al resto della divisione tu(X) sul g(X). Se non ci sono stati errori, il resto, e quindi la sindrome del vettore ricevuto, è 0.

Per correggere gli errori, dobbiamo costruire una tabella in cui in una colonna ci saranno tutti i possibili vettori di errore che dato codice può correggere, e nella seconda colonna - le sindromi corrispondenti a loro. La correzione degli errori comune a tutti i codici di linea sarà la seguente:

1. Per la parola ricevuta, troviamo la sindrome polinomiale corrispondente alla parola ricevuta.

2. Se la sindrome non è uguale a 0, allora dalla sindrome ottenuta (resto dalla divisione) troviamo nella tabella il corrispondente vettore di errore.

3. Correggiamo la parola ricevuta aggiungendo modulo 2 con il vettore di errore calcolato.

Il primo passo, che si esegue moltiplicando la parola ricevuta per la matrice di controllo trasposta, è molto semplice per i codici ciclici se la matrice Hè la matrice di controllo del codice sistematico. In questo caso, j-esima riga della matrice trasposta HT corrisponde al resto della divisione del polinomio x n -1- j dal polinomio generatore del codice, e la sindrome è uguale al resto della divisione del polinomio corrispondente alla parola ricevuta per il polinomio generatore del codice.

Esempio: Considera il codice ciclico (7,1) generato dal polinomio g(X) = X 6 + X 5 + X 4 + X 3 + X 2 + X+1. Il codice è composto da due parole 0000000 e 1111111 e corregge tutte le combinazioni di 3 o meno errori. I generatori sono tutti vettori booleani di lunghezza 7 di peso 0, 1, 2 e 3. La matrice di controllo è costruita utilizzando il quoziente ( X+1) dalla divisione X 7+1 su X 6 + X 5 + X 4 + X 3 + X 2 + X+1 e sembra

Sia accettata la parola 11101101, che corrisponde al polinomio X 6 + X 5 + X 4 + X 2 + 1. Il resto dopo aver diviso questo polinomio per il polinomio del codice generatore è X 3 + X. Mediante verifica diretta, ci si può assicurare che quando si moltiplica il vettore tu= 1110101 per matrice trasposta HT, così come quando si moltiplica il vettore 0001010 per HT si ottiene il vettore 0001010, che corrisponde al polinomio X 3 + X. Il vettore corrispondente al polinomio X 3 + X, ha peso 2, cioè è un generatore del coset. Aggiungendo il vettore ricevuto 11101101 con il generatore 0001010, otteniamo la parola di codice 1111111, ovvero l'errore verrà corretto.

Per i codici lineari, il numero di diverse sindromi è 2 n - K, dove n-K- numero di caratteri di controllo. Pertanto, per i codici con una grande lunghezza di codeword, cioè con abbastanza un largo numero controlla i simboli, la tabella delle sindromi risulta essere molto grande e ci vorrà molto tempo per trovare il vettore di errore. Per ridurre il numero di righe in questa tabella per i codici ciclici, è possibile utilizzare la rigorosa struttura matematica di tali codici. Il teorema principale è il teorema di Megitt, che stabilisce una connessione tra gli spostamenti ciclici di un vettore ei loro resti dopo la divisione per il polinomio generatore del codice.

Teorema 6.1. (Meggit). Permettere S- sindrome del vettore tu lunghezza n. Sindrome da spostamento vettoriale ciclico tu coincide con la sindrome del vettore corrispondente al polinomio xs(X).

Esempio: Si consideri il codice di Hamming (7,4), che è il codice ciclico generato dal polinomio g(X) = X 3 + X+ 1. Il vettore binario 1011000 è una parola in codice, poiché il corrispondente polinomio X 6 + X 4 + X 3 è divisibile per g(X). Supponiamo che durante la trasmissione di questa parola di codice ci sia stato un errore nel bit corrispondente a X 4, e la parola è accettata tu= 1001000. Sindrome S del vettore ricevuto è 110, che corrisponde al polinomio X 2 + X.

Considera uno spostamento ciclico 0010001 del vettore tu. Corrisponde al polinomio X 4 + 1. Mediante verifica diretta, si può verificare che il resto della divisione del polinomio X 4 + 1 per polinomio X 3 + X+ 1 uguale X 2 + X+ 1, cioè la sindrome del vettore 0010001 è 111. Il resto della divisione del polinomio xs(X) = X 3 + X 2 su X 3 + X+ 1 è anche uguale X 2 + X + 1.

Usando il teorema di Megitt, solo le sindromi del vettore di errore corrispondenti agli errori nel bit più significativo possono essere memorizzate nella tabella delle sindromi. La procedura di correzione degli errori contiene i seguenti passaggi:

1. Troviamo la sindrome del vettore ricevuto dividendo il polinomio corrispondente per il polinomio del codice generatore. Se il resto della divisione contenuta nel registro è 0, allora non ci sono stati errori e il quoziente della divisione è la parola informativa richiesta. Altrimenti confrontiamo il resto della divisione con tutte le sindromi contenute nella tabella.

2. Se il resto coincide con una delle sindromi della tabella, allora aggiungiamo il corrispondente vettore di errore alla parola ricevuta, dividiamo la parola risultante per il polinomio generatore del codice; il quoziente della divisione è la parola informativa desiderata. Se il resto xs(X) non corrisponde a nessuna delle sindromi nella tabella, moltiplicare S(X) sul X e dividi il polinomio xs(X) al polinomio generatore del codice.

3. Eseguire il passaggio 2 fino a dopo p il resto dei passaggi non corrisponde a una delle sindromi nella tabella. Successivamente, spostiamo ciclicamente il vettore di errore corrispondente p volte, aggiungi il vettore risultante alla parola ricevuta, dividi la parola risultante per il polinomio generatore del codice; il quoziente della divisione è la parola informativa desiderata.

Esempio: Si consideri il codice di Hamming ciclico (7,4) generato dal polinomio g(X) = X 3 + X+ 1. La tabella di decodifica corrispondente con le sindromi è la seguente.

e si supponga che si sia verificato un errore nella parola di codice trasmessa 0001011, cioè che sia stata ricevuta, ad esempio, la parola 0101011 a cui corrisponde il polinomio X 5 + X 3 + X+ 1. Il resto della divisione del polinomio X 5 + X 3 + X+ 1 per polinomio di codice generatore g(X) = X 3 + X+ 1 uguale X 2 + X+ 1, cioè la sindrome del vettore ricevuto è diversa da 0 ed è uguale a 111. Non esiste tale sindrome nella tabella e quindi non ci sono errori nel bit più significativo. Moltiplicazione di un polinomio X 2 + X+ 1, corrispondente alla sindrome 111, on X e dividere il polinomio risultante X 3 + X 2 + X sul g(X). Resto della divisione di un polinomio X 3 + X 2 + X sul X 3 + X+ 1 uguale X 2 + 1, cioè la sindrome 101, corrispondente al resto, corrisponde alla sindrome nella tabella di decodifica ridotta. Di conseguenza, il generatore 100000 della classe adiacente viene spostato di un bit a sinistra e il vettore ricevuto 0100000 viene aggiunto al vettore ricevuto 0101011. Come risultato, si ottiene la parola 0001011, che è la parola di codice trasmessa, cioè l'errore sarà corretto.

È possibile semplificare questo decodificatore. In particolare, quando una parola ricevuta viene ruotata, molti degli schemi di errore correggibili possono verificarsi più volte. Se una di queste sindromi viene rimossa, con il corrispondente spostamento ciclico, l'errore verrà comunque rilevato. Pertanto, per ciascuna di queste coppie, è sufficiente memorizzare solo una sindrome.