CRC - Simulação da verificação cíclica de redundância (do inglês, CRC - Cyclic Redundancy) PDF

Preview

Summary

Simulação da verificação cíclica de redundância (do inglês, CRC - Cyclic Redundancy Check)...

Description

UNIVERSIDADE FEDERAL DE SANTA MARIA CENTRO DE TECNOLOGIA CURSO DE ENGENHARIA DE TELECOMUNICAÇÕES ELC1131 – REDES INDUSTRIAIS

Mário Sergio Viero Arigony

TOPOLOGIA DE REDES

Santa Maria 2020

INTRODUÇÃO A verificação cíclica de redundância (do inglês, CRC - Cyclic Redundancy Check) é um método de detecção de erros normalmente usada em redes digitais e dispositivos de armazenamento para detectar mudança acidental em cadeias de dados. Mensagens de dados entrando nesses sistemas recebem um pequeno anexo com um valor de verificação baseado no resto de divisão polinomial do seu conteúdo. No ato da recuperação do dado o cálculo é refeito e comparado com o valor gerado anteriormente. Se os valores não se mostrarem semelhantes podem ser aplicadas ações para correção de dados, evitando assim a corrupção de dados. CRC pode ser usada para correção de erros a partir de alguns métodos. O nome CRC vem da redundância do valor de verificação atrelado ao dado (A mensagem recebe um aumento em seu tamanho sem adicionar uma informação) e o algoritmo de validação é construído com laços de repetição cíclicos. A verificação cíclica de redundância é amplamente utilizada em dispositivos binários por ser de simples implementação, é matematicamente fácil de ser analisada e apresenta bons resultados na detecção de erros comuns em canais de transmissão causados por ruído. A função utilizada para gerar o valor de verificação possui tamanho fixo, e é utilizada igualmente como uma função hash.

Cálculo para a sequência binaria CRC ou Cyclic Redundancy Check é um método de detecção de alterações / erros acidentais no canal de comunicação. CRC usa gerador polinomial que está disponível tanto no lado do emissor quanto do receptor. Um polinômio gerador de exemplo tem a forma de 𝑥5 +𝑥4 +𝑥2 +𝑥+1. Este polinômio gerador representa a chave 110111. Lado do remetente (geração de dados codificados a partir de dados e polinômio do gerador (ou chave)): 1. Os dados binários são primeiro aumentados adicionando k-1 zeros no final dos dados 2. Use a divisão binária módulo-2 para dividir os dados binários pela chave e armazenar o restante da divisão. 3. Anexa o restante no final dos dados para formar os dados codificados e envia Lado do receptor (verifique se há erros introduzidos na transmissão) Executa a divisão módulo-2 novamente e se o resto for 0, então não há erros. O cálculo para o exemplo descrito acima dispõe logo abaixo: 𝐺(𝑥) =𝑥5 +𝑥 4 +𝑥2 +𝑥 +1 = 110111 𝑚=11110000 𝑋𝑛 𝑚(𝑥) = 1111000000000 1111000000000 ⌊110111 110111 1011000 010110 000000 101100 110111 110110 110111 000010 000000 000100 000000 001000 000000 010000 000000 10000 ⏟ ⏟ 10000 𝑠𝑒𝑞𝑢ê𝑛𝑐𝑖𝑎=11110000 𝑚𝑒𝑛𝑠𝑎𝑔𝑒𝑚

𝐶𝑅𝐶

Geração de CRC utilizand utilizando o o MATLAB Para geração da sequência CRC, o código em MATLAB dispõe-se logo abaixo:

