|
U skriptama preostalo je 9. i 10. poglavlje.
Ovo zadnje je kratko i prikazuje jednu zgodnu
primjenu dizajna na tzv. neadaptivno grupno testiranje,
tako da se određeni algoritam (NAGTA) temelji na
2-(v,k,1) dizajnu. Vrijedi pročitati, barem informativno,
jer doista je praktično primjenjivo.
Sa svojih 15-ak stranica, znatno je opsežnije 9. poglavlje
koje pruža uvod u teoriju kodiranja.
Riječ je o stvarno ozbiljnim primjenama kombinatoričko-
geometrijskih struktura kakve su dizajni, Hadamardove
matrice i latinski kvadrati, no ovo je doista samo uvod.
Najvažniji kodovi koji se ovdje spominju su Reed-Solomonovi
kodovi (Teorem 9.39.), čija primjena (u naprednijim modifikacijama)
seže od prijenosa digitaliziranih fotografija iz dalekog svemira
(još 1977.) do CD, DVD i DAT tehnike u svakodnevnoj uporabi
(od 1982. dalje).
Temeljni članak Reeda i Solomona (s MIT-a) iz 1960. naslovljen
je "Polynomial Codes Over Certain Finite Fields"
(matematika, očito).
Naš uvod prvenstveno se odnosi na (linearno)algebarske kodove.
Poruke se kodiraju kao vektori duljine [i]n[/i] nad konačnim poljem,
najčešće GF(2) (binarni), ali ternarni i drugi [i]q[/i]-kodovi imaju
svoju ulogu. Najlakše je računati s binarnim kodovima.
Važno i poželjno svojstvo koda je sposobnost otkrivanja
te, po mogućnosti, i ispravljanja pogrešaka nastalih
zbog "šuma" u prijenosu podataka. Povoljno je da duljina [i]n[/i]
"riječi" koda ne bude prevelika, ali da broj riječi [i]M[/i] bude čim
veći, kao i prag [i]d[/i] do kojeg se pogreške mogu ispraviti.
Ta tri parametra međusobno su zavisna, jer
[i]M[/i] ne može biti veći od [i]q[/i]^([i]n[/i]-[i]d[/i]+1)
(Singletonova međa).
Struktura se najpreglednije opisuje ako je kod C potprostor
[i]n[/i]-dim. vektorskog prostora nad poljem GF([i]q[/i]).
Uvođenjem vrlo jednostavne Hammingove metrike taj
prostor postaje i metrički, a snabdijeva se još i korisnim
bilinearnim "kvaziskalarnim" produktom.
Kod s ispravljenjem pogrešaka tada se "vidi" kao
pakiranje kugala u vektorskom prostoru s Hammingovom
metrikom.
Osim povoljnih parametara, važna je praktična efikasnost
kodiranja i dekodiranja poruka. U linearnoalgebarskom
kontekstu to je, barem načelno, dosta jednostavno.
Teoremi 9.33, 9.36 i 9.41 daju neke od rezultata kojima
su izravno povezane konačnogeometrijske strukture
s kodovima povoljnih svojstava.
Konačne geometrije i linearni kodovi korisni su uzajamno,
jer ne samo što pravilnost dizajna može osigurati dobre
kodove, nego se pridruživanje kodova dizajnima
(preko incidencijske matrice) pokazalo kao
moćno sredstvo u istraživanju postojanja projektivnih
ravnina i drugih dizajna.
Primjerice, nepostojanje projektivne ravnine reda 10,
nepostojanje 2-(22,8,4) te 2-(46,6,1) dizajna
(a to su bili iznimno "tvrdi" i reprezentativni problemi)
ustanovljeno je naprednim tehnikama iz teorije kodiranja,
uz bitnu ulogu računarstva.
Izbor zadataka povezanih s 9. poglavljem pojedinačno
će e-mailom dobiti studentice i studenti koji su
rješavali domaće zadaće.
[i]Napominjem da je u sadašnjoj radnoj verziji
rasporeda ispita za Konačne geometrije predviđen
četvrtak 2. srpnja. [/i]
U skriptama preostalo je 9. i 10. poglavlje.
Ovo zadnje je kratko i prikazuje jednu zgodnu
primjenu dizajna na tzv. neadaptivno grupno testiranje,
tako da se određeni algoritam (NAGTA) temelji na
2-(v,k,1) dizajnu. Vrijedi pročitati, barem informativno,
jer doista je praktično primjenjivo.
Sa svojih 15-ak stranica, znatno je opsežnije 9. poglavlje
koje pruža uvod u teoriju kodiranja.
Riječ je o stvarno ozbiljnim primjenama kombinatoričko-
geometrijskih struktura kakve su dizajni, Hadamardove
matrice i latinski kvadrati, no ovo je doista samo uvod.
Najvažniji kodovi koji se ovdje spominju su Reed-Solomonovi
kodovi (Teorem 9.39.), čija primjena (u naprednijim modifikacijama)
seže od prijenosa digitaliziranih fotografija iz dalekog svemira
(još 1977.) do CD, DVD i DAT tehnike u svakodnevnoj uporabi
(od 1982. dalje).
Temeljni članak Reeda i Solomona (s MIT-a) iz 1960. naslovljen
je "Polynomial Codes Over Certain Finite Fields"
(matematika, očito).
Naš uvod prvenstveno se odnosi na (linearno)algebarske kodove.
Poruke se kodiraju kao vektori duljine n nad konačnim poljem,
najčešće GF(2) (binarni), ali ternarni i drugi q-kodovi imaju
svoju ulogu. Najlakše je računati s binarnim kodovima.
Važno i poželjno svojstvo koda je sposobnost otkrivanja
te, po mogućnosti, i ispravljanja pogrešaka nastalih
zbog "šuma" u prijenosu podataka. Povoljno je da duljina n
"riječi" koda ne bude prevelika, ali da broj riječi M bude čim
veći, kao i prag d do kojeg se pogreške mogu ispraviti.
Ta tri parametra međusobno su zavisna, jer
M ne može biti veći od q^(n-d+1)
(Singletonova međa).
Struktura se najpreglednije opisuje ako je kod C potprostor
n-dim. vektorskog prostora nad poljem GF(q).
Uvođenjem vrlo jednostavne Hammingove metrike taj
prostor postaje i metrički, a snabdijeva se još i korisnim
bilinearnim "kvaziskalarnim" produktom.
Kod s ispravljenjem pogrešaka tada se "vidi" kao
pakiranje kugala u vektorskom prostoru s Hammingovom
metrikom.
Osim povoljnih parametara, važna je praktična efikasnost
kodiranja i dekodiranja poruka. U linearnoalgebarskom
kontekstu to je, barem načelno, dosta jednostavno.
Teoremi 9.33, 9.36 i 9.41 daju neke od rezultata kojima
su izravno povezane konačnogeometrijske strukture
s kodovima povoljnih svojstava.
Konačne geometrije i linearni kodovi korisni su uzajamno,
jer ne samo što pravilnost dizajna može osigurati dobre
kodove, nego se pridruživanje kodova dizajnima
(preko incidencijske matrice) pokazalo kao
moćno sredstvo u istraživanju postojanja projektivnih
ravnina i drugih dizajna.
Primjerice, nepostojanje projektivne ravnine reda 10,
nepostojanje 2-(22,8,4) te 2-(46,6,1) dizajna
(a to su bili iznimno "tvrdi" i reprezentativni problemi)
ustanovljeno je naprednim tehnikama iz teorije kodiranja,
uz bitnu ulogu računarstva.
Izbor zadataka povezanih s 9. poglavljem pojedinačno
će e-mailom dobiti studentice i studenti koji su
rješavali domaće zadaće.
Napominjem da je u sadašnjoj radnoj verziji
rasporeda ispita za Konačne geometrije predviđen
četvrtak 2. srpnja.
|
