Codice BCH - BCH code

Nella teoria della codifica , i codici BCH o codici Bose-Chaudhuri-Hocquenghem formano una classe di codici correttivi ciclici che sono costruiti utilizzando polinomi su un campo finito (chiamato anche campo di Galois ). I codici BCH sono stati inventati nel 1959 dal matematico francese Alexis Hocquenghem , e indipendentemente nel 1960 da Raj Bose e DK Ray-Chaudhuri . Il nome Bose–Chaudhuri–Hocquenghem (e l'acronimo BCH ) deriva dalle iniziali dei cognomi degli inventori (erroneamente, nel caso di Ray-Chaudhuri).

Una delle caratteristiche chiave dei codici BCH è che durante la progettazione del codice, c'è un controllo preciso sul numero di errori di simbolo correggibili dal codice. In particolare, è possibile progettare codici BCH binari in grado di correggere errori multipli di bit. Un altro vantaggio dei codici BCH è la facilità con cui possono essere decodificati, ovvero tramite un metodo algebrico noto come decodifica della sindrome . Ciò semplifica la progettazione del decodificatore per questi codici, utilizzando un piccolo hardware elettronico a bassa potenza.

I codici BCH sono utilizzati in applicazioni quali comunicazioni satellitari, lettori di compact disc , DVD , unità disco , unità a stato solido , crittografia resistente ai quanti e codici a barre bidimensionali .

Definizione e illustrazione

Codici BCH primitivi a senso stretto

Dato un numero primo q e una potenza prima q ^m con interi positivi m e d tali che d ≤ q ^m − 1 , un codice BCH primitivo di senso stretto sul campo finito (o campo di Galois) GF( q ) con lunghezza del codice n = q ^m − 1 e la distanza almeno d è costruita con il metodo seguente.

Sia α un elemento primitivo di GF( q ^m ) . Per ogni intero positivo i , sia m _i ( x ) il polinomio minimo con coefficienti in GF( q ) di α ⁱ . Il polinomio generatore del codice BCH è definito come il minimo comune multiplo g ( x ) = lcm( m ₁ ( x ),…, m _{d − 1} ( x )) . Si può vedere che g ( x ) è un polinomio con coefficienti in GF( q ) e divide x ⁿ − 1 . Pertanto, il codice polinomiale definito da g ( x ) è un codice ciclico.

Esempio

Sia q = 2 e m = 4 (quindi n = 15 ). Considereremo diversi valori di d per GF(16) = GF(2 ⁴ ) basati sul polinomio riducente z ⁴ + z + 1 , utilizzando l'elemento primitivo α ( z ) = z . Ci sono quattordici polinomi minimi m _i ( x ) con coefficienti in GF(2) soddisfacenti

${\displaystyle m_{i}\left(\alpha ^{i}\right){\bmod {\left(z^{4}+z+1\right)}}=0.}$

I polinomi minimi sono

${\displaystyle {\begin{allineato}m_{1}(x)&=m_{2}(x)=m_{4}(x)=m_{8}(x)=x^{4}+x+ 1,\\m_{3}(x)&=m_{6}(x)=m_{9}(x)=m_{12}(x)=x^{4}+x^{3}+x ^{2}+x+1,\\m_{5}(x)&=m_{10}(x)=x^{2}+x+1,\\m_{7}(x)&=m_ {11}(x)=m_{13}(x)=m_{14}(x)=x^{4}+x^{3}+1.\end{allineato}}}$

Il codice BCH con ha un polinomio generatore ${\displaystyle d=2,3}$

${\displaystyle g(x)={\rm {lcm}}(m_{1}(x),m_{2}(x))=m_{1}(x)=x^{4}+x+1 .\,}$

Ha una distanza minima di Hamming di almeno 3 e corregge fino a un errore. Poiché il polinomio generatore è di grado 4, questo codice ha 11 bit di dati e 4 bit di checksum.

Il codice BCH con ha un polinomio generatore ${\displaystyle d=4,5}$

${\displaystyle {\begin{allineato}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4 }(x))=m_{1}(x)m_{3}(x)\\&=\sinistra(x^{4}+x+1\destra)\sinistra(x^{4}+x^ {3}+x^{2}+x+1\destra)=x^{8}+x^{7}+x^{6}+x^{4}+1.\end{allineato}}}$

Ha una distanza minima di Hamming di almeno 5 e corregge fino a due errori. Poiché il polinomio generatore è di grado 8, questo codice ha 7 bit di dati e 8 bit di checksum.

Il codice BCH con ha un polinomio generatore ${\displaystyle d=6,7}$

${\displaystyle {\begin{allineato}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4 }(x),m_{5}(x),m_{6}(x))=m_{1}(x)m_{3}(x)m_{5}(x)\\&=\left( x^{4}+x+1\destra)\sinistra(x^{4}+x^{3}+x^{2}+x+1\destra)\sinistra(x^{2}+x+ 1\right)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1.\end{allineato}}}$

Ha una distanza minima di Hamming di almeno 7 e corregge fino a tre errori. Poiché il polinomio generatore è di grado 10, questo codice ha 5 bit di dati e 10 bit di checksum. (Questo particolare polinomio generatore ha un'applicazione nel mondo reale, nei modelli di formato del codice QR .)

Il codice BCH con e superiori ha un polinomio generatore ${\displaystyle d=8}$

${\displaystyle {\begin{allineato}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),...,m_{14}(x) )=m_{1}(x)m_{3}(x)m_{5}(x)m_{7}(x)\\&=\sinistra(x^{4}+x+1\destra)\ sinistra(x^{4}+x^{3}+x^{2}+x+1\destra)\sinistra(x^{2}+x+1\destra)\sinistra(x^{4}+ x^{3}+1\destra)=x^{14}+x^{13}+x^{12}+\cdots +x^{2}+x+1.\end{allineato}}}$

Questo codice ha una distanza minima di Hamming 15 e corregge 7 errori. Ha 1 bit di dati e 14 bit di checksum. In effetti, questo codice ha solo due parole in codice: 000000000000000 e 111111111111111.

Codici BCH generali

I codici BCH generali differiscono dai codici BCH primitivi a senso stretto per due aspetti.

Primo, il requisito che sia un elemento primitivo di può essere rilassato. Con rilassante questo requisito, la lunghezza del codice cambia da a l' ordine dell'elemento${\displaystyle\alpha}$${\displaystyle \mathrm {GF} (q^{m})}$${\displaystyle q^{m}-1}$${\displaystyle \mathrm {ord} (\alpha ),}$${\displaystyle \alpha.}$

