Codificacion Expo

UNIVERSIDAD DE LAS
FUERZAS ARMADAS-ESPE
COMUNICACIÓN Y CODIFICACIÓN DIGITAL
Tema: Códigos BCH
Integrantes:
Xavier Chango
Alex Guamán
Alexis Ramírez
Gissela Vega
CÓDIGOS BOSE-CHAUDHURI-
HOCQUENGHEM (BCH)
Son una clase de códigos cíclicos que incluyen códigos sobre alfabetos BINARIOS y NO
BINARIOS.
La decodificación de estos códigos es posible con el uso de algoritmos de decodificación

algebraica eficientes, ya que su estructura así lo permite.
Los códigos BCH presentan una amplia variedad de parámetros de diseño como: tasas de
código y longitudes de bloque de bajas a moderadas.
Estructura de los Códigos BCH
Dado que los códigos BCH son también códigos cíclicos, se los puede describir en términos
de su polinomio generador g(X)
Los denominados códigos BCH primitivos binarios tienen una longitud de bloque de:
Y se diseñan para conseguir una capacidad de detección garantizada de errores de al menos

t errores para cualquier:
Para dos enteros positivos
Es posible diseñar un código BCH cuyos parámetros satisfagan las relaciones:

1. La primera igualdad determina la longitud de bloque del código.
2. La primera desigualdad establece un límite en el número de bits de verificación de
paridad del código.
3. La segunda desigualdad establece que este código es capaz de corregir al menos t
errores.
A este código se lo conoce con el nombre de código BCH de corrección de t errores

aleatorios por palabra de código, sin embargo existen casos en los que el código puede
corregir más de t errores
Polinomio generador para códigos BCH
Para diseñar un código BCH de corrección de t- errores, se elige α, como un elemento
primitivo de:
Entonces g(X) es el polinomio generador del código BCH y se define como el polinomio de
grado más bajo g(X) sobre GF(2) tal que:
son las raíces.
De la definición de polinomio mínimo de un elemento de campo, se sabe que cualquier

polinomio sobre GF(2) que tiene β ∈ GF(2) como una raíz que es divisible para:
siendo el polinomio mínimo de β.

Por lo tanto g(X) debe ser divisible para:
Dado que g(X) es un polinomio de menor grado se tiene que:
donde MCM denota el mínimo común múltiplo de
También hay que tener en cuenta por ejemplo:
son los mismos ya que los son conjugados y por lo tanto tienen el mismo
polinomio mínimo.
Por lo tanto, la expresión para g(X) es suficiente considerar sólo valores impares de α, es
decir
ya dado que el grado de j no excede m, el grado de g(X) es como máximo mt.
Por lo tanto: n-k≤ mt.
Supongamos que c(X) es una palabra de código polinomial del código BCH diseñado, por la
propiedad cíclica del código se sabe que g(X) es un divisor de c(X). Por lo tanto, todos los
son raíces de c(X); es decir, para cualquier palabra de código polinomial c(X) se tiene:
Las ecuaciones anteriores son condiciones necesarias y suficientes para un polinomio de

grado menor que n para ser una palabra de código polinomial del código BCH.
Decodificación de códigos BCH
Como los códigos BCH son códigos cíclicos, cualquier algoritmo de

decodificación para códigos cíclicos puede ser aplicado a los códigos
BCH. Una ventaja de los códigos BCH es la facilidad con que pueden
ser decodificados, ya que se usan métodos algebraicos que se
conocen como síndrome de decodificación. y se pueden usar otros más
como son:
● Decodificador Meggit
● Algoritmo Berlekamp-Massey
Sin embargo, la estructura adicional en los códigos BCH hace posible el uso más
eficiente de algoritmos de decodificación, particularmente cuando se usan códigos con
longitudes de bloque largas
Supongamos que una palabra de código c está asociada con el polinomio de palabra
de código c (X).
asumimos que el error polinomial es e(X) por lo que el polinomio recibido es:
Denotemos el valor de y (X) en por Si, es decir, los síndromes definidos por:
Obviamente si e (X) es cero, o es igual a una palabra de código distinta de cero, los
síndromes son todo cero. El síndrome puede calcularse a partir de la secuencia recibida
y utilizando 𝐺𝐹 (2𝑚 ).
Ahora supongamos que ha habido (v) errores en la transmisión de c, donde v <= t.

Denotamos la ubicación de estos errores por J1, J2, …, Jv. Donde si no existe pérdida
podemos suponer que:
0< J1 < J2 < … < Jv < n-1
Por lo tanto:
Concluimos que:
Estos son un conjunto de 2𝑡 ecuaciones con v incógnitas, a encontrar J1, J2, …, Jv
o su equivalente .Cualquier método para resolver ecuaciones se puede
aplicar para encontrar incógnitas obteniendo las ubicaciones de error J1,J2, … ,Jv.
Obteniendo las ubicaciones de error determinadas, cambiamos el bit recibido en esas

