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

En la teoría de codificación , los códigos de corrección de errores de ráfaga emplean métodos para corregir errores de ráfaga , que son errores que ocurren en muchos bits consecutivos en lugar de ocurrir en bits independientemente unos de otros.

Se han diseñado muchos códigos para corregir errores aleatorios . Sin embargo, a veces los canales pueden introducir errores que se localizan en un intervalo corto. Dichos errores se producen en ráfagas (denominados errores de ráfaga ) porque se producen en muchos bits consecutivos. Se pueden encontrar muchos ejemplos de errores de ráfaga en los medios de almacenamiento. Estos errores pueden deberse a daños físicos, como un rasguño en un disco o un rayo en el caso de los canales inalámbricos. No son independientes; tienden a estar concentrados espacialmente. Si un bit tiene un error, es probable que los bits adyacentes también puedan estar dañados. Los métodos utilizados para corregir errores aleatorios son ineficientes para corregir errores de ráfaga.

Una explosión de longitud ℓ ^[1]

Digamos que se transmite una palabra de código y se recibe como Entonces, el vector de error se denomina ráfaga de longitud si los componentes distintos de cero de están confinados a componentes consecutivos. Por ejemplo, es una ráfaga de longitud${\estilo de visualización C}$${\displaystyle Y=C+E.}$${\estilo de visualización E}$${\displaystyle \ell}$${\estilo de visualización E}$${\displaystyle \ell}$${\displaystyle E=(0{\textbf {1000011}}0)}$${\displaystyle \ell = 7.}$

Aunque esta definición es suficiente para describir qué es un error de ráfaga, la mayoría de las herramientas desarrolladas para la corrección de errores de ráfaga se basan en códigos cíclicos. Esto motiva nuestra siguiente definición.

Una ráfaga cíclica de longitud ℓ ^[1]

Un vector de error se denomina error de ráfaga cíclica de longitud si sus componentes distintos de cero están confinados a componentes cíclicamente consecutivos. Por ejemplo, el vector de error considerado anteriormente es una ráfaga cíclica de longitud , ya que consideramos que el error comienza en la posición y termina en la posición . Observe que los índices están basados ​​en , es decir, el primer elemento está en la posición .${\estilo de visualización E}$${\displaystyle \ell}$${\displaystyle \ell}$${\displaystyle E=(010000110)}$${\displaystyle \ell = 5}$${\estilo de visualización 6}$${\estilo de visualización 1}$${\estilo de visualización 0}$${\estilo de visualización 0}$

En el resto de este artículo, utilizaremos el término ráfaga para referirnos a una ráfaga cíclica, a menos que se indique lo contrario.

A menudo resulta útil tener una definición compacta de un error de ráfaga, que abarque no solo su longitud, sino también el patrón y la ubicación de dicho error. Definimos una descripción de ráfaga como una tupla donde 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 es la ubicación, en la palabra clave, donde se puede encontrar la ráfaga. ^[1]${\estilo de visualización (P,L)}$${\estilo de visualización P}$${\estilo de visualización L}$

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

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

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

Los códigos cíclicos se definen de la siguiente manera: piense en los símbolos como elementos en . Ahora, podemos pensar en las palabras como polinomios sobre donde los símbolos individuales de una palabra corresponden a los diferentes coeficientes del polinomio. Para definir un código cíclico, elegimos un polinomio fijo, llamado polinomio generador . Las palabras clave de este código cíclico son todos los polinomios que son divisibles por este polinomio generador.${\estilo de visualización q}$${\displaystyle \mathbb {F}_{q}}$${\displaystyle \mathbb {F}_{q},}$

Las palabras clave son polinomios de grado . Supongamos que el polinomio generador tiene grado . Los polinomios de grado que son divisibles por resultan de multiplicar por polinomios de grado . Tenemos tales polinomios. Cada uno de ellos corresponde a una palabra clave. Por lo tanto, para los códigos cíclicos.${\displaystyle \leqslant n-1}$${\estilo de visualización g(x)}$${\estilo de visualización r}$${\displaystyle \leqslant n-1}$${\estilo de visualización g(x)}$${\estilo de visualización g(x)}$${\displaystyle \leqslant n-1-r}$${\displaystyle q^{nr}}$${\displaystyle k=nr}$

Los códigos cíclicos pueden detectar todas las ráfagas de longitud hasta . Más adelante veremos que la capacidad de detección de errores de ráfaga de cualquier código está limitada desde arriba por . Los códigos cíclicos se consideran óptimos para la detección de errores de ráfaga ya que cumplen con este límite superior:${\displaystyle \ell=nk=r}$${\estilo de visualización (n,k)}$${\displaystyle \ell \leqslant nk}$

