En la teoría de la codificación , los códigos de corrección de errores en ráfagas emplean métodos para corregir errores en ráfagas , 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 . A veces, sin embargo, los canales pueden introducir errores que se localizan en un intervalo corto. Tales errores ocurren en una ráfaga (llamados errores de ráfaga ) porque ocurren en muchos bits consecutivos. Los ejemplos de errores de ráfaga se pueden encontrar ampliamente en los medios de almacenamiento. Estos errores pueden deberse a daños físicos, como arañazos en un disco o un rayo en el caso de los canales inalámbricos. No son independientes; tienden a concentrarse espacialmente. 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 explosión de longitud [1]
Di una palabra en clave se transmite y se recibe como Entonces, el vector de error se llama un estallido de longitud si los componentes distintos de cero de están confinados a componentes consecutivos. Por ejemplo, es un estallido de longitud
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 cíclico de ráfaga 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 terminando en la posición . Observe que los índices son-basado, es decir, el primer elemento está en la posición .
En el resto de este artículo, usaremos el término explosión para referirnos a una explosión cíclica, a menos que se indique lo contrario.
Descripción de ráfaga
A menudo es ú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. dónde 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 diferente de cero), y es la ubicación, en la palabra clave, donde se puede encontrar la ráfaga. [1]
Por ejemplo, la descripción de ráfaga del patrón de error es . Tenga en cuenta que dicha descripción no es única, porquedescribe el mismo error de ráfaga. En general, si el número de componentes distintos de cero en es , luego tendrá diferentes descripciones de ráfagas, cada una de las cuales comienza en una entrada diferente de cero de . Para remediar los problemas que surgen por la ambigüedad de las descripciones de ráfagas con el teorema siguiente, sin embargo, antes de hacerlo, primero necesitamos una definición.
Definición. El número de símbolos en un patrón de error dado. se denota por
- Teorema (Unicidad de las descripciones de ráfagas). Suponer es un vector de error de longitud con dos descripciones de ráfagas y . Si entonces las dos descripciones son idénticas, es decir, sus componentes son equivalentes. [2]
- Prueba. Dejar ser el peso de Hamming (o el número de entradas distintas de cero) de . Luego tiene exactamente descripciones de errores. Para no hay nada que probar. Entonces asumimos que y que las descripciones no son idénticas. Observamos que cada entrada distinta de cero de aparecerá en el patrón, y así, los componentes de no incluido en el patrón formará 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. Llamamos al conjunto de índices correspondientes a esta ejecución como la 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. Desde que tenemos cero carreras, y cada una es inconexa, tenemos un total de elementos distintos en todas las carreras cero. Por otro lado tenemos:
- Esto contradice Por tanto, las descripciones de los errores de ráfaga son idénticas.
Un corolario del teorema anterior es que no podemos tener dos descripciones de ráfagas distintas para ráfagas de longitud
Códigos cíclicos para la corrección de errores en ráfagas
Los códigos cíclicos se definen de la siguiente manera: piense en el símbolos como elementos en . Ahora, podemos pensar en las palabras como polinomios sobredonde 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.
Las palabras en clave son polinomios de grado . Suponga que el polinomio generador tiene grado . Polinomios de grado que son divisibles por resultado de multiplicar por polinomios de grado . Tenemostales polinomios. Cada uno de ellos corresponde a una palabra clave. Por lo tanto, para códigos cíclicos.
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 el código está delimitado 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:
- 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
- Prueba. Necesitamos demostrar que si agrega una ráfaga de longitud a una palabra de código (es decir, a un polinomio que es divisible por ), entonces el resultado no será una palabra de código (es decir, el polinomio correspondiente no es divisible por ). Basta mostrar que ninguna ráfaga de longitud es divisible por . Tal explosión tiene la forma , dónde Por lo tanto, no es divisible por (porque este último tiene grado ). no es divisible por (De lo contrario, todas las palabras en clave comenzarían con ). Por lo tanto, no es divisible por también.
La prueba anterior sugiere un algoritmo simple para la detección / corrección de errores en ráfagas en códigos cíclicos: dada una palabra transmitida (es decir, un polinomio de grado ), calcule el resto de esta palabra dividida 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 clave válida).
Por el límite superior en la detección de errores 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. Sobre alfabetos binarios, existen ráfagas de longitud . De esos, solo son divisibles por . Por lo tanto, la probabilidad de falla en la detección es muy pequeña () asumiendo una distribución uniforme en todas las ráfagas de longitud .
Ahora consideramos un teorema fundamental sobre los códigos cíclicos que ayudará a diseñar códigos de corrección de errores de ráfaga eficientes, al clasificar ráfagas en diferentes clases laterales.
- Teorema ( Cosets 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 distintas clases laterales de .
- Prueba. Dejar ser distintos errores de ráfaga de longitud que se encuentran en la misma clase lateral del código . Luego es una palabra en clave. Por tanto, si recibimos podemos decodificarlo para o . Por el contrario, si todos los errores de ráfaga y 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 solo si todos los errores de ráfaga de longitud se encuentran en distintas clases laterales de .
- Teorema (clasificación de palabras de código de error de ráfaga). Dejar ser lineal -Código de corrección de errores de ráfaga. Entonces no hay ráfagas de longitud distinta de cero puede ser una palabra clave.
- Prueba. Dejar ser una palabra en clave con una explosión de longitud . Así tiene el patrón , dónde y son palabras de largo Por lo tanto, las palabras y son dos ráfagas de longitud . Para los códigos lineales binarios, pertenecen a la misma clase lateral. Esto contradice el teorema de Cosets distintos, por lo tanto, no hay ráfagas de longitud distintas de cero. puede ser una palabra clave.
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 puede detectar todos los errores de ráfaga de longitud Una pregunta natural para hacer es: dada y , cual es el maximo que nunca podremos lograr más allá? En otras palabras, ¿cuál es el límite superior de la longitud de ráfagas que podemos detectar usando cualquier ¿código? El siguiente teorema proporciona una respuesta a esta pregunta.
- Teorema (capacidad de detección de errores de ráfaga). La capacidad de detección de errores de ráfaga de cualquier el código es
- Prueba. Primero observamos que un código puede detectar todas las ráfagas de longitud si y solo 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 un estallido de longitud . Al recibir , no podemos decir si la palabra transmitida es de hecho sin errores de transmisión, o si es con un error de ráfaga que ocurrió durante la transmisión. Ahora, suponga que cada dos palabras de código difieren en más de una ráfaga de longitud Incluso si la palabra clave transmitida es golpeado por una ráfaga de longitud , no va a cambiar a otra palabra de código válida. Al recibirlo, podemos decir que este es con un estallido Por la observación anterior, sabemos que no hay dos palabras de código que puedan compartir la primera símbolos. La razón es que incluso si difieren en todos los demás símbolos, seguirán siendo diferentes por una explosión de longitud Por lo tanto, el número de palabras de código satisface Aplicando a ambos lados y reorganizando, podemos ver que .
Ahora, repetimos la misma pregunta pero para la corrección de errores: dado y , ¿cuál es el límite superior de la longitud? de ráfagas que podemos corregir usando cualquier ¿código? El siguiente teorema proporciona una respuesta preliminar a esta pregunta:
- Teorema (capacidad de corrección de errores en ráfagas). La capacidad de corrección de errores de ráfaga de cualquier el código satisface
- Prueba. Primero observamos que un código puede corregir todas las ráfagas de longitud si y solo si no hay dos palabras de código que difieran por la suma de dos ráfagas de longitud Suponga que dos palabras en clave y diferir por ráfagas y de longitud cada. Al recibir golpeado por una ráfaga , podríamos interpretarlo como si fuera golpeado por una ráfaga . No podemos decir si la palabra transmitida es o . Ahora, suponga que cada dos palabras de código difieren en más de dos ráfagas de longitud . Incluso si la palabra clave transmitida es golpeado por un estallido de longitud , no se verá como otra palabra en clave que haya sido golpeada por otra ráfaga. Para cada palabra en clave dejar denotar el conjunto de todas las palabras que difieren de por un estallido de longitud Darse cuenta de incluye sí mismo. Por la observación anterior, sabemos que para dos palabras de código diferentes y y son inconexos. Tenemos palabras en clave. Por tanto, podemos decir que . Además, tenemos . Conectando la última desigualdad con la primera, luego tomando la base logaritmo y reordenamiento, obtenemos el teorema anterior.
El límite de Rieger da un resultado más fuerte:
- Teorema (límite de Rieger). Si es la capacidad de corrección de errores de ráfaga de un código de bloque lineal, luego .
- Prueba. Cualquier código lineal que pueda corregir cualquier patrón de ráfaga de longitud no puede tener una explosión de longitud como palabra clave. Si tuviera un estallido de longitud como una palabra en clave, luego 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 toda palabra de código cero. Si los vectores son distintos de cero en primer lugar símbolos, entonces los vectores deben ser de diferentes subconjuntos de una matriz para que su diferencia no sea una palabra de código de ráfagas de longitud . Asegurando esta condición, el número de tales subconjuntos es al menos igual al número de vectores. Por lo 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 de estos polinomios sería una palabra de código que es la suma de dos ráfagas de longitud Por lo tanto, esto prueba el Rieger Bound.
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.
Más límites en la corrección de errores en ráfagas
Hay más de un límite superior en la tasa de código alcanzable de los códigos de bloques lineales para la corrección de ráfagas de múltiples fases (MPBC). Uno de dichos límites está restringido a una longitud de ráfaga cíclica corregible máxima dentro de cada subbloque, o de manera equivalente, una restricción sobre la longitud o espacio libre de error mínimo 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]
- Teorema (número de ráfagas). Para sobre un alfabeto binario, hay vectores de longitud que son ráfagas de longitud . [1]
- 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 los posiciones del patrón. Cada patrón comienza con y contienen una longitud de . Podemos pensar en él como el conjunto de todas las cadenas que comienzan con y tener longitud . Por tanto, hay un total de posibles tales patrones, y un total de ráfagas de longitud Si incluimos la ráfaga de todo cero, tenemos vectores que representan ráfagas de longitud
- Teorema (ligado al número de palabras en clave). Si un binario -El código de corrección de errores de ráfaga tiene como máximo palabras en clave.
- Prueba. Desde , sabemos que hay ráfagas de longitud . Digamos que el código tiene palabras en clave, entonces hay palabras de código que difieren de una palabra de código por una ráfaga de longitud . Cada una de las las palabras deben ser distintas, de lo contrario el código tendría distancia . Por lo tanto, implica
- Teorema (límites de Abramson). Si es un binario lineal-código de corrección de error de ráfaga, su longitud de bloque debe satisfacer:
- Prueba: para un lineal código, hay palabras en clave. Por nuestro resultado anterior, sabemos que
- Aislar , obtenemos . Desde y debe ser un número entero, tenemos .
Observación. se llama la redundancia del código y en una formulación alternativa para los límites de Abramson es
Códigos de incendios [3] [4] [5]
Si bien los códigos cíclicos en general son herramientas poderosas para detectar errores de ráfaga, ahora consideramos 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 una sola ráfaga, 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.
Dejar ser un polinomio irreducible de grado encima , y deja ser el periodo de . El periodo de, y de hecho de cualquier polinomio, se define como el número entero menos positivo tal que Dejar ser un entero positivo satisfactorio y no divisible por , dónde es el periodo de . Definir el código de incendiospor el siguiente polinomio generador :
Te mostraremos que es un -Código de corrección de errores de ráfaga.
- Lema 1.
- Prueba. Dejar ser el máximo común divisor de los dos polinomios. Desde es irreductible, o . Asumir luego por alguna constante . Pero, es un divisor de desde es un divisor de . Pero esto contradice nuestra suposición de que no divide Por lo tanto, probando el lema.
- Lema 2. Si es un polinomio de período , luego si y solo si
- Prueba. Si , luego . Por lo tanto,
- Ahora suponga . Luego, . Te lo mostramos es divisible por por inducción en . El caso base sigue. Por lo tanto, asuma . Lo sabemos divide a ambos (ya que tiene punto )
- Pero es irreductible, por lo tanto, debe dividir tanto y ; por lo tanto, también divide la diferencia de los dos últimos polinomios, . Entonces, se sigue que divide . Finalmente, también divide: . Por la hipótesis de inducción, , luego .
Un corolario del Lema 2 es que, dado que tiene período , luego divide si y solo si .
Si podemos demostrar que todas las ráfagas de longitud o menos ocurren en diferentes clases sociales , podemos usarlas como líderes de clases laterales que forman patrones de error corregibles. La razón es simple: sabemos que cada clase tiene una decodificación de síndrome única asociada, y si todas las ráfagas de diferentes longitudes ocurren en diferentes clases, entonces todas tienen síndromes únicos, lo que facilita la corrección de errores.
Prueba del teorema
Dejar y ser polinomios con grados y , que representa ráfagas de longitud y respectivamente con Los enteros representan las posiciones iniciales de las ráfagas y son menores que la longitud del bloque del código. Por el bien de la contradicción, suponga que y están en la misma clase lateral. Luego,es una palabra de código válida (ya que ambos términos están en la misma clase lateral). Sin perder la generalidad, elige. Por el teorema de la división podemos escribir: para enteros y . Reescribimos el polinomio como sigue:
Observe que en la segunda manipulación, introdujimos el término . Se nos permite hacerlo, ya que los códigos de incendios operan en. Por 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 relativamente primos, tiene que ser divisible por . Mirando de cerca la última expresión derivada de nos damos cuenta que es divisible por (por el corolario del Lema 2). Por lo tanto, es divisible por o es . Aplicando el teorema de la división nuevamente, vemos que existe un polinomio con grado tal que:
Entonces podemos escribir:
Igualar el grado de ambos lados, nos da Desde podemos concluir lo que implica y . Note que en la expansión:
el termino aparece, pero desde , 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 reflejar es decir . Sustituyendo de nuevo en Nos da,
Desde , tenemos . Pero es irreductible, por lo tanto y debe ser relativamente primo. Desde es una palabra en clave, 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 de 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 ser una palabra clave es incorrecto y, por lo tanto, y están en diferentes clases sociales, con síndromes únicos y, por lo tanto, corregibles.
Ejemplo: código de incendio de corrección de error de 5 ráfagas
Con la teoría presentada en la sección anterior, considere la construcción de un -Ráfaga de error al corregir el código de incendios. Recuerda que para construir un Código de fuego, necesitamos un polinomio irreducible., un entero , que representa la capacidad de corrección de errores de ráfaga de nuestro código, y necesitamos satisfacer la propiedad que no es divisible por el período de . Con estos requisitos en mente, considere el polinomio irreducible, y deja . Desde 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.
Códigos binarios Reed-Solomon
Ciertas familias de códigos, como Reed-Solomon , operan en 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 mediantebits. Si es un Código Reed-Solomon terminado , podemos pensar en como un codificar sobre .
La razón por la que estos códigos son poderosos 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 los bits son erróneos; ya sea un solo bit, o todos loslos bits contienen 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 solo error de símbolo.
Observe que una ráfaga de los errores pueden afectar como máximo símbolos, y una explosión de puede afectar como máximo símbolos. Entonces, una ráfaga de puede afectar como máximo símbolos esto implica que un-símbolos-código de corrección de errores puede corregir una ráfaga de longitud como máximo .
En general, un -error al corregir el código Reed-Solomon 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.
Un ejemplo de un código RS binario
Dejar ser un Código RS sobre . Este código fue empleado por la NASA en su nave espacial Cassini-Huygens . [6] Es capaz de corregirerrores de símbolo. Ahora construimos un código RS binario de . Cada símbolo se escribirá usandobits. Por lo tanto, el código RS binario tendrácomo sus parámetros. Es capaz de corregir cualquier ráfaga de longitud..
Códigos intercalados
El entrelazado se utiliza para convertir códigos convolucionales de correctores de errores aleatorios en correctores de errores de ráfaga. La idea básica detrás del uso de códigos intercalados es mezclar símbolos en el receptor. 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 canal aleatorio. Por tanto, la función principal que realiza el intercalador 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
- 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 -way intercalado es
- Prueba: Supongamos que tenemos una código que puede corregir todas las ráfagas de longitud El intercalado puede proporcionarnos una código que puede corregir todas las ráfagas de longitud para cualquier dado . Si queremos codificar un mensaje de una longitud arbitraria utilizando entrelazado, primero lo dividimos en bloques de longitud . Escribimos el entradas de cada bloque en un matriz utilizando el orden de fila mayor. Luego, codificamos cada fila usando el código. Lo que obtendremos es un matriz. Ahora, esta matriz se lee y se transmite en orden de columna mayor. El truco es que si se produce una explosión de longitud en la palabra transmitida, cada fila contendrá aproximadamente errores consecutivos (más específicamente, cada fila contendrá una ráfaga de longitud al menos y como mucho ). Si luego y el El código puede corregir cada fila. Por lo tanto, el intercalado el código puede corregir la ráfaga de longitud . Por el contrario, si entonces al menos una fila contendrá más de errores consecutivos, y el es posible que el código no los corrija. Por lo tanto, la capacidad de corrección de errores del intercalado el código es exactamente La eficiencia BEC del código intercalado sigue siendo la misma que la del código original. código. Esto es cierto porque:
Intercalador de bloques
La siguiente figura muestra un intercalador de 4 por 3.
El intercalador anterior se denomina intercalador de bloque . 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 la forma deformación. Generalmente, es la longitud de la palabra de código.
Capacidad del intercalador de bloques : para intercalador de bloque y ráfaga de longitud el límite superior del número de errores es Esto es obvio por el hecho de que estamos leyendo la columna de salida sabiamente y el número de filas es . Según el teorema anterior para 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.
Eficiencia del intercalador de bloques (): Se encuentra tomando la relación de la longitud de ráfaga en la que el decodificador puede fallar con la memoria del intercalador. Por tanto, podemos formular como
Inconvenientes del intercalador 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. 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 intercalador convolucional que se describe a continuación.
Intercalador convolucional
El intercalador cruzado es una especie de sistema multiplexor-demultiplexor. En este sistema, las líneas de retardo se utilizan para aumentar progresivamente la longitud. La línea de retardo es básicamente un circuito electrónico que se utiliza para retardar la señal en un tiempo determinado. Dejar 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 tanto, la separación entre entradas consecutivas =símbolos. Deje que la longitud de la palabra en clavePor tanto, cada símbolo de la palabra de código de entrada estará en una línea de retardo distinta. Deje un error de ráfaga de longitudocurrir. Dado que la separación entre símbolos consecutivos es el número de errores que puede contener la salida desintercalada 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 una longitud de ráfaga de el decodificador puede fallar.
Eficiencia del intercalador cruzado (): Se encuentra tomando la relación entre la longitud de ráfaga en la que el decodificador puede fallar y la memoria del intercalador. En este caso, la memoria del intercalador se puede calcular como
Por tanto, podemos formular como sigue:
Rendimiento del intercalador cruzado: como se muestra en la figura del intercalador anterior, la salida no son 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 alrededor de la mitad de la conmutación, podemos leer la primera fila en el receptor. Por lo tanto, necesitamos almacenar un máximo de alrededor de 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 intercalador de bloques. Por tanto, la memoria total del intercalador 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 factible. [7] Los códigos Reed-Solomon pueden corregir un símbolo dañado 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 mucho, la aplicación más común de los códigos RS se encuentra en los discos compactos. Además de la corrección de errores básica proporcionada por los códigos RS, un entrelazador cruzado proporciona protección contra errores de ráfaga debido a rayones en el disco. [3]
El sistema de audio digital de disco compacto actual 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 un recubrimiento 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 se varía de ~ 8 rev / s mientras se escanea en la parte interna de la pista a ~ 3.5 rev / s en la parte externa. Los pozos y las tierras 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 la fuente de señales -> Subprocesos mecánicos para preparar un disco maestro, producir discos de usuario y detectar 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 del usuario
El proceso está sujeto a errores de ráfaga y errores aleatorios. [7] Los errores de rotura incluyen aquellos debidos al material del disco (defectos de la película reflectante de aluminio, índice reflectante deficiente del material del disco transparente), producción del disco (fallas durante la formación y corte del disco, etc.), manipulación del disco (rayones, generalmente delgados, radiales y ortogonal a la dirección de grabación) y variaciones en el mecanismo de reproducción. Los errores aleatorios incluyen los debidos a la fluctuació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 error de hasta 3500 bits en secuencia (2,4 mm de longitud como se ve en la superficie del CD) y compensa ráfagas de error 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 para determinar su amplitud (a 44,1 kHz o 44,100 pares, uno para cada uno de los canales 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 o 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 muestreados a 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 consta de fotogramas de entrada, cada uno de los 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). Un marco se puede representar por dónde y son bytes de los canales izquierdo y derecho del muestra del marco.
Inicialmente, los bytes se permutan para formar nuevos marcos representados por dónde representar 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 sobre . Esto es una corrección de dos errores, siendo de una distancia mínima 5. Esto agrega 4 bytes de redundancia, formando un nuevo marco: . La palabra de código de 28 símbolos resultante se pasa a través de un intercalador cruzado (28.4) que conduce a 28 símbolos intercalados. A continuación, 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 los símbolos de número par de la siguiente palabra de código para romper cualquier ráfaga corta que pueda estar todavía 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] Luego, cada uno de los 33 bytes se convierte en 17 bits mediante EFM (modulación de ocho a catorce) y se agregan 3 bits de combinación. Por lo tanto, la trama de seis muestras da como resultado 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. Depende de los diseñadores individuales de sistemas de CD decidir los métodos de decodificación y optimizar el rendimiento de sus productos. Al tener una 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 desentrelazador en la etapa siguiente distribuye estos borrados entre 28 palabras de código D2. Nuevamente, en la mayoría de las soluciones, D2 está configurado para lidiar solo con borrados (una solución más simple y menos costosa). Si se encontraran más de 4 borrados, D2 emite 24 borrados. A partir de entonces, un sistema de ocultación de errores intenta interpolar (de los símbolos vecinos) en caso de símbolos incorregibles, fallando los sonidos correspondientes a tales símbolos erróneos que se silencian.
Rendimiento de CIRC: [7] CIRC oculta errores de busto largo mediante una interpolación lineal simple. 2,5 mm de longitud de pista (4000 bits) es la longitud de ráfaga máxima 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 la muestra es una cada 10 horas a la tasa de error de bits (BER) y 1000 muestras por minuto a BER = Muestras de errores indetectables (clics): menos de una cada 750 horas con BER = y despreciable en BER = .
Ver también
- 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
Referencias
- ^ a b c d Límites de codificación para códigos de corrección de ráfaga múltiple y de corrección de ráfaga única
- ^ La teoría de la información y la codificación: Edición para estudiantes , por RJ McEliece
- ^ a b c Ling, San y Chaoping Xing. Teoría de la codificación: un primer curso. Cambridge, Reino Unido: Cambridge UP, 2004. Imprimir
- ^ a b Moon, Todd K. Codificación de corrección de errores: métodos matemáticos y algoritmos. Hoboken, Nueva Jersey: Wiley-Interscience, 2005. Imprimir
- ^ a b c d e f Lin, Shu y Daniel J. Costello. Codificación de control de errores: fundamentos y aplicaciones. Upper Saddle River, Nueva Jersey: Pearson-Prentice Hall, 2004. Imprimir
- ^ http://quest.arc.nasa.gov/saturn/qa/cassini/Error_correction.txt Archivado el 27 de junio de 2012 en la Wayback Machine.
- ^ a b c Códigos de control de errores algebraicos (otoño de 2012): folletos de la Universidad de Stanford
- ^ McEliece, Robert J. La teoría de la información y la codificación: un marco matemático para la comunicación. Reading, MA: Addison-Wesley Pub., Advanced Book Program, 1977. Imprimir