1
INTERNACIONALNI UNIVERZITET TRAVNIK U TRAVNIKU
FAKULTET POLITEHNIČKIH NAUKA
TRAVNIK
TEMA: HEMINGOV KOD
SEMINARSKI RAD
PREDMET: KANALNO KODOVANJE
Predmetni nastavnik: Student:
Prof.dr. sc Goran Popović Suad Rodić
Asistent : Almedina Hatarić PT-21/14
Travnik, decembar 2016.
4
1. HEMINGOV KOD
Kodovi za korekciju grešaka koriste višestruke
parity
bitove koji su smkešteni sa bitovima
podataka. Svaki bit provjere je
parity
bit grupe bitova u poruci. Prilikom čitanja primnjene
poruke provjeravaju se svi
parity
bitovi i ako su svi uredu, znači da nije došlo do greške u
prenjetoj poruci. Međutim ako je jedan ili više
parity
bitova neispravno, može se utvrditi koji
je od bitova pogrešan. Jednostruka greška nastaje kada je vrijednost jednog bita u poruci
promenjena sa 1 na 0 ili sa 0 na 1. Ako je utvrđen pogrešan bit, može biti lako korigovan
komplementiranjem njegove vrijednosti. Jedan od najčešće korišćenih kodova sa korekcijom
greške u RAM memorijama je Hamingov kod. Glavne odlike Hamingovog koda su:
- Detekcija greške je jednostavna (dodavanjem
parity
bitova)
- Korekcija greške je kompleksna i zahtjeva Hamingov kod sa više
parity
bitova
U Hamingovom kodu, p -
parity
bitova je dodato na m - bitova u poruci, tako da imamo
novonastalu kodnu riječ on m+p - bitova. Bitske pozicije su numerisane u sekvenci od 1 do
m+p. Sve pozicije u riječi, čiji je broj stepena 2 (pozicije 1,2,4,8,...) koriste se za
parity
bitove. Ostale pozicije su namjenjene za bitove originalne poruke. Izgled kodovane poruke, za
originalnu poruku od 8-bitova:
pozicije: 12 1
Vidimo da je originalnoj 8-bitnoj poruci dodato 4
parity
bita tako da sad sekvenca ima 12
bitova.
Prilikom izbora broja
parity
bitova mora biti zadovoljena sljedeća relacija:
2
m
≥ m+p+1
na primer: za 8-bitnu poruku poruka potrebna su nam 4
parity
bita, tako da će podatak koji
prenosimo sadržati ukupno 12 bitova.
d7
d6
d5
p3
d3
d2
d1
d4
p2
d0
p1
p0
5
-
parity
bitovi su 1,2,4,8, ... (P1,P2,P3,P4)
•
3 = 1+2
•
5 = 1+4
•
6 = 2+4 P1 provjerava bitove 3, 5, 7, 9, 11
•
7 = 1+2+4 P2 provjerava bitove 3,6,7,10,11
•
9 = 1+8 P4 provjerava bitove 5,6,7,12
•
10 =2+8 P8 provjerava bitove 9,10,11,12
•
11 = 1+2+8
•
12 = 4+8
Tako da vrjednosti P1,P2,P4 i P8 računamo kao:
P1 = XOR nad bitovima (3,5,7,9,11)
P2 = XOR nad bitovima (3,6,7,10,11)
P4 = XOR nad bitovima (5,6,7,12)
P8 = XOR nad bitovima (9,10,11,12)
Korišćena ekskluzivna OR operacija ustvari vrši neparnu funkciju. Ona je jednaka 1 kada
imamo neparan broj jedinica između posmatranih promenjivih, a jednaka 0 kada imamo paran
broj jedinica. To nam obezbeđuje da je broj jedinica na proveravanim pozicijama uključujući i
bitove parnosti, uvijek paran.
Na mjestu prijema kompozitna riječ od 12 bitova se ponovo provjerava na grešku. Parnost
riječi se proverava nad istim grupama bitova u reči uključujući i bitove parnosti. Tako da
ćemo sad imati četiri bita provjere:
