Algoritmo di decodifica di Zemor - Zemor's decoding algorithm

Nella teoria dei codici , l'algoritmo di Zemor , progettato e sviluppato da Gilles Zemor, è un approccio ricorsivo a bassa complessità alla costruzione del codice. È un miglioramento rispetto all'algoritmo di Sipser e Spielman .

Zemor ha considerato una tipica classe di costruzione Sipser-Spielman di codici di espansione , in cui il grafo sottostante è grafo bipartito . Sipser e Spielman hanno introdotto una famiglia costruttiva di codici di errore lineare asintoticamente buoni insieme a un semplice algoritmo parallelo che rimuoverà sempre una frazione costante di errori. L'articolo si basa sugli appunti del corso del Dr. Venkatesan Guruswami

Costruzione del codice

L'algoritmo di Zemor si basa su un tipo di grafico espansore chiamato grafico di Tanner . La costruzione del codice è stata proposta per la prima volta da Tanner. I codici sono basati su double cover , regular expander , che è un grafo bipartito. = , dove è l'insieme dei vertici ed è l'insieme degli archi e = e = , dove e denota gli insiemi dei vertici. Sia il numero di vertici in ogni gruppo, cioè , . Il set di bordi è di dimensione = e ogni bordo in ha un punto finale in entrambi e . denota l'insieme di bordi che contengono . ${\displaystyle d}$${\displaystyle G}$${\displaystyle G}$${\displaystyle\left(V,E\right)}$${\displaystyle V}$${\displaystyle E}$${\displaystyle V}$${\displaystyle A}$ ${\displaystyle \cup}$ ${\displaystyle B}$${\displaystyle A}$ ${\displaystyle\cap }$ ${\displaystyle B}$${\displaystyle\emptyset}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n}$${\displaystyle |A|=|B|=n}$${\displaystyle E}$${\displaystyle N}$${\displaystyle nd}$${\displaystyle E}$${\displaystyle A}$${\displaystyle B}$${\displaystyle E(v)}$${\displaystyle v}$

Assumiamo un ordinamento su , quindi l'ordinamento verrà eseguito su ogni bordo di per ogni . Lascia campo finito , e per una parola in , lascia che la sottoparola della parola sarà indicizzata da . Lascia che questa parola sia indicata con . Il sottoinsieme di vertici e induce ogni parola una partizione in sottoparole non sovrapposte , dove varia sugli elementi di . Per costruire un codice , considera un sottocodice lineare , che è un codice, dove , la dimensione dell'alfabeto è . Per ogni vertice , sia un ordinamento dei vertici di adiacente a . In questo codice, ogni bit è collegato a un fronte di . ${\displaystyle V}$${\displaystyle E(v)}$${\displaystyle v\in V}$ ${\displaystyle \mathbb {F} = GF(2)}$${\displaystyle x=(x_{e}),e\in E}$${\displaystyle \mathbb {F} ^{N}}$${\displaystyle E(v)}$${\displaystyle (x)_{v}}$${\displaystyle A}$${\displaystyle B}$${\displaystyle x\in \mathbb {F} ^{N}}$${\displaystyle n}$${\displaystyle \left(x\right)_{v}\in \mathbb {F} ^{d}}$${\displaystyle v}$${\displaystyle A}$${\displaystyle C}$${\displaystyle C_{o}}$${\displaystyle [d,r_{o}d,\delta]}$${\displaystyle q}$${\displaystyle 2}$${\displaystyle v\in V}$${\displaystyle v(1),v(2),\ldots,v(d)}$${\displaystyle d}$${\displaystyle E}$${\displaystyle v}$${\displaystyle x_{e}}$${\displaystyle e}$${\displaystyle E}$

Possiamo definire il codice come l'insieme dei vettori binari di tale che, per ogni vertice di , è una parola di codice di . In questo caso, possiamo considerare un caso speciale quando ogni arco di è adiacente esattamente ai vertici di . Significa che e costituiscono, rispettivamente, l'insieme dei vertici e l'insieme degli archi del grafo regolare . ${\displaystyle C}$${\displaystyle x=\left(x_{1},x_{2},\ldots,x_{N}\right)}$${\displaystyle \{0,1\}^{N}}$${\displaystyle v}$${\displaystyle V}$${\displaystyle \left(x_{v(1)},x_{v(2)},\ldots ,x_{v(d)}\right)}$${\displaystyle C_{o}}$${\displaystyle E}$${\displaystyle 2}$${\displaystyle V}$${\displaystyle V}$${\displaystyle E}$${\displaystyle d}$${\displaystyle G}$

Chiamiamo codice il codice costruito in questo modo . Per un dato grafo e un dato codice , ci sono diversi codici come ci sono diversi modi di ordinare gli archi incidenti su un dato vertice , cioè . In effetti il ​​nostro codice consiste di tutte le parole in codice in modo tale che per tutti . Il codice è lineare in quanto viene generato da un sottocodice , che è lineare. Il codice è definito come per ogni . ${\displaystyle C}$${\displaystyle \left(G,C_{o}\right)}$${\displaystyle G}$${\displaystyle C_{o}}$${\displaystyle \left(G,C_{o}\right)}$${\displaystyle v}$${\displaystyle v(1),v(2),\ldots,v(d)}$${\displaystyle C}$${\displaystyle x_{v}\in C_{o}}$${\displaystyle v\in A,B}$${\displaystyle C}$${\displaystyle [N,K,D]}$${\displaystyle \mathbb {F}}$${\displaystyle C_{o}}$${\displaystyle C}$${\displaystyle C=\{c\in \mathbb {F} ^{N}:(c)_{v}\in C_{o}\}}$${\displaystyle v\in V}$

In questa figura, . Mostra il grafico e il codice . ${\displaystyle (x)_{v}=\left(x_{e1},x_{e2},x_{e3},x_{e4}\right)\in C_{o}}$${\displaystyle G}$${\displaystyle C}$

In matrice , let è uguale al secondo autovalore più grande della matrice di adiacenza di . Qui l'autovalore più grande è . Vengono fatte due affermazioni importanti: ${\displaystyle G}$${\displaystyle \lambda}$${\displaystyle G}$${\displaystyle d}$

Rivendicazione 1

${\displaystyle \left({\dfrac {K}{N}}\right)\geq 2r_{o}-1}$
. Sia la velocità di un codice lineare costruito da un grafo bipartito i cui nodi di cifre hanno grado e i cui nodi di sottocodice hanno grado . Se un singolo codice lineare con parametri e velocità è associato a ciascuno dei nodi del sottocodice, allora${\displaystyle R}$${\displaystyle m}$${\displaystyle n}$${\displaystyle \left(n,k\right)}$${\displaystyle r=\left({\dfrac {k}{n}}\right)}$${\displaystyle k\geq 1-\left(1-r\right)m}$ .

Prova

Sia la velocità del codice lineare, che è uguale a Lascia che ci siano nodi di sottocodice nel grafico. Se il grado del sottocodice è , allora il codice deve avere cifre, poiché ogni nodo di cifra è connesso a degli archi nel grafico. Ogni nodo di sottocodice contribuisce con equazioni alla matrice di controllo di parità per un totale di . Queste equazioni potrebbero non essere linearmente indipendenti. Pertanto, , Poiché il valore di , cioè il nodo della cifra di questo grafo bipartito è e qui , possiamo scrivere come:${\displaystyle R}$${\displaystyle K/N}$${\displaystyle S}$${\displaystyle n}$${\displaystyle \left({\dfrac {n}{m}}\right)S}$${\displaystyle m}$${\displaystyle \left(n\right)S}$${\displaystyle (nk)}$${\displaystyle \left(nk\right)S}$${\displaystyle \left({\dfrac {K}{N}}\right)\geq \left({\dfrac {({\dfrac {n}{m}})S-(nk)S}{({ \dfrac {n}{m}})S}}\right)}$
${\displaystyle \geq 1-m\sinistra({\dfrac {nk}{n}}\destra)}$
${\displaystyle \geq 1-m\sinistra(1-r\destra)}$${\displaystyle m}$${\displaystyle 2}$${\displaystyle r=r_{o}}$
${\displaystyle \left({\dfrac {K}{N}}\right)\geq 2r_{o}-1}$

Rivendicazione 2

${\displaystyle D\geq N\left({\dfrac {(\delta -({\dfrac {\lambda }{d}}))}{(1-({\dfrac {\lambda }{d}}) }})\destra)^{2}}$

