Processing unit and processing method

Details Processing unit and processing method Processing unit and processing method

2001-10-12

2002-11-05

Iqbal, Nadeem (Department: 2184)

Error detection/correction and fault detection/recovery

Data processing system error or fault handling

Reliability and availability

C714S795000

Reexamination Certificate

active

06477661

ABSTRACT:

The present invention relates to a processing unit, which is incorporated into a mobile communication apparatus, for performing an ASC (Addition, Comparison, and Selection) operation of particularly a Viterbi decoding.
BACKGROUND ART
In data communications in a mobile radio communication network, since a bit error frequently occurs, an execution of an error correction processing is needed. In the error correction methods, there is a method in which a convolutional code generated from an input bit is decoded by Viterbi decoding on a receiver side. In the error correction processing, a digital signal processor (hereinafter referred to as “DSP”) is used.
The Viterbi decoding repeats the simple processing such as addition, comparison, and selection and performs a trace-back operation for finally data, thereby realizing a maximum likelihood-decoding of the convolutional code.
The following will briefly explain the Viterbi decoding processing. The convolutional code is generated by mode
2
addition of input bits and a fixed number of bits precedent thereto. Then, a plurality of coding data is generated to correspond to one bit of the input bits. A number of input information bits having influence upon the coding data is called constraint length (K). The number of input information bits is equal to a number of stages of shift registers used in mode
2
addition.
The coding data is determined by the input bits and a state of the preceding (K−1) input bits. When a new information bit is input, the state of the input bits transits to a new state. The state in which coding data transits is determined by whether the new input bit is “0” or “1.” Since the respective (K−1) bits are “1” or “0”, a number of states in which coding data transits becomes 2
(K−1)
.
In the Viterbi decoding, received coding data sequence is observed, and the most-likely state is estimated from all obtainable state transitions. For this reason, every time when coding data (received data sequence) corresponding to one bit of information bits, an inter-signal distance (metric) of the respective paths to each state at that point is computed. Then, operations for leaving a path having a smaller metric among the paths reaching the same state as a survivor are sequentially repeated.
As shown in a state transition diagram of
FIG. 1
, in a convolutional encoder having a constraint length K, two paths each showing a state transition from each of state S[n] and S[n+2
(K−2)
] at one previous point extend to a state S[2n] (n=positive integer) at a certain point. For example, in a case of K=3, a transition from each of S[1] (state S
01
) and S[3] (state S
11
) to S[2] state S
10
) (state in which preceding two bits are input in order of “1” and “0”) at the time of n=1 is possible. Also, at the time of n=2, a transition from each of S[2] (state S
10
) and S [4] state S
00
) to S[4] state S
00
)(state shown by low-order two bits) is possible.
A path metric “a” is a sum of an inter-signal distance (branch metric) “x” between an output symbol of the path inputting to the state S[2n] and the received data sequence and a path metric “A.” The path metric “A” is the total sum of branch metrics of the survivor paths up to the state S[n] at one previous state. Similarly, a path metric “b” is a sum of an inter-signal distance (branch metric) “y” between an output symbol of the path inputting to the state S[2n] and the received data sequence and a path metric “B”. The path metric “B” is the total sum of branch metrics of the survivor paths up to the state S[n+2
(K−2)
] at one previous point. In the Viterbi decoding, the path metrics “a” and “b” inputting to the state S[2n] are compared with each other, and the smaller path is selected as a survivor path.
In the Viterbi decoding, each processing of addition for obtaining the path metric, comparison between the path metrics and the selection of path is executed with respect to 2
(K−2)
states at each point. Moreover, in the selection of path, a history showing which path has been selected is left as a path select signal PS[i], [I=0 to 2
(K−2)
−1].
At this time, if a subscript (e.g., n) of one previous state of the selected path is smaller than a subscript (n+2
(K−2)
) of one previous state of the non-selected other path, PS[i]=0 is established. If the subscript (n) it is larger than the subscript (n+2
(K−2)
), PS[i]=1 is established.
In the case of
FIG. 1
, since n<(n+2
(K−2)
) is established, the state S[n+2
(K−2)
] is selected at the time of a>b and PS[S2n]=1 is established, and the state S[n] is selected at the time of a≦b and PS[S2n]=0 is established.
Then, in the Viterbi decoding, data is decoded while being traced back to the path finally survived based on the path select signal.
The following will explain the conventional processing unit for Viterbi decoding, TMS320C54x, which is a general processing unit, (manufactured by TEXAS INSTRUMENTS, hereinafter referred to as “C54x”) being given as one example. In a GSM cellular radio system, equation (1) set forth below is used as a convolutional code.
G
1
(
D
)=1
+D
3
+
D
4
G
2
(
D
)=1
+D+D
3
+
D
4
  (1)
The above convolutional code is expressed by a trellis diagram of a butterfly structure shown in FIG.
2
. The trellis diagram shows a state in which the convolutional code transits from a certain state to another state. Let us assume that constraint length K is 5. States of 2
(K−2)
=16 or 8 butterfly structures are present for each symbol section. Then, two branches are input in each state, and a new path metric is determined by the ACS operations.
The branch metric can be defined as the following equation (2).
M=SD
(2
*i
)*
B
(
J
,0)+
SD
(2
*i
+1)*
B
(
j
,1)  (2)
where SD(2*i) denotes a first symbol of a symbol metric showing a soft decision input, and SD(2*i+1) denotes a second symbol of the symbol metric. B(J,0)and B(j,1) conform to codes generated by a convolutional encoder as shown in FIG.
3
.
In C54x, an arithmetic logic section (hereinafter referred to as “ALU”) is set to a dual 16-bit mode, thereby processing the butterfly structure at high speed. The determination of a new path metric (j) can be obtained by calculating two path metrics (2*J and 2*J+1) and the branch metrics (M and −M) in parallel based on a DSADT instruction and executing a comparison based on a CMPS instruction. The determination of a new path metric (j+8) can be obtained by calculating two path metrics and the branch metrics (M and −M) in parallel based on the DSADT instruction. The calculation results are stored in high and low order bits of a double-precision accumulator, respectively.
The CMPS instruction compares the high and low order bits of the accumulator and stores a larger value in a memory. Also, every time when the comparison is executed, which value is selected is written in a 16-bit transition register (TRN). The content written to the TRN is stored in the memory every time when each symbol processing is ended. Information to be stored in the memory is used to search a suitable path in the trace-back processing.
FIG. 4
shows a macro program for a butterfly operation of the Viterbi decoding.
The values of the branch metrics are stored in the T register before the macro is called.
FIG. 5
shows an example of a memory mapping of the path metrics.
8 butterfly operations are executed in one symbol section and
16
new states are obtained. This series of processing is repeatedly computed over several sections. After the end of the processing, the trace-back is executed so as to search a suitable path from 16 paths. Thereby, a decoding bit sequen

Affiliated with

Also associated with

Rating

Processing unit and processing method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Processing unit and processing method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing unit and processing method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2984084