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

Códigos destinados a corregir errores cortos y contiguos en un canal de comunicaciones.

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

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

Definiciones

Una ráfaga de longitud 5

Una ráfaga 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 ${\displaystyle C}$ ${\displaystyle Y=C+E.}$ ${\displaystyle E}$ ${\displaystyle \ell }$ ${\displaystyle 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 se limitan 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 . ${\displaystyle E}$ ${\displaystyle \ell }$ ${\displaystyle \ell }$ ${\displaystyle E=(010000110)}$ ${\displaystyle \ell =5}$ ${\displaystyle 6}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 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.

Descripción de la ráfaga

A menudo resulta útil tener una definición compacta de error de ráfaga, que abarque no sólo 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 el palabra clave, donde se puede encontrar la ráfaga. ^[1] ${\displaystyle (P,L)}$ ${\displaystyle P}$ ${\displaystyle L}$

Por ejemplo, la descripción en ráfaga del patrón de error es . Tenga en cuenta 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 es , tendrá diferentes descripciones de ráfaga, cada una de las cuales comenzará en una entrada diferente de cero de . Sin embargo, para remediar los problemas que surgen por la ambigüedad de las descripciones de ráfagas con el siguiente teorema, antes de hacerlo necesitamos una definición. ${\displaystyle E=(010000110)}$ ${\displaystyle D=(1000011,1)}$ ${\displaystyle D'=(11001,6)}$ ${\displaystyle E}$ ${\displaystyle w}$ ${\displaystyle E}$ ${\displaystyle w}$ ${\displaystyle E}$

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

Teorema (singularidad de las descripciones de ráfagas)  :  supongamos que es un vector de error de longitud con dos descripciones de ráfagas y . Entonces , si las dos descripciones son idénticas, sus componentes son equivalentes. ^[2] ${\displaystyle E}$ ${\displaystyle n}$ ${\displaystyle (P_{1},L_{1})}$ ${\displaystyle (P_{2},L_{2})}$ ${\displaystyle \mathrm {length} (P_{1})+\mathrm {length} (P_{2})\leqslant n+1,}$

Prueba

Sea el peso de Hamming (o el número de entradas distintas de cero) de . Entonces tiene exactamente descripciones de errores. Porque no hay nada que demostrar. Entonces asumimos que las descripciones no son idénticas. Observamos que cada entrada distinta de cero aparecerá en el patrón y, por lo tanto, los componentes de no incluidos en el patrón formarán una serie cíclica de ceros, comenzando después de la última entrada distinta de cero y continuando justo antes de la primera entrada distinta de cero del patrón. . Al conjunto de índices correspondientes a esta ejecución lo llamamos ejecución cero. Inmediatamente observamos que cada descripción de ráfaga tiene una ejecución cero asociada y que cada ejecución cero es disjunta. Dado que tenemos cero ejecuciones y cada una es disjunta, tenemos un total de elementos distintos en todas las ejecuciones cero. Por otro lado tenemos: ${\displaystyle w}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle w}$ ${\displaystyle w=0,1,}$ ${\displaystyle w\geqslant 2}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle w}$ ${\displaystyle n-w}$

$${\displaystyle {\begin{aligned}n-w={\text{number of zeros in }}E&\geqslant (n-\mathrm {length} (P_{1}))+(n-\mathrm {length} (P_{2}))\\&=2n-\left(\mathrm {length} (P_{1})+\mathrm {length} (P_{2})\right)\\&\geqslant 2n-(n+1)&&\mathrm {length} (P_{1})+\mathrm {length} (P_{2})\leqslant n+1\\&=n-1\end{aligned}}}$$

Esto contradice. Por tanto, las descripciones de errores de ráfaga son idénticas. ${\displaystyle w\geqslant 2.}$

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

Códigos cíclicos para corrección de errores en ráfaga

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 dónde 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 de código de este código cíclico son todos los polinomios que son divisibles por este polinomio generador. ${\displaystyle q}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \mathbb {F} _{q},}$

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

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 en 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 en ráfagas ya que cumplen con este límite superior: ${\displaystyle \ell =n-k=r}$ ${\displaystyle (n,k)}$ ${\displaystyle \ell \leqslant n-k}$

Teorema (capacidad de corrección de ráfagas cíclicas)  :  cada código cíclico con polinomio generador de grado puede detectar todas las ráfagas de longitud ${\displaystyle r}$ ${\displaystyle \leqslant r.}$

Prueba

