Códigos de Blocos, Códigos Cíclicos e Decodificação de Códigos Cíclicos e Códigos Convolucionais

TECNOLOGIA EM

SISTEMAS DE

TELECOMUNICAÇÕES

DISCIPLINA: TEORIA DA CODIFICAÇÃO

COMPONENTES DO GRUPO:

Evaristo das Chagas Pereira Junior / RA: 6277269834

Marcio da Veiga Bousquet / RA: 6823478536

TURMA: 3ºA

“Códigos de Blocos, Códigos Cíclicos e Decodificação de Códigos Cíclicos e Códigos Convolucionais”.

Professor: Roberto Brito

TAGUATINGA, DF.

04 de Junho de 2013.

CÓDIGO DE BLOCO

Utilizando codificação do canal com um codificador de bloco a informação é quebrada em uma seqüência de blocos de k bits de informação cada. Esse bloco é representado por um vetor binário u =(u0, u1,..., uk-1) de comprimento k chamado de seqüência de informação ou mensagem, portanto existe um total de 2k seqüências de informação distintas possíveis. O codificador transforma cada seqüência de informação u num vetor binário v =(v0, v1,..., vN-1) de comprimento n chamado palavra-código. O vetor binário é composto por k bits de informação e (n – k) bits de redundância. A redundância permite verificar a existência ou não de erros num bloco particular de tamanho n e efetuar a sua correção. Logo, existem 2k palavras código de comprimento n, este código é descrito como um código de bloco (n, k, dHmin), onde dHmin é a distância mínima de Hamming do código (Teorema 1). A razão r = k/n é chamada de taxa do código, e pode ser interpretada como o número de bits de informação que entra no codificador por bit transmitido.

Principais Características dos códigos de bloco

A distância de Hamming (dH) entre dois vetores de 2n (o conjunto das 2n palavras é formado pela união do subconjunto das 2k palavras código de n bits com o subconjunto das 2n – 2k palavras não pertencentes ao código) é definida como sendo o número de posições em que eles diferem. O peso de Hamming(wH) de um vetor é o número de coordenadas não nulas desse vetor, Exemplo: A distância de Hamming entre os vetores 10100 e 11110 é 2. O peso do primeiro vetor é 2 e do segundo é 4.

A distância Mínima de Hamming (dHmin) do código C é a menor distância encontrada entre duas palavras pertencentes ao código. Para o caso do código (7,3,4) vemos pela Tabela 1 que dmin = 4, Exemplo: Considere o código (7,3,4) cujas equações para cálculo dos dígitos redundantes, ou dígitos de verificação de paridade, são as seguintes:

c1 = k1 + k2

c2 = k2 + k3

c3 = k1 + k3

c4 = k1 + k2 + k3

Cada bloco contendo três dígitos de informação é codificado em uma palavra código de sete dígitos, um código de bloco é linear se e somente se a soma módula-2 de duas alavras-código é também uma palavra-código e possui a palavra-código zero. Seqüência de Informação Palavra-Código Wh

Para códigos de blocos lineares o peso de Hamming é igual à distância de Hamming, portanto, a distância mínima de um código de bloco linear é igual ao peso mínimo de suas palavras-códigos não nulas.

Uma palavra recebida com erros em determinadas posições é chamada de padrão de erro. Seja por exemplo, o código binário de repetição C(3,1,3) que possui as seguintes palavras-códigos: 000, 111. Para este código 100 representa um padrão de um erro, pois supondo-se que foi transmitida a palavra-código 000, a palavra recebida possui um erro na primeira posição. Em códigos de bloco a capacidade de detecção td de um código é dada pela seguinte igualdade: td = dHmin – 1

A capacidade de correção tc de um código binário é o número de posições que podem ser corrigidas em uma palavra-código, e é dada pela expressão: tc = (dHmin – 1)/2 onde significa “a parte inteira de”.

Para o caso do código de bloco (7,3,4) vemos que dHmin = 4 e que portanto tc = 1. Logo, esse código é capaz de corrigir qualquer padrão de erro único sobre um bloco de 7 bits.

É interessante observar que a equação da definição 4 garante a correção de um número mínimo de padrões de erro, porém nada diz a respeito do número total de padrões corrigidos.

Matriz Geradora

O processo de codificação pode ser representado pelo produto v = u.G, onde G é a Matriz Geradora do código e u é o vetor de informação.

A matriz geradora G de um código de bloco linear é a matriz de dimensões k x n, cuja k linhas são palavras-código linearmente independentes. G é chamada de matriz geradora por gerar todas as palavras código do código linear. E gi = (gi0 , gi1,..., gin-1), para 0 ≤ i < k, onde gi0 , gi1,..., gk-1 são k palavras-código, portanto

A matriz geradora do código (7,3,4) da Tabela 2.1 pode ser o seguinte:

As palavras-códigos geradas pela matriz são apenas combinações lineares das linhas dessa matriz. Uma propriedade desejável num código linear é a sistematicidade. Essa estrutura sistemática ocorre quando as palavras-código são divididas em duas partes. A parte da informação e a parte da verificação da paridade.

A matriz G de um código linear sistemático é da forma G = [PIk] ou G = [IkP], onde P é uma matriz k x n – k, e Ik é a matriz identidade k x k, portanto para G = [PIk] temos onde Jij é a sub-matriz de paridade. Para a matriz geradora do exemplo 1 temos:

Neste exemplo temos que os bits de informação estão em Ik e os de redundância em P.

Matriz de Verificação de Paridade

Dada a matriz geradora G de um código linear, com k linhas e n colunas, é possível formar uma outra matriz H, com n – k linhas e n colunas, tal que o espaço das linhas de G seja ortogonal a H, isto é, uma n-upla v é uma palavra-código no código gerado por G se e somente se v.HT = 0.

A matriz H é chamada de matriz de verificação de paridade do código. Se G estiver na forma sistemática, então H = [In-kPT] ou H = [PTIn-k] onde PT é uma matriz n –