Decodificación de distancia mínima generalizada

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 borrados 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 tiene en cuenta la información que proporciona la decodificación de máxima verosimilitud (MLD). En otras palabras, en el algoritmo ingenuo, las palabras de código recibidas internas se tratan de la misma manera independientemente de la diferencia entre sus distancias de martillo . Intuitivamente, el decodificador externo debería tener una mayor confianza en los símbolos cuyas codificaciones internas están cerca de la palabra recibida. David Forneyen 1966 ideó un algoritmo mejor llamado decodificación de distancia mínima generalizada (GMD) que hace un mejor uso de esa información. Este método se logra midiendo la confianza de cada palabra de código recibida y borrando los símbolos cuya confianza está por debajo de un valor deseado. Y 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. Los dos primeros serán algoritmos aleatorios, mientras que el último será un algoritmo determinista .

Configuración

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

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

y sus distancias son y . Se puede lograr un código concatenado por donde finalmente tomaremos como código RS , que tiene un decodificador de errores y borrado, y , lo que a su vez implica que MLD en el código interno será polinomial en el tiempo.${\displaystyle D}$${\displaystyle d}$${\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}))}$${\displaystyle C_{\text{out}}(m)=((C_{\text{out}}(m)_{1},\ldots ,(m)_{N})).}$${\displaystyle C_{\text{out}}}$${\displaystyle K=O(\log N)}$${\displaystyle N}$

