Cryptography Reference
In-Depth Information
then applying the permutation 0
0 to column four (an operation
of type 2), then interchange columns one and five (an operation of type 1), we
get
→
1 and 1
→
110010
100110
100011
101010
100111
.
Central Coding Theory Goals
: An optimal (
n,M,d
)-code
C
, is one
with small
n
, large
M
, and large
d
. We require a small length
n
so that we
mayeLcientlytransmit the code. We would like to have a large
M
in order to
be able to send a diverse arrayof messages, and we seek a large
d
so we can
correct as manyerrors as possible when theyoccur. Unfortunatel, these aims
are conflicting, so we usuallyfix one of the values and optimize the other two.
One typical feat is to attempt to minimize
d
and maximize
M
for a given length
n
. For instance, if we have a
q
-ary(
n,M,d
)-code where
M
is a maximum, we
denote the maximum value by
A
q
(
n,d
). Indeed, the extreme cases are easyto
find, namely,
A
q
(
n,
1) =
q
n
and
A
q
(
n,n
)=
q
. In fact, these are special cases of
the next result.
The goals for optimizing the values was given mathematical rigour in [264]
in 1964. This is thus known as the following.
The Singleton Bound
: Let
C
be a
q
-ary(
n,M,d
)-code. Then
q
n
−
d
+1
.
M
≤
Moreover, if
M
=
q
n
−
d
+1
, then
C
is called a
maximum distance separable
(MDS) code.
Hamming also developed a bound, given as follows.
The Hamming Bound
: f
C
is a
q
-ary(
n,M,d
)-ocde with
d
≥
2
t
+1,
then
q
n
j
=0
j
(
q
M
≤
1)
j
,
−
where the value on the right is called the
Hamming bound
.
Perfect Codes
:An(
n,M,d
)-code with
d
=2
t
+ 1 for which
M
equals
the Hamming bound is called a
perfect code
. Another characterization of perfect
codes is that everyvector in
F
q
is a distance of no more than
t
units from exactly
one codeword. In other words, the
M
spheres of radius
t
centered on codewords
in a perfect
t
-error correcting code fills the entiretyof
F
q
without overlapping.
For instance, the binarycode,
C
=
{
(0
,
0
,...,
0)
,
(1
,
1
,...,
1)
}
,
of length
n
where
n
is odd, is a perfect (
n,
2
,n
)-code. Later in this section we will
look at some classes of perfect codes including those discovered byHamming.
Search WWH ::
Custom Search