Codificação de Canal e Códigos de Bloco Lineares

Centro Federal de Educação Tecnológica da Paraíba Curso Superior em Tecnologia de Sistemas de Telecomunicações Teoria da Informação Profa Suzete E N Correia suzetecorreiagmailcom Codificação de Canal Códigos de Bloco Lineares Sistema de Comunicação Digital Símbolos x1 x2 xM erro Fonte Codificador de Fonte Codificador de Canal Destino Decodificador de Fonte Decodificador de Canal Canal Ruído Mensagem k bits 0100 Código n bits 010010 Palavra recebida n bits 011010 Mensagem k bits 0100 Símbolos x1 x2 xM sem erro Canal de retorno Codificação de Canal Os erros de transmissão em comunicações digitais dependem da relação sinalruído SN Se SN for fixa e a taxa de erros for muito elevada é preciso melhorar a confiabilidade do sistema por outro meio Uma maneira possível é codificar a informação de modo a detectar ou corrigir erros ou seja empregar codificação de canal O codificador de canal mapeia k bits de entrada em seqüências de n bits em que n k Os n k bits extras são chamados de bits de paridade Os bits de paridade não transportam informação mas são os responsáveis pela detecção ou até correção dos erros de transmissão Códigos Detectores e Corretores de Erros ARQ AutomaticRepeatRequest Solicitação de repetição automática Necessita de canal de retorno e tem o propósito da detecção de erros FEC Foward Error Correction Correção direta de erros Capacidade de correção e detecção de erros Códigos de Bloco blocos de k bits de entrada são mapeados sucessivamente em blocos de n bits Códigos Convolucionais uma seqüência contínua de k bits de mensagem são mapeados em n bits de saída O mapeamento considera um certo número de bits de entrada anteriores por isso esse código é dito com memória Taxa do código O codificador de canal mapeia k bits de entrada em n bits de saída A taxa do código R é obtida por Pelo Teorema da Codificação de Canal a taxa do código não pode exceder a capacidade do canal Quanto menor a taxa do código mais rápida deve ser a transmissão através do canal o que requer uma canal com maior largura de banda n R k Distância de Hamming A distância de Hamming entre duas palavras códigos c1 e c2 representada por dc1 c2 é definida como sendo o número de posições binárias em que elas diferem Exemplo Propriedades dc1 c2 0 dc1 c2 dc2 c1 dc1 c2 dc2 c3 dc1 c3 c1 01011 e c2 11010 dc1 c2 2 Peso de Hamming O peso de Hamming de uma palavra código c representado por wc é definido como sendo a quantidade de bits nãonulos da palavra código Exemplo O peso de Hamming de uma palavra código é igual a sua distância de Hamming para a palavra zero wc dc0 c 01011 wc 3 Distância mínima A distância mínima de um código representada por dmin é definida como sendo a menor distância de Hamming entre duas palavras quaisquer do código A capacidade de detecção e correção de um código é determinada pela dmin Para códigos lineares a menor distância de Hamming é igual ao menor peso de Hamming 12 min min k j i j i d c c d Exemplo 1 Considere o seguinte código Mensagem k2 00 Palavra código n3 000 001 011 01 10 11 111 dmin 1 dc1 c2 1 dc1 c3 2 dc1 c4 3 dc2 c3 1 dc2 c4 2 dc3 c4 1 Distância de Hamming wc1 0 wc2 1 wc3 2 wc4 3 Peso de Hamming Capacidade de Correção e Detecção Capacidade de detecção de erros Capacidade de correção de erros Capacidade de correção e detecção 1 min s d 1 2 min t d s para t t s d 1 min s e t são respectivamente a quantidade de bits que se deseja detectar e corrigir Exemplo 2 Palavra código n6 Mensagem k2 00 000 000 010 111 101 011 01 10 11 111 100 dmin 4 Capacidade de detecção s 3 Capacidade de correção t 1 Capacidade de detecção e correção s 3 e t 0 s 2 e t 1 Exemplo 2 Para um código com dmin4 dmin4 Palavra código válida Palavra código válida Palavras códigos não válidas Podese detectar a ocorrência de até três erros Podese corrigir um erro pois neste caso a palavra recebida ainda vai diferir em pelo menos duas posições de qualquer outra palavra código sendo possível corrigilo Códigos de Bloco Lineares Códigos lineares são aqueles em que uma combinação linear de duas palavras códigos resulta em uma palavra código O código do exemplo 2 é linear 010 111 101011 111100 A linearidade de um código de bloco facilita a obtenção de bons códigos e permite que a codificação seja feita através de uma matriz geradora do código G soma módulo 2 Códigos de Bloco Lineares A palavra código de um código de bloco nk pode representada na forma sistemática Parte redundante bits de paridade Mensagem bits deinformação nk bits k bits Palavra código n bits bits de mensagem m1 m2 mk bits de paridade b1 b2 bnk bits da palavra código c1 c2 cn Códigos de Bloco Lineares Os nk bits de paridade são obtidos por somas lineares dos k bits de mensagem de acordo com alguma regra de codificação k ki i i i p m p m p m b 2 2 1 1 caso contrário 0 se depender de 1 j i ij m b p Os coeficientes são escolhidos de modo que as linhas da matriz geradora sejam linearmente independentes Matriz de Coeficientes k ki i i i p m p m p m b 2 2 1 1 P k x nk matriz 3 2 1 2 23 22 21 1 13 12 11 2 1 k n k k k k k n k n k p p p p p p p p p p p p m m m b mP b nb k b b b 2 1 P é a matriz de coeficientes ou matriz de paridade Exemplo 3 Código de paridade simples 2 1 1 1 1 m m b Mensagem k2 00 000 101 110 01 10 11 011 Palavra código n3 Regra de codificação o bit de paridade é obtido somandose todos os bits da mensagem 1 1 P Matriz Geradora b1 b2 bnk m1 m2 mk c1 c2 cn n k n i m k n i b c k n i i i 1 21 1 k n k n m m b b c c c c c 1 1 2 1 I m P c mP m c b m c c mG G é a matriz geradora do código Matriz Geradora I P G Forma sistemática matriz Identidade k x k P k x nk matriz 3 2 1 2 23 22 21 1 13 12 11 1 0 0 0 0 0 1 0 0 0 0 1 k n k k k k k n k n p p p p p p p p p p p p G Outra forma de representação I P G Exemplo 4 Código de bloco 74 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 G c mG Codificação 0001101 Se m 1101 c Exemplo 4 Mensagemm Palavra códigoc 0000 0000000 0001 1010001 0010 1110010 0011 0100011 0100 0110100 0101 1100101 0110 1000110 0111 0010111 1000 1101000 1001 0111001 1010 0011010 1011 1001011 1100 1011100 1101 0001101 1110 0101110 1111 1111111 Matriz Teste de Paridade Todo código de bloco nk tem uma matriz dual H denominada matriz teste de paridade de modo que Na forma sistemática 0 HT G Paridade transpost a nk x k matriz 3 2 1 3 33 23 13 2 32 22 12 1 31 21 11 Identidade nk x nk matriz 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 k n k n k n k k n k k k p p p p p p p p p p p p p p p p H I PT H P I G Exemplo 5 Para o código de bloco 74 I PT H P I G 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 G 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 H Outra forma de representação I P H I P G T Cálculo da Sindrome de Erro O receptor decodifica a palavra recebida baseado em um vetor sindrome de erro s c r c e e e c r T T T T T T T T T T eH rH eH mGH rH eH cH rH e H c rH rHT s Como A sindrome depende somente do padrão de erro e não da palavra transmitida Decodificação por Sindrome Calcule a síndrome do vetor recebido r Se r for uma palavra código válida a sindrome é nula Caso contrário a localize o erro padrão cuja síndrome é igual a rHT O erro padrão será escolhido como sendo a palavra código nãoválida com menor peso Decodifique o vetor recebido r como o vetor código vre s rHT Exemplo 6 Decodificação do código de bloco 74 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 HT H Exemplo 6 Decodificação do código de bloco 74 1010000 0100010 0011000 0001100 0000001 100 0101100 0001111 1000100 0100001 0000010 111 1011000 0010011 1000010 0001001 0000100 011 1000011 1100000 0010010 0000101 0001000 110 0000111 0100100 0001010 1000001 0010000 001 0001110 1001000 0010100 0000011 0100000 010 0011100 0101000 0010001 0000110 1000000 100 0110100 0100011 1110010 1010001 0000000 000 Sindrome erro padrão vetor com o menor peso Exemplo 6 Decodificação do código de bloco 74 Tabela de decodificação do código 74 Síndrome erro padrão 100 1000000 010 0100000 001 0010000 110 0001000 011 0000100 111 0000010 101 0000001 Supondo que o vetor r1001111 Calcule a síndrome do vetor recebido rHT 011 Localize o erro padrão e 0000100 Decodifique o vetor recebido r para o vetor código vre 1001111 0000100 1001011