Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
1998-06-23
2001-10-09
Chin, Stephen (Department: 2734)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C714S794000, C714S795000
Reexamination Certificate
active
06301314
ABSTRACT:
TECHNICAL FIELD
This invention relates to a Viterbi decoding apparatus and a Viterbi decoding method used in maximum likelihood decoding of convolution codes, and more particularly to a Viterbi decoding apparatus and a Viterbi decoding method in which the circuit scale of normalization circuit which carries out normalization of a state metric has been reduced and high speed decoding operation has been realized.
BACKGROUND ART
Hitherto, as one of systems of decoding convolution codes, Viterbi decoding system is known. This Viterbi decoding system is the maximum likelihood decoding system with respect to convolution codes, and is adapted to select series nearest to received code series (This series will be called the maximum likelihood path hereinafter) from code series which can be generated from encoder of the transmitting side to thereby carry out error correction.
In the Viterbi decoding apparatus, when data received through transmission path from the transmitting side is inputted, series nearest to received code series (maximum likelihood path) is selected from code series which can be generated from encoder of the transmitting side to generate decode data on the basis of this selected content. Namely, in the Viterbi decoding apparatus, when received data is inputted, branch metric of this received data is calculated by branch metric calculating circuit to deliver this calculated result (branch metric) to ACS (Add Compare Select) circuit. Further, the ACS circuit adds and compares Hamming distance (branch metric) between receive signal and path and state metric of branch metrics until that time with respect to respective two paths caused to flow together to a certain state on the basis of branch metric delivered from the branch metric calculating circuit and state metric (accumulated sum) delivered from state metric memory circuit to select state metric of high likelihood on the basis of this comparison result to deliver this selected content to path memory circuit, and to deliver state metric newly obtained to normalization circuit.
In this case,
FIG. 1
is an explanatory view showing an example of transition diagram in the Viterbi decoding. In the case where constraint length is “3”, branch metric between receive signal and path and state metric of branch metrics until that time are added and compared with respect to respective two paths caused to flow together to a certain state every respective time slots. Thus, state metric of the high likelihood is selected on the basis of this comparison result.
The normalization circuit normalizes state metric outputted from the ACS circuit to allow it to be value within the range set in advance to deliver it to a state metric memory circuit. The state metric memory circuit stores the normalized state metric delivered from the normalization circuit to feed it back to the ACS circuit. Moreover, the path memory circuit stores selected content outputted from the ACS circuit to deliver it to maximum likelihood decoding judgment circuit. The maximum likelihood decoding judgment circuit judges the maximum likelihood path on the basis of the selected content stored in the path memory circuit to generate decode data to output the decode data thus generated.
In the conventional Viterbi decoding apparatus, there was used a normalization circuit
10
of a configuration as shown in
FIG. 2
, for example. This normalization circuit
10
is composed of a minimum value calculating circuit
11
, and plural subtracting circuits
12
. The minimum value calculating circuit
11
is supplied with state metrics corresponding to the number of states. The minimum value calculating circuit
11
calculates minimum value of all state metrics inputted thereto to output the minimum state metric. The respective subtracting circuits
12
subtract the minimum state metric from respective input state metrics to respectively output the subtraction results as normalized state metrics.
Meanwhile, in such a Viterbi decoding apparatus, an approach is employed in the normalization circuit to determine the minimum value from all state metrics sent from the ACS circuit to output the determined minimum value as correction value to subtract this correction value from respective state metrics to thereby carry out normalization thus to obtain normalized state metrics.
In general, in the Viterbi decoding, in order to enhance the error correction ability, constraint length K of code is caused to be large. With respect to the constraint length K of code, the number of states becomes equal to 2
k−1
. For this reason, in the normalization circuit, processing for calculating the minimum value from 2
k−1
number of state metrics every time slot is required.
Implementation of time required processing which detects the minimum value from 2
k−1
number of state metrics in the feedback loop returning to the ACS circuit via the normalization circuit and the state metric memory circuit from the ACS circuit lowers operation speed of the entirety of the Viterbi decoding apparatus.
Moreover, since the normalization processing is carried out by subtraction between corresponding state metric and the minimum value of the state metrics, in the case where the constraint length K is caused to be large, 2
k−1
number of subtracting circuits
12
are required in the above-mentioned normalization circuit
10
. As a result, the circuit scale is increased.
This invention has been made for the purpose of solving the above-described problems, and its object is to provide a Viterbi decoding apparatus having small circuit scale and capable of carrying out high speed operation. In addition, this invention has been made for the purpose of solving the above-described problems, and its object is to provide a Viterbi decoding method which permits reduction in the circuit scale and high speed operation.
DISCLOSURE OF THE INVENTION
FIG. 3
is an explanatory view of normalization processing for inverting Most Significant Bits (MSBs) in the case where the Most Significant Bits of state metrics are at logic “1” level in all states. It can be detected by using logical product circuit having inputs corresponding to the number of states that Most Significant Bits (MSBs) of state metrics are at logic “1” level in all states. Further, the system of inverting Most Significant Bit (MSB) to thereby carry out normalization processing is simple in the configuration, and is easy in the normalization processing.
The property of the state metric will now be described with reference to FIG.
4
. In the
FIG. 4
mentioned above, at a certain time slot, state in which the state metric becomes minimum among all states is assumed to be S. Further, when the state transition is advanced (time is passed) by time slot corresponding to the number of memories m, paths arriving from the previous state S to all states at the current time point are opened (formed). By the algorithm to select smaller one of metrics of the Viterbi decoding apparatus, metric values stored in the path memory circuit are metric values of paths passing from the state S or values smaller than the former at the time slot T+m.
Assuming now that the metric value of the state S at the time slot T is min, and width of (total) value of metrics added for a time period during which the state transition is advanced (time is passed) by time slot corresponding to the number of memories m is 0~Bmax, state metric values of all states at the time slot T+m are caused to fall within the range from min to min+Bmax. Namely, the state metric value at a certain time slot always falls within the width of Bmax.
In the case where state metric V of one state is taken out at a certain time slot to consider the relationship between this state metric V and the other state metric at the same time slot, since the state metric value is caused to always fall within the width Bmax, the following matter can be said.
When state metric of a certain state is V and state metric of the other state is V′, the following relationship holds:
V−B
max≦
V&
Chin Stephen
Jiang Lenny
Limbach & Limbach L.L.P.
Sony Corporation
LandOfFree
Viterbi decoding apparatus and viterbi 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 Viterbi decoding apparatus and viterbi decoding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoding apparatus and viterbi decoding method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2579996