|
1. Vrijedi sljedeći teorem: Ako je t neparan broj i q = 4 t^2 +9
te ako postoji konačno polje GF(q), onda u aditivnoj grupi
tog polja jedan diferencijski skup čine svi elementi oblika x^4
(uključujući 0).
Za dvije najmanje vrijednosti q koje dolaze u obzir po tom teoremu
napišite parametre simetričnog dizajna dobivenog iz takvog
diferencijskog skupa. Za manju vrijednost napišite cijeli
diferencijski skup. Jesu li nam taj dizajn i diferencijski skup
poznati? Obrazložite. Za veću vrijednost q napišite barem
8 elemenata diferencijskog skupa.
2. Skicirajte konstrukciju projektivne ravnine reda 16
pomoću diferencijskog skupa i multiplikatora.
Postupak ne ide sasvim lagano, jer se diferencijski
skup ne dobiva kao jedan ciklus pod djelovanjem multiplikatora p.
Za dopunu diferencijskog skupa pokušajte naći “kratke“
cikluse oblika {x, px} i {y, py, p^2 y}.
3. Za n=10 i d = 5 primjenom poznatih relacija odredite raspon
mogućih vrijednosti k u binarnom linearnom (n,k,d) - kodu.
Konstruirajte, ako je moguće, neki takav kod C za jednu
odabranu vrijednost k >1. Napišite koja
svojstva ispunjava dualni kod takvog koda, posebno što se
sve može zaključiti o matrici provjere parnosti koda C, tj.
generirajućoj matrici njemu dualnog koda. Navedite primjer
dekodiranja poruke (vektora) koji ne pripada kodu C, uz
pretpostavku da broj pogrešaka ne prelazi granicu do koje je
moguće ispravno dekodiranje.
4. Navedite sve bitne karakteristike koda koji se može dobiti
standardnom konstrukcijom pomoću maksimalnog MOLS(7)
(skupa međusobno ortogonalnih latinskih kvadrata reda 7).
Posebno, obrazložite kakva je sposobnost tog koda za
ispravljanje pogrešaka (dokažite tvrdnje).
Napomene o rješenjima:
1. U ovom zadatku, začudo, kao najveći problem pokazalo
se određivanje sljedeće moguće vrijednosti za q, poslije
q = 13 (za t = 1). Za t=3 ne dolazi u obzir pripadna vrijednost 45,
jer to nije potencija primbroja.
No, za t=5 dobiva se q = 109, što je primbroj i onda su parametri
dizajna (109, 28, 7). Dalje se lako dobivaju elementi diferencijskog
skupa kao 4. potencije u GF(109).
2. Ovaj zadatak uglavnom je dobro rješavan, jer je p=2 (kao i potencije
od 2) multiplikator u (273,17,1) dizajnu (projektivnoj ravnini reda 16).
Uz ciklus duljine 12, najjednostavnije (1,2,4,8,...,137), u cikličkoj grupi
reda 273 potreban je još podskup od 5 elemenata invarijantan pod
multiplikatorom 2. Ciklusi duljine 6 su predugi, (0) ne dolazi u obzir, jer jedini
ciklus duljine 2 je (91,182), samo je nekima promaklo da ciklus duljine 3
nije jedinstven (kad se rješava (2^3 - 1)y djeljivo s 273).
3. Singletonova ocjena daje k <= 6, no ocjena "pakiranja kugala"
daje da k ne može biti veći od 4. (To je nekima promaklo).
Najjednostavnije rješenje za konkretni kod dobiva se, naravno, za k=2
kad se može uz nulvektor (kod je linearan) uzeti
1111100000, 0000011111 i njihov zbroj, 1111111111.
4. Zadatak se odnosi na standardnu konstrukciju (Teorem 9.36. iz skripti)
(k+2, q^2, k+1)- koda nad GF(q). Ovdje je q=7, k=6 za MOLS(7)
i to je MDS-kod.
1. Vrijedi sljedeći teorem: Ako je t neparan broj i q = 4 t^2 +9
te ako postoji konačno polje GF(q), onda u aditivnoj grupi
tog polja jedan diferencijski skup čine svi elementi oblika x^4
(uključujući 0).
Za dvije najmanje vrijednosti q koje dolaze u obzir po tom teoremu
napišite parametre simetričnog dizajna dobivenog iz takvog
diferencijskog skupa. Za manju vrijednost napišite cijeli
diferencijski skup. Jesu li nam taj dizajn i diferencijski skup
poznati? Obrazložite. Za veću vrijednost q napišite barem
8 elemenata diferencijskog skupa.
2. Skicirajte konstrukciju projektivne ravnine reda 16
pomoću diferencijskog skupa i multiplikatora.
Postupak ne ide sasvim lagano, jer se diferencijski
skup ne dobiva kao jedan ciklus pod djelovanjem multiplikatora p.
Za dopunu diferencijskog skupa pokušajte naći “kratke“
cikluse oblika {x, px} i {y, py, p^2 y}.
3. Za n=10 i d = 5 primjenom poznatih relacija odredite raspon
mogućih vrijednosti k u binarnom linearnom (n,k,d) - kodu.
Konstruirajte, ako je moguće, neki takav kod C za jednu
odabranu vrijednost k >1. Napišite koja
svojstva ispunjava dualni kod takvog koda, posebno što se
sve može zaključiti o matrici provjere parnosti koda C, tj.
generirajućoj matrici njemu dualnog koda. Navedite primjer
dekodiranja poruke (vektora) koji ne pripada kodu C, uz
pretpostavku da broj pogrešaka ne prelazi granicu do koje je
moguće ispravno dekodiranje.
4. Navedite sve bitne karakteristike koda koji se može dobiti
standardnom konstrukcijom pomoću maksimalnog MOLS(7)
(skupa međusobno ortogonalnih latinskih kvadrata reda 7).
Posebno, obrazložite kakva je sposobnost tog koda za
ispravljanje pogrešaka (dokažite tvrdnje).
Napomene o rješenjima:
1. U ovom zadatku, začudo, kao najveći problem pokazalo
se određivanje sljedeće moguće vrijednosti za q, poslije
q = 13 (za t = 1). Za t=3 ne dolazi u obzir pripadna vrijednost 45,
jer to nije potencija primbroja.
No, za t=5 dobiva se q = 109, što je primbroj i onda su parametri
dizajna (109, 28, 7). Dalje se lako dobivaju elementi diferencijskog
skupa kao 4. potencije u GF(109).
2. Ovaj zadatak uglavnom je dobro rješavan, jer je p=2 (kao i potencije
od 2) multiplikator u (273,17,1) dizajnu (projektivnoj ravnini reda 16).
Uz ciklus duljine 12, najjednostavnije (1,2,4,8,...,137), u cikličkoj grupi
reda 273 potreban je još podskup od 5 elemenata invarijantan pod
multiplikatorom 2. Ciklusi duljine 6 su predugi, (0) ne dolazi u obzir, jer jedini
ciklus duljine 2 je (91,182), samo je nekima promaklo da ciklus duljine 3
nije jedinstven (kad se rješava (2^3 - 1)y djeljivo s 273).
3. Singletonova ocjena daje k <= 6, no ocjena "pakiranja kugala"
daje da k ne može biti veći od 4. (To je nekima promaklo).
Najjednostavnije rješenje za konkretni kod dobiva se, naravno, za k=2
kad se može uz nulvektor (kod je linearan) uzeti
1111100000, 0000011111 i njihov zbroj, 1111111111.
4. Zadatak se odnosi na standardnu konstrukciju (Teorem 9.36. iz skripti)
(k+2, q^2, k+1)- koda nad GF(q). Ovdje je q=7, k=6 za MOLS(7)
i to je MDS-kod.
|