%% Transmissor mensagem=[1 1 1 1 0 0 0 0];%mensagem polinomio=[1 1 0 1 1 1];%polinômio gerador [M N]=size(polinomio);%armazena o tamanho do vetor X_mx=[mensagem zeros(1,N-1)];%adiciona-se zeros a mensagem dado pelo grau do polinômio [q r]=deconv(X_mx,polinomio)%equivalente a divisão de polinômios r=abs(r)%retira-se o modulo dos valores for i=1:length(r) a=r(i);%para cada índice do vetor r if ( mod(a,2)==0)%usa-se a divisão de modulo 2 r(i)=0;%se a divisão resulta zero, componente do vetor e igual a 0 else r(i)=1;%se a divisão resulta diferente de zero, componente do vetor e igual a um 1 end end crc=r(length(mensagem)+1:end)% o crc é dado pelos N-1 índices do vetor r sequenciaCRC = bitor(X_mx,r)%adiciona-se o crc a mensagem

Para o exemplo calculado anteriormente temos a confirmação do resultado como segue: 𝐶𝑅𝐶 =10000 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑖𝑎𝐶𝑅𝐶=1111000010000 A verificação de erros pode ser observada realizando novamente a divisão, o código para o receptor dispõe-se logo abaixo: %% Receptor [q r]=deconv(sequenciaCRC,polinomio); r=abs(r); for i=1:length(r) a=r(i);%para cada índice do vetor r if ( mod(a,2)==0)%usa-se a divisão de modulo 2 r(i)=0;%se a divisão resulta zero, componente do vetor e igual a 0 else r(i)=1;%se a divisão resulta diferente de zero, componente do vetor e igual a um 1 end end erros = r(length(mensagem)+1:end)

sendo o resto da divisão igual a zero temos a confirmação de que não houveram erros. 𝑒𝑟𝑟𝑜𝑠=00000 CRC-4 𝐺(𝑥) =𝑥4 +𝑥 +1 = 10011 𝑚=11110000

%% Transmissor mensagem=[1 1 1 1 0 0 0 0];%mensagem polinomio=[1 0 0 1 1];%polinômio gerador [M N]=size(polinomio);%armazena o tamanho do vetor X_mx=[mensagem zeros(1,N-1)];%adiciona-se zeros a mensagem dado pelo grau do polinômio [q r]=deconv(X_mx,polinomio)%equivalente a divisão de polinômios r=abs(r)%retira-se o modulo dos valores for i=1:length(r) a=r(i);%para cada índice do vetor r

if ( mod(a,2)==0)%usa-se a divisão de modulo 2 r(i)=0;%se a divisão resulta zero, componente do vetor e igual a 0 else r(i)=1;%se a divisão resulta diferente de zero, componente do vetor e igual a um 1 end end crc=r(length(mensagem)+1:end)% o crc é dado pelos N-1 índices do vetor r sequenciaCRC = bitor(X_mx,r)%adiciona-se o crc a mensagem

𝐶𝑅𝐶 =0110 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑖𝑎𝐶𝑅𝐶 =111100000110

CRC-8 𝐺(𝑥) =𝑥8 +𝑥 2 +𝑥 +1 = 100000111 𝑚=11110000

%% Transmissor mensagem=[1 1 1 1 0 0 0 0];%mensagem polinomio=[1 0 0 0 0 0 1 1 1];%polinômio gerador [M N]=size(polinomio);%armazena o tamanho do vetor X_mx=[mensagem zeros(1,N-1)];%adiciona-se zeros a mensagem dado pelo grau do polinomio [q r]=deconv(X_mx,polinomio);%equivalente a divisão de polinômios r=abs(r);%retira-se o modulo dos valores for i=1:length(r) a=r(i);%para cada índice do vetor r if ( mod(a,2)==0)%usa-se a divisão de modulo 2 r(i)=0;%se a divisão resulta zero, componente do vetor e igual a 0 else r(i)=1;%se a divisão resulta diferente de zero, componente do vetor e igual a um 1 end end crc=r(length(mensagem)+1:end)% o crc é dado pelos N-1 índices do vetor r sequenciaCRC = bitor(X_mx,r) )%adiciona-se o crc a mensagem

