|
U skladu s prijedlogom studenata koji su izrazili interes
za pisanje [b]2. kolokvija, taj će se održati u petak 8. srpnja
poslijepodne[/b]. Točan termin bit će oglašen pravodobno,
a zbog nekih zakazanih ispita to neće biti prije 14 sati.
Slijedi 3. domaća zadaća, čiji sadržaj treba shvatitii i kao
dio pripreme za 2. kolokvij (zajedno s 2. domaćom zadaćom).
U skriptama se mogu naći sve potrebne definicije i rezultati
u vezi s gradivom iz kodiranja zastupljenim u zadaći.
Napominjem da su rješenja nekih od zadataka vrlo kratka, iako
se navodi više potpitanja.
Juraj Šiftar
[b]3. DOMAĆA ZADAĆA [/b]
1. Binarni linearni kod C zadan je tako da se vektor (a,b,c,d)
kodira kao (d,c,b,a,a+d,b+c). (Dakle, a, b, c, d
poprimaju vrijednosti 0 ili 1, a zbrajanje je mod 2).
Od koliko se riječi sastoji C, koja je minimalna težina (različita od 0) i
koje se sve težine riječi pojavljuju u C? Koliko se pogrešaka
može otkriti?
Može li se ispraviti barem jedna pogreška? Navedite primjere
koji ilustriraju odgovore.
Uputa: Poslužite se generirajućim matricama koda C i njemu dualnog
koda (nije
potreban standardni oblik) te primijenite svojstva iz skripti u rješavanju.
2. Neka je n prirodni broj koji je umnožak nekoliko različitih primbrojeva
te neka je p najmanji od prim faktora broja n.
Iz tzv. MacNeishove slutnje, koja se pokazala pogrešnom,
slijedilo bi da broj međusobno ortogonalnih latinskih kvadrata (MOLS)
reda n ne može biti veći od p-1.
Jedan od protuprimjera dan je za n=21, konstrukcijom 3 MOLS reda 21.
Ako bi se takva trojka MOLS reda 21 iskoristila za konstrukciju koda
na način opisan teoremom iz skripti (i s predavanja), koji bi bili parametri
tog koda: broj riječi, duljina riječi, minimalna udaljenost, broj pogrešaka
koje bi se mogle otkriti odnosno ispraviti?
Nadalje, kakav bi se kod mogao odatle dobiti "skraćivanjem"?
3. Pretpostavimo da želimo konstruirati binarni kod (ne nužno linearan)
duljine n, koji se sastoji od barem 30 riječi, sa sposobnošću ispravljanja
barem trećine znakova(znamenaka) u riječi. U kojem rasponu vrijednosti
bi morao biti n?
4. Konstruirajte savršeni ternarni, ekvidistantni MDS kod koji ispravlja
barem jednu pogrešku i to s najmanjim brojem riječi koji je za to potreban.
Kod ne mora biti linearan, ali ako je to moguće ostvarite ga i kao linearni kod.
Ispišite sve riječi koda.
Izložite postupak dekodiranja dobivene poruke (što podrazumijeva i ispravljanje
eventualne pogreške).
U skladu s prijedlogom studenata koji su izrazili interes
za pisanje 2. kolokvija, taj će se održati u petak 8. srpnja
poslijepodne. Točan termin bit će oglašen pravodobno,
a zbog nekih zakazanih ispita to neće biti prije 14 sati.
Slijedi 3. domaća zadaća, čiji sadržaj treba shvatitii i kao
dio pripreme za 2. kolokvij (zajedno s 2. domaćom zadaćom).
U skriptama se mogu naći sve potrebne definicije i rezultati
u vezi s gradivom iz kodiranja zastupljenim u zadaći.
Napominjem da su rješenja nekih od zadataka vrlo kratka, iako
se navodi više potpitanja.
Juraj Šiftar
3. DOMAĆA ZADAĆA
1. Binarni linearni kod C zadan je tako da se vektor (a,b,c,d)
kodira kao (d,c,b,a,a+d,b+c). (Dakle, a, b, c, d
poprimaju vrijednosti 0 ili 1, a zbrajanje je mod 2).
Od koliko se riječi sastoji C, koja je minimalna težina (različita od 0) i
koje se sve težine riječi pojavljuju u C? Koliko se pogrešaka
može otkriti?
Može li se ispraviti barem jedna pogreška? Navedite primjere
koji ilustriraju odgovore.
Uputa: Poslužite se generirajućim matricama koda C i njemu dualnog
koda (nije
potreban standardni oblik) te primijenite svojstva iz skripti u rješavanju.
2. Neka je n prirodni broj koji je umnožak nekoliko različitih primbrojeva
te neka je p najmanji od prim faktora broja n.
Iz tzv. MacNeishove slutnje, koja se pokazala pogrešnom,
slijedilo bi da broj međusobno ortogonalnih latinskih kvadrata (MOLS)
reda n ne može biti veći od p-1.
Jedan od protuprimjera dan je za n=21, konstrukcijom 3 MOLS reda 21.
Ako bi se takva trojka MOLS reda 21 iskoristila za konstrukciju koda
na način opisan teoremom iz skripti (i s predavanja), koji bi bili parametri
tog koda: broj riječi, duljina riječi, minimalna udaljenost, broj pogrešaka
koje bi se mogle otkriti odnosno ispraviti?
Nadalje, kakav bi se kod mogao odatle dobiti "skraćivanjem"?
3. Pretpostavimo da želimo konstruirati binarni kod (ne nužno linearan)
duljine n, koji se sastoji od barem 30 riječi, sa sposobnošću ispravljanja
barem trećine znakova(znamenaka) u riječi. U kojem rasponu vrijednosti
bi morao biti n?
4. Konstruirajte savršeni ternarni, ekvidistantni MDS kod koji ispravlja
barem jednu pogrešku i to s najmanjim brojem riječi koji je za to potreban.
Kod ne mora biti linearan, ali ako je to moguće ostvarite ga i kao linearni kod.
Ispišite sve riječi koda.
Izložite postupak dekodiranja dobivene poruke (što podrazumijeva i ispravljanje
eventualne pogreške).
|
