Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
1999-10-21
2001-12-25
Pham, Chi (Department: 2631)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C714S795000
Reexamination Certificate
active
06333954
ABSTRACT:
BACKGROUND OF THE INVENTION
I. Field of the Invention
This invention generally relates to applications of the Viterbi algorithm. More particularly, the present invention relates to an improved system and method of performing a high-rate Add-Compare-Select (ACS) butterfly operation in an implementation of the Viterbi algorithm.
II. Description of Related Art
The Viterbi algorithm was first introduced in 1967 as a method for decoding convolutionally-encoded signals. Since its introduction, the algorithm has gained wide acceptance in the field of data communications, data recording, and digital signal processing. The algorithm has been used to successfully combat a variety of digital estimation issues, including the reduction of recording errors in storage media, the removal of intersymbol interference, and the enhancement of character and text recognition.
As such, the Viterbi algorithm has become the foremost method for the error-correction decoding of convolutionally-encoded data. For such applications, the Viterbi algorithm determines, based on a series of observations, the path with the smallest error metric that traverses a trellis typifying all possible encoder states. This shortest path exemplifies the mostly likely sequence generated by a convolutional encoder.
FIG. 1A
illustrates a typical convolutional encoder. The convolutional encoder
100
comprises an 8-bit tapped shift register
110
and a pair of exclusive OR-type summers
120
that transform a sequence of input data bits U(D)
105
into a sequence of output code symbols C
0
(D), C
1
(D)
125
. In particular,
FIG. 1A
demonstrates the example of a rate
13
code which generates two output coding symbols C
0
(D), C
1
(D)
125
for each input data bit U(D)
105
. It is to be noted that the specific code rate and configuration of the convolutional encoder
100
shown is merely illustrative and in no way limits the operation or scope of the various embodiments of the invention. As such, different code rates, such as ⅓or _, for example, could be used in conjunction with the embodiments of the invention.
Encoder
100
generates each output code symbol C
0
(D), C
1
(D)
125
by shifting and exclusive-OR summing the input bit stream U(D)
105
according to the particular shift-register configuration specified by generator code polynomials G
0
(D), G
1
(D). In this case,
FIG. 1A
depicts the shift-register interconnections that provide the rate
13
generator code polynomial G
0
(D)=1
D
2
D
4
D
7
. The coefficients of polynomial G
0
(D) are convolved with input data sequence U(D)
105
to generate output convolutional code symbol C
0
(D)
125
. Similarly,
FIG. 1A
shows the rate
13
generator code polynomial G
1
(D)=1
D
2
D
5
, whose coefficients are convolved with input data sequence U(D)
105
to generate output convolutional code symbol C
1
(D)
125
. The constraint length K of the encoder
100
is one more than the number of delay elements in shift register
110
; for encoder
100
, constraint length K equals 9. For each data bit
105
inputted into encoder
100
, the output code symbols C
0
(D), C
1
(D)
125
depend on the inputted bit as well as the previous K−1 input bits. Therefore, the encoder
100
produces output code symbols C
0
(D), C
1
(D)
125
that are capable of spanning
2
K−1
possible encoder states.
In a typical communication system, the output code symbols C
0
(D), C
1
(D)
125
are subsequently modulated and transmitted over a noisy channel (not shown). A decoder eventually receives the noisy convolutionally-encoded data stream and employs the Viterbi algorithm, which exploits the properties of convolutional codes to ultimately determine the input data sequence U(D)
105
.
One advantage of convolutional codes is their highly repetitive structure, which provides for a symmetrical code tree. Theoretically, a convolutional code is capable of generating an infinite sequence of code symbols. However, because of its symmetry, the number of states that need to be evaluated in locating the most probable path leading to the inputted data sequence U(D)
105
is reduced to
2
k−1
(in this case, 256) states. Moreover, in decoding such a symmetrical code, only the most probable (i.e surviving) local path into each of the 256 possible encoder states is of interest—all other paths maybe discarded from further consideration. This is because the most probable global path through a state must necessarily follow the surviving local path through that state.
The Viterbi decoder relies on these code properties to function as a finite state machine having a limited set of state transitions. The decoder hypothesizes each of the possible encoder
2
k−1
states and determines the probability that the encoder transitioned from each of those states to the next set of
2
k−1
possible encoder states, based on the observations obtained from the received noisy convolutionally-encoded data stream.
The transition probabilities are represented by quantities, referred to as metrics, which are proportional to the negative logarithm of the probability values. Clearly, the smaller the metric, the higher the probability of occurrence. There are two types of metrics: state metrics and branch metrics. The state metric, also called a path metric, represents the relative probability that the transmitted set of code symbols passed through a particular state. The branch metric represents the conditional probability that the transition from a particular source state to a particular target state was transmitted (assuming that the source state was correct).
The Viterbi algorithm may be summarized as follows: where time is divided into d samples and n possible states S
i
k
exist at each time sample k (where i is an integer from 1
n and k is an integer from 1
d). For k>1, each state may be reached by a path from any one of p precursor states S
j
k−1
(where j is an integer from 1
p). For each state, the path with the minimum metric among these p possible paths is identified and stored, along with the value of that metric:
Initialization: for the starting time sample (k=1), the metric stored at each state S
i
1
is initialized. In the case where the starting state is known, the metric of this case may be set to zero while the metrics of the other states S
i
1
are set to a large number. This scheme forces later iterations of the algorithm to choose only paths originating from the desired starting state.
Iteration: for each time sample (k=2
d), all of the states S
i
k
are visited. At each state S
i
k
, the metric for each path j leading to that state is calculated as the sum of (a) the metric of the precursor state S
j
k−1
and (b) the metric bm
j
k
of the branch leading from state S
j
k−1
to state S
i
k
. Of the p paths leading to each state S
i
k
, the path with the lowest metric (i.e. the survivor path) is selected and stored at that state, and the metric for that path is also stored as the metric sm
i
k
for that state.
Chainback: when all of the states for the last time sample have been visited, the state S
i
d
having the lowest state metric is identified. The survivor path for this state is read from storage, and the corresponding state for time sample d−1 is thereby identified. The survivor path for this latter state is read from storage, and the chainback process is repeated until all of the states comprising the path leading to state S
i
d
(i.e. the most likely path through the state-time matrix) have been identified.
Thus, at any time k, the Viterbi algorithm calculates the metrics of the paths leading to states S
n
k
, determines the survivor paths (one for each of the n states S
n
k
), and stores the n survivor paths as well as their respective metrics. This is equivalent to storing, for every target state considered, the source state which leads to it. As such, any implementation of the Viterbi algorithm requires the use of an Add-Compare-Select (ACS) unit
150
, as illustrated in
FIG. 1B
, to perform these operations. The ACS unit
15
Brown Charles D.
Pham Chi
Qualcomm Incorporated
Seo Howard H.
Tran Khai
LandOfFree
High-speed ACS for Viterbi decoder implementations does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High-speed ACS for Viterbi decoder implementations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-speed ACS for Viterbi decoder implementations will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2595069