Necesitamos demostrar que si agrega una ráfaga de longitud a una palabra en clave (es decir, a un polinomio que es divisible por ), entonces el resultado no será una palabra en clave (es decir, el polinomio correspondiente no es divisible por ). Basta demostrar que ninguna explosión de longitud es divisible por . Tal explosión tiene la forma , donde por lo tanto, no es divisible por (porque este último tiene grado ). no es divisible por (de lo contrario, todas las palabras en código comenzarían con ). Por lo tanto, tampoco es divisible por . ${\displaystyle \leqslant r}$ ${\displaystyle g(x)}$ ${\displaystyle g(x)}$ ${\displaystyle \leqslant r}$ ${\displaystyle g(x)}$ ${\displaystyle x^{i}b(x)}$ ${\displaystyle \deg(b(x))<r.}$ ${\displaystyle b(x)}$ ${\displaystyle g(x)}$ ${\displaystyle r}$ ${\displaystyle g(x)}$ ${\displaystyle x}$ ${\displaystyle 0}$ ${\displaystyle x^{i}}$ ${\displaystyle g(x)}$

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 clave 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 clave válida). ${\displaystyle \leqslant n-1}$ ${\displaystyle g(x)}$ ${\displaystyle g(x)}$ ${\displaystyle g(x)}$

Por el límite superior de detección de errores en ráfagas ( ), 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 sólo cuando la ráfaga es divisible por . En los alfabetos binarios, existen ráfagas de longitud . De ellos, sólo 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 n-k=r}$ ${\displaystyle \ell >r}$ ${\displaystyle >r}$ ${\displaystyle g(x)}$ ${\displaystyle 2^{\ell -2}}$ ${\displaystyle \ell }$ ${\displaystyle 2^{\ell -2-r}}$ ${\displaystyle g(x)}$ ${\displaystyle 2^{-r}}$ ${\displaystyle \ell }$

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

Teorema ( conjuntos laterales distintos )  :  un código lineal es un código de corrección de errores de ráfaga si todos los errores de ráfaga de longitud se encuentran en conjuntos laterales distintos de . ${\displaystyle C}$ ${\displaystyle \ell }$ ${\displaystyle \leqslant \ell }$ ${\displaystyle C}$

Prueba

Sean distintos errores de ráfaga de longitud que se encuentran en la misma clase lateral de código . Entonces es una palabra clave. Por lo tanto, si lo recibimos podemos decodificarlo a o . Por el contrario, si todos los errores de ráfaga no se encuentran en la misma clase lateral, entonces cada error de ráfaga está determinado por su síndrome. Luego, el error puede corregirse mediante su síndrome. Por lo tanto, un código lineal es un código de corrección de errores de ráfaga si y sólo si todos los errores de ráfaga de longitud se encuentran en clases laterales distintas de . ${\displaystyle \mathbf {e} _{1},\mathbf {e} _{2}}$ ${\displaystyle \leqslant \ell }$ ${\displaystyle C}$ ${\displaystyle \mathbf {c} =\mathbf {e} _{1}-\mathbf {e} _{2}}$ ${\displaystyle \mathbf {e} _{1},}$ ${\displaystyle \mathbf {0} }$ ${\displaystyle \mathbf {c} }$ ${\displaystyle \mathbf {e} _{1}}$ ${\displaystyle \mathbf {e} _{2}}$ ${\displaystyle C}$ ${\displaystyle \ell }$ ${\displaystyle \leqslant \ell }$ ${\displaystyle C}$

Teorema (clasificación de palabras clave de error de ráfaga)  :  sea un código lineal de corrección de errores de ráfaga. Entonces, ninguna ráfaga de longitud distinta de cero puede ser una palabra clave. ${\displaystyle C}$ ${\displaystyle \ell }$ ${\displaystyle \leqslant 2\ell }$

Prueba

Sea una palabra en clave con una ráfaga de longitud . Por lo tanto, tiene el patrón , donde y son palabras de longitud. Por lo tanto, las palabras y son dos ráfagas de longitud . Para códigos lineales binarios, pertenecen a la misma clase lateral. Esto contradice el teorema de las clases laterales distintas, por lo que ninguna ráfaga de longitud distinta de cero puede ser una palabra clave. ${\displaystyle c}$ ${\displaystyle \leqslant 2\ell }$ ${\displaystyle (0,1,u,v,1,0)}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \leqslant \ell -1.}$ ${\displaystyle w=(0,1,u,0,0,0)}$ ${\displaystyle c-w=(0,0,0,v,1,0)}$ ${\displaystyle \leqslant \ell }$ ${\displaystyle \leqslant 2\ell }$

Límites de corrección de errores de ráfaga

Límites superiores de detección y corrección de errores de ráfaga

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

Teorema (capacidad de detección de errores en ráfaga)  :  la capacidad de detección de errores en ráfagas de cualquier código es ${\displaystyle (n,k)}$ ${\displaystyle \ell \leqslant n-k.}$

Prueba

