Códigos BCH primitivos de sentido estrecho
Dado un número primo q y prime poder q m con números enteros positivos m y d tal que d ≤ q m - 1 un código BCH-sentido estrecho primitiva sobre el, campo finito (campo de Galois o) GF ( q ) con la longitud de código de n = q m - 1 y la distancia al menos d se construye mediante el siguiente método.
Sea α un elemento primitivo de GF ( q m ) . Para cualquier entero positivo i , sea m i ( x ) el polinomio mínimo con coeficientes en GF ( q ) de α i . El polinomio generador del código BCH se define como el mínimo común múltiplo g ( x ) = lcm ( m 1 ( x ),…, m d - 1 ( x )) . Se puede ver que g ( x ) es un polinomio con coeficientes en GF ( q ) y divide x n - 1 . Por lo tanto, el código polinomial definido por g ( x ) es un código cíclico.
Ejemplo
Deje q = 2 y m = 4 (por lo tanto n = 15 ). Consideraremos diferentes valores de d . Para GF (16) = GF (2 4 ) basado en el polinomio x 4 + x + 1 con raíz primitiva α = x +0 hay polinomios mínimos m i ( x ) con coeficientes en GF (2) que satisfacen
Los polinomios mínimos de las catorce potencias de α son
El código BCH con tiene polinomio generador
Tiene una distancia de Hamming mínima de al menos 3 y corrige hasta un error. Dado que el polinomio generador es de grado 4, este código tiene 11 bits de datos y 4 bits de suma de control.
El código BCH con tiene polinomio generador
Tiene una distancia de Hamming mínima de al menos 5 y corrige hasta dos errores. Dado que el polinomio generador es de grado 8, este código tiene 7 bits de datos y 8 bits de suma de comprobación.
El código BCH con tiene polinomio generador
Tiene una distancia mínima de Hamming de al menos 7 y corrige hasta tres errores. Dado que el polinomio generador es de grado 10, este código tiene 5 bits de datos y 10 bits de suma de comprobación. (Este polinomio generador en particular tiene una aplicación del mundo real, en los patrones de formato del código QR ).
El código BCH con y superior tiene polinomio generador
Este código tiene una distancia mínima de Hamming de 15 y corrige 7 errores. Tiene 1 bit de datos y 14 bits de suma de control. De hecho, este código tiene solo dos palabras en clave: 000000000000000 y 111111111111111.
Códigos BCH generales
Los códigos BCH generales difieren de los códigos BCH primitivos de sentido estrecho en dos aspectos.
Primero, el requisito de que ser un elemento primitivo de se puede relajar. Al relajar este requisito, la longitud del código cambia de a el orden del elemento
En segundo lugar, las raíces consecutivas del polinomio generador pueden ir de en vez de
Definición. Arreglar un campo finito dónde es un poder primordial. Elija números enteros positivos tal que y es el orden multiplicativo de modulo
Como antes, deja ser un primitivola raíz de la unidad en y deja ser el polinomio mínimo sobre de para todos El polinomio generador del código BCH se define como el mínimo común múltiplo
Nota: si como en la definición simplificada, entonces es 1, y el orden de modulo es Por tanto, la definición simplificada es un caso especial de la general.
Casos especiales
- Un código BCH con se denomina código BCH de sentido estricto .
- Un código BCH con se llama primitivo .
El polinomio generador de un código BCH tiene coeficientes de En general, un código cíclico sobre con ya que el polinomio generador se llama código BCH sobre El código BCH terminado y polinomio generador con sucesivos poderes de como raíces es un tipo de código Reed-Solomon donde el alfabeto del decodificador (síndromes) es el mismo que el alfabeto del canal (polinomio de datos y generador), todos los elementos de. [7] El otro tipo de código Reed Solomon es un código Reed Solomon de vista original que no es un código BCH.
Debido a que cualquier polinomio que sea múltiplo del polinomio generador es una palabra de código BCH válida, la codificación BCH es simplemente el proceso de encontrar algún polinomio que tenga el generador como factor.
El código BCH en sí no es prescriptivo sobre el significado de los coeficientes del polinomio; conceptualmente, la única preocupación de un algoritmo de decodificación BCH es encontrar la palabra de código válida con la distancia mínima de Hamming a la palabra de código recibida. Por lo tanto, el código BCH puede implementarse como un código sistemático o no, dependiendo de cómo el implementador elija incrustar el mensaje en el polinomio codificado.
Codificación no sistemática: el mensaje como factor
La forma más sencilla de encontrar un polinomio que sea múltiplo del generador es calcular el producto de algún polinomio arbitrario y el generador. En este caso, el polinomio arbitrario se puede elegir utilizando los símbolos del mensaje como coeficientes.
Como ejemplo, considere el polinomio generador , elegido para su uso en el código binario BCH (31, 21) utilizado por POCSAG y otros. Para codificar el mensaje de 21 bits {101101110111101111101}, primero lo representamos como un polinomio sobre:
Luego, calcule (también sobre ):
Por tanto, la palabra de código transmitida es {1100111010010111101011101110101}.
El receptor puede utilizar estos bits como coeficientes en y, después de la corrección de errores para garantizar una palabra de código válida, puede volver a calcular
Codificación sistemática: el mensaje como prefijo
Un código sistemático es aquel en el que el mensaje aparece literalmente en algún lugar dentro de la palabra en clave. Por lo tanto, la codificación BCH sistemática implica primero incrustar el polinomio del mensaje dentro del polinomio de la palabra de código y luego ajustar los coeficientes de los términos restantes (que no son de mensaje) para asegurar que es divisible por .
Este método de codificación aprovecha el hecho de que restar el resto de un dividendo da como resultado un múltiplo del divisor. Por lo tanto, si tomamos nuestro polinomio de mensaje como antes y multiplicarlo por (para "desplazar" el mensaje fuera del camino del resto), podemos usar la división euclidiana de polinomios para producir:
Aquí vemos que es una palabra de código válida. Como es siempre de grado menor que (que es el grado de ), podemos restarlo con seguridad de sin alterar ninguno de los coeficientes del mensaje, por lo tanto, tenemos nuestro como
Encima (es decir, con códigos BCH binarios), este proceso es indistinguible de agregar una verificación de redundancia cíclica , y si un código BCH binario sistemático se usa solo para fines de detección de errores, vemos que los códigos BCH son solo una generalización de las matemáticas de la redundancia cíclica cheques .
La ventaja de la codificación sistemática es que el receptor puede recuperar el mensaje original descartando todo después de la primera coeficientes, después de realizar la corrección de errores.
Existen muchos algoritmos para decodificar códigos BCH. Los más comunes siguen este esquema general:
- Calcule los síndromes s j para el vector recibido
- Determine el número de errores t y el polinomio localizador de errores Λ (x) de los síndromes
- Calcule las raíces del polinomio de ubicación de error para encontrar las ubicaciones de error X i
- Calcule los valores de error Y i en esas ubicaciones de error
- Corrige los errores
Durante algunos de estos pasos, el algoritmo de decodificación puede determinar que el vector recibido tiene demasiados errores y no se puede corregir. Por ejemplo, si no se encuentra un valor apropiado de t , la corrección fallará. En un código truncado (no primitivo), una ubicación de error puede estar fuera de rango. Si el vector recibido tiene más errores de los que el código puede corregir, el decodificador puede producir sin saberlo un mensaje aparentemente válido que no es el que se envió.
Calcular los síndromes
El vector recibido es la suma de la palabra de código correcta y un vector de error desconocido Los valores del síndrome se forman considerando como polinomio y evaluándolo en Por tanto, los síndromes son [8]
por a
Desde son los ceros de de los cuales es un múltiplo, Por tanto, el examen de los valores del síndrome aísla el vector de error para poder empezar a resolverlo.
Si no hay error, para todos Si todos los síndromes son cero, entonces se realiza la decodificación.
Calcular el polinomio de ubicación del error
Si hay síndromes distintos de cero, entonces hay errores. El decodificador necesita averiguar cuántos errores y la ubicación de esos errores.
Si hay un solo error, escríbalo como dónde es la ubicación del error y es su magnitud. Entonces los dos primeros síndromes son
así que juntos nos permiten calcular y proporcionar información sobre (determinándolo completamente en el caso de los códigos Reed-Solomon).
Si hay dos o más errores,
No es inmediatamente obvio cómo comenzar a resolver los síndromes resultantes para las incógnitas. y
El primer paso es encontrar, compatible con síndromes computados y con el mínimo posible polinomio localizador:
Dos algoritmos populares para esta tarea son:
- Algoritmo Peterson-Gorenstein-Zierler
- Algoritmo de Berlekamp-Massey
Algoritmo Peterson-Gorenstein-Zierler
El algoritmo de Peterson es el paso 2 del procedimiento de decodificación BCH generalizado. El algoritmo de Peterson se utiliza para calcular los coeficientes polinomiales del localizador de errores. de un polinomio
Ahora el procedimiento del algoritmo Peterson-Gorenstein-Zierler. [9] Espere tener al menos 2 t síndromes s c ,…, s c +2 t −1 . Sea v = t .
- Empiece generando el matriz con elementos que son valores de síndrome
- Generar un vector con elementos
- Dejar denotar los coeficientes polinomiales desconocidos, que están dados por
- Forme la ecuación matricial
- Si el determinante de la matriz es distinto de cero, entonces podemos encontrar una inversa de esta matriz y resolver los valores de desconocido valores.
- Si entonces sigue
Si luego declarar un polinomio de localizador de errores vacío Detenga el procedimiento de Peterson. final colocar
continuar desde el comienzo de la decodificación de Peterson haciendo más pequeñas - Después de tener valores de , tienes el polinomio del localizador de errores.
- Detenga el procedimiento de Peterson.
Factor polinomio localizador de errores
Ahora que tienes el polinomio, sus raíces se pueden encontrar en la forma por fuerza bruta, por ejemplo, utilizando el algoritmo de búsqueda de Chien . Los poderes exponenciales del elemento primitivocederá las posiciones donde ocurren errores en la palabra recibida; de ahí el nombre polinomio 'localizador de errores'.
Los ceros de Λ ( x ) son α - i 1 ,…, α - i v .
Calcular valores de error
Una vez que se conocen las ubicaciones de los errores, el siguiente paso es determinar los valores de error en esas ubicaciones. Luego, los valores de error se utilizan para corregir los valores recibidos en esas ubicaciones para recuperar la palabra de código original.
Para el caso de BCH binario, (con todos los caracteres legibles) esto es trivial; simplemente invierta los bits de la palabra recibida en estas posiciones, y tendremos la palabra de código corregida. En el caso más general, los pesos de error se puede determinar resolviendo el sistema lineal
Algoritmo de Forney
Sin embargo, existe un método más eficiente conocido como algoritmo de Forney .
Dejar
Y el polinomio del evaluador de errores [10]
Finalmente:
dónde
Que si los síndromes pudieran explicarse por una palabra de error, que podría ser distinta de cero solo en las posiciones , entonces los valores de error son
Para códigos BCH de sentido estrecho, c = 1, por lo que la expresión se simplifica a:
Explicación del cálculo del algoritmo de Forney
Se basa en la interpolación de Lagrange y técnicas de generación de funciones .
Considerar y en aras de la simplicidad supongamos por y por Luego
Queremos calcular incógnitas y podríamos simplificar el contexto eliminando el condiciones. Esto conduce al polinomio del evaluador de errores
Gracias a tenemos
Gracias a (el truco de interpolación de Lagrange) la suma degenera en un solo sumando para
Llegar deberíamos deshacernos del producto. Podríamos calcular el producto directamente a partir de raíces ya calculadas. de pero podríamos usar una forma más simple.
Como derivado formal
obtenemos de nuevo solo un verano en
Así que finalmente
Esta fórmula es ventajosa cuando se calcula la derivada formal de formulario
flexible:
dónde
Decodificación basada en algoritmo euclidiano extendido
Un proceso alternativo de encontrar tanto el polinomio Λ como el polinomio localizador de errores se basa en la adaptación de Yasuo Sugiyama del algoritmo euclidiano extendido . [11] La corrección de caracteres ilegibles también podría incorporarse fácilmente al algoritmo.
Dejar ser posiciones de caracteres ilegibles. Uno crea polinomios localizando estas posiciones Establezca los valores en las posiciones ilegibles en 0 y calcule los síndromes.
Como ya hemos definido para la fórmula de Forney, dejemos
Ejecutemos un algoritmo euclidiano extendido para localizar el mínimo común divisor de polinomios y El objetivo no es encontrar el mínimo común divisor, sino un polinomio de grado como máximo y polinomios tal que Bajo grado de garantías, que satisfaría extendido (por ) definiendo las condiciones para
Definiendo y usando en el lugar de en la fórmula de Fourney nos dará valores de error.
La principal ventaja del algoritmo es que mientras tanto calcula requerido en la fórmula de Forney.
Explicación del proceso de decodificación
El objetivo es encontrar una palabra en clave que difiera lo más posible de la palabra recibida en posiciones legibles. Al expresar la palabra recibida como una suma de la palabra de código más cercana y la palabra de error, estamos tratando de encontrar la palabra de error con un número mínimo de no ceros en posiciones legibles. Síndrom restringe el error palabra por condición
Podríamos escribir estas condiciones por separado o podríamos crear un polinomio
y comparar coeficientes cerca de potencias a
Suponga que hay una letra ilegible en la posición podríamos reemplazar un conjunto de síndromes por conjunto de síndromes definido por ecuación Suponga que para una palabra de error todas las restricciones por conjunto original de síndromes se mantienen, que
Nuevo conjunto de síndromes restringe el vector de error
de la misma manera que el conjunto original de síndromes restringió el vector de error Excepto la coordenada donde tenemos un es cero, si Con el fin de localizar posiciones de error, podríamos cambiar el conjunto de síndromes de manera similar para reflejar todos los caracteres ilegibles. Esto acorta el conjunto de síndromes por
En la formulación polinomial, la sustitución de síndromes establece por conjunto de síndromes lleva a
Por lo tanto,
Después de la sustitución de por , se requeriría una ecuación para coeficientes cercanos a potencias
Se podría considerar buscar posiciones de error desde el punto de vista de eliminar la influencia de posiciones dadas de manera similar a como ocurre con los caracteres ilegibles. Si encontramosposiciones tales que la eliminación de su influencia conduce a la obtención de un conjunto de síndromes constituidos por ceros, que existe un vector de error con errores solo en estas coordenadas. Si denota el polinomio eliminando la influencia de estas coordenadas, obtenemos
En el algoritmo euclidiano, intentamos corregir como máximo errores (en posiciones legibles), porque con un mayor recuento de errores podría haber más palabras de código en la misma distancia de la palabra recibida. Por lo tanto, para que estamos buscando, la ecuación debe ser válida para coeficientes cercanos a potencias a partir de
En la fórmula de Forney, podría multiplicarse por un escalar dando el mismo resultado.
Podría suceder que el algoritmo euclidiano encuentre de grado superior a teniendo un número de raíces diferentes igual a su grado, donde la fórmula de Fourney podría corregir errores en todas sus raíces, de todos modos corregir tantos errores podría ser arriesgado (especialmente sin otras restricciones en la palabra recibida). Por lo general, después de recibirde mayor grado, decidimos no corregir los errores. La corrección podría fallar en el casotiene raíces con mayor multiplicidad o el número de raíces es menor que su grado. La falla también podría detectarse mediante la fórmula de Forney que devuelve un error fuera del alfabeto transmitido.
Corrige los errores
Utilizando los valores de error y la ubicación del error, corrija los errores y forme un vector de código corregido restando los valores de error en las ubicaciones de error.
Ejemplos de decodificación
Decodificación de código binario sin caracteres ilegibles
Considere un código BCH en GF (2 4 ) con y . (Esto se usa en códigos QR ). Sea [1 1 0 1 1] el mensaje que se va a transmitir, o en notación polinomial, Los símbolos de "suma de comprobación" se calculan dividiendo por y tomando el resto, resultando en o [1 0 0 0 0 1 0 1 0 0]. Estos se añaden al mensaje, por lo que la palabra de código transmitida es [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].
Ahora, imagine que hay dos errores de bit en la transmisión, por lo que la palabra de código recibida es [1 0 0 1 1 1 0 0 0 1 1 0 1 0 0]. En notación polinomial:
Para corregir los errores, primero calcule los síndromes. Tomando tenemos y A continuación, aplique el procedimiento de Peterson mediante la reducción de filas de la siguiente matriz aumentada.
Debido a la fila cero, S 3 × 3 es singular, lo cual no es ninguna sorpresa ya que solo se introdujeron dos errores en la palabra de código. Sin embargo, la esquina superior izquierda de la matriz es idéntica a [ S 2 × 2 | C 2 × 1 ] , que da lugar a la solución El polinomio del localizador de errores resultante es que tiene ceros en y Los exponentes de corresponden a las ubicaciones de error. No es necesario calcular los valores de error en este ejemplo, ya que el único valor posible es 1.
Decodificación con caracteres ilegibles
Suponga el mismo escenario, pero la palabra recibida tiene dos caracteres ilegibles [1 0 0? 1 1? 0 0 1 1 0 1 0 0]. Reemplazamos los caracteres ilegibles por ceros mientras creamos el polinomio que refleja sus posiciones. Calculamos los síndromes y (Utilizando la notación logarítmica que es independiente de los isomorfismos GF (2 4 ). Para la comprobación de los cálculos, podemos utilizar la misma representación para la suma que se utilizó en el ejemplo anterior. Descripción hexadecimal de las potencias de son consecutivamente 1,2,4,8,3,6, C, B, 5, A, 7, E, F, D, 9 con la suma basada en xor bit a bit.)
Hagamos polinomio del síndrome
calcular
Ejecute el algoritmo euclidiano extendido:
Hemos alcanzado el polinomio de grado como máximo 3, y como
obtenemos
Por lo tanto,
Dejar No te preocupes por eso Encuentre por fuerza bruta una raíz de Las raices son y (después de encontrar, por ejemplo podemos dividir por monom correspondiente y la raíz del monom resultante se podría encontrar fácilmente).
Dejar
Busquemos valores de error usando la fórmula
dónde son raíces de Obtenemos
Hecho de que no debería sorprendernos.
Por tanto, el código corregido es [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].
Decodificación con caracteres ilegibles con una pequeña cantidad de errores
Vamos a mostrar el comportamiento del algoritmo para el caso con un pequeño número de errores. Deje que la palabra recibida sea [1 0 0? 1 1? 0 0 0 1 0 1 0 0].
Nuevamente, reemplace los caracteres ilegibles por ceros mientras crea el polinomio que refleja sus posiciones Calcule los síndromes y Crear polinomio de síndrome
Ejecutemos el algoritmo euclidiano extendido:
Hemos alcanzado el polinomio de grado como máximo 3, y como
obtenemos
Por lo tanto,
Dejar No te preocupes por eso La raíz de es
Dejar
Busquemos valores de error usando la fórmula dónde son raíces de polinomio
Obtenemos
El hecho de que no debería sorprendernos.
Por tanto, el código corregido es [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].