In secondo luogo, le radici consecutive del polinomio generatore possono partire da invece di${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}}$${\displaystyle \alpha ,\ldots ,\alpha ^{d-1}.}$

Definizione. Fissa un campo finito dove è una potenza prima. Scegli interi positivi tali che e è l' ordine moltiplicativo di modulo${\displaystyle GF(q),}$${\displaystyle q}$${\displaystyle m,n,d,c}$${\displaystyle 2\leq d\leq n,}$ ${\displaystyle {\rm {gcd}}(n,q)=1,}$${\displaystyle m}$${\displaystyle q}$${\displaystyle n.}$

Come prima, sia una primitiva radice th di unità in e sia il minimo polinomio over di per tutti Il polinomio generatore del codice BCH è definito come il minimo comune multiplo${\displaystyle\alpha}$${\displaystyle n}$${\displaystyle GF(q^{m}),}$${\displaystyle m_{i}(x)}$${\displaystyle GF(q)}$${\displaystyle \alpha ^{i}}$${\displaystyle i.}$ ${\displaystyle g(x)={\rm {lcm}}(m_{c}(x),\ldots, m_{c+d-2}(x)).}$

Nota: se come nella definizione semplificata, allora è 1, e l'ordine del modulo è Pertanto, la definizione semplificata è effettivamente un caso speciale di quella generale. ${\displaystyle n=q^{m}-1}$${\displaystyle {\rm {gcd}}(n,q)}$${\displaystyle q}$${\displaystyle n}$${\displaystyle m.}$

Casi speciali

• Un codice BCH con è chiamato codice BCH a senso stretto .${\displaystyle c=1}$
• Un codice BCH con è chiamato primitivo .${\displaystyle n=q^{m}-1}$

Il polinomio generatore di un codice BCH ha coefficienti da In generale, un codice ciclico sopra con il polinomio generatore è chiamato un codice BCH sopra il codice BCH sopra e polinomio generatore con successive potenze di come radici è un tipo di codice Reed-Solomon dove l'alfabeto del decodificatore (sindromi) è lo stesso dell'alfabeto del canale (polinomio dei dati e del generatore), tutti gli elementi di . L'altro tipo di codice Reed Solomon è un codice Reed Solomon vista originale che non è un codice BCH. ${\displaystyle g(x)}$${\displaystyle \mathrm {GF} (q).}$${\displaystyle \mathrm {GF} (q^{p})}$${\displaystyle g(x)}$${\displaystyle \mathrm {GF} (q^{p}).}$${\displaystyle \mathrm {GF} (q^{m})}$${\displaystyle g(x)}$${\displaystyle\alpha}$${\displaystyle \mathrm {GF} (q^{m})}$

Proprietà

Il polinomio generatore di un codice BCH ha grado al massimo . Inoltre, se e , il polinomio generatore ha grado al massimo . ${\displaystyle (d-1)m}$${\displaystyle q=2}$${\displaystyle c=1}$${\displaystyle dm/2}$

Un codice BCH ha almeno una distanza minima di Hamming . ${\displaystyle d}$

Un codice BCH è ciclico.

Codifica

Poiché qualsiasi polinomio multiplo del polinomio generatore è una parola in codice BCH valida, la codifica BCH è semplicemente il processo di ricerca di un polinomio che abbia il generatore come fattore.

Lo stesso codice BCH non è prescrittivo sul significato dei coefficienti del polinomio; concettualmente, l'unica preoccupazione di un algoritmo di decodifica BCH è trovare la parola in codice valida con la distanza minima di Hamming dalla parola in codice ricevuta. Pertanto, il codice BCH può essere implementato o come codice sistematico o meno, a seconda di come l'implementatore sceglie di incorporare il messaggio nel polinomio codificato.

Codifica non sistematica: il messaggio come fattore

Il modo più semplice per trovare un polinomio multiplo del generatore è calcolare il prodotto di un polinomio arbitrario per il generatore. In questo caso, il polinomio arbitrario può essere scelto utilizzando come coefficienti i simboli del messaggio.

${\displaystyle s(x)=p(x)g(x)}$

Ad esempio, si consideri il polinomio generatore , scelto per l'uso nel codice BCH binario (31, 21) utilizzato da POCSAG e altri. Per codificare il messaggio a 21 bit {101101110111101111101}, lo rappresentiamo prima come un polinomio su : ${\displaystyle g(x)=x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+1}$${\displaystyle GF(2)}$

${\displaystyle p(x)=x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+ x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1}$

Quindi, calcola (anche su ): ${\displaystyle GF(2)}$

${\displaystyle {\begin{allineato}s(x)&=p(x)g(x)\\&=\left(x^{20}+x^{18}+x^{17}+x^ {15}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5 }+x^{4}+x^{3}+x^{2}+1\destra)\sinistra(x^{10}+x^{9}+x^{8}+x^{6} +x^{5}+x^{3}+1\destra)\\&=x^{30}+x^{29}+x^{26}+x^{25}+x^{24} +x^{22}+x^{19}+x^{17}+x^{16}+x^{15}+x^{14}+x^{12}+x^{10}+x ^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{2}+1\end{allineato}}}$

Pertanto, il codice trasmesso è {1100111010010111101011101110101}.

Il ricevitore può utilizzare questi bit come coefficienti e, dopo la correzione degli errori per garantire un codice valido, può ricalcolare${\displaystyle s(x)}$${\displaystyle p(x)=s(x)/g(x)}$

Codifica sistematica: il messaggio come prefisso

Un codice sistematico è quello in cui il messaggio appare alla lettera da qualche parte all'interno del codice. Pertanto, la codifica BCH sistematica comporta prima l'incorporamento del polinomio del messaggio all'interno del polinomio della parola di codice e quindi la regolazione dei coefficienti dei restanti termini (non messaggi) per garantire che sia divisibile per . ${\displaystyle s(x)}$${\displaystyle g(x)}$

Questo metodo di codifica sfrutta il fatto che sottraendo il resto da un dividendo si ottiene un multiplo del divisore. Quindi, se prendiamo il nostro polinomio del messaggio come prima e lo moltiplichiamo per (per "spostare" il messaggio fuori dal resto), possiamo quindi usare la divisione euclidea dei polinomi per ottenere: ${\displaystyle p(x)}$${\displaystyle x^{nk}}$

${\displaystyle p(x)x^{nk}=q(x)g(x)+r(x)}$

Qui vediamo che è un codice valido. Poiché è sempre di grado inferiore a (che è il grado di ), possiamo sottrarlo in sicurezza senza alterare nessuno dei coefficienti del messaggio, quindi abbiamo il nostro as ${\displaystyle q(x)g(x)}$${\displaystyle r(x)}$${\displaystyle nk}$${\displaystyle g(x)}$${\displaystyle p(x)x^{nk}}$${\displaystyle s(x)}$

