Cryptography Reference
In-Depth Information
components of
c
, then
d
(
c,c
) is a minimum. The following is fundamental in
the theoryof theoryof error-correcting codes.
Maximal Error-Correction/Detection
1. A code
C
can
detect
up to
s
errors if
d
(
C
)
≥
s
+1.
2. A code
C
can
correct
up to
t
errors if
d
(
C
)
≥
2
t
+1.
A consequence of the above is that nearest neighbour decoding maybe used
to
detect
up to
d
1)
/
2 errors where
d
is the
minimum distance of a code
C
. This motivates some standard notation used in
error-correcting codes.
−
1 errors or to
correct
up to (
d
−
Notation for Codes
: A code
C
of length
n
, having
M
codewords, and
minimum distance
d
=
d
(
C
), is called an (
n,M,d
)-code. this notation allows us
to formulate more easilythe central problems of coding theor.
We also require the following notion that allows us to determine when two
codes are essentiallythe same.
Equivalent Codes
Two codes are
equivalent
if a code can be obtained from the other bya finite
sequence of operations of the types given in 1 and 2 below:
1. Permute the positions of the code;
2. Permute the symbols appearing in a fixed position of all codewords.
Now we provide a matrix theoretic interpretation of the above. Let a code
C
be given bythe
M
×
n
matrix,
c
1
,
1
c
1
,
2
···
c
1
,n
c
2
,
1
c
2
,
2
···
c
2
,n
,
.
.
.
.
.
.
.
.
.
c
M,
1
c
M,
2
···
c
M,n
sometimes called the
generator matrix
for
C
, where each row is a codeword.
Then operations of type 1 are merely rearrangements of the columns of the
matrix and operations of type 2 are s (relabelling) of entries within a given
column. For instance, if we have the binarycode given bythe matrix,
010111
000011
100111
001111
100011
,
Search WWH ::
Custom Search