Métodos de decodificación

Algoritmos para decodificar mensajes

En teoría de codificación , la decodificación es el proceso de traducir los mensajes recibidos en palabras de código de un código determinado . Existen muchos métodos comunes para asignar mensajes a palabras de código. Estos se utilizan a menudo para recuperar mensajes enviados a través de un canal ruidoso , como un canal simétrico binario .

Notación

${\displaystyle C\subset \mathbb {F} _{2}^{n}}$se considera un código binario con la longitud ; serán elementos de ; y es la distancia entre esos elementos. ${\displaystyle n}$ ${\displaystyle x,y}$ ${\displaystyle \mathbb {F} _{2}^{n}}$ ${\displaystyle d(x,y)}$

Descodificación del observador ideal

Se puede dar el mensaje y luego el observador ideal decodifica el código y genera la palabra clave . El proceso da como resultado esta solución: ${\displaystyle x\in \mathbb {F} _{2}^{n}}$ ${\displaystyle y\in C}$

${\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}$

Por ejemplo, una persona puede elegir la palabra clave que tiene más probabilidades de recibirse como mensaje después de la transmisión. ${\displaystyle y}$ ${\displaystyle x}$

Convenciones de decodificación

Cada palabra clave no tiene una posibilidad esperada: puede haber más de una palabra clave con la misma probabilidad de mutar en el mensaje recibido. En tal caso, el emisor y el receptor deben acordar de antemano una convención de decodificación. Las convenciones más populares incluyen:

1. Solicitar que se vuelva a enviar la palabra clave – solicitud de repetición automática .
2. Elija cualquier palabra clave aleatoria del conjunto de palabras clave más probables que esté más cerca de esa.
3. Si sigue otro código , marque los bits ambiguos de la palabra clave como borrados y espere que el código externo los desambigüe.
4. Informar al sistema de un fallo de decodificación

Descodificación de máxima verosimilitud

Dado un vector recibido, la decodificación de máxima verosimilitud elige una palabra de código que maximiza ${\displaystyle x\in \mathbb {F} _{2}^{n}}$ ${\displaystyle y\in C}$

${\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}$,

es decir, la palabra clave que maximiza la probabilidad de que se haya recibido, dado que se envió. Si todas las palabras clave tienen la misma probabilidad de ser enviadas, entonces este esquema es equivalente a la decodificación del observador ideal. De hecho, por el teorema de Bayes , ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

${\displaystyle {\begin{aligned}\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})&{}={\frac {\mathbb {P} (x{\mbox{ received}},y{\mbox{ sent}})}{\mathbb {P} (y{\mbox{ sent}})}}\\&{}=\mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})\cdot {\frac {\mathbb {P} (x{\mbox{ received}})}{\mathbb {P} (y{\mbox{ sent}})}}.\end{aligned}}}$

Al fijar , se reestructura y es constante, ya que todas las palabras de código tienen la misma probabilidad de ser enviadas. Por lo tanto, se maximiza como una función de la variable precisamente cuando se maximiza, y la afirmación sigue. ${\displaystyle \mathbb {P} (x{\mbox{ received}})}$ ${\displaystyle x}$ ${\displaystyle \mathbb {P} (y{\mbox{ sent}})}$ ${\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}$ ${\displaystyle y}$ ${\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}$

Al igual que con la decodificación del observador ideal, se debe acordar una convención para la decodificación no única.

El problema de decodificación de máxima verosimilitud también se puede modelar como un problema de programación entera . ^[1]

El algoritmo de decodificación de máxima verosimilitud es un ejemplo del problema de "marginalizar una función producto" que se resuelve aplicando la ley distributiva generalizada . ^[2]

Descodificación de distancia mínima

Dada una palabra de código recibida , la decodificación de distancia mínima elige una palabra de código para minimizar la distancia de Hamming : ${\displaystyle x\in \mathbb {F} _{2}^{n}}$ ${\displaystyle y\in C}$

