Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-09-23
2001-07-17
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S796000, C714S794000, C375S262000, C375S265000
Reexamination Certificate
active
06263474
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a data decoding apparatus and a data decoding method used in a data transmission in a digital mobile telephone and a satellite communication.
2. Description of the Related Art
One of decoding methods for convolutional codes is the Viterbi decoding that uses the Viterbi algorithm. The Viterbi decoding is explained with reference to FIG.
1
.
FIG. 1
illustrates the case of transmitting information of J bits using a convolutional coder with constraint length K=3 and code rate R=½.
In
FIG. 1
, an input information sequence is stored in F
0
and F
1
of the shift register. Further when 1 bit is inputted, two bits of Ci(
1
) and Ci(
2
) are obtained as an output using the current input value (bi) and the two previous input values of (bi−1) and (bi−2) stored in the shift register.
An operation of the coder in the case of transmitting information of j bits using the coder is explained. First the states of F
0
and F
1
of the shift register are set at all 0, and J bits of the information sequence bn (n=0 up to N=j−1) are sequentially inputted. After all bits of the information sequence are inputted, further K−1=3−1=2 bits of 0 are input to set the all contents of the shift register at 0. The bit sequence to set the all contents of the shift register at 0 is called tail bit. According to the operation described above, a code sequence of 2×(J+K−1) bit length is obtained, and the obtained code sequence is transmitted via a radio transmission path.
At this time, the coder state S is set at either of following four states, i.e., S
0
=(0,0), S
1
=(1,0), S
2
=(0,1) and S
3
=(0,3) depending on the states of F
0
and F
1
in the shift register. The trellis structure is a representation showing the transition of states in the coder starting from the initial state S
0
according to each input of an information sequence signal.
FIG. 2
illustrates the trellis representation of the code sequence described above. In the Trellis representation, a part like a tree branch is called branch, and the linked more than two branches are called path.
In the Trellis representation illustrated in
FIG. 2
, a dotted branch indicates that an input signal is “0”, and a solid line indicates that an input signal is “1”. Further an input of the coder is indicated along a branch, and in the parenthesis, the left number indicates Ci(
1
) and the right number indicates Ci(
2
).
It is understandable with reference to
FIG. 2
that the coder has any states of S
0
up to S
3
according to the contents of input information sequence at time tJ, and terminates the state of S
0
by the input of tail bit at time tJ+2.
FIG. 3
illustrates a block diagram illustrating a configuration of a Viterbi decoder. The decoding method is explained with FIG.
3
. In the Viterbi decoder, the information sequence is decoded by reproducing the state transition of the coder using a received code sequence according to the following procedure.
First, received signal
1
received via radio transmission paths is in decider
2
converted into a received sequence with binary values of 0 and 1. The received sequence is input to ACS (Add Compare Select) processing section
3
. ACS processing section
3
performs the ACS processing using received sequence C′n(
1
) and C′n(
2
) corresponding to time tn in the trellis representation in FIG.
2
. In the ACS processing, the likelihood that indicates the matching degree of an output of the coder at each branch during time tn−1 up to time tn in the Trellis representation and the received sequence is obtained as a branch metric.
Two branches present at each state of time tn (the transitions from the different two states at time tn−1), and a branch of higher likelihood is selected according to the following way.
The sum of accumulated path metric at time tn−1 and a branch metric is obtained for each of the two branches, and the branch of higher likelihood is selected. Further the summed result of the selected metric is determined as the accumulated path metric of the state at time tn.
For instance, as illustrated in
FIG. 4
, obtain a selected path and an accumulated path metric of the state S
0
at time tn when it is assumed that (1,1) is obtained for C′n(
1
) and C′n(
2
) as a received sequence. The stated S
0
at time tn has two branches from the state S
0
and the state S
2
at time tn−1. When a hamming distance between the received sequence and the coder output is defined as a metric, the branch metric from S
0
to S
0
is 2, and the branch metric from S
2
to S
0
is 0. At time tn−1, the accumulated path metric at S
0
is 2 and the accumulated path metric at S
2
is 0, therefore the sum results of each branch are 4 and 0 respectively. Herein because the hamming distance is used as a likelihood, the smaller sum result is, the higher likelihood is. Accordingly, as the result of the state S
0
at time tn, the accumulated path metric is 0 by selecting the path from the state S
2
at time tn−1.
The above processing is performed for all times and all states in the Trellis representation, and each selected path is stored. In this case, it is already known at a received side that the state starts from S
0
at time t
0
. Then the path metric from S
0
at time t
0
is set at a value of high enough likelihood compared with other path metrics from S
1
up to S
3
at time t
0
, which is called initial weight.
Next the trace back processing is performed in trace back processing section
4
using the above result of the ACS processing. It is already known at the received side that the state of the coder at time tJ+2 is S
0
that is caused by the input of the tail bit at a transmit side. Therefore the state at time tJ+1 is obtained using the selected path at S
0
at time tJ+2 obtained from the ACS result.
By repeating the above processing, the state transition of the coder is obtained while going back to the previous state. Decoded information sequence
5
is obtained as described above when the coder state transition indicates the information sequence at the transmit side.
In the above explanation, as a metric, the hamming distance between a received sequence of 1 and 0 obtained by the hard decision and a coder output is used, however it is preferable to use more levels obtained by the soft decision than two levels of 0 and 1 as a received sequence in the Viterbi decoding. That makes it possible to improve the error correction capability in the Viterbi decoding.
In a mobile communication such as cellular telephone, the received level varies depending on the distance between a mobile station and a base station, and a cellular telephone of a-several-kilometer-radius has a variation range of 60 dB up to 80 dB. Further the received level varies several dB instantly by fading caused by multi-path propagation. In the case of applying the above Viterbi decoding to such transmission condition described above, a level variation is controlled by AGC (Auto Gain Control) and the like, and the soft decision Viterbi decoding is performed while controlling the variation range under 10~20 bits in the fixed point representation. It is easy to set the initial weight in this method because the level variation is made small enough.
In contrast to the method to perform the fixed point processing described above, there is another method to perform the soft decision Viterbi decoding in which a variation of a received signal is represented with a floating point using a floating point digital signal processing processor and the like. By using this method, it is possible to make the error correction decoding capability higher.
However in the soft decision Viterbi decoding in which the floating point processing is performed, as described above, the variation range of a received sequence remains the problem that it is difficult for ACS processing section t
De'cady Albert
Greenblum & Bernstein P.L.C.
Lamarre Guy
Matsushita Electric - Industrial Co., Ltd.
LandOfFree
Data decoding apparatus and data decoding 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 Data decoding apparatus and data decoding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data decoding apparatus and data decoding method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2505998