10, matma III rok, 3 sem, kody
[ Pobierz całość w formacie PDF ]
Wyk“ad10KodyAgataSzmyd16.12.2009
(poprawia“aZo
aMecherzy«ska-Wiktor)
SDA(standardowatablicadekoduj¡ca)dlakoduHammingaH
r
[n=2
r
1;nr;3]
lideresyndromeH
0 0
.
.
.
.
.
.
I
2
r
1
H
Przyk“ad1r=2
0
10
01
11
1
H=
@
A
H
r
:f000;111g
SDA:
eeH
00000
10010
01001
00111
Uwaga1MacierzBwde
nicjiG
C
24
jestsymetrycznaB
T
=B,orazorto-
gonalna,
tzn.B
1
=B
T
=B.
KODYMDS
De
nicja1Kodyliniowedlakt
ó
rychzachodzir
ó
wno–¢d=nk+1
(k=dimC)wograniczeniuSingletonanazywaj¡siƒkodamiMDS(maximum
distanceseparable).
Przyk“adykod
ó
wMDS:
GRS(generalizedReed-Solomon)
RS(Reed-Solomon)
1
Twierdzenie1(OkodachMDS)Nastƒpuj¡cewarunkis¡r
ó
wnowa»ne:
(a)d=nk+1(()k=nd+1)
(b)Ka»dyzbi
ó
rnk(=d1)wierszymacierzyHkontroliparzysto–cijest
liniowoniezale»ny
(c)Ka»dyzbi
ó
rkkolumnwmacierzyG(generuj¡cej)jestliniowoniezale»ny
(d)KodjestMDS
OGRANICZENIEGILBERTA-VARSHAMOVA
Twierdzenie2Kodbinarny,liniowy[n;k;d],gdzied2istnieje,je»eli:
n1
0
+
n1
1
+:::+
n1
d2
<2
nk
Wniosek1Dlan>1,d>1istniejekodliniowyCod“ugo–cinidystansie
przynajmniejdtaki,»e:
jCj
2
n1
P
d2
j=0
n1
j
Przyk“ad2CzyistniejekodliniowyCzparametrami[15,6,5]?
SzukamymacierzyHkontroliparzysto–ciowymiarachnr,gdzier=nk=9.
Chcemyznale„¢15wektor
ó
wliniowoniezale»nychd“ugo–ci9.
KonstrukcjerozpoczynamyodmacierzyI
9
.Dopisujemy3wierszetak,aby
ka»ded1=4wierszepowiƒkszonejmacierzyby“yliniowoniezale»ne.
Przypu–¢my,»emamyH:
2
0
100000000
010000000
001000000
000100000
000010000
000001000
000000100
000000010
000000001
111100000
100011100
101000011
:::
:::
:::
1
H=
@
A
Sprawdzamyczymo»nadopisa¢kolejnywierszw
13
tak,abyzachodzi“ali-
niowaniezale»no–¢.Niemo»eby¢to»adenznastƒpuj¡cychwierszy:
wierszzerowy
wybrane12wierszy
sumadw
ó
chwybranychwierszy(jestich
12
2
)
sumatrzechwybranychwierszy(jestich
12
3
)
Zatemwykluczyli–my
12
0
+
12
1
+
12
2
+
12
3
<2
9
.
Oznaczato,»eistniejejakie–w
13
imo»emyjeznale„¢.
zale»no–¢
13
0
+
13
1
+
13
2
+
13
3
<2
9
,mo»nadopisa¢kolejnywiersz.
Dlaw
15
r
ó
wnie»takienierr
ó
wno–cizachodz¡,azatemmo»emyutworzy¢
»¡dan¡macierz.Istniejewiƒckodliniowyzparametrami[15,6,5].
3
Analogiczniesprawdzamyczymo»nadopisa¢w
14
.Poniewa»zachodzinie-
Przyk“ad3Jakijestoptymalnywymiarkoduzparametramin=15,d=5?
ZograniczeniaSingletonamamy:
kn+1d=11
ZograniczeniaHammingaotrzymujemy:
2
k
=jCj
2
15
15
0
+
15
1
+
15
2
=
2
15
121
<
2
15
2
6
=2
9
Zatemk8.
Przyk“ad4Jakiejestmaksymalneograniczeniedolnelubg
ó
rnenakdla
n=9,d=5?
ZograniczeniaGilberta-Varshamova:
jCj
2
n1
P
d2
j=0
n1
j
=
2
8
P
3
j=0
8
j
2;75
2
k
=jCj4=2
2
,zatemk2
ZograniczeniaHamminga:
jCj
2
n
46
<
2
9
2
5
=2
4
st¡djCj2
3
wiƒck3
Podsumowuj¡c2k2
Dlak=2istniejekod[9;2;5].
Dlak=4nieistniejekod[9;4;5].
Dlak=3problemczyistniejekod[9;3;5]jestnierozstrzygniƒty.
KODYCYKLICZNE
GF(p
m
)mo»emyreprezentowa¢jako:
GF(p
m
)=GF(p)[x]
m1
zmno»eniemmodulonierozk“adalnymonicznywie-
lomianp(x)stopniam.
De
nicja2Wielomiannierozk“adalnystopnian>1nad
K
=GF(2)na-
zywasiƒpierwotnym,gdyniejestpodzielnikiem1+x
m
dla»adnegom<2
n
1.
Uwaga2Nierozk“adalnywielomiannad
K
stopnian>1zawszedzieli
1+x
m
dlam=2
n
1.
Uwaga3Dlan=1wielomianempierwotnymjest1+x.
4
n
0
+
n
1
+
n
2
=
2
9
[ Pobierz całość w formacie PDF ]