Primero observamos que un código puede detectar todas las ráfagas de longitud si y sólo si no hay dos palabras de código que difieran en una ráfaga de longitud . Supongamos que tenemos dos palabras de código y que se diferencian por una ráfaga de longitud . Al recibir , no podemos decir si la palabra transmitida realmente no tiene errores de transmisión o si tiene un error de ráfaga que ocurrió durante la transmisión. Ahora, supongamos que cada dos palabras de código difieren en más de una ráfaga de longitud. Incluso si la palabra de código transmitida se ve afectada por una ráfaga de longitud , no cambiará a otra palabra de código válida. Al recibirlo, podemos decir que se trata de una ráfaga. Por la observación anterior, sabemos que no hay dos palabras en código que puedan compartir los primeros símbolos. La razón es que incluso si difieren en todos los demás símbolos, seguirán siendo diferentes en una ráfaga de longitud. Por lo tanto, el número de palabras en código satisface Aplicando a ambos lados y reorganizando, podemos ver eso . ${\displaystyle \leqslant \ell }$ ${\displaystyle \leqslant \ell }$ ${\displaystyle \mathbf {c} _{1}}$ ${\displaystyle \mathbf {c} _{2}}$ ${\displaystyle \mathbf {b} }$ ${\displaystyle \leqslant \ell }$ ${\displaystyle \mathbf {c} _{1}}$ ${\displaystyle \mathbf {c} _{1}}$ ${\displaystyle \mathbf {c} _{2}}$ ${\displaystyle \mathbf {b} }$ ${\displaystyle \ell .}$ ${\displaystyle \mathbf {c} _{1}}$ ${\displaystyle \mathbf {b} }$ ${\displaystyle \ell }$ ${\displaystyle \mathbf {c} _{1}}$ ${\displaystyle \mathbf {b} .}$ ${\displaystyle n-\ell }$ ${\displaystyle \ell }$ ${\displaystyle \ell .}$ ${\displaystyle q^{k}}$ ${\displaystyle q^{k}\leqslant q^{n-\ell }.}$ ${\displaystyle \log _{q}}$ ${\displaystyle \ell \leqslant n-k}$

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

Teorema (capacidad de corrección de errores en ráfaga)  :  la capacidad de corrección de errores en ráfagas de cualquier código satisface ${\displaystyle (n,k)}$ ${\displaystyle \ell \leqslant n-k-\log _{q}(n-\ell )+2}$

Prueba

Primero observamos que un código puede corregir todas las ráfagas de longitud si y sólo si no hay dos palabras de código que difieran en la suma de dos ráfagas de longitud. Supongamos que dos palabras de código ya difieren en ráfagas y de longitud cada una. Al recibir el impacto de una ráfaga , podríamos interpretarlo como si hubiera sido golpeado por una ráfaga . No podemos saber si la palabra transmitida es o . Ahora supongamos que cada dos palabras en clave difieren en más de dos ráfagas de longitud . Incluso si la palabra clave transmitida se ve afectada por una ráfaga de longitud , no se verá como otra palabra clave que haya sido afectada por otra ráfaga. Para cada palabra de código , indiquemos el conjunto de todas las palabras que se diferencian por una ráfaga de longitud que se incluye a sí misma. Por la observación anterior, sabemos que para dos palabras de código diferentes y y son disjuntos. Tenemos palabras clave. Por tanto, podemos decir eso . Es más, tenemos . Al sustituir la última desigualdad en la primera, luego tomar el logaritmo base y reorganizarlo, obtenemos el teorema anterior. ${\displaystyle \leqslant \ell }$ ${\displaystyle \leqslant \ell .}$ ${\displaystyle \mathbf {c} _{1}}$ ${\displaystyle \mathbf {c} _{2}}$ ${\displaystyle \mathbf {b} _{1}}$ ${\displaystyle \mathbf {b} _{2}}$ ${\displaystyle \leqslant \ell }$ ${\displaystyle \mathbf {c} _{1}}$ ${\displaystyle \mathbf {b} _{1}}$ ${\displaystyle \mathbf {c} _{2}}$ ${\displaystyle -\mathbf {b} _{2}}$ ${\displaystyle \mathbf {c} _{1}}$ ${\displaystyle \mathbf {c} _{2}}$ ${\displaystyle \ell }$ ${\displaystyle \mathbf {c} _{1}}$ ${\displaystyle \ell }$ ${\displaystyle \mathbf {c} ,}$ ${\displaystyle B(\mathbf {c} )}$ ${\displaystyle \mathbf {c} }$ ${\displaystyle \leqslant \ell .}$ ${\displaystyle B(\mathbf {c} )}$ ${\displaystyle \mathbf {c} }$ ${\displaystyle \mathbf {c} _{i}}$ ${\displaystyle \mathbf {c} _{j},B(\mathbf {c} _{i})}$ ${\displaystyle B(\mathbf {c} _{j})}$ ${\displaystyle q^{k}}$ ${\displaystyle q^{k}|B(\mathbf {c} )|\leqslant q^{n}}$ ${\displaystyle (n-\ell )q^{\ell -2}\leqslant |B(\mathbf {c} )|}$ ${\displaystyle q}$

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

