Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Rozwiązanie
Niech
xy
,
E
{0,1},
n
x
±
xx
1
2
,...,
x
n
),
y
±
yy
1
2
,...,
y
n
)
.Wówczas
(,
(,
I
(,)
xy
df
±
Σ
n
I
d
(,
xy
i
i
)
±
Σ
n
wx
(
i
O
2
y
i
)
±
wx
(
-
y
)
±
wx
(
+
y
)
i
±
1
i
±
1
gdzie
I
d
jestmetrykądyskretnąwzbiorze{0,1},asymbol
Ooznaczadziałanie
2
odejmowaniaw
Z
2
tzn.
df
x
i
O
2
y
i
±
z
wtedyitylkowtedy,gdy
z
®
2
y
i
±
x
i
Łatwosprawdzić,żedziałania
®i
2
Ow
2
Z
2
sątymsamymdwuargumento-
wymdziałaniem.
Działanie„–”jestdziałaniemodejmowaniawektorówz{0,1}
n(odejmowanie
modulo2w
Z
2
powspółrzędnych).Działanie„+”jestdziałaniemdodawania
wektorówz{0,1}
n(dodawaniemodulo2w
Z
2
powspółrzędnych).
■
Zadanie1.14
Niech
w
:{0,1}
+ą
N
U
{0}
będziefunkcjąwagi,a
wa
()
wagąwektora
a
E
Z
2
n
.
Wykazać,żedladowolnych
ab
,
E
Z
2
n
,jeśli
wa
()
±
wb
()
,to
p
H
(,)
ab
jestliczbą
parzystą.
Rozwiązanie
1.Zauważmy,żejeślimiejsca,wktórychwystępująjedynki,sąróżnedlawekto-
rówaib,to
p
H
(,)
ab
±
2()
wa
±
2()
wb
.Zatem
p
H
(,)
ab
jestliczbąparzystą.
2.Jeślimiejsca,wktórychwystępująjedynki,siępokrywają,toab
±
ioczywi-
ście
p
H
(,)
ab
±.
0
3.Jeśliniewystępujeaniprzypadek1,ani2,to
p
H
(,)
ab
±
2()
wa
-
2
k
,gdziek
jestliczbąpozycji,naktórychwwektorachaibjednocześniewystępująje-
dynki.Oczywiście
p
H
(,)
ab
±
2()
wa
-
2
k
jestliczbąparzystą.
4.Zatem,jeśli
wa
()
±
wb
()
,towewszystkichmożliwychprzypadkach
p
H
(,)
ab
pozostajeliczbąparzystą.
■
Zadanie1.15
df
Ziluelementówskładasiękuladomknięta
Kxr
(,){
±
y
E
{0,1};
n
p
H
(,)
xy
Ś
r
}
opromieniu
r>
0
wprzestrzeniHamminga{0,1}
n.Jak„wygląda”takakula?
18
