Kódok 2. szakkör

Megoldás a) Egy-egy kérdés a szóbajövõ számok halmazát két részhalmazra bontja: azokra, amelyekre igen a válasz (ha az a szám a gondolt szám) és azokra, amelyekre nem a válasz. "Rossz esetben" olyan választ kapunk, amely azt mutatja, hogy a nagyobb, pontosabban a nem kisebb részhalmazban van a gondolt szám. Ezért, ha biztosra megyünk nem tehetünk jobbat, minthogy kérdéseinkkel megfelezzük a lehetõségeket. 4 kérdés kell a kitaláláshoz, és ennyi elég is.

b) Most is szükséges a 4 kérdés, és elég is. Ehhez azt kell elérnünk, hogy a következõ kérdés az elõzõre adott bármely válasz esetén megfelezze a lehetõségeket.

I. konstrukció Az alábbi megoldás négy kérdése mind így kezdõdik: "A gondolt szám az itt megadott halmazban van?". A négy megadott halmaz:

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

II. konstrukció Az iménti megoldást a diákok gyakran megtalálják, de ritkán veszik észre, hogy teljesen megegyezik a következõvel. Írjuk fel a gondolt számnál eggyel kisebb számot kettes számrendszerben négy jeggyel (pótoljuk az elejét 0-kal, ha szükséges)! Ezek a felírások az alábbi táblázat oszlopaiban láthatók.

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
n-1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
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

Kérdéseink:
1. Az így kapott szám balról (a táblázatban fölülrõl) számított elsõ jegye 0?
2. Az így kapott szám balról (a táblázatban fölülrõl) számított második jegye 0?
3. Az így kapott szám balról (a táblázatban fölülrõl) számított harmadik jegye 0?
4. Az így kapott szám balról (a táblázatban fölülrõl) számított negyedik jegye 0?

A négy válasz alapján megkapjuk a gondolt számnál eggyel kisebb szám kettes számrendszerbeli alakját, így ki tudjuk találni a gondolt számot. Látható, hogy táblázatunk négy sora, megfelel az I. konstrukció négy kérdésének. Az adott sorban az n-1 számnak megfelelõ oszlopban pontosan akkor áll 0, ha az elõzõ megoldás megfelelõ kérdésében n benne volt a kijelölt halmazban.

1.1 Visszatérünk az 1.1 a), b) feladatokhoz, egy általánosító kérdés erejéig. Végezzünk két mérést: az elsõben az 1., 2., ... 10., széria súlyaiból rendre a₁, a₂, ..., a₁₀; a másodikban a szériákból rendre b₁, b₂, ..., b₁₀ darabot teszünk fel a mérlegre (a₁, a₂, ..., a₁₀, b₁, b₂, ..., b₁₀nemnegatív egész számok). Adjunk meg olyan algebrai feltételt a felsorolt darabszámokra vonatkozólag, amely alapján eldönthetõ, hogy a két mérésbõl kitalálható-e hogy melyik széria adatai hibásak vagy nem található ki.

Elemezzük például az alábbi három tervet:

széria:	1.	2.	3.	4.	5.	6.	7.	8.	9.	10.
1. mérés (a_i)	1	2	3	4	5	6	7	8	9	10
2. mérés (b_i)	0	1	2	3	4	5	6	7	8	9

széria:	1.	2.	3.	4.	5.	6.	7.	8.	9.	10.
1. mérés (a_i)	0	1	2	3	4	5	6	7	8	9
2. mérés (b_i)	1	2	4	8	16	32	64	128	256	512

széria:	1.	2.	3.	4.	5.	6.	7.	8.	9.	10.
1. mérés (a_i)	1	1	1	1	1	1	1	1	1	1
2. mérés (b_i)	0	1	2	3	4	4	3	2	1	0

Megoldás

Az A) terv jó, mert a két mérés különbsége, épp az 1.1 a) feladat megoldásában adott mérést állítja elõ, az 1. mérés pedig az 1.1 b) feladat megoldásának mérése.

A B) terv nem jó, a 2. és 3. szériákkal van a gond. Ha a 2. széria súlyai 2 kg-mal nehezebbek az elõírt értéknél, akkor ugyanazokat az eltéréseket érzékeljük, mint amikor a 3. széria súlyai 1 kg-mal nehezebbek az elõírtnál.

A C) tervnél hasonló jellegû a hiba az 1. és a 10., a 2. és a 9., stb. szériapárok viszonyában.

Általában, akkor nem tudjuk eldönteni, hogy a k-adik vagy a j-edik széria a hibás, ha van olyan ε_kés olyan ε_j nemnulla hibatag, amelyre a_k·ε_k = a_j ·ε_j és ugyanakkor b_k·ε_k = b_j·ε_j. Pontosan akkor vannak ilyen ε-ok, ha a_k:a_j = b_k:b_j, azaz ha az (a_k; b_k), (a_j; b_j) vektorok egyállásúak.

Továbbra is házi feladat az 1.2 feladatra vonatkozó hasonló jellegû diszkusszió: ott egy mérési tervhez meg kell adni az elõírt mérések számát - a továbbiakban ezt n jelöli - továbbá nemnegatív egész számokkal kell kitölteni az ûrlap 1., 2., 3., 4., 5. oszlopait. Jelölje az így kapott számtáblázat i-edik sorának (i = 1, 2, ..., n) j-edik oszlopába (j = 1, 2, 3, 4, 5) írt számot a_ij (a_ij természetes szám). Tehát a_ij -vel jelölöm az i-edik mérésnél a j-edik szériából vett súlyok számát. Határozzunk meg az a_ij számokkal kapcsolatos olyan algebrai feltételt, amely azzal ekvivalens, hogy a mérésekbõl meghatározhatók a súlyok (feltéve, hogy legfeljebb egy hibás az eredmények közül).

5.2 Egy hajó és utasai, összesen 100 fõ, Ungabunga szigetén az emberevõk fogságába esett. Tudják, hogy másnap reggel a kannibálok leültetik õket egymás mögé, és mindegyikük fejére egy-egy piros vagy kék sapkát húznak. Mindenki csak az összes elõtte ülõ ember fején lévõ sapkát fogja látni, a sajátját és a mögötte ülõkét nem. A leghátsó embertõl kezdve sorban mindenki hangosan mondhat majd egy színt: pirosat vagy kéket. A végén azt engedik szabadon, aki saját sapkája színét mondta, aki nem találta el, azt bizony megeszik. A kannibálok szigorúak, ha bárki mást tesz, minthogy a lehetõ legegyszerûbben kimondja a "piros" vagy a "kék" szót, akkor senkinek sem kegyelmeznek.
A foglyoknak még egy esélye van. Most este még összebeszélhetnek. Szeretnék, hogy minél többen megszabaduljanak. Hány fogoly tud biztosan megmenekülni?

I. megoldás 50 rabot szabadítok meg, hátulról számítva minden párosadikat. A páratlan sorszámú rabok bemondják az elõttük levõ sapkájának színét, a páros sorszámú rabok pedig a saját sapkájuk színét. Így az utóbbiak mind megszabadulnak, a többiek csak szerencsés esetben menekülhetnek meg.

II. megoldás 93 rabot szabadítok meg. A leghátsó hét rab csak az elsõ 93-mal törõdik. Megszámolják, hogy azokon összesen hány piros sapka van, ezt a számot felírják maguknak kettes számrendszerben (ez legfeljebb hétjegyû), és ennek jegyeit mondják be sorban (pld "piros" jelenti az "1"-et). Az elsõ 93 mindegyike tudja, hogy rajtuk összesen hány piros sapka van, mindegyik hallja a mögötte levõk sapkájának színét (a 93-ból), látja az elõtte levõkét, így a sajátját ki tudja találni és bemondja.

III. megoldás Az elõzõ megoldás javítható. 99 rabot is ki lehet szabadítani.
Az embereknek szükségtelen tudni az összes piros sapka pontos számát, elég tudni a piros sapkák számának paritását. Megállapodnak pld abban, hogy a leghátsó ember "piros"-at mond, ha az elõtte levõ 99 ember közül összesen páratlan soknak a fején lát piros sapkát, és kéket mond az ellenkezõ esetben. Így a 99 emberbõl már mindenki tudja, hogy rajtuk összesen páros vagy páratlan db piros sapka van, látja az elõtte levõk sapkáját, hallja a mögötte levõk sapkájának színét, így a sajátját is kitalálhatja és bemondja.
100 rab nyilván csak szerencsés esetben szabadulhat, a leghátsó nem kap információt saját sapkájáról.

I. megoldás Legyen x₈ ≡ x₁ + 2x₂+ 3x₃+ 4x₄+ 5x₅+ 6x₆+ 7x₇ (mod 10). Az 1.1 d) feladat I. megoldásának mintájára látható, hogy két szomszédos jegy felcserélõdése esetén a jobb oldali kifejezés értéke változik, így az összefüggés nem marad érvényben.

Megjegyzés: Sajnos baj van a 7. és 8. jegyek cseréjénél. Ilyenkor a bal oldal is változik, nem csak a jobb, az összefüggés esetleg érvényben marad. Lehetséges, hogy egyszerre teljesüljön az
x₁ + 2x₂+ 3x₃+ 4x₄+ 5x₅+ 6x₆+ 7x₇≡ x₈ (mod 10) és a x₁ + 2x₂+ 3x₃+ 4x₄+ 5x₅+ 6x₆+ 7x₈≡ x₇(mod 10) összefüggés is. Valóban a két kongruencia kivonása és rendezés után
8(x₈ - x₇) ≡ 0 (mod 10), ami teljesül pld x₈ = 6, x₇ = 1 esetén, tehát ha egy jó nyolcjegyû szám utolsó két jegye 6 és 1, akkor az utolsó két jegy cseréjét nem veszi hibának a rendszer.

II. megoldás Legyen x₈ ≡ x₁ + x₃+ x₅+ x₇ (mod 10). Két szomszédos jegy felcserélõdése esetén a jobb oldali kifejezés értéke változik, így az összefüggés nem marad érvényben.