Teorema (límite de Rieger)  :  si es la capacidad de corrección de errores de ráfaga de un código de bloque lineal, entonces . ${\displaystyle \ell }$ ${\displaystyle (n,k)}$ ${\displaystyle 2\ell \leqslant n-k}$

Prueba

Cualquier código lineal que pueda corregir cualquier patrón de ráfaga de longitud no puede tener una ráfaga de longitud como palabra clave. Si tuviera una ráfaga de longitud como palabra de código, entonces una ráfaga de longitud podría cambiar la palabra de código a un patrón de ráfaga de longitud , que también podría obtenerse cometiendo un error de ráfaga de longitud en todas las palabras de código cero. Si los vectores son distintos de cero en los primeros símbolos, entonces los vectores deben ser de diferentes subconjuntos de una matriz para que su diferencia no sea una palabra clave de ráfagas de longitud . Garantizando esta condición, el número de dichos subconjuntos es al menos igual al número de vectores. Por tanto, el número de subconjuntos sería al menos . Por lo tanto, tenemos al menos símbolos distintos; de lo contrario, la diferencia de dos polinomios de este tipo sería una palabra clave que es una suma de dos ráfagas de longitud. Por lo tanto, esto demuestra el límite de Rieger. ${\displaystyle \leqslant \ell }$ ${\displaystyle \leqslant 2\ell }$ ${\displaystyle \leqslant 2\ell }$ ${\displaystyle \ell }$ ${\displaystyle \ell }$ ${\displaystyle \ell }$ ${\displaystyle 2\ell }$ ${\displaystyle 2\ell }$ ${\displaystyle q^{2\ell }}$ ${\displaystyle 2\ell }$ ${\displaystyle \leqslant \ell .}$

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

Más límites para la corrección de errores en ráfaga

Hay más de un límite superior en la velocidad de código alcanzable de los códigos de bloques lineales para la corrección de ráfagas de fases múltiples (MPBC). Uno de esos límites está restringido a una longitud de ráfaga cíclica máxima corregible dentro de cada subbloque, o de manera equivalente, una restricción en la longitud o espacio mínimo libre de errores dentro de cada ráfaga en fases. Este límite, cuando se reduce al caso especial de un límite para la corrección de ráfagas únicas, es el límite de Abramson (un corolario del límite de Hamming para la corrección de errores de ráfagas) cuando la longitud de la ráfaga cíclica es menor que la mitad de la longitud del bloque. ^[3]

Teorema (número de ráfagas)  :  para un alfabeto binario, hay vectores de longitud que son ráfagas de longitud . ^[1] ${\displaystyle 1\leqslant \ell \leqslant {\tfrac {1}{2}}(n+1),}$ ${\displaystyle n2^{\ell -1}+1}$ ${\displaystyle n}$ ${\displaystyle \leqslant \ell }$

Prueba

Dado que la longitud de la ráfaga es, hay una descripción de ráfaga única asociada con la ráfaga. La ráfaga puede comenzar en cualquiera de las posiciones del patrón. Cada patrón comienza con y contiene una longitud de . Podemos considerarlo como el conjunto de todas las cadenas que comienzan con y tienen longitud . Por lo tanto, hay un total de posibles patrones de este tipo y un total de ráfagas de longitud. Si incluimos la ráfaga de ceros, tenemos vectores que representan ráfagas de longitud. ${\displaystyle \leqslant {\tfrac {1}{2}}(n+1),}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle \ell }$ ${\displaystyle 1}$ ${\displaystyle \ell }$ ${\displaystyle 2^{\ell -1}}$ ${\displaystyle n2^{\ell -1}}$ ${\displaystyle \leqslant \ell .}$ ${\displaystyle n2^{\ell -1}+1}$ ${\displaystyle \leqslant \ell .}$

Teorema (limitado al número de palabras de código)  :  si un código de corrección de errores de ráfaga binaria tiene como máximo palabras de código. ${\displaystyle 1\leqslant \ell \leqslant {\tfrac {1}{2}}(n+1),}$ ${\displaystyle \ell }$ ${\displaystyle 2^{n}/(n2^{\ell -1}+1)}$

Prueba

