next up previous contents
Seguinte: Códigos lineares Acima: Alguns códigos lineares com Anterior: Polinómios   Conteúdo

Códigos de Hamming

Os códigos de Hamming serão os primeiros com direito a implementação. No esquema de correcção de rros, será necessário escrever um número apresentado no sistema binário no decimal. De facto, o número será dado à custa de um vector (coluna) sobre $ {\mathbb{Z}}_2$ . Por exemplo, o vector $ [1,0,1,1]^T$ indica o número $ (1011)_2$ . Pretende-se encontrar a representação decimal. Para tal, recordamos como se faz tal correspondência: a representação decimal de $ (v_1v_2\cdots v_k)_2$ é

$\displaystyle \sum_{i=1}^k v_i 2^{k-i}.$

No exemplo anterior, temos $ 1\cdot 2^3+0\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0$ , que no caso é 11. Este algoritmo é facilmente implementado.

No entanto, o vector $ v$ fornecido pode ser elemento de $ {\mathbb{Z}}_2$ .

>> Z2:=Dom::IntegerMod(2):
>> M2:=Dom::Matrix(Z2):
>> delete(i):
>> v:=M2([1,0,1,1]):
>> sum(v[i]*2^(4-i),i=1..4);

                                  1 mod 2

Aqui surge um problema, já que o MUPAD efectua os cálculos em $ {\mathbb{Z}}_2$ .

Para contornar esta questão, transforma-se, à medida do necessário, as entradas $ v[i]$ de $ v$ dado em elementos de $ {\mathbb{Z}}$ , fazendo uso de uma variável auxiliar:

>> aux:=coerce(v[i],Dom::Integer);

Assuma que usa um ciclo for. A cada passo do ciclo, a soma vai sendo calculada:

>> soma:=soma+aux*2^(n-i);

Ficamos, para este caso, com o ciclo seguinte:

>> soma:=0

                                     0
>> for i from 1 to 4 do
 aux:=coerce(v[i],Dom::Integer);
 soma:=soma+aux*2^(4-i);
 end_for: print(soma);

                                    11

Se estiver a construir um procedimento, não se esqueça de enviar o resultado para o programa principal:

return(soma);

Esta secção tem como finalidade fornecer algumas ideias para a implementação de um código de Hamming. Recorde que a correcção de erros de $ r$ é feita à custa do síndrome de $ r$ , ou seja, à custa do vector coluna $ Hr^T$ , onde $ H$ é a matriz de Hamming, matriz de paridade do código. Mais, um código de Hamming é um código perfeito corrector erros singulares. De facto, a posição do erro em $ r$ é dada pela representação decimal de $ Hr^T$ . Por exemplo, suponha que $ r$ recebido tem síndrome $ [1,0,1,1]^T$ . Pelo que foi visto nas aulas teóricas, a posição de $ r$ com erro é $ (1011)_2$ , que corresponde a $ 11$ na base 10. Note ainda que sendo $ H$ a matriz de paridade do código de Hamming, com 4 linhas, então tem $ 2^4-1=15$ colunas. Ou seja, $ r$ é um vector linha com 14 bits, sendo que o $ 11^\circ$ está incorrecto (segundo o esquema usado na correcção pelo vizinho mais próximo, fazendo uso da distância de Hamming).

É ainda necessário, de forma a se poder implementar um código de Hamming, construir um procedimento hamming:=proc(numero:Type::PosInt) onde $ n$ é um argumento de entrada, número inteiro positivo, e cujo resultado final é uma matriz $ n\times (2^n-1)$ , cuja coluna $ j$ é a representação do número natural $ j$ na sua escrita binária. Ou seja, uma forma fácil de construir uma matriz de Hamming. Para tal, concentramo-nos num algoritmo que, dado um número $ (k)_{10}$ , encontre um vector coluna sobre $ {\mathbb{Z}}_2$ , com dimensão fixa à partida, cujas entradas são os dígitos (0 ou 1) correspondentes à representação binária de $ n$ . Por exemplo, que a $ 5$ , fixando em $ 4$ o número de linhas do vector, tenha como resultado $ [0,1,0,1]^T$ .

