EntradaCodificación de bucle. Centro pedagógico-metódico para la formación de idiomas avtf kc
El código cíclico más simple permite detectar errores únicos y errores de multiplicidad impar. El polinomio generador de este código tiene la forma Entre los polinomios irreducibles incluidos en la expansión, este polinomio es el polinomio de menor grado, por lo que para cualquier número de bits de información solo se necesita un bit de control. El valor de carácter de este bit asegura la paridad del número de unos en cualquier combinación de código permitida. El código de verificación de paridad cíclica resultante es capaz de detectar no solo errores individuales en bits individuales, sino también errores en cualquier número impar de bits.
Ejemplo. Construya un código cíclico para Dado que el polinomio generador es un polinomio de primer grado, el número de bits de verificación En consecuencia, para construir un código cíclico, construimos una matriz generadora
Para construir una matriz adicional, encontramos los restos de dividir la última fila de la matriz unitaria transpuesta, rellenada con ceros, por el polinomio seleccionado:
Por tanto, la matriz adicional C, k tiene la forma
Ahora construimos la matriz generadora
Las líneas de esta matriz son las tres primeras combinaciones de códigos. El resto de las combinaciones permitidas se pueden obtener sumando módulo dos todas las combinaciones posibles de filas de la matriz. Las combinaciones de código destruidas resultantes se dan en la tabla. 39.
Tabla 39 (ver escaneo)
Es de interés conocido considerar el siguiente código más simple del polinomio irreducible de segundo grado
La vista general de la matriz generadora del código cíclico formado por el polinomio difiere en la estructura de la matriz adicional que tiene dos columnas.
Es fácil verificar que, cuando se divide por un generador dado, los polinomios que expresan las filas
la matriz de identidad (para encontrar una matriz adicional, se forman tres tipos de residuos: 11, 01 y 10. En consecuencia, el peso de cada combinación del código obtenido será al menos dos. La distancia mínima de código entre dos combinaciones cualesquiera es también dos. Pero el más simple Sin embargo, la capacidad de corrección de ambos códigos no es la misma. El código en consideración tiene una gran redundancia y permite detectar no solo cualquier error de multiplicidad impar, sino también cualquier error adyacente emparejado, así como todos los errores separados por un elemento no distorsionado.
La clase de códigos lineales, que se denominan códigos cshaic... El nombre proviene de la propiedad principal de estos códigos: si alguna combinación de códigos pertenece a un código cíclico, entonces la combinación obtenida por permutación cíclica de la combinación original (desplazamiento cíclico) también pertenece a este codigo:
La segunda propiedad de todas las combinaciones permitidas de códigos cíclicos es su divisibilidad sin un resto por algún polinomio elegido, llamado generador.
Estas propiedades se utilizan en la construcción de códigos para codificar y decodificar dispositivos, así como en la detección y corrección de errores.
Códigos cíclicos es toda una familia de códigos correctores de errores (una de cuyas variedades son los códigos Hamming), que proporciona una gran flexibilidad en cuanto a la posibilidad de implementar códigos con la capacidad necesaria para detectar y corregir errores que ocurren al transmitir combinaciones de códigos a través de un canal de comunicación. El código cíclico se refiere al bloque sistemático (l, &): códigos en los que Para los primeros dígitos son una combinación del código primario y los siguientes (l - Para) los dígitos están comprobando.
La construcción de códigos cíclicos se basa en la operación de dividir la palabra de código transmitida por el polinomio generador irreducible de grado GRAMO. El resto de la división se utiliza para formar dígitos de control. En este caso, la operación de división está precedida por la operación de multiplicación, que realiza un desplazamiento a la izquierda de la combinación del código de información de bits ^ por GRAMO descargas.
Cuando se decodifica la palabra de código de n bits recibida, se vuelve a realizar la división por el polinomio generador (generador, generador).
El síndrome de error en estos códigos es la presencia del resto de la división de la palabra de código recibida por el polinomio generador. Si el síndrome es cero, se considera que no hay errores. De lo contrario, utilizando el síndrome resultante, puede determinar el número de bit de la palabra de código recibida, en la que se produjo el error, y corregirlo.
Sin embargo, no se excluye la posibilidad de múltiples errores en las combinaciones de códigos, que pueden dar lugar a falsas correcciones y (o) no detección de errores al transformar una combinación permitida en otra.
Sea el número total de bits en el bloque igual a i, de los cuales información útil llevar T bits, entonces, en caso de error, es posible corregir j bits. Dependencia 5 de NS y T para los códigos se pueden determinar a partir de la tabla. 2.6.
Cuadro 2.6
Dependencia del número total de dígitos de combinaciones en el número de dígitos informativos y corregidos
Aumentando la diferencia (n - t), no solo puede aumentar el número de bits corregibles s, pero también detecta múltiples errores. Los porcentajes de errores múltiples detectados se muestran en la tabla. 2.7.
Cuadro 2.7
Porcentaje de errores múltiples detectados
Es conveniente describir los códigos cíclicos y su construcción utilizando polinomios (o polinomios). La combinación se escribe en forma de polinomio para mostrar de forma formalizada el funcionamiento del desplazamiento cíclico de la palabra de código original. Por lo tanto, la combinación de código de elemento "se puede describir mediante el polinomio (NS- 1) grados:
dóndea „_j =(0, 1) ya „_, =0 corresponde a cero elementos de la combinación, q „_, = 1 - distinto de cero;I- número del bit de la combinación de código.
Representemos los polinomios para combinaciones específicas de 4 elementos:
Las operaciones de suma y resta son equivalentes y asociativas y se realizan en módulo 2:
Ejemplos de operaciones de realización:
La operación de división es la división habitual de polinomios, pero en lugar de restar, se usa la suma módulo 2:
Desplazamiento cíclico de una combinación de código: mover sus elementos de derecha a izquierda sin alterar su orden, de modo que el elemento más a la izquierda ocupe el lugar del más a la derecha.
Las principales propiedades y el nombre de los códigos cíclicos están relacionados con el hecho de que todas las combinaciones permitidas de bits en el mensaje transmitido (palabras de código) pueden obtenerse mediante la operación de desplazamiento cíclico de alguna palabra de código fuente.
Digamos que se dan la combinación de código original y el polinomio correspondiente:
Multiplicar Oh) sobre NS:
Desde el grado máximo NS en una palabra en clave de longitud NS no excede (n - 1), luego del lado derecho de la expresión resultante para obtener el polinomio original, es necesario restar Oh"- 1). Sustracción Oh"- 1) se llama tomando el resto módulo (x n - 1).
El cambio de la combinación original por / medidas se puede representar de la siguiente manera: una (x)? Y - Oh"- 1), es decir multiplicación Oh) nah "y tomando el resto módulo (x" - 1). Tomar el resto es necesario para obtener un polinomio de grado mayor o igual a NS.
La idea de construir códigos cíclicos se basa en el uso de polinomios irreducibles. Un polinomio irreducible es un polinomio que no se puede representar como un producto de polinomios de grados inferiores, es decir, divisible solo por sí mismo o por uno y no divisible por ningún otro polinomio. Los binomios (x "+ 1) son divisibles por tal polinomio sin un resto. Los polinomios irreducibles en la teoría de códigos cíclicos juegan el papel de generar polinomios.
Volviendo a la definición del código cíclico y teniendo en cuenta el registro de las operaciones de desplazamiento cíclico de las combinaciones de código, podemos escribir la matriz generadora del código cíclico de la siguiente forma:
dóndeP (x)- la combinación de código original, sobre la base de la cual todos los demás(T- 1) combinaciones básicas;
С, = 0 oCj =1 ("O" si el grado resultante del polinomioP (x) -x 'no excede (l - 1), o "1" - si lo hace).
Combinación P (x) se llama una combinación de generación (generador). Para construir un código cíclico, basta con elegir correctamente P (x). Entonces, todas las demás combinaciones de códigos son las mismas que en el código de grupo.
El polinomio generador debe cumplir los siguientes requisitos:
- P (x) debe ser distinto de cero;
- el peso P (x) no debe ser menor que la distancia mínima del código: V (P (x))> d mm;
- P (x) debe tener el grado máximo k (k - el número de elementos redundantes en el código);
- P (x) debe ser un divisor del polinomio (x "- 1).
El cumplimiento de la última condición conduce al hecho de que todas las combinaciones de código de trabajo del código cíclico adquieren la propiedad de divisibilidad por P (x) sin un resto. Teniendo esto en cuenta, podemos dar otra definición de código cíclico: un código cíclico es un código, cuyas combinaciones de trabajo son divisibles por el polinomio generador sin resto.
Para determinar el grado del polinomio generador, se puede usar la expresión r> log 2 (y + 1), donde NS- el tamaño del paquete transmitido a la vez, es decir la longitud del código cíclico construido.
En la tabla se dan ejemplos de generación de polinomios. 2.8.
Cuadro 2.8
Ejemplos de polinomios generadores
El algoritmo para obtener una combinación de código permitido de un código cíclico a partir de una combinación de un código simple es el siguiente.
Sea un polinomio P (x) = una z _ (x z + una z _ 2 x r ~ 1 + ... + 1, que determina la capacidad de corrección del código y el número de bits de verificación Para, así como la combinación original de un código simple desde el elemento y bits de información en forma de polinomio Una m (x).
Es necesario determinar la combinación de código permitida del código cíclico (y, Para).
- 1. Representamos la combinación de código original en forma de polinomio. Una m (x). Multiplicamos el polinomio de la palabra de código original por x g: A t (x) x d. Grado de polinomio generador GRAMO igual al valor del bit más significativo de la palabra de código original.
- 2. Determinar los dígitos de control que complementen la combinación de información original a la permitida, como el resto de dividir el producto obtenido en el párrafo anterior por el generador.
polinomio: 
El resto de la división se denota como R (x).
3. El patrón cíclico finalmente resuelto
el código se define como = ¿Y t (x)? x r + R (x).
Para determinar los errores en la palabra de código recibida, basta con dividirla por el polinomio generador. Si la combinación aceptada es legal, el resto de la división será cero. Un resto distinto de cero indica que la combinación aceptada contiene errores. Por el tipo de resto (síndrome), en algunos casos, también es posible sacar una conclusión sobre la naturaleza del error y su ubicación y corregir el error.
El algoritmo para determinar el error es el siguiente.
Deje que las combinaciones de elementos "( n = k + t).
- 1. Identificamos el hecho de la presencia de un error. Obtenemos el resto de la división de la combinación aceptada A n - (x) al polinomio generador P (x): A(NS)
- --- = Rq (x). La presencia del resto R 0 (x) para (A 0 (x) f 0) indica P (x)
sobre el error.
2. Divida el polinomio resultante # (x) = Л „_,(NS) 0 Rq (x) por generador R g (x): W-1 = R (x), dónde R (x)- saldo actual.
3. Compare LDx) y R (x). Si son iguales, entonces el error ocurrió en el bit más significativo. Si no es así, aumentamos el grado del polinomio adoptado por x y dividimos nuevamente:
4. Compare el saldo resultante con Rq (x). Si son iguales, entonces el error ocurrió en el segundo bit. Si no son iguales, multiplicamos Shx) x 2 y repetimos estas operaciones hasta que obtengamos
R (x) = infierno.
El error estará en el dígito correspondiente al número en el que se incrementa el grado Shx), más 1. Por ejemplo, en el caso de igualdad R (x) y LDx)
Coincidiendo con esta palabra, de variable formal X... Se puede ver que esta correspondencia no es solo uno a uno, sino también isomórfica. Dado que las "palabras" consisten en letras de un campo, se pueden agregar y multiplicar (elemento por elemento), y el resultado estará en el mismo campo. El polinomio correspondiente a una combinación lineal de un par de palabras y es igual a una combinación lineal de los polinomios de estas palabras.
Esto nos permite considerar el conjunto de palabras de longitud n sobre un campo finito como un espacio lineal de polinomios con grado como máximo n-1 sobre el campo.
Descripción algebraica
Si palabra clave obtenido desplazando cíclicamente un bit a la derecha de la palabra, luego el polinomio correspondiente C 1 (X) se obtiene del anterior multiplicando por x:
Aprovechando que,
Desplácese hacia la derecha y hacia la izquierda, respectivamente, por j dígitos:
Si metro(X) es un polinomio arbitrario sobre el campo GRAMOF(q) y C(X) es la palabra clave del cíclico ( norte,k) código, luego metro(X)C(X)metrooD(X norte − 1) es también la palabra clave de este código.
Generando polinomio
Definición El polinomio generador del cíclico ( norte,k) código C se llama un polinomio distinto de cero 
de C, cuyo grado es el más pequeño y el coeficiente en el grado más alto gramo r = 1
.
Teorema 1
Si C- cíclico ( norte,k) código y gramo(X) es su polinomio generador, luego el grado gramo(X) es igual a r = norte − k y cada palabra de código se puede representar de forma única como
C(X) = metro(X)gramo(X) ,
donde el grado metro(X) es menor o igual que k − 1 .
Teorema 2
gramo(X) es el polinomio generador del cíclico ( norte,k) del código es un divisor del binomio X norte − 1
Consecuencias: así, como polinomio generador, puedes elegir cualquier polinomio, el divisor X norte- 1. El grado del polinomio seleccionado determinará el número de símbolos de verificación r, el número de símbolos de información k = norte − r .
Matriz generativa
Los polinomios son linealmente independientes, de lo contrario metro(X)gramo(X) = 0 en un valor distinto de cero metro(X), lo cual es imposible.
Esto significa que las palabras de código se pueden escribir, como para los códigos lineales, de la siguiente manera:
, dónde GRAMO es un matriz generadora, metro(X)
- información polinomio.
La matriz GRAMO se puede escribir en forma simbólica: 
Verificar matriz
Para cada palabra clave del código cíclico es verdadera. Es por eso comprobar matriz Se puede escribir como:
Codificación
No sistemático
Con codificación no sistemática, la palabra de código se obtiene en forma del producto del polinomio de información por el generador
C(X) = metro(X)gramo(X) .
Se puede implementar mediante multiplicadores polinomiales.
Sistemático
Con la codificación sistemática, la palabra de código se forma en forma de un sub-bloque de información y un control
Deje que la palabra de información forme los poderes más altos de la palabra de código, luego
C(X) = X r metro(X) + s(X),r = norte − k
Luego, de la condición, se sigue
Esta ecuación establece la regla para la codificación sistemática. Se puede implementar mediante filtros lineales multiciclo (MLF)
Ejemplos de
Código binario (7,4,3)
Como divisor X 7-1 elegimos el polinomio generador de tercer grado gramo(X) = X 3 + X + 1 , entonces el código resultante tendrá longitud norte= 7, el número de símbolos de verificación (el grado del polinomio generador) r= 3, el número de símbolos de información k= 4, distancia mínima D = 3 .
Matriz generativa código:
,
donde la primera línea representa la notación polinomial gramo(X) coeficientes en grado ascendente. El resto de las líneas son cambios cíclicos de la primera línea.
Verificar matriz:
,
donde la i-ésima columna, comenzando desde la 0-ésima, es el resto de la división X I por polinomio gramo(X), escrito en grados ascendentes, comenzando desde arriba.
Entonces, por ejemplo, se obtiene la tercera columna, o en notación vectorial.
Es fácil ver eso GRAMOH T = 0 .
Código BCH binario (15.7.5)
Como polinomio generador gramo(X) puedes elegir el producto de dos divisores X 15 − 1 ^
gramo(X) = gramo 1 (X)gramo 2 (X) = (X 4 + X + 1)(X 4 + X 3 + X 2 + X + 1) = X 8 + X 7 + X 6 + X 4 + 1 .
Luego, cada palabra de código se puede obtener utilizando el producto del polinomio de información metro(X) con grado k- 1 de esta manera:
C(X) = metro(X)gramo(X) .
Por ejemplo, la palabra de información corresponde al polinomio metro(X) = X 6 + X 5 + X 4 + 1 , luego la palabra en clave C(X) = (X 6 + X 5 + X 4 + 1)(X 8 + X 7 + X 6 + X 4 + 1) = X 14 + X 12 + X 9 + X 7 + X 5 + 1 , o en forma vectorial
ver también
Enlaces
Fundación Wikimedia. 2010.
- Formas cíclicas en la música
- Condiciones cíclicas de contorno
Vea qué son los "códigos cíclicos" en otros diccionarios:
códigos cíclicos abreviados- - [L.G. Sumenko. El Diccionario Inglés Ruso de Tecnología de la Información. M.: GP TsNIIS, 2003.] Sujetos tecnologías de la información en general EN códigos cíclicos abreviados ...
Códigos Reed-Solomon- códigos cíclicos no binarios para corregir errores en bloques de datos. Los elementos del vector de código no son bits, sino grupos de bits (bloques). Los códigos de Reed Solomon que funcionan con bytes (octetos) son muy comunes. El código de Reed Solomon es ... Wikipedia
Códigos Golay- Una familia de códigos de bloques lineales perfectos con corrección de errores. El más útil es el código binario de Golay. También se conoce el código ternario Golay. Los códigos Golay pueden considerarse códigos cíclicos. ... ... Guía del traductor técnico
Códigos de corrección de errores
Error al corregir códigos- Detección de errores en la tecnología de la comunicación, acción dirigida a monitorear la integridad de los datos durante la grabación / reproducción de información o durante su transmisión por líneas de comunicación. Corrección de errores (corrección de errores) el procedimiento para restaurar información después de ... ... Wikipedia
Códigos de corrección de errores- Detección de errores en la tecnología de la comunicación, acción dirigida a monitorear la integridad de los datos durante la grabación / reproducción de información o durante su transmisión por líneas de comunicación. Corrección de errores (corrección de errores) el procedimiento para restaurar información después de ... ... Wikipedia
Es una subclase de códigos lineales que tienen la propiedad de que la permutación cíclica de símbolos en un bloque codificado produce otro posible bloque codificado del mismo código. Los códigos cíclicos se basan en la aplicación de ideas de la teoría algebraica de los campos de Galois1.
Muchos de los códigos antiinterferencias más importantes de los sistemas de comunicación, -
en particular cíclico, basado en estructuras de aritmética finita
Campos de Galois. Por el campo se llama al conjunto de elementos que tienen un campo finito
los nombres de las operaciones están entre comillas porque no siempre son operaciones aritméticas generalmente aceptadas. El campo siempre contiene un elemento cero (0), o cero, y un elemento (1) o uno. Si el numero q los elementos del campo son limitados, entonces el campo se llama campo finito, o campo finito de Galois, y denotado GF (q) y dónde q - orden de campo. El campo de Galois más pequeño es el iole de dos elementos GF ( 2), que consta de solo dos elementos 1 y 0. Para
1 Evariste Galois (1811-1832) - matemático francés, sentó las bases del álgebra moderna.
realizar operaciones en elementos GF ( 2) no llevaron a ir más allá de este campo, se llevan a cabo módulo 2 (en general, esto está determinado por el orden del campo para campos de Galois simples).
El campo tiene una serie de propiedades matemáticas específicas. Para los elementos de campo, se definen operaciones de suma y multiplicación, y los resultados de estas operaciones deben pertenecer al mismo conjunto.
Para operaciones de suma y multiplicación, se siguen las reglas habituales de asociatividad matemática: a + (B + c) = (a + B)+ c, conmutatividad - a + b = b + a y a b = b a y distribución - a (B+ s) = a B + a con.
Para cada elemento del campo a la adición inversa debe existir (-a) y si a distinto de cero, elemento inverso de multiplicación (th ').
El campo debe contener unidad de aditivo - elemento 0 tal que a + 0 = a para cualquier elemento de campo una.
El campo debe contener unidad multiplicativa - elemento 1 tal que aL = a para cualquier elemento de campo una.
Por ejemplo, hay campos numeros reales, números racionales, números complejos. Estos campos contienen un número infinito de elementos.
De hecho, todos los conjuntos formados por permutación cíclica de una palabra de código también son palabras de código. Entonces, por ejemplo, las permutaciones cíclicas de la combinación 1000101 también serán combinaciones de códigos 0001011, 0010110, 0101100, etc. Esta propiedad permite simplificar enormemente el codificador y el descodificador, especialmente a la hora de detectar errores y corregir un solo error. La atención a los códigos cíclicos se debe al hecho de que sus altas propiedades de corrección inherentes se realizan sobre la base de métodos algebraicos relativamente simples. Al mismo tiempo, para decodificar un código de bloque lineal arbitrario, a menudo se utilizan métodos tabulares, que requieren una gran cantidad de memoria del decodificador.
Un código cíclico se llama bloque lineal. (n, k) - código que es cíclico, es decir un desplazamiento a la izquierda de cualquier palabra de código permitida en un paso también da una palabra de código permitida que pertenece al mismo código, y en la que el conjunto de palabras de código está representado por un conjunto de polinomios de grado (NS- 1) o menos divisible por el polinomio generador g (x) la licenciatura r = n-k y binomio NS n +
En un código cíclico, las palabras de código se representan mediante polinomios (polinomios)
dónde NS - longitud del código; A i - Coeficientes de campo de Galois (valores de combinación de códigos).
Por ejemplo, para la combinación de códigos 101101, la notación polinomial tiene la forma
Ejemplos de códigos cíclicos son los códigos de verificación uniforme, los códigos de repetición, los códigos de Hamming, los códigos de PC y los códigos turbo.
Código Hamming... Las capacidades de corrección de errores del código Hamming están relacionadas con la distancia mínima de codificación d 0. Se corrigen todos los errores de multiplicidad q= cnt (d 0- l) / 2 (aquí cnt significa "parte entera") y se detectan errores de multiplicidad d 0 - 1. Entonces, al verificar si hay rarezas d Q = 2 y se detectan errores únicos. En el código de Hamming d 0 = 3. Además de los bits de información, un L = log 2 Q de bits de control redundantes, donde Q - el número de bits de información. Parámetro L redondeado al valor entero superior más cercano. El código de control de bits L es el resultado invertido de la suma bit a bit (módulo de adición 2) de los números de esos bits de información, cuyos valores son iguales a uno.
Ejemplo 7.7
Supongamos que tenemos el código principal 100110, es decir Q = 6. Definamos un código adicional.
Solución
Encontramos eso L= 3 y el código complementario es
donde P es el símbolo de la operación de suma bit a bit, y después de invertir tenemos 000. Ahora el código adicional se transmitirá con el código principal. En el receptor, el código adicional se calcula nuevamente y se compara con el transmitido. El código de comparación es fijo, y si es diferente de cero, entonces su valor es el número del bit del código principal recibido erróneamente. Entonces, si se recibe el código 100010, entonces el código adicional calculado es igual a la inversión de 010SH10 = 100, es decir, 011, lo que significa un error en el tercer dígito.
La generalización de los códigos de Hamming son códigos BCH cíclicos, que permiten corregir múltiples errores en la palabra de código recibida.
Reed - códigos de Solomon se basan en campos de Galois o ceros finales. Las operaciones aritméticas son suma, resta, multiplicación, división, etc. sobre los elementos de un cero final dan un resultado que también es un elemento de ese cero. Un codificador o decodificador Reed-Solomon debe realizar estas operaciones. Todas las operaciones para implementar el código requieren equipamiento especial o software especializado.
Códigos turbo. Los códigos redundantes se pueden utilizar tanto de forma independiente como en forma de alguna combinación de varios códigos, cuando los conjuntos de símbolos de un código redundante se consideran símbolos de información elemental de otro código redundante. Tal unión comenzó a llamarse cascada código. Una gran ventaja de los códigos concatenados es que su uso permite simplificar el codificador y especialmente el descodificador en comparación con dispositivos similares de códigos no concatenados de la misma longitud y redundancia. La codificación concatenada condujo a la creación de códigos turbo. Turbocode se llama una estructura de señal paralela que consta de dos o más códigos sistemáticos. El principio básico de su construcción es el uso de varios codificadores de componentes que trabajan en paralelo. Como códigos de componentes se pueden utilizar tanto códigos de bloque como convolucionales, códigos Hamming, código PC, BCH, etc. El uso de la perforación (pinchadura) permite aumentar la velocidad relativa del código turbo, adaptando su capacidad correctora a las características estadísticas de el canal de comunicación. El principio de formación del código turbo es el siguiente: señal de entrada NS, que consiste en PARA bit, alimentado en paralelo a norte intercaladores. Cada uno de estos últimos es un dispositivo que permuta elementos en un bloque de PARA bits en orden pseudoaleatorio. La señal de salida de los intercaladores, los símbolos reordenados, se envía a los codificadores elementales correspondientes. Secuencias binarias x p yo= 1,2, ..., JV, en la salida del codificador hay símbolos de verificación, que junto con los bits de información forman una sola palabra de código. El uso del intercalador permite evitar la aparición de secuencias de errores correlacionados al decodificar códigos turbo, lo cual es importante cuando se utiliza el método de decodificación recursiva, tradicional en el procesamiento. Dependiendo de la elección del código del componente, los códigos turbo se dividen en códigos turbo convolucionales y códigos de producto en bloque.
Los códigos cíclicos se denominan así porque en ellos parte de las combinaciones de códigos o todas las combinaciones se pueden obtener mediante el desplazamiento cíclico de una o más combinaciones de códigos. El desplazamiento cíclico se lleva a cabo de derecha a izquierda y el carácter situado más a la izquierda se transfiere al final de la combinación cada vez. Los códigos cíclicos, prácticamente, todos se refieren a códigos sistemáticos, en ellos los dígitos de control e información se ubican en lugares estrictamente definidos. Además, los códigos se clasifican como códigos de bloque. Cada bloque (una letra es un caso especial de un bloque) se codifica de forma independiente.
La idea de construir códigos cíclicos se basa en el uso de polinomios irreductibles en el campo de los números binarios. Irreducible Se denominan polinomios que no pueden representarse como producto de polinomios de grados inferiores con coeficientes del mismo campo, así como los números primos no pueden representarse como producto de otros números. En otras palabras, los polinomios irreducibles son divisibles sin residuo solo por sí mismos o por unidad.
Los polinomios irreducibles en la teoría de códigos cíclicos juegan el papel de generadores de polinomios. Si la combinación de código dada se multiplica por el polinomio irreducible seleccionado, obtenemos un código cíclico, cuyas capacidades de corrección están determinadas por el polinomio irreducible.
Suponga que desea codificar una de las combinaciones de cuatro dígitos código binario... Supongamos también que esta combinación G (x) = x 3 + x 2 + 1 ® 1011. Sin fundamentar nuestra elección, tomamos de la tabla de polinomios irreducibles como polinomio generador P (x) = x 3 + x + 1 ® 1011. Luego multiplicamos G (x) por un monomio del mismo grado que el polinomio generador. De multiplicar un polinomio por un monomio de grado norte el grado de cada término en el polinomio aumentará en norte, que es equivalente a asignar norte ceros en el lado de los bits menos significativos del polinomio. Dado que el grado del polinomio irreducible seleccionado es igual a tres, la combinación de información original se multiplica por un monomio de tres grados
G (x) x n =(x 3 + x 2 + 1) x 3 = x 6 + x 5 + x 3 = 1101000.
Esto se hace para que posteriormente en el lugar de estos ceros sea posible escribir dígitos de corrección.
El valor de los dígitos correctores se obtiene a partir de los resultados de la división. G (x) x n sobre P (x):
x 6 + x 5 + 0 + x 3 + 0 + 0 + 0 ½x 3 + x + 1
x 6 + 0 + x 4 + x 3
x 5 + x 4 + 0 + 0 x 3 + x 2 + x + 1 + x 5 + 0 + x 3 + x 2
x 4 + x 3 + x 2 +0
x 4 + 0 + x 2 + x
x 3 + 0 + x + 0
x 3 + 0 + x + 1
Por lo tanto,
o en vista general
dónde Q (x)¾ privado y R (x)¾ resto de la división G (x) × x n sobre P (x).
Dado que en aritmética binaria 1 Å 1 = 0, lo que significa -1 = 1, al sumar números binarios, es posible transferir términos de una parte a otra sin cambiar el signo (si es conveniente), por lo tanto, una igualdad de la formulario a Å b = 0 se puede escribir como a = b, Y cómo a - b = 0. Las tres igualdades en este caso significan que a y B son iguales a 0, o a y B son iguales a 1, es decir tienen la misma paridad.
Por tanto, la expresión (5.1) se puede escribir como
F (x) = Q (x) P (x) = G (x) x n + R (x),
que en el caso de nuestro ejemplo dará
F (x) =(x 3 + x 2 + x + 1) (x 3 + x + 1)= (x 3 + x 2 + 1)x 3 + 1,
F (x) = 1111 1011 = 1101000 + 001 = 1101001.
El polinomio 1101001 es la combinación deseada, donde 1101 es una parte de información y 001 son los caracteres de control. Tenga en cuenta que obtendríamos la combinación deseada tanto como resultado de multiplicar una de las combinaciones del código binario completo de cuatro dígitos (en este caso 1111) por el polinomio generador, como de multiplicar la combinación dada por un monomio que tiene el mismo grado como polinomio generador elegido (en nuestro caso, se obtuvo así la combinación 1101000) con la posterior adición al producto resultante del resto de la división de este producto por el polinomio generador (en nuestro ejemplo, el resto tiene la forma 001 ).
Y aquí el papel decisivo lo juegan las propiedades del polinomio generador P (x)... El método de construcción de un código cíclico es tal que el polinomio generador participa en la formación de cada combinación de código, por lo tanto, cualquier polinomio del código cíclico es dividido por el generador sin resto. Pero solo aquellos polinomios que pertenecen al código dado son divisibles sin residuo, es decir, el polinomio generador te permite elegir las combinaciones permitidas entre todas las posibles. Si al dividir el código cíclico por el polinomio generador se obtiene un resto, entonces se ha producido un error en el código o es una combinación de algún otro código (combinación prohibida). Por el resto, se detecta la presencia de una combinación prohibida, es decir, se detecta un error. El resto de la división de los polinomios son los reconocedores de errores de los códigos cíclicos.
Por otro lado, los restos de dividir uno con ceros por el polinomio generador se utilizan para construir códigos cíclicos.
Al dividir uno con ceros por un polinomio generador, debe recordarse que la longitud del resto no debe ser menor que el número de dígitos de control, por lo tanto, en caso de escasez de dígitos en el resto, el número necesario de ceros es asignado a la derecha del resto.
01100 11111+
a partir del octavo, se repetirán los restos.
Los restos de la división se utilizan para construir matrices generadoras que, debido a su claridad y conveniencia para obtener combinaciones de derivadas, se utilizan ampliamente para construir códigos cíclicos. La construcción de una matriz generadora se reduce a la compilación de una unidad transpuesta y matriz adicional, cuyos elementos son los restos de dividir uno con ceros por el polinomio generador. P (x)... Recuerde que la matriz de identidad transpuesta es una matriz cuadrada, todos los elementos de los cuales son ceros, excepto los elementos ubicados diagonalmente de derecha a izquierda de arriba a abajo (en una matriz no transpuesta, la diagonal con elementos de identidad es de izquierda a derecha de arriba a abajo). Los elementos de la matriz adicional se asignan a la derecha de la matriz de identidad transpuesta. Solo aquellos residuos cuyo peso sea W³ d 0- 1, donde d 0 Es la distancia mínima del código. La longitud de los residuos debe ser al menos el número de bits de control y el número de residuos debe ser igual al número de bits de información.
Las filas de la matriz generadora son las primeras combinaciones. código fuente... Las combinaciones restantes del código se obtienen sumando módulo 2 todas las combinaciones posibles de filas de la matriz generadora.
Ejemplo.
Construya una matriz generadora completa de un código cíclico que detecte todos los errores simples y dobles al transmitir combinaciones binarias de 10 bits.
Solución.
De acuerdo con la tabla 5.12, seleccione el valor más cercano k ³ 10.
Tabla 5.12 - Relaciones entre la información y los caracteres de verificación para un código con una longitud de hasta 16 bits
| norte | k | ρ | norte | k | ρ |
Según la tabla, este valor será k = 11, mientras r = 4, a
n = 15. También elegimos el polinomio generador x 4 + x 3 +1.
La matriz generadora completa se construye a partir de la matriz de transposición unitaria en forma canónica y una matriz adicional correspondiente a los dígitos de control.
Transponer matriz para k = 11 se parece a:
Se puede construir una matriz adicional a partir del resto de la división de una combinación en forma de uno seguido de ceros (la última fila de la matriz de identidad transpuesta) por el polinomio generador seleccionado.
La matriz completa del generador se verá así:
El método anterior para construir matrices generadoras no es el único. La matriz generadora se puede construir como resultado de la multiplicación directa de los elementos de la matriz identidad por el polinomio generador. Esto suele ser más conveniente que encontrar el resto de una división. Los códigos resultantes no difieren de ninguna manera de los códigos construidos a partir de matrices generadoras, en las que la matriz adicional consiste en los restos de dividir uno con ceros por el polinomio generador.
La matriz generadora se puede construir de la misma manera mediante desplazamiento cíclico de la combinación obtenida como resultado de multiplicar la fila de la matriz identidad de rango k en el polinomio generador.
Los errores en los códigos cíclicos se detectan utilizando los restos de dividir la combinación resultante por el polinomio generador. El resto de la división son identificadores de error, pero no indican directamente la ubicación del error en el código cíclico.
La idea de corrección de errores se basa en el hecho de que la combinación errónea después de un cierto número de desplazamientos cíclicos se “ajusta” al resto de tal manera que, junto con el resto, da la palabra de código corregida. En este caso, el resto no es más que la diferencia entre los símbolos distorsionados y correctos, las unidades en el resto están exactamente en los lugares de los bits distorsionados en la combinación ajustada por cambios cíclicos. La combinación distorsionada se ajusta hasta que el número de unos en el resto sea igual al número de errores en el código. En este caso, naturalmente, el número de unos puede ser igual al número de errores s, corregido por este código (el código corrige 3 errores y 3 errores en una combinación distorsionada), o menos s(el código corrige 3 errores, y en la combinación aceptada 1 error).
No importa la ubicación del error en la combinación de códigos. Si k ³ (n / 2), luego de un cierto número de turnos todos los errores estarán en la zona de la acción "única" del polinomio generador, es decir, es suficiente para obtener un resto, cuyo peso es W £ s, y esto ya será suficiente para corregir la combinación distorsionada.
El proceso de corrección de errores se analiza en detalle a continuación utilizando ejemplos de códigos específicos de construcción.