Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

9. További feladatok

9. További feladatok

12. feladat. Mutassuk meg, hogy a Hamming távolságra

d ( a , b ) + d ( b , c ) ? d ( a , c ) ,

azaz a háromszög-egyenlőtlenség megfelelője teljesül!

13. feladat. (ld. [6]) Tekintsünk egy három halmazt ábrázoló Venn-diagramot, a halmazokat jelölje A , B , C . 4-bites üzeneteket fogunk kódolni 7 bitessé. Írjuk be a négy bitet az A ? B , A ? C , B ? C , és az A ? B ? C -nek megfelelő részekbe. A hozzáillesztett három bit a fennmaradó három részből jön, aszerint, hogy az A , B , C mindegyikében páros sok egyes kell legyen. Mutassuk meg, hogy ily módon 1 hibát javító kódot kapunk.

3. ábra.

14. feladat. Előfordulhat, hogy az üzenetben nem hibát, hanem „olvashatatlan” részt (más szóval „törlést”) látunk. Hibajavítás helyett beszélhetünk törlés-javításról is. Tegyük fel, hogy az üzenet egy szavában t karakter letörlődött, e pedig hibás. Mely ( t , e ) párokra olvasható ki a szó

a) a Hamming-kód;

b) a Mariner szonda kódja;

c) a Golay-kódok esetén?

15. feladat. Családtagjaink személyi számának ismeretében találjuk ki, hogy hogyan keletkezik a személyi szám utolsó, ellenőrző jegye!

16. feladat. Tízjegyű számoknál más lehetőség is lenne, mint az ISBN-számnál megismert kódolás, lehetne modulo 11 helyett modulo 10 számolni. Miért jobb a modulo 11? És ha X helyett 0-t írnánk?

17. feladat. A Mariner-expedíciónál használt kódokhoz olyan n × n -es mátrixra volt szükség, amelynek elemei ± 1 -ek, és bármely két sor skaláris szorzata 0. Mutassuk meg, hogy ilyen mátrix csak n = 1 , n = 2 , továbbá néggyel osztható n esetén létezhet! Keressünk ilyen mátrixot n = 12 -re!

18. feladat. Lássuk be az e -hibajavító kódok méretére vonatkozó (1) becslést!

19. feladat. Lássuk be, hogy a modulo p maradékosztálytest feletti Hamming-kódok 1 hibát javító perfekt kódok.

20. feladat. Lássuk be, hogy a (6)(9) egyenletekkel definiált kódokkal tényleg 2 hibát tudunk javítani!

21. feladat. A 31 elemű ábécé felett adjunk meg 3 hibát javító kódot!

22. feladat. Hány TOTÓ-szelvényt kell kitöltenünk a biztos 13 találathoz, ha tudjuk, hogy lesz X? Hány szelvényt kell kitöltsünk, ha 5 találattal is megelégszünk?

23. feladat. Lássuk be a TOTÓ-ra vonatkozó (10), illetve az általános (11) korlátot!

24. feladat. Lássuk be, hogy a ternér Golay-kód valóban két hibát javít.

25. feladat. Lássuk be, hogy a bináris Golay-kód valóban három hibát javít.

26. feladat. A v szó súlya a nem-nulla koordináták száma (azaz a 0-tól mért távolság). A C kód minimális súlya a 0-tól különböző kódszavak súlyának minimuma. Mutassuk meg, hogy lineáris kód minimális súlya és minimális távolsága megegyezik.

27. feladat. Legyen C ? { 0 , 1 } n . Definiáljuk C ¯ -t úgy, hogy

( c 1 , , c n , c n + 1 ) ? C ¯

akkor és csak akkor, ha ? i = 1 n + 1 c i = 0 (persze mod 2 számolva), és ( c 1 , , c n ) ? C . Milyen összefüggés van C és C ¯ minimális súlya között?

28. feladat. Mutassuk meg, hogy a CD lejátszókon alkalmazott kód leírásánál található kód MDS kód.