Desde entonces , sabemos que hay ráfagas de longitud . Digamos que el código tiene palabras en clave, entonces hay palabras en clave que difieren de una palabra en clave por una ráfaga de longitud . Cada una de las palabras debe ser distinta, de lo contrario el código tendría distancia . Por lo tanto, implica ${\displaystyle \ell \leqslant {\tfrac {1}{2}}(n+1)}$ ${\displaystyle n2^{\ell -1}+1}$ ${\displaystyle \leqslant \ell }$ ${\displaystyle M}$ ${\displaystyle Mn2^{\ell -1}}$ ${\displaystyle \leqslant \ell }$ ${\displaystyle M}$ ${\displaystyle <1}$ ${\displaystyle M(2^{\ell -1}+1)\leqslant 2^{n}}$ ${\displaystyle M\leqslant 2^{n}/(n2^{\ell -1}+1).}$

Teorema (límites de Abramson)  :  si se trata de un código de corrección de errores de ráfaga lineal binaria , la longitud de su bloque debe satisfacer: ${\displaystyle 1\leqslant \ell \leqslant {\tfrac {1}{2}}(n+1)}$ ${\displaystyle (n,k),\ell }$

$${\displaystyle n\leqslant 2^{n-k-\ell +1}-1.}$$

Prueba

Para un código lineal, existen palabras clave. Por nuestro resultado anterior, sabemos que ${\displaystyle (n,k)}$ ${\displaystyle 2^{k}}$

$${\displaystyle 2^{k}\leqslant {\frac {2^{n}}{n2^{\ell -1}+1}}.}$$

Aislando , obtenemos . Dado que y debe ser un número entero, tenemos . ${\displaystyle n}$ ${\displaystyle n\leqslant 2^{n-k-\ell +1}-2^{-\ell +1}}$ ${\displaystyle \ell \geqslant 1}$ ${\displaystyle n}$ ${\displaystyle n\leqslant 2^{n-k-\ell +1}-1}$

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

Códigos de incendio

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 denominados Códigos de incendio, 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 lapso 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 número entero menos positivo tal que Sea un entero positivo que satisfaga y no sea divisible por , donde es el período de . Defina el código de incendio 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 p}$ ${\displaystyle p(x)}$ ${\displaystyle G}$

$${\displaystyle g(x)=\left(x^{2\ell -1}+1\right)p(x).}$$

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

Lema  1  ${\displaystyle \gcd \left(p(x),x^{2\ell -1}+1\right)=1.}$

Prueba

Sea el máximo común divisor de los dos polinomios. Dado que es irreducible, o . Supongamos entonces para alguna constante . Pero es divisor de ya que es divisor de . Pero esto contradice nuestra suposición de que no divide . De esta manera se demuestra el lema. ${\displaystyle d(x)}$ ${\displaystyle p(x)}$ ${\displaystyle \deg(d(x))=0}$ ${\displaystyle \deg(p(x))}$ ${\displaystyle \deg(d(x))\neq 0,}$ ${\displaystyle p(x)=cd(x)}$ ${\displaystyle c}$ ${\displaystyle (1/c)p(x)}$ ${\displaystyle x^{2\ell -1}+1}$ ${\displaystyle d(x)}$ ${\displaystyle x^{2\ell -1}+1}$ ${\displaystyle p(x)}$ ${\displaystyle x^{2\ell -1}+1.}$ ${\displaystyle \deg(d(x))=0,}$

Lema 2  :  si es un polinomio de período , entonces si y solo si ${\displaystyle p(x)}$ ${\displaystyle p}$ ${\displaystyle p(x)|x^{k}-1}$ ${\displaystyle p|k.}$

Prueba

Si entonces . De este modo, ${\displaystyle p|k}$ ${\displaystyle x^{k}-1=(x^{p}-1)(1+x^{p}+x^{2p}+\dots +x^{k/p})}$ ${\displaystyle p(x)|x^{k}-1.}$

Ahora supongamos . Entonces, . Demostramos que es divisible por inducción en . A continuación se presenta el caso base . Por lo tanto, supongamos . Sabemos que divide a ambos (ya que tiene punto ) ${\displaystyle p(x)|x^{k}-1}$ ${\displaystyle k\geqslant p}$ ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle k=p}$ ${\displaystyle k>p}$ ${\displaystyle p(x)}$ ${\displaystyle p}$

$${\displaystyle x^{p}-1=(x-1)\left(1+x+\dots +x^{p-1}\right)\quad {\text{and}}\quad x^{k}-1=(x-1)\left(1+x+\dots +x^{k-1}\right).}$$

Pero es irreducible, por lo tanto debe dividir a ambos y ; por tanto, también divide la diferencia de los dos últimos polinomios, . Entonces, se deduce que divide . Finalmente, también divide: . Por la hipótesis de inducción, entonces . ${\displaystyle p(x)}$ ${\displaystyle (1+x+\dots +x^{p-1})}$ ${\displaystyle (1+x+\dots +x^{k-1})}$ ${\displaystyle x^{p}(1+x+\dots +x^{p-k-1})}$ ${\displaystyle p(x)}$ ${\displaystyle (1+x+\cdots +x^{p-k-1})}$ ${\displaystyle x^{k-p}-1=(x-1)(1+x+\dots +x^{p-k-1})}$ ${\displaystyle p|k-p}$ ${\displaystyle p|k}$

