Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
1999-03-16
2002-09-17
Phu, Phuong (Department: 2631)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C375S262000, C714S795000
Reexamination Certificate
active
06452985
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a Viterbi decoding apparatus and a Viterbi decoding method, and more particularly, is preferably applied to decode encoded data convolutionally encoded by using a Viterbi decoding algorithm in a cellular radio communication system.
2. Description of the Related Art
The field of mobile communication has been quickly advanced in recent years. Particularly, a cellular radio communication system represented by a portable-telephone system has been remarkably developed. In the cellular radio communication system, an area in which communication service is provided is divided into cells of a desired size, a base station serving as a fixed station is set in each of the cells, and a communication terminal unit serving as a mobile station performs radio communication with the base station which is likely under the best available communication condition.
Various systems have been proposed as communication systems of the above cellular radio communication system: for example, the frequency division multiple access (FDMA) system, the time division multiple access (TDMA) system, and the code division multiple access (CDMA) system. Particularly, the CDMA system has an advantage that a lot of channels per cell, that is, a large system capacity can be secured compared to other systems and is noticed as a next-generation cellular radio communication system. Actually, the CDMA system is standardized as the IS-95 standard by the Electronic Industries Association/the Telecommunications Industry Association (EIA/TIA).
Thus, various communication systems have been proposed. However, even when using any communication system, errors may occur in transmission data on a radio transmission line in the case of the cellular radio communication system because the system performs communication through a radio line. Therefore, in the cellular radio communication system, transmission data is convolutionally encoded in order to correct errors in the transmission mode and the encoded data thus obtained is transmitted through a radio transmission line, and the reception side correctly restores the transmitted data by Viterbi-decoding the received encoded data.
The convolutional encoding and Viterbi-decoding are specifically described below. The convolutional encoding is generally referred to as error correction coding, which is an encoding system for dispersing the information of transmission data into a plurality of data by successively applying the convolutional operation to the transmission data to be input. An encoder used for the convolutional encoding is constituted, for example, as shown in FIG.
1
. That is, a convolutional encoder
1
is constituted with a shift register
2
having a proper number of stages for successively capturing and shifting input transmission data S
1
and exclusive OR circuits
3
and
4
for performing a convolutional operation by applying the exclusive OR operation to the register value at a predetermined stage of the shift register
2
. The convolutional encoder
1
is a circuit for outputting output values C
1
and C
2
of the exclusive OR circuits
3
and
4
as encoded data.
Normally, in the case of convolutional encoding, the number of stages of a shift register is referred to as a constraint length and the rate of the number of encoded data to be output for an input of one bit is referred to as an encoding rate, and the convolutional encoding characteristic is specified by these parameters. In
FIG. 1
, the number of stages of the shift register
2
is “3” and the encoded data of two bits is output for the input of one bit. Therefore, as for the convolutional encoding characteristic, the constraint length is “3” and the encoding rate is “½”.
The encoded data to be output in the convolutional encoding is determined in accordance with a value currently stored in a shift register and a value currently input, and has regularity. For example, in
FIG. 1
, encoded data values (c
1
and c
2
) are determined in accordance with the two-bit values (a
2
and a
3
) being currently in the shift register
2
and the one-bit value (a
1
) currently input. In this case, when assuming that four states determined by the two bits (a
2
and a
3
) being in the shift register 2 are referred to as “A”, “B”, “C”, and “D”, the convolutional encoding can be expressed by the state transition diagram shown in FIG.
2
. In this case, the values written on the arrow for the state transition from each state to the next state denote the encoded data (c
1
and c
2
) to be output and the data (a
1
) then input.
A trellis diagram is obtained by arranging state-transition arrows output from the states A, B, C, and D shown by the above state transition diagram, in the temporally transverse direction as shown in FIG.
3
. In
FIG. 3
, a continuous line shows the case of an input value “0” and a dotted line shows the case of an input value “1”. In this connection, each arrow connecting the states is normally referred to as a branch, and a branch route until reaching an optional state is referred to as a path.
In this case, Viterbi decoding restores the convolutionally encoded data to the original data. The Viterbi decoding is also referred to a maximum-likelihood decoding method which restores the correct data to which error correction is applied by observing a received data series while considering a trellis diagram and obtaining the nearest data string on the trellis diagram. An index of likelihood referred to a metric is one of the scales for obtaining the nearest data string. The metric normally uses a hamming distance.
The hamming distance shows the distance between data and generally shows the difference between a received data series and the branch data on a trellis diagram. For example, when the received data series is (1,0), the series is different from the branch (0,0) on the trellis diagram by one bit. Therefore, the hamming distance between these data becomes “1” and therefore, the metric for the branch (0,0) results in “1”. Moreover, when the received data series is (1,1), it is different from the branch (0,0) on the trellis diagram by two bits. Therefore, the hamming distance between these data becomes “2” and the metric for the branch (0,0) results in “2”.
The Viterbi decoding computes a data series closest to a received data series by obtaining the metric of a branch (hereafter referred to a branch metric) at each time based on the received data series, obtaining the metrics of two paths (hereafter referred to as path metrics) input to each state based on the branch metric to select a higher-likelihood path, selecting the maximum-likelihood path out of the finally surviving paths, and inversely tracing the maximum-likelihood path (this operation is hereafter referred to as tracing-back).
Here, a case of transmitting a transmission data series (1,0,1,0,1,0,0) is considered as an example. When the above transmission data series is input to the register
2
of the convolutional encoder
1
shown in
FIG. 1
under the state in which the register
2
is initially set to (0,0,0), (11,01,00,01,00,01,11) is obtained as the encoded data values c
1
and c
2
. It is assumed that an actually-received reception data series is (01,00,00,01,00,01,11) because an error occurs in a transmission line when such encoded data is transmitted through the radio line.
In the case of Viterbi decoding, as shown in
FIG. 4
, initial values of path metrics of the states are first uniformly set to “0”, the hamming distance between the data value of the received reception data series and the data value of each branch is calculated under the above state to obtain each branch metric, and a path metric is computed in accordance with the branch metric and the path metric at the last time to select a likelihood path at any time. Note that each numeral entered in a circle in
FIG. 3
denotes a path metric. For example, at the time t
1
, two branches from the states A and C are input to the state A. The data value of the branch from the stat
Hatakeyama Izumi
Naito Masahiko
Maioli Jay H.
Phu Phuong
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-2817135