Kódok 6. szakkör

6. szakkör

Az elõadó betegsége miatt az óra kissé szokatlan volt. A nebulók a 4.7, 5.10 feladatok megoldásával folytatták a Kódok feladatgyûjtemény feldolgozását, majd egy esszét olvashattak a CD mûködésének matematikai alapjairól.
Új házi feladat nincs, de korábbról megmaradt a hétszögminták, 5.11, az Általános Hamming-kód és az "Ideális 1001-es".

4.7 Összehasonlítunk három kódot! Mindhárom kód kilenc szóból áll, mindegyik egy hárombetûs ABC-t használ.
k₁) A legegyszerûbb: A szavak kétbetûsek, a kilenc kódszó az összes kétbetûs szó.
k₂) Mindent háromszor: A szavak hatbetûsek és úgy készülnek, hogy a kétbetûs szót háromszor írjuk le egymás után.
k₃) A sûrû: A szavak négybetûsek, a 4.6 feladatban meghatározott 1-hiba javító tökéletes kódot alkotják.
Tegyük fel, hogy egy betû a kommunikáció során 10% eséllyel megváltozik és 90% eséllyel jól továbbítódik. k₂ és k₃ esetén a kiolvasott jelsorozatot mindig a tõle legkevesebb jelben eltérõ kódszóra változtatjuk. Ha ez nem egyértelmû, akkor nem javítunk. Határozzuk meg a három esetben külön-külön, hogy mi az esélye, hogy egy szót úgy olvasunk ki, ahogy elküldték!

Megoldás k₁ esetén mindkét jelet jól kell kiolvasni, így 0,9²= 0,81 alapján 81% az esély.
k₂ esetén mindkét jel három példányából háromnak vagy kettõnek kell helyesen megérkeznie, tehát a számolás: (0,9³ + 3·0,1·0,9²)²= 0,944784, azaz 94,4784% az esély.
k₃ esetén a négy jelbõl négynek vagy háromnak kell helyesnek lennie, így 0,9⁴ + 4·0,1·0,9³ = 0,9477 alapján 94,77% az esély.

5.10 (Dienes Péter javaslata)
Hanyag Hugó az 1, 2, 3, ..., 16 számok egyikére gondolt. Egy-egy cetlire kell fölírni kérdéseinket, s mind odaadni neki, majd amikor ráér egyszerre mindegyikre válaszol fog. De lehet rá számítani, hogy az egyik választ elveszti mielõtt az eljutna hozzánk. Legalább hány kérdésre van így szükség ahhoz, hogy kitaláljuk a gondolt számot?

Megoldás Öt kérdés nyilván szükséges, de ennyi elég is. Öt megfelelõ kérdés megkapható az 5.9 feladatra adott bármelyik konstrukció mintájára (lásd a 18. szakkör anyagát).
Most 16 db olyan 5 hosszúságú 0 - 1 sorozatot keresünk, amelyek közül bármelyik kettõ legalább két helyen eltér egymástól. Ha ugyanis az egyik kérdésre nem érkezik válasz, azaz a sorozatokban az egyik helyen álló elem eltûnik, akkor továbbra is 16 különbözõ sorozatot kell kapjunk. Ez felel meg annak, hogy a négy megmaradt kérdésre adott válaszból minden esetben kitalálható a gondolt szám. Az alábbi táblázat oszlopaiba 16 megfelelõ sorozatot írtunk be.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1. sor	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
2. sor	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
3. sor	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
4. sor	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
5. sor	0	1	1	0	1	0	0	1	1	0	0	1	0	1	1	0

Látható, hogy az utolsó sor az elõzõekhez hozzátett paritásjelzõ-bit. Az öt kérdés közül az elsõ négy megegyezik az 5.8 b) feladat megoldásaként konstruált négy kérdéssel, az ötödik pedig azokra a számokra kérdez rá, amelyekre addig páratlan sokszor kérdeztünk rá. Így összességében minden számra páros sokszor kérdezünk rá, tehát ha mind az öt kérdésre kapnánk választ, akkor páros sok "Igen"-t hallanánk. Ezért, ha egy válasz hiányzik, akkor az már kitalálható a többi négybõl.

Megjegyzések:
1. Az 5.9 feladatra (hazudós barkochba) adott II. konstrukció szellemében fenti kérdéseink így is írhatók:

"x₈= 0?"; "x₄= 0?"; "x₂= 0?"; "x₁= 0?"; "x₈ + x₄ + x₂ + x₁= 0?".
2. Táblázatunk oszlopai most egy 16 kódszóból álló ötbetûs 1-törlés javító kódot alkotnak.

"Ideális 1001-es" Ebben a feladatban a természetes számok bizonyos részhalmazait keressük. A számokat mindig kettes számrendszerben leírva képzeljük, illetve alább így is említjük õket. Két számot nem a szokásos módon adunk össze, hanem kettes számrendszerbeli alakjuk megfelelõ jegyeit modulo 2, és átvitel nélkül adjuk össze (pld 1100110 + 10011 = 1110101).
A természetes számok (pontosabban azok kettes számrendszerbeli alakjainak) egy I₁₀₀₁ részhalmazát "ideális 1001-es"-nek nevezzük,
1. Ha h I₁₀₀₁-ben van, akkor h0 is I₁₀₀₁-ben van; (h0 a h dupláját, tehát azt a számot jelöli, amelyet úgy kapunk, hogy h mögé írunk egy 0-t)
2. Ha h és j is I₁₀₀₁-ban van, akkor h + j is ott van.
3. 1001 is I₁₀₀₁-ben van (itt 1001 az egy-nulla-nulla-egy számot, azaz a kilencet és nem az ezeregyet jelenti).
Hány "ideális 1001-es" részhalmaza van a természetes számok halmazának?

Hétszögminták Ebben a feladatban egy szabályos hétszög csúcsaira írunk 0-t vagy 1-et. Összesen 2⁷=128 ilyen kitöltés van. A kitöltések egy I₇ részhalmaza "7-szögre ideális",
1. ha h az I₇-ben van, akkor h bármely (n·360°/7-kal való) elforgatottja is I₇-ben van.
2. ha bármely két I₇-beli kitöltés csúcsonként és mod 2 számított összege is I₇-ben van.

A kitöltéseknek hány "7-szögre ideális" részhalmaza van?

5.11 (Juhász Istvántól és Szegedy Balázstól is hallottam)
Egy kém az ellenséges ország televíziójánál dolgozik. Esténként alkalma van az adásba kerülõ 8×8-as fekete fehér tábla egyetlen mezõjének színét megváltoztatni. Nem feltétlenül szükséges változtatnia. Sajnos sohasem tudja elõre, hogy milyen mintázatú lesz a 64 mezõ, amikor eléje kerül. Hányféle információt tud így küldeni a TV-n keresztül?