Un corolario del Lema 2 es que desde tiene período , luego se divide si y sólo si . ${\displaystyle p(x)=x^{p}-1}$ ${\displaystyle p}$ ${\displaystyle p(x)}$ ${\displaystyle x^{k}-1}$ ${\displaystyle p|k}$

Teorema  :  el código contra incendios corrige errores en ráfagas ^{[4] [5]} ${\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, y si todas las ráfagas de diferentes longitudes ocurren en clases laterales diferentes, entonces todas tienen síndromes únicos, lo que facilita la corrección de errores. ${\displaystyle \ell }$

Prueba del teorema

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. En aras de la contradicción, supongamos que y están en la misma clase lateral. Entonces, es una palabra clave 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 incendio operan en . Según nuestra suposición, es una palabra clave válida y, por 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 de 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}}}$$

Al igualar el grado de ambos lados, obtenemos Dado que podemos concluir que implica y . Observe que en la expansión: ${\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).}$$

Desde que tenemos . Pero es irreducible, por tanto, y debe ser relativamente primo. Dado que es una palabra en clave, debe ser divisible por , ya que no puede ser divisible por . Por tanto, debe ser 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 múltiplo de ya que ambos son menores que . Por lo tanto, nuestra suposición de que somos una palabra clave es incorrecta y, por lo tanto, se encuentran 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)}$

Ejemplo: código de incendio de corrección de errores de 5 ráfagas

Con la teoría presentada en la sección anterior, considere la construcción de un código de incendio que corrija errores en ráfagas. Recuerde que para construir un código de incendio, necesitamos un polinomio irreducible , un número entero , que represente la capacidad de corrección de errores de ráfaga de nuestro código, y debemos satisfacer la propiedad 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 . De este modo, ${\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}$

Códigos binarios Reed-Solomon