Suponha, então, que se pretende construir um vector coluna $ v$ , com dimen linhas, cujas entradas são os símbolos da representação binária de $ q$ , onde dimen $ \ge \lfloor\log_2 q\rfloor +1$ . Aplica-se o algoritmo da divisão:

$\displaystyle q=q_0$ $\displaystyle =$ $\displaystyle 2q_1+r_1,$  
$\displaystyle q_1$ $\displaystyle =$ $\displaystyle 2q_2+r_2,$  
    $\displaystyle \vdots$  
$\displaystyle q_{n-2}$ $\displaystyle =$ $\displaystyle 2q_{n-1}+r_{n-1},$  
$\displaystyle q_{n-1}$ $\displaystyle =$ $\displaystyle 2*0+r_n,$  

onde $ 0\le r_i<2$ . O vector pretendido será $ [0,\dots,0,r_n,r_{n-1},\dots ,r_2,r_1]^T$ .

No que se segue, atribua 4 a dimen e 5 a $ q$ .

>> for i from dimen downto 1 do
                v[i]:=Dom::IntegerMod(2)(q):
                q:=q div 2:
   end_for:
>> v;
                               +-         -+
                               |  0 mod 2  |
                               |           |
                               |  1 mod 2  |
                               |           |
                               |  0 mod 2  |
                               |           |
                               |  1 mod 2  |
                               +-         -+

O que lhe resta fazer? Construir cada coluna da matriz de Hamming, concatenando-as. Por exemplo:

export(linalg):
dimen:=3:
q:=1: v:=M2(dimen,1):
for i from dimen downto 1 do
                v[i]:=Dom::IntegerMod(2)(q):
                q:=q div 2:
   end_for:
H:=v:
for q2 from 2 to 2^dimen-1 do
q:=q2:for i from dimen downto 1 do
                v[i]:=Dom::IntegerMod(2)(q):
                q:=q div 2:
   end_for:
H:=concatMatrix(H,v)
end_for: print(H);

Suponha que foi recebido por uma canal simétrico binário

$\displaystyle r=\left(\begin{array}{ccccccc}
1\,\text{mod}\,2 & 1\,\text{mod}\,...
...2 \
& 1\,\text{mod}\,2 & 1\,\text{mod}\,2 & 1\,\text{mod}\,2\end{array}\right)$

onde o esquema de codificação usado foi Hamming [7,4]. Seja $ H$ a matriz de Hamming com 3 linhas, que pode ser obtida pelas instruções atrás definidas. Basta-nos calcular o síndrome de $ r$ , isto é, $ Hr^T$ :
>> H*transpose(r)
                               +-         -+
                               |  0 mod 2  |
                               |           |
                               |  0 mod 2  |
                               |           |
                               |  0 mod 2  |
                               +-         -+

Assuma que previamente foi exportada a livraria linalg. Como o síndrome é o vector nulo, segue que $ r$ é palavra-código.

Suponha agora que foi recebido

$\displaystyle r=\left(\begin{array}{ccccccc}
1\,\text{mod}\,2 & 1\,\text{mod}\,...
... \
& 0\,\text{mod}\,2 & 0\,\text{mod}\,2 & 1\,\text{mod}\,2\end{array}\right)
$

Calcula-se o síndrome de $ r$
>> s:=H*transpose(r)
                               +-         -+
                               |  1 mod 2  |
                               |           |
                               |  1 mod 2  |
                               |           |
                               |  1 mod 2  |
                               +-         -+
para se concluir que não é palavra-código. Sendo o código de Hamming, o processo de correcção de erros (neste caso de um erro) fornece um algoritmo para a correcção: o síndrome é a representação binária da posição de $ r$ que tem o erro. Faça-se uso do que inicialmente se tratou nesta secção.
>> soma:=0:
for i from 1 to 3 do
 aux:=coerce(s[i],Dom::Integer);
 soma:=soma+aux*2^(3-i);
end_for: 
print(soma);
                                     7
Ou seja, o elemento $ r[7]$ está errado. Corrijamo-lo:
>> r[soma]:=r[soma]+Z2(1);
                                  0 mod 2


next up previous contents
Seguinte: Códigos lineares Acima: Alguns códigos lineares com Anterior: Polinómios   Conteúdo
2006-12-21