No exemplo anterior, temos , que no caso é 11. Este algoritmo é facilmente implementado.
No entanto, o vector fornecido pode ser elemento de .
>> 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 .
Para contornar esta questão, transforma-se, à medida do necessário, as entradas de dado em elementos de , 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 é feita à custa do síndrome de , ou seja, à custa do vector coluna , onde é 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 é dada pela representação decimal de . Por exemplo, suponha que recebido tem síndrome . Pelo que foi visto nas aulas teóricas, a posição de com erro é , que corresponde a na base 10. Note ainda que sendo a matriz de paridade do código de Hamming, com 4 linhas, então tem colunas. Ou seja, é um vector linha com 14 bits, sendo que o 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 é um argumento de entrada, número inteiro positivo, e cujo resultado final é uma matriz , cuja coluna é a representação do número natural 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 , encontre um vector coluna sobre , com dimensão fixa à partida, cujas entradas são os dígitos (0 ou 1) correspondentes à representação binária de . Por exemplo, que a , fixando em o número de linhas do vector, tenha como resultado .
Suponha, então, que se pretende construir um vector coluna
, com dimen linhas, cujas entradas são os símbolos da representação binária de
, onde dimen
. Aplica-se o algoritmo da divisão:
No que se segue, atribua 4 a dimen e 5 a .
>> 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
onde o esquema de codificação usado foi Hamming [7,4]. Seja a matriz de Hamming com 3 linhas, que pode ser obtida pelas instruções atrás definidas. Basta-nos calcular o síndrome de , isto é, :
>> 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 é palavra-código.
Suponha agora que foi recebido
Calcula-se o síndrome de
>> 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 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); 7Ou seja, o elemento está errado. Corrijamo-lo:
>> r[soma]:=r[soma]+Z2(1); 0 mod 2