${\displaystyle =N\left(\delta ^{2}-O\left({\dfrac {\lambda }{d}}\right)\right)}$ ${\displaystyle \rightarrow (1)}$

Se è il codice lineare della velocità , la lunghezza del codice a blocchi e la distanza relativa minima , e se è il grafico dell'incidenza del vertice del bordo di un grafo regolare con il secondo autovalore più grande , allora il codice ha almeno la velocità e almeno la distanza relativa minima .${\displaystyle S}$${\displaystyle r}$${\displaystyle d}$${\displaystyle \delta}$${\displaystyle B}$${\displaystyle d}$${\displaystyle \lambda}$${\displaystyle C(B,S)}$${\displaystyle 2r_{o}-1}$${\displaystyle \left(\left({\dfrac {\delta -\left({\dfrac {\lambda }{d}}\right)}}{1-\left({\dfrac {\lambda }{d} }\destra)}}\destra)\destra)^{2}}$

Prova

Sia derivato dal grafo regolare . Quindi, il numero di variabili di is e il numero di vincoli è . Secondo Alon-Chung, se è un sottoinsieme di vertici di dimensione , allora il numero di archi contenuti nel sottografo è indotto da in è al massimo . ${\displaystyle B}$${\displaystyle d}$${\displaystyle G}$${\displaystyle C(B,S)}$${\displaystyle \left({\dfrac {dn}{2}}\right)}$${\displaystyle n}$${\displaystyle X}$${\displaystyle G}$${\displaystyle \gamma n}$${\displaystyle X}$${\displaystyle G}$${\displaystyle \left({\dfrac {dn}{2}}\right)\left(\gamma ^{2}+({\dfrac {\lambda }{d}})\gamma \left(1-\ gamma \right)\right)}$

Di conseguenza, qualsiasi insieme di variabili avrà almeno dei vincoli come vicine. Quindi il numero medio di variabili per vincolo è:${\displaystyle \left({\dfrac {dn}{2}}\right)\left(\gamma ^{2}+\left({\dfrac {\lambda }{d}}\right)\gamma \left (1-\gamma \right)\right)}$${\displaystyle \gamma n}$${\displaystyle \left({\dfrac {({\dfrac {2nd}{2}})\left(\gamma ^{2}+({\dfrac {\lambda }{d}})\gamma \left( 1-\gamma \right)\right)}{\gamma n}}\right)}$ ${\displaystyle =d\left(\gamma +({\dfrac {\lambda }{d}})\left(1-\gamma\right)\right)}$ ${\displaystyle \rightarrow (2)}$

Quindi se , allora una parola di peso relativo , non può essere una parola in codice di . La disuguaglianza è soddisfatta per . Pertanto, non può avere un codice diverso da zero di peso relativo o inferiore. ${\displaystyle d\left(\gamma +({\dfrac {\lambda }{d}})\left(1-\gamma\right)\right)<\gamma d}$${\displaystyle \left(\gamma ^{2}+({\dfrac {\lambda }{d}})\gamma \left(1-\gamma \right)\right)}$${\displaystyle C(B,S)}$${\displaystyle (2)}$${\displaystyle \gamma <\left({\dfrac {1-({\dfrac {\lambda }{d}})}{\delta -({\dfrac {\lambda }{d}})}}\right )}$${\displaystyle C(B,S)}$${\displaystyle \left({\dfrac {\delta -({\dfrac {\lambda }{d}})}{1-({\dfrac {\lambda }{d}})}}\right)^{ 2}}$

In matrice , possiamo assumere che è limitato da . Per quei valori di in cui è primo dispari, ci sono costruzioni esplicite di sequenze di grafi bipartiti regolari con un numero arbitrariamente grande di vertici tale che ogni grafo nella sequenza è un grafo di Ramanujan . Si chiama grafico Ramanujan in quanto soddisfa la disuguaglianza . Alcune proprietà di espansione sono visibili nel grafico come la separazione tra gli autovalori e . Se il grafico è un grafico Ramanujan, allora quell'espressione diventerà alla fine man mano che diventa grande. ${\displaystyle G}$${\displaystyle \lambda /d}$${\displaystyle 1}$${\displaystyle d}$${\displaystyle d-1}$${\displaystyle d}$${\displaystyle G}$${\displaystyle \lambda (G)\leq 2{\sqrt {d-1}}}$${\displaystyle G}$${\displaystyle d}$${\displaystyle \lambda}$${\displaystyle G}$${\displaystyle (1)}$${\displaystyle 0}$${\displaystyle d}$

