Hamminga kļūdu labošanas kods: definīcija, darbības princips un piemēri

Hamminga kods ir kļūdu labošanas bloka kods. Kods nosaukts pēc Ričarda Haminga, kurš to izstrādāja pagājušā gadsimta 50. gados, strādājot ar mašīnām, kurās bija releji un datu nolasīšanai izmantoja perforētās kartes. Tā kā perforētās kartes bija pakļautas bojājumiem un kļūdām, Hamming meklēja efektīvu veidu, kā tās automātiski atrast un — kur iespējams — arī labot.

Kas ir Hamminga kods un kā tas darbojas

Hamminga kodi tiek plaši izmantoti ciparu signālu apstrādē un telekomunikācijās, jo tie nodrošina efektīvu veidu vienu bita kļūdu labošanai ar minimālu papildu bitu skaitu. Hamminga kods sastāv no lietotāja datu bitiem un paritātes (kontroles) bitiem. Paritātes bits norāda, vai konkrētā bitu grupā 1 skaits ir pāra vai nepāra, un katrs datu bits tiek iekļauts vairākos paritātes aprēķinos. Šī pārklāšanās ļauj vienbitu kļūdu ne tikai atklāt, bet arī precīzi lokalizēt un labot.

Attiecība starp paritātes bitu skaitu un koda garumu

Lai aptvertu visas pozīcijas no 1 līdz n ar k paritātes bitiem un spētu identificēt vienbitu kļūdu, jāizpildās nosacījumam:

k paritātes biti ļauj adresēt n = 2^k − 1 pozīcijas. Konkrēti:

2 k - 1 {\displaystyle 2^{k}-1} $2^{k}-1$

Piemēram, ja k = 3 paritātes biti, tad n = 2³ − 1 = 7, un lietotāja datu bitu skaits būs n − k = 4. Šādu kodu pieraksta kā (7,4).

Konstrukcija — paritātes bitu īpašā izvietojuma nozīme

Standarta Hamminga kodā paritātes biti izvieto pozīcijās, kas ir divu pakāpes: 1, 2, 4, 8, ... (tātad 2⁰, 2¹, 2², ...). Pārējās pozīcijas aizņem datu biti. Katrs paritātes bits pārbauda konkrētu pozīciju kopu — tieši tās pozīcijas, kuru binārajā attēlojumā attiecīgais bitu svars ir 1.

Piemēram (7,4) kodā:

pozīcija 1 = p1 (paritātes bits), pārbauda pozīcijas 1,3,5,7;
pozīcija 2 = p2, pārbauda pozīcijas 2,3,6,7;
pozīcija 3 = d1 (datu bits);
pozīcija 4 = p4, pārbauda pozīcijas 4,5,6,7;
pozīcijas 5,6,7 = d2,d3,d4 (datu biti).

Enkodēšana — piemērs (7,4)

Pieņemsim, ka mūsu lietotāja dati ir 1 0 1 1 (d1=1,d2=0,d3=1,d4=1). Piemēram, izmantojot pāra paritāti (t.i., paritātes bits tiek izvēlēts tā, lai kopā ar kontrolētajiem biti skaits būtu pāra skaits), aprēķini notiek šādi:

p1 pārbauda pozīcijas 1,3,5,7 → p1 = d1 ⊕ d2 ⊕ d4 = 1 ⊕ 0 ⊕ 1 = 0;
p2 pārbauda pozīcijas 2,3,6,7 → p2 = d1 ⊕ d3 ⊕ d4 = 1 ⊕ 1 ⊕ 1 = 1;
p4 pārbauda pozīcijas 4,5,6,7 → p4 = d2 ⊕ d3 ⊕ d4 = 0 ⊕ 1 ⊕ 1 = 0.

Tādējādi koda vārds pozīcijās 1..7 būs: p1 p2 d1 p4 d2 d3 d4 = 0 1 1 0 0 1 1 (t.i., 0110011).

Atklāšana un labošanas algoritms — sindroms

Pēc saņemšanas pārraidei saņēmējs pārskaita tās pašas paritātes kontrollistes; iegūtie paritātes rezultāti veido tā saukto sindromu. Sindroma bits atbilst tam pašam paritātes bitam (p1,p2,p4,...). Ja sindroms ir nulle (visi paritātes pārbaudes rezultāti — pāri), kļūdu nav. Ja sindroms satur nenulles bināru vērtību, tā decimālā interpretācija norāda pozīciju, kurā ir bojāts bits.

Piemērs: ja no sūtītā 0110011 pozīcijā 5 bits tiek pārvērsts no 0 uz 1 (radot vārdu 0110111), saņēmējs aprēķinās sindromu:

s1 = pārbaude 1,3,5,7 → atklās pārbīdījumu;
s2 = pārbaude 2,3,6,7;
s4 = pārbaude 4,5,6,7;

Apvienojot s4s2s1 kā bināru skaitli, iegūst pozīciju 5 — tātad tieši 5. pozīciju jāinvertē, kas labo vārdu atpakaļ uz 0110011.

Īsākais Hamminga kods un kodu īpašības

Īsākais Haminga kods ir (3,1) (k = 2, n = 2² − 1 = 3, lietotāja biti = 1). Šim kodam, ja datu bits ir 0, kods ir 000, ja datu bits ir 1, kods ir 111. Ja pārraides laikā iekrīt vienbitu kļūda, dekodēšana to atpazīst un atgriež tuvāko derīgo koda vārdu (piemēram, 001, 010, 100 tiks laboti uz 000, bet 011, 101, 110 uz 111).

Hamminga kodu minimālais Hamming distances ir 3, kas nozīmē, ka tas var droši labot jebkuru vienu bita kļūdu (single-error-correcting, SEC) un atklāt daļu divu bita kļūdu gadījumu. Lai paplašinātu spējas un atklātu arī divbitu kļūdas, bieži pievieno vēl vienu kopējo paritātes bitu (SECDED — single-error-correcting, double-error-detecting). Piemērs ir (8,4) paplašinātais Hamminga kods, kur pievienots pārklājuma paritātes bits.

Praktiskās piezīmes un ierobežojumi

Priekšrocības: efektīvs un vienkāršs vienbitu kļūdu labošanai, zems paritātes bitu pārslodze attiecībā pret aizsargātajiem datiem.
Ierobežojumi: nevar labot divu vai vairāk bitu kļūdas; bez papildu kopējā paritātes bita tas dažkārt pat neatklāj divbitu kļūdas (var rasties nekorekti labojumi), tāpēc kritiskos pielietojumos izmanto papildu mehānismus vai spēcīgākus kodus.
Lietojumi: atmiņas ierīcēs (ECC RAM), zemo latentuma kanālos, iebūvētajās sistēmās un citur, kur tiek sagaidīts galvenokārt vienbitu kļūdu modelis.

Kopsavilkumā — Hamminga kods ir vienkāršs, labi saprotams un efektīvs risinājums, lai automātiski atklātu un labotu vienbitu kļūdas, ar viegli izsekojamu konstrukciju (paritātes bitu izvietojums uz 2^i pozīcijām) un skaidru dekodēšanas algoritmu, kas balstīts uz sindromu aprēķinu.

Jautājumi un atbildes

J: Kas ir Haminga kods?

A: Hamminga kods ir kļūdu labošanas bloka kods, ko pagājušā gadsimta 50. gados izstrādāja Ričards Hamings. To izmanto ciparu signālu apstrādē un telekomunikācijās, lai atklātu un labotu kļūdas.

J: Kā darbojas Haminga kods?

A: Hamminga kods izmanto vairākus paritātes bitus, lai aptvertu katru datu bitu, kas ļauj atklāt kļūdas un noteiktos gadījumos arī labot tās. Tas izmanto arī dublēšanu, kas nozīmē, ka kopējam koda vārda garumam jābūt vienādam ar 2^k - 1, kur k ir paritātes bitu skaits.

J: Kas izgudroja Haminga kodu?

A: Haminga kodu izgudroja Ričards Hamings pagājušā gadsimta 50. gados.

J: Kādam nolūkam Ričards Hamings izmantoja savu izgudrojumu?

A: Savā laikā Ričards Hammings izmantoja savu izgudrojumu, lai palīdzētu labot kļūdas perforētās kartītēs, ko plaši izmantoja mašīnās ar releju. Mūsdienās to galvenokārt izmanto ciparu signālu apstrādei un telekomunikācijās.

J: Ko raksta kā (N,n), runājot par Hamminga kodu?

A: Runājot par hamminga kodu, (N,n) apzīmē kodu vārda kopējo garumu (pirmais skaitlis) un lietotāja datu bitu skaitu (otrais skaitlis). Piemēram, (7,4) nozīmē, ka kopējais bitu skaits ir 7, no kuriem 4 ir lietotāja datu biti.

J: Kāds ir īsākais iespējamais Hamminga kods?

A: Īsākais iespējamais Hamminga kods ir (3,1), kas nozīmē, ka ir 3 kopējie biti, no kuriem 1 ir lietotāja datu bits.