• Decodificación de máxima verosimilitud (MLD): MLD es un método de decodificación para códigos de corrección de errores, que genera la palabra de código más cercana a la palabra recibida en la distancia de Hamming. La función MLD denotada por se define como sigue. Por cada .${\displaystyle D_{MLD}:\Sigma ^{n}\to C}$${\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 en un espacio muestral es un mapeo de eventos de a números reales tal que para cualquier evento , y para dos eventos que se excluyen mutuamente y${\displaystyle \Pr }$${\displaystyle S}$${\displaystyle S}$${\displaystyle \Pr[A]\geq 0}$${\displaystyle A,\Pr[S]=1}$${\displaystyle \Pr[A\cup B]=\Pr[A]+\Pr[B]}$${\displaystyle A}$${\displaystyle B}$
• Valor esperado : el valor esperado de una variable aleatoria discreta es${\displaystyle X}$

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

Algoritmo aleatorizado

Considere la palabra recibida que fue corrompida por un canal ruidoso . La siguiente es la descripción del algoritmo para el caso general. En este algoritmo, podemos decodificar y simplemente declarando un borrado en cada posición incorrecta y ejecutando los errores y el algoritmo de decodificación de borrado en el vector resultante.${\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}$${\displaystyle C_{\text{out}}}$

Randomized_Decoder
Teniendo en cuenta: .${\displaystyle \mathbf {y} =(y_{1},\dots ,y_{N})\in [q^{n}]^{N}}$

1. Para cada , calcule .${\displaystyle 1\leq i\leq N}$${\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}$
2. Establecer .${\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{\tfrac {d}{2}})}$
3. Para cada , repita: Con probabilidad , establezca lo contrario .${\displaystyle 1\leq i\leq N}$${\displaystyle 2\omega _{i} \over d}$${\displaystyle y_{i}''\leftarrow ?,}$${\displaystyle y_{i}''=y_{i}'}$
4. Ejecute el algoritmo de errores y borrado para el .${\displaystyle C_{\text{out}}}$${\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}$

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

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

Lema 1. Sea válido el supuesto del teorema 1. Y si tiene errores y borrados (en comparación con ) después del Paso 1 , entonces${\displaystyle \mathbf {y} ''}$${\displaystyle e'}$${\displaystyle s'}$${\displaystyle \mathbf {c} }$${\displaystyle \mathbb {E} [2e'+s']<D.}$

Observación. Si , se generará el algoritmo del paso 2 . El lema anterior dice que en la expectativa, este es de hecho el caso. Tenga en cuenta que esto no es suficiente para demostrar el teorema 1 , pero puede ser crucial en el desarrollo de variaciones futuras del algoritmo.${\displaystyle 2e'+s'<D}$${\displaystyle \mathbf {c} }$

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

${\displaystyle \sum _{i=1}^{N}e_{i}<{\frac {Dd}{2}}\qquad \qquad (1)}$

A continuación para cada , definimos dos variables indicadoras :${\displaystyle 1\leq i\leq N}$

${\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 eso 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 expectativa, obtenemos

${\displaystyle \mathbb {E} [2e'+s']\leqslant {\frac {2}{d}}\sum _{i}e_{i}<D.}$

Para demostrar (2) consideramos dos casos: -th bloque está correctamente decodificado ( Caso 1 ), -th bloque está incorrectamente decodificado ( Caso 2 ):${\displaystyle i}$${\displaystyle i}$

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

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

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

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 hasta la mitad de su distancia de diseño.${\displaystyle C_{\text{out}}\circ C_{\text{in}}}$

Algoritmo aleatorio modificado

Tenga en cuenta que, en la versión anterior del algoritmo GMD en el paso "3", realmente no es necesario utilizar la aleatoriedad "nueva" para cada uno . Ahora creamos otra versión aleatoria del algoritmo GMD que usa la misma aleatoriedad para todos . Esta idea sigue el algoritmo siguiente.${\displaystyle i}$${\displaystyle i}$

Modified_Randomized_Decoder
Dado:, elegir al azar. Entonces cada para cada :${\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}$${\displaystyle \theta \in [0,1]}$${\displaystyle 1\leq i\leq N}$

1. Establecer .${\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 , establece lo contrario .${\displaystyle \theta <{\tfrac {2\omega _{i}}{d}}}$${\displaystyle y_{i}''\leftarrow ?,}$${\displaystyle y_{i}''=y_{i}'}$
4. Ejecute el algoritmo de errores y borrado para el .${\displaystyle C_{\text{out}}}$${\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 deriva de la elección de . La prueba del Lema 1 también se puede utilizar para mostrar la versión 2 de GMD. En la siguiente sección, veremos cómo obtener una versión determinista del algoritmo GMD eligiendo entre un conjunto de tamaño polinomial en contraposición al conjunto infinito actual .${\displaystyle \theta }$${\displaystyle \mathbb {E} [2e'+s']<D}$${\displaystyle \theta }$${\displaystyle [0,1]}$

Algoritmo determinista

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

${\displaystyle Q=\{0,1\}\cup \{q_{1},\ldots ,q_{m}\}}$

donde para algunos . Tenga en cuenta que para cada , el paso 1 de la segunda versión del algoritmo aleatorio genera lo mismo . Por lo tanto, debemos considerar todo el valor posible de . Esto da el algoritmo determinista a continuación.${\displaystyle q_{1}<\cdots <q_{m}}$${\displaystyle m\leq \left\lfloor {\frac {d}{2}}\right\rfloor }$${\displaystyle \theta \in [q_{i},q_{i+1}]}$${\displaystyle \mathbf {y} ''.}$${\displaystyle \theta \in Q}$

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

1. Calcular para .${\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}$${\displaystyle 1\leq i\leq N}$
2. Establecer para todos .${\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{d \over 2})}$${\displaystyle 1\leq i\leq N}$
3. Si , establece lo contrario .${\displaystyle \theta <{2\omega _{i} \over d}}$${\displaystyle y_{i}''\leftarrow ?,}$${\displaystyle y_{i}''=y_{i}'}$
4. Ejecute el algoritmo de errores y borrados para on . Sea la palabra de código correspondiente a la salida del algoritmo, si existe.${\displaystyle C_{\text{out}}}$${\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}$${\displaystyle c_{\theta }}$${\displaystyle C_{\text{out}}\circ C_{\text{in}}}$
5. Entre todas las salidas en 4, la salida más cercana a${\displaystyle c_{\theta }}$${\displaystyle \mathbf {y} }$

Cada ciclo de 1 ~ 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 errores lleva tiempo. Finalmente, el tiempo de ejecución del algoritmo anterior es donde está el tiempo de ejecución del decodificador de errores y borrados externos.${\displaystyle <dD/2}$${\displaystyle O(d)}$${\displaystyle O(NQn^{O(1)}+NT_{\text{out}})}$${\displaystyle T_{\text{out}}}$

Ver también

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

Referencias

• Notas de la conferencia de la Universidad de Buffalo sobre teoría de la codificación - Atri Rudra
• Notas de la conferencia del MIT sobre la teoría de la codificación esencial - Madhu Sudan
• Universidad de Washington - Venkatesan Guruswami
• G. David Forney. Decodificación de distancia mínima generalizada. Transacciones IEEE sobre teoría de la información , 12: 125-131, 1966