Algoritmo di Zemor

L'algoritmo di decodifica iterativo scritto di seguito si alterna tra i vertici e in e corregge la parola in codice di in e quindi passa a correggere la parola in codice in . Qui i bordi associati a un vertice su un lato di un grafico non sono incidenti con l'altro vertice su quel lato. In effetti, non importa in quale ordine, l'insieme di nodi e vengono elaborati. L'elaborazione dei vertici può essere eseguita anche in parallelo. ${\displaystyle A}$${\displaystyle B}$${\displaystyle G}$${\displaystyle C_{o}}$${\displaystyle A}$${\displaystyle C_{o}}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$

Il decoder sta per un decoder che recupera correttamente con qualsiasi parola di codice con meno di errori. ${\displaystyle \mathbb {D}:\mathbb {F} ^{d}\rightarrow C_{o}}$${\displaystyle C_{o}}$${\displaystyle \left({\dfrac {d}{2}}\right)}$

Algoritmo di decodifica

Parola ricevuta: Uscita:${\displaystyle w=(w_{e}),e\in E}$
${\displaystyle z\leftarrow w}$
For ${\displaystyle t\leftarrow 1}$ to ${\displaystyle m}$ do //${\displaystyle m}$ is the number of iterations
{ if (${\displaystyle t}$ is odd) // Here the algorithm will alternate between its two vertex sets.
${\displaystyle X\leftarrow A}$
else ${\displaystyle X\leftarrow B}$
Iteration ${\displaystyle t}$: For every ${\displaystyle v\in X}$, let ${\displaystyle (z)_{v}\leftarrow \mathbb {D} ((z)_{v})}$ // Decoding ${\displaystyle z_{v}}$ to its nearest codeword.
}
${\displaystyle z}$

Spiegazione dell'algoritmo

Poiché è bipartito, l'insieme dei vertici induce la partizione dell'insieme degli archi = . L'insieme induce un'altra partizione, = . ${\displaystyle G}$${\displaystyle A}$${\displaystyle E}$${\displaystyle \cup _{v\in A}E_{v}}$${\displaystyle B}$${\displaystyle E}$${\displaystyle \cup _{v\in B}E_{v}}$

Sia il vettore ricevuto e ricordalo . La prima iterazione dell'algoritmo consiste nell'applicare la decodifica completa per il codice indotta da per ogni . Ciò significa che per sostituire, per ogni , il vettore con uno dei codici più vicini di . Poiché i sottoinsiemi di archi sono disgiunti per , la decodifica di questi sottovettori di può essere eseguita in parallelo. ${\displaystyle con \{0,1\}^{N}}$${\displaystyle N=dn}$${\displaystyle E_{v}}$${\displaystyle v\in A}$${\displaystyle v\in A}$${\displaystyle \left(w_{v(1)},w_{v(2)},\ldots ,w_{v(d)}\right)}$${\displaystyle C_{o}}$${\displaystyle E_{v}}$${\displaystyle v\in A}$${\displaystyle n}$${\displaystyle w}$

L'iterazione produrrà un nuovo vettore . L'iterazione successiva consiste nell'applicare la procedura precedente a ma con sostituita da . In altre parole, consiste nel decodificare tutti i sottovettori indotti dai vertici di . Le prossime iterazioni ripetono questi due passaggi applicando alternativamente la decodifica parallela ai sottovettori indotti dai vertici di e ai sottovettori indotti dai vertici di . Nota: [Se e è il grafo bipartito completo, allora è un codice prodotto di con se stesso e l'algoritmo di cui sopra si riduce alla naturale decodifica iterativa dei codici prodotto]. ${\displaystyle z}$${\displaystyle z}$${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$
${\displaystyle d=n}$${\displaystyle G}$${\displaystyle C}$${\displaystyle C_{o}}$

Qui, il numero di iterazioni è . In generale, l'algoritmo di cui sopra può correggere una parola in codice il cui peso di Hamming non è superiore a quello per i valori di . Qui, l'algoritmo di decodifica è implementato come un circuito di dimensioni e profondità che restituisce la parola in codice dato che il vettore di errore ha un peso inferiore a . ${\displaystyle m}$${\displaystyle \left({\dfrac {(\log {n})}{\log(2-\alpha )}}\right)}$${\displaystyle ({\dfrac {1}{2}}).\alpha N\delta \left(({\dfrac {\delta }{2}})-({\dfrac {\lambda }{d}} )\right)=\left(({\dfrac {1}{4}}).\alpha N(\delta ^{2}-O({\dfrac {\lambda }{d}})\right)}$${\displaystyle \alpha <1}$${\displaystyle O(N\log {N})}$${\displaystyle O(\log {N})}$${\displaystyle \alpha N\delta ^{2}(1-\epsilon )/4}$

Teorema

Se è un grafo Ramanujan di grado sufficientemente alto, per qualsiasi , l'algoritmo di decodifica può correggere gli errori, in round (dove la notazione big nasconde una dipendenza da ). Questo può essere implementato in tempo lineare su un singolo processore; sui processori ogni round può essere implementato in tempo costante.${\displaystyle G}$${\displaystyle \alpha <1}$${\displaystyle ({\dfrac {\alpha \delta _{o}^{2}}{4}})(1-\in )N}$${\displaystyle O(\log {n})}$${\displaystyle O}$${\displaystyle\alpha}$${\displaystyle n}$

Prova

Poiché l'algoritmo di decodifica è insensibile al valore degli archi e per linearità, possiamo assumere che la parola di codice trasmessa sia il vettore di tutti zero. Lascia che il codice ricevuto sia . Viene considerato l'insieme dei bordi che ha un valore errato durante la decodifica. Qui per valore errato intendiamo in uno qualsiasi dei bit. Sia il valore iniziale del codice, siano i valori dopo first, second . . . fasi di decodifica. Qui, , e . Qui corrisponde a quei set di vertici che non sono stati in grado di decodificare con successo il loro codice nel round. Dall'algoritmo sopra come numero di vertici non riusciti verrà corretto in ogni iterazione. Possiamo dimostrare che è una successione decrescente. In effetti, . Come stiamo assumendo, , l'equazione di cui sopra è in una sequenza geometrica decrescente . Quindi, quando , sono necessari più di round. Inoltre, e se implementiamo l' arrotondamento nel tempo, il tempo di esecuzione sequenziale totale sarà lineare. ${\displaystyle w}$${\displaystyle 1}$${\displaystyle w=w^{0}}$${\displaystyle w^{1},w^{2},\ldots ,w^{t}}$${\displaystyle}$${\displaystyle X^{i}={e\in E|x_{e}^{i}=1}}$${\displaystyle S^{i}={v\in V^{i}|E_{v}\cap X^{i+1}!=\emptyset }}$${\displaystyle S^{i}}$${\displaystyle i^{th}}$${\displaystyle S^{1}<S^{0}}$${\displaystyle S^{0}>S^{1}>S^{2}>\cdots }$${\displaystyle |S_{i+1}|<=({\dfrac {1}{2-\alpha }})|S_{i}|}$${\displaystyle \alpha <1}$${\displaystyle |S_{i}|<n}$${\displaystyle log_{2-\alpha }n}$${\displaystyle \sum |S_{i}|=n\sum ({\dfrac {1}{(2-\alpha )^{i}}})=O(n)}$${\displaystyle i^{th}}$${\displaystyle O(|S_{i}|)}$

Svantaggi dell'algoritmo di Zemor

1. È un processo lungo poiché il numero di iterazioni necessarie nell'algoritmo del decodificatore è${\displaystyle m}$${\displaystyle [(\log {n})/(\log(2-\alpha ))]}$
2. L'algoritmo di decodifica di Zemor trova difficile decodificare le cancellazioni. Un modo dettagliato di come possiamo migliorare l'algoritmo è

dato dentro.

Guarda anche

• Codici di espansione
• Grafico abbronzante
• Codifica e decodifica in tempo lineare di codici a correzione di errore

Riferimenti