Cryptography Reference
In-Depth Information
and since the only remaining roots of
x
7
1
are
α
j
−
for
j
=3
,
5
,
6
, then these
are the roots of
p
(
x
)=
x
3
+
x
2
+1
,
the parity-check polynomial.
We will not discuss BCH decoding since it is quite complicated in the general
case, and simplification to the single error-correcting BCH codes reduces us to
what we have alreadystudied, the reason being that there exists an isomorphism
between such a code and a Hamming code. For a complete and detailed overview
of the general BCH decoding scheme, see [153], for instance. That said, the
special case where
n
=
q
−
1 defined above is worth exploring.
Reed-Solomon Codes
Reed-Solomon codes are a specific kind of BCH code with a vast arrayof
applications in digital communications including digital television; high-speed
modems; satellite communications; wireless communications; and storage de-
vices such as barcodes, compact disks, DVDs, and the like. These codes excel
at correcting certain types of errors called
burst errors
.
11.11
These are errors
that occur close together, as opposed to randomly. As examples: a burst of
solar energycan introduce errors in satellite communications; a scratch on a
CD can introduce errors in contiguous bits; and electrical interference can be
caused when an electric motor starts near a data-carrying cable. Hence, these
codes are potent and have great eLcacyin the aforementioned applications.
If
n
=
q
−
1, then
F
q
contains a primitive
n
th root of unity,
α
. In other
words,
F
q
=
F
q
(
α
). Select a natural number
d
=2
t
+
i
−
1
<n
, where
i,t
∈
N
,
and set
2
t
α
i
)(
x
α
i
+1
)
α
2
t
+
i
−
1
)=
c
j
x
j
g
(
x
)=(
x
−
−
···
(
x
−
∈
F
q
[
x
]
.
(11.11)
j
=0
then the code
C
=
2
t,t
]-code called a
Reed-Solomon code
,
which achieves the maximum possible minimum code distance
d
(
C
)=2
t
+1
for anylinear code with the same encoder input and output block lengths.
Often the Reed-Solomon codes, defined above, are denoted by
RS
(
n,t
) over
F
q
where
q
=
p
m
, which is a cyclic code of length
n
=
p
m
g
(
x
)
is a cyclic [
n,n
−
−
1, containing
q
n
−
2
t
codewords, having dimension
n
−
2
t
, with generating polynomial given by
(11.11), and minimum distance 2
t
+1.
Example 11.15
Let us see how
RS
(7
,
2)
is constructed. In this case,
q
=2
3
,
n
=7
,
t
=2
,
i
=1
,
α
, a primitive
7
th root of unity, and
4
α
j
)=(
x
α
2
)(
x
α
3
)(
x
α
4
)=
g
(
x
)=
(
x
−
−
α
)(
x
−
−
−
j
=1
11.11
For instance, a Reed-Solomon code may correct an entire byte, even if only one bit is
corrupted. This gives these codes a huge advantage over binary codes that might only correct
a bit, when several contiguous bits have been corrupted. We lookat other codes, with respect
to burst errors, in Appendix E (see page 549).
Search WWH ::
Custom Search