${\displaystyle s(x)=q(x)g(x)=p(x)x^{nk}-r(x)}$

Oltre (cioè con i codici BCH binari), questo processo è indistinguibile dall'aggiunta di un controllo di ridondanza ciclico , e se un codice BCH binario sistematico viene utilizzato solo per scopi di rilevamento degli errori, vediamo che i codici BCH sono solo una generalizzazione della matematica del ciclico controlli di ridondanza . ${\displaystyle GF(2)}$

Il vantaggio della codifica sistematica è che il ricevente può recuperare il messaggio originale scartando tutto dopo i primi coefficienti, dopo aver eseguito la correzione degli errori. ${\displaystyle k}$

decodifica

Esistono molti algoritmi per la decodifica dei codici BCH. I più comuni seguono questo schema generale:

1. Calcolare le sindromi s _j per il vettore ricevuto
2. Determinare il numero di errori t e il polinomio di localizzazione dell'errore Λ(x) dalle sindromi
3. Calcola le radici del polinomio della posizione dell'errore per trovare le posizioni dell'errore X _i
4. Calcola i valori di errore Y _i in quelle posizioni di errore
5. Correggi gli errori

Durante alcuni di questi passaggi, l'algoritmo di decodifica può determinare che il vettore ricevuto contiene troppi errori e non può essere corretto. Ad esempio, se non viene trovato un valore appropriato di t , la correzione fallirebbe. In un codice troncato (non primitivo), una posizione di errore potrebbe essere fuori intervallo. Se il vettore ricevuto ha più errori di quanti il ​​codice possa correggere, il decodificatore può inconsapevolmente produrre un messaggio apparentemente valido che non è quello che è stato inviato.

Calcola le sindromi

Il vettore ricevuto è la somma del codice corretto e di un vettore di errore sconosciuto I valori della sindrome sono formati considerando come un polinomio e valutandolo a Quindi le sindromi sono ${\displaystyle R}$${\displaystyle C}$${\displaystyle E.}$${\displaystyle R}$${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}.}$

${\displaystyle s_{j}=R\left(\alpha ^{j}\right)=C\left(\alpha ^{j}\right)+E\left(\alpha ^{j}\right)}$

per a${\displaystyle j=c}$${\displaystyle c+d-2.}$

Poiché sono gli zeri di cui è un multiplo, l' esame dei valori della sindrome isola quindi il vettore di errore in modo che si possa iniziare a risolverlo. ${\displaystyle \alpha ^{j}}$${\displaystyle g(x),}$${\displaystyle C(x)}$${\displaystyle C\left(\alpha ^{j}\right)=0.}$

Se non c'è errore, per tutti Se le sindromi sono tutte zero, allora la decodifica è fatta. ${\displaystyle s_{j}=0}$${\displaystyle j.}$

Calcola il polinomio di posizione dell'errore

Se ci sono sindromi diverse da zero, allora ci sono errori. Il decoder deve capire quanti errori e la posizione di quegli errori.

Se c'è un singolo errore, scrivilo come dove è la posizione dell'errore e la sua grandezza. Allora le prime due sindromi sono ${\displaystyle E(x)=e\,x^{i},}$${\displaystyle i}$${\displaystyle e}$

${\displaystyle {\begin{allineato}s_{c}&=e\,\alpha ^{c\,i}\\s_{c+1}&=e\,\alpha ^{(c+1)\ ,i}=\alpha ^{i}s_{c}\end{allineato}}}$

quindi insieme ci permettono di calcolare e fornire alcune informazioni in merito (determinandolo completamente nel caso dei codici Reed-Solomon). ${\displaystyle e}$${\displaystyle i}$

Se ci sono due o più errori,

${\displaystyle E(x)=e_{1}x^{i_{1}}+e_{2}x^{i_{2}}+\cdots \,}$

Non è immediatamente ovvio come iniziare a risolvere le sindromi risultanti per le incognite e${\displaystyle e_{k}}$${\displaystyle i_{k}.}$

Il primo passo è trovare, compatibile con le sindromi calcolate e con il minimo polinomio di locatore possibile : ${\displaystyle t,}$

${\displaystyle \Lambda (x)=\prod _{j=1}^{t}\left(x\alpha ^{i_{j}}-1\right)}$

Tre algoritmi popolari per questo compito sono:

1. Algoritmo di Peterson-Gorenstein-Zierler
2. Algoritmo di Berlekamp-Massey
3. Algoritmo euclideo di Sugiyama

Algoritmo di Peterson-Gorenstein-Zierler

L'algoritmo di Peterson è il passaggio 2 della procedura di decodifica BCH generalizzata. L'algoritmo di Peterson viene utilizzato per calcolare i coefficienti polinomiali del localizzatore di errore di un polinomio ${\displaystyle \lambda _{1},\lambda _{2},\dots,\lambda _{v}}$

${\displaystyle \Lambda (x)=1+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{v}x^{v}.}$

Ora la procedura dell'algoritmo di Peterson-Gorenstein-Zierler. Aspettiamo di avere almeno 2 t sindromi s _c , …, s _{c +2 t −1} . Sia v  =  t .

Polinomio di localizzazione dell'errore del fattore

Ora che hai il polinomio, le sue radici possono essere trovate nella forma con la forza bruta, ad esempio usando l' algoritmo di ricerca di Chien . Le potenze esponenziali dell'elemento primitivo forniranno le posizioni in cui si verificano errori nella parola ricevuta; da qui il nome polinomio 'locatore errore'. ${\displaystyle \Lambda (x)}$${\displaystyle \Lambda (x)=\left(\alpha ^{i_{1}}x-1\right)\left(\alpha ^{i_{2}}x-1\right)\cdots \left( \alpha ^{i_{v}}x-1\destra)}$${\displaystyle\alpha}$

Gli zeri di Λ( x ) sono α ^{− i ₁} , …, α ^{− i _v} .

Calcola i valori di errore

Una volta note le posizioni degli errori, il passaggio successivo consiste nel determinare i valori di errore in tali posizioni. I valori di errore vengono quindi utilizzati per correggere i valori ricevuti in quelle posizioni per recuperare il codice originale.

Per il caso di BCH binario, (con tutti i caratteri leggibili) questo è banale; basta capovolgere i bit per la parola ricevuta in queste posizioni e abbiamo la parola in codice corretta. Nel caso più generale, i pesi di errore possono essere determinati risolvendo il sistema lineare ${\displaystyle e_{j}}$

