Hammingo kodas: klaidų taisymas, veikimo principas ir pavyzdžiai

Hammingo kodas: klaidų taisymas, veikimo principai ir aiškūs pavyzdžiai — nuo (3,1) iki (7,4), pariteto bitų paaiškinimai ir praktinės taikymo instrukcijos telekomunikacijoms.

Hammingo kodas yra blokinis klaidų taisymo kodas, pavadintas jį 1950-aisiais sukūrusio Richardo Hammingo vardu. Jį iš pradžių taikė mašinose, kurios naudojo relės ir duomenims skaityti – perforuotas korteles, kuriose dėl mechaninių priežasčių dažnai atsirasdavo bitų klaidų. Hammingo kodas buvo sukurtas tam, kad tokius vieno bito gedimus būtų galima aptikti ir pataisyti automatiškai.

Veikimo principas

Hammingo kodai naudoja kelis pariteto bitus. Pariteto bitas nurodo, ar tam tikro bitų rinkinio skaičius yra lyginis, ar nelyginis. Dažniausiai taikoma lygi pariteto taisyklė (even parity): pariteto bitas parenkamas taip, kad įskaičiuojant jį į bitų grupę, visų 1-ų skaičius būtų lyginis.

Pariteto bitai išdėstomi kodo žodyje pozicijose, kurios yra dvejeto laipsniai: 1, 2, 4, 8 ir t. t. Visi kiti bitai yra vartotojo (duomenų) bitai. Kiekvienas pariteto bitas kontroliuoja tam tikras pozicijas (pagal jų dvejetainę reikšmę), todėl kiekvienas duomenų bitas yra „dengiamas“ kelių pariteto bitų. Jei gavus kodo žodį iš naujo apskaičiuojame paritetus ir jie neatitinka siųstų pariteto bitų, gauname klaidų diagnozę — vadinamąją sindromą. Sindromo dvejetainė reikšmė nurodo, kuriame bitų pozicijoje įvyko vieno bito klaida; tokiu būdu vieno bito klaida gali būti automatiškai pataisyta.

Hammingo kode naudojamas tam tikras perteklius. Jeigu k yra pariteto bitų skaičius, tada bendras kodo žodžio ilgis n = 2^k − 1. Iš jų k yra pariteto bitai, tad naudotojo duomenų bitų skaičius yra n − k = 2^k − 1 − k. Pvz., kai k = 3, n = 7, tad lieka 4 duomenų bitai — tai žinomas (7,4) Hammingo kodas. (Šią formulę matote ir originaliame žymėjime: 2 k - 1 {\displaystyle 2^{k}-1}.)

Pavyzdys: (7,4) Hammingo kodas žingsnis po žingsnio

Sudėliokime (7,4) kodo bitų išdėstymą: pozicijos 1, 2 ir 4 skiriamos pariteto bitams p1, p2, p4; duomenų bitai eina pozicijose 3, 5, 6, 7 (taip, kad seką duomenų bitų pažymėsime d1, d2, d3, d4).

Tarkime, norime perduoti duomenis d1 d2 d3 d4 = 1 0 1 1. Jas priskiriame atitinkamoms pozicijoms:

• pozicija 3 = 1, pozicija 5 = 0, pozicija 6 = 1, pozicija 7 = 1

Dabar apskaičiuojame pariteto bitus (naudodami lygią paritetą):

• p1 (poz.1) dengia pozicijas 1,3,5,7 → duomenys: 1,0,1 → XOR = 1 ^ 0 ^ 1 = 0, todėl p1 = 0
• p2 (poz.2) dengia pozicijas 2,3,6,7 → duomenys: 1,1,1 → XOR = 1 ^ 1 ^ 1 = 1, todėl p2 = 1
• p4 (poz.4) dengia pozicijas 4,5,6,7 → duomenys: 0,1,1 → XOR = 0 ^ 1 ^ 1 = 0, todėl p4 = 0

Taigi pilnas kodo žodis (pozicijomis 1–7) bus: 0 1 1 0 0 1 1, t. y. 0110011.

Klaidų aptikimas ir taisymas (sindromas)

Jeigu vienas bitas pernešimo metu pasikeičia, gavėjas perskaičiavęs paritus gaus sindromą, sudarytą iš pariteto neatitikimų (s1, s2, s4), kurie užrašomi dvejetainiu formatu s4 s2 s1 ir nurodo klaidingos pozicijos numerį. Pvz., jeigu pakitęs yra bitas pozicijoje 6, sindromas bus 110 (dvejetainė reikšmė = 6) — taip nustatoma klaidinga pozicija ir tas bitas gali būti apverstas atgal.

Tai leidžia Hammingo kodui:

• pataisyti vieno bito klaidą (single-error correction, SEC);
• aptikti dviejų bitų klaidas (kadangi minimalus Hammingo kodo Hammingo atstumas yra 3, jis gali aptikti iki dviejų klaidų), tačiau dviejų bitų klaidos jis pataisyti negali.

Trumpiausias Hammingo kodas: (3,1)

Trumpiausias Hammingo kodas yra (3,1): vienam duomenų bitui naudojami 2 pariteto bitai. Tokiam kodui galimi tik du galiojantys kodo žodžiai, kurių lygi pariteto atveju yra 000 (duomenų bitui 0) ir 111 (duomenų bitui 1). Visi kiti 3-bitų deriniai yra klaidų rezultatai, kurie pagal artimiausią galiojantį žodį bus pataisyti:

• 001, 010, 100 bus interpretuojami (pataisyti) kaip 000;
• 011, 101, 110 bus pataisyti kaip 111.

Pritaikymas ir išplėtimas

Hammingo kodai plačiai naudojami skaitmeniniame signalų apdorojime, atmintyje (ECC RAM), telekomunikacijose ir kitose srityse, kur svarbi klaidų korekcija. Paprastasis Hammingo kodas pataiso vieno bito klaidas. Jei norima ir dviejų bitų aptikimo, ir vieno bito taisymo (SECDED — single-error correction, double-error detection), prie Hammingo kodo dažnai pridedamas papildomas globalus pariteto bitas.

Ribotumai:

• Hammingo kodas pataiso tik vieno bito klaidas; dviejų ar daugiau bitų klaidų taisymas reikalauja sudėtingesnių kodų.
• Jis reikalauja perteklinių bitų (pariteto), taigi sumažina naudingų duomenų dalį.

Bendros formulės ir pastebėjimai

• Bendra formulė: n = 2^k − 1, kur k — pariteto bitų skaičius.
• Naudotojo (duomenų) bitų skaičius: n − k = 2^k − 1 − k.
• Hammingo kodas yra sisteminis kodas (duomenų bitai gali būti matomi kodo žodyje neperrašyti), todėl jį lengva naudoti praktikoje.

Apibendrinant: Hammingo kodas yra paprastas, efektyvus sprendimas vieno bito klaidų taisymui, ypač ten, kur klaidų dažnis nėra labai didelis, o svarbu automatizuotas klaidų taisymas be didelio papildomo sudėtingumo.

Klausimai ir atsakymai

K: Kas yra Hamingo kodas?

K: Kaip veikia Hamingo kodas?

K: Kas išrado Hamingo kodą?

K: Kam Richardas Hammingas panaudojo savo išradimą?

K: Kas rašoma kaip (N,n), kai kalbama apie Hamingo kodą?

Klausimas: Koks yra trumpiausias įmanomas hamingo kodas?

Paieška pagal raidę