En la teoría de la codificación , la decodificación es el proceso de traducir los mensajes recibidos en palabras clave de un código dado . Ha habido muchos métodos comunes de mapear mensajes a palabras en clave. A menudo se utilizan para recuperar mensajes enviados a través de un canal ruidoso , como un canal simétrico binario .
Notación
se considera un código binario con la longitud; serán elementos de ; y es la distancia entre esos elementos.
Decodificación de observador ideal
A uno se le puede dar el mensaje , luego la decodificación del observador ideal genera la palabra de código. El proceso da como resultado esta solución:
Por ejemplo, una persona puede elegir la palabra clave que es más probable que se reciba como mensaje después de la transmisión.
Convenciones de decodificación
Cada palabra de código no tiene una posibilidad esperada: puede haber más de una palabra de código con la misma probabilidad de mutar en el mensaje recibido. En tal caso, el remitente y el (los) receptor (es) deben acordar de antemano una convención de decodificación. Las convenciones populares incluyen:
- Solicite que se vuelva a enviar la palabra en clave: solicitud de repetición automática .
- Elija cualquier palabra de código aleatoria del conjunto de palabras de código más probable que esté más cerca de eso.
- Si sigue otro código , marque los bits ambiguos de la palabra de código como borrados y espere que el código externo los elimine.
Decodificación de máxima verosimilitud
Dado un vector recibido la decodificación de máxima probabilidad elige una palabra de códigoque maximiza
- ,
es decir, la palabra en clave que maximiza la probabilidad de que fue recibido, dado que fue enviado. Si todas las palabras de código tienen la misma probabilidad de enviarse, este esquema es equivalente a la decodificación ideal del observador. De hecho, según el teorema de Bayes ,
Al arreglar , se reestructura y es constante ya que es igualmente probable que se envíen todas las palabras de código. Por lo tanto, se maximiza en función de la variable precisamente cuando se maximiza, y la afirmación sigue.
Al igual que con la decodificación de 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 puede modelarse como un problema de programación de números enteros . [1]
El algoritmo de decodificación de máxima verosimilitud es un ejemplo del problema de "marginar una función de producto" que se resuelve aplicando la ley distributiva generalizada . [2]
Decodificación de distancia mínima
Dada una palabra de código recibida , la decodificación de distancia mínima elige una palabra de códigopara minimizar la distancia de Hamming :
es decir, elija la palabra en clave que está lo más cerca posible de .
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
luego:
que (dado que p es menos de 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 asistido o automatizado usando 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:
- La probabilidad que se produzca un error es independiente de la posición del símbolo.
- 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 por un canal simétrico binario . Pueden no ser razonables 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.
Decodificación del síndrome
La decodificación de síndrome es un método muy eficaz para decodificar un código lineal en un canal ruidoso , es decir, uno en el que se cometen errores. En esencia, la decodificación de síndrome es una decodificación de distancia mínima utilizando una tabla de búsqueda reducida. Esto está permitido por la linealidad del código. [3]
Suponer que es un código lineal de longitud y distancia mínima con matriz de control de paridad . Entonces claramente es capaz de corregir hasta
errores cometidos por el canal (ya que si no más de se cometen errores, la decodificación de distancia mínima seguirá decodificando correctamente la palabra de código transmitida incorrectamente).
Ahora suponga que una palabra en clave se envía por el canal y el patrón de error ocurre. LuegoEsta recibido. 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
para todos . La decodificación del síndrome aprovecha la propiedad de la matriz de paridad que:
para todos . El síndrome de lo recibido se define como:
Para realizar la decodificación ML en un canal simétrico binario , uno tiene que buscar una tabla de tamaño precalculada, mapeo a .
Tenga en cuenta que esto ya tiene una complejidad significativamente menor que la de una decodificación de matriz estándar .
Sin embargo, bajo el supuesto de que no más de Se cometieron errores durante la transmisión, el receptor puede buscar el valor en una tabla de tamaño más reducida
Decodificación de listas
Decodificación del conjunto de información
Esta es una familia de métodos probabilísticos de Las Vegas , todos basados en la observación de que es más fácil adivinar suficientes posiciones libres de errores que adivinar todas las posiciones de error.
La forma más simple se debe a Prange: Let ser el matriz generadora de utilizado para la codificación. Seleccione columnas de al azar, y denotar por la correspondiente submatriz de . Con probabilidad razonable tendrá rango completo, lo que significa que si dejamos ser el subvector de las posiciones correspondientes de cualquier palabra de código de para un mensaje , podemos recuperarnos como . Por lo tanto, si tuviéramos suerte de que estos posiciones de la palabra recibida no contenía errores, y por lo tanto igualaba las posiciones de la palabra de código enviada, entonces podemos decodificar.
Si ocurrieron errores, la probabilidad de una selección de columnas tan afortunada viene dada por .
Este método ha sido mejorado de varias formas, por ejemplo, por Stern [4] y Canteaut y Sendrier. [5]
Máxima probabilidad de respuesta parcial
La máxima verosimilitud de respuesta parcial ( PRML ) es un método para convertir la señal analógica débil del cabezal de un disco magnético o unidad de cinta en una señal digital.
Decodificador de Viterbi
Un decodificador de Viterbi utiliza el algoritmo de Viterbi para decodificar un flujo de bits que se ha codificado mediante la corrección de errores hacia adelante basada en un código convolucional. La distancia de Hamming se utiliza como métrica para los decodificadores Viterbi de decisión difícil. La distancia euclidiana al cuadrado se utiliza como métrica para decodificadores de decisión suave.
Ver también
Referencias
- ^ Feldman, Jon; Wainwright, Martin J .; Karger, David R. (marzo de 2005). "Uso de la programación lineal para decodificar códigos lineales binarios". Transacciones IEEE sobre teoría de la información . 51 (3). págs. 954–972. doi : 10.1109 / TIT.2004.842696 .
- ^ Aji, Srinivas M .; McEliece, Robert J. (marzo de 2000). "La ley distributiva generalizada" (PDF) . Transacciones IEEE sobre teoría de la información . 46 (2): 325–343. doi : 10.1109 / 18.825794 .
- ^ Beutelspacher, Albrecht ; Rosenbaum, Ute (1998). Geometría proyectiva . Prensa de la Universidad de Cambridge . pag. 190. ISBN 0-521-48277-1.
- ^ Stern, Jacques (1989). "Un método para encontrar palabras en clave de poco peso". Teoría y aplicaciones de la codificación . Apuntes de conferencias en informática. 388 . Springer-Verlag . págs. 106-113. doi : 10.1007 / BFb0019850 . ISBN 978-3-540-51643-9.
- ^ Ohta, Kazuo; Pei, Dingyi, eds. (1998). Criptoanálisis del criptosistema original de McEliece . Avances en Criptología - ASIACRYPT'98 . Apuntes de conferencias en informática. 1514 . págs. 187–199. doi : 10.1007 / 3-540-49649-1 . ISBN 978-3-540-65109-3. S2CID 37257901 .
Otras lecturas
- Hill, Raymond (1986). Un primer curso de teoría de la codificación . Serie de Ciencias de la Computación y Matemáticas Aplicadas de Oxford. Prensa de la Universidad de Oxford . ISBN 978-0-19-853803-5.
- Pless, Vera (1982). Introducción a la teoría de los códigos correctores de errores . Serie Wiley-Interscience en matemáticas discretas. John Wiley e hijos . 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). 86 (2 ed.). Springer-Verlag . ISBN 978-3-540-54894-2.