${\displaystyle {\begin{allineato}s_{c}&=e_{1}\alpha ^{c\,i_{1}}+e_{2}\alpha ^{c\,i_{2}}+\ cdots \\s_{c+1}&=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2 }}+\cdots \\&{}\ \vdots \end{allineato}}}$

Algoritmo di Forney

Tuttavia, esiste un metodo più efficiente noto come algoritmo di Forney .

Permettere

${\displaystyle S(x)=s_{c}+s_{c+1}x+s_{c+2}x^{2}+\cdots +s_{c+d-2}x^{d-2 }.}$

${\displaystyle v\leqslant d-1,\lambda _{0}\neq 0\qquad \Lambda (x)=\sum _{i=0}^{v}\lambda _{i}x^{i} =\lambda _{0}\prod _{k=0}^{v}\left(\alpha ^{-i_{k}}x-1\right).}$

E il polinomio valutatore di errore

${\ Displaystyle \ Omega (x) \ equiv S (x) \ Lambda (x) {\ bmod {x ^ {d-1}}}}$

Finalmente:

${\displaystyle \Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},}$

dove

${\displaystyle i\cdot x:=\sum _{k=1}^{i}x.}$

Quindi se le sindromi potessero essere spiegate da una parola di errore, che potrebbe essere diversa da zero solo sulle posizioni , allora i valori di errore sono ${\displaystyle i_{k}}$

${\displaystyle e_{k}=-{\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right) \over \alpha ^{c\cdot i_{k} }\Lambda '\left(\alpha ^{-i_{k}}\right)}.}$

Per i codici BCH a senso stretto, c = 1, quindi l'espressione si semplifica in:

${\displaystyle e_{k}=-{\Omega \left(\alpha ^{-i_{k}}\right) \over \Lambda '\left(\alpha ^{-i_{k}}\right)} .}$

Spiegazione del calcolo dell'algoritmo di Forney

Si basa sull'interpolazione di Lagrange e sulle tecniche di generazione di funzioni .

Considera e per semplicità supponi per e per Allora ${\ Displaystyle S (x) \ Lambda (x),}$${\displaystyle \lambda _{k}=0}$${\displaystyle k>v,}$${\displaystyle s_{k}=0}$${\displaystyle k>c+d-2.}$

${\displaystyle S(x)\Lambda (x)=\sum _{j=0}^{\infty }\sum _{i=0}^{j}s_{j-i+1}\lambda _{ io}x^{j}.}$

${\displaystyle {\begin{allineato}S(x)\Lambda (x)&=S(x)\left\{\lambda _{0}\prod _{\ell =1}^{v}\left( \alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{i=0}^{d-2}\sum _{j=1} ^{v}e_{j}\alpha ^{(c+i)\cdot i_{j}}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell = 1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_ {j}\alpha ^{ci_{j}}\sum _{i=0}^{d-2}\left(\alpha ^{i_{j}}\right)^{i}x^{i} \right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\} \\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}} \right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\right\}\left\{\lambda _{0}\prod _{\ell =1} ^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\lambda _{0}\sum _{j=1}^{v}e_ {j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j }}-1}}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\left(\left(x\alpha ^{i_{j}}\right)^{d-1}-1 \right)\prod _{\ell \in \{1,\cdot s ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right)\end{allineato}}}$

Vogliamo calcolare le incognite e potremmo semplificare il contesto rimuovendo i termini. Questo porta al polinomio valutatore di errore ${\displaystyle e_{j},}$${\displaystyle \left(x\alpha ^{i_{j}}\right)^{d-1}}$

${\displaystyle \Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}.}$

Grazie a abbiamo ${\displaystyle v\leqslant d-1}$

${\displaystyle \Omega (x)=-\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\prod _{\ell \in \ {1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right).}$

Grazie a (il trucco dell'interpolazione di Lagrange) la somma degenera in un solo addizione per${\displaystyle\Lambda}$${\displaystyle x=\alpha ^{-i_{k}}}$

${\displaystyle \Omega \left(\alpha ^{-i_{k}}\right)=-\lambda _{0}e_{k}\alpha ^{c\cdot i_{k}}\prod _{\ ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right). }$

Per ottenerlo dovremmo semplicemente sbarazzarci del prodotto. Potremmo calcolare il prodotto direttamente dalle radici già calcolate di ma potremmo usare una forma più semplice. ${\displaystyle e_{k}}$${\displaystyle \alpha ^{-i_{j}}}$${\displaystyle\Lambda,}$

Come derivato formale

${\displaystyle \Lambda '(x)=\lambda _{0}\sum _{j=1}^{v}\alpha ^{i_{j}}\prod _{\ell \in \{1,\ cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right),}$

otteniamo di nuovo solo una somma in

${\displaystyle \Lambda '\left(\alpha ^{-i_{k}}\right)=\lambda _{0}\alpha ^{i_{k}}\prod _{\ell \in \{1, \cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).}$

Quindi finalmente

${\displaystyle e_{k}=-{\frac {\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right)}{\alpha ^{c\cdot i_ {k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}}.}$

Questa formula è vantaggiosa quando si calcola la derivata formale della forma ${\displaystyle\Lambda}$

${\displaystyle \Lambda (x)=\sum _{i=1}^{v}\lambda _{i}x^{i}}$

cedendo:

${\displaystyle \Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},}$

dove

${\displaystyle i\cdot x:=\sum _{k=1}^{i}x.}$

Decodifica basata su algoritmo euclideo esteso

Un processo alternativo per trovare sia il polinomio che il polinomio di localizzazione dell'errore si basa sull'adattamento di Yasuo Sugiyama dell'algoritmo euclideo esteso . Anche la correzione dei caratteri illeggibili potrebbe essere incorporata facilmente nell'algoritmo.

Siano posizioni di caratteri illeggibili. Si crea un polinomio localizzando queste posizioni. Impostare i valori sulle posizioni illeggibili a 0 e calcolare le sindromi. ${\displaystyle k_{1},...,k_{k}}$${\displaystyle \Gamma (x)=\prod _{i=1}^{k}\left(x\alpha ^{k_{i}}-1\right).}$

Come abbiamo già definito per la formula di Forney poniamo ${\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}.}$

Eseguiamo l'algoritmo euclideo esteso per localizzare il minimo comun divisore di polinomi e L'obiettivo non è trovare il minimo comun divisore, ma un polinomio di grado al massimo e polinomi tali che Basso grado di garanzie, che soddisferebbe condizioni estese (per ) definenti per${\displaystyle S(x)\Gamma (x)}$${\displaystyle x^{d-1}.}$${\displaystyle r(x)}$${\displaystyle \lfloor (d+k-3)/2\rfloor }$${\displaystyle a(x),b(x)}$${\displaystyle r(x)=a(x)S(x)\Gamma (x)+b(x)x^{d-1}.}$${\displaystyle r(x)}$${\displaystyle a(x)}$${\displaystyle \Gamma}$${\displaystyle\Lambda.}$

Definire e utilizzare al posto di nella formula di Fourney ci darà valori di errore. ${\ Displaystyle \ Xi (x) = a (x) \ Gamma (x)}$${\displaystyle\Xi}$${\displaystyle \Lambda (x)}$

Il vantaggio principale dell'algoritmo è che nel frattempo calcola richiesto nella formula di Forney. ${\ Displaystyle \ Omega (x) = S (x) \ Xi (x) {\ bmod {x}} ^ {d-1} = r (x)}$

Spiegazione del processo di decodifica

L'obiettivo è trovare una parola in codice che differisca il meno possibile dalla parola ricevuta su posizioni leggibili. Quando esprimiamo la parola ricevuta come somma della parola in codice più vicina e della parola di errore, stiamo cercando di trovare la parola di errore con un numero minimo di valori diversi da zero sulle posizioni leggibili. La sindrome limita l'errore parola per condizione ${\displaystyle s_{i}}$

${\displaystyle s_{i}=\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}.}$

Potremmo scrivere queste condizioni separatamente o potremmo creare un polinomio

${\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}}$

e confrontare i coefficienti vicino alle potenze a${\displaystyle 0}$${\displaystyle d-2.}$

${\displaystyle S(x){\stackrel {\{0,\cdots,\,d-2\}}{=}}E(x)=\sum _{i=0}^{d-2}\ somma _{j=0}^{n-1}e_{j}\alpha ^{ij}\alpha ^{cj}x^{i}.}$

Supponiamo che ci sia una lettera illeggibile sulla posizione , potremmo sostituire un insieme di sindromi con un insieme di sindromi definito dall'equazione Supponiamo che per una parola di errore valgano tutte le restrizioni dell'insieme originale di sindromi, che ${\displaystyle k_{1},}$${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$${\displaystyle \{t_{c},\cdots ,t_{c+d-3}\}}$${\displaystyle t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}.}$${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$

${\displaystyle t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}=\alpha ^{k_{1}}\sum _{j=0}^{n- 1}e_{j}\alpha ^{ij}-\sum _{j=0}^{n-1}e_{j}\alpha ^{j}\alpha ^{ij}=\sum _{j= 0}^{n-1}e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)\alpha ^{ij}.}$

