Cryptography Reference
In-Depth Information
as the number of errors to be corrected. The Hamming distance is a function
on
q
that satisfies the following.
F
Properties of the Hamming Function
Each of the following holds:
∈
F
q
,
d
(
u,v
) = 0 if and onlyif
u
=
v
.
1. Given
u,v
2. For any
u,v
∈
F
q
,
d
(
u,v
)=
d
(
v,u
).
q
,
3. For any
u,v,w
∈
F
d
(
u,v
)+
d
(
v,w
)
≥
d
(
u,w
)
,
called the
triangle inequality
.
If
C
is a code, then the Hamming distance,
d
(
C
), is also defined on
C
as the
minimum distance between anytwo codewords. In mathematical terms,
d
(
C
) = min
{
d
(
u,v
):
u,v
∈
C
, with
u
=
v
}
.
For error-correcting codes, this is a valuable number since it provides the small-
est number of errors that have to be corrected.
Another fundamental concept in the theoryof error detection comes from
the geometric arena.
Hamming Sphere
A
Hamming sphere
in
q
of radius
r
centered at the codeword
u
q
is the
F
∈
F
set of all vectors, denoted by
S
(
u,r
) given as follows:
q
:
d
(
u,v
)
{
∈
F
≤
}
S
(
u,r
)=
v
r
,
which has cardinalitygiven by
n
j
(
q
r
1)
j
.
|
S
(
u,r
)
|
=
−
j
=0
Now we need to address the issue of decoding. If we receive a message
v
sent through a noisychannel, we maydecode it to
u
where
u
is that value such
that
d
(
u,v
) is the smallest possible. This process is called the
nearest neighbour
decoding
.
To set the stage for the next important result, we need the following defini-
tions. We saythat a code
C
can
detect
up to
s
errors provided that changing
s
+1
components in a codeword can change it into another codeword, but changing
s
or fewer components in a codeword cannot alter it to make another codeword.
Also, we saythat a code
C
can
correct
up to
t
errors if changes made to at most
t
components of a codeword
c
C
, ensure that the closest codeword remains
c
. In other words, if
c
represents a codeword obtained byaltering at most
t
∈
Search WWH ::
Custom Search