Decodificación generalizada de distancia mínima

En la teoría de la codificación , la decodificación de distancia mínima generalizada (GMD) proporciona un algoritmo eficiente para decodificar códigos concatenados , que se basa en el uso de un decodificador de errores y borraduras para el código externo .

Un algoritmo de decodificación ingenuo para códigos concatenados no puede ser una forma óptima de decodificación porque no toma en cuenta la información que proporciona la decodificación de máxima verosimilitud (MLD). En otras palabras, en el algoritmo ingenuo, las palabras clave internas recibidas se tratan de la misma manera, independientemente de la diferencia entre sus distancias de Hamming . Intuitivamente, el decodificador externo debería otorgar mayor confianza a los símbolos cuyas codificaciones internas están cerca de la palabra recibida. David Forney, en 1966, ideó un algoritmo mejor llamado decodificación de distancia mínima generalizada (GMD), que aprovecha mejor esa información. Este método se logra midiendo la confianza de cada palabra clave recibida y borrando los símbolos cuya confianza está por debajo de un valor deseado. El algoritmo de decodificación GMD fue uno de los primeros ejemplos de decodificadores de decisión suave . Presentaremos tres versiones del algoritmo de decodificación GMD. Las dos primeras serán algoritmos aleatorios, mientras que la última será un algoritmo determinista .

• Distancia de Hamming  : Dados dos vectores${\displaystyle u,v\in \Sigma ^{n}}$la distancia de Hamming entre${\displaystyle u}$y${\displaystyle v}$, denotado por${\displaystyle \Delta (u,v)}$, se define como el número de posiciones en las que${\displaystyle u}$y${\displaystyle v}$diferir de.
• Distancia mínima: Deje${\displaystyle C\subseteq \Sigma ^{n}}$ser un código . La distancia mínima del código${\displaystyle C}$se define como${\displaystyle d=\min \Delta (c_{1},c_{2})}$dónde${\displaystyle c_{1}\neq c_{2}\in C}$
• Concatenación de códigos: Dado${\displaystyle m=(m_{1},\cdots ,m_{K})\in [Q]^{K}}$Consideremos dos códigos que llamaremos código externo y código interno.

${\displaystyle C_{\text{out}}=[Q]^{K}\to [Q]^{N},\qquad C_{\text{in}}:[q]^{k}\to [q]^{n},}$

y sus distancias son${\displaystyle D}$y${\displaystyle d}$. Se puede obtener un código concatenado mediante${\displaystyle C_{\text{out}}\circ C_{\text{in}}(m)=(C_{\text{in}}(C_{\text{out}}(m)_{1}),\ldots ,C_{\text{in}}(C_{\text{out}}(m)_{N}))}$dónde${\displaystyle C_{\text{out}}(m)=((C_{\text{out}}(m)_{1},\ldots ,(m)_{N})).}$Finalmente tomaremos${\displaystyle C_{\text{salida}}}$ser código RS , que tiene un decodificador de errores y borrado, y${\displaystyle K=O(\log N)}$, lo que a su vez implica que MLD en el código interno será polinomial en${\displaystyle N}$tiempo.

• Decodificación de máxima verosimilitud (MLD): MLD es un método de decodificación para códigos de corrección de errores, que produce la palabra clave más cercana a la palabra recibida en distancia de Hamming. La función MLD se denota por${\displaystyle D_{MLD}:\Sigma ^{n}\to C}$se define de la siguiente manera. Para cada${\displaystyle y\in \Sigma ^{n},D_{MLD}(y)=\arg \min _{c\in C}\Delta (c,y)}$.
• Función de densidad de probabilidad  : Una distribución de probabilidad${\displaystyle \Pr }$en un espacio muestral${\displaystyle S}$es un mapeo de eventos de${\displaystyle S}$a números reales tales que${\displaystyle \Pr[A]\geq 0}$para cualquier evento${\displaystyle A,\Pr[S]=1}$, y${\displaystyle \Pr[A\cup B]=\Pr[A]+\Pr[B]}$para cualesquiera dos eventos mutuamente excluyentes${\displaystyle A}$y${\displaystyle B}$
• Valor esperado : El valor esperado de una variable aleatoria discreta.${\displaystyle X}$es

