Corrigindo erros: códigos de bloco

Sinal BPSK contaminado com ruído guassiano. Os códigos apresentam melhor desempenho quando a relação sinal ruído é maior que ~ 8dB.

Corrigir um erro na vida pode não ser nada fácil, mas corrigir um erro em uma comunicação digital pode ser relativamente simples. Quando um sinal passa por um canal de comunicação, em geral, ele sofre alguma distorção e adição de ruído. Isso faz com que o receptor cometa erros. Esses erros, sob certas condições, podem ser corrigidos pelo uso de um código corretor de erros. Um exemplo "trivial" de código é o código de repetição: para cada bit, são transmitidos k bits iguais (k ímpar). Assim, se a maioria dos bits recebidos for "1", o bit transmitido é '1". Um código um pouco mais sofisticado é o de Hamming (ver, por exemplo, aqui).

Codificação com Código de Bloco de Hamming.

A mensagem m com k bits é convertida em uma palavra codificada c com n bits, $n > k$. A inclusão desses bits adicionais é uma redundância controlada. Ela pode ser realizada usando-se uma matriz geradora G com a forma G = [P | I$_k$], sendo P uma matriz $k \times (n - k)$ de que gera os bits de paridade e I é uma matriz identidade de dimensão $k \times k$. Assim, c = mG (produto módulo 2, isto é 0+0=0, 0+1=1, 1+1=0).

A verificação da mensagem recebida, após passar pelo canal, é feita usando-se uma matriz de verificação de paridade H. Essa matriz H tem a forma H = [P$^t$ | I$_{n-k}$] e GH$^t$ = 0. Assim, se houver o erro de um bit na mensagem recebida, o cálculo da síndrome s = cH$^t \neq$ 0. Com a síndrome calculada, o erro pode ser corrigido.

Essa classe de códigos tem a propriedade $(n,k) = (2^m-1,  2^m-1-m)$, como por exemplo o código (7,4) - $m = 3$, mas possível se construir códigos que não respeitam estritamente essa propriedade.

Obs: se a taxa de erro for elevada, é provável que o código corretor de erros acabe inserindo ainda mais erros e piorando ainda mais a taxa de erro.

******************

***********

***

O código Scilab abaixo foi usado para gerar o gráfico que abre essa postagem.

function trocax()
af=gca();
if af.log_flags = "nnn" then af.log_flags = "nln"
else af.log_flags = "nnn";
    end;
endfunction

function x=somab(vb)
    x=0;
    pt2=1;
    tam=max(size(vb))
    for k=1:tam
        x = x + vb(k)*pt2;
        pt2=pt2*2;
    end
endfunction

clc;

//// codigo 3+4: 4/7  (Rc = 4/7)
P1 = [0 1 1
      1 0 1
      1 1 0
      1 1 1];
Im = eye(4,4);
G1 = [P1, Im];

