Information Technology Reference
In-Depth Information
()
()
(
(
)
)
(6)
x
p
y
⇔
ones
y
=
ones
x
+
1
∧
ones
XOR
x
,
y
=
1
Figure 2 shows this lattice for
n
= 4. The set
H
provided with a distance function is
called a (
binary
)
Hamming shape-space
. A usual definition of a distance function on
H
(cf. e.g. [4]) is the following one:
(
)
(
(
)
)
(7)
d
XOR
x
,
y
=
ones
XOR
x
,
y
thus (
H
,
d
XOR
) is a shape-space. Because of the isomorphism between (2
V
,
) (
V
a
finite set) and (
H
,
p
) we can restrict the investigation of finite shape-spaces to that of
binary Hamming spaces.
⊆
1 1 1 1
1 1 1 0
1 1 0 1
1 0 1 1
0 1 1 1
1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 1
0 0 1 1
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
Fig. 2.
The lattice of a binary Hamming space with strings of length 4
n
based shape-spaces distance functions should be
metrics in order to define complementary elements. This does not hold for Hamming
shape-spaces because here the complement of an element can be defined independ-
ently from the chosen distance function. However, one may ask if all distance
functions are metrics as some authors believe (e.g. [8]). Therefore some distance
functions that are in use for Hamming spaces will be examined in the following.
First, I will show that
d
XOR
is a metric. For this purpose the conditions (i) - (iv) of
the definition must be checked. The first three are trivial. The triangle inequation can
be proven as follows: Assume
ones
(
XOR
(
x
,
y
)) =
k
. Then
x
and
y
differ in
k
positions.
If
z
=
x
or
z
=
y
the triangle inequation is trivially satisfied. If
z
In section 2 I argued that in
ℜ
y
let
ones
(
XOR
(
x
,
z
)) =
l
and
ones
(
XOR
(
y
,
z
)) =
m
. This means,
z
is identical with
x
except
in
l
positions. But then
z
must be different from
y
in at least
k
-
l
positions, otherwise
ones
(
XOR
(
x
,
y
)) <
k
, therefore
l
+
m
≠
x
and
z
≠
k
.
Since
d
XOR
is a metric, we can also describe what an
≥
ε
-ball centered around an
element
i
would be. It is defined by
b
(
ε
,
i
) = {
x
∈
S
:
ones
(
XOR
(
i
,
x
)) <
ε
}. The points
x
in the
ε
-ball have the property that they differ from
i
in at most ⎣
ε
⎦ positions, where
