Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
1997-09-29
2001-07-10
Pham, Chi (Department: 2631)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C714S795000
Reexamination Certificate
active
06259749
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to trellis-coded communications systems, and more specifically to Viterbi decoder having a high processing speed.
2. Description of the Related Art
A Viterbi decoder with a code rate ½ and a constraint length 3 (four metric states) is disclosed in Japanese Laid-Open Patent Specification Hei-6-303153. The disclosed decoder includes a branch metric calculator and a pair of add/compare/select (ACS) circuits to which the outputs of the branch metric calculator are supplied on a time-shared basis. The outputs of the ACS circuits are stored back into memories as intermediate results of an ACS process to be updated with new branch metrics from the calculator. A maximum likelihood decision circuit compares path metrics from the ACS circuits to select path metrics of the most likely path in the trellis diagram.
In most data communication systems, however, the constraint length is usually 7 which implies that the metric states amount to as large as 64. If a Viterbi decoder with constraint length 7 were implemented using the prior art technique, it would be necessary to provide as many connections for the data path of the path metrics as there are state metrics. Since the access to the path metric memories is a dominant factor on the overall performance of the Viterbi decoder, a long queue would be formed in the ACS circuits if parallel mode of operation is implemented.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a Viterbi decoder in which a high speed operation is achieved by having a plurality of ACS circuits operate continuously on a pipelined basis.
According to the present invention, there is provided a Viterbi decoder for receiving a sequence of convolutional codewords, comprising means for deriving a sequence of branch metrics from the received codeword sequence, and means for dividing the branch metric sequence into a plurality of branch metric sequences. A plurality of add/compare/select (ACS) circuits are provided for adding the branch metric sequences to a plurality ACS of previous path metrics and determining therefrom a plurality of sequences of path metrics of maximum likelihood paths and a plurality of indicators identifying the maximum likelihood paths. A pipelining circuit is provided for reordering, or pipelining state metrics of the path metrics of the maximum likelihood paths and supplying the pipelined state metrics to the ACS circuits. The indicators from the ACS circuits are used to recover an original bit sequence.
According to one embodiment, the pipelining circuit comprises a first bank of first and second memories and a second bank of first and second memories, and a control circuit for controlling the memories of the banks. During write operation, state metrics of respective path metric sequences from he ACS circuits are stored into the first and second memories of the first bank and state metrics of the respective path metric sequences are subsequently stored into the first and second memories of the second bank. During read operation, a first sequence of even-numbered state metrics and a second sequence of odd-numbered sate metrics are read from the first memory of the first bank and supplied to the ACS circuits, and a first sequence of odd-numbered state metrics and a second sequence of even-numbered state metrics are read from the second memory of the first bank and supplied to the ACS circuits, wherein the first sequence of even-numbered state metrics and the first sequence of odd-numbered state metrics form state metrics of consecutive numbers of a first group, and the second sequence of even-numbered state metrics and the second sequence of odd-numbered state metrics form state metrics of consecutive numbers of a second group following the consecutive numbers of the first group.
According to another embodiment, the pipelining circuit comprises a first bank of first, second, third and fourth memories and a second bank of first, second, third and fourth memories, and a control circuit for controlling the memories of the banks. During write operation, state metrics of respective path metric sequences from the ACS circuits are stored into the first, second, third and fourth memories of the first bank and state metrics of the respective sequences are subsequently stored into the first, second third and fourth memories of the second bank. During read operation, a first sequence of even-numbered state metrics is read from the first memory, a second sequence of odd-numbered state metrics is read from the second memory, a third sequence of even-numbered state metrics is read from the third memory, and a fourth sequence of odd-numbered state metrics is read from the fourth memory, the first and second sequences forming state metrics of consecutive numbers of a first group, and the third and fourth sequences forming state metrics of consecutive numbers of a second group following the consecutive numbers of the first group, wherein the state metrics read from the first and third memories of the first bank are supplied to a first group of the ACS circuits and the state metrics read from the second and fourth memories of the first bank are supplied to a second group of the ACS circuits.
BRIEF DESCRIPTION OF THE DRAWINGS
The present invention will be described in further detail with reference to the accompanying drawings, in which:
FIG. 1
is a block diagram of a convolutional encoder used at the transmit end of a communication link for describing the Viterbi decoder of the present invention located at the receive end of the link;
FIG. 2
is a block diagram of a general configuration of the Viterbi decoder of the present invention;
FIG. 3
is a block diagram of a normalized branch metric calculator of the present invention;
FIG. 4
is a block diagram of a dividing circuit of the present invention;
FIG. 5
a
is a timing diagram of pulse sequences produced by a write address generator of the dividing circuit;
FIG. 5
b
is a timing diagram of pulse sequences produced by a read address generator of the dividing circuit and their relationships with two output sequences of branch metrics delivered from the dividing circuit;
FIG. 5
c
is a tabulation of relationships between the read address and branch metric pairs;
FIG. 6
is a block diagram of add/compare/select circuits of the present invention;
FIG. 7
is a block diagram of a reordering circuit of the present invention;
FIG. 8
a
is a table for mapping the relationships between read and write addresses used by the memories of the reordering circuit;
FIG. 8
b
is a table for mapping the contents of the memories of the reordering circuit to corresponding read/write addresses;
FIGS. 9
a
,
9
b
and
9
c
are tables mapping the relationships between encoder's operating states and decoder's branch metrics and path metrics;
FIG. 10
is a table for mapping the relationships between encoder's initial states and encoder's resultant states depending on input values for an example metric state;
FIG. 11
is a block diagram of a modified Viterbi decoder of the present invention;
FIG. 12
is a block diagram of the reordering circuit of the modified Viterbi decoder; and
FIG. 13
is a timing diagram of the various path metric sequences appearing in the reordering circuit of FIG.
12
.
REFERENCES:
patent: 4614933 (1986-09-01), Yamashita et al.
patent: 60-173930 (1985-09-01), None
patent: 60-199240 (1985-10-01), None
patent: 1-295533 (1989-11-01), None
patent: 8-340262 (1996-12-01), None
patent: 9-148943 (1997-06-01), None
Bayard Emmanuel
Foley & Lardner
NEC Corporation
Pham Chi
LandOfFree
Viterbi decoder with pipelined ACS circuits does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Viterbi decoder with pipelined ACS circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoder with pipelined ACS circuits will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2435754