Código de corrección de errores en ráfaga

A menudo es útil tener una definición compacta de un error de ráfaga, que abarque no solo su duración, sino también el patrón y la ubicación de dicho error. Definimos una descripción de ráfaga como una tupla.${\displaystyle (P,L)}$dónde${\displaystyle P}$es el patrón del error (es decir, la cadena de símbolos que comienza con la primera entrada distinta de cero en el patrón de error y termina con el último símbolo distinto de cero), y${\displaystyle L}$es la ubicación, en la palabra clave, donde se puede encontrar la ráfaga. ^{[ 1 ]}

Por ejemplo, la descripción de la ráfaga del patrón de error.${\displaystyle E=(010000110)}$es${\displaystyle D=(1000011,1)}$Nótese que dicha descripción no es única, porque${\displaystyle D'=(11001,6)}$describe el mismo error de ráfaga. En general, si el número de componentes distintos de cero en${\displaystyle E}$es${\displaystyle w}$, entonces${\displaystyle E}$tendrá${\displaystyle w}$diferentes descripciones de ráfaga, cada una comenzando en una entrada distinta de cero de${\displaystyle E}$Para remediar los problemas que surgen de la ambigüedad de las descripciones de ráfagas con el teorema que se presenta a continuación, sin embargo, antes de hacerlo necesitamos una definición.

Definición. El número de símbolos en un patrón de error determinado.${\displaystyle y,}$se denota por${\displaystyle \mathrm {longitud} (y).}$

Un corolario del teorema anterior es que no podemos tener dos descripciones distintas de ráfagas para ráfagas de longitud${\displaystyle {\tfrac {1}{2}}(n+1).}$

Por límite superior, nos referimos a un límite en nuestra capacidad de detección de errores que nunca podemos superar. Supongamos que queremos diseñar un${\displaystyle (n,k)}$código que puede detectar todos los errores de ráfaga de longitud${\displaystyle \leqslant \ell .}$Una pregunta natural que cabe plantearse es: dado${\displaystyle n}$y${\displaystyle k}$¿Cuál es el máximo?${\displaystyle \ell }$¿Qué es lo que nunca podremos superar? En otras palabras, ¿cuál es el límite superior de la longitud?${\displaystyle \ell }$de ráfagas que podemos detectar usando cualquier${\displaystyle (n,k)}$¿Código? El siguiente teorema proporciona una respuesta a esta pregunta.

Ahora repetimos la misma pregunta pero para la corrección de errores: dado${\displaystyle n}$y${\displaystyle k}$¿Cuál es el límite superior de la longitud?${\displaystyle \ell }$de ráfagas que podemos corregir usando cualquier${\displaystyle (n,k)}$¿Código? El siguiente teorema proporciona una respuesta preliminar a esta pregunta:

Un resultado más contundente lo proporciona la cota de Rieger:

Definición. Un código lineal de corrección de errores en ráfagas que alcanza la cota de Rieger mencionada anteriormente se denomina código óptimo de corrección de errores en ráfagas.

Existe más de un límite superior para la tasa de codificación alcanzable de los códigos de bloque lineales para la corrección de ráfagas de fase múltiple (MPBC). Uno de estos límites está restringido a una longitud máxima de ráfaga cíclica corregible dentro de cada subbloque, o equivalentemente, a una restricción sobre la longitud o brecha mínima libre de errores dentro de cada ráfaga de fase. Este límite, cuando se reduce al caso especial de un límite para la corrección de ráfaga única, es el límite de Abramson (un corolario del límite de Hamming para la corrección de errores de ráfaga) cuando la longitud de la ráfaga cíclica es menor que la mitad de la longitud del bloque. ^{[ 3 ]}

Observación.${\displaystyle r=n-k}$se denomina redundancia del código y en una formulación alternativa para los límites de Abramson es${\displaystyle r\geqslant \lceil \log _{2}(n+1)\rceil +\ell -1.}$

Dejar ${\displaystyle x^{i}a(x)}$y${\displaystyle x^{j}b(x)}$sean polinomios con grados ${\displaystyle \ell _{1}-1}$y${\displaystyle \ell _{2}-1}$, que representan ráfagas de longitud${\displaystyle \ell _{1}}$y ${\displaystyle \ell _{2}}$respectivamente con${\displaystyle \ell _{1},\ell _{2}\leqslant \ell .}$Los números enteros${\displaystyle i,j}$representan las posiciones iniciales de las ráfagas y son menores que la longitud del bloque del código. Por contradicción, supongamos que ${\displaystyle x^{i}a(x)}$y${\displaystyle x^{j}b(x)}$están en el mismo coset. Entonces,${\displaystyle v(x)=x^{i}a(x)+x^{j}b(x)}$es una palabra clave válida (ya que ambos términos están en la misma clase lateral). Sin pérdida de generalidad , elija${\displaystyle i\leqslant j}$Por el teorema de la división podemos escribir:${\displaystyle j-i=g(2\ell -1)+r,}$para números enteros${\displaystyle g}$y${\displaystyle r,0\leqslant r<2\ell -1}$. Reescribimos el polinomio${\displaystyle v(x)}$como sigue: $${\displaystyle v(x)=x^{i}a(x)+x^{i+g(2\ell -1)+r}=x^{i}a(x)+x^{i+g(2\ell -1)+r}+2x^{i+r}b(x)=x^{i}\left(a(x)+x^{b}b(x)\right)+x^{i+r}b(x)\left(x^{g(2\ell -1)}+1\right)}$$

Nótese que en la segunda manipulación, introdujimos el término ${\displaystyle 2x^{i+r}b(x)}$. Se nos permite hacerlo, ya que los códigos de incendios operan en ${\displaystyle \mathbb {F} _{2}}$. Según nuestra suposición,${\displaystyle v(x)}$es una palabra clave válida y, por lo tanto, debe ser un múltiplo de${\displaystyle g(x)}$. Como se mencionó anteriormente, dado que los factores de${\displaystyle g(x)}$son relativamente importantes,${\displaystyle v(x)}$tiene que ser divisible por${\displaystyle x^{2\ell -1}+1}$. Observando detenidamente la última expresión derivada para${\displaystyle v(x)}$observamos que${\displaystyle x^{g(2\ell -1)}+1}$es divisible por${\displaystyle x^{2\ell -1}+1}$(por el corolario del Lema 2). Por lo tanto,${\displaystyle a(x)+x^{b}b(x)}$es divisible por${\displaystyle x^{2\ell -1}+1}$o es${\displaystyle 0}$. Aplicando nuevamente el teorema de la división, vemos que existe un polinomio${\displaystyle d(x)}$con título${\displaystyle \delta }$de tal manera que: $${\displaystyle a(x)+x^{b}b(x)=d(x)(x^{2\ell -1}+1)}$$

Entonces podemos escribir: $${\displaystyle {\begin{aligned}\delta +2\ell -1&=\deg \left(d(x)\left(x^{2\ell -1}+1\right)\right)\\&=\deg \left(a(x)+x^{b}b(x)\right)\\&=\deg \left(x^{b}b(x)\right)&&\deg(a(x))=\ell _{1}-1<2\ell -1\\&=b+\ell _{2}-1\end{aligned}}}$$

Igualando el grado de ambos lados, obtenemos ${\displaystyle b=2\ell -\ell _{2}+\delta .}$Desde ${\displaystyle \ell _{1},\ell _{2}\leqslant \ell }$podemos concluir ${\displaystyle b\geqslant \ell +\delta ,}$lo cual implica ${\displaystyle b>\ell -1}$y ${\displaystyle b>\delta }$. Observe que en la expansión: $${\displaystyle a(x)+x^{b}b(x)=1+a_{1}x+a_{2}x^{2}+\dots +x^{\ell _{1}-1}+x^{b}\left(1+b_{1}x+b_{2}x^{2}+\dots +x^{\ell _{2}-1}\right).}$$ El término ${\displaystyle x^{b}}$aparece, pero desde ${\displaystyle \delta <b<2\ell -1}$, la expresión resultante${\displaystyle d(x)(x^{2\ell -1}+1)}$no contiene ${\displaystyle x^{b}}$, por lo tanto${\displaystyle d(x)=0}$y posteriormente${\displaystyle a(x)+x^{b}b(x)=0.}$Esto requiere que ${\displaystyle b=0}$, y ${\displaystyle a(x)=b(x)}$. Podemos revisar aún más nuestra división de${\displaystyle j-i}$por${\displaystyle g(2\ell -1)}$para reflejar${\displaystyle b=0,}$eso es${\displaystyle j-i=g(2\ell -1)}$. Sustituyendo de nuevo en${\displaystyle v(x)}$nos da, $${\displaystyle v(x)=x^{i}b(x)\left(x^{j-1}+1\right).}$$

Desde${\displaystyle \deg(b(x))=\ell _{2}-1<\ell }$, tenemos${\displaystyle \deg(b(x))<\deg(p(x))=m}$. Pero${\displaystyle p(x)}$es irreductible, por lo tanto ${\displaystyle b(x)}$y${\displaystyle p(x)}$debe ser relativamente primo. Dado que${\displaystyle v(x)}$es una palabra clave,${\displaystyle x^{j-1}+1}$debe ser divisible por${\displaystyle p(x)}$, ya que no puede ser divisible por${\displaystyle x^{2\ell -1}+1}$. Por lo tanto,${\displaystyle j-i}$debe ser un múltiplo de${\displaystyle p}$. Pero también debe ser un múltiplo de${\displaystyle 2\ell -1}$, lo que implica que debe ser un múltiplo de${\displaystyle n={\text{lcm}}(2\ell -1,p)}$pero esa es precisamente la longitud del bloque del código. Por lo tanto,${\displaystyle j-i}$no puede ser un múltiplo de${\displaystyle n}$ya que ambos son menores que${\displaystyle n}$. Por lo tanto, nuestra suposición de${\displaystyle v(x)}$ser una palabra clave es incorrecto y por lo tanto${\displaystyle x^{i}a(x)}$y${\displaystyle x^{j}b(x)}$se encuentran en diferentes grupos, con síndromes únicos y, por lo tanto, corregibles.

Con la teoría presentada en la sección anterior, considere la construcción de un ${\displaystyle 5}$Código de incendios con corrección de errores en ráfagas. Recuerde que para construir un código de incendios, necesitamos un polinomio irreducible.${\displaystyle p(x)}$, un número entero${\displaystyle \ell }$, que representa la capacidad de corrección de errores en ráfaga de nuestro código, y necesitamos satisfacer la propiedad de que ${\displaystyle 2\ell -1}$no es divisible por el período de${\displaystyle p(x)}$. Teniendo en cuenta estos requisitos, considere el polinomio irreducible${\displaystyle p(x)=1+x^{2}+x^{5}}$y dejar${\displaystyle \ell =5}$. Desde${\displaystyle p(x)}$es un polinomio primitivo, su período es${\displaystyle 2^{5}-1=31}$. Confirmamos que${\displaystyle 2\ell -1=9}$no es divisible por${\displaystyle 31}$. De este modo, $${\displaystyle g(x)=(x^{9}+1)\left(1+x^{2}+x^{5}\right)=1+x^{2}+x^{5}+x^{9}+x^{11}+x^{14}}$$ es un generador de códigos de incendios. Podemos calcular la longitud del bloque del código evaluando el mínimo común múltiplo de${\displaystyle p}$y${\displaystyle 2\ell -1}$. En otras palabras,${\displaystyle n={\text{lcm}}(9,31)=279}$. Por lo tanto, el Código de Fuego anterior es un código cíclico capaz de corregir cualquier ráfaga de longitud${\displaystyle 5}$o menos.

Dejar${\displaystyle G}$ser un${\displaystyle [255,223,33]}$Código RS sobre${\displaystyle \mathbb {F} _{2^{8}}}$Este código fue empleado por la NASA en su nave espacial Cassini-Huygens . ^{[ 6 ]} Es capaz de corregir${\displaystyle \lfloor 33/2\rfloor =16}$errores de símbolos. Ahora construimos un código RS binario.${\displaystyle G'}$de${\displaystyle G}$Cada símbolo se escribirá utilizando${\displaystyle \lceil \log _{2}(255)\rceil =8}$bits. Por lo tanto, el código binario RS tendrá${\displaystyle [2040,1784,33]_{2}}$como sus parámetros. Es capaz de corregir cualquier ráfaga única de longitud${\displaystyle l=121}$.

La siguiente figura muestra un intercalador de 4 por 3.

El entrelazador anterior se llama entrelazador de bloques . Aquí, los símbolos de entrada se escriben secuencialmente en las filas y los símbolos de salida se obtienen leyendo las columnas secuencialmente. Por lo tanto, tiene la forma de${\displaystyle M\times N}$matriz. Generalmente,${\displaystyle N}$es la longitud de la palabra clave.

Capacidad del entrelazador de bloques : Para un${\displaystyle M\times N}$intercalador de bloques y ráfaga de longitud${\displaystyle \ell ,}$El límite superior en el número de errores es${\displaystyle {\tfrac {\ell }{M}}.}$Esto es obvio por el hecho de que estamos leyendo la salida columna por columna y el número de filas es${\displaystyle M}$. Por el teorema anterior para la capacidad de corrección de errores hasta${\displaystyle t,}$La longitud máxima de ráfaga permitida es${\displaystyle Mt.}$Para la duración de ráfaga de${\displaystyle Mt+1}$, el decodificador puede fallar.

Eficiencia del entrelazador de bloques (${\displaystyle \gamma }$): Se encuentra tomando la relación de la longitud de la ráfaga donde el decodificador puede fallar a la memoria del entrelazador. Por lo tanto, podemos formular${\displaystyle \gamma }$como $${\displaystyle \gamma ={\frac {Mt+1}{MN}}\approx {\frac {t}{N}}.}$$

Desventajas del entrelazador de bloques  : Como se observa en la figura, las columnas se leen secuencialmente, por lo que el receptor solo puede interpretar una fila después de recibir el mensaje completo. Además, el receptor requiere una cantidad considerable de memoria para almacenar los símbolos recibidos y el mensaje completo. Por lo tanto, estos factores generan dos inconvenientes: la latencia y el almacenamiento (una cantidad considerable de memoria). Estos inconvenientes pueden evitarse utilizando el entrelazador convolucional que se describe a continuación.

El entrelazador cruzado es un tipo de sistema multiplexor-demultiplexor. En este sistema, se utilizan líneas de retardo para aumentar progresivamente la longitud. Una línea de retardo es básicamente un circuito electrónico que se utiliza para retrasar la señal durante un cierto período de tiempo.${\displaystyle n}$sea ​​el número de líneas de retardo y${\displaystyle d}$sea ​​el número de símbolos introducidos por cada línea de retardo. Por lo tanto, la separación entre entradas consecutivas =${\displaystyle nd}$símbolos. Sea la longitud de la palabra clave.${\displaystyle \leqslant n.}$Por lo tanto, cada símbolo en la palabra clave de entrada estará en una línea de retardo distinta. Sea un error de ráfaga de longitud${\displaystyle \ell }$ocurrir. Dado que la separación entre símbolos consecutivos es${\displaystyle nd,}$El número de errores que puede contener la salida desentrelazada es${\displaystyle {\tfrac {\ell }{nd+1}}.}$Según el teorema anterior, para una capacidad de corrección de errores de hasta${\displaystyle t}$, la longitud máxima de ráfaga permitida es${\displaystyle (nd+1)(t-1).}$Para la duración de ráfaga de${\displaystyle (nd+1)(t-1)+1,}$El decodificador puede fallar.

Eficiencia del entrelazador cruzado (${\displaystyle \gamma }$): Se obtiene tomando la relación entre la longitud de la ráfaga donde el decodificador puede fallar y la memoria del entrelazador. En este caso, la memoria del entrelazador se puede calcular como $${\displaystyle (0+1+2+3+\cdots +(n-1))d={\frac {n(n-1)}{2}}d.}$$

Por lo tanto, podemos formular${\displaystyle \gamma }$como sigue: $${\displaystyle \gamma ={\frac {(nd+1)(t-1)+1}{{\frac {n(n-1)}{2}}d}}.}$$

Rendimiento del entrelazador cruzado  : Como se muestra en la figura del entrelazador anterior, la salida no es más que los símbolos diagonales generados al final de cada línea de retardo. En este caso, cuando el conmutador del multiplexor de entrada completa aproximadamente la mitad de la conmutación, podemos leer la primera fila en el receptor. Por lo tanto, necesitamos almacenar como máximo la mitad del mensaje en el receptor para leer la primera fila. Esto reduce drásticamente a la mitad el requisito de almacenamiento. Dado que ahora solo se requiere la mitad del mensaje para leer la primera fila, la latencia también se reduce a la mitad, lo que supone una mejora considerable con respecto al entrelazador de bloques. Por lo tanto, la memoria total del entrelazador se divide entre el transmisor y el receptor.

Sin códigos de corrección de errores, el audio digital no sería técnicamente factible. ^{[ 7 ]} Los códigos Reed-Solomon pueden corregir un símbolo corrupto con un solo bit de error con la misma facilidad que pueden corregir un símbolo con todos los bits erróneos. Esto hace que los códigos RS sean particularmente adecuados para corregir errores en ráfaga. ^{[ 5 ]} La aplicación más común de los códigos RS se encuentra, con mucho, en los discos compactos. Además de la corrección de errores básica que proporcionan los códigos RS, un entrelazador cruzado ofrece protección contra errores en ráfaga debidos a arañazos en el disco. ^{[ 3 ]}

El sistema actual de audio digital en disco compacto fue desarrollado por NV Philips de los Países Bajos y Sony Corporation de Japón (acuerdo firmado en 1979).

Un disco compacto consta de un  disco aluminizado de 120 mm recubierto con una capa de plástico transparente, con una pista espiral de aproximadamente 5  km de longitud, que se escanea ópticamente mediante un láser de longitud de onda de ~0,8 μm a una velocidad constante de ~1,25  m/s. Para lograr esta velocidad constante, la rotación del disco varía desde ~8 rev/s durante el escaneo en la parte interior de la pista hasta ~3,5 rev/s en la parte exterior. Los hoyos y las llanuras son las depresiones (0,12 μm de profundidad) y los segmentos planos que constituyen los datos binarios a lo largo de la pista (0,6 μm de ancho). ^{[ 8 ]}

El proceso de CD se puede abstraer como una secuencia de los siguientes subprocesos:

• Codificación de canal de la fuente de señales
• Subprocesos mecánicos de preparación de un disco maestro, producción de discos de usuario y detección de las señales incrustadas en los discos de usuario durante la reproducción: el canal
• Decodificación de las señales detectadas desde los discos de usuario

El proceso está sujeto a errores de ráfaga y errores aleatorios. ^{[ 7 ]} Los errores de ráfaga incluyen aquellos debidos al material del disco (defectos de la película reflectante de aluminio, índice de reflectancia bajo del material del disco transparente), producción del disco (fallas durante la formación y corte del disco, etc.), manipulación del disco (rayas, generalmente delgadas, radiales y ortogonales a la dirección de grabación) y variaciones en el mecanismo de reproducción. Los errores aleatorios incluyen aquellos debidos a la fluctuación de la onda de señal reconstruida e interferencia en la señal. CIRC ( Cross-Interleaved Reed-Solomon code ) es la base para la detección y corrección de errores en el proceso de CD. Corrige ráfagas de errores de hasta 3500 bits en secuencia (2,4  mm de longitud vistos en la superficie del CD) y compensa las ráfagas de errores de hasta 12 000 bits (8,5  mm) que pueden ser causadas por rayones menores.

Codificación: Las ondas sonoras se muestrean y se convierten a formato digital mediante un convertidor A/D. La onda sonora se muestrea para obtener amplitud (a 44,1  kHz o 44.100 pares, uno para cada canal del sonido estéreo). A la amplitud en un instante se le asigna una cadena binaria de longitud 16. Por lo tanto, cada muestra produce dos vectores binarios a partir de${\displaystyle \mathbb {F} _{2}^{16}}$o 4${\displaystyle \mathbb {F} _{2}^{8}}$bytes de datos. Cada segundo de sonido grabado resulta en 44 100 × 32 = 1 411 200 bits (176 400 bytes) de datos. ^{[ 5 ]} El flujo de datos muestreados de 1,41 Mbit/s pasa a través del sistema de corrección de errores y finalmente se convierte en un flujo de 1,88 Mbit/s.   

La entrada para el codificador consiste en tramas de entrada, cada una de 24 símbolos de 8 bits (12 muestras de 16 bits del convertidor A/D, 6 de cada una de las fuentes de datos (sonido) izquierda y derecha). Una trama puede representarse mediante ${\displaystyle L_{1}R_{1}L_{2}R_{2}\ldots L_{6}R_{6}}$dónde${\displaystyle L_{i}}$y${\displaystyle R_{i}}$son bytes de los canales izquierdo y derecho del${\displaystyle i^{th}}$muestra del marco.

Inicialmente, los bytes se permutan para formar nuevos marcos representados por${\displaystyle L_{1}L_{3}L_{5}R_{1}R_{3}R_{5}L_{2}L_{4}L_{6}R_{2}R_{4}R_{6}}$dónde${\displaystyle L_{i},R_{i}}$representar${\displaystyle i}$-muestras izquierda y derecha del fotograma después de 2 fotogramas intermedios.

A continuación, estos 24 símbolos de mensaje se codifican utilizando el código Reed-Solomon C2 (28,24,5), que es un código RS abreviado.${\displaystyle \mathbb {F} _{256}}$. Esto es de corrección de dos errores, siendo de distancia mínima 5. Esto agrega 4 bytes de redundancia,${\displaystyle P_{1}P_{2}}$formando un nuevo marco:${\displaystyle L_{1}L_{3}L_{5}R_{1}R_{3}R_{5}P_{1}P_{2}L_{2}L_{4}L_{6}R_{2}R_{4}R_{6}}$La palabra clave resultante de 28 símbolos se pasa a través de un entrelazador cruzado (28.4), lo que da como resultado 28 símbolos entrelazados. Estos se pasan luego a través del código RS C1 (32,28,5), lo que da como resultado palabras clave de 32 símbolos de salida codificados. Se realiza una reagrupación adicional de los símbolos impares de una palabra clave con los símbolos pares de la siguiente palabra clave para romper cualquier ráfaga corta que aún pueda estar presente después del entrelazado de retardo de 4 tramas anterior. Por lo tanto, por cada 24 símbolos de entrada habrá 32 símbolos de salida que dan como resultado${\displaystyle R=24/32}$Finalmente, se agrega un byte de información de control y visualización. ^{[ 5 ]} Cada uno de los 33 bytes se convierte a 17 bits mediante EFM (modulación de ocho a catorce) y la adición de 3 bits de fusión. Por lo tanto, la trama de seis muestras resulta en 33 bytes ×  17 bits (561 bits) a los que se agregan 24 bits de sincronización y 3 bits de fusión, lo que da un total de 588 bits.

Decodificación: El reproductor de CD (decodificador CIRC) recibe el flujo de datos de 32 símbolos de salida. Este flujo pasa primero por el decodificador D1. Corresponde a los diseñadores individuales de sistemas de CD decidir los métodos de decodificación y optimizar el rendimiento de su producto. Al tener una distancia mínima de 5, los decodificadores D1 y D2 pueden corregir cada uno una combinación de${\displaystyle e}$errores y${\displaystyle f}$borrados tales que${\displaystyle 2e+f<5}$[ ^{5 ] En la mayoría de} las soluciones de decodificación, D1 está diseñado para corregir un solo error. Y en caso de más de 1 error, este decodificador emite 28 borraduras. El desentrelazador en la etapa subsiguiente distribuye estas borraduras en 28 palabras clave D2. Nuevamente, en la mayoría de las soluciones, D2 está configurado para manejar solo borraduras (una solución más simple y menos costosa). Si se encontraran más de 4 borraduras, D2 emitiría 24 borraduras. Posteriormente, un sistema de ocultación de errores intenta interpolar (a partir de símbolos vecinos) en caso de símbolos no corregibles, lo que falla, los sonidos correspondientes a dichos símbolos erróneos se silencian.

Rendimiento de CIRC: ^{[ 7 ]} CIRC oculta errores de ráfaga largos mediante interpolación lineal simple . 2,5  mm de longitud de pista (4000 bits) es la longitud máxima de ráfaga completamente corregible. 7,7  mm de longitud de pista (12 300 bits) es la longitud máxima de ráfaga que se puede interpolar. La tasa de interpolación de muestras es de una cada 10 horas a la tasa de error de bits (BER).${\displaystyle =10^{-4}}$y 1000 muestras por minuto a BER =${\displaystyle 10^{-3}}$Muestras de error indetectables (clics): menos de una cada 750 horas a BER =${\displaystyle 10^{-3}}$y despreciable en BER =${\displaystyle 10^{-4}}$.