Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-10-11
2003-11-25
Tu, Christine T. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S794000
Reexamination Certificate
active
06654926
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data communication systems and more particularly relates to a soft decision decoder suitable for use in a code shift keying based direct sequence spread spectrum communication system.
BACKGROUND OF THE INVENTION
In recent years, the world has witnessed explosive growth in the demand for communications and networking and it is predicted that this demand will increase in the future. Many communication and networking schemes utilize some form of error correcting techniques to correct errors caused during transmission over noisy, non-ideal communication channels. The use of error detection and correcting codes has thus been widely used in various communications fields in order to improve the reliability of data transmission. In particular, a well-known class of error correcting code (ECC) schemes includes block codes and decoders that perform maximum likelihood detection decoding.
Block Coded Digital Communications and Maximum Likelihood Decoder
A block diagram illustrating a generalized digital communication system is shown in FIG.
1
. The general digital communication system, generally referenced
10
, comprises a transmitter
12
and receiver
14
connected via a channel
20
. The data arrives at a rate of one bit every T
s
seconds and is stored until a block of K bits accumulates. The block is then input to the encoder
16
as one of M possible messages denoted H
1
, H
2
, . . . , H
M
where M=2
K
. The encoder performs a mapping from the input message to a signal x
m
. The modulator
18
converts the signal x
m
to a signal of finite duration T=KT
S
. Thus, a set of messages {H
m
} is mapped to a set of signals {x
m
(t)}.
The goal of the channel encoder
16
is to perform a mapping from an input digital sequence to a channel input sequence and the goal of the channel decoder
24
is to perform a mapping from the channel output sequence to an output digital sequence. The encoder and decoder should be constructed so as to minimize the effect of channel noise, i.e. the differences between input and output digital sequences are minimized. In order to achieve this, redundancy is introduced in the channel encoder that is subsequently used by the decoder to reconstruct the input sequence as accurately as possible.
The signals are transmitted onto the channel
20
and received as y(t) at the receiver
14
. The receiver comprises a demodulator
22
and decoder
24
. In particular, the goal of the decoder is to perform a mapping from the vector y to a decision H
{circumflex over (m)}
on the message transmitted. A suitable criterion for this decision is to minimize the probability of error of the decision. The optimum decision rule, given the criterion is to minimize the error probability in mapping each vector y to a decision, can be expressed as
H
{circumflex over (m)}
=H
m
if
Pr
(
H
m
sent|
y
)≧
Pr
(
H
m′
sent|
y
) for all
m′≠m
(1)
The above condition can be expressed in terms of prior probabilities of the messages and in terms of the conditional probabilities of y given each H
m
that are called the likelihood functions. The optimum decision in Equation 1 can be expressed, using Bayes' rule, as
H
m
^
=
H
m
if
ln
π
m
+
∑
n
=
1
N
ln
p
(
y
n
❘
x
mn
)
>
ln
π
m
′
+
∑
n
=
1
N
ln
p
(
y
n
❘
x
m
′
n
)
for
all
m
′
≠
m
(
2
)
where x
mn
represents the n
th
component (i.e. an individual bit) of the m
th
vector. Thus, the goal is the choose the output decision (i.e. codeword H
m
) that yields a maximum.
In most cases, the message probabilities are all equal,thus
π
m
=
1
M
m
=
1
,
2
,
…
,
M
(
3
)
Therefore the factors &pgr;
m
, &pgr;
m′
can be eliminated from Equation 2. The resulting decision rule is then referred to as maximum likelihood. The maximum likelihood decoder depends only on the channel. Note that the logarithm of the likelihood function is commonly used as the metric. The maximum likelihood decoder thus functions to compute the metrics for each possible signal vector, compare them and decide in favor of the maximum.
Additional background information on coding and digital communications can be found in the book “Principles of Digital Communication and Coding,” A. J. Viterbi and J. K. Omura, McGraw Hill, Inc., 1979.
Soft Decision Decoding
Soft decision decoding techniques are known in the art. Examples of well-known codes include Tornado code, Hamming code, Convolution Code, Turbo Code, Reed-Solomon Code and Arithmetic Code. The Hamming Code is a family of optimal binary (2
n
−1, 2
n
−1−n) codes that is capable of correcting one error or three erasures. A disadvantage of this code is that it is a binary code and thus cannot take advantage of multi-bit symbol constellations associated with symbol codes. The convolution code is one of the best known soft decision codes that can be decoded using a Viterbi algorithm. A disadvantage of this code is that it is complex to implement in hardware and is not as effective for high code rates close to one.
Turbo codes (or parallel concatenated convolution codes) are more complex than convolution codes but provide better performance. Disadvantages of this code include relatively long decoding delays (i.e. very long codewords), complex decoding algorithm with large memory requirements and the fact that the code is a binary code and not a symbol code.
The Reed-Solomon code is a special case of the block Hamming Code. It is a symbol code (2−1, 2
n
−1−2t) capable of t error or 2t erasure corrections. A disadvantage in realizing this type of coder/decoder is the large amount of hardware required. In addition, it is relatively difficult to perform soft decision decoding with Reed Solomon codes.
Another well known coding technique is Wagner coding, in which encoding is performed by appending a single parity check bit to a block of k information bits. Upon reception of each received digit r
i
, the a posteriori probabilities p(0|r
i
) and p(1|r
i
) are calculated and saved, and a hard bit decision is made on each of the k+1 digits. Parity is checked, and if satisfied, the k information bits are accepted. If parity fails, however, the received digit having the smallest different between its two a posteriori probabilities is inverted before the k information bits are accepted. In this case, a single erasure may be filled but no errors can be corrected.
A generalization of the Wagner coding technique applicable to any multiple error correcting (n, k) code is a scheme known as forced erasure decoding. The receiver, using such a scheme, makes a hard binary decision on each received bit as well as measures relative reliability. Note that in many communication systems, the probability of correct bit demodulation and decoding is monotonically related to the magnitude of the detected signal, i.e. the detected signal strength is a measure of bit reliability.
A disadvantage of the prior art soft decision decoding techniques is that they are intended for blocks of information made up of bits and not symbols. In addition, most require very large gate counts in order to realize the hardware circuitry needed to implement the code.
SUMMARY OF THE INVENTION
Accordingly, it is a general object of the present invention to provide a novel and useful soft decision maximum likelihood detection method, in which the problems described above are eliminated. The present invention comprises an encoder and decoder for a forward error correcting code. The decoding technique of the present invention utilizes soft decision maximum likelihood decoding that is especially suited for codes that operate on symbols rather than bits and is particularly well suited fo
Barkan Gonen
Raphaeli Dan
Chase Shelly A
Itran Communications Ltd.
Tu Christine T.
Zaretsky Howard
LandOfFree
Soft decision maximum likelihood encoder and decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Soft decision maximum likelihood encoder and decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Soft decision maximum likelihood encoder and decoder will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3125659