Ik = eye(3,3);
H1 = [Ik, P1'];
   
m = [1 0 1 1];
mG = pmodulo(m*G1,2);
ss = pmodulo(m*G1*H1',2);

// mG com um erro:
sd1 = zeros(7,3);
for k=0:7
    e = zeros(1,7);
    if k>0 then e(k)=1; end;
    mGe = pmodulo(mG + e,2);
    sd1(k+1,:) = pmodulo(mGe*H1',2);
    // disp([k, sd1(k+1,:), somab(sd1(k+1,:))]);
end;

//// codigo 4+7: 7/11  (Rc = 7/11)
P3 = [1 0 1 0
      1 1 1 0
      0 1 1 1
      1 1 0 1
      1 0 0 1
      0 1 0 1
      1 1 0 0];
Im = eye(7,7);
G3 = [P3, Im];

Ik = eye(4,4);
H3 = [Ik, P3'];
   
m = [1 0 1 0 1 1 1];
mG = pmodulo(m*G3,2)
ss = pmodulo(m*G3*H3',2)

// mG com um erro:
sd3 = zeros(11,4);
for k=0:11
    e = zeros(1,11);
    if k>0 then e(k)=1; end;
    mGe = pmodulo(mG + e,2);
    sd3(k+1,:) = pmodulo(mGe*H3',2);
  //  disp([k, sd3(k+1,:), somab(sd3(k+1,:))]);
end;

//// codigo 4+8: 8/12  (Rc = 2/3)
P4 = [0 0 1 1
      0 1 0 1
      0 1 1 0
      1 0 1 0
      1 1 0 0
      1 1 0 1
      1 1 1 0
      1 1 1 1];
Im = eye(8,8);
G4 = [P4, Im];

Ik = eye(4,4);
H4 = [Ik, P4'];
   
m = [1 0 1 0 1 0 1 1];
mG = pmodulo(m*G4,2)
ss4 = pmodulo(m*G4*H4',2)

// mG com um erro:
sd4 = zeros(12,4);
for k=0:12
    e = zeros(1,12);
    if k>0 then e(k)=1; end;
    mGe = pmodulo(mG + e,2);
    sd4(k+1,:) = pmodulo(mGe*H4',2);
//    disp([k, sd4(k+1,:), somab(sd4(k+1,:))]);
end;

//// desempenho dos códigos:
v0 = zeros(1,11);
v74 = v0;
v128 = v0;
pp=1;
for Av=0:11;

    erros = 0;
    errosc = 0;
    errosc4 = 0;

    Amp = sqrt(10^(-Av/10));
    for nb=1:500000
    // código (7,4):
    info = (1+sign(rand(1,4,'n')))/2;  // 1000 blocos de 4 bits
    infoc = pmodulo(info*G1,2); // mensagem com código
    infocm = infoc*2-1;  // BPSK ==> {-1.+1}
    infocmr = infocm + Amp*rand(1,max(size(infocm)),'n');  // sinal com ruido
    infocmrd = (1+sign(infocmr))/2;  // decidido e demodulado
    //erros = erros + sum(abs(infoc-infocmrd));
    ss = pmodulo(infocmrd*H1',2);
    infocss = infocmrd;
    if sum(ss)>0 then   // corrige apenas 1 erro:
        for kk=2:8
            ve = zeros(1,7);
            ve(kk-1)=1;
            if ss==sd1(kk,:) then
                infocss = pmodulo(infocmrd+ve,2);
            end
        end
    end
    errosc = errosc + sum(abs(infoc-infocss));
 
    // código (12,8):
    info = (1+sign(rand(1,8,'n')))/2;  // 1000 blocos de 8 bits
    infoc = pmodulo(info*G4,2); // mensagem com código
    infocm = infoc*2-1;  // BPSK ==> {-1.+1}
    infocmr = infocm + Amp*rand(1,max(size(infocm)),'n');  // sinal com ruido
    infocmrd = (1+sign(infocmr))/2;  // decidido e demodulado
    erros = erros + sum(abs(infoc-infocmrd));
    ss = pmodulo(infocmrd*H4',2);
    infocss = infocmrd;
    if sum(ss)>0 then   // corrige apenas 1 erro:
        for kk=2:13
            ve = zeros(1,12);
            ve(kk-1)=1;
            if ss==sd4(kk,:) then
                infocss = pmodulo(infocmrd+ve,2);
            end
        end
    end
    errosc4 = errosc4 + sum(abs(infoc-infocss));
end
    v0(pp) = erros/(12*nb);
    v74(pp) = errosc/(7*nb);
    v128(pp) = errosc4/(12*nb);
    pp = pp + 1;
    disp([erros/(12*nb), errosc/(7*nb), errosc4/(12*nb)]);
end;

Av=0:11;
vx = Av;
Av2 = 0:0.25:14;
ax2 = sqrt(10.^(-Av2/10));
ct = 0.5*erfc((1.0)./(sqrt(2)*ax2));
d74 = 10*log10(7/4);
d128 = 10*log10(12/8);
if min(v74)<1e-12 e-12="" end="" p="" then="" v74="">if min(v128)<1e-12 e-12="" end="" p="" then="" v128="">
close;
f1 = figure();
plot(vx,v0,'-x',vx+d74,v74,'-o',vx+d128,v128,'-d',Av2,ct,'k');
legend('Sem código','Código (7,4)','Código (12,8)','Sem código - teórico');
xgrid;

a=gca();
a.log_flags = "nln";
h1=uicontrol(f1,"style","pushbutton","string","lin/log","position", [10 10 40 20],"callback","trocax()");