Add-compare selection circuit

Details Add-compare selection circuit Add-compare selection circuit

1999-03-17

2003-03-04

Phu, Phuong (Department: 2631)

Pulse or digital communications

Systems using alternating or pulsating current

Plural channels for transmission of a single pulse train

C375S341000, C714S795000

Reexamination Certificate

active

06529557

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to an apparatus and method for processing a Viterbi algorithm, which may be used, for example, in a digital mobile communications system.
Viterbi decoders are used in digital wireless communication receivers to correct bit errors that occur in the wireless communication channel. With the Viterbi technique, an original data stream is encoded prior to transmission by adding bits thereto in a predetermined manner. The encoded bit stream is transmitted in a noisy channel which may produce bit errors due to multipath fading and the like. On the receive side, by decoding the received data stream using the Viterbi algorithm, the original data stream can be reproduced despite the occurrence of bit errors in the channel, provided that the number of bit errors is not excessive. Viterbi decoders operate by implementing a sequence determining method modeling a Gaussian channel.
Viterbi algorithms are widely used in mobile communications receivers owing to their excellent error correction rates. However, the Viterbi algorithm approach does involve substantial calculations and implementation time. In particular, the add-compare select (ACS) and trace-back portions of the computation require the most processing time. The ACS portion is used to determine the number of states in a convolutional encoder when a constraint length “K” is applied to the encoder. The trace-back portion uses simulation to determine a path length which plays an important role in determining the performance of the Viterbi algorithm.
In various mobile communication terminals which use time division multiple access (TDMA), such as in the Global Systems Mobile (GSM) system (a European digital mobile communications standard), since the time for processing received data is predetermined, the Viterbi algorithm must be as fast as possible. For example, since a TDMA cycle of the GSM system is limited to 4.615 ms, it is important to have a time margin for the purpose of achieving stable operation.
Recently, baseband systems have been implemented with digital signal processing (DSP). Since the Viterbi algorithm processing portion of the DSP requires numerous calculations and fast processing speed, a separate co-processing system is necessary. Although the Viterbi algorithm is determined in advance, there is still the possibility of improvements in design which increase speed and efficiency.
FIG. 1
is a block diagram of a conventional Viterbi decoder. A branch metric calculator (BMC)
1
b
receives a digital signal and calculates a branch metric value as probabilistic information. An add-compare selector (ACS)
2
b
uses the branch metric value from the BMC
1
b
to update a previous path metric corresponding to each state in a trellis. The ACS
2
b
compares the updated path metrics with each other and outputs a selected path metric and a determining bit. In a metric memory
3
b,
the path metric selected by the ACS
2
b
is fed back to the ACS
2
b
in a subsequent step. A path memory
4
b
stores the determining bit output from the ACS
2
b.
A trace-back controller
5
b
implements a trace-back operation using the determining bit stored in the path memory
4
b
and traces back the sequence of original information.
The conventional design of the ACS
2
b
will now be described. For the sake of explanation, an example of four states will be used. It is necessary to trace the most likely metric in the Viterbi algorithm for searching proper data. The following formula is used for calculating a survival metric in the Viterbi algorithm:
M
n
,s
0
=max(
M
n−1
p0
+bmc
1
p0
s0
,M
n−1
p1
+bmc
2
p1
s0
)
M
n
,s
1
=max(
M
n−1
p2
+bmc
1
p2
s1
,M
n−1
p3
+bmc
2
p3
s1
)
M
n
,s
2
=max(
M
n−1
p0
+bmc
1
p0
s2
,M
n−1
p1
+bmc
2
p1
s2
)
M
n
,s
3
=max(
M
n−1
p2
+bmc
1
p2
s3
,M
n−1
p3
+bmc
2
p3
s3
)  (1)
where M implies the survival metric of two metric values.
The BMC
1
b
generates the same metric value as that of the convolutional encoder and obtains the difference from received data, to generate branch metrics such as bmc
1
p0
s0
and bmc
2
p1
s0
. Thus, the survival metric of the present state is the larger value of two values, i.e., the first value being the sum of a first previous metric value and a first branch metric (of the present state) and the second value being the sum of a second previous metric value and a second branch metric (of the next state). To this end, at least two adders and a comparator are necessary.
To calculate the survival metric of the present state, the previous metric value stored in the metric memory
3
b
is read and compared with a value obtained by adding the read metric value and the present metric value. Then the most similar value to the transmitted value is searched.
FIG. 2
illustrates metric values of the respective states and calculated branch metric values for calculating the survival metric of the Viterbi algorithm. As shown, to calculate the metric value of a state 00, the previous metric value M
n−1
p0
is read. Then, a value obtained by adding the same to bmc
1
p0
s0
is compared with a value obtained by adding M
n−1
p1
to bmc
2
p1
s0
. Of the two values, the larger value is determined as the survival metric (M
n
,s
0
) of the state 00. Thus, to obtain one survival metric value, two cycles are required in each state just for reading the previous metric values. In other words, to calculate the survival metric value, the previous metric values 0 and 1 must be read in the state 00, and the previous metric values 2 and 3 must be read in the state 01. To calculate the survival metric values in the case of four states (e.g., states 00, 01, 10 and 10 in FIG.
2
), eight cycles are required just for reading the previous metric values.
Thus, with the above approach, the metric memory must be frequently accessed, resulting in excessive operations and power consumption. Also, since many clock cycles are required to compute survival metrics, this method is not suitable for a high speed Viterbi algorithm implementation, such as in a GSM communication system.
A Viterbi algorithm processing apparatus as that discussed above is useful for both a Viterbi equalizer and a Viterbi decoder. The term “equalizer” is a generic term for a signal processing device that can demodulate or decode a signal while compensating for certain imperfections in the radio link. The Viterbi equalizer effectuates this by using a model of the channel or propagation paths which is applied to hypothesized symbol sequences to predict what should be received. The hypothesis that most closely matches the actual received signal is then retained.
FIG. 3A
is a block diagram of a Viterbi algorithm processing apparatus
25
included in a Viterbi equalizer. The structure is similar to the decoder of
FIG. 1
, except the BMC
1
b
is replaced by a Euclidean Distance Calculator (EDC)
1
a.
FIG. 3B
is a block diagram of a Viterbi equalizer including the Viterbi algorithm processing apparatus.
Referring to
FIG. 3B
, an impulse response estimator
20
receives input data and measures a channel impulse response of the received data. A filter
10
is implemented by a finite impulse response (FIR) filter designed to have the maximum signal-to-noise ratio at the output terminal at a particular time. The filter
10
is a matched filter which multiplies a reversal of the channel impulse response input from the impulse response estimator
20
by the received data and then time-shifts the multiplied value. Viterbi algorithm processing apparatus
25
receives the data output from the filter
10
and the channel impulse response from the impulse response estimator
10
and performs the Viterbi algorithm for equalization. A demodulator
40
MSK demodulates data output from the Viterbi algorithm processing apparatus
25
. A reliability calculator
50
calculates the reliability of the data processed in the Viterbi algorithm processing apparatus
25
.
Such a Viterbi equali

Affiliated with

Also associated with

Rating

Add-compare selection circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Add-compare selection circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Add-compare selection circuit will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3036150