·
Engenharia Elétrica ·
Transmissão de Dados
· 2021/1
Send your question to AI and receive an answer instantly
Recommended for you
Preview text
2021-1 IF65F – Transmissão de Dados Prof. Eduardo Alves Hodgson hodgson@utfpr.edu.br Códigos Corretores de Erros UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ Câmpus Cornélio Procópio IF65F Transmissão de Dados 2 Tópicos ❑ Códigos de bloco lineares ❑ Códigos de Hamming ❑ Detecção e correção de erros de bit em códigos de bloco lineares ❑ Desempenho de códigos de Hamming em Bit Error Rate Com códigos corretores de erros, podemos reduzir uma probabilidade de erro de bit, por exemplo, 1 em cada 1000 bits (10−3) para 1 em cada 1 milhão de bits (10−6). IF65F Transmissão de Dados 3 Códigos Corretores de Erros Principais classes de códigos corretores de erro: ▪ Códigos de Bloco Lineares (Hamming 1950, Bell Labs) o Codificação e decodificação simples, por blocos de bits. ▪ Códigos Convolucionais (Viterbi 1967). o Muito empregado em comunicações sem fio (NASA, etc.). ▪ Códigos Turbo (1991, NASA, WiMAX, 3G/4G, 5G?). o Bem menos complexo que códigos convolucionais. ▪ Low density parity check, LDPC (1996, WiFi, DVB, 5G?). IF65F Transmissão de Dados 4 Códigos de Bloco Lineares • Um Código de Bloco codifica: ❑ um vetor de 𝑘 bits da fonte 𝐝 = [𝑑1, 𝑑2, … , 𝑑𝑘] em ❑ uma palavra código de 𝑛 bits 𝐜 = [𝑐1, 𝑐2, … , 𝑐𝑛], com 𝑛 > 𝑘. • A redundância é 𝑚 = (𝑛 − 𝑘) bits. • A taxa de código 𝑟 é: 𝑟 = 𝑘 𝑛 , 𝑟 ≤ 1 Introdução IF65F Transmissão de Dados 5 Códigos de Bloco Lineares • Um Código de Bloco codifica: ❑ um vetor de 𝑘 bits da fonte 𝐝 = [𝑑1, 𝑑2, … , 𝑑𝑘] em ❑ uma palavra código de 𝑛 bits 𝐜 = [𝑐1, 𝑐2, … , 𝑐𝑛], com 𝑛 > 𝑘. 𝐆 é a matriz geradora do código de bloco, codificando 𝐝 em 𝐜: 𝐜 = 𝐝𝐆 Codificação IF65F Transmissão de Dados 6 Códigos de Bloco Lineares • Um Código de Bloco codifica: ❑ um vetor de 𝑘 bits da fonte 𝐝 = [𝑑1, 𝑑2, … , 𝑑𝑘] em ❑ uma palavra código de 𝑛 bits 𝐜 = [𝑐1, 𝑐2, … , 𝑐𝑛], com 𝑛 > 𝑘. 𝐆 é a matriz geradora do código de bloco, codificando 𝐝 em 𝐜: 𝐜 = 𝐝𝐆 Ex: Um código de bloco 𝑛, 𝑘 = (6, 3) gera as seguintes palavras código: Codificação IF65F Transmissão de Dados 7 Códigos de Bloco Lineares A matriz 𝐆 abaixo é um código sistemático pois • os últimos 𝑘 = 3 bits (mais significativos) são iguais ao vetor de entrada 𝐝, obtido pela matriz identidade 𝐈𝐤 • os demais 𝑚 = 6 − 3 = 3 bits menos significativos são combinações lineares da entrada 𝐝, obtido pela matriz 𝐏. 𝐜 = 𝐝𝐆 = 𝐝[𝐏|𝐈k] Codificação IF65F Transmissão de Dados 8 Códigos de Bloco Lineares A matriz 𝐆 abaixo é um código sistemático pois • os últimos 𝑘 = 3 bits (mais significativos) são iguais ao vetor de entrada 𝐝, obtido pela matriz identidade 𝐈𝐤 • os demais 𝑚 = 6 − 3 = 3 bits menos significativos são combinações lineares da entrada 𝐝, obtido pela matriz 𝐏. 𝐜 = 𝐝𝐆 = 𝐝[𝐏|𝐈k] Codificação IF65F Transmissão de Dados 9 Códigos de Bloco Lineares >> d = [1 1 1] %bits que serão codificados >> G=[1 0 1 1 0 0; 0 1 1 0 1 0; 1 1 0 0 0 1] G = 1 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 >> c=d*G %soma binária não fica correta (1+1->0) c = 2 2 2 1 1 1 Implementação em Matlab – forma errada IF65F Transmissão de Dados 10 Códigos de Bloco Lineares >> d = [1 1 1] %bits que serão codificados >> G=[1 0 1 1 0 0; 0 1 1 0 1 0; 1 1 0 0 0 1] G = 1 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 >> c=mod(d*G,2) %mod(x,2)=resto de divisão de x por 2 c = 0 0 0 1 1 1 Implementação em Matlab – forma correta IF65F Transmissão de Dados 11 Códigos de Bloco Lineares A palavra código 𝐜 é enviada em um canal e é perturbado por ruído, podendo ou não adicionar erros de bit, dado pelo vetor de erro ou padrão de erro 𝐞: 𝐫 = 𝐜 ⨁ 𝐞 Decodificação 𝐞 = 100000 𝐫 = 𝟎10101 Ƹ𝐜 = 𝟏10101 IF65F Transmissão de Dados 12 Códigos de Bloco Lineares A palavra código 𝐜 é enviada em um canal e é perturbado por ruído, podendo ou não adicionar erros de bit, dado pelo vetor de erro ou padrão de erro 𝐞: 𝐫 = 𝐜 ⨁ 𝐞 A decodificação consiste em multiplicar o vetor recebido 𝐫 pela matriz de verificação de paridade 𝐇T(T = transposto), para obter o vetor síndrome de erro 𝐬 = 𝐫 𝐇T onde 𝐇 = [𝐈𝑚|𝐏T] Decodificação IF65F Transmissão de Dados 13 Códigos de Bloco Lineares A palavra código 𝐜 é enviada em um canal e é perturbado por ruído, podendo ou não adicionar erros de bit, dado pelo vetor de erro ou padrão de erro 𝐞: 𝐫 = 𝐜 ⨁ 𝐞 A decodificação consiste em multiplicar o vetor recebido 𝐫 pela matriz de verificação de paridade 𝐇T(T = transposto), para obter o vetor síndrome de erro 𝐬 = 𝐫 𝐇T onde 𝐇 = [𝐈𝑚|𝐏T] Se 𝐬 for um vetor de zeros, não houve erro de bit. Isso acontece porque 𝐜𝑖𝐇T = 0 para todas palavras código 𝐜𝑖. Isso é uma propriedade deste tipo de código. Decodificação IF65F Transmissão de Dados 14 Códigos de Bloco Lineares Se 𝐬 não for um vetor de zeros, então existe um erro de bit. 𝐬 = 𝐫 𝐇T 𝐬 = 𝐜 ⨁ 𝐞 𝐇T = 𝐜𝐇T⨁ 𝐞𝐇T Como 𝐜𝑖𝐇T = 0, as síndromes de erro só dependem do vetor de erro: 𝐬 = 𝐞𝐇T Decodificação IF65F Transmissão de Dados 15 Códigos de Bloco Lineares Se 𝐬 não for um vetor de zeros, então existe um erro de bit. 𝐬 = 𝐫 𝐇T 𝐬 = 𝐜 ⨁ 𝐞 𝐇T = 𝐜𝐇T⨁ 𝐞𝐇T Como 𝐜𝑖𝐇T = 0, as síndromes de erro só dependem do vetor de erro: 𝐬 = 𝐞𝐇T Como existem 2𝑘 palavras código 𝐜, então existem também 2𝑘 vetores de erros 𝐞. A informação da síndrome 𝐬 não é suficiente para encontrar o exato valor de erro. Porém, ajuda a decidir qual o vetor mais provável. Vamos continuar a decodificação com um exemplo de código de Hamming a seguir. Decodificação IF65F Transmissão de Dados 16 Códigos de Bloco Lineares Parâmetros de códigos de blocos lineares: • A distância de Hamming 𝑑(𝐜1, 𝐜2) é o número de posições com elementos diferentes: 𝑑 1001𝟎𝟎, 1001𝟏𝟏 = 2 • O peso de Hamming 𝑤(𝐞) é o número de elementos diferentes de zero de um vetor: 𝑤 𝐞 = 𝑤 𝟏00𝟏00 = 2 • A distância mínima 𝑑𝑚𝑖𝑛 de um código de bloco é a menor distância de Hamming entre quaisquer dois vetores de código 𝐜. Importante informação sobre um código de bloco. Distância de Hamming IF65F Transmissão de Dados 17 Códigos de Bloco Lineares Parâmetros de códigos de blocos lineares: • A distância de Hamming 𝑑(𝐜1, 𝐜2) é o número de posições com elementos diferentes: 𝑑 1001𝟎𝟎, 1001𝟏𝟏 = 2 • O peso de Hamming 𝑤(𝐞) é o número de elementos diferentes de zero de um vetor: 𝑤 𝐞 = 𝑤 𝟏00𝟏00 = 2 • A distância mínima 𝑑𝑚𝑖𝑛 de um código de bloco é a menor distância de Hamming entre quaisquer dois vetores de código 𝐜. Importante informação sobre um código de bloco. Um código de bloco linear (𝑛, 𝑘) consegue corrigir todos os vetores de erro 𝐞 com peso 𝑤 𝐞 = 𝑡 ou menor se 𝑑𝑚𝑖𝑛 ≥ 2𝑡 + 1 𝑡 ≤ 1/2(𝑑𝑚𝑖𝑛 − 1) Distância de Hamming IF65F Transmissão de Dados 18 Códigos de Bloco Lineares Um código de bloco linear (𝑛, 𝑘) consegue corrigir todos os vetores de erro 𝐞 com peso 𝑤 𝐞 = 𝑡 ou menor se 𝑑𝑚𝑖𝑛 ≥ 2𝑡 + 1 𝑡 ≤ ( Τ 1 2)(𝑑𝑚𝑖𝑛 − 1) Ex.1: Um código de bloco linear (𝑛, 𝑘) que corrige 𝑡 = 1 bit precisa ter uma 𝑑𝑚𝑖𝑛 ≥ 2𝑡 + 1 = 3. Se houver 2 bits errados, este código já não consegue mais corrigir os erros. Distância de Hamming IF65F Transmissão de Dados 19 Códigos de Bloco Lineares Um código de bloco linear (𝑛, 𝑘) consegue corrigir todos os vetores de erro 𝐞 com peso 𝑤 𝐞 = 𝑡 ou menor se 𝑑𝑚𝑖𝑛 ≥ 2𝑡 + 1 𝑡 ≤ ( Τ 1 2)(𝑑𝑚𝑖𝑛 − 1) Ex.1: Um código de bloco linear (𝑛, 𝑘) que corrige 𝑡 = 1 bit precisa ter uma 𝑑𝑚𝑖𝑛 ≥ 2(1) + 1 = 3. Se houver 2 bits ou mais errados, este código já não consegue mais corrigir os erros. Ex.2: Um código de bloco linear (𝑛, 𝑘) que corrige 𝑡 = 2 ou menos bits precisa ter uma 𝑑𝑚𝑖𝑛 ≥ 2(2) + 1 = 5. Se houver 3 bits ou mais errados, este código já não consegue mais corrigir os erros. Distância de Hamming IF65F Transmissão de Dados 20 Tópicos ❑ Códigos de bloco lineares ❑ Códigos de Hamming ❑ Detecção e correção de erros de bit em códigos de bloco lineares ❑ Desempenho de códigos de Hamming em Bit Error Rate IF65F Transmissão de Dados 21 Códigos de Hamming Códigos de Hamming são uma família de códigos de bloco lineares. Códigos de Hamming possuem os seguintes parâmetros: • Tamanho do vetor código: 𝑛 = 2𝑚 − 1 • Número de bits da mensagem: 𝑘 = 2𝑚 − 𝑚 − 1 • Número de bits de paridade: 𝑚 = 𝑛 − 𝑘, onde 𝑚 ≥ 3 Definições e Exemplo 𝐞 = 100000 𝐫 = 𝟎10101 Ƹ𝐜 = 𝟏10101 IF65F Transmissão de Dados 22 Códigos de Hamming Códigos de Hamming são uma família de códigos de bloco lineares. Códigos de Hamming possuem os seguintes parâmetros: • Tamanho do vetor código: 𝑛 = 2𝑚 − 1 • Número de bits da mensagem: 𝑘 = 2𝑚 − 𝑚 − 1 • Número de bits de paridade: 𝑚 = 𝑛 − 𝑘, onde 𝑚 ≥ 3 Exemplo: Código de Hamming (7,4) com 𝑚 = 3 e seguintes matrizes geradora 𝐆 e de verificação de paridade 𝐇: Definições e Exemplo IF65F Transmissão de Dados 23 Códigos de Hamming Com 𝑘 = 4, há 24 = 16 palavras código distintas listadas abaixo Propriedade de um Código de Hamming: • A distância mínima é sempre 𝑑𝑚𝑖𝑛 = 3, independente de 𝑚. • Logo, códigos de Hamming sempre corrigem até 𝑡 ≤ہ ۂ (1/2)(𝑑𝑚𝑖𝑛 − 1) = 𝟏 bit de erro por palavra-código. Exemplo IF65F Transmissão de Dados 24 Códigos de Hamming Tabela com síndromes e padrões de erros de 1 bit obtida com 𝐬 = 𝐞𝐇T Passos para obter esta tabela: 1. Criamos a 2ª coluna de possíveis padrões de erro com erro 𝐞 de 1 bit. 2. Calculamos todas síndrome 𝐬 para cada erro 𝐞 da 2ª coluna na 1ª coluna. 3. Síndrome 000 significa que não há erro de bit, ou seja, 𝐞 = 0000000. Exemplo IF65F Transmissão de Dados 25 Tópicos ❑ Códigos de bloco lineares ❑ Códigos de Hamming ❑ Detecção e correção de erros de bit em códigos de bloco lineares ❑ Desempenho de códigos de Hamming em Bit Error Rate IF65F Transmissão de Dados 26 Códigos de Hamming Suponha que a palavra código 𝐜 = [1110010] seja enviada e o vetor recebido seja 𝐫 = [11𝟎0010] com erro no 3º bit, que se deseja identificar e corrigir. Exemplo 𝐞 = 100000 𝐜 = [1110010] Ƹ𝐜 = 𝟏10101 𝐫 = [11𝟎0010] 𝐞 = [0010000] 𝐝 = [0010] መ𝐝 = [0010] IF65F Transmissão de Dados 27 Códigos de Hamming Suponha que a palavra código 𝐜 = [1110010] seja enviada e o vetor recebido seja 𝐫 = [11𝟎0010] com erro no 3º bit, que se deseja identificar e corrigir. A síndrome calculada será: 𝐬 = 𝐫𝐇T = 1 1 0 0 0 1 0 × 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 = 0 0 1 • 𝐬 = [001] corresponde a 4ª linha da tabela de síndrome, ou seja, o vetor erro detectado pelo código é: ො𝐞 = 0010000 . Exemplo IF65F Transmissão de Dados 28 Códigos de Hamming Suponha que a palavra código 𝐜 = [1110010] seja enviada e o vetor recebido seja 𝐫 = [11𝟎0010] com erro no 3º bit, que se deseja identificar e corrigir. A síndrome calculada será: 𝐬 = 𝐫𝐇T = 1 1 0 0 0 1 0 × 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 = 0 0 1 • 𝐬 = [001] corresponde a 4ª linha da tabela de síndrome, ou seja, o vetor erro detectado pelo código é: ො𝐞 = 0010000 . • A correção do bit errado é realizada obtendo a palavra código Ƹ𝐜: Ƹ𝐜 = 𝐫 + ො𝐞 = 11𝟎0010 + 0010000 = 1110010 = 𝐜 • Por fim, com a palavra código Ƹ𝐜, obtemos o vetor መ𝐝 = [0010] a partir da tabela do código. Exemplo IF65F Transmissão de Dados 29 Códigos de Hamming Resumo da codificação e decodificação de um código de bloco linear já criado: 1. Codificação do vetor de dados: 𝐜 = 𝐝𝐆 = 𝐝 𝐏 𝐈k 2. Transmissão no canal ruidoso: 𝐫 = 𝐜 ⨁ 𝐞 3. Decodificação: obtenção da síndrome 𝐬 = 𝐫𝐇T 4. Estimação do erro ො𝐞 mais provável pela tabela de síndromes 5. Correção do vetor recebido Ƹ𝐜 = 𝐫 + ො𝐞 6. Com Ƹ𝐜 obtemos o vetor de dados estimados መ𝐝. Exemplo 𝐞 = 100000 𝐜 = [1110010] Ƹ𝐜 = 𝟏10101 𝐫 = [11𝟎0010] 𝐞 = [0010000] 𝐝 = [0010] መ𝐝 = [0010] IF65F Transmissão de Dados 30 Tópicos ❑ Códigos de bloco lineares ❑ Códigos de Hamming ❑ Detecção e correção de erros de bit em códigos de bloco lineares ❑ Desempenho de códigos de Hamming em Bit Error Rate IF65F Transmissão de Dados 31 Códigos de Hamming Bit Error Rate 2-PAM com códigos de Hamming (7,4) e 15,11 : Exemplo IF65F Transmissão de Dados 32 Para diminuir um Bit Error Rate de 10−3 (ponto A) para 10−4 existem duas opções. Exemplo Ponto C: utilizando códigos corretores de erro. Porém, com uma taxa de transmissão em bps 𝑛/𝑘 maior. Ponto B: aumentando a SNR em 1,5 dB. Códigos de Hamming IF65F Transmissão de Dados 33 Códigos de Hamming Bit Error Rate (2-PAM) com códigos de Hamming (7,4), 15,11 , 31,26 , (127,120) sem correção de 𝑬𝒃/𝑵𝟎 : Exemplo IF65F Transmissão de Dados 34 Códigos de Hamming Bit Error Rate (2-PAM) com códigos de Hamming (7,4), 15,11 , 31,26 , (127,120) com correção de 𝑬𝒃/𝑵𝟎: Exemplo O código (7,4) precisa enviar 7 símbolos no canal, ao invés de 4 do não codificado. Logo, gasta 7/4 mais potência que o não codificado (ex: gasta 7W ao invés de 4W). Portanto, o código (7,4) precisa somar um ganho de 𝐺 = 10 ∗ log10 7/4 = 2,43 dB em 𝐸𝑏/𝑁0 na hora de plotar o resultado, já que gasta mais potência. IF65F Transmissão de Dados 35 Códigos de Hamming Bit Error Rate (2-PAM) com códigos de Hamming (7,4), 15,11 , 31,26 , (127,120) com correção de 𝑬𝒃/𝑵𝟎: Exemplo O código (127,120) precisa enviar 127 símbolos no canal, ao invés de 120 do não codificado. Logo, gasta 127/120 mais potência que o não codificado. Portanto, o código (127,120) precisa somar um ganho de 𝐺 = 10 ∗ log10(127/120) = 0,246 dB em 𝐸𝑏/𝑁0 na hora de plotar o resultado, já que gasta mais potência. IF65F Transmissão de Dados 36 Códigos de Hamming Bit Error Rate (2-PAM) com códigos de Hamming (7,4), 15,11 , 31,26 , (127,120) com correção de 𝑬𝒃/𝑵𝟎: Exemplo IF65F Transmissão de Dados 37 Códigos de Hamming Bit Error Rate (2-PAM) com códigos de Hamming (7,4), 15,11 , 31,26 , (127,120) sem correção de 𝑬𝒃/𝑵𝟎: Exemplo O longo código (127,120) gasta bem menos potência que o código curto (7,4). Porém, o código de Hamming (127,120) corrige apenas 𝑡 = 1 bit em cada palavra código de 127 bits. Ou seja, ele corrige bits errados apenas quando a probabilidade de erro de bit é menor que 10−2 (1 bit errado em cada 100 bits). Se tiver 2 bits errados a cada 100, ele não consegue corrigir e gera mais bits errados. Por isso a curva fica pior. IF65F Transmissão de Dados 38 Códigos Cíclicos Códigos cíclicos são uma subclasse de códigos de bloco lineares: • Códigos de Hamming. • Códigos de máximo comprimento, com boas propriedades de auto correlação, com outras funções além de correção de erros (CDMA). • CRC: códigos de verificação cíclica de redundância, com função de apenas detectar erros de forma confiável. Ex: detecta um pacote de dados errado e pede para reenviar em TCP/IP. • BCH: códigos Bose-Chaudhuri-Hocquenghem, com flexibilidade em parâmetros como tamanho e taxa de código. • RS: códigos Reed-Solomon são uma subclasse de BCH não binários.
Send your question to AI and receive an answer instantly
Recommended for you
Preview text
2021-1 IF65F – Transmissão de Dados Prof. Eduardo Alves Hodgson hodgson@utfpr.edu.br Códigos Corretores de Erros UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ Câmpus Cornélio Procópio IF65F Transmissão de Dados 2 Tópicos ❑ Códigos de bloco lineares ❑ Códigos de Hamming ❑ Detecção e correção de erros de bit em códigos de bloco lineares ❑ Desempenho de códigos de Hamming em Bit Error Rate Com códigos corretores de erros, podemos reduzir uma probabilidade de erro de bit, por exemplo, 1 em cada 1000 bits (10−3) para 1 em cada 1 milhão de bits (10−6). IF65F Transmissão de Dados 3 Códigos Corretores de Erros Principais classes de códigos corretores de erro: ▪ Códigos de Bloco Lineares (Hamming 1950, Bell Labs) o Codificação e decodificação simples, por blocos de bits. ▪ Códigos Convolucionais (Viterbi 1967). o Muito empregado em comunicações sem fio (NASA, etc.). ▪ Códigos Turbo (1991, NASA, WiMAX, 3G/4G, 5G?). o Bem menos complexo que códigos convolucionais. ▪ Low density parity check, LDPC (1996, WiFi, DVB, 5G?). IF65F Transmissão de Dados 4 Códigos de Bloco Lineares • Um Código de Bloco codifica: ❑ um vetor de 𝑘 bits da fonte 𝐝 = [𝑑1, 𝑑2, … , 𝑑𝑘] em ❑ uma palavra código de 𝑛 bits 𝐜 = [𝑐1, 𝑐2, … , 𝑐𝑛], com 𝑛 > 𝑘. • A redundância é 𝑚 = (𝑛 − 𝑘) bits. • A taxa de código 𝑟 é: 𝑟 = 𝑘 𝑛 , 𝑟 ≤ 1 Introdução IF65F Transmissão de Dados 5 Códigos de Bloco Lineares • Um Código de Bloco codifica: ❑ um vetor de 𝑘 bits da fonte 𝐝 = [𝑑1, 𝑑2, … , 𝑑𝑘] em ❑ uma palavra código de 𝑛 bits 𝐜 = [𝑐1, 𝑐2, … , 𝑐𝑛], com 𝑛 > 𝑘. 𝐆 é a matriz geradora do código de bloco, codificando 𝐝 em 𝐜: 𝐜 = 𝐝𝐆 Codificação IF65F Transmissão de Dados 6 Códigos de Bloco Lineares • Um Código de Bloco codifica: ❑ um vetor de 𝑘 bits da fonte 𝐝 = [𝑑1, 𝑑2, … , 𝑑𝑘] em ❑ uma palavra código de 𝑛 bits 𝐜 = [𝑐1, 𝑐2, … , 𝑐𝑛], com 𝑛 > 𝑘. 𝐆 é a matriz geradora do código de bloco, codificando 𝐝 em 𝐜: 𝐜 = 𝐝𝐆 Ex: Um código de bloco 𝑛, 𝑘 = (6, 3) gera as seguintes palavras código: Codificação IF65F Transmissão de Dados 7 Códigos de Bloco Lineares A matriz 𝐆 abaixo é um código sistemático pois • os últimos 𝑘 = 3 bits (mais significativos) são iguais ao vetor de entrada 𝐝, obtido pela matriz identidade 𝐈𝐤 • os demais 𝑚 = 6 − 3 = 3 bits menos significativos são combinações lineares da entrada 𝐝, obtido pela matriz 𝐏. 𝐜 = 𝐝𝐆 = 𝐝[𝐏|𝐈k] Codificação IF65F Transmissão de Dados 8 Códigos de Bloco Lineares A matriz 𝐆 abaixo é um código sistemático pois • os últimos 𝑘 = 3 bits (mais significativos) são iguais ao vetor de entrada 𝐝, obtido pela matriz identidade 𝐈𝐤 • os demais 𝑚 = 6 − 3 = 3 bits menos significativos são combinações lineares da entrada 𝐝, obtido pela matriz 𝐏. 𝐜 = 𝐝𝐆 = 𝐝[𝐏|𝐈k] Codificação IF65F Transmissão de Dados 9 Códigos de Bloco Lineares >> d = [1 1 1] %bits que serão codificados >> G=[1 0 1 1 0 0; 0 1 1 0 1 0; 1 1 0 0 0 1] G = 1 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 >> c=d*G %soma binária não fica correta (1+1->0) c = 2 2 2 1 1 1 Implementação em Matlab – forma errada IF65F Transmissão de Dados 10 Códigos de Bloco Lineares >> d = [1 1 1] %bits que serão codificados >> G=[1 0 1 1 0 0; 0 1 1 0 1 0; 1 1 0 0 0 1] G = 1 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 >> c=mod(d*G,2) %mod(x,2)=resto de divisão de x por 2 c = 0 0 0 1 1 1 Implementação em Matlab – forma correta IF65F Transmissão de Dados 11 Códigos de Bloco Lineares A palavra código 𝐜 é enviada em um canal e é perturbado por ruído, podendo ou não adicionar erros de bit, dado pelo vetor de erro ou padrão de erro 𝐞: 𝐫 = 𝐜 ⨁ 𝐞 Decodificação 𝐞 = 100000 𝐫 = 𝟎10101 Ƹ𝐜 = 𝟏10101 IF65F Transmissão de Dados 12 Códigos de Bloco Lineares A palavra código 𝐜 é enviada em um canal e é perturbado por ruído, podendo ou não adicionar erros de bit, dado pelo vetor de erro ou padrão de erro 𝐞: 𝐫 = 𝐜 ⨁ 𝐞 A decodificação consiste em multiplicar o vetor recebido 𝐫 pela matriz de verificação de paridade 𝐇T(T = transposto), para obter o vetor síndrome de erro 𝐬 = 𝐫 𝐇T onde 𝐇 = [𝐈𝑚|𝐏T] Decodificação IF65F Transmissão de Dados 13 Códigos de Bloco Lineares A palavra código 𝐜 é enviada em um canal e é perturbado por ruído, podendo ou não adicionar erros de bit, dado pelo vetor de erro ou padrão de erro 𝐞: 𝐫 = 𝐜 ⨁ 𝐞 A decodificação consiste em multiplicar o vetor recebido 𝐫 pela matriz de verificação de paridade 𝐇T(T = transposto), para obter o vetor síndrome de erro 𝐬 = 𝐫 𝐇T onde 𝐇 = [𝐈𝑚|𝐏T] Se 𝐬 for um vetor de zeros, não houve erro de bit. Isso acontece porque 𝐜𝑖𝐇T = 0 para todas palavras código 𝐜𝑖. Isso é uma propriedade deste tipo de código. Decodificação IF65F Transmissão de Dados 14 Códigos de Bloco Lineares Se 𝐬 não for um vetor de zeros, então existe um erro de bit. 𝐬 = 𝐫 𝐇T 𝐬 = 𝐜 ⨁ 𝐞 𝐇T = 𝐜𝐇T⨁ 𝐞𝐇T Como 𝐜𝑖𝐇T = 0, as síndromes de erro só dependem do vetor de erro: 𝐬 = 𝐞𝐇T Decodificação IF65F Transmissão de Dados 15 Códigos de Bloco Lineares Se 𝐬 não for um vetor de zeros, então existe um erro de bit. 𝐬 = 𝐫 𝐇T 𝐬 = 𝐜 ⨁ 𝐞 𝐇T = 𝐜𝐇T⨁ 𝐞𝐇T Como 𝐜𝑖𝐇T = 0, as síndromes de erro só dependem do vetor de erro: 𝐬 = 𝐞𝐇T Como existem 2𝑘 palavras código 𝐜, então existem também 2𝑘 vetores de erros 𝐞. A informação da síndrome 𝐬 não é suficiente para encontrar o exato valor de erro. Porém, ajuda a decidir qual o vetor mais provável. Vamos continuar a decodificação com um exemplo de código de Hamming a seguir. Decodificação IF65F Transmissão de Dados 16 Códigos de Bloco Lineares Parâmetros de códigos de blocos lineares: • A distância de Hamming 𝑑(𝐜1, 𝐜2) é o número de posições com elementos diferentes: 𝑑 1001𝟎𝟎, 1001𝟏𝟏 = 2 • O peso de Hamming 𝑤(𝐞) é o número de elementos diferentes de zero de um vetor: 𝑤 𝐞 = 𝑤 𝟏00𝟏00 = 2 • A distância mínima 𝑑𝑚𝑖𝑛 de um código de bloco é a menor distância de Hamming entre quaisquer dois vetores de código 𝐜. Importante informação sobre um código de bloco. Distância de Hamming IF65F Transmissão de Dados 17 Códigos de Bloco Lineares Parâmetros de códigos de blocos lineares: • A distância de Hamming 𝑑(𝐜1, 𝐜2) é o número de posições com elementos diferentes: 𝑑 1001𝟎𝟎, 1001𝟏𝟏 = 2 • O peso de Hamming 𝑤(𝐞) é o número de elementos diferentes de zero de um vetor: 𝑤 𝐞 = 𝑤 𝟏00𝟏00 = 2 • A distância mínima 𝑑𝑚𝑖𝑛 de um código de bloco é a menor distância de Hamming entre quaisquer dois vetores de código 𝐜. Importante informação sobre um código de bloco. Um código de bloco linear (𝑛, 𝑘) consegue corrigir todos os vetores de erro 𝐞 com peso 𝑤 𝐞 = 𝑡 ou menor se 𝑑𝑚𝑖𝑛 ≥ 2𝑡 + 1 𝑡 ≤ 1/2(𝑑𝑚𝑖𝑛 − 1) Distância de Hamming IF65F Transmissão de Dados 18 Códigos de Bloco Lineares Um código de bloco linear (𝑛, 𝑘) consegue corrigir todos os vetores de erro 𝐞 com peso 𝑤 𝐞 = 𝑡 ou menor se 𝑑𝑚𝑖𝑛 ≥ 2𝑡 + 1 𝑡 ≤ ( Τ 1 2)(𝑑𝑚𝑖𝑛 − 1) Ex.1: Um código de bloco linear (𝑛, 𝑘) que corrige 𝑡 = 1 bit precisa ter uma 𝑑𝑚𝑖𝑛 ≥ 2𝑡 + 1 = 3. Se houver 2 bits errados, este código já não consegue mais corrigir os erros. Distância de Hamming IF65F Transmissão de Dados 19 Códigos de Bloco Lineares Um código de bloco linear (𝑛, 𝑘) consegue corrigir todos os vetores de erro 𝐞 com peso 𝑤 𝐞 = 𝑡 ou menor se 𝑑𝑚𝑖𝑛 ≥ 2𝑡 + 1 𝑡 ≤ ( Τ 1 2)(𝑑𝑚𝑖𝑛 − 1) Ex.1: Um código de bloco linear (𝑛, 𝑘) que corrige 𝑡 = 1 bit precisa ter uma 𝑑𝑚𝑖𝑛 ≥ 2(1) + 1 = 3. Se houver 2 bits ou mais errados, este código já não consegue mais corrigir os erros. Ex.2: Um código de bloco linear (𝑛, 𝑘) que corrige 𝑡 = 2 ou menos bits precisa ter uma 𝑑𝑚𝑖𝑛 ≥ 2(2) + 1 = 5. Se houver 3 bits ou mais errados, este código já não consegue mais corrigir os erros. Distância de Hamming IF65F Transmissão de Dados 20 Tópicos ❑ Códigos de bloco lineares ❑ Códigos de Hamming ❑ Detecção e correção de erros de bit em códigos de bloco lineares ❑ Desempenho de códigos de Hamming em Bit Error Rate IF65F Transmissão de Dados 21 Códigos de Hamming Códigos de Hamming são uma família de códigos de bloco lineares. Códigos de Hamming possuem os seguintes parâmetros: • Tamanho do vetor código: 𝑛 = 2𝑚 − 1 • Número de bits da mensagem: 𝑘 = 2𝑚 − 𝑚 − 1 • Número de bits de paridade: 𝑚 = 𝑛 − 𝑘, onde 𝑚 ≥ 3 Definições e Exemplo 𝐞 = 100000 𝐫 = 𝟎10101 Ƹ𝐜 = 𝟏10101 IF65F Transmissão de Dados 22 Códigos de Hamming Códigos de Hamming são uma família de códigos de bloco lineares. Códigos de Hamming possuem os seguintes parâmetros: • Tamanho do vetor código: 𝑛 = 2𝑚 − 1 • Número de bits da mensagem: 𝑘 = 2𝑚 − 𝑚 − 1 • Número de bits de paridade: 𝑚 = 𝑛 − 𝑘, onde 𝑚 ≥ 3 Exemplo: Código de Hamming (7,4) com 𝑚 = 3 e seguintes matrizes geradora 𝐆 e de verificação de paridade 𝐇: Definições e Exemplo IF65F Transmissão de Dados 23 Códigos de Hamming Com 𝑘 = 4, há 24 = 16 palavras código distintas listadas abaixo Propriedade de um Código de Hamming: • A distância mínima é sempre 𝑑𝑚𝑖𝑛 = 3, independente de 𝑚. • Logo, códigos de Hamming sempre corrigem até 𝑡 ≤ہ ۂ (1/2)(𝑑𝑚𝑖𝑛 − 1) = 𝟏 bit de erro por palavra-código. Exemplo IF65F Transmissão de Dados 24 Códigos de Hamming Tabela com síndromes e padrões de erros de 1 bit obtida com 𝐬 = 𝐞𝐇T Passos para obter esta tabela: 1. Criamos a 2ª coluna de possíveis padrões de erro com erro 𝐞 de 1 bit. 2. Calculamos todas síndrome 𝐬 para cada erro 𝐞 da 2ª coluna na 1ª coluna. 3. Síndrome 000 significa que não há erro de bit, ou seja, 𝐞 = 0000000. Exemplo IF65F Transmissão de Dados 25 Tópicos ❑ Códigos de bloco lineares ❑ Códigos de Hamming ❑ Detecção e correção de erros de bit em códigos de bloco lineares ❑ Desempenho de códigos de Hamming em Bit Error Rate IF65F Transmissão de Dados 26 Códigos de Hamming Suponha que a palavra código 𝐜 = [1110010] seja enviada e o vetor recebido seja 𝐫 = [11𝟎0010] com erro no 3º bit, que se deseja identificar e corrigir. Exemplo 𝐞 = 100000 𝐜 = [1110010] Ƹ𝐜 = 𝟏10101 𝐫 = [11𝟎0010] 𝐞 = [0010000] 𝐝 = [0010] መ𝐝 = [0010] IF65F Transmissão de Dados 27 Códigos de Hamming Suponha que a palavra código 𝐜 = [1110010] seja enviada e o vetor recebido seja 𝐫 = [11𝟎0010] com erro no 3º bit, que se deseja identificar e corrigir. A síndrome calculada será: 𝐬 = 𝐫𝐇T = 1 1 0 0 0 1 0 × 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 = 0 0 1 • 𝐬 = [001] corresponde a 4ª linha da tabela de síndrome, ou seja, o vetor erro detectado pelo código é: ො𝐞 = 0010000 . Exemplo IF65F Transmissão de Dados 28 Códigos de Hamming Suponha que a palavra código 𝐜 = [1110010] seja enviada e o vetor recebido seja 𝐫 = [11𝟎0010] com erro no 3º bit, que se deseja identificar e corrigir. A síndrome calculada será: 𝐬 = 𝐫𝐇T = 1 1 0 0 0 1 0 × 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 = 0 0 1 • 𝐬 = [001] corresponde a 4ª linha da tabela de síndrome, ou seja, o vetor erro detectado pelo código é: ො𝐞 = 0010000 . • A correção do bit errado é realizada obtendo a palavra código Ƹ𝐜: Ƹ𝐜 = 𝐫 + ො𝐞 = 11𝟎0010 + 0010000 = 1110010 = 𝐜 • Por fim, com a palavra código Ƹ𝐜, obtemos o vetor መ𝐝 = [0010] a partir da tabela do código. Exemplo IF65F Transmissão de Dados 29 Códigos de Hamming Resumo da codificação e decodificação de um código de bloco linear já criado: 1. Codificação do vetor de dados: 𝐜 = 𝐝𝐆 = 𝐝 𝐏 𝐈k 2. Transmissão no canal ruidoso: 𝐫 = 𝐜 ⨁ 𝐞 3. Decodificação: obtenção da síndrome 𝐬 = 𝐫𝐇T 4. Estimação do erro ො𝐞 mais provável pela tabela de síndromes 5. Correção do vetor recebido Ƹ𝐜 = 𝐫 + ො𝐞 6. Com Ƹ𝐜 obtemos o vetor de dados estimados መ𝐝. Exemplo 𝐞 = 100000 𝐜 = [1110010] Ƹ𝐜 = 𝟏10101 𝐫 = [11𝟎0010] 𝐞 = [0010000] 𝐝 = [0010] መ𝐝 = [0010] IF65F Transmissão de Dados 30 Tópicos ❑ Códigos de bloco lineares ❑ Códigos de Hamming ❑ Detecção e correção de erros de bit em códigos de bloco lineares ❑ Desempenho de códigos de Hamming em Bit Error Rate IF65F Transmissão de Dados 31 Códigos de Hamming Bit Error Rate 2-PAM com códigos de Hamming (7,4) e 15,11 : Exemplo IF65F Transmissão de Dados 32 Para diminuir um Bit Error Rate de 10−3 (ponto A) para 10−4 existem duas opções. Exemplo Ponto C: utilizando códigos corretores de erro. Porém, com uma taxa de transmissão em bps 𝑛/𝑘 maior. Ponto B: aumentando a SNR em 1,5 dB. Códigos de Hamming IF65F Transmissão de Dados 33 Códigos de Hamming Bit Error Rate (2-PAM) com códigos de Hamming (7,4), 15,11 , 31,26 , (127,120) sem correção de 𝑬𝒃/𝑵𝟎 : Exemplo IF65F Transmissão de Dados 34 Códigos de Hamming Bit Error Rate (2-PAM) com códigos de Hamming (7,4), 15,11 , 31,26 , (127,120) com correção de 𝑬𝒃/𝑵𝟎: Exemplo O código (7,4) precisa enviar 7 símbolos no canal, ao invés de 4 do não codificado. Logo, gasta 7/4 mais potência que o não codificado (ex: gasta 7W ao invés de 4W). Portanto, o código (7,4) precisa somar um ganho de 𝐺 = 10 ∗ log10 7/4 = 2,43 dB em 𝐸𝑏/𝑁0 na hora de plotar o resultado, já que gasta mais potência. IF65F Transmissão de Dados 35 Códigos de Hamming Bit Error Rate (2-PAM) com códigos de Hamming (7,4), 15,11 , 31,26 , (127,120) com correção de 𝑬𝒃/𝑵𝟎: Exemplo O código (127,120) precisa enviar 127 símbolos no canal, ao invés de 120 do não codificado. Logo, gasta 127/120 mais potência que o não codificado. Portanto, o código (127,120) precisa somar um ganho de 𝐺 = 10 ∗ log10(127/120) = 0,246 dB em 𝐸𝑏/𝑁0 na hora de plotar o resultado, já que gasta mais potência. IF65F Transmissão de Dados 36 Códigos de Hamming Bit Error Rate (2-PAM) com códigos de Hamming (7,4), 15,11 , 31,26 , (127,120) com correção de 𝑬𝒃/𝑵𝟎: Exemplo IF65F Transmissão de Dados 37 Códigos de Hamming Bit Error Rate (2-PAM) com códigos de Hamming (7,4), 15,11 , 31,26 , (127,120) sem correção de 𝑬𝒃/𝑵𝟎: Exemplo O longo código (127,120) gasta bem menos potência que o código curto (7,4). Porém, o código de Hamming (127,120) corrige apenas 𝑡 = 1 bit em cada palavra código de 127 bits. Ou seja, ele corrige bits errados apenas quando a probabilidade de erro de bit é menor que 10−2 (1 bit errado em cada 100 bits). Se tiver 2 bits errados a cada 100, ele não consegue corrigir e gera mais bits errados. Por isso a curva fica pior. IF65F Transmissão de Dados 38 Códigos Cíclicos Códigos cíclicos são uma subclasse de códigos de bloco lineares: • Códigos de Hamming. • Códigos de máximo comprimento, com boas propriedades de auto correlação, com outras funções além de correção de erros (CDMA). • CRC: códigos de verificação cíclica de redundância, com função de apenas detectar erros de forma confiável. Ex: detecta um pacote de dados errado e pede para reenviar em TCP/IP. • BCH: códigos Bose-Chaudhuri-Hocquenghem, com flexibilidade em parâmetros como tamanho e taxa de código. • RS: códigos Reed-Solomon são uma subclasse de BCH não binários.