La nuova serie di sindromi limita il vettore di errore

${\displaystyle f_{j}=e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)}$

allo stesso modo in cui l'insieme originale di sindromi limitava il vettore di errore Tranne la coordinata in cui abbiamo an è zero, se Per l'obiettivo di localizzare le posizioni di errore potessimo modificare l'insieme di sindromi in modo simile per riflettere tutti i caratteri illeggibili. Questo accorcia l'insieme delle sindromi di${\displaystyle e_{j}.}$${\displaystyle k_{1},}$${\displaystyle f_{k_{1}}=0,}$${\displaystyle f_{j}}$${\displaystyle e_{j}=0.}$${\displaystyle k.}$

Nella formulazione polinomiale, la sostituzione di sindromi impostate da sindromi impostate porta a ${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$${\displaystyle \{t_{c},\cdots ,t_{c+d-3}\}}$

${\displaystyle T(x)=\sum _{i=0}^{d-3}t_{c+i}x^{i}=\alpha ^{k_{1}}\sum _{i=0 }^{d-3}s_{c+i}x^{i}-\sum _{i=1}^{d-2}s_{c+i}x^{i-1}.}$

Perciò,

${\displaystyle xT(x){\stackrel {\{1,\cdots,\,d-2\}}{=}}\left(x\alpha ^{k_{1}}-1\right)S( X).}$

Dopo la sostituzione di by , si richiederebbe l'equazione per coefficienti vicini alle potenze${\displaystyle S(x)}$${\displaystyle S(x)\Gamma (x)}$${\displaystyle k,\cdots ,d-2.}$

Si potrebbe considerare la ricerca di posizioni di errore dal punto di vista dell'eliminazione dell'influenza di determinate posizioni allo stesso modo dei caratteri illeggibili. Se trovassimo posizioni tali che l'eliminazione della loro influenza porti ad ottenere un insieme di sindromi consistenti di tutti zeri, allora esiste un vettore di errore con errori solo su queste coordinate. Se denota il polinomio eliminando l'influenza di queste coordinate, si ottiene ${\displaystyle v}$${\displaystyle \Lambda (x)}$

${\displaystyle S(x)\Gamma (x)\Lambda (x){\stackrel {\{k+v,\cdots, d-2\}}{=}}0.}$

Nell'algoritmo euclideo, cerchiamo di correggere al massimo gli errori (su posizioni leggibili), perché con un numero di errori maggiore potrebbero esserci più parole di codice alla stessa distanza dalla parola ricevuta. Pertanto, per quanto stiamo cercando, l'equazione deve valere per coefficienti prossimi alle potenze a partire da ${\displaystyle {\tfrac {1}{2}}(d-1-k)}$${\displaystyle \Lambda (x)}$

${\displaystyle k+\left\lfloor {\frac {1}{2}}(d-1-k)\right\rfloor .}$

Nella formula di Forney, potrebbe essere moltiplicato per uno scalare dando lo stesso risultato. ${\displaystyle \Lambda (x)}$

Potrebbe accadere che l'algoritmo euclideo trovi di grado maggiore di avere un numero di radici diverse pari al suo grado, dove la formula di Fourney sarebbe in grado di correggere errori in tutte le sue radici, tuttavia correggere così tanti errori potrebbe essere rischioso (soprattutto con nessun altro restrizioni sulla parola ricevuta). Solitamente dopo aver conseguito il titolo di studio superiore, decidiamo di non correggere gli errori. La correzione potrebbe fallire nel caso in cui abbia radici con una molteplicità maggiore o il numero di radici sia inferiore al suo grado. L'errore potrebbe essere rilevato anche dalla formula di Forney che restituisce un errore al di fuori dell'alfabeto trasmesso. ${\displaystyle \Lambda (x)}$${\displaystyle {\tfrac {1}{2}}(d-1-k)}$${\displaystyle \Lambda (x)}$${\displaystyle \Lambda (x)}$

Correggi gli errori

Utilizzando i valori di errore e la posizione dell'errore, correggere gli errori e formare un vettore di codice corretto sottraendo i valori di errore nelle posizioni dell'errore.

Esempi di decodifica

Decodifica del codice binario senza caratteri illeggibili

Consideriamo un codice BCH in GF(2 ⁴ ) con e . (Questo è usato nei codici QR .) Lascia che il messaggio da trasmettere sia [1 1 0 1 1], o in notazione polinomiale, I simboli "checksum" sono calcolati dividendo per e prendendo il resto, risultando in o [ 1 0 0 0 0 1 0 1 0 0 ]. Questi vengono aggiunti al messaggio, quindi il codice trasmesso è [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ]. ${\displaystyle d=7}$${\displaystyle g(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1}$${\displaystyle M(x)=x^{4}+x^{3}+x+1.}$${\displaystyle x^{10}M(x)}$${\displaystyle g(x)}$${\displaystyle x^{9}+x^{4}+x^{2}}$

Ora, immagina che ci siano due errori di bit nella trasmissione, quindi il codice ricevuto è [ 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 ]. In notazione polinomiale:

${\displaystyle R(x)=C(x)+x^{13}+x^{5}=x^{14}+x^{11}+x^{10}+x^{9}+x ^{5}+x^{4}+x^{2}}$

Per correggere gli errori, calcolare prima le sindromi. Prendendo abbiamo e Avanti, applica la procedura di Peterson riducendo per riga la seguente matrice aumentata. ${\displaystyle \alpha =0010,}$${\displaystyle s_{1}=R(\alpha ^{1})=1011,}$ ${\displaystyle s_{2}=1001,}$ ${\displaystyle s_{3}=1011,}$ ${\displaystyle s_{4}=1101,}$ ${\displaystyle s_{5}=0001,}$${\displaystyle s_{6}=1001.}$

${\displaystyle \left[S_{3\times 3}|C_{3\times 1}\right]={\begin{bmatrix}s_{1}&s_{2}&s_{3}&s_{4}\\s_ {2}&s_{3}&s_{4}&s_{5}\\s_{3}&s_{4}&s_{5}&s_{6}\end{bmatrix}}={\begin{bmatrix}1011&1001&1011&1101\\1001&1011&1101&0001 \\1011&1101&0001&1001\end{bmatrix}}\Rightarrow {\begin{bmatrix}0001&0000&1000&0111\\0000&0001&1011&0001\\0000&0000&0000&0000\end{bmatrix}}}$

A causa della riga zero, S _3×3 è singolare, il che non sorprende poiché nel codice sono stati introdotti solo due errori. Tuttavia, l'angolo superiore sinistro della matrice è identico a [ S _2×2 | C _2×1 ] , che dà luogo alla soluzione Il polinomio di localizzazione dell'errore risultante è che ha zeri in e Gli esponenti di corrispondono alle posizioni dell'errore. Non è necessario calcolare i valori di errore in questo esempio, poiché l'unico valore possibile è 1. ${\displaystyle \lambda _{2}=1000,}$ ${\displaystyle \lambda _{1}=1011.}$${\displaystyle \Lambda (x)=1000x^{2}+1011x+0001,}$${\displaystyle 0100=\alpha ^{-13}}$${\displaystyle 0111=\alpha ^{-5}.}$${\displaystyle\alpha}$

Decodifica con caratteri illeggibili

Supponiamo lo stesso scenario, ma la parola ricevuta ha due caratteri illeggibili [ 1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0 ]. Sostituiamo i caratteri illeggibili con zeri durante la creazione del polinomio che riflette le loro posizioni Calcoliamo le sindromi e (Utilizzando la notazione logaritmica che è indipendente dagli isomorfismi GF(2 ⁴ ). Per il controllo del calcolo possiamo usare la stessa rappresentazione per l'addizione usata in precedenza esempio. Descrizione esadecimale delle potenze di sono consecutivamente 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9 con l'addizione basata su xor bit per bit.) ${\displaystyle \Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).}$${\displaystyle s_{1}=\alpha ^{-7},s_{2}=\alpha ^{1},s_{3}=\alpha ^{4},s_{4}=\alpha ^{2 },s_{5}=\alfa ^{5},}$${\displaystyle s_{6}=\alpha ^{-7}.}$${\displaystyle\alpha}$

Facciamo la sindrome polinomiale

${\displaystyle S(x)=\alpha ^{-7}+\alpha ^{1}x+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^ {5}x^{4}+\alfa ^{-7}x^{5},}$

calcolare

${\displaystyle S(x)\Gamma (x)=\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{ 3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+\alpha ^{7}x^{6}+\alpha ^{-3}x^{ 7}.}$

Esegui l'algoritmo euclideo esteso:

${\displaystyle {\begin{allineato}&{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}\\[6pt]={}&{\begin {pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1} x^{4}+\alpha ^{5}x^{5}+\alpha ^{7}x^{6}+\alpha ^{-3}x^{7}\\x^{6}\ end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}+\alpha ^{-3}x&1\\1&0\end{pmatrix}}{\begin{pmatrix} x^{6}\\\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^ {-1}x^{4}+\alpha ^{5}x^{5}+2\alpha ^{7}x^{6}+2\alpha ^{-3}x^{7}\end {pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}+\alpha ^{-3}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\ alpha ^{4}+\alpha ^{-5}x&1\\1&0\end{pmatrix}}\\&\qquad {\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\ alfa ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}\\ \alpha ^{-3}+\left(\alpha ^{-7}+\alpha ^{3}\right)x+\left(\alpha ^{3}+\alpha ^{-1}\right)x ^{2}+\left(\alpha ^{-5}+\alpha ^{-6}\right)x^{3}+\left(\alpha ^{3}+\alpha ^{1}\right )x^{4}+2\alpha ^{-6}x^{5}+2x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{ pmatrix}\left(1+\alpha ^{-4}\right)+\left(\alpha ^{1}+\alpha ^{2}\right)x+\alpha ^{7}x^{2}& \alpha ^{7}+\alpha ^{-3}x\\\alpha ^{4}+\alpha ^{-5}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{-7 }+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^ {5}x^{5}\\\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3} +\alpha ^{-6}x^{4}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{-3}+\alpha ^{5}x+\ alpha ^{7}x^{2}&\alpha ^{7}+\alpha ^{-3}x\\\alpha ^{4}+\alpha ^{-5}x&1\end{pmatrix}}{ \begin{pmatrix}\alpha ^{-5}+\alpha ^{-4}x&1\\1&0\end{pmatrix}}\\&\qquad {\begin{pmatrix}\alpha ^{-3}+\ alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\left(\ alpha ^{7}+\alpha ^{-7}\right)+\left(2\alpha ^{-7}+\alpha ^{4}\right)x+\left(\alpha ^{-5}+ \alpha ^{-6}+\alpha ^{-1}\right)x^{2}+\left(\alpha ^{-7}+\alpha ^{-4}+\alpha ^{6}\ destra)x^{3}+\sinistra(\alpha ^{4}+\alpha ^{-6}+\alpha ^{-1}\destra)x^{4}+2\alpha ^{5}x ^{5}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}x+\alpha ^{ 5}x^{2}+\alpha ^{3}x^{3}&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&\alpha ^{4}+\alpha ^{-5}x\end{pmatrix}}{\begin{ pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6} x^{4}\\\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}\end{pmatrix }}.\end{allineato}}}$

