Information Technology Reference
In-Depth Information
-ball is the
set of points x with ones ( XOR ( i , x )) = k . These points can be reached from i traversing
through the lattice on paths of length k . Take as an example the point 1101 in figure 2.
In order to determine the points that can be reached on paths of length 2 from 1101 it
is easier to change the lattice of figure 2 such that 1101 becomes the top element, cf.
figure 3.
In this lattice we have to go down two steps from the top element and find the
elements that are different from i in exactly two positions. These points form the
surface of an
ε
⎦ is the greatest integer less than
ε
. Let ⎣
ε
⎦ = k . Then the surface of the
ε
< 3. Notice that for this lattice a variant of the partial
order is required. It is defined by
ε
-ball with 2
ε
(
(
)
)
(
(
)
)
(
(
)
)
(8)
x
p
y
ones
XOR
x
,
y
=
1
ones
XOR
y
,
top
<
ones
XOR
x
,
top
where top is the chosen top element, i.e. i . Actually, the lattice of an n -dimensional
Hamming space is an n -dimensional diamond that can be turned in arbitrary direction
such that every element can become the top element.
i
1 1 0 1
0 1 0 1
1 0 0 1
1 1 1 1
1 1 0 0
0 0 0 1
0 1 1 1
1 0 1 1
0 1 0 0
1 1 1 0
1 0 0 0
0 0 1 1
0 0 0 0
0 1 1 0
1 0 1 0
compl ( i )
0 0 1 0
Fig. 3. A lattice for binary strings of length 4 with top element 1101
Usually, the complement of an element x
H is defined as the element y for
which XOR ( x , y ) = 1 holds, i.e. compl ( x ) = y
XOR ( x , y ) = 1 . Figure 4 illustrates
this operation.
1 0 1 1 1 0 1 0 1 0
XOR
0 1 0 0 0 1 0 1 0 1
=
1 1 1 1 1 1 1 1 1 1
Fig. 4. The operation compl in a Hamming space
 
Search WWH ::




Custom Search