Ciertas familias de códigos, como Reed-Solomon , operan con tamaños de alfabeto mayores que el binario. Esta propiedad otorga a dichos códigos potentes capacidades de corrección de errores en ráfagas. Considere un código que opera en . Cada símbolo del alfabeto se puede representar mediante bits. Si se trata de un código Reed-Solomon terminado , podemos considerarlo como un código terminado . ${\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 la perspectiva de la decodificación sigue siendo un error de un solo símbolo. En otras palabras, dado que los errores de ráfaga tienden a ocurrir en grupos, existe una gran posibilidad de que varios errores binarios contribuyan a un error de símbolo único. ${\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 errores puede afectar a la mayoría de los símbolos. Entonces, 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, una corrección de errores del código Reed-Solomon puede corregir cualquier combinación de ${\displaystyle t}$ ${\displaystyle \mathbb {F} _{2^{m}}}$

$${\displaystyle {\frac {t}{1+\lfloor (l+m-2)/m\rfloor }}}$$

${\displaystyle l}$ ${\displaystyle t}$

Un ejemplo de código RS binario

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 binario RS tendrá como parámetros. Es capaz de corregir cualquier ráfaga 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}$

Códigos entrelazados

El entrelazado se utiliza para convertir códigos convolucionales de correctores de errores aleatorios en correctores de errores en ráfaga. 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 de canal aleatorio. Por 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 desintercalador alterará la secuencia recibida para recuperar la secuencia original inalterada en el transmisor.

Capacidad de corrección de errores de ráfaga del intercalador

Ilustración del orden principal de filas y columnas

Teorema  :  si la capacidad de corrección de errores de ráfaga de algún código es, entonces la capacidad de corrección de errores de ráfaga de su entrelazado de vías es ${\displaystyle \ell ,}$ ${\displaystyle \lambda }$ ${\displaystyle \lambda \ell .}$

Prueba

Supongamos que tenemos un código que puede corregir todas las ráfagas de longitud. El intercalado puede proporcionarnos un código que puede corregir todas las ráfagas de longitud para un determinado valor . Si queremos codificar un mensaje de una longitud arbitraria mediante entrelazado, primero lo dividimos en bloques de longitud . Escribimos las entradas de cada bloque en una matriz usando el orden de fila principal. Luego, codificamos cada fila usando el código. Lo que obtendremos es una matriz. Ahora, esta matriz se lee y se transmite en orden de columnas principales. El truco es que si se produce una ráfaga de longitud en la palabra transmitida, entonces cada fila contendrá errores aproximadamente consecutivos (más específicamente, cada fila contendrá una ráfaga de longitud al menos y como máximo ). Si entonces y el código puede corregir cada fila. Por lo tanto, el código entrelazado puede corregir la ráfaga de longitud . Por el contrario, si al menos una fila contendrá más de errores consecutivos, es posible que el código no pueda corregirlos. Por lo tanto, la capacidad de corrección de errores del código entrelazado es exactamente. La eficiencia BEC del código entrelazado sigue siendo la misma que la del código original. Esto es cierto porque: ${\displaystyle (n,k)}$ ${\displaystyle \leqslant \ell .}$ ${\displaystyle (\lambda n,\lambda k)}$ ${\displaystyle \leqslant \lambda \ell ,}$ ${\displaystyle \lambda }$ ${\displaystyle \lambda k}$ ${\displaystyle \lambda k}$ ${\displaystyle \lambda \times k}$ ${\displaystyle (n,k)}$ ${\displaystyle \lambda \times n}$ ${\displaystyle h}$ ${\displaystyle {\tfrac {h}{\lambda }}}$ ${\displaystyle \lfloor {\tfrac {h}{\lambda }}\rfloor }$ ${\displaystyle \lceil {\tfrac {h}{\lambda }}\rceil }$ ${\displaystyle h\leqslant \lambda \ell ,}$ ${\displaystyle {\tfrac {h}{\lambda }}\leqslant \ell }$ ${\displaystyle (n,k)}$ ${\displaystyle (\lambda n,\lambda k)}$ ${\displaystyle h}$ ${\displaystyle h>\lambda \ell ,}$ ${\displaystyle {\tfrac {h}{\lambda }}}$ ${\displaystyle (n,k)}$ ${\displaystyle (\lambda n,\lambda k)}$ ${\displaystyle \lambda \ell .}$ ${\displaystyle (n,k)}$

$${\displaystyle {\frac {2\lambda \ell }{\lambda n-\lambda k}}={\frac {2\ell }{n-k}}}$$

Intercalador de bloques

La siguiente figura muestra un entrelazador de 4 por 3.

Un ejemplo de entrelazador de bloques

El entrelazador anterior se denomina 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, esto tiene forma de matriz. Generalmente, es la longitud de la palabra clave. ${\displaystyle M\times N}$ ${\displaystyle N}$

Capacidad del entrelazador de bloques : para un entrelazador de bloques y una ráfaga de longitud, el límite superior en el número de errores es. Esto es obvio por el hecho de que estamos leyendo la salida por columnas y el número de filas es . Según el teorema anterior, la capacidad de corrección de errores hasta la longitud máxima de ráfaga 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 determina tomando la relación de longitud de ráfaga donde el decodificador puede fallar en la memoria del entrelazador. Así, podemos formular como ${\displaystyle \gamma }$

$${\displaystyle \gamma ={\frac {Mt+1}{MN}}\approx {\frac {t}{N}}.}$$

Desventajas del intercalador de bloques: como se desprende claramente 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. Así, estos factores dan lugar a dos inconvenientes, uno es la latencia y otro es el almacenamiento (cantidad de memoria bastante grande). Estos inconvenientes se pueden evitar utilizando el entrelazador convolucional que se describe a continuación.

Intercalador convolucional

El intercalador 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 que se utiliza para retrasar la señal durante un tiempo determinado. Sea el número de líneas de retraso y el número de símbolos introducidos por cada línea de retraso. Por tanto, la separación entre entradas consecutivas = símbolos. Sea la longitud de la palabra clave. Por lo tanto, cada símbolo en la palabra clave de entrada estará en una línea de retardo distinta. Supongamos 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 la salida desentrelazada puede contener es. Según el teorema anterior, para una capacidad de corrección de errores de hasta , la longitud máxima de ráfaga 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,}$

Un ejemplo de entrelazador convolucional

Un ejemplo de desintercalador

Eficiencia del entrelazador cruzado ( ): ${\displaystyle \gamma }$ se determina tomando la relación entre la longitud de la 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 de la siguiente manera: ${\displaystyle \gamma }$

$${\displaystyle \gamma ={\frac {(nd+1)(t-1)+1}{{\frac {n(n-1)}{2}}d}}.}$$

Rendimiento del intercalador cruzado: como se muestra en la figura del intercalador 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 interruptor 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 alrededor de la mitad del mensaje en el receptor para poder leer la primera fila. Esto reduce drásticamente el requisito de almacenamiento a la mitad. Dado que ahora sólo se requiere la mitad del mensaje para leer la primera fila, la latencia también se reduce a la mitad, lo que supone una buena mejora con respecto al entrelazador de bloques. Por tanto, la memoria total del entrelazador se divide entre el transmisor y el receptor.

Aplicaciones

Disco compacto