${\displaystyle d(x,y)=\#\{i:x_{i}\not =y_{i}\}}$

es decir, elija la palabra clave que sea lo más cercana posible a . ${\displaystyle y}$ ${\displaystyle x}$

Tenga en cuenta que si la probabilidad de error en un canal discreto sin memoria es estrictamente menor que la mitad, entonces la decodificación de distancia mínima es equivalente a la decodificación de máxima verosimilitud , ya que si ${\displaystyle p}$

${\displaystyle d(x,y)=d,\,}$

entonces:

${\displaystyle {\begin{aligned}\mathbb {P} (y{\mbox{ received}}\mid x{\mbox{ sent}})&{}=(1-p)^{n-d}\cdot p^{d}\\&{}=(1-p)^{n}\cdot \left({\frac {p}{1-p}}\right)^{d}\\\end{aligned}}}$

que (ya que p es menor que la mitad) se maximiza minimizando d .

La decodificación de distancia mínima también se conoce como decodificación del vecino más cercano . Puede ser asistida o automatizada mediante el uso de una matriz estándar . La decodificación de distancia mínima es un método de decodificación razonable cuando se cumplen las siguientes condiciones:

1. La probabilidad de que ocurra un error es independiente de la posición del símbolo. ${\displaystyle p}$
2. Los errores son eventos independientes: un error en una posición del mensaje no afecta a otras posiciones.

Estas suposiciones pueden ser razonables para transmisiones a través de un canal binario simétrico , pero pueden ser irrazonables para otros medios, como un DVD, donde un solo rasguño en el disco puede causar un error en muchos símbolos o palabras de código adyacentes.

Al igual que con otros métodos de decodificación, se debe acordar una convención para la decodificación no única.

Descodificación del síndrome

La decodificación de síndromes es un método muy eficiente para decodificar un código lineal en un canal ruidoso , es decir, en el que se cometen errores. En esencia, la decodificación de síndromes es una decodificación de distancia mínima utilizando una tabla de búsqueda reducida. Esto es posible gracias a la linealidad del código. ^[3]

Supongamos que es un código lineal de longitud y distancia mínima con matriz de comprobación de paridad . Entonces claramente es capaz de corregir hasta ${\displaystyle C\subset \mathbb {F} _{2}^{n}}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle H}$ ${\displaystyle C}$

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor }$

errores cometidos por el canal (ya que si no se cometen más de errores, la decodificación de distancia mínima decodificará correctamente la palabra de código transmitida incorrectamente). ${\displaystyle t}$

Ahora supongamos que se envía una palabra de código por el canal y se produce el patrón de error. Luego se recibe. La decodificación de distancia mínima ordinaria buscaría el vector en una tabla de tamaño para la coincidencia más cercana, es decir, un elemento (no necesariamente único) con ${\displaystyle x\in \mathbb {F} _{2}^{n}}$ ${\displaystyle e\in \mathbb {F} _{2}^{n}}$ ${\displaystyle z=x+e}$ ${\displaystyle z}$ ${\displaystyle |C|}$ ${\displaystyle c\in C}$

${\displaystyle d(c,z)\leq d(y,z)}$

Para todos . La decodificación del síndrome aprovecha la propiedad de la matriz de paridad que: ${\displaystyle y\in C}$

${\displaystyle Hx=0}$

Para todos . El síndrome del receptor se define como: ${\displaystyle x\in C}$ ${\displaystyle z=x+e}$

${\displaystyle Hz=H(x+e)=Hx+He=0+He=He}$

Para realizar la decodificación ML en un canal simétrico binario , es necesario consultar una tabla precalculada de tamaño , que se asigna a . ${\displaystyle 2^{n-k}}$ ${\displaystyle He}$ ${\displaystyle e}$

Tenga en cuenta que esto ya es significativamente menos complejo que la decodificación de una matriz estándar .

Sin embargo, suponiendo que no se hayan cometido más de 10 errores durante la transmisión, el receptor puede buscar el valor en una tabla de tamaño aún más reducida. ${\displaystyle t}$ ${\displaystyle He}$

${\displaystyle {\begin{matrix}\sum _{i=0}^{t}{\binom {n}{i}}\\\end{matrix}}}$

Descodificación de listas

Decodificación de conjuntos de información

Se trata de una familia de métodos probabilísticos de Las Vegas, todos ellos basados ​​en la observación de que es más fácil adivinar suficientes posiciones libres de errores que adivinar todas las posiciones con errores.

