Matematické Fórum

Dobrý den,

Zrovna řeším implementaci hammingova kódu. Mám příklad:
VSTUPNÍ DATA: 0b1000 0110 (0x86)

KÓDOVÁNÍ
Bajt rozdělým na dva půlbajty - horní (1000) a spodní (0110). A na každou tuto čtveřici dopočítávám paritní (kontrolní) bity dle následujícího klíče (příklad pro spodní půlbajt):
_    _   0  _    1   1   0   ? (na LSB bitu nezáleží - mám nastaveno trvale na 0)
P1 P2 D0 P4 D1 D2 D3

P1 = D0 XOR D1 XOR D3 = 0 ^ 1 ^ 0 = 1;
P2 = D0 XOR D2 XOR D3 = 0 ^ 1 ^ 0 = 1;
P4 = D1 XOR D2 XOR D3 = 1 ^ 1 ^ 0 = 0;

doplním výsledný bajt:
1   1   0   0   1   1   0   ? (na LSB bitu nezáleží - mám nastaveno trvale na 0)
P1 P2 D0 P4 D1 D2 D3

takže odesílám bajt: 0b1100 1100


/*****************************************************************

DEKÓDOVÁNÍ
Vezmu odeslaný bajt a vypočítám prvky syndromu podle tohoto klíče:
P1 = P1 XOR D0 XOR D1 XOR D3 = 1 ^ 0 ^ 1 ^ 0 = 0;
P2 = P2 XOR D0 XOR D2 XOR D3 = 1 ^ 0 ^ 1 ^ 0 = 0;
P4 = P4 XOR D1 XOR D2 XOR D3 = 0 ^ 1 ^ 1 ^ 0 = 0;
Fajn, syndrom je 0,0,0 takže data bez chyb. To samé udělám i pro druhý půl bajt, spojíme je dohromady a mám opět na konci řetězce to samé co na začátku.


Pokud se objeví 1 chyba v jednom bitu (řekněme třeba v 4. zleva) - přijaté slovo bude: 0b1101 1100. Syndrom:
P1 = P1 XOR D0 XOR D1 XOR D3 = 1 ^ 0 ^ 1 ^ 0 = 0;
P2 = P2 XOR D0 XOR D2 XOR D3 = 1 ^ 0 ^ 1 ^ 0 = 0;
P4 = P4 XOR D1 XOR D2 XOR D3 = 1 ^ 1 ^ 1 ^ 0 = 1;
OK. Syndrom 0,0,1 - takže chyba v 4. bitu zleva, ten se automaticky neguje, čímž se slovo změní na 0b1100 1100, opět se provede výpočet syndromu (vyjde 0,0,0) a data jsou prohlášena za platná, s tím že došlo k detekci a korekci jedné chyby. Super, zatím to funguje....


Teď ale nastává problém. Řekněme, že chyba nastala ve 2 bitech současně a to na 4. a 5. zleva a přijaté slovo je: 0b1101 0100. Syndrom:
P1 = P1 XOR D0 XOR D1 XOR D3 = 1 ^ 0 ^ 0 ^ 0 = 1;
P2 = P2 XOR D0 XOR D2 XOR D3 = 1 ^ 0 ^ 1 ^ 0 = 0;
P4 = P4 XOR D1 XOR D2 XOR D3 = 1 ^ 0 ^ 1 ^ 0 = 0;
OK, takže máme chybu na 1. bitu zleva. Znegujeme ho a dostaneme: 0b0101 0100 a opět vypočteme syndrom:
P1 = P1 XOR D0 XOR D1 XOR D3 = 0 ^ 0 ^ 0 ^ 0 = 0;
P2 = P2 XOR D0 XOR D2 XOR D3 = 1 ^ 0 ^ 1 ^ 0 = 0;
P4 = P4 XOR D1 XOR D2 XOR D3 = 1 ^ 0 ^ 1 ^ 0 = 0;
A ejhle - syndrom je 0,0,0 a systém si právě myslí, že opět detekoval a opravil jednu chybu a data (výsledek v tomto případě bude 0x4 namísto správného 0x6) prohlásí za platná, ačkoliv jsou blbě.

Když jsem si to zkoušel ještě na jiném příkladu na papíře, nasimulovat dvojitou chybu, tak poprvé syndrom vyšel blbě (nenulově) a po druhé také, přičemž algoritmus, pokud zjistí, že je i po druhém průchodu syndrom jiný, než nulový, tak ohlásí chybu a data jsou prohlášena za neplatná, protože (jsem se domníval), že tak se právě projeví dvojitá chyba.

Může mi prosím někdo poradit, jaký je tedy algoritmus dekódování hammingova kódu ?
P.S.
Info jsem bral odsud: http://users.cis.fiu.edu/~downeyt/cop3402/hamming.html

Děkuji