HW01: Hammingov kód (40,32)
Odevzdávání úkolu je ukončeno.
Autor zadání Dávid Šutor
Odevzdávané soubory main.c
Začátek odevzdávání viz diskusní fórum
Další odevzdání navíc do 2025-03-06 24:00
Konec odevzdání 2025-03-12 24:00
Vzorová implementace /home/kontr/pb071/hw01/hamming
Opravy v zadání 2025-03-04 22:39
Kostra úkolu
Vzorové řešení

Predstavenie úlohy

Tvoja mamka prišla za tebou so svojim problémom. Ukázala ti cédéčko, na ktorom má veľmi dôležite dáta, a bojí sa, že sa poškriabaním zničia. Preto ti neostáva nič iné[1], ako napísať vlastné kódovanie schopné odhaliť a opraviť chyby.

Zadanie

Vašou úlohou bude napísať program, ktorý bude vedieť kódovať a dekódovať prúd bajtov zo štandardného vstupu. Výsledok kódovania, resp. dekódovania sa vypíše na štandardný výstup.
Na kódovanie sa použije naša upravená verzia Hammingovho kódu, ktorého algoritmus je popísaný v nasledujúcich dvoch sekciách.

Kódovanie

Kódovať budeme každú štvoricu bajtov zo štandardného vstupu na výstupnú päticu bajtov. V rámci tohto textu budeme nazývať túto vstupnú štvoricu informačné slovo a výstupnú päticu bajtov kódové slovo.

Algoritmus si vysvetlíme na príklade kódovania informačného slova $00010203_{\text{HEX}}$ (hodnota pozostáva zo 4 bajtov zapísaných v hexadecimálnej sústave).

Pre lepšiu vizualizáciu slov si každý bajt uložíme do tabuľky pod seba a rozpíšeme na osmicu bitov. Každá bunka tabuľky obsahuje bit a jeho pozíciu. Pozíciu budeme značiť v dvojkovej sústave, kvôli lepšiemu porozumeniu algoritmu.

ilustrations Information word
Pozícia v našom ponímaní neodpovedá skutočnému umiestneniu bitov v informačnom slove. Teda pozícia najmenej významného bitu informačného slova sa nenachádza na pozícii 0 ale na 31. Treba na to myslieť pri implementovaní algoritmu.
Algoritmus

  1. Všetky bity informačného slova uložíme do kódového slova, pričom nevypĺňame nultú pozíciu, poslednú pozíciu a pozície, ktoré sú mocninami dvojky. Teda pozície 0, 1, 2, 4, 8, 16, 32 a 39 sa preskočia. Bity začneme ukladať od pozície 3.

ilustrations Encoded without parity

  1. Nultý a posledný bit kódového slova nastavíme na nulu

ilustrations Encoded word first and last

  1. Bity na pozíciách mocniny dvojky nazveme paritné bity. Hodnota paritného bitu na pozícii i-tej mocniny dvojky ($2^i$) sa vypočíta ako bitový exkluzívny súčet (XOR $\oplus$) bitov, ktorých pozícia v dvojkovej sústave má jednotku na i-tom bite.

Príklad

Ukážeme si konkrétny výpočet paritného bitu na pozícii 8.

Číslo 8 reprezentujeme v binárnej sústave ako 001000. Pre výpočet hodnoty paritného bitu sa musíme pozerať na bity, ktorých pozícia v binárnej sústave je v tvare XX1XXX, kde X je buď 0 alebo 1 (viď animácia nižšie). Výpočet spočíva v tom, že spravíme XOR bitov na pozíciách XX1XXX, samozrejme okrem pozície paritného bitu 001000.

  • $p_{001000} = b_{001001} \oplus b_{001011} \oplus b_{001100} \oplus \cdots \oplus b_{011111} = b_{011100} = 1$ pričom $p_x$ označuje paritný bit na pozícii x a $b_x$ označuje bit na pozícii x.

parity
Výpočet paritných bitov

