Elementos de Álgebra brunat2 EA 2015

Prévia do material em texto

1 
 
UNIVERSIDADE ESTADUAL DE CAMPINAS 
 
INSTITUTO DE MATEMÁTICA, ESTATÍSTICA E COMPUTAÇÃO CIENTÍFICA. 
 
 
 
 
 
 
 
 
 
CÓDIGOS BCH 
 
 
 
 
 
 
 
 
 
 
 
Disciplina MA673 – Elementos de Álgebra Turma: A 
Professor responsável: Fernando Eduardo Torres Orihuela 
Alunos: Natália De Nadai RA: 034964 
 Bruno Cézar da Silva RA:143204 
 
 
 
 
 
 
 
 
 
 
 
Campinas, 07 julho de 2015 
 2 
ÍNDICE 
 
1. INTRODUÇÃO...................................................................................................3 
2. PARTE HISTÓRIA.............................................................................................4 
3. DEFINIÇÕES.....................................................................................................5 
 3.1. CÓDIGOS CÍCLICOS..........................................................................5 
 3.2. COMO GERAR CÓDIGOS CÍCLICOS................................................5 
 3.3.POLINÔMIOS USADOS EM CÓDIGOS CÍCLICOS.............................6 
 3.4.CORPOS FINITOS...............................................................................6 
4.CÓDIGOS BCH..................................................................................................7 
 4.1.CONSTRUÇÃO DE CÓDIGOS BCH....................................................8 
 4.2.TIPOS DE CÓDIGOS BCH...................................................................9 
 4.3.CÓDIGO BCH PRIMITIVO....................................................................9 
 4.4.DECODIFICAÇÃO DE CÓDIGOS BCH................................................9 
 4.5.CÓDIGOS BCH PRIMITIVOS SOBRE GF(q).....................................10 
5. CONCLUSÃO..................................................................................................11 
6. BIBLIOGRAFIA................................................................................................12 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 3 
1.INTRODUÇÃO 
 
Nesse trabalho será aborado um breve conhecimento histórico sobre os 
códigos BCH, além de discutir códigos cíclicos , como gerá-los e os polinômios 
utilizados. 
Terá uma breve discussão sobre os corpos finitos, pois são as classes 
cíclicas de correção de erros (constituídas à partir de corpos finitos) que geram 
os códigos BCH. 
A utilização dos códigos controladores de erros provém da necessidade 
de armazenar e/ou transmitir grandes volumes de dados, muitos dos quais são 
sensíveis a erros. Os códigos controladores de erros são largamente utilizados 
em sistemas de comunicações via satélite, em redes locais de computadores, 
em discos a laser, em sistemas de tele-supervisão e controle e em automação 
bancária. 
Portanto, onde se deseja uma alta confiabilidade na transmissão e/ou 
armazenamento de dados, faz-se necessária a implementação de sistemas 
codificadores e decodificadores para códigos controladores de erro. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 4 
2.PARTE HISTÓRICA 
 
A primeira aplicação bem sucedida de codificação ocorreu nas comunicações 
espaciais. Só assim tem sido possível, por exemplo, a recepção de imagens e 
outras informações. 
Hoje em dia é muito fácil encontrar sistema de comunicação para controle de 
erros para qualquer sistema de comunicação moderno, como por exemplo as 
televisões digitais. 
A técnica de controle de erros mais amplamente usada talvez seja a que detecta 
erros por várias “verificações cíclicas” (CRC). 
Os códigos BCH formam uma classe cíclica de correção de erros que são 
construídos à partir de corpos finitos. Esse códigos foram inventados em 1959 
por Alexis Hocquenghem, Raj Chandra Bose e Ray-Chaudhurj. Sendo BCH a 
abreviação dos nomes desses inventores. 
Durante a concepção de um código, existe um controle preciso sobre o número 
de erros, essa é a característica chave do código BCH, pois é possível projetar 
códigos BCH binários que podem corrigir múltiplos erros de bits, além da 
facilidade com que podem ser decodificados. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 5 
3.DEFINIÇÕES 
 
3.1) Códigos Cíclicos 
Os códigos cíclicos são os códigos de blocos lineares mais úteis e populares. 
 
 
 
• Os códigos cíclicos são "manuseáveis" algebricamente, com polinómios, sem 
necessidade de recorrer a matrizes e vectores. 
• Num código cíclico um deslocamento de uma palavra de código conduz a uma 
outra palavra de código. 
• Mas, só n-1 palavras de código são geradas por deslocamento cíclico. 
Para gerar por deslocamento todo o conjunto de 2k palavras de código 
temos de considerar várias palavras. 
 
3.2) Como gerar códigos cíclicos? 
 
Vamos ver duas maneiras de calcular as palavras de código a partir da 
mensagem, uma para códigos sistemáticos. 
 
 6 
 
 
3.3) Polinômios usados em códigos cíclicos. 
 
 
3.4) Corpos finitos. 
 