La prueba anterior sugiere un algoritmo simple para la detección/corrección de errores de ráfaga en códigos cíclicos: dada una palabra transmitida (es decir, un polinomio de grado ), calcule el resto de esta palabra cuando se divide por . Si el resto es cero (es decir, si la palabra es divisible por ), entonces es una palabra de código válida. De lo contrario, informe un error. Para corregir este error, reste este resto de la palabra transmitida. El resultado de la resta será divisible por (es decir, será una palabra de código válida).${\displaystyle \leqslant n-1}$${\estilo de visualización g(x)}$${\estilo de visualización g(x)}$${\estilo de visualización g(x)}$

Por el límite superior de detección de error de ráfaga ( ), sabemos que un código cíclico no puede detectar todas las ráfagas de longitud . Sin embargo, los códigos cíclicos pueden detectar la mayoría de las ráfagas de longitud . La razón es que la detección falla solo cuando la ráfaga es divisible por . En los alfabetos binarios, existen ráfagas de longitud . De ellas, solo son divisibles por . Por lo tanto, la probabilidad de falla de detección es muy pequeña ( ) suponiendo una distribución uniforme en todas las ráfagas de longitud .${\displaystyle \ell \leqslant nk=r}$${\displaystyle \ell >r}$${\estilo de visualización >r}$${\estilo de visualización g(x)}$${\displaystyle 2^{\ell -2}}$${\displaystyle \ell}$${\displaystyle 2^{\ell -2-r}}$${\estilo de visualización g(x)}$${\estilo de visualización 2^{-r}}$${\displaystyle \ell}$

Ahora consideramos un teorema fundamental sobre códigos cíclicos que ayudará a diseñar códigos de corrección de errores de ráfagas eficientes, categorizando las ráfagas en diferentes clases laterales.

Por límite superior, nos referimos a un límite en nuestra capacidad de detección de errores que nunca podemos ir más allá. Supongamos que queremos diseñar un código que pueda detectar todos los errores de ráfaga de longitud Una pregunta natural que nos hacemos es: dados y , ¿cuál es el máximo que nunca podemos alcanzar más allá? En otras palabras, ¿cuál es el límite superior en la longitud de las ráfagas que podemos detectar usando cualquier código? El siguiente teorema proporciona una respuesta a esta pregunta.${\estilo de visualización (n,k)}$${\displaystyle \leqslant \ell .}$${\estilo de visualización n}$${\estilo de visualización k}$${\displaystyle \ell}$${\displaystyle \ell}$${\estilo de visualización (n,k)}$

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

Un resultado más fuerte lo proporciona el límite de Rieger:

Definición. Un código de corrección de errores de ráfaga lineal que alcanza el límite de Rieger anterior se denomina código de corrección de errores de ráfaga óptimo.