ubicaciones para encontrar la palabra de código transmitida c.
Para definir el número de ubicación de error sustituimos: obteniendo:

Resolver este conjunto de ecuaciones determina el valor de β en el cual se encuentran
ubicados los errores.Obviamente, los β son miembros de 𝐺𝐹(2𝑚 ) y la resolución de
estas ecuaciones requiere aritmética sobre 𝐺𝐹(2𝑚 ), que presenta como inconveniente
muchas soluciones para el sistema.
Para que cumpla con distancia mínima de Hamming lo que se busca es una solución
con el menor número de β posible.
Para resolver estas ecuaciones, introducimos el polinomio localizador de errores

como:
Encontrar las raíces de este polinomio determina la ubicación de los errores

Reemplazando estos valores obtenemos una ecuación que relaciona los coeficientes σ(X) y
los síndromes:
Necesitamos obtener el polinomio de grado más bajo σ(X) cuyos coeficientes satisfacen este
conjunto de ecuaciones. Después de determinar σ(X), tenemos que encontrar sus raíces
𝒊 ) ya que el inverso de las raíces proporciona la ubicación de los errores.
(𝜷−𝟏
El algoritmo de decodificación
Berlekamp-Massey para códigos BCH
Pasos para implementar el algoritmo de Berlekamp-Massey

•Se empieza por encontrar un polinomio de grado más bajo
Que satisfaga la siguiente ecuación:
•Ahora se comprueba si satisface la ecuación

•Si satisface la segunda ecuación, se establece
De lo contrario, se introduce un término de corrección a para

obtener , el polinomio del grado más bajo que satisface las dos
primeras ecuaciones.
Este proceso continúa hasta que se obtenga un polinomio de grado mínimo
que satisfaga todas las ecuaciones.
Si es el polinomio de menor grado que satisface las primeras 𝜇 ecuaciones
Para encontrar , se calcula la discrepancia, denotada por como :
Si no se necesita ninguna corrección que satisface la 𝜇+1 ecuación

y en este caso se establece que:
Si la corrección es necesaria. En este caso está dado por:
donde se selecciona de modo que . Este es el polinomio de menor grado

que satisface las primeras 𝜇+1 ecuaciones. Este proceso continúa hasta que se deriva
El algoritmo de Berlekamp-Massey se puede llevar a cabo mejor si se comienza con una
tabla como la siguiente:
Bibliografía
Proakis, John & Salehi, Masoud. (2007). Digital Communications (Quinta

ed.). Estados Unidos de América: McGraw-Hill Education

Codificacion Expo

Cargado por

Copyright:

Formatos disponibles

Codificacion Expo

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Codificacion Expo

Cargado por

Copyright:

Formatos disponibles

UNIVERSIDAD DE LAS

La decodificación de estos códigos es posible con el uso de algoritmos de decodificación

Y se diseñan para conseguir una capacidad de detección garantizada de errores de al menos

Es posible diseñar un código BCH cuyos parámetros satisfagan las relaciones:

A este código se lo conoce con el nombre de código BCH de corrección de t errores

son las raíces.

De la definición de polinomio mínimo de un elemento de campo, se sabe que cualquier

siendo el polinomio mínimo de β.

Dado que g(X) es un polinomio de menor grado se tiene que:

donde MCM denota el mínimo común múltiplo de

También hay que tener en cuenta por ejemplo:

ya dado que el grado de j no excede m, el grado de g(X) es como máximo mt.

Por lo tanto: n-k≤ mt.

Las ecuaciones anteriores son condiciones necesarias y suficientes para un polinomio de

Como los códigos BCH son códigos cíclicos, cualquier algoritmo de

Ahora supongamos que ha habido (v) errores en la transmisión de c, donde v <= t.

0< J1 < J2 < … < Jv < n-1

Obteniendo las ubicaciones de error determinadas, cambiamos el bit recibido en esas

Para definir el número de ubicación de error sustituimos: obteniendo:

Para resolver estas ecuaciones, introducimos el polinomio localizador de errores

Encontrar las raíces de este polinomio determina la ubicación de los errores

Pasos para implementar el algoritmo de Berlekamp-Massey

Que satisfaga la siguiente ecuación:

•Ahora se comprueba si satisface la ecuación

•Si satisface la segunda ecuación, se establece

De lo contrario, se introduce un término de corrección a para

Si es el polinomio de menor grado que satisface las primeras 𝜇 ecuaciones

Para encontrar , se calcula la discrepancia, denotada por como :

Si no se necesita ninguna corrección que satisface la 𝜇+1 ecuación

Si la corrección es necesaria. En este caso está dado por:

donde se selecciona de modo que . Este es el polinomio de menor grado

Proakis, John & Salehi, Masoud. (2007). Digital Communications (Quinta

También podría gustarte