Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem I. 163. (September 2007)

I. 163. Error detecting and correcting codes are frequently used in digital data transfer. A famous code of Richard Wesley Hamming can detect and correct a parity bit error occurring at most once in every block of 7 bits. (A parity error occurs when one bit is changed to its opposite.) To code the message one has to partition the data into blocks of 4 bits and extend each block with 3 checking bits as follows:

(The \oplus sign denotes addition modulo 2, that is ``exclusive or'': x_1\oplus x_2\oplus
\dots \oplus x_n=1 if and only if an odd number of the bits x1,x2,...,xn are equal to 1.)

We then transmit this word k7...k1 consisting of 7 bits. The received message (possibly containing an error) is denoted by f7...f1.

The message is decoded as follows. We recompute the check-sums using the corresponding fj's and the result is compared with the checking bits f4, f2 and f1, that is, for example, f2 with the sum f_7\oplus f_6\oplus f_3. We sum those i indices for which the value of the checking bit fi is incorrect. If this sum is 0, then we consider this word as correct. Otherwise, and this is the main advantage of this method, the sum gives the position of the error, so it can be corrected by simply inverting that bit. Finally we only need to read off the (now correct) bits and have the original message.

Write a program that performs Hamming encoding or decoding. The first argument is en or de, the second argument is the name of the input file, while the third argument is the name of the output. The files consist of 0-1 sequences separated by spaces. The order of the code bits within a code word is arbitrary.

(Checking bit f4 in the first code shows the position of the error is 4, so we invert that bit. The second code is correct. We see that f4 and f2 detected an error, so we should correct the sixth bit f6.)

The source code of your program (i163.pas, i163.cpp, ...) together with a short documentation (i163.txt, i163.pdf, ...) should be submitted, specifying also which developer environment can be used to compile your program.

(10 pont)

Deadline expired on October 15, 2007.


Sorry, the solution is available only in Hungarian. Google translation

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


Statistics:

15 students sent a solution.
10 points: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 points:2 students.
7 points:2 students.
6 points:1 student.
4 points:1 student.

Problems in Information Technology of KöMaL, September 2007