Sadržaj
Hammingovi kodovi koriste se za umetanje podataka o ispravljanju pogrešaka u tokove podataka. Kodovi su dizajnirani tako da se pogreška ne samo otkrije, već i ispravi. Dodavanje informacija o ispravljanju pogrešaka povećava količinu podataka, ali također povećava pouzdanost komunikacije preko medija s visokim stopama pogrešaka.
Hammingovo kodiranje može biti složeno za implementaciju, ali to se može učiniti vrlo brzo pomoću aritmetičkih trikova na razini bita. To omogućuje stvaranje korisnog i brzog sustava ispravljanja pogrešaka koji će se koristiti u ugrađenim aplikacijama.
Korak 1
Stvorite podatkovnu riječ. Bilo koji bit s položajem koji je stepen dvojke (prvi, drugi, četvrti itd.) Mora biti rezerviran za informacije o paritetu. Koristite onoliko dugo koliko je potrebno da riječ ima izvorne podatke i bitove pariteta.
Primjer:
1 1 0 1 0 0 1 0 postaje _ _ 1 _ 1 0 1 _ 0 0 1 0
Izvorni bitovi ostaju istim redoslijedom, ali su rašireni kako bi se umetnuli bitovi pariteta.
Korak 2
Izračunajte prvi bit parnosti. Počevši od prvog bita, malo se čita, a zatim se malo preskače i postupak se ponavlja do kraja. U međuvremenu se broji broj pronađenih. Bitovi pariteta se ne računaju u ovom procesu.
Ako je broj jedinica paran, prvi bit postavite na nulu. Inače, postavite ga na jedan.
Primjer:
Bitovi 1, 3, 5, 7, 9 i 11 od _ _ 1 _ 1 0 1 _ 0 0 1 0, _11101, sadrže četiri jedinice. To je parno, pa je prvi bit postavljen na nulu: 0 _ 1 _ 1 0 1 _ 0 0 1 0
3. korak
Izračunajte preostale bitove pariteta. Počevši od drugog bita, čitaju se dva bita, a zatim se preskaču dva bita i postupak se ponavlja do kraja. Četvrti bit čita četiri bita, preskače još četiri, počevši od bita četiri. Isti obrazac slijede svi bitovi pariteta, dok se svi ne izračunaju.
Primjer:
Bit 2: 0 _ 1 _ 1 0 1 _ 0 0 1 0 provjerava _1, 01, 01, koji sadrže tri jedinice, pa je bit 2 postavljen na jedan. Bit 4: _ 0 1 1 1 0 1 _ 0 0 1 0 provjerava _101, 0, koji sadrži dva, pa je bit 4 postavljen na nulu. Bit 8: 0 1 1 0 1 0 1 _ 0 0 1 0 provjerava _0010, koji sadrži samo jedan, pa je bit 8 postavljen na jedan.
Riječ je stoga šifrirana kao 011010110010.
4. korak
Potvrdite riječ. Ako je riječ oštećena, bitovi pariteta neće se podudarati s očekivanim. Da biste potvrdili da riječ nije oštećena, samo izračunajte bitove pariteta pomoću koraka dva i tri. Ako bitovi nisu isti, zabilježite njihove položaje.
Korak 5
Ispravite pogrešan bit. Ako pronađete netočne bitove pariteta, jednostavno dodajte položaje bitova. Vrijednost zbroja je položaj netočnog bita. Promijenite vrijednost bita u ovom položaju.
Na primjer, ako su netočni bitovi pariteta jedan i četiri, promjena vrijednosti petog bita ispravit će pogrešku.