Az I. 163. feladat (2007. szeptember)

I. 163. 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: akkor és csak akkor, ha x₁,x₂,...,x_n bitek közül páratlan sok egyes.)

Az így kapott 7 bites k₇...k₁ kódszókat visszük át, a vevő által érzékelt (esetleg hibás) kódot jelöljük f₇...f₁-gyel.

A dekódolás a következőképp zajlik. A megfelelő f_j-kből újból kiszámoljuk az ellenőrzőösszegeket, és az eredményt összevetjük az f₄, f₂ és f₁ ellenőrzőbitekkel. (Tehát például f₂-t az összeggel.) Azokat az i indexeket, melyekre az f_i 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 f₄ ellenőrző bit jelez hibát, így a 4. bitet, f₄-et invertáljuk. A második kód helyes, a harmadikban pedig f₄ és f₂ is hibát jelez, így a 6. bitet, f₆-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ó.

(10 pont)

A beküldési határidő 2007. október 15-én LEJÁRT.

Megoldás

A feladatra sok jó megoldás érkezett. Ezek közül is a két legszebb megoldást tesszük közzé: - Földes Imre (Szolnok, Verseghy Ferenc Gimnázium, 11. osztály) megoldása Pascal nyelven - Nagy Zoltán (Kaposvár, Munkácsy Mihály Gimnázium és Szakközépiskola, 11. osztály) megoldása C nyelven - Mintamegoldás C++ nyelven

Típushibák, tanulságok

A problémák döntő része a tesztelés hiányából adódott.

Néhány megoldás a példabemenetre helyesen lefutott, ugyanakkor a további tesztadatokra már nem. Ez általában akkor fordul elő, ha a programba a példára alapozott feltevéseket építünk be (pl. az első bit mindig 1-es), implementációs hiba van a kódban, de a példa végrehajtása során a vezérlés nem kerül a hibás kódrészletre (pl. egy ellenőrzőösszeg nem működik, de nem fordul elő ilyen hiba), vagy, legrosszabb esetben, még rá is kerül, de a tesztadat felépítése olyan, hogy a hibás eredmény épp egybeesik a helyessel (pl. kikódolásnál rossz biteket olvasunk ki adatként).

A problémák másik része az adatok beolvasásával volt kapcsolatos.

Több megoldás nem kezelte helyesen, ha a fájl végén is volt szóköz. Noha ilyen esetben is elvártuk volna helyes működést, mivel a megoldások szóköz nélkül jól működtek, ezért nem vontunk le pontot. Egy, a feladat szövegének megfelelő, ideális megoldás természetesen nemcsak a fájlvégi szóközt kezeli, hanem például a többszörös szóközöket is. Több ilyen megoldás is érkezett, ezeknek nagyon örültünk.

Súlyos hibának tekintettük, ha a program egy fix hosszúságú tömbbe vagy egy (maximum 255 karakter hosszú) Pascal-sztringbe kívánta beolvasni az egész fájlt, hisz ekkor elegendően hosszú tesztfájl esetén az menthetetlenül túlcsordult (vagy a tesztadat csonkolódott). Ha a feladatban nincs specifikálva a bemenet hossza, akkor azt mindig részletekben olvassuk, mindig legfeljebb annyit, amennyit feltétlen kell!

Összegezve: a jövőben figyeljünk oda a specifikációk pontos betartására, a megfelelő beolvasásra, illetve a megfelelő tesztelésre - ha kell, generáljunk magunk további tesztadatokat!

coder.cpp

foldes.zip

nagy.zip

Statisztika:

15 dolgozat érkezett.
10 pontot kapott:	Adrián Patrik, Erdős Gergely, Fábián András, Földes Imre, Juhász Péter, Molnár Gábor, Nagy Zoltán, Véges Márton, Vladiszavlyev Gergő.
8 pontot kapott:	2 versenyző.
7 pontot kapott:	2 versenyző.
6 pontot kapott:	1 versenyző.
4 pontot kapott:	1 versenyző.

A KöMaL 2007. szeptemberi informatika feladatai