Abbiamo raggiunto il polinomio di grado al massimo 3, e come

${\displaystyle {\begin{pmatrix}-\left(\alpha ^{4}+\alpha ^{-5}x\right)&\alpha ^{-3}+\alpha ^{5}x+\alpha ^ {7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)\end{pmatrix}}{\begin{pmatrix}\alpha ^{7}x+\alpha ^{5}x ^{2}+\alpha ^{3}x^{3}&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3 }+\alpha ^{-5}x+\alpha ^{6}x^{2}&\alpha ^{4}+\alpha ^{-5}x\end{pmatrix}}={\begin{pmatrix} 1&0\\0&1\end{pmatrix}},}$

noi abbiamo

${\displaystyle {\begin{pmatrix}-\left(\alpha ^{4}+\alpha ^{-5}x\right)&\alpha ^{-3}+\alpha ^{5}x+\alpha ^ {7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)\end{pmatrix}}{\begin{pmatrix}S(x)\Gamma (x)\\x^{ 6}\end{pmatrix}}={\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2} x^{3}+\alpha ^{-6}x^{4}\\\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^ {-5}x^{3}\end{pmatrix}}.}$

Perciò,

${\displaystyle S(x)\Gamma (x)\left(\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}\right)-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)x^{6}=\alpha ^{-4}+\alpha ^{4 }x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}.}$

