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}}}$

This is a family of Las Vegas-probabilistic methods all based on the observation that it is easier to guess enough error-free positions, than it is to guess all the error-positions.

The simplest form is due to Prange: Let ${\displaystyle G}$ be the ${\displaystyle k\times n}$ generator matrix of ${\displaystyle C}$ used for encoding. Select ${\displaystyle k}$ columns of ${\displaystyle G}$ at random, and denote by ${\displaystyle G'}$ the corresponding submatrix of ${\displaystyle G}$. With reasonable probability ${\displaystyle G'}$ will have full rank, which means that if we let ${\displaystyle c'}$ be the sub-vector for the corresponding positions of any codeword ${\displaystyle c=mG}$ of ${\displaystyle C}$ for a message ${\displaystyle m}$, we can recover ${\displaystyle m}$ as ${\displaystyle m=c'G'^{-1}}$. Hence, if we were lucky that these ${\displaystyle k}$ positions of the received word ${\displaystyle y}$ contained no errors, and hence equalled the positions of the sent codeword, then we may decode.

If ${\displaystyle t}$ errors occurred, the probability of such a fortunate selection of columns is given by ${\displaystyle \textstyle {\binom {n-t}{k}}/{\binom {n}{k}}\approx \exp(-tk/n)}$.

This method has been improved in various ways, e.g. by Stern^[4] and Canteaut and Sendrier.^[5]

Partial response maximum likelihood (PRML) is a method for converting the weak analog signal from the head of a magnetic disk or tape drive into a digital signal.

A Viterbi decoder uses the Viterbi algorithm for decoding a bitstream that has been encoded using forward error correction based on a convolutional code. The Hamming distance is used as a metric for hard decision Viterbi decoders. The squaredEuclidean distance is used as a metric for soft decision decoders.

Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system.^[6]

• Don't care alarm
• Error detection and correction
• Forbidden input

• 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.