Sin códigos de corrección de errores, el audio digital no sería técnicamente viable. ^[7] Los códigos Reed-Solomon pueden corregir un símbolo corrupto con un error de un solo bit tan fácilmente como pueden corregir un símbolo con todos los bits incorrectos. Esto hace que los códigos RS sean especialmente adecuados para corregir errores de ráfaga. ^[5] Con diferencia, la aplicación más común de los códigos RS es en discos compactos. Además de la corrección de errores básica proporcionada por los códigos RS, un intercalador cruzado proporciona protección contra errores de ráfaga debidos a rayones en el disco. ^[3]

El actual sistema de audio digital de 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 comprende 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 es escaneado ópticamente por 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 mientras se escanea en la parte interior de la pista hasta ~3,5 rev/s en la parte exterior. Los hoyos y los terrenos 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 resumir como una secuencia de los siguientes subprocesos:

• Codificación de canal de 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 en los discos del usuario

El proceso está sujeto tanto a errores de ráfaga como a errores aleatorios. ^[7] Los errores de explosión incluyen aquellos debidos al material del disco (defectos de la película reflectante de aluminio, índice de reflexión deficiente del material del disco transparente), producción del disco (fallos durante la formación y corte del disco, etc.), manejo del disco (arañazos, generalmente delgados, radiales). y ortogonal 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 y a 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 rayones menores.

Codificación: las ondas sonoras se muestrean y se convierten a formato digital mediante un convertidor A/D. La onda de sonido se muestrea en 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 a partir 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 a través del 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 24 símbolos de 8 bits (12 muestras de 16 bits del convertidor A/D, 6 de cada fuente de datos (sonido) izquierda y derecha). Una trama se puede representar mediante dónde y son bytes de los canales izquierdo y derecho de la muestra de la trama. ${\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 la -ésima muestra 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 Reed-Solomon C2 (28,24,5), que es un código RS abreviado . Se trata de una corrección de dos errores, con una distancia mínima de 5. Esto añade 4 bytes de redundancia, formando una nueva trama: . La palabra clave de 28 símbolos resultante se pasa a través de un entrelazador cruzado (28.4) que conduce a 28 símbolos entrelazados. Luego, estos se pasan a través del código RS C1 (32,28,5), lo que da como resultado palabras en código de 32 símbolos de salida codificados. Se realiza una reagrupación adicional de 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, lo que dará como resultado . Finalmente se agrega un byte de información de control y visualización. ^[5] Cada uno de los 33 bytes se convierte luego 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. Esta corriente pasa primero a través del decodificador D1. Corresponde a los diseñadores individuales de sistemas de CD decidir los métodos de decodificación y optimizar el rendimiento de sus productos. Siendo de distancia mínima 5 Los decodificadores D1, D2 pueden corregir cada uno una combinación de errores y borrados tales 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 desintercalador 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 manejar borrados únicamente (una solución más simple y menos costosa). Si se encontraran más de 4 borrados, D2 generará 24 borrados. A partir de entonces, un sistema de ocultación de errores intenta interpolar (a partir de símbolos vecinos) en caso de símbolos incorregibles, de lo 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 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. La longitud de pista de 7,7 mm (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 con una tasa de error de bits (BER) y 1000 muestras por minuto con BER = Muestras de error indetectables (clics): menos de una cada 750 horas con BER = e insignificante con BER = . ${\displaystyle =10^{-4}}$ ${\displaystyle 10^{-3}}$ ${\displaystyle 10^{-3}}$ ${\displaystyle 10^{-4}}$

Ver también

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

Referencias

1. Fong, WH (2011). "Límites de codificación para códigos de corrección de ráfagas múltiples y de ráfagas únicas". arXiv : 1104.1408 [cs.IT].
2. McEliece, RJ (2004). La teoría de la información y la codificación (edición estudiantil). Prensa de la Universidad de Cambridge. ISBN 978-0-521-83185-7.
3. Ling, San; Xing, Chaoping (2004). Teoría de la codificación: un primer curso. Prensa de la Universidad de Cambridge. ISBN 978-0-521-52923-5.
4. Luna, Todd K. (2005). Codificación de corrección de errores: métodos y algoritmos matemáticos. Wiley. ISBN 978-0-471-64800-0.
5. Lin, Shu; Costello, Daniel J. (2004). Codificación de control de errores: fundamentos y aplicaciones (2ª ed.). Pearson-Prentice Hall. ISBN 978-0-13-017973-9.
6. "Cassini: ¿Qué tipo de corrección de errores?". quest.arc.nasa.gov . 1999. Archivado desde el original el 27 de junio de 2012.
7. Códigos de control de errores algebraicos abc (otoño de 2012): folletos de la Universidad de Stanford
8. McEliece, Robert J. (1977). La teoría de la información y la codificación: un marco matemático para la comunicación . Programa de libros avanzados. Addison-Wesley.