Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-06-20
2004-12-21
Lamarre, Guy J. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C375S262000, C375S341000, C704S242000
Reexamination Certificate
active
06834369
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a digital date transmission system using error-correcting (or error control) codes, and more specifically to techniques for determining a maximum metric and thereafter specifying a most likely code word corresponding thereto in a decoder provided in such a system.
2. Description of Related Art
It is known in the art that in order to reliably reproduce information sequences transmitted over a noisy channel, a wide variety of error control coding/decoding techniques using block codes or convolutional codes have been proposed.
Prior to turning to the present invention, it is deemed preferable to briefly describe, with reference to
FIGS. 1-5
, a conventional digital data transmission system using block codes so as to combat noisy transmission environments.
FIG. 1
is a block diagram showing a simplified example of a transmitter
10
which is provided in a typical digital data transmission system and which utilizes block codes for the purposes of error-correcting coding. Since the transmitter
10
itself is well known in the art, and accordingly, only a brief description thereof will be given. An encoder (channel encoder)
12
is supplied with an information sequence U and divides the same into message blocks of a fixed bit length each. For the sake of simplifying the descriptions, it is assumed that each message block is represented by a binary 4-tuple called a message, and hence there are 2
4
(=16) different possible messages (depicted by U(
1
)-U(
16
)). The encoder
12
transforms the messages U(
1
)-U(
16
) independently into code words C(
1
)-C(
16
) on a one-to-one basis using a coding table
14
listed below the encoder
12
.
A modulator
16
receives successively the code words outputted from the encoder
12
and translates them into corresponding analog baseband signal
18
. Following this, an up-converter
20
converts, using a local oscillator (not shown), the analog base-band signal
18
to an operating frequency of the transmitter
10
in preparation for transmission, after which the code modulated high-frequency signal is radiated to the destination via an antenna
22
.
FIG. 2
is a block diagram schematically showing a simplified example of a receiver (depicted by
24
). The code modulated high-frequency signal, transmitted from the transmitter
10
, is applied to a down-converter
26
by way of an antenna
25
. The down-converter
26
operates such as to convert the incoming high-frequency signal to the corresponding analog baseband signal using a local oscillator (not shown). The analog baseband signal is applied to a demodulator
28
, which in turn generates a demodulated received signal R. A decoder (i.e., channel decoder)
30
is supplied with the signal R, estimating an original code word and generating the estimate as a reproduced information sequence.
Referring to
FIG. 3
, the decoder
30
(
FIG. 2
) is shown in detail in terms of configuration thereof. As illustrated, the decoder
30
is comprised of a memory
40
, a plurality of metric calculators
42
(
1
)-
42
(
16
) which are identical with each other in both configuration and function, a most likely code word determiner
44
, and a code converter
46
. The metric calculators
42
(
1
)-
42
(
16
) are respectively supplied with the code words C(
1
)-C(
16
) previously stored in the memory
40
and identical to those used in the transmitter
24
, and also supplied with the received signal R which has been demodulated at the demodulator
28
of FIG.
2
. Each of the metric calculators
42
(
1
)-
42
(
16
) calculates a metric which is a measure of the closeness of the received signal R to the corresponding code word (viz., one of C(
1
)-C(
16
)), and applies a corresponding metric (viz., one of M(
1
)-M(
18
)) to the most likely cord word determiner
44
. This determiner
44
searches the maximum metric among the metrics M(
1
)-M(
16
) applied thereto, and determines one code word corresponding to the maximum metric, the operation of which will be further described later. The code word thus determined, viz., the output of the determiner
44
, is depicted by D(
15
), and is subject to code conversion at the code converter
46
and outputted therefrom as a reproduced information sequence.
FIG. 4
is a block diagram showing the detail of the most likely code word determiner
44
(
FIG. 3
) which comprises a plurality of selectors
50
(
1
)-
50
(
15
). In brief, the determiner
44
operates such as to detect the maximum metric among the inputted metrics M(
1
)-M(
16
) in a tournament-like manner until only one remains, and then determine and generate the most likely code word (one of C(
1
)-C(
16
)) corresponding to the detected maximum metric.
The selectors
50
(
1
)-
50
(
15
) are substantially identical with each other in both configuration and function, and as such, the selector
50
(
1
) is mainly described. As shown in
FIG. 4
, the selector
50
(
1
) receives two pairs of {M(
1
), C(
1
)} and {M(
2
), C(
2
)}, comparing the received metrics of M(
1
) and M(
2
), and selecting and outputting either pair with the larger metric. The pair (viz, {M(
1
), C(
1
)} or {M(
2
), C(
2
)}) selected at the selector
50
(
1
) is depicted by {N(
1
), D(
1
)}. More specifically, if the selector
50
(
1
) selects the pair {M(
1
), C(
1
)}, the output N(
1
) equals M(
1
), and the output D(
1
) equals C(
1
).
Each of the remaining selectors
50
(
2
)-
50
(
15
) operates in exactly the same manner as the selector
50
(
1
) and outputs the corresponding pair {N(k), D(k)} (k=2, 3, . . . 15). The rightmost selector
50
(
15
) eventually determines one pair, wherein the metric (=N(
15
)) exhibits the maximum value and wherein the cord word D(
15
) corresponds to the maximum metric N(
15
) and is regarded as the most likely code word. Note that the metric N(
15
) outputted from comparator
50
(
15
) has done the job and thus will not used in the subsequent processing. The code word D(
15
) thus detected corresponds to one of the cord words C(
1
)-C(
16
) and applied to the code converter
46
(FIG.
3
), whereat the code word is converted to the corresponding information sequence (depicted by U) as mentioned above.
The selector
50
(
1
) of
FIG. 4
will further be described with reference to FIG.
5
. As shown in
FIG. 5
, the selector
50
(
1
) is comprised of a comparator
52
and two selectors
54
and
56
. The comparator
52
compares the two metrics M(
1
) and M(
2
), and applies the comparison result to the selectors
54
and
56
. The selector
54
responds to the comparison result and selects M(
1
) as N(
1
) if M(
1
)≧M(
2
), and selects M(
2
) as N(
1
) if M(
1
)<M(
2
). On the other hand, the selector
56
is responsive to the comparison result and outputs C(
1
) as D(
1
) if M(
1
)≧M(
2
), and output C(
2
) as D(
1
) If M(
1
)<M(
2
).
Returning to
FIG. 4
, the most likely code word determiner
44
is provided with four (4) stages for selecting the larger metric each, because it has been assumed that each message is a binary 4-tuple. In general, if Q represents the different possible messages to be transmitted, the number of the metric selecting stages at the determiner
44
is given by log
2
Q. Namely, the number of the metric selecting stages of the determiner
44
increases with increase in the different possible messages to be transmitted. On the other hand, the computation at each stage of the determiner
44
accompanies the comparing operation, which inevitably incurs a relatively large delay. Accordingly, the aforesaid conventional techniques for determining the most likely code word has encountered the problems that it is practically not applicable to a system that requires a very high transmission speed. By way of example, with the Viterbi decoder, the value of Q is typically limited to a range of 2
4
to 2
7
because if Q is made larger that that, it is impossible to realize a practically available decode
Shimada Michio
Suzuki Hisashi
Lamarre Guy J.
Machine Learning Laboratory, Inc.
LandOfFree
Apparatus and method for determining a most likely code word... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for determining a most likely code word..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for determining a most likely code word... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3288985