La forma más simple se debe a Prange: Sea la matriz generadora de utilizada para la codificación. Seleccione columnas de al azar y denote por la submatriz correspondiente de . Con una probabilidad razonable tendrá rango completo, lo que significa que si dejamos que sea el subvector para las posiciones correspondientes de cualquier palabra de código de para un mensaje , podemos recuperar como . Por lo tanto, si tuvimos suerte de que estas posiciones de la palabra recibida no contuvieran errores y, por lo tanto, fueran iguales a las posiciones de la palabra de código enviada, entonces podemos decodificar. ${\displaystyle G}$ ${\displaystyle k\times n}$ ${\displaystyle C}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle G'}$ ${\displaystyle G}$ ${\displaystyle G'}$ ${\displaystyle c'}$ ${\displaystyle c=mG}$ ${\displaystyle C}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m=c'G'^{-1}}$ ${\displaystyle k}$ ${\displaystyle y}$

Si se produjeron errores, la probabilidad de una selección tan afortunada de columnas viene dada por . ${\displaystyle t}$ ${\displaystyle \textstyle {\binom {n-t}{k}}/{\binom {n}{k}}}$

Este método ha sido mejorado de diversas maneras, por ejemplo por Stern ^[4] y Canteaut y Sendrier. ^[5]

Respuesta parcial de máxima verosimilitud

La respuesta parcial de máxima verosimilitud ( PRML ) es un método para convertir la señal analógica débil del cabezal de un disco magnético o una unidad de cinta en una señal digital.

Descodificador Viterbi

Un decodificador de Viterbi utiliza el algoritmo de Viterbi para decodificar un flujo de bits que se ha codificado utilizando corrección de errores hacia adelante basada en un código convolucional. La distancia de Hamming se utiliza como métrica para decodificadores de Viterbi de decisión dura. La distancia euclidiana al cuadrado se utiliza como métrica para decodificadores de decisión suave.

Algoritmo de decodificación de decisiones óptimas (ODDA)

Algoritmo de decodificación de decisión óptima (ODDA) para un sistema TWRC asimétrico. ^{[ aclaración necesaria ] [6]}

Véase también

• No me importa la alarma
• Detección y corrección de errores
• Entrada prohibida

Referencias

1. Feldman, Jon; Wainwright, Martin J.; Karger, David R. (marzo de 2005). "Uso de programación lineal para decodificar códigos lineales binarios". IEEE Transactions on Information Theory . 51 (3): 954–972. CiteSeerX  10.1.1.111.6585 . doi :10.1109/TIT.2004.842696. S2CID  3120399.
2. Aji, Srinivas M.; McEliece, Robert J. (marzo de 2000). "La ley distributiva generalizada" (PDF) . IEEE Transactions on Information Theory . 46 (2): 325–343. doi :10.1109/18.825794.
3. Beutelspacher, Albrecht ; Rosenbaum, Ute (1998). Geometría proyectiva . Prensa de la Universidad de Cambridge . pag. 190.ISBN​ 0-521-48277-1.
4. Stern, Jacques (1989). "Un método para encontrar palabras clave de poco peso". Coding Theory and Applications . Lecture Notes in Computer Science. Vol. 388. Springer-Verlag . págs. 106–113. doi :10.1007/BFb0019850. ISBN 978-3-540-51643-9.
5. Ohta, Kazuo; Pei, Dingyi, eds. (1998). Avances en criptología — ASIACRYPT'98 . Apuntes de clase en informática. Vol. 1514. págs. 187–199. doi :10.1007/3-540-49649-1. ISBN 978-3-540-65109-3. Número de identificación del sujeto  37257901.
6. Siamack Ghadimi (2020), Algoritmo de decodificación de decisión óptima (ODDA) para un sistema TWRC asimétrico; , Revista universal de ingeniería eléctrica y electrónica

Lectura adicional

• Hill, Raymond (1986). Un primer curso de teoría de la codificación . Oxford Applied Mathematics and Computing Science Series. Oxford University Press . ISBN 978-0-19-853803-5.
• Pless, Vera (1982). Introducción a la teoría de códigos correctores de errores . Serie Wiley-Interscience en Matemáticas Discretas. John Wiley & Sons . ISBN 978-0-471-08684-0.
• van Lint, Jacobus H. (1992). Introducción a la teoría de la codificación . Textos de posgrado en matemáticas (GTM). Vol. 86 (2.ª ed.). Springer-Verlag . ISBN. 978-3-540-54894-2.