É um corpo em que o conjunto dos elementos é finito, algumas de suas muitas 
aplicações são na teoria dos códigos, teoria dos números e teoria matemática 
dos jogos. 
O corpo Fp = (Zp, ⊕p, ⊗p) dos inteiros módulo p (p primo) é, evidentemente, o 
exemplo mais familiar de corpo finito. Muitas das suas propriedades 
generalizam-se aos corpos finitos arbitrários. Os corpos Fp representam um 
papel muito importante na teoria dos corpos pois, como vimos, todo o corpo de 
característica p contém uma cópia isomorfa de Fp (como seu subcorpo primo) e 
pode então ser visto como uma extensão de Fp. Esta observação, 
conjuntamente com o fato óbvio de que todo o corpo finito tem característica 
finita (prima), é fundamental para a classificação dos corpos finitos. 
Exemplos mais comuns: 
 Todo anel , para p primo, é um corpo, logo é um corpo finito. 
 Existe um (único, significando que todos são isomorfos) corpo finito com 4 
elementos. Seja K este corpo. É fácil ver que o grupo aditivo (K, +) não pode 
ser isomorfo a (porque, qualquer que seja a operação de 
 7 
multiplicação temos que , e 
um corpo não pode ter divisores de zero). Então temos que (K, +) deve ser 
isomorfo ao grupo de Klein de ordem 4. Sem perda de generalidade, 
podemos definir K = { }, e, como a equação só pode ter 
2 raízes (0 e 1), e a equação tem 1 como raiz dupla, temos 
que . Com isso, completa-se a tabela multiplicativa do corpo de 
ordem 4. Note-se que e são as raízes do polinômio (irredutível em 
) . 
 
4.CÓDIGOS BCH 
 
B-Bose C-Chaudhuri H-Hocquenghem 
É um dos mais importantes códigos cíclicos e é uma generalização dos códigos 
de Hamming, permitindo correções de erros múltiplos. 
Para um dado comprimento de bloco, n, podem definir-se códigos com uma 
gama alargada de taxas e capacidades de correção de erros: 
 
 
 
 
 8 
 
4.1) Construção de Códigos BCH. 
 
Para cada raiz βr incluída em g(x), existe um polinômio mínimal f(r)(x) que tem βr 
como raiz [i.e., f(r)(βr) = 0] e com coeficientes em GF(2). 
O polinômio gerador, com coeficientes binários, que contém todas as raízes 
necessárias pode ser obtido como sendo o mínimo comum múltiplo (LCM) de 
todos os polinômios minimais correspondentes às raízes utilizadas: 
g(x) = LCM{f(b+1)(x), f(b+2)(x), ..., f(b+δ-1)(x)} 
 
 
 9 
4.2) Tipos de Códigos BCH. 
 
Se β é um elemento primitivo de GF(2m), o código BCH resultante é chamado de 
código BCH primitivo e as suas palavras-código têm comprimento 2m – 1 bits. 
Se β não é um elemento primitivo de GF(2m), o código BCH resultante é 
chamado de código BCH não primitivoe as suas palavras-código têm 
comprimento igual à ordem de β. 
Se b = 0, a primeira das (δ - 1) potências de β será β1 = β, ⇒ código BCH no 
sentido estrito. • Se b ≠ 0, ⇒ código BCH no sentido amplo. 
 
 
4.3) Códigos BCH Primitivos. 
Para qualquer m ≥ 3 e t ≤ 2m − 1 , existe um código BCH com os seguinte 
parâmetros: 
 n = 2m − 1 , 
 n − k ≤ mt, 
dmin ≥ 2t + 1 
 
O polinômio gerador do código, g(x), é o polinômio de menor grau sobre GF(2) 
contendo 
α, α2 ,α3,...,α 2t 
 
como raízes, onde α é um elemento primitivo de GF(2m). 
 
4.4) Decodificação de Códigos BCH. 
 
Computar as síndromes S = (S1, S2, ..., S2t ) a partir de r(x). 
Determinar σ(x) a partir de S1, S2, ..., S2t 
Determinar as localizações dos erros, β1, β2, ..., βv encontrando as raízes de σ(x) 
e corrigir os erros em r(x). 
 
 10 
4.5) Códigos BCH Primitivos sobre GF(q). 
 
Seja α um elemento primitivo em GF(qm ). 
O polinômio gerador, g(x), de um código BCH q- ário primitivo corretor de t erros 
é o polinômio de menor grau sobre GF(q) contendo α, α2 ,α3,...,α 2t como raízes. 
Seja φi (x) o polinômio minimal de αi , 1 ≤ i ≤ 2t. Então, 
g(x) = LCM{φ1(x), φ2(x), ..., φ2t (x)} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 11 
5. CONCLUSÃO 
 
Por se tratar de um código relativamente simples, suas aplicações são diversas 
e sua função principal é no armazenamento e transmissão de dados, portanto, , 
faz-se necessária a implementação de sistemas codificadores e decodificadores 
para códigos controladores de erro. 
Além disso podemos ver no Anexo que existem vários outros tipos de códigos, 
porém nesse trabalho foi analisado somente o caso dos códigos BCH. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 12 
 
 
6.BIBLIOGRAFIA 
 
[1] http://arquivoescolar.org/bitstream/arquivo-e/132/4/cap2.pdf 
[2] http://www.eletrica.ufpr.br/evelio/TE812/bch.pdf 
[3] http://www2.fc.unesp.br/revistacqd/v2e2/v2e2_art6.pdf 
[4] http://www.professores.uff.br/jcolombo/artigos/codigosCiclicosBCH.pdf 
[5] http://www.mat.uc.pt/~picado/algebraII/0405/Apontamentos/aula22.pdf 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 13 
ANEXO 
 
Características dos Códigos mais conhecido