Feladat: I.163 Korcsoport: - Nehézségi fok: -
Füzet: 2007/szeptember, 358 - 359. oldal  PDF  |  MathML 
Témakör(ök): Feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A digitális adatátvitel során fellépő hibák javítására alkalmazott kódok közül az egyik leghíresebb Richard Wesley Hamming nevéhez fűződik. A kód egyik változata 7 bitenként legfeljebb egy ú.n. átállítódásos hiba (az átvitel során egy bit értéke invertálódik, azaz ellentettjére változik) javítására képes.
A kódolás menete a következő. A továbbítandó adatokat 4 bites egységekre bontjuk, majd ezeket 3 ellenőrzőbittel egészítjük ki az alábbiak szerint:

 
 
(Ahol ⊕ a modulo 2 összeadás, a ,,kizáró vagy'' művelet: x1⊕x2⊕...⊕xn=1 akkor és csak akkor, ha x1,x2,...,xn bitek közül páratlan sok egyes.)
Az így kapott 7 bites k7...k1 kódszókat visszük át, a vevő által érzékelt (esetleg hibás) kódot jelöljük f7...f1-gyel.
A dekódolás a következőképp zajlik. A megfelelő fj-kből újból kiszámoljuk az ellenőrzőösszegeket, és az eredményt összevetjük az f4, f2 és f1 ellenőrzőbitekkel. (Tehát például f2-t az f7⊕f6⊕f3 összeggel.) Azokat az i indexeket, melyekre az fi ellenőrzőbit értéke helytelen, összeadjuk. Ha az így kapott érték 0, akkor a kódszó hibátlan, egyébként pedig, és itt mutatkozik meg a kód igazi szépsége, a hiba helyét adja, így azt invertálással rögtön javíthatjuk. Ezután a (már) helyes kódszó megfelelő bitjeit kiolvasva megkapjuk az adatot.
Írjunk programot, amely attól függően, hogy első parancssori argumentuma ,,be'' vagy ,,ki'', a második argumentumként kapott fájlt be-, illetve kikódolja a harmadik argumentumként kapott fájlba. A fájlokban az adat- és kódszavak szóközzel elválasztott 0‐1 sorozatok legyenek. A kódbitek kódszón belüli sorrendje tetszőleges.
 
 
(Az első kódban az f4 ellenőrző bit jelez hibát, így a 4. bitet, f4-et invertáljuk. A második kód helyes, a harmadikban pedig f4 és f2 is hibát jelez, így a 6. bitet, f6-ot kell javítani.)
Beküldendő a program forráskódja (i163.pas, i163.cpp, ...), valamint a program rövid dokumentációja (i163.txt, i163.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.