Métodos de decodificación

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

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

A uno se le puede dar el mensaje${\displaystyle x\in \mathbb {F} _{2}^{n}}$, entonces la decodificación del observador ideal genera la palabra clave.${\displaystyle y\in C}$El proceso da como resultado esta solución:

${\displaystyle \mathbb {P} (y{\mbox{ enviado}}\mid x{\mbox{ recibido}})}$

Por ejemplo, una persona puede elegir la palabra clave.${\displaystyle y}$que es más probable que se reciba como el mensaje${\displaystyle x}$después de la transmisión.

Dado un vector recibido${\displaystyle x\in \mathbb {F} _{2}^{n}}$La decodificación de máxima probabilidad elige una palabra clave.${\displaystyle y\in C}$que maximiza

${\displaystyle \mathbb {P} (x{\mbox{ recibido}}\mid y{\mbox{ enviado}})}$,

es decir, la palabra clave${\displaystyle y}$que maximiza la probabilidad de que${\displaystyle x}$fue recibido, dado que${\displaystyle y}$fue enviado. 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 {\begin{aligned}\mathbb {P} (x{\mbox{ recibido}}\mid y{\mbox{ enviado}})&{}={\frac {\mathbb {P} (x{\mbox{ recibido}},y{\mbox{ enviado}})}{\mathbb {P} (y{\mbox{ enviado}})}}\\&{}=\mathbb {P} (y{\mbox{ enviado}}\mid x{\mbox{ recibido}})\cdot {\frac {\mathbb {P} (x{\mbox{ recibido}})}{\mathbb {P} (y{\mbox{ enviado}})}}.\end{aligned}}}$

Al fijar${\displaystyle \mathbb {P} (x{\mbox{ recibido}})}$,${\displaystyle x}$se reestructura y ${\displaystyle \mathbb {P} (y{\mbox{ enviado}})}$es constante ya que todas las palabras clave tienen la misma probabilidad de ser enviadas. Por lo tanto, ${\displaystyle \mathbb {P} (x{\mbox{ recibido}}\mid y{\mbox{ enviado}})}$ se maximiza en función de la variable${\displaystyle y}$precisamente cuando ${\displaystyle \mathbb {P} (y{\mbox{ enviado}}\mid x{\mbox{ recibido}})}$ se maximiza y la reclamación se deriva de ello.

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 puede modelarse como un problema de programación entera . ^{[ 1 ]}

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

Dado un vector recibido${\displaystyle x\in \mathbb {F} _{2}^{n}}$La decodificación de distancia mínima elige una palabra clave .${\displaystyle y\in C}$para minimizar la distancia de Hamming :

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

Es decir, elige la palabra clave.${\displaystyle y}$que sea lo más cercano posible a${\displaystyle x}$.

Tenga en cuenta que si la probabilidad de error en un canal discreto sin memoria${\displaystyle p}$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 d(x,y)=d,\,}$

entonces:

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

lo cual (dado 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 realizarse con la ayuda de una matriz estándar o de forma automatizada . La decodificación de distancia mínima es un método de decodificación adecuado cuando se cumplen las siguientes condiciones:

1. La probabilidad${\displaystyle p}$Que se produzca un error es independiente de la posición del símbolo.
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 . Sin embargo, pueden resultar irrazonables para otros soportes, como un DVD , donde un solo arañazo en el disco puede provocar un error en muchos símbolos o códigos adyacentes.

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

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

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

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

errores cometidos por el canal (ya que si no más de${\displaystyle t}$Si se producen errores, la decodificación de distancia mínima seguirá decodificando correctamente la palabra clave transmitida incorrectamente.

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

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

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

${\displaystyle Hx=0}$

a pesar de${\displaystyle x\in C}$. El síndrome de los recibidos${\displaystyle z=x+e}$se define como:

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

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

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${\displaystyle t}$Se produjeron errores durante la transmisión, el receptor puede consultar el valor.${\displaystyle He}$en una tabla de tamaño aún más reducida

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

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 sin errores que adivinar todas las posiciones con errores.

La forma más simple se debe a Prange: Sea${\displaystyle G}$ser el${\displaystyle k\times n}$matriz generadora de${\displaystyle C}$Se utiliza para la codificación. Seleccionar${\displaystyle k}$columnas de${\displaystyle G}$al azar, y denotemos por${\displaystyle G'}$la submatriz correspondiente de${\displaystyle G}$Con una probabilidad razonable${\displaystyle G'}$tendrá rango completo, lo que significa que si dejamos${\displaystyle c'}$sea ​​el subvector para las posiciones correspondientes de cualquier palabra clave${\displaystyle c=mG}$de${\displaystyle C}$para un mensaje${\displaystyle m}$podemos recuperarnos${\displaystyle m}$como${\displaystyle m=c'G'^{-1}}$Por lo tanto, si tuviéramos la suerte de que estos${\displaystyle k}$posiciones de la palabra recibida${\displaystyle y}$No contenía errores y, por lo tanto, coincidía con las posiciones de la palabra clave enviada, entonces podemos decodificarla.

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

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

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

Un decodificador Viterbi utiliza el algoritmo Viterbi para decodificar una secuencia de bits codificada mediante 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 rígida. La distancia euclidiana al cuadrado se utiliza como métrica para los decodificadores de decisión flexible.

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

• Alarma de no importarme
• Detección y corrección de errores
• Entrada prohibida

• Hill, Raymond (1986). Un primer curso de teoría de la codificación . Serie de Matemáticas Aplicadas y Ciencias de la Computación de Oxford. Oxford University Press . 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 & 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.