𝐶𝑅𝐶 =11011110 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑖𝑎𝐶𝑅𝐶=1111000011011110 CRC-10 𝐺(𝑥) =𝑥10+𝑥9 +𝑥5 +𝑥 4 +𝑥 +1 = 11000110011 𝑚=11110000

%% Transmissor mensagem=[1 1 1 1 0 0 0 0];%mensagem polinomio=[1 1 0 0 0 1 1 0 0 1 1];%polinômio gerador [M N]=size(polinomio);%armazena o tamanho do vetor X_mx=[mensagem zeros(1,N-1)];%adiciona-se zeros a mensagem dado pelo grau do polinomio [q r]=deconv(X_mx,polinomio);%equivalente a divisão de polinômios r=abs(r);%retira-se o modulo dos valores for i=1:length(r) a=r(i);%para cada índice if ( mod(a,2)==0)%usa-se r(i)=0;%se a divisão else r(i)=1;%se a divisão igual a um 1

do vetor r a divisão de modulo 2 resulta zero, componente do vetor e igual a 0 resulta diferente de zero, componente do vetor e

end end crc=r(length(mensagem)+1:end)% o crc é dado pelos N-1 índices do vetor r sequenciaCRC = bitor(X_mx,r)%adiciona-se o crc a mensagem

𝐶𝑅𝐶 =0100011111 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑖𝑎𝐶𝑅𝐶 =111100000100011111 CRC-16 𝐺(𝑥) =𝑥16+𝑥12+𝑥5 +1 = 10001000000100001 𝑚=11110000

%% Transmissor mensagem=[1 1 1 1 0 0 0 0];%mensagem polinomio=[1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1];%polinômio gerador [M N]=size(polinomio);%armazena o tamanho do vetor X_mx=[mensagem zeros(1,N-1)];%adiciona-se zeros a mensagem dado pelo grau do polinomio [q r]=deconv(X_mx,polinomio);%equivalente a divisão de polinômios r=abs(r);%retira-se o modulo dos valores for i=1:length(r) a=r(i);%para cada índice do vetor r if ( mod(a,2)==0)%usa-se a divisão de modulo 2 r(i)=0;%se a divisão resulta zero, componente do vetor e igual a 0 else r(i)=1;%se a divisão resulta diferente de zero, componente do vetor e igual a um 1 end end crc=r(length(mensagem)+1:end)% o crc é dado pelos N-1 índices do vetor r sequenciaCRC = bitor(X_mx,r)%adiciona-se o crc a mensagem

𝐶𝑅𝐶 =1110111100011111 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑖𝑎𝐶𝑅𝐶=111100001110111100011111 CRC-32 𝐺(𝑥) =𝑥32+𝑥 26+𝑥23+𝑥 22+𝑥16+𝑥12+𝑥11+𝑥10+𝑥 8 +𝑥 7 +𝑥5 +𝑥 4 +𝑥 2 +𝑥 +1 =100000100110000010001110110110111 𝑚=11110000

%% Transmissor mensagem=[1 1 1 1 0 0 0 0];%mensagem polinomio=[1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1]; %polinômio gerador [M N]=size(polinomio);%armazena o tamanho do vetor X_mx=[mensagem zeros(1,N-1)];%adiciona-se zeros a mensagem dado pelo grau do polinômio [q r]=deconv(X_mx,polinomio);%equivalente a divisão de polinômios r=abs(r);%retira-se o modulo dos valores for i=1:length(r) a=r(i);%para cada índice if ( mod(a,2)==0)%usa-se r(i)=0;%se a divisão else r(i)=1;%se a divisão igual a um 1 end end

do vetor r a divisão de modulo 2 resulta zero, componente do vetor e igual a 0 resulta diferente de zero, componente do vetor e

crc=r(length(mensagem)+1:end)% o crc é dado pelos N-1 índices do vetor r sequenciaCRC = bitor(X_mx,r)%adiciona-se o crc a mensagem

𝐶𝑅𝐶 =10001001101110001111110100001001 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑖𝑎𝐶𝑅𝐶=1111000010001001101110001111110100001001...