Codificação de Canal em Sistemas de Comunicação Digital

Codificação de Canal Códigos corretores de erros Códigos de bloco Códigos convolucionais Centro de Tecnologia Departamento de Eletrônica e Computação UFSM00261 SISTEMAS DE COMUNICAÇÃO DIGITAL I Prof Fernando DeCastro Codificação de Canal Conforme já brevemente discutido nos slides 3 8 e 9 do Cap I o Codificador de Canal channel encoder marca c bits de paridade as palavras binárias recebidas do Codificador de Fonte de modo que o Decodificador de Canal channel decoder corrija os erros em bits causados pelo ruído branco aditivo originado no canal e no front end de RF do RX Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 2 Portanto a Codificação de Canal é o processo responsável em um sistema digital por manter a BER bit error rate dentro de um limite máximo considerado aceitável no âmbito das especificações de desempenho de um determinado sistema digital RX TX Quando informação digital é enviada pelo TX através do canal de transmissão ruído e interferência inerentes a qualquer canal prático degradam o sinal de forma que as palavras binárias recebidas no RX contêm erros O usuário do sistema digital geralmente estabelece uma taxa de erro máxima aceitável por exemplo um bit errado em 1 106 bits recebidos ie 𝐵𝐸𝑅 1 106 acima da qual os dados recebidos não são considerados utilizáveis pelo usuário Esta taxa de erro máxima aceitável depende da informação que transita pelo canal A título de comparação a BER máxima permitida para transmissão de voz através de telefonia celular é muito maior do que a BER exigida para transmissão de dados Isto ocorre porque na pior das hipóteses mesmo sob uma alta BER e consequente distorção o sistema auditivo humano é capaz de compreender o significado das frases pelo contexto da conversa o que já não acontece quando dois computadores trocam dados binários Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 3 Codificação de Canal RX TX Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 4 Codificação de Canal RX TX O Codificador de Canal é portanto o responsável em um sistema digital por manter a BER dentro de um limite máximo aceitável A possibilidade do uso de codificação para controlar com eficiência a BER de um sistema de comunicação digital foi demonstrada por Shannon em 1948 através do Teorema Fundamental de Shannon já discutido nos slides 34 a 46 do Cap I das notas de aula Teorema Fundamental de Shannon Se a taxa velocidade de transmissão R bitss da informação a ser enviada pelo canal é menor que um valor C bitss denominada de Capacidade do Canal então a comunicação através do canal pode ser estabelecida com probabilidade de erro tão baixa quanto se deseje através do uso de um código adequado para correção de erro Códigos corretores de erro Desta maneira o Teorema Fundamental de Shannon estabelece a existência de um código corretor de erro tal que a informação pode ser enviada pelo TX e transmitida através do canal de transmissão com uma BER arbitrariamente baixa resultante no RX desde que a taxa de transmissão R bitss seja menor ou igual à capacidade do canal C bitss Neste estudo daremos enfoque às técnicas de correção de erro mais importantes no âmbito de duas grandes classes de códigos para correção de erro 1 códigos de bloco ver httpsenwikipediaorgwikiBlockcode 2 códigos convolucionais ver httpsenwikipediaorgwikiConvolutionalcode Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 5 RX TX Códigos de Bloco De maneira similar aos códigos para compressão por entropia discutidos no Cap II um código de bloco pode ser considerado como um operador 𝜽 tal que 𝑪 𝜽𝑿 onde 𝑿 𝑥𝑖 𝑥0 𝑥1 𝑥𝑀1 é o conjunto de 𝑀 possíveis mensagens 𝑥𝑖 a serem codificadas e 𝑪 𝑐𝑖 𝑐0 𝑐1 𝑐𝑀1 é o conjunto de 𝑀 possíveis palavrascódigo 𝑐𝑖 resultantes da codificação com 𝑖 01 𝑀 1 O operador 𝜽 é definido por um codebook que efetua um mapeamento unívoco entre cada mensagem 𝑥𝑖 e a respectiva palavracódigo 𝑐𝑖 O conjunto de caracteres do código ou alfabeto do código é o conjunto 𝐀 𝑎0 𝑎1 𝑎𝐷1 composto por 𝐷 elementos de cuja composição são formadas cada mensagem e sua respectiva palavracódigo para códigos binários 𝚨 01 Codificador de Canal 𝜽 Mensagem 𝑥𝑖 𝑘 𝑏𝑖𝑡𝑠 PalavraCódigo 𝑐𝑖 𝑛 𝑏𝑖𝑡𝑠 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 6 Cada mensagem 𝑥𝑖 𝑿 é considereda como sendo um vetor 𝑥𝑖 𝑥𝑖𝑘1𝑥𝑖𝑘2 𝑥𝑖1𝑥𝑖0 de 𝑘 componentes 𝑥𝑖𝑗 𝑨 sendo 𝑗 𝑘 1 𝑘 2 10 Visto que os 𝑘 componentes da 𝑖ésima mensagem 𝑥𝑖 pertencem ao alfabeto 𝑨 é válida a relação de pertinência 𝑥𝑖 𝑨𝑘 Da mesma forma cada palavracódigo 𝑐𝑖 𝑪 é um vetor 𝑐𝑖 𝑐𝑖 𝑛1 𝑐𝑖 𝑛2 𝑐𝑖1𝑐𝑖0 de 𝑛 componentes 𝑐𝑖𝑗 𝑨 sendo 𝑗 𝑛 1 𝑛 2 10 Visto que os 𝑛 componentes da 𝑖ésima palavracódigo 𝑐𝑖 pertencem ao alfabeto 𝑨 vale a relação de pertinência 𝑐𝑖 𝑨𝑛 Por exemplo a 𝑖ésima palavracódigo binária 0101 de 𝑛 4 bits é representada pelo vetor 𝑐𝑖 0 1 0 1 onde 𝑐𝑖 𝑨4 sendo o alfabeto definido por 𝚨 01 𝑐𝑖3 𝑐𝑖0 Códigos de Bloco binários Um código de bloco binário 𝜽 mapeia um conjunto 𝑿 𝑥𝑖 𝑥0 𝑥1 𝑥𝑀1 de 𝑀 2𝑘 mensagens binárias cada uma delas com 𝑘 bits em um conjunto 𝑪 𝑐𝑖 𝑐0 𝑐1 𝑐𝑀1 palavrascódigo binárias cada uma delas com 𝑛 bits onde 𝑛 𝑘 O mapeamento é definido por um codebook que implementa a operação 𝑐𝑖 𝜽𝑥𝑖 Um codebook que implementa o mapeamento 𝑐𝑖 𝜽𝑥𝑖 de um código binário cujas mensagens 𝑥𝑖 de 𝑘 bits são codificadas em palavrascódigo 𝑐𝑖 de 𝑛 bits é alternativamente representado pelo operador 𝜽𝑛 𝑘 ou simplesmente 𝜽𝑛 𝑘 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 7 Codificador de Canal 𝜽𝒏 𝒌 Mensagem 𝑥𝑖 𝑘 bits PalavraCódigo 𝑐𝑖 𝑛 bits Um código 𝜽𝑛 𝑘 é sistemático quando cada palavracódigo de 𝑛 bits é formada pelos 𝑘 bits da respectiva mensagem associada acrescidos por justaposição de 𝑟 𝑛 𝑘 bits adicionais destinados ao controle e correção de erros denominados de bits de paridade Portanto em um código sistemático cada mensagem contendo 𝑘 bits de informação é expandida em uma palavracódigo de 𝑛 𝑘 𝑟 bits onde 𝒓 é o número de bits representativos da informação redundante adicionada visando o controle e correção de erro Um código 𝜽𝑛 𝑘 é nãosistemático quando nas palavrascódigos de 𝑛 bits não aparecem explicitamente representados os 𝑘 bits de informação da respectiva mensagem associada É possível converter um código nãosistemático em um código sistemático Em função disto nossa atenção será dada aos códigos sistemáticos Tanto o código não sistemático quanto o código convertido em um código sistemático possuem a mesma capacidade de correção e de detecção por isso são ditos códigos equivalentes Note no entanto que a implementação em hardware de um código sistemático é mais simples do que a de um código nãosistemático Códigos de Bloco binários Por exemplo o código 𝜽43 definido no codebook abaixo é sistemático porque cada palavracódigo 𝑐𝑖 de 𝑛 4 bits é formada pela justaposição de 1 bit de paridade aos 𝑘 3 bits de informação da mensagem 𝑥𝑖 associada Observe que como 𝑛 𝑘 no conjunto de todas as 2𝑛possíveis palavrascódigos de 𝑛 bits existem 𝟐𝒏 𝟐𝒌 elementos que não são associados a qualquer elemento do conjunto 𝑿 𝑥𝑖 𝑥0 𝑥1 𝑥𝑀1 de 𝑀 2𝑘 mensagens binárias de 𝑘 bits Por exemplo para o código binário 𝜽43 no codebook abaixo existem 2𝑛 2𝑘 24 23 8 elementos no conjunto de todas as 2𝑛 24 16 possíveis palavrascódigos de 4 bits sem associação com qualquer mensagem do conjunto 𝑿 000 001 010 011 100 101 110 111 Mensagem 𝑥𝑖 Palavracódigo 𝑐𝑖 000 0000 001 0011 010 0101 011 0110 100 1001 101 1010 110 1100 111 1111 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 8 Razão de codificação Peso de uma PalavraCódigo O tempo 𝒏𝝉𝒔 de duração de cada palavracódigo 𝒄𝒊 deve ser igual ao tempo de duração 𝒌𝝉𝒙 de cada mensagem 𝒙𝒊 ie 𝒏𝝉𝒔 𝒌𝝉𝒙 vide figura abaixo onde 𝜏𝑠 representa a duração de cada bit em uma palavracódigo 𝑐𝑖 e 𝜏𝑥 representa a duração de cada bit em uma mensagem 𝑥𝑖 Se a condição 𝒏𝝉𝒔 𝒌𝝉𝒙 não é obedecida as palavras códigos 𝒄𝒊 resultarão com um tempo de duração 𝒏𝝉𝒔 diferente do que o tempo de duração 𝒌𝝉𝒙 das respectivas mensagens 𝒙𝒊 que a elas deram origem resultando que o espectro da informação codificada será alterado conforme brevemente discutido no slide 8 do Cap I Esta condição implica na inviabilidade de se adotar códigos com uma enorme quantidade 𝑟 𝑛 𝑘 de bits de paridade porque ao aumentar 𝑛 excessivamente resultará em uma muito pequena duração 𝜏𝑠 𝑘 𝑛 𝜏𝑥 em cada bit das palavrascódigo 𝑐𝑖 aumentando a BW final do espectro do sinal transmitido através do canal de transmissão conforme já discutido no slide 5 do Cap I Note que aumentar o número 𝑟 𝑛 𝑘 de bits de paridade em um código aumenta a distância de Hamming entre as palavras código do codebook o que aumenta a robustez do código o que é desejável ver discussão no slide 9 do Cap I No entanto a condição 𝑛𝜏𝑠 𝑘𝜏𝑥 impõe um limite prático para o aumento do número 𝑟 𝑛 𝑘 de bits de paridade em função do indesejável aumento da BW final do espectro do sinal transmitido através do canal de transmissão Dado que a condição 𝑛𝜏𝑠 𝑘𝜏𝑥 precisa ser obedecida para efeito de não alterar o espectro da informação codificada então a razão de codificação 𝑹𝒄 de um código de bloco é definida por 𝑹𝒄 Τ 𝒌 𝒏 Τ 𝝉𝒔 𝝉𝒙 sendo 𝒏 𝒌 O peso de uma palavracódigo 𝑐𝑖 é definido como o número de dígitos 1 nela presentes O conjunto de todos os pesos de um código constitui a distribuição de pesos do código Por exemplo o peso da palavracódigo 𝑐𝑖 0 1 0 1 é 2 Quando todas as 𝑀 palavrascódigo 𝑐𝑖 têm pesos iguais o código é denominado de código de peso constante Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 9 Codificador de Canal 𝜽𝒏 𝒌 Mensagem 𝑥𝑖 𝑘 bits duração 𝑘𝜏𝑥 PalavraCódigo 𝑐𝑖 𝑛 bits duração 𝑛𝜏𝑠 Códigos de Bloco representação polinomial O processo de codificaçãodecodificação de um código de bloco baseiase na propriedade algébrica de que o conjunto de palavrascódigo 𝑪 𝑐𝑖 𝑐0 𝑐1 𝑐𝑀1 pode ser mapeado em um conjunto de polinômios 𝐶𝑖 𝑝 𝐶0 𝑝 𝐶1 𝑝 𝐶𝑀1 𝑝 Os componentes do vetor 𝑐𝑖 𝑐𝑖𝑛1 𝑐𝑖𝑛2 𝑐𝑖1 𝑐𝑖0 que representa a 𝑖ésima palavracódigo 𝑐𝑖 correspondem aos coeficientes do polinômio 𝐶𝑖 𝑝 𝑐𝑖𝑛1𝑝𝑛1 𝑐𝑖𝑛2𝑝𝑛2 𝑐𝑖1𝑝 𝑐𝑖0 associado à palavracódigo 𝑐𝑖 A mesma propriedade algébrica pode ser aplicada sobre o conjunto de mensagens 𝑿 𝑥𝑖 𝑥0 𝑥1 𝑥𝑀1 de modo que este também pode ser mapeado em um conjunto de polinômios 𝑋𝑖 𝑝 𝑋0 𝑝 𝑋1 𝑝 𝑋𝑀1 𝑝 Os componentes do vetor 𝑥𝑖 𝑥𝑖𝑘1𝑥𝑖𝑘2 𝑥𝑖1𝑥𝑖0 que representa a 𝑖ésima mensagem 𝑥𝑖 correspondem aos coeficientes do polinômio 𝑋𝑖 𝑝 𝑥𝑖𝑘1𝑝𝑛1 𝑥𝑖𝑘2𝑝𝑛2 𝑥𝑖1𝑝 𝑥𝑖0 associado à mensagem 𝑥𝑖 Por este motivo os códigos de bloco são também denominados de códigos polinomiais Por exemplo a representação polinomial do código sistemático 𝜽43 definido no codebook do slide 8 é mostrada na tabela abaixo Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 10 Mensagem 𝑥𝑖 Polinômio 𝑋𝑖𝑝 Palavracódigo 𝑐𝑖 Polinômio 𝐶𝑖𝑝 000 0 0000 0 001 1 0011 𝑝 1 010 𝑝 0101 𝑝2 1 011 𝑝 1 0110 𝑝2 𝑝 100 𝑝2 1001 𝑝3 1 101 𝑝2 1 1010 𝑝3 𝑝 110 𝑝2 𝑝 1100 𝑝3 𝑝2 111 𝑝2 𝑝 1 1111 𝑝3 𝑝2 𝑝 1 O processo de codificaçãodecodificação envolve operações aritméticas de adição e multiplicação binárias realizadas sobre o conjunto de polinômios 𝐶𝑖 𝑝 𝐶0 𝑝 𝐶1 𝑝 𝐶𝑀1 𝑝 que representam as palavrascódigo conforme veremos nos próximos slides Um código corretor de erro deve ser tal que o conjunto de polinômios 𝐶𝑖 𝑝 e as operações aritméticas binárias sobre ele definidas obedeçam a determinado regramento algébrico caso contrário a unicidade e o custo computacional no hardware do processo de codificaçãodecodificação resultarão prejudicados Este conjunto de polinômios e o respectivo regramento algébrico a ele associado é denominado de campo algébrico Um campo algébrico conforme veremos nos próximos slides é uma entidade matemática estudada em Álgebra Linear Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 11 Códigos de Bloco representação polinomial Campo Algébrico Um campo algébrico F é um conjunto de elementos que permite duas operações sobre seus elementos adição e multiplicação operações que satisfazem às seguintes propriedades Adição 1 O conjunto F é fechado sob a adição ie se ab F então a b F 2 A adição em F é associativa ie se abc F então a b c a b c 3 A adição em F é comutativa ie se ab F então a b b a 4 O conjunto F contém um único elemento denominado zero representado por 0 que satisfaz a condição a 0 a a F 5 Cada elemento em F tem o seu elemento negativo simétrico Se b F então seu simétrico é denotado por b tal que b b 0 Se a F então a subtração a b entre os elementos a e b é definida como a b Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 12 Multiplicação 1 O conjunto F é fechado sob a multiplicação ie se ab F então ab F 2 A multiplicação em F é associativa ie se F c b a então 𝑎 𝑏𝑐 𝑎𝑏 c 3 A multiplicação em F é comutativa ie se ab F então ab ba 4 A multiplicação em F é distributiva sobre a adição ie se abc F então ab c ab ac 5 O conjunto F contém um único elemento denominado identidade representado por 1 que satisfaz a condição 1a a a F 6 Cada elemento de F exceto o elemento 0 possui um elemento inverso Assim se b F e b 0 então o inverso de b é definido como 𝑏1 tal que 𝑏𝑏1 1 Se a F então a divisão a b entre os elementos a e b é definida como 𝑎𝑏1 Por exemplo o conjunto ℝ dos números reais é um campo algébrico com infinitos elementos assim como também o é o conjunto dos números complexos ℂ Estes dois conjuntos obedecem às propriedades dos campos algébricos descritas anteriormente Um campo algébrico finito com 𝐷 elementos é denominado de Campo de Galois Galois Field e é designado por GF 𝐷 Nem para todos os valores de 𝐷 é possível formar um campo Em geral quando 𝐷 é primo ou uma potência inteira de um número primo é possível construir o campo finito GF 𝐷 consistindo dos elementos 01 𝐷 1 desde que as operações de adição e multiplicação sobre GF 𝐷 sejam operações módulo D Nota Uma operação op é módulo D quando pode ser representada por 𝑎 𝐨𝐩 𝑏 mod 𝐷 onde 𝑥 mod 𝑦 é o operador que resulta no resto da divisão 𝑥𝑦 Por exemplo a operação de soma módulo 5 entre os números 4 e 3 4 𝐨𝐩 3mod 5 resulta em 2 visto que o resto da divisão 75 é 2 portanto 4 3 mod 5 2 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 13 Campo de Galois GF2 Dado que o hardware do codificador e do decodificador de canal executa operações binárias o enfoque em nosso estudo será o Campo de Galois para 𝑫 2 denominado GF2 O GF2 é formado pelo conjunto 01 e pelas operações módulo 2 de soma e multiplicação definidas nas tabelas I e II Tabela I Soma sobre GF2 0 1 0 0 1 1 1 0 Tabela II Multiplicação sobre GF2 0 1 0 0 0 1 0 1 Note nas tabelas I e II que I A soma entre dois elementos 𝑎 e 𝑏 pertencentes a GF2 é implementada pela operação lógica 𝑎 𝑏 ou 𝑎 XOR 𝑏 II A multiplicação entre dois elementos 𝑎 e 𝑏 pertencentes a GF2 é implementada pela operação lógica 𝑎 𝑏 ou 𝑎 AND 𝑏 Dada a facilidade de implementação em hardware das operações de soma e multiplicação com portas lógicas AND e XOR é usual os códigos corretores serem construídos em GF2 Assim um código corretor de erro binário com alfabeto Α 01 é tal que os coeficientes dos polinômios em 𝐶𝑖 𝑝 pertencem a GF2 No hardware do codificador do TX e do decodificador do RX as operações aritméticas realizadas sobre o conjunto de polinômios 𝐶𝑖 𝑝 𝐶0 𝑝 𝐶1 𝑝 𝐶𝑀1 𝑝 ou equivalentemente sobre o conjunto de palavrascódigo 𝐶 𝑐𝑖 𝑐0 𝑐1 𝑐𝑀1 durante o processo de codificaçãodecodificação obedecem às tabelas I e II do slide anterior Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 14 Campo de Galois GF2 Capacidade de detecção e correção de erro de um código binário Suponhamos que 𝑐𝑖 e 𝑐𝑗 sejam duas palavrascódigo quaisquer no codebook de um código 𝜽𝑛 𝑘 Uma medida da dessemelhança entre duas palavrascódigo 𝑐𝑖 e 𝑐𝑗 é o número de bits em posições correspondentes que diferem entre si Esta medida é denominada de Distância de Hamming e é denotada por 𝑑H 𝑑𝑖𝑗 Por exemplo sejam 𝒄𝒊 0 1 0 1 e 𝒄𝒋 1 0 0 0 Então a distância de Hamming é 𝒅𝐇 𝒅𝒊𝒋 3 Observe que 𝑑𝑖𝑗 sempre satisfaz a condição 0 𝑑𝑖𝑗 𝑛 𝑖 𝑗 para duas palavrascódigo 𝑐𝑖 e 𝑐𝑗 ambas de 𝑛 bits por definição em um código 𝜽𝑛 𝑘 𝑐𝑖 𝑐𝑗 𝑖 e 𝑗 com 𝑖 𝑗 O menor valor no conjunto 𝒅𝒊𝒋 é a distância mínima do código denotada como 𝒅𝒎𝒊𝒏 sendo 𝑖 𝑗 0 1 𝑀 1 𝑖 𝑗 e 𝑀 2𝑘 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 15 Codificador de Canal 𝜽𝒏 𝒌 Mensagem 𝑥𝑖 𝑘 bits PalavraCódigo 𝑐𝑖 𝑛 bits A Distância de Hamming 𝒅𝒊𝒋 é uma medida do grau de separação dissimilaridade entre duas palavrascódigo 𝒄𝒊 e 𝒄𝒋 no codebook 𝑪 conforme já discutimos no slide 9 do Cap I Desta maneira 𝑑𝑚𝑖𝑛 define a capacidade do decodificador do código 𝜽𝑛 𝑘 no RX em detectar e corrigir palavrascódigo que são recebidas em erro como consequência do ruído aditivo presente no canal de transmissão Note portanto que quanto maior 𝒅𝒎𝒊𝒏 maior a capacidade de um código 𝜽𝒏 𝒌 detectar e corrigir bits recebidos em erro Uma técnica de decodificação ótima é a decodificação por síndrome que veremos adiante Uma técnica alternativa mas de maior custo computacional é o MaximumLikelihood Decoding MLD conforme já discutido no slide 8 do Cap I e que também veremos adiante No MLD para corrigir os bits errados em uma palavracódigo 𝑐r recebida no decodificador do RX o decodificador MLD determina as 𝑀 respectivas distâncias de Hamming 𝑑H𝑖 entre 𝑐r recebido e as M palavras código 𝑐𝑖 do codebook com 𝑖 0 1 𝑀 1 resultando no conjunto 𝒅𝐇 𝑑𝐻0 𝑑𝐻1 𝑑𝐻𝑀1 O decodificador MLD identifica então qual a menor 𝑑H𝑖 no conjunto 𝒅𝐇 e infere que a palavracódigo 𝑐𝑖 que foi transmitida pelo TX é aquela que corresponde à menor 𝑑H𝑖 no conjunto 𝒅𝐇 Por exemplo 𝑑𝑚𝑖𝑛 2 para o código do código sistemático 𝜽𝑛 4 𝑘 3 definido no codebook do slide 8 cujas 𝑀 2𝑘 8 palavras código no codebook são 𝑪 𝑐𝑖 𝑐0 𝑐1 𝑐𝑀1 0000 0011 0101 0110 1001 1010 1100 1111 Para um código corretor binário 𝜽𝑛 𝑘 que é capaz de detectar até 𝑑 bits errados em cada palavracódigo 𝑐𝑖 de 𝑛 bits recebida no decodificador do RX e que é capaz de corrigir até 𝑡 bits errados em cada palavracódigo 𝑐𝑖 de 𝑛 bits recebida no decodificador do RX é possível demonstrar que 𝑑 e 𝑡 são dados por Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 16 Capacidade de detecção e correção de erro de um código binário sendo o operador que resulta no inteiro mais próximo e menor que o argumento Novamente note de 1 e 2 que quanto maior a 𝒅𝒎𝒊𝒏 resultante do conjunto de palavras códigos no codebook de um código 𝜽𝒏 𝒌 maior será o número de bits recebidos em erro que o código é capaz detectar e corrigir Por exemplo para o código sistemático 𝜽𝑛 4 𝑘 3 definido no codebook do slide 8 e abaixo reproduzido temos que 𝑑𝑚𝑖𝑛 2 de modo que de 1 e 2 obtemos 𝑑 𝑑𝑚𝑖𝑛 1 𝑡 𝑑𝑚𝑖𝑛 1 2 1 2 𝑑 𝑑𝑚𝑖𝑛 1 2 1 1 𝑡 𝑑𝑚𝑖𝑛1 2 21 2 0 Portanto o código sistemático 𝜽𝑛 4 𝑘 3 com 𝑑𝑚𝑖𝑛 2 dado no codebook ao lado é capaz de detectar no máximo 𝑑 𝑑𝑚𝑖𝑛 1 1 um bit errado por palavracódigo recebida no decodificador do RX mas é incapaz de corrigir qualquer bit errado em uma palavracódigo recebida visto que 𝑡 𝑑𝑚𝑖𝑛1 2 0 De fato o codebook ao lado define um simples código paritycheck Um código paritycheck apenas verifica através do bit de paridade se ocorreu algum bit errado mas não é capaz de corrigir o erro Especificamente este código sistemático efetua o XOR entre os bits na palavracódigo 𝑐𝑖 correspondentes ao da mensagem 𝑥𝑖 e compara com o bit de paridade em 𝑐𝑖 Mensagem 𝑥𝑖 Palavracódigo 𝑐𝑖 000 0000 001 0011 010 0101 011 0110 100 1001 101 1010 110 1100 111 1111 Note portanto que se dessemelhança mínima entre as palavrascódigo do codebook dada pelo valor de 𝒅𝒎𝒊𝒏 é insuficiente em relação ao número 𝒕 de bits recebidos em erro então o decodificador se torna incapaz de corrigir os bits errados ou se torna incapaz até mesmo de detectar os bits errados Consideremos a 𝑖 ésima mensagem do codebook de um código binário 𝜽𝑛 𝑘 representada pelo vetor 𝑥𝑖 𝑥𝑖0 𝑥𝑖1 𝑥𝑖𝑘1 e seja a 𝑖ésima palavracódigo do codebook representada pelo vetor 𝑐𝑖 𝑐𝑖0 𝑐𝑖1 𝑐𝑖𝑛1 onde 𝑖 0 1 𝑀 1 𝑀 2𝑘 O processo de codificação da mensagem 𝑥𝑖 𝑥𝑖0 𝑥𝑖1 𝑥𝑖𝑘1 na respectiva palavracódigo 𝑐𝑖 𝑐𝑖0 𝑐𝑖1 𝑐𝑖𝑛1 efetuado pelo codebook de um código binário 𝜽𝑛 𝑘 é representado em forma matricial através de Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 17 𝑐𝑖 𝑥𝑖𝐆 onde a matriz 𝐆𝑘𝑛 é denominada de matriz geradora do código 𝜽𝑛 𝑘 sendo dada por 3 4 A Matriz Geradora de um Código 𝜽𝒏 𝒌 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 18 Desta maneira cada palavracódigo 𝑐𝑖 𝑐𝑖0 𝑐𝑖1 𝑐𝑖𝑛1 obtida através da equação 3 𝑐𝑖 𝑥𝑖𝐆 é simplesmente uma combinação linear dos vetores 𝒈𝒋 sendo os coeficientes da combinação linear dados pelos componentes da mensagem associada 𝑥𝑖 𝑥𝑖0 𝑥𝑖1 𝑥𝑖𝑘1 isto é Podemos interpretar a matriz 𝐆 como um conjunto de 𝑘 vetoreslinha 𝑔𝑗 𝑗 0 1 𝑘 1 tal que 5 𝑐𝑖 𝑥𝑖𝐆 𝑥𝑖0 𝑔0 𝑥𝑖1 𝑔1 𝑔𝑘1 𝑔0 𝑔1 𝑔𝑘1 6 A Matriz Geradora de um Código 𝜽𝒏 𝒌 Exemplo 1 Consideremos o código sistemático 𝜽𝑛 4 𝑘 3 definido no codebook do slide 8 e reproduzido ao lado Verifique se a matriz 𝐆 abaixo é a matriz geradora deste código 𝜽4 3 Solução Cada palavracódigo 𝑐𝑖 𝑐𝑖0 𝑐𝑖1 𝑐𝑖 𝑛1 de 𝑛 4 bits é gerada através de 𝑐𝑖 𝑥𝑖𝐆 a partir da respectiva mensagem 𝑥𝑖 𝑥𝑖0 𝑥𝑖1 𝑥𝑖𝑘1 de 𝑘 3 bits No total existem 2𝑘 8 palavrascódigo em 𝜽43 Assim utilizando 6 para determinar 𝑐𝑖 𝑥𝑖𝐆 e lembrando que no GF2 a multiplicação é efetuada através da operação AND e a soma é efetuada através da operação XOR obtemos A Matriz Geradora de um Código 𝜽𝒏 𝒌 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 19 Portanto 𝐆 é a matriz geradora do código 𝜽43 especificado no codebook acima Mensagem 𝑥𝑖 Palavracódigo 𝑐𝑖 000 0000 001 0011 010 0101 011 0110 100 1001 101 1010 110 1100 111 1111 G 1 0 0 1 0 1 0 1 0 0 1 1 Qualquer matriz geradora 𝐆 de um código 𝜽𝑛 𝑘 pode ser reduzida à forma sistemática através de operações elementares em suas linhas e permutações em suas colunas quando então o código gerado é sistemático Uma matriz geradora 𝐆 encontrase na forma sistemática quando é formatada conforme abaixo Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 20 onde 𝐈𝑘 é a matriz identidade 𝑘 𝑘 e P é uma matriz 𝑘 𝑛 𝑘 que determina os 𝑛 𝑘 bits de paridade na palavra código 𝑐𝑖 de 𝑛 bits a partir dos 𝑘 bits da mensagem 𝑥𝑖 Por exemplo a matriz 𝐆 de Exemplo 1 no slide anterior está na forma sistemática dada por 7 e portanto o codebook do código sistemático 𝜽43 gerado por 𝐆 exibe palavras código 𝑐𝑖 tais que os 𝑘 bits mais à esquerda de cada 𝑐𝑖 são uma cópia da respectiva mensagem 𝑥𝑖 7 Mensagem 𝑥𝑖 Palavracódigo 𝑐𝑖 000 0000 001 0011 010 0101 011 0110 100 1001 101 1010 110 1100 111 1111 G 1 0 0 1 0 1 0 1 0 0 1 1 𝑐𝑖 𝑥𝑖𝐆 𝑏2 𝑏1 𝑏0 1 0 0 1 0 1 0 1 0 0 1 1 A Matriz Geradora de um Código 𝜽𝒏 𝒌 Dois códigos que diferem somente na ordem de suas palavrascódigo símbolos 𝑐𝑖 nos seus respectivos codebooks no Codificador de Canal no TX resultam no mesmo valor de BER bit error rate na saída do Decodificador de Canal do RX porque as distâncias de Hamming entre as palavrascódigo 𝑐𝑖 de seus respectivos codebooks são as mesmas Tais códigos são denominados equivalentes Lembrando aqui que os erros de bit nas mensagens 𝑥𝑖 decodificadas na saída do Decodificador de Canal no RX são decorrentes do nível de ruído aditivo no Canal de Transmissão e que excede a capacidade de correção de ambos os códigos resultando no valor de BER não nula Especificamente o código 𝜽𝒆𝒏 𝒌 é equivalente ao código 𝜽𝑛 𝑘 se a matriz geradora 𝐆𝒆 de 𝜽𝒆 𝒏 𝒌 puder ser obtida através da permutação de colunas da matriz 𝐆 geradora de 𝜽𝑛 𝑘 ou através de operações elementares realizadas entre as linhas de 𝐆 Uma operação elementar em GF2 entre duas linhas de uma matriz consiste em permutar as linhas ou em substituir uma linha pela soma dela com outra linha Assim sempre podemos transformar uma matriz 𝐆 qualquer para a forma sistemática 𝐆 através de operações elementares entre linhas ou permutações entre colunas mantendo a equivalência entre os respectivos códigos gerados ie mantendo a mesma robustez ao ruído aditivo Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 21 RX TX 𝑥𝑖 𝑐𝑖 𝑥𝑖 𝑐𝑖 A Matriz Geradora de um Código 𝜽𝒏 𝒌 Note que a implementação em hardware de um código sistemático é mais simples do que a de um código nãosistemático e por esta razão é sempre preferível trabalhar com códigos sistemáticos Exemplo 2 Dada a matriz geradora 𝐆 0 0 1 1 0 1 0 1 1 1 1 1 pedese a Transformar 𝐆 para a sua forma sistemática 𝐆 b Verifique comparativamente se 𝐆 gera um código equivalente ao código gerado por 𝐆 Solução a Visto que a matriz geradora é uma matriz 𝐆34 então o código gerado será um código 𝜽43 𝐆 pode ser obtida pelo seguinte conjunto de operações elementares feito sobre as linhas de 𝐆 A Matriz Geradora de um Código 𝜽𝒏 𝒌 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 22 𝐆 A Matriz Geradora de um Código 𝜽𝒏 𝒌 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 23 b O código gerado por 𝐆 é O código gerado por 𝐆 é o mesmo código especificado no codebook do Exemplo 1 no slide 19 Comparativamente note que as distâncias de Hamming entre as palavrascódigo 𝑐𝑖 dos códigos gerados por 𝐆 e 𝐆 são as mesmas A única diferença que se observa é na ordem de suas palavrascódigo símbolos 𝑐𝑖 nos seus respectivos codebooks Portanto ambos os códigos apresentam a mesma robustez ao ruído aditivo Conforme vimos nos slides anteriores a matriz geradora 𝐆 é usada no codificador de canal do TX para gerar o codebook de um código 𝜽𝑛 𝑘 que na grande maioria das situações práticas será um código sistemático A razão para isto é o fato de que a implementação em hardware de um código sistemático é mais simples do que a de um código nãosistemático No decodificador de canal do RX uma matriz 𝐇 denominada de matriz de paridade é utilizada para detectar erros de bits nas palavrascódigo 𝑐𝑖 recebidas A matriz de paridade 𝐇 do RX é determinada a partir da matriz geradora 𝐆 do TX conforme veremos a seguir Seja então um código 𝜽𝑛 𝑘 com matriz geradora 𝐆 dada na forma sistemática ver slide 20 𝑥𝑖 𝑎𝑖 𝐏 𝐈𝑛𝑘 0 Matriz de paridade transposta 𝐇𝑇 A Matriz de Paridade de um Código 𝜽𝒏 𝒌 Uma observação preliminar Anteriormente no Cap III estávamos adotando a notação 𝑐𝑖 𝑐𝑖0 𝑐𝑖1 𝑐𝑖 𝑛1 e 𝑥𝑖 𝑥𝑖0 𝑥𝑖1 𝑥𝑖𝑘1 para atender à representação matricial de 𝐆 ver equação 5 no slide 18 Mas de agora em diante vamos inverter a ordem dos índices na notação de 𝑐𝑖 e 𝑥𝑖 de modo que 𝑐𝑖0 e 𝑥𝑖0 representem o bit de ordem 0 ie o bit mais à direita em uma palavre binária conforme é usual em notação de hardwarever página 3 de httpswwwfccdecastrocombrpdfEDC5pdf e a página 15 de httpswwwfccdecastrocombrpdfEDC3pdf Seja então a 𝑖ésima palavracódigo do codebook de um código 𝜽𝑛 𝑘 sistemático dada por 𝑐𝑖 𝑐𝑖 𝑛1 𝑐𝑖 𝑛2 𝑐𝑖1𝑐𝑖0 a qual resulta da respectiva mensagem 𝑥𝑖 𝑥𝑖𝑘1𝑥𝑖𝑘2 𝑥𝑖1𝑥𝑖0 através da equação 3 ie através de 𝑐𝑖 𝑥𝑖𝐆 Dado que 𝜽𝑛 𝑘 é sistemático então sua matriz geradora 𝐆 é da forma sistemática conforme equação 7A acima e portanto a palavracódigo 𝑐𝑖 pode ser decomposta em 𝑐𝑖 𝑥𝑖 𝑎𝑖 onde 𝑎𝑖 𝑥𝑖𝐏 é um vetorlinha que contém os 𝒏 𝒌 bits de paridade da palavracódigo 𝒄𝒊 Visto que 𝑎𝑖 𝑥𝑖𝐏 e considerando que a soma em GF2 é uma operação módulo 2 ie soma é XOR então podemos somar 𝑥𝑖𝐏 à esquerda e à direita de 𝑎𝑖 𝑥𝑖𝐏 resultando em 7A 8 que pode ser escrita matricialmente conforme 9 abaixo definindo algebricamente a matriz de paridade 𝐇 𝑥𝑖𝐏 𝑎𝑖 𝑥𝑖𝐏 𝑥𝑖𝐏 𝑥𝑖𝐏 𝑎𝑖 0 9 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 24 𝐆 𝐈𝑘 𝐏 A equação 12 𝑐𝑖𝐇𝑇 0 estabelece que cada palavracódigo 𝑐𝑖 do código 𝜽𝑛 𝑘 é ortogonal a cada linha da matriz 𝐇 Isto decorre do fato de que se dois vetores 𝑢 e 𝑣 são ortogonais então o produto escalar 𝑢 𝑣𝑇 resulta nulo ie 𝑢 𝑣𝑇 0 ver httpsenwikipediaorgwikiDotproduct Deste modo a equação 12 permite detectar se a palavra código 𝑐𝑖 recebida na entrada do Decodificador de Canal do RX apresenta algum bit recebido em erro em consequência da degradação de sinal imposta pelo ruído aditivo do canal de transmissão Ou seja se 𝑐𝑖𝐇𝑇 0 então 𝑐𝑖 foi recebida sem erro em seus bits e se 𝑐𝑖𝐇𝑇 0 então 𝑐𝑖 foi recebida com algum bit em erro Especificamente seja 𝑐𝑖 a palavracódigo transmitida e 𝑦𝑖 a palavracódigo recebida Se 𝑦𝑖𝐇𝑇 0 então 𝑦𝑖 𝑐𝑖 e portanto 𝑦𝑖 apresenta pelo menos um bit recebido em erro Se 𝑦𝑖𝐇𝑇 0 então 𝑦𝑖 𝑐𝑖 e portanto 𝑦𝑖 não apresenta bits recebidos em erros Por este motivo 𝐇𝑛𝑘𝑛 é denominada de matriz de paridade 𝑐𝑖 𝐇𝑇 A Matriz de Paridade de um Código 𝜽𝒏 𝒌 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 25 Da equação 9 no slide anterior obtemos então a definição para a matriz de paridade 𝐇 𝐇 𝐇𝑇𝑇 𝐏 𝐈𝑛𝑘 𝑇 𝐏𝑇 𝐈𝑛𝑘 𝑇 𝐏𝑇 𝐈𝑛𝑘 𝐇 𝐏𝑇 𝐈𝑛𝑘 10 11 Note em 11 que 𝐇 é uma matriz de 𝑛 𝑘 𝑛 bits Da equação 9 no slide anterior temos ainda que 𝑥𝑖 𝑎𝑖 𝐏 𝐈𝑛𝑘 0 𝑐𝑖𝐇𝑇 0 12 Solução a A matriz geradora 𝐆 de 𝜽43 na forma sistemática é ver solução do item a do Exemplo 2 no slide 22 b Verificando se GH𝑇 0 A Matriz de Paridade de um Código 𝜽𝒏 𝒌 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 26 Exemplo 3 Considere a matriz geradora 𝐆 0 0 1 1 0 1 0 1 1 1 1 1 do Exemplo 2 no slide 22 Pedese a Determine a matriz de paridade H do código 𝜽43 do Exemplo 2 b Verifique se 𝐆𝐇𝑇 0 c Verifique se 𝑐𝑖𝐇𝑇 0 verificado Note que 𝐇 é uma matriz de 𝑛 𝑘 𝑛 bits com 𝑛 4 e 𝑘 3 c Verificando se 𝑐𝑖H𝑇0 onde o conjunto de palavrascódigo 𝑐𝑖 está explicitado na solução do item b do Exemplo 2 no slide 23 A Matriz de Paridade de um Código 𝜽𝒏 𝒌 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 27 verificado Decodificação pela Mínima Distância MLD MaximumLikelihood Decoding Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 28 Uma técnica de decodificação conceitualmente simples mas de custo computacional significativo é o MaximumLikelihood Decoding MLD conforme já discutido no slide 8 do Cap I No RX a palavracódigo recebida 𝑦𝑖 de 𝑛 bits é recebida na entrada do decodificador MLD do código 𝜽𝑛 𝑘 adotado no TX O codebook do código 𝜽𝑛 𝑘 é formado por 𝑀 2𝑘 possíveis palavrascódigo 𝑐𝑗 𝑗 0 1 𝑀 1 sendo 𝑘 o número de bits em cada mensagem 𝑥𝑗 associada através do codebook à respectiva palavra código 𝑐𝑗 de 𝑛 bits Daí o decodificador MLD no RX compara 𝑦𝑖 recebida com as 𝑀 2𝑘 possíveis palavrascódigo 𝑐𝑗 do codebook do código 𝜽 𝑛 𝑘 e decide em favor daquela palavracódigo 𝑐𝑗 portanto em favor da mensagem 𝑥𝑗 associada que é mais próxima da palavracódigo 𝑦𝑖 recebida proximidade que é medida através da distância de Hamming entre 𝑦𝑖 e 𝑐𝑗 Esta operação de decodificação efetuada pelo decodificador MLD no RX é expressa matematicamente através de 𝜃1 𝑦𝑖 arg min 𝑐𝑗 𝑦𝑖 𝑐𝑗 𝐻 13 onde a palavracódigo 𝑐𝑗 pertence ao conjunto 𝐂 de palavrascódigo do codebook ie 𝑐𝑗 𝐂 sendo 𝐂 𝑐𝑖 𝑐0 𝑐1 𝑐𝑀1 e onde 𝑦𝑖 𝑐𝑗 𝐻 denota a distância de Hamming entre a palavracódigo recebida 𝑦𝑖 e a palavracódigo 𝑐𝑗 do codebook ver discussão em vermelho no slide 11 do Cap II O problema da técnica de decodificação MLD discutida no slide anterior é a necessidade de calcular todas as 2𝑘 distâncias de Hamming 𝑦𝑖 𝑐𝑗 𝐻 p decodificar a palavracódigo 𝑦𝑖 recebida o que representa algum custo computacional Uma maneira mais eficiente de implementar um decodificador MLD mas aproveitando as propriedades da matriz de paridade 𝐇𝑛𝑘𝑛 de um código 𝜽𝑛 𝑘 é a técnica de decodificação denominada de Decodificação por Arranjo Padrão Standard Array Decoding ver httpsenwikipediaorgwikiStandardarray utilizando o conceito de síndrome httpsenwikipediaorgwikiDecodingmethodsSyndromedecoding Conforme veremos a seguir na decodificação por síndrome o número de distâncias de Hamming 𝑦𝑖 𝑐𝑗 𝐻 calculadas é reduzido de 2𝑘 para 2𝑛𝑘 lembrando que na prática usualmente 𝑛 𝑘 𝑘 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 29 Arranjo padrão e decodificação por síndrome Seja 𝑐𝑖 a palavracódigo do código 𝜽𝑛 𝑘 enviada pelo TX através do canal de transmissão e seja 𝑦𝑖 a palavracódigo recebida na entrada do decodificador do RX Devido ao ruído aditivo no canal de transmissão a palavracódigo 𝑦𝑖 recebida pode conter erros de modo que 𝑦𝑖 pode ser expressa por 𝑦𝑖 𝑐𝑖 𝑒𝑖 14 onde 𝑒𝑖 é o vetorlinha de 𝑛 bits que representa o Padrão de Erro ie os bits errados em 𝑦𝑖 resultante da degradação do sinal causada pelo ruído aditivo no canal Por exemplo seja 𝑐𝑖 0 1 0 1 a palavracódigo enviada pelo TX através do canal de transmissão e seja 𝑦𝑖 0 1 0 0 a palavracódigo recebida na entrada do decodificador do RX E daí de 14 padrão de erro é 𝑒𝑖 0 0 0 1 Note de 14 que se soubermos uma estimativa do valor 𝑒𝑖 e se somarmos em GF2 o valor 𝑒𝑖 a ambos os lados da equação obtemos a estimativa da palavracódigo 𝑐𝑑𝑒𝑐 transmitida pelo TX que é a palavracódigo decodificada O Peso do Padrão de Erro é a distância de Hamming entre e 𝑦𝑖 e 𝑐𝑖 ie é o número de bits em posições correspondentes de 𝑦𝑖 e 𝑐𝑖 que diferem entre si Portanto no exemplo do parágrafo anterior o Peso do Padrão de Erro é 1 porque em 𝑒𝑖 0 0 0 1 há somente um bit de valor 1 𝑦𝑖 𝑒𝑖 𝑐𝑖 𝑒𝑖 𝑒𝑖 𝑐𝑖 𝑐𝑑𝑒𝑐 15 Pósmultiplicando a equação 14 𝑦𝑖 𝑐𝑖 𝑒𝑖 por 𝐇𝑇 obtemos Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 30 Arranjo padrão e decodificação por síndrome 𝑦𝑖𝐇𝑇 𝑐𝑖 𝑒𝑖 𝐇𝑇 𝑐𝑖𝐇𝑇 𝑒𝑖𝐇𝑇 𝑒𝑖𝐇𝑇 0 ver equação 12 no slide 25 16 Da equação 16 definese a síndrome do padrão de erro ou simplesmente síndrome como o vetor 𝑠𝑖 originado a partir do padrão de erro 𝑒𝑖 decorrente da palavracódigo 𝑦𝑖 𝑐𝑖 𝑒𝑖 recebida na entrada do decodificador do RX vetor 𝑠𝑖 que é dado por 𝑠𝑖 𝑒𝑖𝐇𝑇 17 Note em 17 que a matriz de paridade 𝐇 é uma matriz de 𝑛 𝑘 𝑛 bits 𝑒𝑖 é um vetorlinha de 𝑛 bits e 𝑠𝑖 é um vetor linha de 𝑛 𝑘 bits É importante enfatizar que o conjunto de síndromes 𝐒 𝑠𝑖 é determinado apenas a partir do conjunto de padrões de erro 𝑒𝑖 e não pelo conjunto 𝐂 𝑐𝑖 de palavrascódigo transmitidas como podemos inferir de 𝑠𝑖 𝑦𝑖𝐇𝑇 𝑒𝑖𝐇𝑇 Observe ainda que 𝑒𝑖 é um vetorlinha de 𝑛 bits então existem 2𝑛 possíveis padrões de erro no conjunto 𝑒𝑖 𝑠𝑖 é um vetorlinha de 𝑛 𝑘 bits então existem 2𝑛𝑘 possíveis síndromes no conjunto 𝐒 Como existem menos síndromes 𝑠𝑖 do que padrões de erro 𝑒𝑖 a consequência é que 𝑠𝑖 𝑒𝑖𝐇𝑇 mapeia diferentes padrões de erro 𝐞𝐢 na mesma síndrome 𝒔𝒊 O mapeamento do padrão de erro 𝑒𝑖 em uma síndrome 𝑠𝑖 através da equação 17 𝑠𝑖 𝑒𝑖𝐇𝑇 resulta na Tabela de Síndromes com 2𝑛𝑘 síndromes Por exemplo abaixo é mostrada a Tabela de Síndromes para um código 𝜽52 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 31 Arranjo padrão e decodificação por síndrome O processo de decodificação por síndrome da palavracódigo recebida 𝑦𝑖 é constituído das seguintes etapas I Determinar a síndrome 𝑠𝑖 a partir da palavracódigo recebida 𝑦𝑖 através da equação 16 𝑠𝑖 𝑦𝑖𝐇𝑇 𝑒𝑖𝐇𝑇 II Identificar o padrão de erro 𝑒𝑖 associado à síndrome 𝑠𝑖 obtida em I consultando a Tabela de Síndromes para o código 𝜽𝑛 𝑘 A Tabela de Síndromes é determinada previamente e uma única vez sendo única para cada código 𝜽𝑛 𝑘 III Determinar a palavracódigo decodificada 𝑐𝑑𝑒𝑐 através da equação 15 𝑐𝑑𝑒𝑐 𝑦𝑖 𝑒𝑖 onde 𝑒𝑖 foi obtido em II IV Determinar a estimativa da mensagem transmitida 𝑥𝑑𝑒𝑐 Para códigos sistemáticos a mensagem 𝑥𝑑𝑒𝑐 corresponde aos primeiros bits da palavracódigo 𝑐𝑑𝑒𝑐 obtida em III Deste modo para obter 𝑥𝑑𝑒𝑐 basta descartar os 𝑛 𝑘 bits de paridade de 𝑐𝑑𝑒𝑐 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 32 Arranjo padrão e decodificação por síndrome Assim como a Tabela de Síndromes ver slide 31 o Arranjo Padrão AP é também uma tabela que possui 2𝑛𝑘 linhas respectivas às 2𝑛𝑘 possíveis síndromes de um código 𝜃 𝑛 𝑘 conforme mostrado na tabela abaixo O número de colunas do AP é 2𝑘 correspondendo ao número de palavrascódigo 𝑐𝑖 no codebook do código 𝜃 𝑛 𝑘 Para efeito de construção de um AP a linha superior do AP recebe a designação L0 e a coluna mais à esquerda recebe a designação C0 O AP é formado de 2𝑛𝑘 2𝑘 2𝑛 células ie 2𝑛 possíveis padrões de erro ver slide 29 Forma geral do Arranjo Padrão AP para um código 𝜃 𝑛 𝑘 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 33 Arranjo padrão e decodificação por síndrome AP p 𝜃 𝑛 𝑘 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 34 Arranjo padrão e decodificação por síndrome AP p 𝜃 𝑛 𝑘 Na linha L0 do AP são listadas da esquerda para a direita as 2𝑘 palavrascódigo 𝑐𝑖 do codebook de 𝜽 𝑛 𝑘 cada uma delas representada por um vetor de 𝑛 bits definido por 𝑐𝑖 𝑐𝑖 𝑛1 𝑐𝑖 𝑛2 𝑐𝑖1𝑐𝑖0 A palavracódigo 𝑐 0 pertencente à célula identificada pela intersecção da coluna C0 com a linha L0 célula L0 C0 obrigatoriamente deve ser aquela representada pelo vetor 0 Na coluna C0 abaixo da palavracódigo 0 são listados de alto a baixo os 2𝑛𝑘 1 padrões de erro relativos à palavra código 𝑐0 0 Primeiramente são listados na coluna C0 todos os 𝑛 padrões de erro de peso 1 isto é todos os padrões de erro que resultam de uma Distância de Hamming unitária entre a palavracódigo 𝑦 recebida e 𝑐0 0 Se 2𝑛𝑘 𝑛 então listase a seguir em C0 todos os possíveis padrões de erro de peso 2 Em seguida listase em C0 todos os possíveis padrões de erro de peso 3 e assim sucessivamente até que todas as 2𝑛𝑘 células de C0 estejam preenchidas Neste contexto 𝑒0 𝑐0 0 representa o padrão de erro de peso 0 isto é representa a nãoocorrência de erro Nota Visto que cada linha do AP necessita corresponder a uma única síndrome dentre as 2𝑛𝑘possíveis síndromes devemos ter o cuidado de na construção de C0 assegurar que distintos padrões de erro de peso maior que 1 em C0 correspondam a síndromes que são distintas entre si e que são simultaneamente distintas daquelas síndromes que correspondem a padrões de erro de peso 1 conforme veremos no Exemplo 4 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 35 Arranjo padrão e decodificação por síndrome AP p 𝜃 𝑛 𝑘 Dando prosseguimento à construção do AP somase o padrão de erro contido na 𝑖ésima célula de C0 à palavracódigo na célula L𝑖 C1 e colocase o resultado da soma na 𝑖ésima célula em C1 com 𝑖 01 2𝑛𝑘 1 A seguir somase o padrão de erro contido na 𝑖ésima célula de C0 à palavracódigo na célula L𝑖 C2 e colocase o resultado da soma na 𝑖ésima célula em C2 com 𝑖 01 2𝑛𝑘 1 E assim fazse sucessivamente até completar a última coluna C 2𝑘 1 mais à direita no AP Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 36 Arranjo padrão e decodificação por síndrome AP p 𝜃 𝑛 𝑘 Exemplo 4 Seja o Codificador de Canal no TX de um sistema de comunicação digital que utiliza o código de bloco 𝜽 𝑛 𝑘 gerado pela matriz geradora G abaixo especificada Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 37 Arranjo padrão e decodificação por síndrome Pedese a Construa um possível AP para este código 𝜽 𝑛 𝑘 e a Tabela de Síndromes associada visando o posterior projeto do decodificador no RX b Suponha que o TX digital envie a palavracódigo 𝑐 1 0 1 0 1 através do canal de transmissão O ruído aditivo do canal degrada o sinal de forma que o demodulador no RX entrega para o decodificador a palavracódigo 𝑦 1 1 1 0 1 erro no bit 𝑏3 considerando aqui a representação 𝑏4 𝑏3 𝑏2 𝑏1𝑏0 Verifique a capacidade do decodificador em detectar e corrigir este erro c Suponha que o ruídointerferência no canal seja intenso de forma que o demodulador no RX entrega para o decodificador a palavracódigo 𝑦 1 1 1 1 1 erro nos bits 𝑏1 e 𝑏3 Verifique a capacidade do decodificador em detectar e corrigir este erro duplo Solução a A matriz geradora G não necessita ser transformada por permutação de colunas ou por operações elementares em linhas visto que já encontrase na forma sistemática isto é Visto que 𝐆𝑘𝑛 dada no enunciado é uma matriz de dimensões 𝐆25 então o código em questão é 𝜽52 e portanto 𝑛 5 e 𝑘 2 𝑐0 0 0 𝐆 0 0 0 0 0 𝑐1 0 1 𝐆 0 1 0 1 1 𝑐2 1 0 𝐆 1 0 1 0 1 𝑐3 1 1 𝐆 1 1 1 1 0 As 2𝑘 22 4 palavrascódigo 𝑐𝑖 do código 𝜽52 gerado por G são obtidas da equação 3 𝑐𝑖 𝑥𝑖𝐆 do slide 17 e resultam conforme codebook ao lado 𝑥𝑖 𝑐𝑖 Conforme discussão nos slides 32 a 35 para determinar os padrões de erro da coluna C0 do AP precisamos verificar quais as síndromes resultantes dos 𝑛 5 padrões de erro de peso 1 para que não ocorra igualdade com as síndromes resultantes dos padrões de erro de peso maior que 1 Os padrões de erro 𝑒𝑖 de peso 1 para este código 𝜽52 são 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 e 1 0 0 0 0 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 38 Arranjo padrão e decodificação por síndrome Da matriz geradora 𝐆 dada no enunciado que já está na forma sistemática 𝐆 𝐈𝑘 𝐏 conforme equação 7A do slide 24 e da equação 11 do slide 25 obtemos a matriz de paridade 𝐇 para este código 𝜽52 As síndromes 𝑠𝑖 resultantes dos padrões de erro de peso 1 são portanto 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 Obviamente a síndrome resultante do padrão de erro de peso 0 inexistência de erro é 0 0 0 0 0 𝐇𝑇 0 0 0 O mapeamento destes padrões de erro 𝑒𝑖 de peso 1 nas respectivas síndromes 𝑠𝑖 é obtido através da equação 17 𝑠𝑖 𝑒𝑖𝐇𝑇 no slide 30 e resulta na Tabela de Síndromes ao lado Conforme slide 33 o AP a ser construído possui 2𝑛𝑘 252 8 linhas correspondentes às 2𝑛𝑘 síndromes Já determinamos no slide anterior 𝑛 1 6 síndromes padrões de erro de peso 0 e peso 1 Ainda faltam determinar 2𝑛𝑘 𝑛 1 8 5 1 2 síndromes Estas 2 síndromes faltantes devem obrigatoriamente ser distintas entre si e distintas das 𝑛 1 6 síndromes já determinadas ver nota no slide 35 Note que os 2 padrões de erro que resultam respectivamente nestas 2 síndromes 1 1 0 e 1 1 1 devem ser padrões de erro de peso 𝟐 visto que já esgotamos os possíveis padrões de erro de peso 0 e de peso 1 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 39 Arranjo padrão e decodificação por síndrome Tendo esta condição em mente verificase na Tabela de Síndromes ao lado que as síndromes faltantes são 1 1 0 e 1 1 1 Neste contexto se expressarmos o padrão de erro por 𝑒𝑖 𝑏4 𝑏3 𝑏2 𝑏1𝑏0 onde 𝑏𝑖 representa a ordem do bit e da equação 17 𝑠𝑖 𝑒𝑖𝐇𝑇 do slide 30 temos então para a síndrome 𝑠𝑖 1 1 0 18 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 40 Arranjo padrão e decodificação por síndrome 18 A equação matricial 18 resulta no seguinte sistema de equações em GF2 19 onde 𝑏 representa a negação do valor lógico do bit b Um possível padrão de erro de peso 2 que obedece às equações 19 acima é 𝑒𝑖 1 1 0 0 0 Portanto este será o padrão de erro que associaremos à síndrome 𝑠𝑖 1 1 0 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 41 Arranjo padrão e decodificação por síndrome De mesma forma expressando o padrão de erro por 𝑒𝑖 𝑏4 𝑏3 𝑏2 𝑏1𝑏0 onde 𝑏𝑖 representa a ordem do bit da equação 17 𝑠𝑖 𝑒𝑖𝐇𝑇 do slide 30 temos para a síndrome 𝑠𝑖 1 1 1 20 A equação matricial 20 resulta no seguinte sistema de equações em GF2 21 Um possível padrão de erro de peso 2 distinto do anterior que obedece às equações 21 acima é 𝑒𝑖 1 0 0 1 0 Portanto este será o padrão de erro que associaremos à síndrome 𝑠𝑖 1 1 1 De posse destes resultados e conforme discussão nos slides 32 a 35 o AP é construído como Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 42 Arranjo padrão e decodificação por síndrome E a Tabela de Síndromes completa para implementação do decodificador de canal no RX resulta em Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 43 Arranjo padrão e decodificação por síndrome b Da equação 16 𝑠𝑖 𝑦𝑖𝐇𝑇 𝑒𝑖𝐇𝑇 do slide 30 e dada a palavracódigo recebida 𝑦𝑖 1 1 1 0 1 obtemos 𝑟 𝑦𝑖𝐇𝑇 0 1 1 onde 𝑟 é a síndrome da palavracódigo recebida 𝑦𝑖 1 1 1 0 1 Calculando as 2𝑛𝑘 252 8 distâncias de Hamming 𝑟 𝑠𝑖 𝐻 na Tabela de Síndromes no slide 43 verificase que 𝑟 𝑠𝑖 𝐻 0 para 𝑠𝑖 0 1 1 e que o padrão de erro correspondente é 𝑒𝑖 0 1 0 0 0 Da equação 15 do slide 29 obtemos a palavracódigo decodificada 𝑐𝑑𝑒𝑐 e do codebook do slide 37 obtemos a correspondente mensagem 𝑥𝑑𝑒𝑐 𝑐𝑑𝑒𝑐 𝑦𝑖 𝑒𝑖 1 0 1 0 1 𝑥𝑑𝑒𝑐 1 0 Portanto para este caso o decodificador detectou e corrigiu o erro Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 44 Arranjo padrão e decodificação por síndrome Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 45 Arranjo padrão e decodificação por síndrome c Da equação 16 𝑠𝑖 𝑦𝑖𝐇𝑇 𝑒𝑖𝐇𝑇 do slide 30 e dada a palavracódigo recebida 𝑦𝑖 1 1 1 1 1 obtemos 𝑟 𝑦𝑖𝐇𝑇 0 0 1 onde 𝑟 é a síndrome da palavracódigo recebida 𝑦𝑖 1 1 1 1 1 Calculando as 2𝑛𝑘 252 8 distâncias de Hamming 𝑟 𝑠𝑖 𝐻 na Tabela de Síndromes no slide 43 verificase que 𝑟 𝑠𝑖 𝐻 0 para 𝑠𝑖 0 0 1 e que o padrão de erro correspondente é 𝑒𝑖 0 0 0 0 1 Da equação 15 do slide 29 obtemos a palavracódigo decodificada 𝑐𝑑𝑒𝑐 e do codebook do slide 37 obtemos a correspondente mensagem 𝑥𝑑𝑒𝑐 𝑐𝑑𝑒𝑐 𝑦𝑖 𝑒𝑖 1 1 1 1 0 𝑥𝑑𝑒𝑐 1 1 Portanto para este caso o decodificador detectou o erro mas não corrigiu o erro A impossibilidade deste código 𝜽52 corrigir todos os padrões de erro com peso maior que 1 pode ser também verificada bastando consultar a coluna C0 do AP no slide 42 Por inspeção da coluna C0 concluise que este código corrige todos os 5 padrões de erro de peso 1 possíveis e somente 2 padrões de erro de peso 2 quais sejam 𝑒𝑖 1 1 0 0 0 e 𝑒𝑖 1 0 0 1 0 Em geral o projetista do código escolhe os padrões de erro de peso 𝑤 que corrigem 𝑤 erros com base em alguma peculiaridade do sistema digital Neste Exemplo 4 o número total de padrões de erro de peso 2 é dado pela combinação de 𝑛 5 bits tomados de 𝑚 2 a 𝑚 isto é 𝐶𝑜𝑚𝑏𝑛 𝑚 𝐶𝑜𝑚𝑏52 10 onde 𝐶𝑜𝑚𝑏𝑛 𝑚 𝑛 𝑚 𝑛 𝑚 No entanto na construção do AP foi possível utilizar apenas 2 deles 𝑒𝑖 1 1 0 0 0 e 𝑒𝑖 1 0 0 1 0 O projetista do código escolheu então este padrões de erro de peso 2 que corrigem 2 erros simultâneos porque nestas posições de bits está armazenada informação binária que dependem uma da outra e que são cruciais para o desempenho do sistema digital Por exemplo o bit de controle do tipo de criptografia DES AES e o bit de controle de quantos bits 128 256 são usados na criptografia Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 46 Arranjo padrão e decodificação por síndrome Videoaula Codificação de Canal Decodificação por Arranjo Padrão 13 Profa Cristina De Castro Videoaula Codificação de Canal Decodificação por Arranjo Padrão 23 Profa Cristina De Castro Videoaula Codificação de Canal Decodificação por Arranjo Padrão 33 Profa Cristina De Castro Nos links abaixo encontrase disponível uma videoaula c a revisão passo a passo da solução deste exemplo Exemplo 4 slide 37 Principais Códigos de Blocos Binários Códigos de Hadamard Códigos de Hadamard são códigos 𝜽𝑛 𝑘 𝜽2𝑘 𝑘 caracterizados por 𝑑min 𝑛2 Em geral os Códigos de Hadamard apresentam baixa razão de codificação 𝑅𝐶 Τ 𝑘 𝑛 Τ 𝜏𝑠 𝜏𝑥 𝑘2𝑘 onde 𝜏𝑠 representa a largura duração no tempo dos bits em uma palavracódigo e 𝜏𝑥 representa a largura dos bits na respectiva mensagem ver slide 9 Portanto como Τ 𝜏𝑠 𝜏𝑥 é pequeno o uso de um Código de Hadamard implica em um considerável aumento na largura do espectro do sinal transmitido no canal de transmissão e por isso não é muito utilizado exceto em sistemas spread spectrum que será estudado em Sistemas de Comunicação Digital II Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 47 Ver httpsenwikipediaorgwikiHadamardcode A matriz geradora de um Código de Hadamard 𝜽𝑛 𝑘 𝜽2𝑘 𝑘 caracterizase pelas suas 𝑛 2𝑘 colunas serem formadas por todos os vetores distintos 𝑘 dimensionais em GF2 Por exemplo abaixo é mostrado a matriz geradora de um Código de Hadamard para 𝑘 3 ie 𝜽 𝑛 𝑘 𝜽 2𝑘 𝑘 𝜽 83 𝐆 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 2 3 4 5 6 7 valor decimal do número binário armazenado na respectiva coluna de 𝐆 O Código de Golay apresenta as seguintes características Capacidade de correção de até 𝑡 𝑑𝑚𝑖𝑛1 2 71 2 3 erros de bit simultâneos Capacidade de detecção de até 𝑑 𝑑𝑚𝑖𝑛 1 7 1 6 erros de bit simultâneos O Código de Golay é um código peculiar porque ele é o único código conhecido de 23 bits capaz de corrigir até 3 erros de bit simultâneos O Código de Golay é usado nas missões da NASA no deep space como por exemplo nas missões Voyager 1 e Voyager 2 Ver httpsenwikipediaorgwikiBinaryGolaycode Principais Códigos de Blocos Binários Código de Golay Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 48 O Código de Golay é um código 𝜽𝑛 𝑘 𝜽2312 com 𝑑min 7 A matriz geradora 𝐆𝑘𝑛 𝐆1223 é conforme abaixo 𝐆1223 1 0 Principais Códigos de Blocos Binários Códigos de Hamming Códigos de Hamming são códigos 𝜽𝑛 𝑘 𝜽2𝑚 1 2𝑚 1 𝑚 largamente utilizados pela facilidade de construção aliada a uma distância mínima 𝑑min 3 detecta até 2 erros simultâneos e corrige até 1 erro sendo 𝑚 𝑛 𝑘 um inteiro positivo Por exemplo se 𝑚 3 obtemos um Código de Hamming 𝜽74 A construção de um código de bloco 𝛉𝑛 𝑘 consiste em definir a sua matriz de paridade 𝐇 𝑛𝑘 𝑛 e a partir da definição de 𝐇 𝑛𝑘 𝑛 determinar a sua matriz geradora 𝐆𝑘𝑛 com base nas equações 7 e 11 ie 𝐆𝑘𝑛 𝐈𝑘 𝐏 e 𝐇𝑛𝑘𝑛 𝐏𝑇 𝐈𝑛𝑘 É uma propriedade de um Código de Hamming 𝛉2𝑚 12𝑚 1 𝑚 que a sua matriz de paridade 𝐇 𝑛𝑘 𝑛 caracterizase pelas suas 𝑛 2𝑚 1 colunas serem formadas por todos os vetores distintos 𝑚 dimensionais em GF2 exceto o vetor 0 Por exemplo um código 𝛉31 é um Código de Hamming com 𝑚 2 em que a matriz 𝐇 é formada pelos 𝑛 3 vetores colunas 0 1T 1 0T 1 1T conforme abaixo Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 49 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 50 Exemplo 5 O Codificador de Canal de um TX digital adota um Código de Hamming 𝜽𝑛 𝑘 em que as mensagens recebidas do Codificador de Fonte são palavras binárias de 𝑘 4 bits Pedese a Determine a matriz geradora 𝐆 deste código b Quantos erros de bit simultâneos este código é capaz de corrigir Solução a Conforme slide anterior para 𝑘 4 temos que 𝑘 4 2𝑚 1 𝑚 e resolvendo esta equação para a incógnita 𝑚 obtemos 𝑚 3 E daí 𝑛 2𝑚 1 7 e portanto este Código de Hamming é 𝜽 𝑛 𝑘 𝜽 7 4 Conforme visto no slide anterior a matriz de paridade 𝐇 𝑛𝑘 𝑛 de um Código de Hamming 𝛉2𝑚 12𝑚 1 𝑚 caracterizase pelas suas 𝑛 2𝑚 1 colunas serem formadas por todos os vetores distintos 𝑚 dimensionais em GF2 exceto o vetor 0 Temos então Principais Códigos de Blocos Binários Códigos de Hamming 𝐇 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 𝐇 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 𝐇𝑛𝑘𝑛 𝐏𝑇 𝐈𝑛𝑘 𝐆𝑘𝑛 𝐈𝑘 𝐏 permutação de colunas p converter 𝐇 p a forma sistemática 𝐈𝑛𝑘 𝐏𝑇 𝐆 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1 𝐈𝑘 𝐏 1 2 3 4 5 6 7 valor decimal do número binário armazenado na respectiva coluna de 𝐇 A partir de 𝐇 na forma sistemática obtemos b Todos os Códigos de Hamming têm 𝑑min 3 Assim da equação 2 no slide 16 temos 𝑡 𝑑𝑚𝑖𝑛 1 2 3 1 2 1 Principais Códigos de Blocos Códigos ReedSolomon Códigos ReedSolomon constituem uma subclasse de uma ampla classe de códigos cíclicos denominada de Códigos BCH Bose Chaudhuri Hocquenghem ver httpsenwikipediaorgwikiReedE28093Solomonerrorcorrection Os códigos ReedSolomon RS encontramse entre os códigos com alta capacidade de correção de erro sendo largamente utilizados em muitos sistemas digitais como Dispositivos de armazenamento Fita MagnéticaCDs DVD códigos de barra etc Comunicações Móveis e wireless Telefonia celular links de microondas etc Comunicações via Satélite Televisão Digital Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 51 Vimos em slides anteriores que um código de bloco binário 𝜃𝑛 𝑘 codifica mensagens de 𝑘 bits em palavrascódigo de 𝑛 bits podendo corrigir até 𝑡 𝑑min1 2 bits errados Um Código ReedSolomon 𝜃𝑛 𝑘 representado por 𝐑𝐒𝑛 𝑘 codifica mensagens de 𝑘 símbolos em palavrascódigo de 𝑛 símbolos sendo capaz de corrigir até 𝑡 𝑛𝑘 2 símbolos errados Cada símbolo em uma palavracódigo ou em uma mensagem de um código 𝐑𝐒𝑛 𝑘 é um bloco de 𝒎 bits Daí portanto o poder de correção de erro de um código 𝐑𝐒𝑛 𝑘 Mesmo que todos os 𝑚 bits de cada um dos 𝑡 símbolos recebidos estejam errados o código 𝐑𝐒𝑛 𝑘 efetua a correção não importando a localização dos símbolos na palavra código Ainda não importando o número e a posição dos bits errados em cada símbolo o código 𝐑𝐒𝑛 𝑘 corrigirá até 𝑡 símbolos e caso o número de símbolos errados ultrapassar 𝑡 o código 𝐑𝐒𝑛 𝑘 detectará esta situação No contexto do codificador de canal de um sistema de comunicações digitais esta característica é extremamente vantajosa porque permite a correção de um surto de 𝑚 𝑡 bits sequenciais recebidos em erro error burst correction Se o número de erros ultrapassar 𝑡 então o código 𝐑𝐒𝑛 𝑘 avisa o sistema de que não foi capaz de corrigir todos os erros É de especial interesse o caso em que 𝑚 8 quando cada símbolo representa 1 byte Por exemplo consideremos um código 𝐑𝐒𝑛 𝑘 𝐑𝐒2016 com 𝑚 8 Suponhamos que queiramos codificar a mensagem de 𝑘 16 bytes ie 𝑘 16 símbolos abaixo especificada Este código 𝐑𝐒 2016 tem a capacidade de corrigir até 𝑡 𝑛𝑘 2 2016 2 2 símbolos 16 bits contíguos Principais Códigos de Blocos Códigos ReedSolomon Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 52 Observe que nenhum símbolo é maior do que 255 valor máximo decimal para 1 byte 𝑚 8 bits Observe também que as operações entre polinômios são todas executadas em GF2𝑚 𝐺𝐹28 GF256 Foge ao escopo deste texto o estudo da álgebra de polinômios em GF2𝑚 e portanto não nos aprofundaremos na teoria dos Códigos ReedSolomon O código 𝐑𝐒2016 adiciona 𝑛 𝑘 4 bytes símbolos de paridade e codifica a mensagem acima na palavracódigo em forma sistemática abaixo O exemplo acima é baseado no CODEC RS descrito em linguagem C no link ReedSolomon CODEC 24 KB c CODEC COder and DECcoder Códigos LDPC LowDensity ParityCheck Os códigos LowDensity ParityCheck LDPC são uma subcategoria dos códigos de bloco lineares e foram originalmente introduzidos por Gallager nos anos 1960 ver httpsenwikipediaorgwikiLowdensityparitycheckcode Códigos LDPC são códigos de bloco com matriz de paridade 𝑯 com muitos 0s e poucos 1s Códigos LDPC longos quando decodificados com o algoritmo SomaProduto SPA ver httpsenwikipediaorgwikiBeliefpropagation e ver seção 5 de httpswwwfccdecastrocombrpdfLDPCintropdf são capazes de atingir um desempenho muito próximo ao limite de Shannon Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 53 Além do excelente desempenho o processo de codificação e decodificação adotado pelos códigos LDPC é menos complexo quando comparado a uma outra classe de códigos cujo desempenho também aproximase do Limite de Shannon os denominados Turbo Códigos que discutiremos adiante A decodificação dos códigos LDPC é realizada através de um processo iterativo do tipo softdecision denominado message passing algorithm especificamente a subclasse belief propagation algorithm BPA onde as probabilidades de ocorrência dos bits das palavrascódigo são passadas entre o conjunto de nodos de validação CN check nodes e o conjunto de nodos de bits BN bit nodes representados por um Grafo de Tanner conforme mostrado ao lado ver APÊNDICE A no slide 92 Em cada rodada de iterações as probabilidades dos bits são passadas dos nodos BN p os nodos CN e dos nodos CN de volta aos nodos BN até que as probabilidades dos bits indiquem a convergência do processo iterativo O grafo de Tanner ao lado representa a equação 12 do slide 25 ie 𝑐𝑖𝐇𝑇 0 sendo 𝑐𝑖 correspondente à palavra binária aplicada ao nodo BN e o resultado da equação síndrome correspondente à palavra binária resultante nos nodos CN A diferença aqui é que as operações não são efetuadas no GF2 c o valor do bits mas sim em termos de softdecisions do BPA baseadas na probabilidade de ocorrência do valor do bit Neste link do GitHub httpsgithubcomtopicsldpc estão disponibilizados códigos fonte em C C Python e scripts Matlab p a implementação prática de códigos LDPC Um código convolucional é gerado pela combinação linear em GF das saídas de um shiftregister de K estágios A sequência de bits a ser codificada é aplicada na entrada do shiftregister e este executa a convolução em GF entre a sequência de entrada e a resposta ao impulso da máquina de estado state machine representada pelo shiftregister A saída da máquina de estado constitui portanto a sequência codificada Diferem dos códigos de bloco porque o mapeamento entradasaída do codificador não é dado por uma matriz geradora e sim dependente do estado da máquina Códigos Convolucionais Decodificador de Viterbi Exemplos de Codificadores Convolucionais Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 54 O no de estados da máquina de estado de um codificador convolucional é K sendo K o no de estágios do shiftregister No contexto de códigos convolucionais K 1 recebe o nome de constraint length A razão entre o no de entradas e o no de saídas da máquina de estados define a razão de codificação c R do codificador Codificador Convolucional com K 1 estágio 2 2 K estados e Rc Codificador Convolucional com K estágios K estados e Rc Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 55 Códigos Convolucionais Decodificador de Viterbi Um codificador Convolucional de 1 estágio 2 estados e Rc poderá apresentar por exemplo o seguinte mapeamenteo entradasaída Entrada Estado Saída 0 0 O1 1 0 10 0 1 11 1 1 00 Se o mapeamento entradasaída do codificador não é dado por uma matriz geradora e sim dependente do estado da máquina uma entrada 1 como no exemplo acima poderá ser mapeada em uma saída 10 mas também poderá ser mapeada em uma saída 00 Por que este codificador será utilizável Como uma máquina de estados construída a partir de um shiftregister apresenta um conjunto finito de transições permitidas entre estados quando a sequência a ser codificada é a ela submetida implicitamente ficarão restritas as transições da sequência codificada em sua saída Ou seja há um conjunto conhecido e finito de possíveis transições de estado Se o receptor conhecer a tabela de transições permitidas então os erros gerados por degradação do sinal no canal de comunicações poderão ser identificados e corrigidos por um Decodificador de Viterbi Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 56 Códigos Convolucionais Decodificador de Viterbi A Figura abaixo apresenta um codificador convolucional com 2 estágios e 4 estados e Rc A sequência de bits a ser codificada é representada por u e a saída do codificador é a sequência de bits v Visto que Rc para cada bit de u são gerados dois bits em v O estágio 0 D transfere o valor lógico em sua entrada para a sua saída imediatamente após a ocorrência da borda de descida do pulso de clock não representado na figura De forma idêntica opera o estágio 1 D Representando a saída do estágio 0 D por 0 D e representando a saída do estágio 1 D por 1 D então o par de bits D 1 D identifica um dos estados da máquina de estado Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 57 Códigos Convolucionais Decodificador de Viterbi Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 58 Códigos Convolucionais Decodificador de Viterbi Dada uma seqüência u a ser codificada 1 0 1 1 1 a saída v no codificador de um transmissor digital é enviada ao receptor através do canal de transmissão sendo recebida como uma sequência r A Tabela acima apresenta uma possível sequência u e a resultante sequência v para o codificador da Figura É mostrada também a trajetória do estado D à medida que u é codificada partindo inicialmente do estado 0 Se nenhuma degradação de sinal ocorreu no canal de transmissão r v Diagrama de transição de estados Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 59 Códigos Convolucionais Decodificador de Viterbi Exemplo de codificação p o codificador do slide anterior u 1 0 1 1 1 Datual 0 1 0 1 1 Dfuturo 1 0 1 1 1 v 11 10 11 01 01 r 11 10 11 11 01 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 60 Códigos Convolucionais Decodificador de Viterbi Diagrama de transição de estados Exemplo de codificação p o codificador do slide anterior u 1 0 1 1 1 Datual 0 1 0 1 1 Dfuturo 1 0 1 1 1 v 11 10 11 01 01 r 11 10 11 11 01 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 61 Códigos Convolucionais Decodificador de Viterbi 0 0 0 1 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 62 Códigos Convolucionais Decodificador de Viterbi Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 63 Códigos Convolucionais Decodificador de Viterbi Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 64 Códigos Convolucionais Decodificador de Viterbi Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 65 Códigos Convolucionais Decodificador de Viterbi Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 66 Códigos Convolucionais Decodificador de Viterbi 11 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 67 Códigos Convolucionais Decodificador de Viterbi A técnica de decodificação consiste em acumular em cada nó da treliça as Distâncias de Hamming entre a saída v do codificador e a sequência r recebida a cada instante i Se mais de um caminho chega a um nó matase aqueles de maior métrica maior distância acumulada caminhos marcados com x na Figura a seguir ficando apenas aquele de menor métrica denominado de caminho sobrevivente A métrica acumulada de cada caminho encontrase em negrito à direita de cada nó na Figura Métricas em vermelho representam ramos que incidem no nó por cima e métricas em azul representam ramos que incidem no nó por baixo já que no máximo 2 ramos incidem em um nó para este decodificador Métricas sublinhadas representam métricas de caminhos sobreviventes Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 68 Códigos Convolucionais Decodificador de Viterbi A técnica de decodificação consiste em acumular em cada nó da treliça as Distâncias de Hamming entre a saída v do codificador e a sequência r recebida a cada instante i Se mais de um caminho chega a um nó matase aqueles de maior métrica maior distância acumulada caminhos marcados com x na Figura a seguir ficando apenas aquele de menor métrica denominado de caminho sobrevivente A métrica acumulada de cada caminho encontrase em negrito à direita de cada nó na Figura Métricas em vermelho representam ramos que incidem no nó por cima e métricas em azul representam ramos que incidem no nó por baixo já que no máximo 2 ramos incidem em um nó para este decodificador Métricas sublinhadas representam métricas de caminhos sobreviventes Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 69 Códigos Convolucionais Decodificador de Viterbi A técnica de decodificação consiste em acumular em cada nó da treliça as Distâncias de Hamming entre a saída v do codificador e a sequência r recebida a cada instante i Se mais de um caminho chega a um nó matase aqueles de maior métrica maior distância acumulada caminhos marcados com x na Figura a seguir ficando apenas aquele de menor métrica denominado de caminho sobrevivente A métrica acumulada de cada caminho encontrase em negrito à direita de cada nó na Figura Métricas em vermelho representam ramos que incidem no nó por cima e métricas em azul representam ramos que incidem no nó por baixo já que no máximo 2 ramos incidem em um nó para este decodificador Métricas sublinhadas representam métricas de caminhos sobreviventes Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 70 Códigos Convolucionais Decodificador de Viterbi A técnica de decodificação consiste em acumular em cada nó da treliça as Distâncias de Hamming entre a saída v do codificador e a sequência r recebida a cada instante i Se mais de um caminho chega a um nó matase aqueles de maior métrica maior distância acumulada caminhos marcados com x na Figura a seguir ficando apenas aquele de menor métrica denominado de caminho sobrevivente A métrica acumulada de cada caminho encontrase em negrito à direita de cada nó na Figura Métricas em vermelho representam ramos que incidem no nó por cima e métricas em azul representam ramos que incidem no nó por baixo já que no máximo 2 ramos incidem em um nó para este decodificador Métricas sublinhadas representam métricas de caminhos sobreviventes Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 71 Códigos Convolucionais Decodificador de Viterbi A técnica de decodificação consiste em acumular em cada nó da treliça as Distâncias de Hamming entre a saída v do codificador e a sequência r recebida a cada instante i Se mais de um caminho chega a um nó matase aqueles de maior métrica maior distância acumulada caminhos marcados com x na Figura a seguir ficando apenas aquele de menor métrica denominado de caminho sobrevivente A métrica acumulada de cada caminho encontrase em negrito à direita de cada nó na Figura Métricas em vermelho representam ramos que incidem no nó por cima e métricas em azul representam ramos que incidem no nó por baixo já que no máximo 2 ramos incidem em um nó para este decodificador Métricas sublinhadas representam métricas de caminhos sobreviventes Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 72 Códigos Convolucionais Decodificador de Viterbi A técnica de decodificação consiste em acumular em cada nó da treliça as Distâncias de Hamming entre a saída v do codificador e a sequência r recebida a cada instante i Se mais de um caminho chega a um nó matase aqueles de maior métrica maior distância acumulada caminhos marcados com x na Figura a seguir ficando apenas aquele de menor métrica denominado de caminho sobrevivente A métrica acumulada de cada caminho encontrase em negrito à direita de cada nó na Figura Métricas em vermelho representam ramos que incidem no nó por cima e métricas em azul representam ramos que incidem no nó por baixo já que no máximo 2 ramos incidem em um nó para este decodificador Métricas sublinhadas representam métricas de caminhos sobreviventes Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 73 Códigos Convolucionais Decodificador de Viterbi A técnica de decodificação consiste em acumular em cada nó da treliça as Distâncias de Hamming entre a saída v do codificador e a sequência r recebida a cada instante i Se mais de um caminho chega a um nó matase aqueles de maior métrica maior distância acumulada caminhos marcados com x na Figura a seguir ficando apenas aquele de menor métrica denominado de caminho sobrevivente A métrica acumulada de cada caminho encontrase em negrito à direita de cada nó na Figura Métricas em vermelho representam ramos que incidem no nó por cima e métricas em azul representam ramos que incidem no nó por baixo já que no máximo 2 ramos incidem em um nó para este decodificador Métricas sublinhadas representam métricas de caminhos sobreviventes Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 74 Códigos Convolucionais Decodificador de Viterbi A técnica de decodificação consiste em acumular em cada nó da treliça as Distâncias de Hamming entre a saída v do codificador e a sequência r recebida a cada instante i Se mais de um caminho chega a um nó matase aqueles de maior métrica maior distância acumulada caminhos marcados com x na Figura a seguir ficando apenas aquele de menor métrica denominado de caminho sobrevivente A métrica acumulada de cada caminho encontrase em negrito à direita de cada nó na Figura Métricas em vermelho representam ramos que incidem no nó por cima e métricas em azul representam ramos que incidem no nó por baixo já que no máximo 2 ramos incidem em um nó para este decodificador Métricas sublinhadas representam métricas de caminhos sobreviventes Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 75 Códigos Convolucionais Decodificador de Viterbi A decodificação final é iniciada a partir do caminho sobrevivente de menor métrica acumulada identificando cada ramo sobrevivente da direita para a esquerda na treliça Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 76 Códigos Convolucionais Decodificador de Viterbi A decodificação final é iniciada a partir do caminho sobrevivente de menor métrica acumulada identificando cada ramo sobrevivente da direita para a esquerda na treliça Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 77 Códigos Convolucionais Decodificador de Viterbi A decodificação final é iniciada a partir do caminho sobrevivente de menor métrica acumulada identificando cada ramo sobrevivente da direita para a esquerda na treliça Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 78 Códigos Convolucionais Decodificador de Viterbi A decodificação final é iniciada a partir do caminho sobrevivente de menor métrica acumulada identificando cada ramo sobrevivente da direita para a esquerda na treliça Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 79 Códigos Convolucionais Decodificador de Viterbi A decodificação final é iniciada a partir do caminho sobrevivente de menor métrica acumulada identificando cada ramo sobrevivente da direita para a esquerda na treliça Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 80 Códigos Convolucionais Decodificador de Viterbi A decodificação final é iniciada a partir do caminho sobrevivente de menor métrica acumulada identificando cada ramo sobrevivente da direita para a esquerda na treliça Ao lermos o valor de u nos identificadores uv0v1 de cada ramo sobrevivente na Figura verificamos que a sequência originalmente transmitida foi u 10111 o que concorda com u originalmente transmitido Portanto o decodificador identificou e corrigiu o erro ocorrido Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 81 Códigos Convolucionais Decodificador de Viterbi u 1 0 1 1 1 Datual 0 1 0 1 1 Dfuturo 1 0 1 1 1 v 11 10 11 01 01 r 11 10 11 11 01 Diagrama de Transição de Estados Exemplo de codificação para o codificador da Figura Diagrama de Treliça do Decodificador de Viterbi Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 82 Códigos Convolucionais Decodificador de Viterbi Nos links abaixo encontramse disponíveis duas videoaulas c a revisão passo a passo da solução deste exemplo Exemplo 1 slide 58 Videoaula Codificação de Canal Codificador Convolucional Profa Cristina De Castro Videoaula Codificação de Canal Decodificador de Viterbi Profa Cristina De Castro Exemplo 2 A Figura abaixo apresenta o diagrama de transição de estados do codificador convolucional da Figura ao lado Na Figura cada círculo representa um estado DD dentre os K possíveis estados O diagrama é construído a partir dos estados individuais considerando as transições permitidas a partir de cada estado como consequência do valor lógico de u Por exemplo suponhamos que a máquina de estado encontrese no estado 10 ie D e D na Figura acima Se u a saída resultante é v e após a borda de descida do clock a máquina vai para o estado 11 Se u a saída resultante é v e após a borda de descida do clock a máquina vai para o estado 01 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 83 Códigos Convolucionais Decodificador de Viterbi Dada uma seqüência u a ser codificada a saída v no codificador de um transmissor digital é enviada ao receptor através do canal de transmissão sendo recebida como uma sequência r Se nenhuma degradação de sinal ocorreu no canal de transmissão r v A Tabela a seguir mostra uma possível sequência u e a resultante sequência v para o codificador do Exemplo 2 É mostrada também a trajetória do estado DD à medida que u é codificada partindo inicialmente do estado 00 Assumindo que v seja enviado através de um canal de transmissão com ruídointerferência a Tabela apresenta uma possível sequência r recebida com 2 erros Codificação u 0 1 1 0 0 D0D1 atual 00 00 10 11 01 D0D1 futuro 00 10 11 01 00 v 00 11 10 10 11 r 01 11 11 10 11 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 84 Códigos Convolucionais Decodificador de Viterbi Diagrama de transição de estados do codificador convolucional No receptor digital o decodificador utiliza um algoritmo de decodificação baseado no princípio de mínima distância MLSE maximum likelihood sequence detector denominado Algoritmo de Viterbi Vamos decodificar a sequência r da Tabela através do Algoritmo de Viterbi para testar a capacidade de correção de erros do mesmo A Figura a seguir apresenta o diagrama de treliça utilizado pelo Decodificador de Viterbi adequado a este codificador convolucional Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 85 Códigos Convolucionais Decodificador de Viterbi O diagrama de treliça mostra todas as trajetórias caminhos das transições de estado da máquina de estado do codificador a cada instante i de codificação a partir do estado 00 Cada ramo da treliça começa e termina em um estado representando assim uma transição permitida Cada ramo é identificado por u vv isto é a saída v do codificador quando ao aplicarmos u em sua entrada a máquina de estado executa a transição representada pelo ramo em questão Diagrama de transição de estados do codificador convolucional Diagrama de Treliça do Decodificador de Viterbi para o codificador convolucional Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 86 Códigos Convolucionais Decodificador de Viterbi A técnica de decodificação consiste em acumular em cada nó da treliça as Distâncias de Hamming entre a saída v do codificador e a sequência r recebida a cada instante i Se mais de um caminho chega a um nó matase aqueles de maior métrica maior distância acumulada caminhos marcados com x na Figura ficando apenas aquele de menor métrica denominado de caminho sobrevivente A métrica acumulada de cada caminho encontrase em negrito à direita de cada nó na Figura Métricas sublinhadas representam métricas de caminhos sobreviventes Métricas em itálico representam ramos que incidem no nó por cima e métricas em nãoitálico representam ramos que incidem no nó por baixo já que no máximo 2 ramos incidem em um nó para este decodificador Diagrama de Treliça do Decodificador de Viterbi para o codificador convolucional Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 87 Códigos Convolucionais Decodificador de Viterbi A decodificação final é iniciada a partir do caminho sobrevivente de menor métrica acumulada identificando cada ramo sobrevivente da direita para a esquerda na treliça conforma mostra a Figura Ao lermos o valor de u nos identificadores u vv de cada ramo sobrevivente na Figura verificamos que a sequência originalmente transmitida foi u o que concorda com u mostrado na Tabela efetivamente transmitido Portanto o decodificador identificou e corrigiu os 2 erros Decodificando a sequência r Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 88 Códigos Convolucionais Decodificador de Viterbi Neste link do GitHub httpsgithubcomtopicsviterbialgorithmlc estão disponibilizados códigos fonte em linguagem C no âmbito da implementação prática de códigos convolucionais e decodificadores de Viterbi Neste link httpsgithubcomtopicsviterbidecoderlc2B2B estão disponibilizados códigos fonte em linguagem C E neste link httpsgithubcomtopicsviterbialgorithmlmatlab estão disponibilizados scripts Matlab sobre o mesmo tema Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 89 Turbo Códigos Turbo Códigos TCs foram propostos em 1993 por Berrou Glavieux e Thitimajashima que relataram excelentes resultados de ganho de codificação aproximandose do Limite de Shannon ver httpsenwikipediaorgwikiTurbocode A sequência de informação é codificada duas vezes com um interleaver ver httpsenwikipediaorgwikiBursterror correctingcodeInterleavedcodes entre os dois codificadores servindo para tornar as duas sequências de dados codificadas aproximadamente estatisticamente independentes uma da outra conforme mostrado em A abaixo A Turbo encoder Usualmente o turbo encoder encoder codificador utiliza codificadores convolucionais sistemáticos recursivos RSC Recursive Systematic Convolutional com razão de codificação ½ ver slide 9 ie para cada bit de entrada na entrada do codificador RSC resultam dois bits de saída conforme mostrado em B Cada codificador RSC Component Code 1 e Component Code 2 em A acima produz em sua saída um stream de bits sistemáticos que é equivalente ao stream de bits de informação em sua entrada e seguidos dos bits de paridade acrescidos pelo codificador Puncturing é então aplicado aos bits de paridade em cada um dos dois streams ver httpsenwikipediaorgwikiPuncturedcode de modo a aumentar a razão de codificação de cada codificador Os dois streams são então multiplexados e transmitidos B RSC encoder O excelente desempenho de TCs é devido à ação do interleaver que indiretamente aumenta a duração da sequência de bits de paridade aumentando a capacidade de correção quanto maior o comprimento do interleaver melhor o desempenho do TC Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 90 Turbo Códigos A Turbo decoder No decodificador são usados dois decoders RSC Component Decoder conforme mostrado em A O stream de entrada de cada decoder não são os bits em si mas sim a probabilidade de ocorrência do valor do bit representação denominada de soft input Mesmo acontece para a saída do decoder denominada de soft output O valor em ponto flutuante de um soft input ou de um soft output fornece não apenas uma indicação se um determinado bit é 0 ou 1 mas também uma indicação que dá a probabilidade verossimilhança de que o bit tenha sido decodificado corretamente O decodificador turbo opera iterativamente Usualmente cada decodificador é um decodificador de Viterbi adaptado para soft inputs e soft outputs ver httpsenwikipediaorgwikiViterbialgorithmtextSoft20output20Viterbi20algorithm The20soft20outputtextSOVA Na 1ª iteração o 1º decodificador RSC resulta em uma sequência de soft outputs fornecendo uma estimativa da sequência de bits originalmente transmitidos baseado unicamente nas soft inputs provenientes do canal Ele também gera a saída extrínseca extrinsic output 1 A saída extrínseca para um determinado bit não é baseada na entrada do canal para aquele bit mas nas informações dos bits próximos na sequência e nos condicionantes impostos pelo código que está sendo usado Esta saída extrínseca do 1º decodificador é usada pelo 2º decodificador RSC como informação apriori e esta informação junto com os soft inputs do canal são usados pelo 2º decodificador RSC para gerar a sua soft output e a extrinsic output 2 extrinsic output 1 extrinsic output 2 apriori info apriori info 1 2 Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 91 Turbo Códigos Na 2ª iteração a informação extrínseca do 2º decodificador obtida na 1ª iteração é usada como a informação apriori para o 1º decodificador e usando esta informação apriori o 1º decodificador decodifica mais bits corretamente do que na 1ª iteração Este ciclo continua sendo que em cada iteração ambos os decodificadores RSC produzem um soft output e uma extrinsic output baseadas no soft input do canal e baseada na informação a priori obtida da extrinsic output do decodificador anterior Após cada iteração a taxa de erro de bits BER na sequência decodificada reduz mas a taxa de redução na BER vai diminuindo a medida que o número de iterações aumenta de modo que por razões de complexidade geralmente apenas entre 4 e 12 iterações são usadas Uma descrição detalhada da operação do decodificador mostrado em A é encontrada na seção 53 Turbo Decoder na página 110 de httpswwwfccdecastrocombrpdfTCTESTCpdf A Turbo decoder extrinsic output 1 extrinsic output 2 apriori info apriori info 1 2 𝑏4 𝑏3 𝑏2 𝑏1 𝑏0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 𝑠2 𝑠1 𝑠0 𝑏4 𝑏2 𝑠2 𝑏3 𝑏1 𝑠1 𝑏4 𝑏3 𝑏0 𝑠0 𝑐𝑖𝐇𝑇 𝑠𝑖 𝑏4 𝑏3 𝑏2 𝑏1 𝑏0 𝑠2 𝑠1 𝑠0 APÊNDICE A Grafo de Tanner matriz de Paridade H e síndrome 𝑠𝑖 Grafo de Tanner resultante de H Sistemas de Comunicação Digital I Cap III Codificação de Canal Prof Fernando DeCastro 92