Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Czycośsięzmieni,jeślizastąpimyzbiór
{0,1}
dowolnymniepustymzbiorem
skończonymV,tzn.rozważamyprzestrzeńmetryczną(
V
n
,
p
H
)
(Vmożebyćnp.
dowolnymustalonymalfabetem)?
Rozwiązanie
1.Zauważmynajpierw,żemetrykaHammingajestodwzorowaniem
p
H
:{0,1}
n
X
{0,1}
n
ą
N
U
{0}
awięcprzyjmujewartościcałkowitoliczbowe.Jeżeliir
!±||
LJ(gdziex
r
||
LJjest
„podłogą”dlaliczbyrzeczywistejxR
E),to
Kxr
(,)
±
Kxr!
(,)
.
2.Niech
x
±
xx
1
2
,...,
x
n
){0,1},
E
n
y
±
yy
1
2
,...,
y
n
){0,1}
E
n
.Wówczas
(,
(,
Kxr
(,)
±
Kxr
!
±
yy
1
2
,...,
y
n
){0,1};
E
n
p
H
xx
1
2
,...,
x
n
(,){(,
((,
),(,
yy
1
2
,...,
y
n
))
Ś
r
}
±
±{
[
[
{0,1},
yy
1
n
2
,...
y
n
){0,1};card{;
E
n
ix
i
#
y
i
}
Ś
r
!
},
{(,
gdy
r
!
Ś
n
gdy
r
!2
n
3.Zatem
card
Kxr
(,)
±{
[
|
()()
r
n
!
+
r
!-
n
1
+
+
()
n
0
,
gdy
r
!
Ś
n
...
.
|
[
2,
n
gdy
r
!
2
n
4.Jeślizastąpimyzbiór{0,1}zbioremskończonymV,to:
Kxr
(,)
±{
[
[
V
n
yy
,
1
2
,...
y
n
)
E
V
n
;card{;
ix
i
#
y
i
}
Ś
r
!
},
gdy
gdy
{(,
r
!
Ś
n
(1)
r
!2
n
oraz
card
Kxr
(,)
±{
[
|
()
r
n
!
(card
V
-
1)
r
!
+
()
r
!-
n
1
(card
V
-
1)
r
!-
1
+
...
.
+
()
n
0
,
gdy
gdy
r
r
!
!
Ś
2
n
n
|
[
(card
V
),
n
5.Łatwozauważyć,żewprzypadkuzbioruVnieskończonego,wzór(1)pozosta-
jeniezmieniony,natomiastkula
Kxrzawieranieskończonąliczbęelemen-
(,)
tów.
■
Zadanie1.16
Pokazać,żeprzestrzeńHamminga{0,1}
n
jestprzestrzeniąliniowąnadciałem
Z±
2
{0,1}
.
19