Takže výsledné kódové slovo bude $2080040806_{\text{HEX}}$.

ilustrations Encoded word final

Dekódovanie

Dekódovanie popíšeme na našom predošlom kódovom slove $2080040806_{\text{HEX}}$. Vzhľadom k tomu, že sme informačné bity pri kódovaní nemodifikovali, tak stačí, aby sme z kódového slova vytiahli informačné slovo presne opačne, ako pri kódovaní. Teda zoberieme prvých 32 bitov, ktoré nie sú na pozíciach mocniny dvojky alebo na nultej a poslednej pozícii. Tým pádom dostaneme naspäť informačné slovo $00010203_{\text{HEX}}$.

Paritné bity využijeme v rámci bonusového rozšírenia.

Okrem papiera a ceruzky si algoritmus môžete vyskúšať v našej interaktívnej aplikácii. Táto aplikácia avšak nepočíta paritné bity, ale umožňuje si ich jednoducho vyklikať.

Požiadavky

Kostra zadania obsahuje dve prázdne funkcie, encode() a decode(). Vašou úlohou je tieto dve funkcie doimplementovať podľa nasledujúcich požiadaviek:

bool encode(void);

Funkcia postupne číta bajty zo štandardného vstupu a každé 4 bajty zakóduje na 5 bajtov, ktoré vypíše na štandardný výstup. Použite kódovanie popísané v sekcii Kódovanie.

Ak celkový počet bajtov na vstupe nebude deliteľný 4, tak sa bajty vyplnia nulovými bajtmi sprava. Napríklad vstup $010203_{\text{HEX}}$ sa zakóduje rovnako ako $01020300_{\text{HEX}}$.

Je postačujúce, aby encode() vrátila vždy true. Jediný chybový stav je v prípade, keby nastala chyba pri čítaní zo štandardného vstupu. Tento stav nemusíte ošetrovať.

bool decode(void);

Analogicky táto funkcia bude čítať bajty zo štandardného vstupu a každých 5 bajtov dekóduje na pôvodné štyri bajty postupom popísaným v sekcii Dekódovanie. Na rozdiel od encode(), v prípade, že celkový počet bajtov na vstupe nebude deliteľný 5, tak funkcia vráti false a na štandardný chybový výstup vypíše chybovú hlášku "Wrong code word" a znak konca riadka. V opačnom prípade vráti true.

Pre vypísanie hlášky na štandardný chybový výstup použite napríklad príkaz
fprintf(stderr, "Wrong code word\n"). Znak konca riadka je nutný a testy ho tam budú očakávať.
Program berie dva prepínače. -e na kódovanie, ktorý zavolá funkciu encode() a -d na dekódovanie, ktorý zavolá funkciu decode().

Bonusové rozšírenia

Detekcia a oprava jednoduchej chyby [15 b]

Rozšírte funkciu decode() aby vo vstupnom kódovom slove vedela na informačných bitoch rozoznať a opraviť jednoduchú chybu a na paritných bitoch rozoznať jednoduchú chybu.

Slovo s jednoduchou chybou sa líši od kódového slova práve v jednom bite.

Algoritmus

  1. Urobíme XOR pozícií bitov, ktoré sú nastavené na hodnotu 1.

  2. Vetvíme na základe výsledku XORu:

    1. Ak výsledok je 0, tak nenastala žiadna chyba.

    2. Inak výsledok reprezentuje pozíciu bitu, na ktorom nastala chyba.

Príklad

Pre naše príkladové kódové slovo $2080040806_{\text{HEX}}$ spravíme chybu v bite na pozícii 3 a dostaneme slovo $3080040806_{\text{HEX}}$.

ilustrations Encoded word final error

Ak spravíme XOR všetkých pozícií bitov s hodnotou 1 tak dostaneme:

Pozície v dvojkovej sústave ktoré XORneme

000010
000011
001000
010101
011100
100101
100110
------
000011

