|
Zadaci na 2. kolokviju:
1. Konstruirajte simetrični (37, 9, 2) dizajn. Navedite teorem koji ukazuje
na mogućnost konstrukcije metodom koju ste primijenili.
2. Odredite sve vrijednosti k, 0 ≤ k ≤ 6, takve da automorfizam (kolineacija)
projektivne ravnine reda 2 može imati točno k fiksnih točaka. Ako su
neke vrijednosti isključene, obrazložite zašto je tako.
Za moguće (ostvarive) vrijednosti navedite primjere kolineacija.
3. Prije parlamentarnih izbora održavaju se televizijska sučeljavanja
predstavnika dviju vodećih političkih stranaka. Svaka stranka
delegirala je po 7 predstavnika, a emisije će se emitirati sedam dana u
tjednu zaredom i to u sedam istih termina svaki dan. Načinite raspored
tako da se susretne svaki par suprotstavljenih stranačkih predstavnika
i da svaki predstavnik nastupi svaki dan u različltim terminima.
4. Matrica P tipa 3x7 formira se tako da se u stupce unose redom binarni
zapisi cijelih brojeva od 1 do 7 (prvi stupac je [0 0 1] t itd). P je
matrica provjere parnosti binarnog Hammingovog koda H duljine 7, što
znači da se kod sastoji od vektora iz prostora F7 (F = GF(2)) koji su
ortogonalni na sve retke matrice P (v pripada kodu H ↔ v Pt = 0).
(a) Koliko pogrešaka otkriva kod H, a koliko ih ispravlja? Obrazložite.
(b) Kako izgleda razdioba težina riječi koda H, tj. koliko u H ima riječi
pojedine težine? Za primljenu poruku u obliku vektora x iz F7,
za koje težine w(x) se poruka mora odbaciti kao pogrešna, a za
koje težine w(x) se poruka može jednoznačno dekodirati?
(c) Riječi koda H shvatimo kao binarne zapise odgovarajućih cijelih
brojeva. Dekodirajte poruke koje redom znače: 14, 15, 30, 60, 120.
Rješenja:
Prije samih rješenja, primjedba kako je na dan 7.7. kolokvij
ispao (nenamjerno) koncepcijski baziran na broju 7, budući da
je 7 važan u svakom od zadataka.
1.
Simetrični 2-(37,9,2) dizajn lako se konstruira pomoću diferencijskog
skupa i multiplikatora t=7. Taj primjer nalazi se i u skriptama.
Na multiplikator 7 upućuje, dakako, teorem (također u skriptama)
da će prim broj p koji ne dijeli v, dijeli n = k- λ i veći je od λ
biti multiplikator za (v,k, λ) diferencijski skup.
2.
Uočimo da čim kolineacija fiksira dvije točke, mora fiksirati i
treću na pravcu koji ih spaja. Zato broj fiksnih točaka ne može
biti točno 2, a onda se lako vidi da ne može biti niti točno 4, 5
ili 6. No, može biti 0, 1 ili 3.
Za primjere se poslužimo cikličkim zapisom projektivne ravnine
reda 2 iz dif. skupa {0,1,3}, dakle pravci su 013, 124, 235, 346,
450, 561 i 602.
Kolineacija bez fiksnih točaka upravo je taj ciklus 0123456.
Kolineacija s jedinom fiksnom točkom 0 je (0)(1,2,4)(3,6,5).
Kolineacija s točno 3 fiksne točke je (0)(1)(3)(2,6)(4,5).
3.
Očito treba konstruirati dva ortogonalna latinska kvadrata reda 7.
Vjerojatno najlakši način je algebarski, pomoću polja GF(7)
i u njemu operacija oblika x * y = ax + y, za a različite od 0
(odnosno, to su dvije klase paralelnih pravaca u afinoj ravnini
reda 7).
4.
Namjera u ovom zadatku bila je da se i bez naročitog
predznanja (ili čitanja skripte) može elementarno snalaziti
u rješavanju.
Izravno se može odrediti taj Hammingov kod, čiji su
parametri (7,4,3), dakle ima 16 riječi i one su u parovima
"suprotne", a + a' = (1,1,1,1,1,1,1).
Osim jedinstvenih riječi težina 0 i 7, ima po 7 riječi
težina 3 i 4.
Riječi se lako dobiju npr iz jednadžbi ortogonalnosti
s retcima matrice P.
Te riječi su binarni zapisi sljedećih brojeva u dekadskom
zapisu:
0, 15, 22, 25, 37, 42, 51, 60,
67, 76, 85, 90, 102, 105, 112, 127.
Kod otkriva do 2 pogreške, a ispravlja jednu. Niti jedan
binarni vektor duljine 7 ne može se odbaciti kao sigurno
pogrešna poruka, jer je kod savršen, dakle svaki vektor
prostora ili pripada kodu ili se nalazi na udaljenosti 1 od
točno jedne riječi koda.
Dekodiranje se izvodi po pravilu najbližeg vektora,
računski pogreška (ako postoji točno jedna) nalazi se na
onom mjestu koje se dobije umnoškom v Pt.
Dakle, 15 i 60 se prihvaćaju kao ispravne poruke,
14 se dekodira kao 15, 30 kao 22 i 120 kao 112.
(Naravno, Hamming najbliži nije uvijek i "dekadski najbliži").
Zadaci na 2. kolokviju:
1. Konstruirajte simetrični (37, 9, 2) dizajn. Navedite teorem koji ukazuje
na mogućnost konstrukcije metodom koju ste primijenili.
2. Odredite sve vrijednosti k, 0 ≤ k ≤ 6, takve da automorfizam (kolineacija)
projektivne ravnine reda 2 može imati točno k fiksnih točaka. Ako su
neke vrijednosti isključene, obrazložite zašto je tako.
Za moguće (ostvarive) vrijednosti navedite primjere kolineacija.
3. Prije parlamentarnih izbora održavaju se televizijska sučeljavanja
predstavnika dviju vodećih političkih stranaka. Svaka stranka
delegirala je po 7 predstavnika, a emisije će se emitirati sedam dana u
tjednu zaredom i to u sedam istih termina svaki dan. Načinite raspored
tako da se susretne svaki par suprotstavljenih stranačkih predstavnika
i da svaki predstavnik nastupi svaki dan u različltim terminima.
4. Matrica P tipa 3x7 formira se tako da se u stupce unose redom binarni
zapisi cijelih brojeva od 1 do 7 (prvi stupac je [0 0 1] t itd). P je
matrica provjere parnosti binarnog Hammingovog koda H duljine 7, što
znači da se kod sastoji od vektora iz prostora F7 (F = GF(2)) koji su
ortogonalni na sve retke matrice P (v pripada kodu H ↔ v Pt = 0).
(a) Koliko pogrešaka otkriva kod H, a koliko ih ispravlja? Obrazložite.
(b) Kako izgleda razdioba težina riječi koda H, tj. koliko u H ima riječi
pojedine težine? Za primljenu poruku u obliku vektora x iz F7,
za koje težine w(x) se poruka mora odbaciti kao pogrešna, a za
koje težine w(x) se poruka može jednoznačno dekodirati?
(c) Riječi koda H shvatimo kao binarne zapise odgovarajućih cijelih
brojeva. Dekodirajte poruke koje redom znače: 14, 15, 30, 60, 120.
Rješenja:
Prije samih rješenja, primjedba kako je na dan 7.7. kolokvij
ispao (nenamjerno) koncepcijski baziran na broju 7, budući da
je 7 važan u svakom od zadataka.
1.
Simetrični 2-(37,9,2) dizajn lako se konstruira pomoću diferencijskog
skupa i multiplikatora t=7. Taj primjer nalazi se i u skriptama.
Na multiplikator 7 upućuje, dakako, teorem (također u skriptama)
da će prim broj p koji ne dijeli v, dijeli n = k- λ i veći je od λ
biti multiplikator za (v,k, λ) diferencijski skup.
2.
Uočimo da čim kolineacija fiksira dvije točke, mora fiksirati i
treću na pravcu koji ih spaja. Zato broj fiksnih točaka ne može
biti točno 2, a onda se lako vidi da ne može biti niti točno 4, 5
ili 6. No, može biti 0, 1 ili 3.
Za primjere se poslužimo cikličkim zapisom projektivne ravnine
reda 2 iz dif. skupa {0,1,3}, dakle pravci su 013, 124, 235, 346,
450, 561 i 602.
Kolineacija bez fiksnih točaka upravo je taj ciklus 0123456.
Kolineacija s jedinom fiksnom točkom 0 je (0)(1,2,4)(3,6,5).
Kolineacija s točno 3 fiksne točke je (0)(1)(3)(2,6)(4,5).
3.
Očito treba konstruirati dva ortogonalna latinska kvadrata reda 7.
Vjerojatno najlakši način je algebarski, pomoću polja GF(7)
i u njemu operacija oblika x * y = ax + y, za a različite od 0
(odnosno, to su dvije klase paralelnih pravaca u afinoj ravnini
reda 7).
4.
Namjera u ovom zadatku bila je da se i bez naročitog
predznanja (ili čitanja skripte) može elementarno snalaziti
u rješavanju.
Izravno se može odrediti taj Hammingov kod, čiji su
parametri (7,4,3), dakle ima 16 riječi i one su u parovima
"suprotne", a + a' = (1,1,1,1,1,1,1).
Osim jedinstvenih riječi težina 0 i 7, ima po 7 riječi
težina 3 i 4.
Riječi se lako dobiju npr iz jednadžbi ortogonalnosti
s retcima matrice P.
Te riječi su binarni zapisi sljedećih brojeva u dekadskom
zapisu:
0, 15, 22, 25, 37, 42, 51, 60,
67, 76, 85, 90, 102, 105, 112, 127.
Kod otkriva do 2 pogreške, a ispravlja jednu. Niti jedan
binarni vektor duljine 7 ne može se odbaciti kao sigurno
pogrešna poruka, jer je kod savršen, dakle svaki vektor
prostora ili pripada kodu ili se nalazi na udaljenosti 1 od
točno jedne riječi koda.
Dekodiranje se izvodi po pravilu najbližeg vektora,
računski pogreška (ako postoji točno jedna) nalazi se na
onom mjestu koje se dobije umnoškom v Pt.
Dakle, 15 i 60 se prihvaćaju kao ispravne poruke,
14 se dekodira kao 15, 30 kao 22 i 120 kao 112.
(Naravno, Hamming najbliži nije uvijek i "dekadski najbliži").
|
