Hamingov kod (7,4)
Hamingov(7,4)-kod | |
---|---|
Imenovan po | Ričardu Hamingu |
Parameteri | |
Dužina bloka | 7 |
Dužina poruke | 4 |
Stopa | 4/7 ~ 0.571 |
Rastojanje | 3 |
Veličina alfabeta | 2 |
Notacija | [7,4,3]2-code |
Svojstva | |
savršeni kod | |
U teoriji kodiranja Hamingov kod (7,4) je linearni kod za korekciju greške koji kodira 4 bita podataka u 7 bitova tako što dodaje 3 bita parnosti. Hamingov kod (7,4) je deo veće porodice Hamingovih kodova, ali termin Hamingov kod se obično odnosi na ovaj specifični kod koji je 1950. godine uveo Ričard Haming. Svojevremeno, Haming je radio u Bell Labs-u i bio je frustriran greškama čitača za bušene kartice, zbog toga je počeo da radi na kodovima za ispravljanje grešaka.[1]
Hamingov kod dodaje 3 dodatna bita provere svakom četvrtom bitu podatka u poruci. Hamingov (7,4) algoritam može da ispravi svaku jedno-bitnu grešku, ili da detektuje sve jednobitne i dvobitne greške. Drugim rečima, minimalno Hamingovo rastojanje između bilo dve kodirane reči je 3, i primljene reči mogu biti ispravno dekodirane ako su na rastojanju od najviše jedane kodne reči koja je prosleđena od pošiljaoca. To znači da za prenos srednjeg slučaja gde se engl. burst greške ne izvršavaju, Hamingov kod (7,4) je efikasan.
Cilj[uredi | uredi izvor]
Cilj Hamingovog koda je da kreira skup parnosti bita koji se preklapaju tako da jedno-bitna greška (vrednost bita je logički je flipovana) u bitu podatka ili parnosti bita može biti detektovana i ispravljena. Dok može da se kreira više preklapanja, opšti metod je predstavljen u Hamingovim kodovima.
Bit# 1 2 3 4 5 6 7 Prenosivi bit Da Ne Da Ne Da Ne Da Ne Da Da Ne Ne Da Da Ne Ne Ne Da Da Da Da
Ova tabela opisuje koji bit parnosti pokriva koje prenosne bitove u kodiranoj reči. Na primer, p2 obezbeđuje parnu parnost za bitove 2, 3, 6, & 7. Ona takođe, čitajući kolone, detaljno opisuje koji bit prenosi koji bit parnosti Na primer, d1 je pokriveno sa p1 i p2 ali ne sa p3. Ova tabela će upadljivo ličiti na matricu provere parnosti (H) u sedećoj sekciji.
Štaviše, ako su kolone parnosti u gornjoj tabeli uklonjene
Da Da Ne Da Da Ne Da Da Ne Da Da Da
zatim sličnost sa redovima 1, 2, & 4 generatora koda matrice (G) ispod, takođe će biti očigledna.
Dakle, pravilno birajući pokrivenost bita parnosti, sve greške sa Hamingovim rastojanjem od 1, mogu da se otkriju i isprave, što je i poenta korišćenja Hamingovog koda.
Hamingove matrice[uredi | uredi izvor]
Hamingovi kodovi se mogu računati u terminima linearne algebre matrice, zato što su Hamingovi kodovi linearni kodovi. Za svrhe Hamingovih kodova, dve Hamingove matrice se mogu definisati: kod generatora matrice G i matrica provere parnosti H:
Kao što smo u delu iznad As mentioned above, rows 1, 2, & 4 of G should look familiar as they map the data bits to their parity bits:
Sve kodne reči[uredi | uredi izvor]
Pošto je izvor samo 4 bita onda postoji samo 16 mogućih prenosivih reči. Uključena je 8-bitna vrednost ukoliko se koristi dodatni bit parnosti (Bitovi podataka su prikazani u plavoj boji, parnost bita je prikazana u crvenoj boji, i ekstra parnost bita je prikazana u zelenoj boji.)
Reference[uredi | uredi izvor]
- ^ „History of Hamming Codes”. Arhivirano iz originala 25. 10. 2007. g. Pristupljeno 3. 4. 2008.