${\displaystyle \mathbb {E} [X]=\sum _{x}\Pr[X=x].}$

Considere la palabra recibida${\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}$que fue corrompido por un canal ruidoso . A continuación se describe el algoritmo para el caso general. En este algoritmo, podemos decodificar y simplemente declarando un borrado en cada posición defectuosa y ejecutando el algoritmo de decodificación de errores y borrados para${\displaystyle C_{\text{out}}}$sobre el vector resultante.

Decodificador aleatorio dado  :${\displaystyle \mathbf {y} =(y_{1},\dots ,y_{N})\in [q^{n}]^{N}}$.

1. Por cada${\displaystyle 1\leq i\leq N}$, calcular${\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}$.
2. Colocar${\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{\tfrac {d}{2}})}$.
3. Por cada${\displaystyle 1\leq i\leq N}$, repetir  : Con probabilidad${\displaystyle 2\omega _{i} \over d}$, colocar${\displaystyle y_{i}''\leftarrow$ ?,} de lo contrario establecer${\displaystyle y_{i}''=y_{i}'}$.
4. Errores de ejecución y algoritmo de borrado para${\displaystyle C_{\text{out}}}$en${\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}$.

Teorema 1. Sea y una palabra recibida tal que existe una palabra clave.${\displaystyle \mathbf {c} =(c_{1},\cdots ,c_{N})\in C_{\text{out}}\circ {C_{\text{in}}}\subseteq [q^{n}]^{N}}$de tal manera que${\displaystyle \Delta (\mathbf {c} ,\mathbf {y} )<{\tfrac {Dd}{2}}}$. Luego, el algoritmo GMD determinista produce:${\displaystyle \mathbf {c} }$.

Tenga en cuenta que un algoritmo de decodificación ingenuo para códigos concatenados puede corregir hasta${\displaystyle {\tfrac {Dd}{4}}}$errores.

Lema 1. Supongamos que se cumple la hipótesis del Teorema 1. Y si${\displaystyle \mathbf {y} ''}$tiene${\displaystyle e'}$errores y${\displaystyle s'}$borraduras (en comparación con${\displaystyle \mathbf {c} }$) después del Paso 1 , entonces${\displaystyle \mathbb {E} [2e'+s']<D.}$

Observación. Si${\displaystyle 2e'+s'<D}$, entonces el algoritmo del paso 2 generará la salida${\displaystyle \mathbf {c} }$El lema anterior afirma que, en promedio, esto es así. Cabe señalar que esto no basta para demostrar el Teorema 1 , pero puede ser crucial para desarrollar futuras variaciones del algoritmo.

Demostración del lema 1. Para cada${\displaystyle 1\leq i\leq N,}$definir${\displaystyle e_{i}=\Delta (y_{i},c_{i}).}$Esto implica que

$${\displaystyle \sum _{i=1}^{N}e_{i}<{\frac {Dd}{2}}\qquad \qquad (1)}$$ Siguiente para cada${\displaystyle 1\leq i\leq N}$, definimos dos variables indicadoras :

$${\displaystyle {\begin{aligned}X{_{i}^{?}}=1&\Leftrightarrow y_{i}''=?\\X{_{i}^{e}}=1&\Leftrightarrow C_{\text{in}}(y_{i}'')\neq c_{i}\ {\text{and}}\ y_{i}''\neq$$ ?\end{aligned}}} Afirmamos que hemos terminado si podemos demostrar que para cada${\displaystyle 1\leq i\leq N}$:

$${\displaystyle \mathbb {E} \left[2X{_{i}^{e}+X{_{i}^{?}}}\right]\leqslant {2e_{i} \over d}\qquad \qquad (2)}$$ Claramente, por definición

$${\displaystyle e'=\sum _{i}X_{i}^{e}\quad {\text{and}}\quad s'=\sum _{i}X_{i}^{?}.}$$ Además, por la linealidad de la esperanza, obtenemos

$${\displaystyle \mathbb {E} [2e'+s']\leqslant {\frac {2}{d}}\sum _{i}e_{i}<D.}$$ Para demostrar (2) consideramos dos casos:${\displaystyle i}$El bloque -ésimo se decodifica correctamente ( Caso 1 ), ${\displaystyle i}$El bloque -ésimo se decodifica incorrectamente ( Caso 2 ):

Caso 1:${\displaystyle (c_{i}=C_{\text{in}}(y_{i}'))}$

Tenga en cuenta que si${\displaystyle y_{i}''=?}$entonces${\displaystyle X_{i}^{e}=0}$, y${\displaystyle \Pr[y_{i}''=?]={\tfrac {2\omega _{i}}{d}}}$implica${\displaystyle \mathbb {E} [X_{i}^{?}]=\Pr[X_{i}^{?}=1]={\tfrac {2\omega _{i}}{d}},}$y${\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=0}$.

Además, por definición tenemos

$${\displaystyle \omega _{i}=\min \left(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{\tfrac {d}{2}}\right)\leqslant \Delta (C_{\text{in}}(y_{i}'),y_{i})=\Delta (c_{i},y_{i})=e_{i}}$$Caso 2:${\displaystyle (c_{i}\neq C_{\text{in}}(y_{i}'))}$

En este caso,${\displaystyle \mathbb {E} [X_{i}^{?}]={\tfrac {2\omega _{i}}{d}}}$y${\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=1-{\tfrac {2\omega _{i}}{d}}.}$

Desde${\displaystyle c_{i}\neq C_{\text{in}}(y_{i}'),e_{i}+\omega _{i}\geqslant d}$. Esto sigue a otro análisis de caso ^{[ 1 ]} cuando${\displaystyle (\omega _{i}=\Delta (C_{\text{in}}(y_{i}'),y_{i})<{\tfrac {d}{2}})}$O no.

Finalmente, esto implica

$${\displaystyle \mathbb {E} [2X_{i}^{e}+X_{i}^{?}]=2-{2\omega _{i} \over d}\leq {2e_{i} \over d}.}$$ En las siguientes secciones, finalmente mostraremos que la versión determinista del algoritmo anterior puede realizar una decodificación única de${\displaystyle C_{\text{out}}\circ C_{\text{in}}}$hasta la mitad de su distancia de diseño.

Tenga en cuenta que, en la versión anterior del algoritmo GMD en el paso "3", realmente no necesitamos usar aleatoriedad "nueva" para cada${\displaystyle i}$Ahora presentamos otra versión aleatoria del algoritmo GMD que utiliza la misma aleatoriedad para cada${\displaystyle i}$Esta idea sigue el siguiente algoritmo.

Decodificador aleatorio modificado dado  :${\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}$, elegir${\displaystyle \theta \in [0,1]}$al azar. Luego cada uno por cada${\displaystyle 1\leq i\leq N}$:

1. Colocar${\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}$.
2. Calcular${\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{d \over 2})}$.
3. Si${\displaystyle \theta <{\tfrac {2\omega _{i}}{d}}}$, colocar${\displaystyle y_{i}''\leftarrow$ ?,} de lo contrario establecer${\displaystyle y_{i}''=y_{i}'}$.
4. Errores de ejecución y algoritmo de borrado para${\displaystyle C_{\text{out}}}$en${\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}$.

Para la demostración del Lema 1 , solo usamos la aleatoriedad para mostrar que

$${\displaystyle \Pr[y_{i}''=?]={2\omega _{i} \over d}.}$$ En esta versión del algoritmo GMD, observamos que

$${\displaystyle \Pr[y_{i}''=?]=\Pr \left[\theta \in \left[0,{\tfrac {2\omega _{i}}{d}}\right]\right]={\tfrac {2\omega _{i}}{d}}.}$$ La segunda igualdad anterior se deduce de la elección de${\displaystyle \theta }$La demostración del Lema 1 también puede utilizarse para demostrar${\displaystyle \mathbb {E} [2e'+s']<D}$para la versión 2 de GMD. En la siguiente sección, veremos cómo obtener una versión determinista del algoritmo GMD eligiendo${\displaystyle \theta }$de un conjunto de tamaño polinomial en contraposición al conjunto infinito actual${\displaystyle [0,1]}$.

Dejar${\displaystyle Q=\{0,1\}\cup \{{2\omega _{1} \over d},\ldots ,{2\omega _{N} \over d}\}}$. Dado que para cada${\displaystyle i,\omega _{i}=\min(\Delta (\mathbf {y_{i}'} ,\mathbf {y_{i}} ),{d \over 2})}$, tenemos

$${\displaystyle Q=\{0,1\}\cup \{q_{1},\ldots ,q_{m}\}}$$ dónde${\displaystyle q_{1}<\cdots <q_{m}}$para algunos${\displaystyle m\leq \left\lfloor {\frac {d}{2}}\right\rfloor }$. Tenga en cuenta que para cada${\displaystyle \theta \in [q_{i},q_{i+1}]}$, el paso 1 de la segunda versión del algoritmo aleatorio produce el mismo resultado${\displaystyle \mathbf {y} ''.}$. Por lo tanto, necesitamos considerar todos los valores posibles de${\displaystyle \theta \in Q}$Esto da como resultado el algoritmo determinista que se muestra a continuación.

Decodificador_determinista Dado  :${\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}$, por cada${\displaystyle \theta \in Q}$, repita lo siguiente.

1. Calcular${\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}$para${\displaystyle 1\leq i\leq N}$.
2. Colocar${\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{d \over 2})}$por cada${\displaystyle 1\leq i\leq N}$.
3. Si${\displaystyle \theta <{2\omega _{i} \over d}}$, colocar${\displaystyle y_{i}''\leftarrow$ ?,} de lo contrario establecer${\displaystyle y_{i}''=y_{i}'}$.
4. Ejecutar el algoritmo de errores y borrados para${\displaystyle C_{\text{out}}}$en${\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}$. Dejar${\displaystyle c_{\theta }}$ser la palabra clave en${\displaystyle C_{\text{out}}\circ C_{\text{in}}}$correspondiente al resultado del algoritmo, si lo hubiera.
5. Entre todos los${\displaystyle c_{\theta }}$Salida en 4, salida la más cercana a${\displaystyle \mathbf {y} }$

Cada bucle de 1 a 4 se puede ejecutar en tiempo polinomial , el algoritmo anterior también se puede calcular en tiempo polinomial. Específicamente, cada llamada a un decodificador de errores y borrados de${\displaystyle <dD/2}$Los errores toman${\displaystyle O(d)}$tiempo. Finalmente, el tiempo de ejecución del algoritmo anterior es${\displaystyle O(NQn^{O(1)}+NT_{\text{out}})}$dónde${\displaystyle T_{\text{out}}}$es el tiempo de ejecución del decodificador de errores y borrados externos.

• Códigos concatenados
• Corrección de errores de Reed Solomon
• Algoritmo de Welch-Berlekamp

• Apuntes de clase de la Universidad de Buffalo sobre teoría de la codificación – Atri Rudra
• Apuntes de clase del MIT sobre teoría esencial de la codificación – Madhu Sudán
• Universidad de Washington – Venkatesan Guruswami
• G. David Forney. Decodificación generalizada de distancia mínima. IEEE Transactions on Information Theory , 12:125–131, 1966.