Let Non ti preoccupare che Find con la forza bruta una radice di Le radici sono e (dopo aver trovato per esempio possiamo dividere da corrispondenti Monom e la radice del conseguente Monom potrebbe essere trovato facilmente). ${\displaystyle \Lambda (x)=\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}.}$${\displaystyle \lambda _{0}\neq 1.}$${\displaystyle\Lambda.}$${\displaystyle \alpha ^{2},}$${\displaystyle \alpha ^{10}}$${\displaystyle \alpha ^{2}}$${\displaystyle\Lambda}$${\displaystyle \left(x-\alpha ^{2}\right)}$

Permettere

${\displaystyle {\begin{allineato}\Xi (x)&=\Gamma (x)\Lambda (x)=\alpha ^{3}+\alpha ^{4}x^{2}+\alpha ^{ 2}x^{3}+\alpha ^{-5}x^{4}\\\Omega (x)&=S(x)\Xi (x)\equiv \alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}{\bmod {x^{6}}}\end{allineato}}}$

Cerchiamo i valori di errore usando la formula

${\displaystyle e_{j}=-{\frac {\Omega \left(\alpha ^{-i_{j}}\right)}{\Xi '\left(\alpha ^{-i_{j}}\ Giusto)}},}$

dove sono le radici di We get ${\displaystyle \alpha ^{-i_{j}}}$${\displaystyle \Xi (x).}$ ${\displaystyle \Xi '(x)=\alpha ^{2}x^{2}.}$

${\displaystyle {\begin{allineato}e_{1}&=-{\frac {\Omega (\alpha ^{4})}{\Xi '(\alpha ^{4})}}={\frac { \alpha ^{-4}+\alpha ^{-7}+\alpha ^{-5}+\alpha ^{7}}{\alpha ^{-5}}}={\frac {\alpha ^{ -5}}{\alpha ^{-5}}}=1\\e_{2}&=-{\frac {\Omega (\alpha ^{7})}{\Xi '(\alpha ^{7 })}}={\frac {\alpha ^{-4}+\alpha ^{-4}+\alpha ^{1}+\alpha ^{1}}{\alpha ^{1}}}=0 \\e_{3}&=-{\frac {\Omega (\alpha ^{10})}{\Xi '(\alpha ^{10})}}={\frac {\alpha ^{-4} +\alpha ^{-1}+\alpha ^{7}+\alpha ^{-5}}{\alpha ^{7}}}={\frac {\alpha ^{7}}{\alpha ^{ 7}}}=1\\e_{4}&=-{\frac {\Omega (\alpha ^{2})}{\Xi '(\alpha ^{2})}}={\frac {\ alpha ^{-4}+\alpha ^{6}+\alpha ^{6}+\alpha ^{1}}{\alpha ^{6}}}={\frac {\alpha ^{6}}{ \alpha ^{6}}}=1\end{allineato}}}$

In effetti , questo non dovrebbe sorprendere. ${\displaystyle e_{3}=e_{4}=1,}$

Il codice corretto è quindi [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Decodifica con caratteri illeggibili con un piccolo numero di errori

Mostriamo il comportamento dell'algoritmo per il caso con un piccolo numero di errori. Lascia che la parola ricevuta sia [ 1 0 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ].

Di nuovo, sostituisci i caratteri illeggibili con zeri mentre crei il polinomio che riflette le loro posizioni Calcola le sindromi e Crea il polinomio della sindrome ${\displaystyle \Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).}$${\displaystyle s_{1}=\alpha ^{4},s_{2}=\alpha ^{-7},s_{3}=\alpha ^{1},s_{4}=\alpha ^{1 },s_{5}=\alfa ^{0},}$${\displaystyle s_{6}=\alpha ^{2}.}$

${\displaystyle {\begin{allineato}S(x)&=\alpha ^{4}+\alpha ^{-7}x+\alpha ^{1}x^{2}+\alpha ^{1}x^ {3}+\alpha ^{0}x^{4}+\alpha ^{2}x^{5},\\S(x)\Gamma (x)&=\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^ {5}+\alpha ^{-1}x^{6}+\alpha ^{6}x^{7}.\end{allineato}}}$

Eseguiamo l'algoritmo euclideo esteso:

${\displaystyle {\begin{allineato}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}&={\begin{pmatrix}\alpha ^{4 }+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{- 1}x^{5}+\alpha ^{-1}x^{6}+\alpha ^{6}x^{7}\\x^{6}\end{pmatrix}}\\&={ \begin{pmatrix}\alpha ^{-1}+\alpha ^{6}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}x^{6}\\\alpha ^{4}+\ alfa ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x ^{5}+2\alpha ^{-1}x^{6}+2\alpha ^{6}x^{7}\end{pmatrix}}\\&={\begin{pmatrix}\alpha ^ {-1}+\alpha ^{6}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{3}+\alpha ^{1}x&1\\1&0\end{pmatrix}} {\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1} x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\left(\alpha ^{-5}+\alpha ^{5}\right)x+2 \alpha ^{-7}x^{2}+2\alpha ^{6}x^{3}+2\alpha ^{4}x^{4}+2\alpha ^{2}x^{5 }+2x^{6}\end{pmatrix}}\\&={\begin{pmatrix}\left(1+\alpha ^{2}\right)+\left(\alpha ^{0}+\alpha ^{-6}\right)x+\alpha ^{7}x^{2}&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+ \alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\alpha ^{0 }x\end{pmatrix}}\end{allineato}}}$

Abbiamo raggiunto il polinomio di grado al massimo 3, e come

${\displaystyle {\begin{pmatrix}-1&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&-\left(\alpha ^{ -7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)\end{pmatrix}}{\begin{pmatrix}\alpha ^{-7}+\alpha ^{7 }x+\alpha ^{7}x^{2}&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&1\end{pmatrix} }={\begin{pmatrix}1&0\\0&1\end{pmatrix}},}$

noi abbiamo

${\displaystyle {\begin{pmatrix}-1&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&-\left(\alpha ^{ -7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)\end{pmatrix}}{\begin{pmatrix}S(x)\Gamma (x)\\x^ {6}\end{pmatrix}}={\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^ {3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\alpha ^{0}x\end{pmatrix}} .}$

Perciò,

${\displaystyle S(x)\Gamma (x)\left(\alpha ^{3}+\alpha ^{1}x\right)-\left(\alpha ^{-7}+\alpha ^{7} x+\alpha ^{7}x^{2}\right)x^{6}=\alpha ^{7}+\alpha ^{0}x.}$

Lasciate Non ti preoccupare che la radice di IS${\displaystyle \Lambda (x)=\alpha ^{3}+\alpha ^{1}x.}$${\displaystyle \lambda _{0}\neq 1.}$${\displaystyle \Lambda (x)}$${\displaystyle \alpha ^{3-1}.}$

Permettere

${\displaystyle {\begin{allineato}\Xi (x)&=\Gamma (x)\Lambda (x)=\alpha ^{3}+\alpha ^{-7}x+\alpha ^{-4}x ^{2}+\alpha ^{5}x^{3},\\\Omega (x)&=S(x)\Xi (x)\equiv \alpha ^{7}+\alpha ^{0} x{\bmod {x^{6}}}\end{allineato}}}$

Cerchiamo i valori di errore usando la formula dove sono le radici del polinomio${\displaystyle e_{j}=-\Omega \left(\alpha ^{-i_{j}}\right)/\Xi '\left(\alpha ^{-i_{j}}\right),}$${\displaystyle \alpha ^{-i_{j}}}$${\displaystyle \Xi (x).}$

${\displaystyle \Xi '(x)=\alpha ^{-7}+\alpha ^{5}x^{2}.}$

Noi abbiamo

${\displaystyle {\begin{allineato}e_{1}&=-{\frac {\Omega \left(\alpha ^{4}\right)}{\Xi '\left(\alpha ^{4}\right )}}={\frac {\alpha ^{7}+\alpha ^{4}}{\alpha ^{-7}+\alpha ^{-2}}}={\frac {\alpha ^{3 }}{\alpha ^{3}}}=1\\e_{2}&=-{\frac {\Omega \left(\alpha ^{7}\right)}{\Xi '\left(\alpha ^{7}\right)}}={\frac {\alpha ^{7}+\alpha ^{7}}{\alpha ^{-7}+\alpha ^{4}}}=0\\e_ {3}&=-{\frac {\Omega \left(\alpha ^{2}\right)}{\Xi '\left(\alpha ^{2}\right)}}={\frac {\alpha ^{7}+\alpha ^{2}}{\alpha ^{-7}+\alpha ^{-6}}}={\frac {\alpha ^{-3}}{\alpha ^{-3 }}}=1\end{allineato}}}$

Il fatto non dovrebbe sorprendere. ${\displaystyle e_{3}=1}$

Il codice corretto è quindi [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

citazioni

Riferimenti

Fonti primarie

• Hocquenghem, A. (settembre 1959), "Codes Correcteurs d'erreurs", Chiffres (in francese), Paris, 2 : 147-156
• Bose, RC ; Ray-Chaudhuri, DK (marzo 1960), "On A Class of Error Correcting Binary Group Codes" (PDF) , Informazioni e controllo , 3 (1): 68–79, doi : 10.1016/s0019-9958(60)90287- 4 , ISSN  0890-5401

Fonti secondarie

• Gill, John (nd), EE387 Notes #7, Handout #28 (PDF) , Stanford University, pp. 42–45 , recuperato il 21 aprile 2010Apparentemente le note del corso sono in fase di rifacimento per il 2012: http://www.stanford.edu/class/ee387/
• Gorenstein, Daniel ; Peterson, W. Wesley ; Zierler, Neal (1960), "I codici di correzione di due errori Bose-Chaudhuri sono quasi perfetti", Informazione e controllo , 3 (3): 291–294, doi : 10.1016/s0019-9958(60)90877-9
• Lidl, Rodolfo; Pilz, Günter (1999), Algebra astratta applicata (2a ed.), John Wiley
• Reed, Irving S. ; Chen, Xuemin (1999), Codifica per il controllo degli errori per reti di dati , Boston, MA: Kluwer Academic Publishers , ISBN 0-7923-8528-4

Ulteriori letture

• Blahut, Richard E. (2003), Codici algebrici per la trasmissione dei dati (2a ed.), Cambridge University Press , ISBN 0-521-55374-1
• Gilbert, WJ; Nicholson, WK (2004), Algebra moderna con applicazioni (2a ed.), John Wiley
• Lin, S.; Costello, D. (2004), Codifica per il controllo degli errori: Fondamenti e applicazioni , Englewood Cliffs, NJ: Prentice-Hall
• MacWilliams, FJ; Sloane, NJA (1977), La teoria dei codici di correzione degli errori , New York, NY: North-Holland Publishing Company
• Rudra, Atri, CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications , University at Buffalo, archiviato dall'originale il 02-07-2010 , recuperato il 21 aprile 2010