Existe más de un límite superior para la tasa de código alcanzable de los códigos de bloque lineales para la corrección de ráfagas múltiples en fase (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, una restricción sobre la longitud mínima libre de errores o espacio dentro de cada ráfaga en 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. se llama redundancia del código y en una formulación alternativa para los límites de Abramson es${\displaystyle r=n-k}$${\displaystyle r\geqslant \lceil \log _{2}(n+1)\rceil +\ell -1.}$

Fuentes: ^{[3] [4] [5]}

Si bien los códigos cíclicos en general son herramientas poderosas para detectar errores de ráfaga, ahora consideraremos una familia de códigos cíclicos binarios llamados Códigos de Fuego, que poseen buenas capacidades de corrección de errores de ráfaga única. Por ráfaga única, digamos de longitud , queremos decir que todos los errores que posee una palabra de código recibida se encuentran dentro de un intervalo fijo de dígitos.${\displaystyle \ell }$${\displaystyle \ell }$

Sea un polinomio irreducible de grado sobre , y sea el período de . El período de , y de hecho de cualquier polinomio, se define como el menor entero positivo tal que Sea un entero positivo que satisface y no es divisible por , donde y son el grado y el período de , respectivamente. Defina el Código contra incendios mediante el siguiente polinomio generador :${\displaystyle p(x)}$${\displaystyle m}$${\displaystyle \mathbb {F} _{2}}$${\displaystyle p}$${\displaystyle p(x)}$${\displaystyle p(x)}$${\displaystyle r}$${\displaystyle p(x)|x^{r}-1.}$${\displaystyle \ell }$${\displaystyle \ell \leqslant m}$${\displaystyle 2\ell -1}$${\displaystyle p}$${\displaystyle m}$${\displaystyle p}$${\displaystyle p(x)}$${\displaystyle G}$$${\displaystyle g(x)=\left(x^{2\ell -1}+1\right)p(x).}$$

Demostraremos que es un código de corrección de ráfagas de errores.${\displaystyle G}$${\displaystyle \ell }$

Si podemos demostrar que todas las ráfagas de longitud o menos ocurren en diferentes clases laterales , podemos usarlas como líderes de clases laterales que forman patrones de error corregibles. La razón es simple: sabemos que cada clase lateral tiene una decodificación de síndrome única asociada con ella, y si todas las ráfagas de diferentes longitudes ocurren en diferentes clases laterales, entonces todas tienen síndromes únicos, lo que facilita la corrección de errores.${\displaystyle \ell }$

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

Observe que en la segunda manipulación, introdujimos el término . Se nos permite hacerlo, ya que los Códigos de Incendios operan en . Según nuestra suposición, es una palabra de código válida y, por lo tanto, debe ser un múltiplo de . Como se mencionó anteriormente, dado que los factores de son primos relativos, tiene que ser divisible por . Si observamos de cerca la última expresión derivada para , notamos que es divisible por (por el corolario del Lema 2). Por lo tanto, es divisible por o es . Aplicando nuevamente el teorema de la división, vemos que existe un polinomio con grado tal que:${\displaystyle 2x^{i+r}b(x)}$${\displaystyle \mathbb {F} _{2}}$${\displaystyle v(x)}$${\displaystyle g(x)}$${\displaystyle g(x)}$${\displaystyle v(x)}$${\displaystyle x^{2\ell -1}+1}$${\displaystyle v(x)}$${\displaystyle x^{g(2\ell -1)}+1}$${\displaystyle x^{2\ell -1}+1}$${\displaystyle a(x)+x^{b}b(x)}$${\displaystyle x^{2\ell -1}+1}$${\displaystyle 0}$${\displaystyle d(x)}$${\displaystyle \delta }$$${\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 Como podemos concluir que implica y . Observe que en la expansión: El término aparece, pero como , la expresión resultante no contiene , por lo tanto y posteriormente Esto requiere que , y . Podemos revisar aún más nuestra división de por para reflejar que es . Sustituyendo nuevamente en obtenemos,${\displaystyle b=2\ell -\ell _{2}+\delta .}$${\displaystyle \ell _{1},\ell _{2}\leqslant \ell }$${\displaystyle b\geqslant \ell +\delta ,}$${\displaystyle b>\ell -1}$${\displaystyle b>\delta }$$${\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).}$$${\displaystyle x^{b}}$${\displaystyle \delta <b<2\ell -1}$${\displaystyle d(x)(x^{2\ell -1}+1)}$${\displaystyle x^{b}}$${\displaystyle d(x)=0}$${\displaystyle a(x)+x^{b}b(x)=0.}$${\displaystyle b=0}$${\displaystyle a(x)=b(x)}$${\displaystyle j-i}$${\displaystyle g(2\ell -1)}$${\displaystyle b=0,}$${\displaystyle j-i=g(2\ell -1)}$${\displaystyle v(x)}$$${\displaystyle v(x)=x^{i}b(x)\left(x^{j-1}+1\right).}$$

Como , tenemos . Pero es irreducible, por lo tanto y deben ser primos entre sí. Como es una palabra de código, debe ser divisible por , ya que no puede ser divisible por . Por lo tanto, debe ser un múltiplo de . Pero también debe ser un múltiplo de , lo que implica que debe ser un múltiplo de pero esa es precisamente la longitud del bloque del código. Por lo tanto, no puede ser un múltiplo de ya que ambos son menores que . Por lo tanto, nuestra suposición de que es una palabra de código es incorrecta y, por lo tanto , y están en diferentes clases laterales, con síndromes únicos y, por lo tanto, corregibles.${\displaystyle \deg(b(x))=\ell _{2}-1<\ell }$${\displaystyle \deg(b(x))<\deg(p(x))=m}$${\displaystyle p(x)}$${\displaystyle b(x)}$${\displaystyle p(x)}$${\displaystyle v(x)}$${\displaystyle x^{j-1}+1}$${\displaystyle p(x)}$${\displaystyle x^{2\ell -1}+1}$${\displaystyle j-i}$${\displaystyle p}$${\displaystyle 2\ell -1}$${\displaystyle n={\text{lcm}}(2\ell -1,p)}$${\displaystyle j-i}$${\displaystyle n}$${\displaystyle n}$${\displaystyle v(x)}$${\displaystyle x^{i}a(x)}$${\displaystyle x^{j}b(x)}$

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

Ciertas familias de códigos, como Reed–Solomon , operan en tamaños de alfabeto mayores que el binario. Esta propiedad otorga a estos códigos potentes capacidades de corrección de errores en ráfagas. Consideremos un código que opera en . Cada símbolo del alfabeto puede representarse mediante bits. Si es un código Reed–Solomon sobre , podemos pensar en un código sobre .${\displaystyle \mathbb {F} _{2^{m}}}$${\displaystyle m}$${\displaystyle C}$${\displaystyle (n,k)}$${\displaystyle \mathbb {F} _{2^{m}}}$${\displaystyle C}$${\displaystyle [mn,mk]_{2}}$${\displaystyle \mathbb {F} _{2}}$

La razón por la que estos códigos son eficaces para la corrección de errores en ráfagas es que cada símbolo está representado por bits y, en general, es irrelevante cuántos de esos bits son erróneos; ya sea que un solo bit o todos los bits contengan errores, desde una perspectiva de decodificación sigue siendo un error de un solo símbolo. En otras palabras, dado que los errores en ráfagas tienden a ocurrir en grupos, existe una gran posibilidad de que varios errores binarios contribuyan a un solo error de símbolo.${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$

Tenga en cuenta que una ráfaga de errores puede afectar a la mayoría de los símbolos, y una ráfaga de puede afectar a la mayoría de los símbolos. Luego, una ráfaga de puede afectar a la mayoría de los símbolos; esto implica que un código de corrección de errores de símbolos puede corregir una ráfaga de longitud como máximo .${\displaystyle (m+1)}$${\displaystyle 2}$${\displaystyle 2m+1}$${\displaystyle 3}$${\displaystyle tm+1}$${\displaystyle t+1}$${\displaystyle t}$${\displaystyle (t-1)m+1}$

En general, un código Reed–Solomon corrector de errores puede corregir cualquier combinación de o menos ráfagas de longitud , además de poder corregir errores aleatorios en el peor de los casos.${\displaystyle t}$${\displaystyle \mathbb {F} _{2^{m}}}$$${\displaystyle {\frac {t}{1+\lfloor (l+m-2)/m\rfloor }}}$$${\displaystyle l}$${\displaystyle t}$

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

El entrelazado se utiliza para convertir códigos convolucionales de correctores de errores aleatorios a correctores de errores en ráfagas. La idea básica detrás del uso de códigos entrelazados es mezclar símbolos en el transmisor. Esto conduce a la aleatorización de ráfagas de errores recibidos que están ubicados cerca y luego podemos aplicar el análisis para un canal aleatorio. Por lo tanto, la función principal realizada por el entrelazador en el transmisor es alterar la secuencia de símbolos de entrada. En el receptor, el desentrelazador alterará la secuencia recibida para recuperar la secuencia original inalterada en el transmisor.

La siguiente figura muestra un intercalador de 4 x 3.

El entrelazador anterior se denomina entrelazador de bloques . En este caso, 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 una matriz. Generalmente, es la longitud de la palabra de código.${\displaystyle M\times N}$${\displaystyle N}$

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

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

Desventajas del entrelazador de bloques: Como se desprende de la figura, las columnas se leen secuencialmente, el receptor puede interpretar una sola fila solo después de recibir el mensaje completo y no antes. Además, el receptor requiere una cantidad considerable de memoria para almacenar los símbolos recibidos y tiene que almacenar el mensaje completo. Por lo tanto, estos factores dan lugar a dos inconvenientes, uno es la latencia y otro es el almacenamiento (cantidad bastante grande de memoria). Estos inconvenientes se pueden evitar utilizando el entrelazador convolucional descrito 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. La línea de retardo es básicamente un circuito electrónico utilizado para retrasar la señal durante un tiempo determinado. Sea el número de líneas de retardo y sea el número de símbolos introducidos por cada línea de retardo. Por lo tanto, la separación entre entradas consecutivas = símbolos. Sea la longitud de la palabra de código Por lo tanto, cada símbolo en la palabra de código de entrada estará en una línea de retardo distinta. Sea que se produzca un error de ráfaga de longitud. Dado que la separación entre símbolos consecutivos es el número de errores que puede contener la salida desentrelazada es Por el teorema anterior, para una capacidad de corrección de errores de hasta , la longitud de ráfaga máxima permitida es Para la longitud de ráfaga del decodificador puede fallar.${\displaystyle n}$${\displaystyle d}$${\displaystyle nd}$${\displaystyle \leqslant n.}$${\displaystyle \ell }$${\displaystyle nd,}$${\displaystyle {\tfrac {\ell }{nd+1}}.}$${\displaystyle t}$${\displaystyle (nd+1)(t-1).}$${\displaystyle (nd+1)(t-1)+1,}$

Eficiencia del entrelazador cruzado ( ):${\displaystyle \gamma }$ se obtiene tomando la relación entre la longitud de ráfaga en la que 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.}$$

Así, podemos formular lo siguiente:${\displaystyle \gamma }$$${\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 la conmutación 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 un máximo de aproximadamente la mitad del mensaje en el receptor para leer la primera fila. Esto reduce drásticamente el requisito de almacenamiento a la mitad. 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 es una buena mejora 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 error de bit con la misma facilidad con la 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 de ráfaga. ^[5] La aplicación más común de los códigos RS es, con diferencia, en los discos compactos. Además de la corrección de errores básica que proporcionan los códigos RS, un entrelazador cruzado proporciona protección contra los errores de ráfaga debidos a arañazos en el disco. ^[3]

El actual sistema de audio digital de discos compactos 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 en 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 de ~8 rev/s mientras se escanea en la parte interior de la pista a ~3,5 rev/s en la parte exterior. Los hoyos y las mesetas 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 canales de origen 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 integradas en los discos de usuario durante la reproducción: el canal
• Descodificación de las señales detectadas desde los discos del usuario

El proceso está sujeto tanto a errores de ráfaga como a errores aleatorios. ^[7] Los errores de ráfaga incluyen aquellos debidos al material del disco (defectos de la película reflectante de aluminio, bajo índice de reflexión del material transparente del disco), la producción del disco (fallas durante la formación del disco y el corte del disco, etc.), la manipulación del disco (rayones, generalmente finos, 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 vibración de la onda de señal reconstruida y la interferencia en la señal. CIRC ( código Reed-Solomon entrelazado cruzado ) 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 como se ve en la superficie del CD) y compensa ráfagas de errores de hasta 12 000 bits (8,5 mm) que pueden ser causadas por pequeños arañazos.

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

La entrada para el codificador consta de cuadros de entrada, cada uno de los cuales contiene 24 símbolos de 8 bits (12 muestras de 16 bits del conversor A/D, 6 de cada una de las fuentes de datos (sonido) izquierda y derecha). Un cuadro se puede representar mediante donde y son bytes de los canales izquierdo y derecho de la muestra del cuadro.${\displaystyle L_{1}R_{1}L_{2}R_{2}\ldots L_{6}R_{6}}$${\displaystyle L_{i}}$${\displaystyle R_{i}}$${\displaystyle i^{th}}$

Inicialmente, los bytes se permutan para formar nuevos cuadros representados por donde representan las muestras izquierda y derecha del cuadro después de 2 cuadros intermedios.${\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}}$${\displaystyle L_{i},R_{i}}$${\displaystyle i}$

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

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. Depende de los diseñadores individuales de sistemas de CD decidir sobre los métodos de decodificación y optimizar el rendimiento de sus productos. Al estar a una distancia mínima de 5 Los decodificadores D1, D2 pueden corregir cada uno una combinación de errores y borrados de manera que . ^[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 genera 28 borrados. El desentrelazador en la etapa siguiente distribuye estos borrados en 28 palabras de código D2. Nuevamente, en la mayoría de las soluciones, D2 está configurado para tratar solo los borrados (una solución más simple y menos costosa). Si se encontraran más de 4 borrados, D2 genera 24 borrados. Posteriormente, un sistema de ocultación de errores intenta interpolar (a partir de símbolos vecinos) en caso de símbolos incorregibles; en caso contrario, los sonidos correspondientes a dichos símbolos erróneos se silencian.${\displaystyle e}$${\displaystyle f}$${\displaystyle 2e+f<5}$

Rendimiento de CIRC: ^[7] CIRC oculta errores de busto largo 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 una cada 10 horas a una tasa de error de bit (BER) y 1000 muestras por minuto a BER = Muestras de error indetectables (clics): menos de una cada 750 horas a BER = e insignificante a BER = .${\displaystyle =10^{-4}}$${\displaystyle 10^{-3}}$${\displaystyle 10^{-3}}$${\displaystyle 10^{-4}}$

• Detección y corrección de errores
• Códigos de corrección de errores con retroalimentación
• Tasa de código
• Corrección de errores de Reed-Solomon