Introdução à Codificação de Canal e Probabilidade de Erro de Bit

2BlocoV2011Rev4 Geraldo Gil R Gomes 21 Um canal de comunicação pode apresentar uma série de imperfeições que dificultam a correta interpretação e perfeita reprodução dos sinais transmitidos Tais imperfeições se apresentam como ruídos distorções interferências desvanecimentos etc e como consequência a função do receptor pode ser resumida como sendo habilidade de apresentar em sua saída a melhor estimativa da informação ou mensagem que foi transmitida 1 Em sistemas de comunicações digitais o parâmetro de desempenho que permite quantificar o que pode ser a melhor estimativa é a probabilidade de erro de bit Pb cujo valor para ser considerado satisfatório depende fundamentalmente do tipo de informação que está sendo transmitida A questão fundamental apresentada neste capítulo está diretamente relacionada com o controle da probabilidade de erro de bit abordada a partir da próxima seção 21 INTRODUÇÃO À CODIFICAÇÃO DE CANAL A codificação de canal é um processo em que redundâncias são introduzidas antes da transmissão com o objetivo de permitir que no receptor a semelhança entre o sinal que foi transmitido e o sinal que foi reproduzido seja a máxima possível Ou por outro lado é um processo que permite a redução da Pb a valores tão baixos quanto possíveis A partir desse ponto é inevitável a imposição de uma questão Em termos objetivos o que se pode esperar obter como máxima semelhança ou Pb tão baixa quanto possível com a codificação de canal Essa questão foi parcialmente respondida no capítulo anterior através do Teorema da Codificação de Canal cuja consequência é reproduzida a seguir por conveniência 123 Desde que a taxa de transmissão seja menor do que a capacidade do canal então existe um esquema de codificação capaz de permitir a obtenção de taxas de erro de bit arbitrariamente baixas O Teorema da Codificação de Canal no entanto é insatisfatório sob o ponto de vista prático porque não conduz a uma indicação do esquema de codificação capaz de produzir um resultado esperado nem tampouco o seu grau de complexidade ou da dificuldade de encontrálo Uma discussão mais detalhada sobre esse assunto pode ser encontrada em diversas publicações sobre Teoria da Informação De fato a busca de um esquema de codificação que em geral é um processo heurístico nem sempre tem como principal meta alcançar desempenhos próximos dos apresentados pelos limites fundamentais da Teoria da Informação Em sistemas reais a busca de um esquema de codificação pode estar associada a aspectos práticos como velocidade de processamento complexidade de implementação etc 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES Independentemente de qual seja a abordagem utilizada na busca de um esquema de codificacao é necessario um bom conhecimento dos fundamentos associados as técnicas de codificagao para controle de erro O objetivo deste capitulo é apresentar os fundamentos dos Cédigos de Bloco Lineares e seus desempenhos Eles sao apresentados em cinco seoes Definigdes Fundamentais Cdédigos de Bloco Lineares Desempenho dos Cédigos de Bloco Lineares Cddigos Ciclicos Caracteristicas dos Codigos de Bloco Bem Conhecidos 22 CODIGOS DE BLoco DEFINIGOES INICIAIS Antes da apresentacao dos Cédigos de Blocos Lineares algumas definig6es iniciais sAo oportunas Codigos de blocos se caracterizam pelo fato do processo de codificagao ser feito sobre blocos de bits ou bloco de simbolos Isso quer dizer que um feixe de bits ou simbolos é segmentado em blocos de bits ou simbolos a partir dos quais sao geradas palavras cédigos com n bits ou simbolos Assim a notagao que caracteriza um cédigo de bloco é n k Por conveniéncia a partir deste ponto a notacao n k estara associada a quantidade de bits Quando a notacao n k for usada para representar simbolos isso sera definido explicitamente Se k bits estao contidos em um bloco de n bits entéo a quantidade de bits de redundancia introduzidos no processo de codificacgao é n k 221 TAXA DE CODIFICAGAO A taxa de codificagao de um cédigo de bloco é definida como sendo a relacao entre o numero de bits de informagao e o numero de bits da palavra cédigo Ou seja r 21 n A taxa de codificagao é uma indicagao relativa de quantos bits de informaao sao transmitidos por palavra codigo Uma vez que 0 k n entao 0 R 1 Entretanto para que um cédigo produza algum beneficio é necessario que k n ou n k 0 Consequentemente 0 R 1 Notase que se nenhum artificio for usado para compensar o acréscimo de bits devido a introdugéo da redundancia entéo para a manutencao da taxa de transmissaéo dos bits de informacao é necessario aumentar a taxa de transmissao total resultando em um acréscimo ou expansdo da largura de faixa Essa expansao da largura de faixa é de exatamente a 1R Ou seja quanto maior for o numero de bits de redundancia introduzidos maior sera a expansao da largura de faixa 222 GANHO DE CODIFICAGAO O beneficio obtido com o processo de codificagaéo pode ser quantificado por meio do ganho de codificagdo O ganho de codificagao é definido como sendo a relacao entre E No do sinal nao codificado pelo EF No do sinal codificado para uma dada taxa de erro ie o ganho de codificacgao é 22 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 23 tipicamente uma função de Pb A expressão do ganho de codificação em dB é apresentada a seguir 346 dB 10log log 10 0 0 c b nc b N E N E G 22 Onde Eb N0nc é a relação entre a energia de bit e a densidade espectral de ruído sem codificação e Eb N0c é a relação entre a energia de bit e a densidade espectral de ruído com codificação As curvas características de Pb em função de Eb N0 para um esquema de transmissão codificado e não codificado são apresentado na Figura 21 Um cuidado deve ser tomado para a correta determinação de Pb em função de Eb N0 com a codificação o valor de Eb referese à energia por bit de informação ou seja admitindose que a energia total gasta para a transmissão seja a mesma para os dois casos então a energia por bit de informação com a codificação é menor do que a energia de bit sem a codificação devido à inserção dos bits de redundância Assim sendo a relação entre Eb N0c e Eb N0nc fica afetada pela taxa de codificação na forma nc b c b N R E N E 0 0 23 Os valores de taxa de erro e de Eb N0 apresentados na Figura 21 referemse a um esquema hipotético e tem por objetivo permitir generalizar conclusões apresentadas a seguir 1 Para baixos valores de Eb N0 a codificação não apresenta nenhum benefício ou seja o ganho de codificação pode ser nulo para o valor de Eb N0 determinado pelo cruzamento das curvas ou negativo para valores menores 2 Para diferentes valores de Pb obtémse diferentes ganhos de codificação Por exemplo para Pb 104 o ganho de codificação é igual o a 14 dB enquanto para Pb 106 o ganho sobe para 2 dB Isso demonstra a dependência do ganho de codificação com Pb 3 A codificação permite obter redução de Pb com a mesma energia Eb N0 constante em relação ao sinal sem codificação Por exemplo para Eb N0 7 dB a Pb cai de 103 para um pouco mais que 105 Considerandose a expansão de largura de faixa provocada pela codificação podese concluir ainda 4 A diminuição de Pb eou Eb N0 decorrente da codificação produz uma expansão na largura de faixa 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 24 Figura 21 Curvas típicas de probabilidade de erro versus Eb N0 para um sinal com codificação e sem codificação 223 VETOR CÓDIGO VETOR ERRO VETOR RECEBIDO E VETOR DECODIFICADO Conforme definido previamente o processo de codificação por bloco consiste em transformar um segmento da mensagem m com k bits em uma palavra código ou vetor código c com n bits O vetor código é transmitido e pode sofrer alterações devido às degradações impostas pelo meio de transmissão As alterações sofridas pelo vetor códigos podem ser representadas por meio de um vetor erro e Um vetor código c somado com um vetor erro e resulta em um vetor recebido r Ou seja e c r 24 O vetor recebido é entregue ao decodificador cuja finalidade é transformar o vetor recebido no vetor decodificado que consiste na melhor estimativa do vetor código transmitido A partir do vetor código estimado c a melhor estimativa da mensagem m é reproduzida na saída do decodificador Essa cadeia de transformações é ilustrada no diagrama em blocos apresentado na Figura 22 e pelo Exemplo 21 EbN0 dB Pb 10 2 10 1 10 3 10 4 10 5 10 6 7 8 9 10 6 5 4 3 Sem codificação Com codificação 14 dB 2 dB 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 25 Figura 22 Diagrama em blocos do processo de codificação e decodificação EXEMPLO 21 Seja um código de repetição 5 1 aplicado ao vetor mensagem m 1 Admitindo que o canal introduza um vetor erro e 01010 ao vetor código pedese determinar todas as transformações vetoriais desde a codificação da mensagem até a obtenção da mensagem estimada na saída do decodificador Solução Evidentemente para o código de repetição 5 1 só existem duas palavras códigos possíveis 00000 e 11111 A palavra código correspondente à mensagem m 1 é c 11111 O vetor recebido é r c e 11111 01010 r 10101 Como um código de repetição pode ser decodificado por lógica majoritária então a melhor estimativa para o vetor código a partir do vetor recebido é c 11111 que resulta na mensagem estimada m 1 224 PESO DE HAMMING E DISTÂNCIA DE HAMMING O peso de Hamming de um vetor v cuja notação é wv é definido como o sendo o número de elementos não zero em v Para um vetor binário o peso de Hamming é igual ao número de dígitos 1 contidos em v 123456 EXEMPLO 22 Determinar o peso de Hamming do vetor v 10110 Solução wv 3 Codificador Canal e c m Decodificador Estimador de c Estimador de m r c m 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 26 A distância de Hamming entre dois vetores códigos v e x cuja notação é dv x é definida como sendo o número de posições em que os dígitos dos dois vetores que são diferentes entre si Para o caso binário a distância de Hamming pode ser determinada facilmente através da propriedade de adição módulo2 pois ela é igual ao número de dígitos 1 contidos no vetor resultante da operação v x Ou seja x v v x w d 25 EXEMPLO 23 Determinar a distância de Hamming entre o vetor v 10110 e x 10101 Solução 00011 10101 10110 w w w d x v v x 2 d v x 225 ESPAÇO VETORIAL E SUBESPAÇO VETORIAL Considere um conjunto V constituídos por K vetores v0 v1 v2 vK1 formado por n elementos de 0 1 Admita que sobre este conjunto sejam definidas duas operações cujas regras são apresentadas na Tabela 21 A adição representada por definida entre os elementos de V e a multiplicação representada por entre um elemento de 0 1 e qualquer vetor de V 123456 Tabela 21 Operações algébricas no campo binário Adição Multiplicação 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 O conjunto V é definido como um espaço vetorial sobre 0 1 se as seguintes condições são satisfeitas 1 A adição de quaisquer dois vetores de V resulta em outro vetor em V propriedade do fechamento 2 O produto escalar de um elemento de 0 1 e qualquer vetor de V resulta em outro vetor em V 3 A lei distributiva é satisfeita ou seja se a1 e a2 são escalares de 0 1 e v1 e v2 são vetores de V então 2 1 2 1 1 1 1 1 1 1 2 1 2 1 v v v v v v v a a a a a a a 26 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 27 4 A lei associativa é satisfeita ou seja se a1 e a2 são escalares de 0 1 e v1 é um vetor de V então 2 1 2 1 1 1 v v a a a a 27 EXEMPLO 24 Encontrar o espaço vetorial V composto pelo maior número possível de vetores com seis elementos de 0 1 Solução O espaço vetorial V6 é o conjunto de todos os vetores binários com seis elementos n 6 apresentados na Tabela 22 Tabela 22 Espaço vetorial V6 V6 000000 000001 000010 000011 000100 000101 000110 000111 001000 001001 001010 001011 001100 001101 001110 001111 010000 010001 010010 010011 010100 010101 010110 010111 011000 011001 011010 011011 011100 011101 011110 011111 100000 100001 100010 100011 100100 100101 100110 100111 101000 101001 101010 101011 101100 101101 101110 101111 110000 110001 110010 110011 110100 110101 110110 110111 111000 111001 111010 111011 111100 111101 111110 111111 Um subconjunto S de um espaço vetorial V é chamado de subespaço vetorial de V se as quatro condições definidas acima são verificadas Entretanto como S é um subconjunto de V é suficiente que as duas primeiras condições sejam satisfeitas para a identificação de um subespaço em V isto é 1 A adição de quaisquer dois vetores de S resulta em outro vetor em S propriedade do fechamento 2 O produto escalar de um elemento de 0 1 e qualquer vetor de S resulta em outro vetor em S Ou simplesmente o vetor nulo ou vetor todo zero pertence a S EXEMPLO 25 A partir das propriedades do subespaço vetorial identificar dois subespaços vetoriais de V6 apresentado na Tabela 23 que contenha 1 4 vetores 2 8 vetores 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 28 Solução Tabela 23 Subespaços de V6 com 4 e 8 vetores S com 4 vetores S com 8 vetores 000000 000000 011001 101011 110101 101011 110110 101100 110010 011101 011110 000111 Importante Os subespaços encontrados acima não são únicos É possível encontrar em V6 outros subespaços contendo 4 e 8 vetores 23 CÓDIGOS DE BLOCO LINEARES 123456 Um código de bloco linear binário é um subespaço vetorial com 2k vetores do espaço vetorial constituído de todos os 2n vetores com n elementos de 0 1 Este conceito está ilustrado na Figura 23 Consequentemente considerando as duas condições necessárias para caracterizar um subespaço vetorial aplicadas aos códigos de bloco lineares concluise que 1 A soma de duas palavras códigos quaisquer resulta em outra palavra código e 2 O vetor nulo ou vetor todo zero é também uma palavra código Figura 23 Representação dos códigos de blocos lineares como um subespaço vetorial de um espaço vetorial Vn Notase que o subespaço vetorial constitui o conjunto dos vetores códigos ou vetores válidos Portanto qualquer vetor de n bits que não pertença ao subespaço vetorial está no espaço vetorial porém é um vetor não válido Uma estratégia de detecção de erros consiste em verificar se o vetor recebido é um vetor válido ou não válido ie se ele pertence ou não ao subespaço vetorial Uma vez constatado que o vetor recebido é um vetor não válido uma estratégia de correção de erros consiste na identificação de qual é o vetor válido que apresenta a menor distância de Hamming em relação ao vetor recebido e elegêlo como sendo o vetor transmitido Conjunto dos 2n vetores com n bits 2n Conjunto dos 2k vetores códigos de n bits 2k 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 29 Nos códigos de bloco lineares onde o valor de k é baixo esta tarefa é simples Entretanto quando k apresenta valores relativamente altos esta tarefa pode tornarse impraticável conforme mostrado no Exemplo 26 EXEMPLO 26 Admitindo a existência de um código de bloco linear 255 130 pedese a Determinar a quantidade de vetores códigos binários existentes neste código b Determinar a quantidade de vetores não possíveis c Descrever uma estratégia de correção de erros admitindo que o vetor recebido é um vetor não válido Solução a A quantidade de vetores códigos é 2k 2130 136 1039 vetores válidos b Como o vetor é não válido então ele é um dos 2n 2k vetores não válidos ou um entre 2255 2130 2255 57896 1076 vetores não válidos c Uma estratégia de correção de erros é identificar entre os 136 1039 vetores válidos qual é o vetor que apresenta a menor distância de Hamming em relação ao vetor não válido recebido Notase que um subespaço vetorial é um conjunto de vetores linearmente dependentes LD devido à propriedade do fechamento ie qualquer vetor pode ser obtido pela soma de outros dois vetores do subespaço Uma vez que um subespaço vetorial binário contém 2k vetores então deve existir um ou mais subconjuntos com k vetores ditos linearmente independentes LI cujas combinações lineares produzem todos os outros vetores do subespaço Esses k vetores linearmente independentes são chamados de base do subspaço Os conceitos de espaço vetorial subespaço vetorial e base do subespaço estão apresentados em termos de conjunto na Figura 24 Figura 24 Representação de espaço vetorial subespaço vetorial e base do subespaço vetorial Espaço 2n Subespaço 2k k Base do Subespaço Vetorial 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 210 EXEMPLO 27 A partir do subespaço vetorial com 8 vetores apresentado na Tabela 23 identificar uma base capaz de gerar todos os outros vetores deste subespaço através de combinações lineares dos vetores desta base Solução Como o objetivo é formar uma base para a geração dos de um subespaço com 2k 8 vetores LD o número necessário de vetores na base será k 3 vetores LI Escolhendose arbitrariamente 3 vetores LI entre os 8 vetores da Tabela 23 podese obter b0 110101 b1 101100 b2 011110 Prova Com a combinação linear dos vetores encontrados é possível encontrar todos os outros vetores do subespaço representados a seguir pelos vetores vj obtidos a partir da operação 1 1 1 1 0 0 k k j u u u b b b v K 28 onde ui é um elemento de 0 1 para i 1 2 k 1 e j 0 1 2k 1 v0 0 b0 0 b1 0 b2 000000 v1 1 b0 0 b1 0 b2 110101 Vetor da base v2 0 b0 1 b1 0 b2 101100 Vetor da base v3 0 b0 0 b1 1 b2 011110 Vetor da base v4 1 b0 1 b1 0 b2 011001 v5 1 b0 0 b1 1 b2 101011 v6 0 b0 1 b1 1 b2 110010 v7 1 b0 1 b1 1 b2 000111 231 MATRIZ GERADORA Uma matriz geradora G é aquela que permite obter os vetores códigos cj correspondentes às mensagens mi a partir do produto interno determinado por G m c j j 29 Evidentemente a matriz geradora G é uma consequência direta de uma base do subespaço vetorial Ela é uma matriz de dimensões k n que consiste do arranjo formado pelos vetores linearmente independentes ou vetores geradores que compõem uma base do subespaço conforme apresentado em 210 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 211 1 1 1 2 1 1 0 1 1 1 12 11 10 1 0 02 01 00 1 1 0 n k k k k n n k g g g g g g g g g g g g L M M M M L L M g g g G 210 Onde g0 g1 gk 1 são os vetores geradores Para uma conveniente simplificação da notação a partir deste ponto os vetores códigos cj e mj serão denotados simplesmente por c e m respectivamente Logo substituindo 210 em 29 obtémse 1 1 1 1 0 0 1 1 0 1 1 0 k k k k m m m m m m g g g g g g m G c K M K 211 Observase claramente a semelhança entre 28 e 211 o que significa que a combinação linear dos elementos dos vetores mensagem com as linhas da matriz geradora produzem vetores códigos que estão associados inequivocamente aos vetores mensagens que os produziu EXEMPLO 28 A partir da base do subespaço vetorial apresentado no Exemplo 27 pedese a Construir uma matriz geradora b A partir da matriz geradora construir uma tabela com os vetores mensagens e seus respectivos vetores códigos Solução a A obtenção de uma matriz geradora a partir do Exemplo 27 é direta pois ela nada mais é do que a base de um subespaço vetorial logo utilizando os mesmos vetores b0 110110 b1 101100 e b2 011101 para g0 g1 e g2 respectivamente obtémse 0 1 1 1 1 0 0 0 1 1 0 1 1 0 1 0 1 1 G 212 b Como a matriz geradora possui três linhas os vetores resultantes de todas as combinações lineares serão 2k 23 8 obtidos a partir de todos os vetores mensagens possíveis contendo de três bits Consequentemente G é a matriz geradora de um código 6 3 conforme mostrado a seguir 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 212 Tabela 24 Vetores códigos do códigos 6 3 gerados a partir da matriz G em 212 m c mG c 000 c0 0 110101 0 101100 0 011110 000000 100 c1 1 110101 0 101100 0 011110 110101 010 c2 0 110101 1 101100 0 011110 101100 110 c3 1 110101 1 101100 0 011110 011001 001 c4 0 110101 0 101100 1 011110 011110 101 c5 1 110101 0 101100 1 011110 101011 011 c6 0 110101 1 101100 1 011110 110010 111 c7 1 110101 1 101100 1 011110 000111 232 CODIFICAÇÃO SISTEMÁTICA E NÃO SISTEMÁTICA Os vetores códigos apresentados na Tabela 24 gerados pela operação apresentada em 211 não apresentam explicitamente a mensagem que o gerou como sendo um segmento do próprio vetor código Isso significa que neste tipo de codificação a mensagem passa a ser conhecida somente após o processo de decodificação Essa forma de codificação é chamada de codificação não sistemática Uma característica desejável em um processo de codificação para um código de bloco linear é aquela que permite que o vetor código seja composto por dois segmentos um segmento composto pelos n k bits de redundância que permitem a verificação da validade do vetor e outro segmento correspondente aos k bits da mensagem que gerou os bits de redundância A disposição do segmento redundância e do segmento mensagem é uma questão de convenção A convenção adotada neste texto está apresentada na Figura 25 A forma de codificação que permite a obtenção do vetor código nesse formato é chamada de codificação sistemática Figura 25 Vetor código obtido por codificação sistemática Vetores códigos com a convenção mostrada na Figura 25 podem ser obtidos a partir de matrizes geradoras com um formato específico Este formato apresentado em 213 consiste de uma matriz geradora formada por duas outras matrizes uma matriz de paridade com dimensões k n k e outra matriz identidade de dimensões k k Desta forma a matriz de paridade permite que o segmento paridade seja obtido pela soma linear dos bits da mensagem enquanto a matriz identidade permite que o segmento mensagem seja replicado em seguida 1 1 0 1 1 1 1 0 1 1 1 11 10 1 0 01 00 1 0 0 0 1 0 0 0 1 k n k k k k k n k n k k n k k p p p p p p p p p g g g I P G M L M M M L L M M M L L 213 Segmento dos n k bits de redundância Segmento dos k bits de mensagem Vetor Código 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 213 Uma vez que uma matriz geradora é um arranjo de vetores linearmente independentes uma matriz geradora de um código de bloco linear na forma sistemática pode ser obtida pela conveniente combinação linear dos vetores geradores eou permutação de colunas ou linhas da matriz geradora na forma não sistemática para a obtenção de outro arranjo de novos vetores geradores linearmente independentes no formato desejado Essa operação é mostrada no Exemplo 29 EXEMPLO 29 A partir da matriz geradora do código 6 3 apresentada pela Equação 212 pedese a Obter uma matriz geradora na forma sistemática no formato apresentado em 213 b Construir uma tabela com os vetores mensagens e seus respectivos vetores códigos Solução a De 212 0 1 1 1 1 0 0 0 1 1 0 1 1 0 1 0 1 1 2 1 0 g g g G A matriz na forma sistemática G correspondente à matriz G é obtida a partir das seguintes operações a partir da matriz G g0 g1 101100 g1 g1 g2 110010 g2 g0 g1 011001 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 2 1 0 g g g G 214 b Repetindo a operação apresentada em 211 para a matriz G em 214 obtémse os vetores códigos apresentados na Tabela 25 Tabela 25 Vetores códigos do códigos 5 3 gerados a partir da matriz G 214 m c mG c 000 c0 0 101100 0 110010 0 011001 000000 100 c1 1 101100 0 110010 0 011001 101100 010 c2 0 101100 1 110010 0 011001 110010 110 c3 1 101100 1 110010 0 011001 011110 001 c4 0 101100 0 110010 1 011001 011001 101 c5 1 101100 0 110010 1 011001 110101 011 c6 0 101100 1 110010 1 011001 101011 111 c7 1 101100 1 110010 1 011001 000111 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 214 Observe que tanto a matriz G quanto a matriz G geram o mesmo subespaço vetorial Entretanto para cada uma das mensagens os vetores códigos gerados são diferentes em cada caso 233 MATRIZ VERIFICADORA DE PARIDADE Conforme apresentado na Figura 22 o vetor recebido r pode ser entendido como um vetor código que ao ser transmitido através de um canal de comunicação pode ter sofrido uma alteração consequência da adição de um padrão de erro Portanto uma tarefa do decodificador é verificar se o vetor recebido é ou não um vetor código ou vetor válido Mais uma vez uma abordagem simplista para a realização desta tarefa seria a comparação do vetor recebido com todos os vetores códigos Entretanto para valores de k da ordem de algumas dezenas esta abordagem pode tornarse árdua conforme mostrado no Exemplo 210 Uma forma mais simples para a verificação da validade ou não de um vetor recebido utiliza uma propriedade dos subespaços vetoriais que pode ser definida da seguinte forma Se um subespaço vetorial S1 pertence a um espaço vetorial Vn composto por todos os vetores de comprimento n então deve existir um subespaço vetorial S2 que é o espaço nulo ou o espaço dual de S1 e que pode ser representado por uma matriz composta por vetores bases linearmente independentes No estudo de códigos de bloco lineares a matriz geradora do subespaço nulo relativo ao subespaço gerado por G é chamada de matriz verificadora de paridade cuja notação é H e tem dimensões n k n ou seja 1 1 1 2 1 1 0 1 1 1 12 11 10 1 0 02 01 00 1 1 0 n n k n k n k k n n n n k h h h h h h h h h h h h L M M M M L L M h h h H 215 Se um subespaço gerado por H é dual ao subespaço gerado por G então os vetores de G são ortogonais aos vetores de H ou seja 0 G HT 216 Podese verificar sem dificuldades que uma consequência direta de 216 é que a condição de ortogonalidade de qualquer vetor código c gerado por G em relação ao espaço nulo gerado por H é verdadeira ie 0 c HT 217 Quando a matriz G está na forma sistemática conforme apresentada em 213 ou seja k k n k k I P G a obtenção da matriz H é direta conforme mostrado a seguir 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 215 1 1 1 1 1 0 1 1 11 01 1 0 10 00 1 0 0 0 1 0 0 0 1 n k k n k k n k k T n k k n p p p p p p p p p L M M M L L L M M M L P I H 218 EXEMPLO 210 A partir da matriz geradora para o código 6 3 apresentada em 214 pedese a Obter a matriz verificadora de paridade H b Verificar a condição de ortogonalidade apresentada por 217 para o vetor código correspondente ao vetor mensagem m 101 Solução a A partir da matriz geradora na forma sistemática 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 k k k n k I P G obtémse a matriz H na forma 1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 T n k n k P I H 219 b O vetor código c correspondente ao vetor mensagem m 101 pode ser obtido conforme mostrado em 211 ou seja 110101 1 011001 0 110010 1 101100 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 101 m G c A condição de ortogonalidade pode ser verificada a partir do resultado do produto interno entre o vetor código c e a matriz verificadora de paridade transposta HT conforme mostrado a seguir 000 1 011 0 110 1101 0 001 1 010 100 1 1 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 110101 c HT 220 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 216 234 DISTÂNCIA MÍNIMA DE UM CÓDIGO DE BLOCO LINEAR Considere o conjunto de distâncias entre todos os pares de vetores código em um espaço Vn O menor membro do conjunto é a distância mínima do código e é denotado por dmin Mais uma vez a propriedade dos códigos lineares discutida anteriormente permite afirmar que se c1 e c2 são vetores código então o vetor c3 obtido pela operação c1 c2 é também um vetor código Assim a distância de Hamming entre dois vetores códigos é determinada como sendo 3c c c c c w w d 2 1 1 2 221 Portanto não há necessidade de examinarmos as distâncias entre todas as combinações possíveis entre pares de palavrascódigo basta que se verifique o peso de cada palavra código com exceção da palavra toda zero O menor peso encontrado corresponde à menor distância mínima do código As propriedades dos códigos de blocos permitem ainda determinarmos a distância mínima do código através da inspeção da matriz verificadora de paridade Neste caso a distância mínima do código será igual ao menor número de colunas da matriz verificadora de paridade que quando somadas resultam em uma coluna toda zero Este procedimento é particularmente útil quando o código possui um número muito grande de palavras código para serem inspecionadas sem auxílio computacional Exemplo 211 Determine a distância mínima do código 6 3 definida pela matriz G 214 repetida abaixo por conveniência 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 G Solução Uma vez que este código possui poucas palavras códigos uma solução é listálas por meio da operação c mG O resultado dessa operação para todas as possíveis mensagens com 3 bits está mostrado na tabela a seguir Tabela 26 Vetores códigos do códigos 6 3 gerados a partir da matriz G 214 m c 000 000000 100 101100 010 110010 110 011110 001 011001 101 110101 011 101011 111 000111 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 217 Podese verificar inspecionandose a tabela acima que as palavras de menor peso são as palavras com peso 3 Logo a distância mínima é igual a 3 Ou alternativamente inspecionandose a matriz verificadora de paridade apresentada abaixo é fácil verificar que o menor número de colunas que quando somadas resulta em uma coluna toda zero é 3 por exemplo 1a 2a 5a ou 2a 3a 6a ou 1a 3a 4a 1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 H 222 É muito comum um código de bloco linear n k com distância mínima dmin ser representado pela notação n k dmin Assim o código 6 3 do Exemplo 211 é um código 6 3 3 235 CAPACIDADE DE CORREÇÃO E DE DETECÇÃO DE ERROS DE UM CÓDIGO DE BLOCO LINEAR No receptor o decodificador tem por função estimar o vetor código recebido em função do vetor código transmitido Em um canal de transmissão AWGN Ruído Branco Gaussiano Aditivo o ruído afeta os símbolos transmitidos aleatoriamente segundo uma distribuição estatística normal ou gaussiana Assim padrões de erros com menos bits errados tem maior probabilidade de ocorrer do que padrões de erros com mais bits errados Consequentemente em um canal BSC Canal Simétrico Binário dado um vetor recebido r a melhor estimativa é feita admitindose que o vetor código transmitido é aquele que está mais próximo de r sob o ponto de vista da distância de Hamming Se dois vetores códigos tiverem a mesma distância de Hamming do vetor r recebido a escolha pode ou não ser arbitrária dependendo do tipo de decisor utilizado hard decision ou soft decision A Figura 26 apresenta dois vetores c1 e c2 unidos por uma linha calibrada em distância de Hamming Cada ponto preto representa um vetor recebido r Na parte a da figura o vetor recebido r1 dista 1 bit de c1 e 4 bits de c2 De acordo com a estratégia de máxima probabilidade o decodificador selecionará o vetor c1 como aquele que foi transmitido Na parte b da figura o vetor recebido r2 dista 2 bits de c1 e 3 bits de c2 Mais uma vez o decodificador selecionará o vetor c1 como sendo o vetor recebido Finalmente na parte c da figura o vetor recebido r3 dista 3 bit de c1 e 2 bits de c2 Desta vez o decodificador selecionará o vetor c2 como sendo o vetor recebido 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 218 Figura 26 Capacidade de detecção e correção de erro a Vetor recebido r1 b Vetor recebido r2 c Vetor recebido r3 Consequentemente a capacidade de correção de erro de um código de bloco linear t é definida como o número máximo de erros garantidamente corrigíveis por palavra código determinado por 2 1 dmin t 223 onde x significa o maior inteiro que não excede o valor de x Assim um código que corrige todas as sequências de t erros pode também corrigir certas sequências de t 1 erros Se o código for usado com a finalidade exclusiva de detectar erros ao invés de corrigir erros a capacidade de detecção de erros do código é determinada por e dmin 1 224 onde e é o número de erros detectados Entretanto é possível utilizar um código de bloco para corrigir τ erros e detectar ε erros simultaneamente desde que τ t e ε e e a seguinte condição seja satisfeita 1 min ε τ d 225 Assim um código com dmin 7 por exemplo pode corrigir todos os padrões de 3 erros t 3 ou detectar todas as combinações possíveis de até 6 erros e 6 Entretanto se ele for usado para corrigir até 2 erros τ 2 ele pode detectar simultaneamente padrões de até 4 erros ε 4 pois neste caso a condição apresentada por 225 é satisfeita a b c Linha de decisão Região 1 Região 2 r1 r2 r3 c1 c1 c1 c2 c2 c2 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 219 236 SÍNDROME DE ERRO Seja r r1 r2 rn um vetor recebido ie uma das 2n palavras de n bits do espaço vetorial Vn resultante da transmissão de um vetor código c c1 c2 cn ie uma das 2k palavras códigos de n bits através de um canal com ruído Logo e c r 226 onde e e1 e2 en é um vetor erro ou padrão de erro introduzido pelo canal Síndrome de erro é um vetor com n k bits definido pela operação r HT S 227 Combinando 226 e 227 temse T T T e H c H H e c S 228 mas 0 c HT 229 Consequentemente e HT S 230 A equação acima mostra que a síndrome S está associada a um padrão de erro Esta é uma importante propriedade fundamental para o processo de decodificação ou seja cada padrão de erro corrigível deve estar associado a uma síndrome específica É importante notar que para isso ocorra duas propriedades da matriz verificadora de paridade são necessárias Nenhuma coluna da matriz H pode ser toda zero caso contrário um erro na posição correspondente à linha toda zero seria indetectável Todas as colunas de H devem ser únicas Se duas colunas de H forem iguais erros nas posições correspondentes a essas linhas podem ser indistinguíveis Um código de bloco linear n k com capacidade de correção de t erros é capaz de corrigir um total de 2nk padrões de erros Os códigos que corrigem exclusivamente todos os padrões de t erros ou menos e nenhum padrão maior que t erros são denominados códigos perfeitos isto é o número de síndromes deve ser igual ao número exato de padrões com até t erros e nenhum padrão de erro contendo um número maior do que t erros Uma vez que todo código de bloco é capaz de corrigir 2nk padrões de erros um código é perfeito quando a igualdade apresentada a seguir é satisfeita t i n k i n 0 2 231 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 220 EXEMPLO 212 Considere o código de bloco linear 6 3 3 gerado por 214 Pedese a Determinar a capacidade de correção de erros do código b Listar todos os padrões de erros corrigíveis dentro da capacidade de correção de erros do código c Listar todas as síndromes de erros associadas aos padrões de erros corrigíveis dentro da capacidade de correção de erros do código d Verificar se este código é um código perfeito Solução a A capacidade de correção de erros do código Como a distância mínima deste código é dmin 3 então 1 2 3 1 2 1 min t d t b Padrões de erros corrigíveis dentro da capacidade de correção de erros do código Como a capacidade de correção de erro é t 1 então este código é capaz de corrigir todos os padrões com 1 erro ou seja e t 1 100000 010000 001000 000100 000010 000001 c Síndromes de erros associadas aos padrões de erros corrigíveis dentro da capacidade de correção de erros do código Da matriz H 222 obtémse HT ou seja 1 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 HT 232 De 230 e HT S 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 221 Para todos os valores de e t 1 obtémse Tabela 27 Padrões de erros corrigíveis e suas respectivas síndromes para o código de bloco linear 6 3 3 gerado por 214 e t 1 S 100000 100 010000 010 001000 001 000100 101 000010 110 000001 011 d Verificação se este código é um código perfeito Um código perfeito deve satisfazer 7 6 1 1 6 0 6 8 2 2 2 0 3 6 0 t i k n t i k n i n i n Logo o código de bloco linear 6 3 3 não é um código perfeito De fato o número de síndromes possíveis são todas as síndromes não nulas mais a síndrome nula que totalizam 7 síndromes Por inspeção à Tabela 27 verificase a ausência da nula e da síndrome S 111 A ausência da síndrome nula devese ao fato que ela corresponde ao padrão de todo zero ou seja vetor recebido sem erro enquanto que a síndrome 111 só ocorrerá se o padrão de erro tiver 2 ou mais erros o que está fora da capacidade de correção deste código 237 CORREÇÃO DE ERROS PELA SÍNDROME Conforme mostrado no Exemplo 212 deve existir uma correspondência exclusiva entre um padrão de erro e uma síndrome de erro Isso abre a possibilidade de não só podermos detectar erros mas também corrigilos A correção de erros pode ser feita de diversas formas A seguir será apresentada a correção de erros por meio da síndrome de erros Basicamente este processo de correção é feito a partir da identificação do padrão de erro mais provável por meio do cálculo da síndrome de erros Uma vez conhecido o padrão de erro é possível fazer a correção de erro somandose o vetor r recebido com o padrão de erro e associado a ele pois em 226 e c r então e r c 233 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 222 Onde c é a melhor estimativa do vetor código que foi transmitido pelo canal ruidoso Este procedimento pode ser resumido de acordo com os seguintes passos 1 A partir da capacidade de correção de erros do código determinase a síndrome para todos os padrões de erros corrigíveis por meio 230 2 Calculase a síndrome de r usando 227 3 Localizase o padrão de erro correspondente à síndrome calculada 4 O vetor código será aquele determinado por 233 Observação O erro só será corrigido se o padrão de erro correspondente à síndrome de vetor recebido for igual ao padrão de erro introduzido pelo canal ie o padrão de erro introduzido pelo canal deve ser um padrão de erro corrigível EXEMPLO 213 Suponha que o vetor c 101011 do código 6 3 3 gerado por 214 tenha sido transmitido e corrompido por ruído no canal de modo que na recepção foi detectado o vetor r 101010 Corrija o erro introduzido pelo canal a partir da associação da síndrome com o padrão de erro mais provável Solução A síndrome de erros para o vetor recebido é determinada por meio de 233 ou seja 011 001 110 100 0011 1 110 0101 1 001 0010 100 1 1 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 101010 S S r H S T Em canais AWGN os padrões de erros mais prováveis são aqueles com menor número de erros Além disso o erro só será corrigido com certeza se o padrão de erro introduzido pelo canal for um padrão de erro corrigível pelo código A Tabela 27 obtida no Exemplo 212 associa os padrões de erros às suas respectivas síndromes Esta tabela é reapresentada a seguir com as colunas invertidas e reordenadas para permitir mais facilmente a identificação do padrão de erro a partir da síndrome obtida acima Tabela 28 Sindromes e seus respectivos padroes para 0 codigo de bloco linear 6 3 3 gerado por 227 000 000000 001 001000 010 010000 011 000001 100 100000 101 000100 110 000010 De acordo a Tabela 28 a sindrome calculada corresponde ao padrao de erro e 000001 Logo o vetor cddigo mais provavel de ter sido 0 vetor transmitido pode ser determinado por 239 1e cre101010000001 c101011 ke ARRANJO PADRAO O arranjo padrao 6 um esquema de decodificagao baseado em sindrome de erro Apesar da sua importancia didatica sua aplicabilidade fica restrita aos cddigos de bloco com numero reduzido de palavras cddigos Conforme ja apresentado um cédigo de bloco é um subespaco vetorial composto por 2 palavras codigos Entretanto quando uma palavra codigo é transmitida por um canal ruidoso e corrompida por ruido ela pode se transformar em uma palavra nao valida que pertence a um conjunto de 2 palavras com n bits que constitui o espaco vetorial V Considere as 2 palavras cédigos de um cédigo de bloco linear CC 0 Considere também os 2 padroes de erros ee gent associados as 2 sindromes possiveis Um arranjo padrao é constituido por todas as palavras do espago vetorial V de acordo com os passos apresentados a seguir e ilustrados na Figura 27 1 Um arranjo padrao é formado por 2 subconjuntos sendo que cada subconjunto é uma coluna do arranjo padrao Consequentemente um arranjo padrao possui 2 colunas 2 A primeira linha do arranjo padrao é composta por todas as 2 palavras codigos ou seja a primeira linha do arranjo padrio 6 o subespaco vetorial das 2 palavras cédigos Obrigatoriamente a palavra toda zero ou chamada de e 0 a palavra que ocupa a posicao superior esquerda do arranjo 3 A primeira coluna do arranjo padrao é formada por todos os 2 padrées de erros incluindo o vetor todo zero que ocupa a posiao superior esquerda do arranjo Consequentemente um arranjo padrao possui 2 linhas A segunda linha do arranjo 6 formada pela soma de ey com cada um dos vetores cddigos na primeira linha Este procedimento se repete até que a nk sima linha complete o arranjo 223 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 224 Cada linha do arranjo forma um subconjunto disjunto dos demais subconjuntos das outras linhas Cada subconjunto é chamado de coset e o vetor do coset que pertence a primeira coluna é chamado de lider do coset O arranjo padrão permite a decodificação direta da palavra recebida pela identificação de um dos 2k subconjunto ou coluna ao qual pertence a palavra recebida Uma vez identificada esta coluna o vetor código decodificado é o vetor da primeira linha da coluna identificada Figura 27 Arranjo padrão O Exemplo 214 apresenta o uso do arranjo padrão para a correção de erros e também um comentário sobre o equívoco de decodificação que pode ocorrer quando o código usado não é um código perfeito EXEMPLO 214 Considere o código 6 3 3 gerado por 214 Pedese a Construir um arranjo padrão para este código b Decodificar o vetor recebido 101010 c Admita que o vetor código 101100 tenha sido corrompido pelo padrão de erro 010100 Decodifique o vetor recebido Solução a O Arranjo Padrão De acordo com o Exemplo 213 este código é capaz de corrigir garantidamente todos os padrões de um erro Como n 6 então existem seis padrões de um erro que são aqueles listados na Tabela 27 Entretanto para a montagem do arranjo padrão são necessários 2nk 8 padrões de erros para compor a primeira coluna do arranjo Esses oito padrões de erros geram evidentemente oito síndromes de erro incluindo o padrão de erro e 000000 associado à síndrome S 111 que ocupa a primeira célula da primeira coluna Logo Conforme apresentado na Tabela 28 a única síndrome não nula não associada aos padrões de um erro é a síndrome 0 1 1 c e 2 c ic 2c k 2e 2 2 e c ic e 2 2k 2 e c 3e 2 3 e c ic e 3 2k 3 e c M je e c2 j i j e c k j e c2 M 2e nk 2 2 c e nk 2 2 c e nk k n k 2 2 c e cosets líderes dos cosets palavras códigos subconjuntos s 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 225 S 111 Isso significa que deve haver um ou mais padrões de duplo erro associado à síndrome S 111 pois a capacidade de correção deste código é de um erro De fato podese verificar que existem três padrões de duplo erro capaz de gerar a síndrome S 111 conforme mostrado a seguir mas apenas uma deve ser escolhida para compor o arranjo padrão 111 1 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 001010 010100 100001 S e H S ou ou T Uma vez escolhido o padrão de duplo erro para completar a primeira linha do arranjo padrão que neste exemplo é o padrão de erro e 100001 podese montar o arranjo padrão da seguinte forma 1 1a Linha todas as palavras códigos iniciandose pela palavra toda zero Tabela 26 000000 101100 110010 011110 011001 110101 101011 000111 2 1a Coluna os n k padrões de erros corrigíveis garantidamente ou não 000000 101100 110010 011110 011001 110101 101011 000111 100000 010000 001000 000100 000010 000001 100001 3 Demais células cada célula é ocupada pelo vetor resultante da soma da palavra código do subconjunto da célula pelo seu líder do coset 000000 101100 110010 011110 011001 110101 101011 000111 100000 001100 010010 111110 111001 010101 001011 100111 010000 111100 100010 001110 001001 100101 111011 010111 001000 100100 111010 010110 010001 111101 100111 001111 000100 101000 110110 011010 011101 110001 101111 000011 000010 101110 110000 011100 011011 110111 101001 000101 000001 101101 110011 011111 011000 110100 101010 000110 100001 001101 010011 111111 111000 010100 001010 100110 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 226 b Decodificação do vetor 101010 Conforme mostrado abaixo o vetor 101010 pertence ao coset cujo líder é o padrão de erro 000001 e ao subconjunto do vetor código 101011 000000 101100 110010 011110 011001 110101 101011 000111 100000 001100 010010 111110 111001 010101 001011 100111 010000 111100 100010 001110 001001 100101 111011 010111 001000 100100 111010 010110 010001 111101 100111 001111 000100 101000 110110 011010 011101 110001 101111 000011 000010 101110 110000 011100 011011 110111 101001 000101 000001 101101 110011 011111 011000 110100 101010 000110 100001 001101 010011 111111 111000 010100 001010 100110 Deste modo a decodificação pelo arranjo padrão pressupõe que o vetor código transmitido foi o vetor 101011 vetor decodificado que foi corrompido pelo padrão de erro 000001 c Decodificação do vetor c 101100 corrompido por e 010100 r c e 101100 010100 r 111000 000000 101100 110010 011110 011001 110101 101011 000111 100000 001100 010010 111110 111001 010101 001011 100111 010000 111100 100010 001110 001001 100101 111011 010111 001000 100100 111010 010110 010001 111101 100111 001111 000100 101000 110110 011010 011101 110001 101111 000011 000010 101110 110000 011100 011011 110111 101001 000101 000001 101101 110011 011111 011000 110100 101010 000110 100001 001101 010011 111111 111000 010100 001010 100110 A decodificação pelo arranjo padrão pressupõe que o vetor código transmitido foi o vetor 011001 vetor decodificado que foi corrompido pelo padrão de erro 100001 Note que houve um equívoco na decodificação porque existem três padrões de duplo erro associado à síndrome S 111 e o que foi escolhido para compor o arranjo padrão não foi o padrão de duplo erro introduzido pelo canal 238 CODIFICADOR PARA CÓDIGOS DE BLOCO SISTEMÁTICOS SIMPLES Quando os códigos de blocos são simples e curtos a implementação de um circuito de codificação pode ser feita diretamente com o auxílio das equações que determinam as palavras códigos Para um código de bloco linear sistemático a palavra código pode ser escrita como 1 1 0 1 1 0 k n k m m m p p p K K c 234 Note que a obtenção dos bits de paridade a partir de 213 resumese às seguintes operações 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 227 1 1 1 1 1 1 1 0 0 1 11 1 11 1 01 0 1 1 0 1 10 1 00 0 0 n k k k n k n k k n k k k k p m p m p m p p m p m p m p p m p m p m p K M K K 235 Assim com o conhecimento da matriz geradora na forma sistemática é possível particularizar o conjunto de equações apresentadas em 235 para a geração das palavras códigos por meio de circuitos lógicos combinacionais Veja Exemplo 215 EXEMPLO 215 Construa um codificador para o código 6 3 representado pela sua matriz geradora reproduzida a seguir 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 0 1 k k k n k I P G Solução De acordo com 241 as equações de paridade para a matriz geradora acima são 1 0 2 2 1 1 2 0 0 m m p m m p m m p Logo um circuito codificador pode ser implementado conforme apresentado a seguir Figura 28 Circuito de codificação para o código 6 3 m m0 m1 m2 p0 p1 p2 c Geração dos bits de paridade 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 228 239 DECODIFICADOR PARA CÓDIGOS DE BLOCO SISTEMÁTICOS SIMPLES Quando os códigos de blocos são simples e curtos um decodificador pode ser implementado com um circuito simples a partir dos seguintes passos 1 Calculo da síndrome 2 Localização do padrão de erro 3 Soma módulo2 do padrão de erro com o vetor recebido O cálculo da síndrome pode ser feito considerando as expressões apresentadas a seguir 1 1 0 1 1 1 1 0 1 1 1 11 10 1 0 01 00 1 0 1 1 0 0 0 1 0 0 0 1 k n n k k k k k n n k n T s s s p p p p p p p p p r r r K L M M M L L L M M M L L K r H S 236 1 1 1 1 1 1 1 0 1 1 11 1 11 1 01 1 1 01 1 10 1 00 0 0 n k k n n k n k n k n k n k k n k n n k k n k n n k k n p r p r p r r s p r p r p r r s p r p r p r r s K M K K 237 Cada síndrome deve gerar um padrão de erro corrigível que deverá ser somado ao vetor recebido EXEMPLO 216 Construa um decodificador para o código 6 3 representado pela sua matriz verificadora de paridade transposta reproduzida a seguir 1 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 HT 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 229 Solução De acordo com 237 as equações das síndromes a partir da matriz verificadora de paridade acima são 5 3 2 2 5 4 1 1 4 3 0 0 r r r s r r r s r r r s Seguindo os passos apresentados e utilizando as equações acima podese desenhar o circuito de decodificação apresentado a seguir Note que o circuito de decodificação pode ser simplificado por meio da exclusão das portas acinzentadas responsáveis pelos bits c0 c1 e c2 de paridade uma vez que o resultado da decodificação resumese aos bits de informação c3 c4 e c5 Figura 29 Circuito de decodificação para o código 6 3 24 DESEMPENHO DOS CÓDIGOS DE BLOCO LINEARES 1 Se um código de bloco capaz de corrigir t erros é utilizado exclusivamente para correção de erros em um canal binário simétrico BSC com probabilidade de transição probabilidade de erro de bit p a probabilidade de erro de bit após a decodificação pode ser determinada aproximadamente por j n j n j t b p p j j n n P 1 1 1 238 Para fins de comparação o desempenho de alguns códigos de bloco lineares simples em um canal AWGN com modulação BPSK com detecção coerente pode ser obtido considerandose que a Vetor recebido r r0 r1 r2 r3 r4 r5 c0 c1 c2 c3 c4 c5 r4 r5 r3 r2 r1 r0 e1 e0 e2 e3 e4 e5 s0 s1 s2 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 230 probabilidade de erro de símbolo em termos da relação entre a energia de símbolo codificado e a densidade espectral de ruído EcN0 pode ser determinada por 0 2 1 N E erfc p c 239 Por sua vez é necessário relacionar também EcN0 com EbN0 que é relação entre energia gasta com os bits de informação e a densidade espectral de ruído ou seja 0 0 0 N R E N E n k N E b c b c 240 Substituindo 246 em 245 obtémse 0 2 1 N erfc R E p b c 241 Com 241 e 238 a comparação do desempenho aproximado entre alguns códigos de blocos simples transmitidos sobre a modulação BPSK com a própria modulação BPSK não codificada pode ser obtida diretamente A Figura 210 mostra o desempenho aproximado entre a modulação BPSK não codificada com as BPSKs com os códigos Hamming 7 4 BCH 15 7 Golay 23 12 BCH 63 36 e BCH 127 64 Figura 210 Desempenho de alguns códigos de blocos lineares Pb 2 4 6 8 10 12 10 7 10 6 10 5 10 4 10 3 001 01 EbN0 BPSK não codificada 7 4 t 1 15 7 t 2 23 12 t 3 63 36 t 5 127 64 t 10 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 231 Note que os códigos cujos desempenhos estão apresentados na Figura 210 possuem taxa de codificação entre 047 e 057 Procurouse desta forma manter a taxa de codificação praticamente constante para que o desempenho dos códigos com diferentes comprimentos fossem comparados Isso foi feito com o objetivo de evidenciar uma importante característica dos códigos de blocos a capacidade dc correção de erros por bloco aumenta com o aumento do comprimento quando a taxa de codificação é mantida constante Como consequência aumentos significativos no desempenho podem ser obtidos 25 CÓDIGOS CÍCLICOS 123456 251 INTRODUÇÃO AOS CÓDIGOS CÍCLICOS Os códigos cíclicos binários são uma importante subclasse de códigos de bloco lineares São códigos de fácil implementação com registradores de deslocamento realimentados O cálculo da síndrome também pode ser facilmente executado de forma similar com registradores de deslocamento realimentados Um código linear n k é chamado de código cíclico se ele pode ser descrito pela propriedade apresentada a seguir Se a ntupla c c0 c1 c2 cn1 é um vetor código no subespaço S então c1 cn1 c0 c1 cn2 obtido pelo deslocamento correspondente a uma posição de bit é também um vetor código em S Em geral ci cni cni1 c1 cn1 c0 c1 cni1 obtido pelo deslocamento correspondente a i posições de bit é também um vetor código em S Os componentes de um vetor código u podem ser tratados como os coeficientes de um polinômio cX como mostrado a seguir cX c0 c1X c2X 2 cn1X n1 242 Nesta representação a presença ou ausência de cada termo no polinômio indica a presença de um 1 ou 0 respectivamente na correspondente locação da ntupla Desta forma o polinômio pode ter grau n 1 ou menos 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 232 Exemplo 217 Seja o vetor código c 0 0 0 1 1 0 1 de um código de bloco linear 7 4 Sua representação polinomial é cX X 3 X 4 X 6 ou seja um polinômio de grau n 1 O valor de c3 que também pertence ao mesmo código 7 4 é c3 1 0 1 0 0 0 1 Podemse gerar códigos cíclicos usando um polinômio gerador da mesma forma que são gerados os códigos de bloco usando uma matriz geradora O polinômio gerador gX para um código cíclico n k tem a forma gX g0 g1 X g2 X 2 gn k X nk 243 onde g0 e gnk devem ser iguais a 1 e o grau do polinômio gerador deve ser n k Finalmente um polinômio gX é um polinômio gerador de um código cíclico n k se e somente se ele for um fator de X n 1 EXEMPLO 218 Verifique se o polinômio X 3 X 1 gera um código cíclico C 7 4 Solução X 7 1 X 3 X 1 X 7 X 5 X 4 X 4 X 2 X 1 0 X 5 X 4 1 X 5 X 3 X 2 0 X 4 X 3 X 2 1 X 4 X 2 X 0 X 3 X 1 X 3 X 1 0 Conclusão O polinômio X 3 X 1 gera um código cíclico 7 4 e ainda permitenos concluir que o polinômio X 4 X 2 X 1 que é o quociente da divisão realizada gera um código cíclico 7 3 pois X 7 1 X 4 X 2 X 1 X 3 X 1 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 233 A matriz geradora para um código cíclico gerado pelo polinômio gerador gX pode ser obtida fazendo k n k n k n k n g g g g g g g g g g g g g g g g L L M M L L L L L L 2 1 0 2 1 0 2 1 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 G 244 Onde g0 g1 g2 gnk são os termos do polinômio gX g0 g1X g2X 2 gnk X nk É possível fazer a codificação de forma sistemática através de uma matriz geradora G obtida a partir da matriz G Para isso conforme visto anteriormente G deve ter a forma 1 0 0 0 1 0 0 0 1 2 1 2 22 21 1 12 11 L L M M M M M M M L L L L M n k k k k k n k n k p p p p p p p p p I P G 245 Isso pode ser feito através de operações lineares com as linhas de G até que G tome a forma desejada EXEMPLO 219 Determine o vetor código de um código cíclico 7 4 correspondente a mensagem m 1011 utilizando a matriz geradora na forma sistemática obtida a partir do polinômio gerador gX X 3 X 1 Solução Do exemplo anterior a matriz geradora na forma não sistemática é 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 G Por inspeção verificase que a primeira e a segunda linha estão corretamente posicionadas para a obtenção de uma matriz na forma sistemática A terceira linha da matriz pode ser obtida através da soma das linhas 1 e 3 A quarta linha da matriz pode ser obtida somandose as linhas 1 2 e 4 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 234 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 O vetor código na forma sistemática é obtido pela operação U mG conseqüentemente 1001011 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 1011 G m c c É fácil concluir que uma vez obtida a matriz G na forma sistemática a obtenção da matriz verificadora de paridade H do código C gerado por G é imediata pois T n k P I H M 252 CODIFICAÇÃO SISTEMÁTICA DE CÓDIGOS CÍCLICOS COM REGISTRADORES DE DESLOCAMENTO DE nk ESTÁGIOS Um vetor mensagem pode ser escrito na forma polinomial como 1 1 2 2 1 0 m mk X k m X m X m X 246 Na forma sistemática os dígitos de mensagem são apresentados explicitamente como parte do vetor código Para que a porção mensagem da palavra código ocupe as posições dos bits mais significativos podemos fazer um deslocamento dos bits de mensagem para a direita ficando as n k posições mais a esquerda para a parte de paridade ou seja 1 1 1 1 0 m n k n k n k n k X m m X m X X X 247 Dividindo a expressão acima por gX obtémse X X X X X n k r g q m 248 ou então X X X X X X n k c g q m r 249 Onde o resto rX representa a parte de paridade do vetor código e o produto Xn k mX representa a parte mensagem que foi deslocada n k bits para a direita 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 235 EXEMPLO 220 Determine o vetor código de um código cíclico 7 4 na forma sistemática para m 1011 utilizando o polinômio gerador gX X 3 X 1 Solução mX 1 X 2 X 3 X n k mX X 3 1 X 2 X 3 X 3 X 5 X 6 Dividindo X n k mX por gX podese escrever X 3 X 5 X 6 1 X X 2 X 3 1 X X 3 1 X n k X q X gX resto Finalmente cX rX X 3 mX 1 X 3 X 5 X 6 c 1001011 O circuito que faz as operações polinomiais apresentadas anteriormente está apresentado na Figura 211 Figura 211 Codificador para códigos cíclicos sistemáticos utilizando registradores de deslocamento g1 g2 gnk1 r0 r1 r2 rnk1 Chave 1 a b Entrada Chave 2 saída gi Conexão vinculada a existência de gi 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 236 O procedimento de codificação com o circuito da Figura 211 é o seguinte Passo 1 A chave 1 permanece fechada para permitir a entrada dos bits de mensagem no estágio de codificação A chave 2 permanece na posição a para permitir a transmissão dos bits de mensagem diretamente para o registro de saída durante os primeiros k deslocamentos Passo 2 Após a transmissão dos k bits de mensagem a chave 1 é aberta impedindo a realimentação e a chave 2 é movida para a posição b Passo 3 Os nk bits de paridade que estão armazenados nos registros de deslocamento são transmitidos completando a transmissão do polinômio código EXEMPLO 221 Seja o código 7 4 cujo polinômio gerador é gX 1 X X 3 Para o vetor mensagem m 1011 o polinômio código resultante é cX 1 X 3 X 5 X 6 que corresponde ao vetor código c 1001011 Mostre a formação e transmissão deste vetor código utilizando o circuito da Figura 211 Solução Figura 212 Circuito de codificação para o Exemplo 221 Fila de entrada Número de deslocamentos Conteúdo dos registradores Saída 1011 101 10 1 0 1 2 3 4 000 110 101 100 100 1 1 0 1 Após os 4 deslocamentos a chave 1 é aberta a chave 2 passa para a posição b e o conteúdo dos registros paridade é transmitido Logo o vetor transmitido é c 1001011 r0 r1 r2 Chave 1 a b mX 1 X 2 X 3 Entrada Chave 2 Saída g0 g1 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 237 253 DETECÇÃO DE ERROS DE CÓDIGOS CÍCLICOS SISTEMÁTICOS COM REGISTRADORES DE DESLOCAMENTO DE nk ESTÁGIOS Um vetor código transmitido cX pode ser alterado pela presença de ruído de forma que função do decodificador é recuperar o vetor código transmitido a partir do vetor recebido Seja então um vetor recebido 1 1 2 2 1 0 r rn X n r X r X r X L 250 O decodificador deve testar se o vetor recebido é um vetor código o que equivale a dividir o polinômio recebido pelo polinômio gerador pois S g q r X X X X 251 Se a síndrome for zero o vetor recebido é aceito como um vetor código caso contrário temse uma detecção de erro através da síndrome EXEMPLO 222 Determinar a síndrome do vetor r 1001011 codificado na forma sistemática a partir do polinômio gerador gX 1 X X 3 utilizando registradores de deslocamento Mostre a formação da síndrome a cada deslocamento Solução O circuito para a determinação da síndrome é semelhante ao utilizado para a codificação conforme mostrado a seguir Figura 213 Circuito de detecção de erros para o código cíclico gerado por gX 1 X X 3 r0 r1 r2 Chave Saída da síndrome g0 g1 Chave Entrada 1001011 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 238 Procedimento Passo 1 A chave 1 é inicialmente fechada e a chave 2 aberta O vetor recebido é deslocado pela entrada dos registradores cujos estados iniciais são todos zero Após o vetor recebido estar todo nos registradores seu conteúdo é a síndrome Passo 2 A chave 1 é então aberta e a chave 2 fechada de forma a permitir que o vetor síndrome possa ser deslocado para fora dos registradores O conteúdo dos registradores a cada deslocamento é apresentado a seguir Fila de entrada Número de deslocamentos Conteúdo dos registradores 1001011 100101 10010 1001 100 10 1 0 1 2 3 4 5 6 7 000 100 110 011 011 111 101 000 254 DECODIFICADOR DE MEGGITT 346 Códigos cíclicos podem ser decodificados utilizandose o decodificador cujo modelo genérico é apresentado na Figura 214 conhecido como Decodificador de Meggitt Seu funcionamento pode ser descrito da seguinte forma Passo 1 Inicialmente as chaves CH 1 CH 3 e CH 4 estão fechadas e as chaves CH2 e CH5 abertas A síndrome é gerada pelo deslocamento do vetor recebido ao mesmo tempo em que este é armazenado no registrador de deslocamento Passo 2 A síndrome é lida pelo gerador de padrão de erro O gerador de padrão de erro é um circuito combinacional que apresenta 1 em sua saída se e somente se a síndrome gerada corresponde ao padrão de erro na posição mais a direita do vetor recebido Se o vetor recebido for um vetor válido o gerador de padrão de erro terá zero em sua saída e assim permanecerá até que o vetor recebido seja todo deslocado para fora 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 239 Figura 214 Diagrama em blocos do decodificador de Meggitt Passo 3 As chaves CH 1 e CH 3 são abertas a chave CH4 permanece fechada e as chaves CH2 e CH5 são fechadas É iniciado o deslocamento cíclico do vetor recebido ao mesmo tempo em que o gerador de padrão de erro realimenta o gerador de síndrome Se o vetor recebido tiver um padrão de erro corrigível durante o deslocamento cíclico do vetor recebido o padrão de erro irá se deslocar até que ele alcance a posição mais a direita do registrador de deslocamento Durante esse processo a síndrome é modificada a cada deslocamento Quando o padrão de erro alcança a posição mais a direita do registrador de deslocamento o gerador de padrão de erro apresentará 1 em sua saída que será somado na saída do decodificador e inverterá o bit correspondente a esta posição Após o enésimo deslocamento o conteúdo do registrador de deslocamento é o vetor recebido corrigido Registrador de deslocamento Gerador de síndrome Gerador de padrão de erro Vetor corrigido Vetor recebido Conexões de realimentação Modificação da síndrome CH 1 CH 2 CH 3 CH 4 CH 5 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 240 Passo 4 Após todo o deslocamento do vetor recebido as chaves CH 1 CH 3 e CH 4 são fechadas e as chaves CH2 e CH5 abertas e a decodificação do próximo vetor é feita repetindose os passos de 1 a 3 O exemplo apresentado a seguir ilustra todos os passos da operação de decodificação de um decodificador de Meggitt EXEMPLO 223 Considere a decodificação do código cíclico 7 4 gerado pelo polinômio gX 1 X X 3 Este é um código perfeito capaz de corrigir exclusivamente todos os padrões de um erro Suponha que o vetor código c 1 0 0 1 0 1 1 tenha sido transmitido e o vetor recebido tenha sido r 1 0 1 1 0 1 1 Evidentemente existe um erro na terceira posição da esquerda para a direita Mostre a decodificação deste vetor passo a passo utilizando o decodificador de Meggitt Solução Os padrões de erros e suas respectivas síndromes para este código são apresentados na Tabela 29 Tabela 29 Padrões de erros e síndromes para o código gerado por gX 1 X X 2 Padrões de erros Síndromes 1000000 100 0100000 010 0010000 001 0001000 110 0000100 011 0000010 111 0000001 101 Note que a síndrome correspondente ao padrão de erro posicionado mais a direita 0000001 é 101 que será o único padrão de erro gerado pelo decodificador O decodificador de Meggitt para este código está apresentado na Figura 215 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 241 Figura 215 Decodificador de Meggitt para o código cíclico gerado por gX 1 X X 2 Passo 1 Inicialmente as chaves CH 1 CH 3 e CH 4 estão fechadas e as chaves CH2 e CH5 abertas O vetor 1 0 1 1 0 1 1 é carregado no registrador de deslocamento Passo 2 A síndrome correspondente ao padrão de erro é gerada e lida pelo gerador de padrão de erro conforme mostrado na Figura 216 a Como a síndrome não corresponde ao padrão de erro na posição mais a direita do vetor recebido a saída do gerador de padrão de erro é zero Passo 3 As chaves CH 1 e CH3 são abertas CH 4 permanece fechada e as chaves CH2 e CH5 são fechadas É iniciado o deslocamento cíclico do vetor recebido Note que enquanto a posição de erro não alcança a última posição do registrador de deslocamento nada é somado à saída do decodificador Veja Figura 216 a até d Vetor corrigido Vetor recebido CH 1 CH 2 CH 3 CH 4 CH 5 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 242 Figura 216 a a d Decodificação passoapasso para o Exemplo 223 No quarto deslocamento Figura 216 e o padrão de erro alcança a última posição do registrador de deslocamento e o gerador de padrão de erro gera 1 para ser somado com a última posição de bit do registrador de deslocamento que é o bit errado A partir do quinto deslocamento não há mais erro no vetor e a síndrome passa a ser zero e assim permanece até que todo o deslocamento cíclico seja completado A Figura 216 h apresenta o vetor corrigido como conteúdo do registrador de deslocamento 1 0 1 1 0 1 1 0 0 1 2 1 0 s s s Registrador de deslocamento Síndrome Padrão de erro a Passo 1 0 1 1 0 1 1 0 1 1 1 0 2 1 0 s s s b 1 o Deslocamento 0 1 1 1 0 1 1 0 0 1 1 2 1 0 s s s c 2o Deslocamento 0 0 1 1 1 0 1 1 1 1 1 2 1 0 s s s d 3o Deslocamento 0 Erro Erro Erro Erro 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 243 Figura 216 e a h Decodificação passoapasso para o Exemplo 223 1 0 1 1 1 0 1 1 0 1 2 1 0 s s s e 4o Deslocamento 1 0 1 0 1 1 1 0 0 0 0 2 1 0 s s s f 5 o Deslocamento 0 0 0 1 0 1 1 1 0 0 0 2 1 0 s s s Saída g 6o Deslocamento 0 1 0 0 1 0 1 1 0 0 0 2 1 0 s s s Saída h 7o Deslocamento 0 Erro 0 Correção do bit errado Bit corrigido Vetor código 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 244 26 CÓDIGOS DE BLOCOS BEM CONHECIDOS 6 Nas subseções a seguir são apresentados os códigos de blocos mais conhecidos uma breve descrição de cada um e as suas principais características 261 CÓDIGOS DE HAMMING São códigos de bloco simples que podem ser obtidos de forma cíclica caracterizados pela seguinte estrutura n k 2m 1 2m 1 m 252 onde m 2 3 Isto é suas características principais são apresentadas na Tabela 210 Tabela 210 Principais características dos Códigos de Hamming Comprimento do código n 2m 1 Número de bits de informação k 2m 1 m Número de bits de paridade n k m Distância mínima dmin 3 Capacidade de correção t 1 Estes códigos têm uma distância mínima igual a 3 e apesar de terem capacidade de correção de erro limitada eles pertencem a uma classe muito limitada de códigos de bloco conhecidos como códigos perfeitos 262 CÓDIGOS GOLAY Também é um código cíclico e perfeito Possui maior capacidade de correção do que os códigos de Hamming Suas principais características estão são apresentadas na Tabela 211 n k 23 12 Tabela 211 Principais características do Código Golay Comprimento do código n 23 Número de bits de informação k 12 Número de bits de paridade n k 11 Distância mínima dmin 7 Capacidade de correção t 3 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 245 O código Golay pode ser gerado a partir de um dos dois polinômios g1X 1 X 2 X 4 X 5 X 6 X 10 X 11 g2X 1 X X 5 X 6 X 7 X 9 X 11 253 254 O código Golay é facilmente decodificado através de dois decodificadores de armadilha de erro refinados o decodificador de Kasami e o decodificador de busca sistemática Maiores detalhes a respeito de ambos podem ser encontrados em 4 263 CÓDIGOS BCH BOSE CHAUDHURI HOCQUENGHEM Os códigos BCH formam uma extensa classe de códigos cíclicos com grande capacidade de correção de erros Eles são uma extraordinária generalização dos códigos de Hamming para correção de múltiplos erros Os códigos BCH podem ser caracterizados da seguinte forma para qualquer inteiro positivo m m 3 e t t 2m 1 existe um código BCH binário com os parâmetros apresentados na Tabela 212 Tabela 212 Principais características dos códigos BCH Comprimento do código n 2m 1 Número de bits de informação k 2m 1 mt Número de bits de paridade n k mt Distância mínima dmin 2t 1 Capacidade de correção t erros Detalhes a respeito da implementação dos códigos BCH bem como os principais algoritmos de decodificação são encontrados nas Referências 4 e 6 264 CÓDIGOS REEDSOLOMON RS Os códigos Reed Solomon RS são uma subclasse dos códigos BCH São códigos cíclicos não binários com símbolos formados por seqüências de m bits onde m é qualquer positivo inteiro tendo valor maior do que 2 Os códigos RS com símbolos de m bits existem para todo n e k para o qual 2 2 0 m n k 255 onde k é o número de símbolos de dados que estão sendo codificados e n é o número de símbolos códigos em um bloco codificado As principais características dos códigos RS mais comuns estão apresentadas na Tabela 213 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 246 Tabela 213 Principais características dos códigos RS mais comuns Comprimento do código n 2m 1 Número de bits de informação k 2m 1 2t Número de bits de paridade n k 2t Distância mínima dmin n k 1 Capacidade de correção 2 k n t Esses códigos além de uma notável capacidade de correção de erros são particularmente úteis para correção de erros em rajada São extensamente utilizados em diversos sistemas de comunicações concatenados principalmente com códigos convolucionais além de outros sistemas de armazenamento de informações como CD para áudio digital 265 CÓDIGOS REEDMULLER RM Os códigos ReedMuller são uma importante subclasse dos códigos decodificáveis por lógica majoritária baseados em geometria finita ou geometria euclidiana São códigos que podem ser gerados na forma cíclica e não cíclica Suas principais características são apresentadas na Tabela 214 Tabela 214 Principais características dos códigos RM Comprimento do código n 2m 1 Número de bits de informação µ i 0 i m k Número de bits de paridade µ 0 1 2 i m i m k n Distância mínima dmin 2mµ 1 Capacidade de correção 2 2 2 m µ t Para comprimentos moderados n os códigos RM possuem uma capacidade de correção de erro ligeiramente inferior que os códigos BCH Entretanto a decodificação por lógica majoritária é muito mais simples de implementar do que as decodificações para códigos BCH o que torna atrativo o seu uso Para comprimentos grandes o desempenho dos códigos RM tornase muito inferior quando comparado com os BCH 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 247 27 EXERCÍCIOS 1 Projete um código de bloco linear 5 2 com codificação na forma sistemática tendo como objetivo a maximização do valor de dmin e determine a A matriz geradora do código b A matriz verificadora de paridade c A capacidade de detecção e de correção de erros do código d A tabela de síndrome associada aos padrões de erros corrigíveis 2 Considere um código sistemático 8 4 cujas equações de verificação de paridade são p0 m1 m2 m3 p1 m0 m1 m2 p2 m0 m1 m3 p3 m0 m2 m3 onde m0 m1 m2 e m3 são bits de mensagem e p0 p1 p2 e p3 são bits de verificação de paridade Pedese a Encontrar a matriz geradora e a matriz verificadora de paridade para este código b Mostre que a distância mínima deste código é 4 Justifique c Verifique se os vetores recebidos 10101010 e 01011100 são vetores códigos usando a síndrome de erros d Desenhe um circuito codificação para este código e Desenhe um circuito de decodificação para este código de forma que a correção de todos os padrões de um erro e detecção simultânea de dois erros possa ser realizada 3 Calcule a probabilidade de uma mensagem formada por uma seqüência de 12 bits codificada com um código de bloco linear 24 12 possuir um erro Admita que o código corrige todos os padrões de 1 e 2 erros e nenhum outro padrão a mais Admita também que a probabilidade de erro do canal é igual a 103 4 Considere o código cíclico 7 4 gerado por gX 1 X 2 X 3 a Mostre que o polinômio gerador apresentado gera de faro um código cíclico 7 4 b Encontre todas as palavras códigos c Encontre a matriz verificadora de paridade do código d Verifique se o vetor recebido r 1101101 é um vetor válido através da síndrome e Qual é a capacidade de correção de erros do código f Qual é a capacidade de detecção de erros do código g Desenhe um codificador para este código utilizando registradores de deslocamento h Desenhe o decodificador de Meggitt para este código 2 CODIFICAÇÃO DE CANAL CÓDIGOS DE BLOCO LINEARES 2BlocoV2011Rev4 Geraldo Gil R Gomes 248 5 Considere o código cíclico 15 7 gerado por gX 1 X 4 X 6 X 7 X 8 a Encontre a matriz verificadora de paridade deste código b Determine a capacidade de correção de erros deste código c Este é um código perfeito Por quê d Desenhe um circuito para o cálculo da síndrome de erros para este código e Mostre como funciona o circuito para o cálculo da síndrome para cada bit de entrada do polinômio recebido rX 1 X 10 X 12 X 13 X 14 f Determine qual é o vetor código mais provável de ter sido o vetor transmitido considerando o polinômio recebido apresentado na questão e 28 REFERÊNCIAS BIBLIOGRÁFICAS 1 SKLAR B Digital Communications Fundamentals and Applications 2nd ed PTR Prentice Hall Upper Saddle River NJ 2001 1079 p 2 McELIECE Robert J The theory of information and coding 2 ed Cambridge Cambridge University Press 2002 ISBN 0521000955 3 ZIEMER R E PETERSON R L Introduction to Digital Communication 2 ed Upper Saddle River Prentice Hall 2001 ISBN 0138964815 4 LIN S COSTELO JR D J Error Control Coding Fundamentals and Applications Englewood Cliffs Prentice Hall 1983 ISBN 013283796X 5 BERLEKAMP Elwin R Algebric Coding Theory New York McGrawHill 1968 6 WICKER S B Error control systems for digital communication and storage Upper Saddle River New Jersey Prentice Hall 1995