|
[b]4. (i zadnja) domaća zadaća iz Konačnih geometrija: Kodovi[/b]
1. Ako je C linearni binarni kod, on je jednak dualnom kodu svog dualnog koda. Dokažite.
2. Neka je C binarni kod duljine n koji ispravlja jednu pogrešku
(C je podskup od F^n, F ={0,1}, nije nužno linearan tj. potprostor).
Tada kard C nije veći od (2^n)/(n+1), pri čemu jednakost vrijedi
ako i samo ako je C savršen kod. Dokažite tu tvrdnju i odatle
izvedite da duljina n savršenog koda s ispravljanjem 1 pogreške
mora biti oblika n = 2^r - 1 za neki r.
3. Neka je H* prošireni Hammingov (8,4)-kod. Pokažite da riječi
minimalne težine tog koda (tj. nosači vektora minimalne
težine) čine 3-(8,4,1) dizajn.
Zaključak pokušajte izvesti ne "inspekcijom" nego kombinatorički.
(Uputa: pojedina trojka točaka "pokrivena" je s najviše jednom
riječi minimalne težine, jer u protivnom minimalna udaljenost
ne bi bila 4. Ukupni broj trojki točaka usporedite s brojem
trojki sadržanih u nosačima vektora minimalne težine).
4. Pretpostavimo da želimo konstruirati binarni linearni kod koji
ispravlja 1 pogrešku, a sadrži barem 8 riječi (kako bi se mogle
kodirati npr. strane svijeta - N, W, S, E i NW, SW, SE, NE).
Kolika je najmanja duljina takvog koda? Konstruirajte takav kod,
što manje duljine.
5. Neka je C binarni linearni kod generiran retcima incidencijske matrice
projektivne ravnine reda n, pri čemu je n neparan. Dokažite da se
C sastoji od svih vektora parne težine u F^v. (Uputa: Pokažite da
C sadrži sve vektore koji ne jednom mjestu imaju 0, a na svim
ostalim mjestima 1. Takvih vektora je v, a v-1 ih je linearno nezavisnih
pa je dim C = v-1).
4. (i zadnja) domaća zadaća iz Konačnih geometrija: Kodovi
1. Ako je C linearni binarni kod, on je jednak dualnom kodu svog dualnog koda. Dokažite.
2. Neka je C binarni kod duljine n koji ispravlja jednu pogrešku
(C je podskup od F^n, F ={0,1}, nije nužno linearan tj. potprostor).
Tada kard C nije veći od (2^n)/(n+1), pri čemu jednakost vrijedi
ako i samo ako je C savršen kod. Dokažite tu tvrdnju i odatle
izvedite da duljina n savršenog koda s ispravljanjem 1 pogreške
mora biti oblika n = 2^r - 1 za neki r.
3. Neka je H* prošireni Hammingov (8,4)-kod. Pokažite da riječi
minimalne težine tog koda (tj. nosači vektora minimalne
težine) čine 3-(8,4,1) dizajn.
Zaključak pokušajte izvesti ne "inspekcijom" nego kombinatorički.
(Uputa: pojedina trojka točaka "pokrivena" je s najviše jednom
riječi minimalne težine, jer u protivnom minimalna udaljenost
ne bi bila 4. Ukupni broj trojki točaka usporedite s brojem
trojki sadržanih u nosačima vektora minimalne težine).
4. Pretpostavimo da želimo konstruirati binarni linearni kod koji
ispravlja 1 pogrešku, a sadrži barem 8 riječi (kako bi se mogle
kodirati npr. strane svijeta - N, W, S, E i NW, SW, SE, NE).
Kolika je najmanja duljina takvog koda? Konstruirajte takav kod,
što manje duljine.
5. Neka je C binarni linearni kod generiran retcima incidencijske matrice
projektivne ravnine reda n, pri čemu je n neparan. Dokažite da se
C sastoji od svih vektora parne težine u F^v. (Uputa: Pokažite da
C sadrži sve vektore koji ne jednom mjestu imaju 0, a na svim
ostalim mjestima 1. Takvih vektora je v, a v-1 ih je linearno nezavisnih
pa je dim C = v-1).
|