Megjegyzés: Sajnos most is baj van a 7. és 8. jegyek cseréjénél. Lehetséges, hogy egyszerre teljesüljön az
x₁ + x₃+ x₅+ x₇≡ x₈ (mod 10) és a x1 + x₃+ x₅+ x₈≡ x₇(mod 10) összefüggés is. Valóban a két kongruencia kivonása és rendezés után
2(x₈ - x₇) ≡ 0 (mod 10), ami az elõzõével analóg hibát okoz.

I'. megoldás Legyen x₈ ≡ 0x₁ + 1x₂+ 2x₃+ 3x₄+ 4x₅+ 5x₆+ 6x₇ (mod 10). Most a 7. és 8. jegy felcserélését firtató kongruencia-rendszer a

7(x₈ - x₇) ≡ 0 (mod 10) kongruenciához vezet, amelybõl már következik, hogy x₈ ≡ x₇ (mod 10), azaz x₈= x₇, azaz nincs igazi csere.

II'. megoldás Legyen x₈ ≡ x₂ + x₄+ x₆ (mod 10). Az elsõ hét jegybõl két szomszédos cseréjénél csak a jobb oldal, az utolsó két jegy cseréjénél csak a bal oldal értéke változik, tehát a kongruencia nem marad fenn.

Elméleti összefoglaló a kódokról:

Legyen adva egy tetszõleges abc (betûkészlet, a kódolásnál tipikusan {0,1}) és egy n pozitív egész (a szavak hossza).

Az abc elemeibõl készíthetõ n hosszúságú sorozatokat szavaknak nevezzük.

Két szó távolságán (Hamming távolság) azoknak a helyeknek a számát értjük, amelyeken különböznek egymástól.

(Az AABC, CBBC szavak távolsága pld. 2, mert az elsõ és a második helyen térnek el egymástól.)

Az általános megközelítésben kódon a szavak egy tetszõleges részhalmazát értjük. A kódba tartozó szavak a kódszavak.

Úgy képzeljük, hogy két fél kommunikál egymással és a kódszavak az értelemmel bíró jelek. Elõfordulhat, hogy a kommunikáció során egy kódszó sérül (a küldõ hibázott, a kommunikációs csatorna zaja módosította az üzenetet vagy a fogadó fél hibásan olvasta ki a szót). A kapott szót úgy javítjuk, hogy átírjuk a tõle legkisebb (Hamming) távolságra lévõ egyik kódszóra.

A kód k-hiba javító, ha bármelyik kódszavában k vagy annál kevesebb betû módosulása esetén a fenti hibajavító módszer mindig egyértelmûen helyreállítja az eredeti üzenetet.

A kód k-hiba jelzõ, ha bármelyik kódszavában k vagy annál kevesebb betû módosulása esetén nem juthatunk másik kódszóhoz, azaz a fogadó fél észre tudja venni, hogy hiba van, mert nem kódszót olvas.

A kód k-törlés javító, ha bármelyik kódszavában k vagy annál kevesebb betû törlõdése (olvashatatlansága) esetén hiányzó k betû csak egyféleképpen tölthetõ ki úgy, hogy kódszót kapjunk.

A kód minimális távolsága a kódszavai között fellépõ legkisebb pozitív Hamming távolság.

Régen, amikor a számítógépeknek kazettán adtak információt, akkor az üzenetet hetes bitcsomagokban tárolták, és minden hetest egy további bittel egészítettek ki egy byte-tá. Ez az egy bit volt az úgynevezett paritásjelzõ bit, amelyet úgy állítottak be, hogy a byteban összesen páros darab 1-es legyen. Ha egy kiolvasott byteban nem ez volt a helyzet, akkor újra lekérték az adatot. Ebben a megközelítésben egy 1-hiba jelzõ kódról van szó.

Az 5.2 feladatban egy hasonló eljárást 1-törlés javításra alkalmaztunk. A "törlés" itt azt jelenti, hogy (az elsõ 99 ember közül) mindenki látja vagy hallja a többiek sapkájának színét, számára egy sapka színe - a sajátjáé - van törölve.

Az 5.5 feladat (térbeli sakktábla) megoldása is felfogható ilyen módon. Nézzük pld a 8×8-as esetet! A "tábla" mezõit nevezzük meg a {0, 1, 2, ..., 7} halmazból képzett számhármasokkal. (2, 0, 3) pld a 2. emelet 0. sor 3. oszlopában álló mezõ kódja. A 64 bástya mezõinek koordinátáit (x, y, z) megadhatjuk pld az alábbi feltétellel:

x + y + z ≡ 0 (mod 8).

Ennek 64 mezõ felel meg, hiszen x és y értéke tetszõlegesen megadható. Két bástya akkor üti egymást, ha koordinátáik közül kettõ is megegyezik egymással. Ez a fenti feltételnek eleget tevõ mezõk közül semelyik kettõre sem teljesülhet, ugyanis, ha x, y és z közül kettõt megadunk, akkor a harmadik már egyértelmûen meghatározható, nincs két lehetõség.