Pri detekcii chyby program vypíše na štandardný chybový výstup "One-bit error in byte X" a znak konca riadka, kde X je poradie prečítaného bajtu zo vstupu. Indexuje sa od nuly.
V prípade detekcie chyby na informačnom bite sa chyba musí aj opraviť. Program pokračuje vo výpočte v prípade detekcie chyby.

Požiadavky na návratovú hodnotu decode() zostávajú nezmenené. Z toho vyplýva, že v prípade detekcie chyby bude funkcia aj naďalej vracať true.

Užitočné Poznámky

  • Pre načítanie znaku zo vstupu a vypísanie znaku na výstup si vystačíte s funkciami getchar() a putchar().

  • Odporúčame používať typy s pevnou dĺžkou definované v stdint.h.

  • Vašu implementáciu si môžete porovnať so vzorovou, ktorá sa nachádza na aise. Umiestnenie vzorovej implementácie je:

/home/kontr/pb071/hw01/hamming

Ako testovať?

Jednotkové testy

Odporúčaný spôsob, ako otestovať vašu implementáciu, je napísaním jednotkových testov.

V kostre nájdete dve rôzne knižnice na testovanie. Prvej knižnici CUT prislúcha súbor tests-cut/tests-mine.c a knižnici CLI súbor tests-cli/tests-mine.sh. Obidva súbory obsahujú podrobný popis, ako si napísať vlastné testy.

Na kompiláciu testov odporúčame použiť cmake. V zložke, v ktorej vám vygeneruje kompilačné súbory, zadajte make hamming-tests-cli na spustenie CLI testov. CUT testy budú skompilované do jedného spustitelného súboru hamming-tests-cut po zadaní príkazu make.

Kostra taktiež obsahuje súbor tests-cut/tests-nanecisto.c, ktorý zodpovedá testom nanečisto, voči ktorým sa bude vyhodnocovať vaše riešenie.

Pri písaní testov sa vám určite bude hodiť naša interaktívna aplikácia.

Príkazový riadok

Ďalší spôsob, ako otestovať vašu implementáciu na Linuxe, je použiť napr. príkaz echo:

echo -en  "\x00\x01\x02\x03" | ./hamming
echo -en  "\x20\x80\x04\x08\x06" | ./hamming -d

Keďže nie všetky bajty sú zobraziteľné, je potrebné vedieť výstup nášho rozumne zobraziť. Našťastie na to môžeme použiť napr. programy hexdump alebo xxd.

echo -en  "\x00\x01\x02\x03" | ./hamming | hexdump -C
# Výstup
# 00000000  20 80 04 08 06                                    | ....|
# 00000005

echo -en  "\x20\x80\x04\x08\x06" | ./hamming -d | xxd
# Výstup
# 00000000: 0001 0203                                ....

Na Windows odporúčame použiť Windows Subsystem for Linux alebo Git Bash

Niektoré Linuxové distribúcie nepodporujú všetky prepínače. V takom prípade testujte na svoj kód na aise.

Čo znamená príkaz echo -en "\x00\x01\x02\x03" | ./hamming?

  • spusti príkaz echo s prepínačmi e a n s argumentom \x00\x01\x02\x03.

    • prepínač e zapína interpretovanie znaku \

    • prepínač n vypína pridanie znaku nového riadka na koniec výstupu

    • argument \x00 reprezentuje bajt s hodnotou nula. Hodnota je v šestnástkovej sústave. Analogicky platí pre \x01, \x02 a \x03.

  • znak | spôsobí, že výstup programu echo sa presmeruje na vstup programu ./hamming.

1. Vážne nie

Opravy v zadání

Extend early deadline by a day
2025-03-04 22:39 Roman Lacko

Extend early deadline by a day

a977860 2025-03-04 22:39 Roman Lacko 
 -6,3 +6,3  solution-path: "/home/kontr/pb071/hw01/hamming"
 publish: now
-deadline-early: 2025-03-05 24:00
+deadline-early: 2025-03-06 24:00
 deadline-final: 2025-03-12 24:00