JPH11266164A - Viterbi decoding device and Viterbi decoding method - Google Patents

Abstract

(57) Abstract: The present invention relates to a Viterbi decoding device, and can improve decoding accuracy and speed up decoding processing as compared with the related art. An initial path metric value of each state is set to a value weighted based on an initial value of a convolutional encoder, and a fixed state determined by a tail bit value when a path metric operation reaches a final operation is set as a starting state. By decoding the data sequence one bit at a time every time one step traceback is performed, the path metric can be accurately calculated, the number of tracebacks can be reduced, and the decoding accuracy is improved as compared with the prior art. And can speed up the decoding process.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[Table of Contents] The present invention will be described in the following order.

BACKGROUND OF THE INVENTION Prior Art (FIGS. 13 to 16) Problems to be Solved by the Invention (FIG. 17) Means for Solving the Problems Embodiments of the Invention (FIGS. 1 to 12) effect

[0003]

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, to a Viterbi decoding apparatus and a Viterbi decoding method which are suitably applied to decoding of convolutionally encoded data using a Viterbi decoding algorithm in a cellular radio communication system. It is.

[0004]

2. Description of the Related Art In recent years, the field of mobile communication has been rapidly developing. In particular, a cellular radio communication system represented by a cellular phone system has been remarkably developed. This cellular radio communication system divides an area for providing a communication service into cells of a desired size, installs base stations as fixed stations in the cells, and a communication terminal device as a mobile station enters a communication state. It communicates wirelessly with the best base station.

As a communication system of such a cellular radio communication system, FDMA (Frequency Division Multi
ple Access: frequency division multiple access (TDMA)
me Division Multiple Access (Time Division Multiple Access) or CDMA (Code Division Multiple Access)
: Code division multiple access) system and the like. Among them, the CDMA system has the advantage that it can secure a larger number of channels per cell, so-called system capacity, as compared with other systems, and has attracted attention as a next-generation cellular wireless communication system. , EIA / TIA (Electonic Industries Associati
on: Electronics Industry Association / Tele-communicationsIndustry As
Sociation: Telecommunications Machinery Industry Association) has standardized it as the IS-95 standard.

As described above, various communication systems have been proposed, but no matter which communication system is used,
In a cellular wireless communication system, since communication is performed via a wireless line, there is a possibility that an error occurs in transmission data in a wireless transmission path. For this reason, in a cellular radio communication system, at the time of transmission, convolutional coding is performed on transmission data for error correction, and the resulting coded data is transmitted via a wireless transmission path. The transmitted data is correctly restored by performing Viterbi decoding on the data.

Here, the convolutional coding and the Viterbi decoding will be specifically described. Convolutional coding is generally called an error correction code, and is an encoding method in which information of the transmission data is dispersed into a plurality of data by sequentially performing a convolution operation on input transmission data.
An encoder for this convolutional coding is configured, for example, as shown in FIG. That is, the convolutional encoder 1 includes a shift register 2 having an appropriate number of stages for sequentially receiving and shifting input transmission data S1, and the shift register 2
An exclusive OR circuit 3 that performs a convolution operation by performing an exclusive OR operation on the value of the register at a predetermined stage of
4 and outputs the output values C1 and C2 of the exclusive OR circuits 3 and 4 as coded data.

Normally, in convolutional coding, the number of stages of the shift register is called a constraint length, and the ratio of the number of coded data output to one bit input is called a coding rate.
The convolutional coding characteristics are specified by these parameters. In the example shown in FIG.
Since the number of stages of the shift register 2 is "3" and 2-bit encoded data is output in response to 1-bit input, the convolutional encoding characteristic has a constraint length of "3" and an encoding rate of "1". / 2 ".

The encoded data output in the convolutional encoding is determined by the value currently stored in the shift register and the value input this time, and has regularity. For example, in the example shown in FIG. 13, the 2-bit value (a
2, a3) and the one-bit value (a1) inputted this time determine the value of the encoded data (c1, c2). Here, the two bits (a2, a2,
Assuming that four states (hereinafter, referred to as states) determined by a3) are A, B, C, and D, this convolutional encoding is performed as shown in FIG.
This can be represented by a state transition diagram as shown in FIG. In this case, what is written on the arrow of the state transition from each state to the next state is the encoded data (c1, c2) to be output and the data (a
1).

[0010] A trellis diagram is obtained by arranging the state transition arrows from each of the states A, B, C, and D shown in the state transition diagram in the horizontal direction in time as shown in FIG. In FIG. 15, the solid line indicates the input value “0”.
, The dotted line indicates the case where the input value is “1”. Incidentally, each arrow connecting the respective states is generally called a branch, and a branch path leading to an arbitrary state is called a path.

Here, Viterbi decoding restores the encoded data subjected to such convolutional encoding to the original data. Viterbi decoding is also called maximum likelihood decoding, and observes a received encoded data sequence while considering a trellis diagram,
By obtaining the closest data string on the trellis diagram, the error-corrected correct data is restored. One of the measures for finding the closest data sequence is a measure of certainty called a metric.
Usually, the Hamming distance is used for this metric.

The Hamming distance indicates a distance between data, and generally indicates how different a received data sequence differs from data of a branch on a trellis diagram. For example, when the received data sequence is (1, 0), the branch (0, 0) on the trellis diagram is 1
Since the bits are different, the Hamming distance between these data is "1", so that the metric for branch (0, 0) is "1". Also, when the received data sequence is (1, 1), the Hamming distance between these data is "2" because it is different from the branch (0, 0) on the trellis diagram by two bits, so that the branch (0 , 0) is "2".

In Viterbi decoding, a metric of a branch (hereinafter, referred to as a branch metric) is obtained at each time based on a received data sequence, and two paths input to each state are determined based on the branch metric. For each metric (hereinafter referred to as a path metric), a more probable path is selected, a maximum likelihood path is finally selected from the surviving paths, and the maximum likelihood path is traced in reverse (hereinafter, referred to as a path metric). , This is called a traceback) to calculate the data sequence closest to the received data sequence.

Here, as an example, a transmission data sequence (1, 0,
(1, 0, 1, 0, 0) is considered. When such a transmission data sequence is input to the register 2 of the convolutional encoder 1 shown in FIG. 13 with the register 2 first set to (0, 0, 0), the encoded data c1,
(11, 01, 00, 01, 00, 01, 11) is obtained as c2. When such coded data was transmitted via a wireless line, an error occurred in the transmission path, and the received data sequence actually received was (01, 00, 00, 01, 00, 01, 1).
Assume 1).

In the Viterbi decoding, as shown in FIG. 16, first, the initial value of the path metric of each state is uniformly set to "0" (the number indicated by a circle in the figure indicates the path metric). The Hamming distance between the data value of the received data sequence received from this state and the data value of each branch is obtained to obtain each branch metric, and the path metric is calculated based on the branch metric and the path metric at the previous time to obtain a certain metric. I choose a pass that seems to be appropriate at any time. For example, at time t1, the branches input to state A include two branches from states A and C. The data value of the branch from state A is (0,
0) and the received data sequence is (0, 1), so that the branch metric of this branch is “1”.
The data value of the branch from state C is (1, 1)
Therefore, the branch metric of this branch is also “1”. In this case, since the branch metric is all "1", no path selection is performed, and the value "1" obtained by simply adding the branch metric "1" to the path metric "0" is used as the state A of the next state. Set as a path metric.

Similarly, at time t1, the branches input to state B include two branches from states A and C. Since the data value of the branch from state A is (1, 1) and the received data sequence is (0, 1), the branch metric of this branch is "1". Since the data value of the branch from the state C is (0, 0), the branch metric of this branch is also "1". In this case, similarly, since the branch metric is "1", no path selection is performed, and the value "1" obtained by simply adding the branch metric "1" to the path metric "0" is changed to the next state. Is set as the path metric of the state B.

Similarly, at the time t1, the branches input to the state C include two branches from the states B and D. Since the data value of the branch from state B is (0, 1) and the received data sequence is (0, 1), the branch metric of this branch is "0". Since the data value of the branch from state D is (1, 0), the branch metric of this branch is "2". Therefore, in this case, the path from the state B is selected (that is, the path from the state D is discarded), and the value obtained by adding the branch metric “0” to the path metric “0” of the state B is obtained. "0" is set as the path metric of the next state C.

Similarly, at time t1, the branches input to state D include two branches from states B and D. Since the data value of the branch from state B is (1, 0) and the received data sequence is (0, 1), the branch metric of this branch is "2". Since the data value of the branch from the state D is (0, 1), the branch metric of this branch is "0". Therefore, in this case, the path from the state D is selected (that is, the path from the state B is discarded), and the branch metric “0” is added to the path metric “0” of the state D to obtain a value “ "0" is set as the path metric of the next state D.

In the same manner, at times t2 to t7, when a path metric is calculated based on the received data and path selection is performed, a trellis diagram as shown in FIG. 16 can be formed.

As shown in FIG. 16, at time t
In step 7, "1", "3", "3", and "3" are obtained as path metrics of the states A, B, C, and D, respectively. In this case, since the state with the smallest path metric is the maximum likelihood state, the state A is the maximum likelihood state. Accordingly, when the trace back is performed from the state A, the correct decoded data (1, 0, 1, 0, 1, 0, 0) is restored by the path indicated by the thick line in the figure (each branch and the decoded data). Is easy to understand with reference to FIG. 14).

In the Viterbi algorithm described above, the path selection process by calculating the path metric and the path metric calculation process by adding the branch metric are usually called ACS (Add Compare Select) operation, and are exclusive ACS operations. It is realized by an arithmetic circuit. A trellis diagram as shown in FIG. 16 is formed by writing the path metric and the surviving path in a memory called a path memory every time the path metric is calculated by the ACS operation.

[0022]

In a cellular radio communication system, transmission data is usually transmitted for each predetermined data unit called a frame. Therefore, the convolutional coding process itself is also performed for each frame. It is processed to be completed within. When decoding coded data that has been convolutionally coded to be completed in units of frames using the above-described Viterbi algorithm, the memory length of the path memory is an important factor. This is because in the case of Viterbi decoding, the longer the distance of the trace back (that is, the longer the length of the path memory) is, the more the decoding accuracy can be improved. However, in practice, the use of a path memory having a memory length longer than the data length of encoded data hinders downsizing of a receiving apparatus. Therefore, usually, the constraint length of convolutional encoding is 5 to 6 times. A path memory about twice as long is used.

As shown in FIG. 17, in a Viterbi decoder for performing Viterbi decoding using a path memory having a memory length shorter than the data length of encoded data, as shown in FIG. When the path information (comprising the path metrics and the selected path) is fully stored in the path memory, the traceback is stored in the path memory starting from the most likely state among the last states in the path memory. , And decodes the first transmission data D ₁ , and when the transmission data D ₁ can be decoded, the path information input first as in a FIFO (First-In First-Out) memory Discard. Next, when the ACS operation is performed once, the path information obtained by the operation is input to the path memory, and the second transmission is performed by tracing the trace back for the path memory length starting from the maximum likelihood state among the last states. It decodes the data D _2. Hereinafter, the same processing is repeated, and every time new path information is input to the path memory, a traceback corresponding to the path memory length is performed to decode the transmission data. After the reception data is exhausted, the path information is calculated assuming that the reception data "00" has been received, and the transmission data is similarly decoded by performing a trace back for the path memory length.

Thus, in the conventional Viterbi decoder,
When the memory length of the path memory is shorter than the data length of the coded data, each time until the end of the transmission data D _n can decrypt performs ACS calculation necessary by performing Toresubatsuku only memory length portion of the path memory It is designed to ensure a high decoding accuracy. However, in the conventional Viterbi decoder, the ACS operation must be performed every time, and the traceback must be performed for the length of the path memory. Therefore, the processing becomes complicated, and the time required for the processing is increased, and the received data is rapidly processed. There is a problem that the decoding process cannot be performed.

The present invention has been made in view of the above points, and is intended to propose a Viterbi decoding device and a Viterbi decoding method capable of improving the decoding accuracy and speeding up the decoding process as compared with the prior art. is there.

[0026]

According to the present invention, a tail bit consisting of a predetermined value of (k-1) bits is set at the end of a data string of a predetermined length, where k is the constraint length of the convolutional encoder. The data string to which the tail bit has been added is converted to a symbol string generated by setting the initial value of each register of the shift register of the convolutional encoder to a predetermined value and performing convolutional encoding using the convolutional encoder. When receiving and decoding a data sequence from the symbol sequence, a path metric value weighted based on the initial value of each register is set as an initial path metric value of each state, and the symbol sequence is set based on the initial path metric value. Each time a path metric is received, the path metric value of each state is calculated sequentially, and the surviving paths are stored in the path memory. Until the path metric operation reaches the last operation in the symbol sequence, the data sequence is decoded one bit each time trace back is performed by the path memory length with the maximum likelihood state determined based on the path metric value as a starting state, When the path metric operation reaches the last operation in the symbol sequence, the data sequence is decoded one bit each time one step traceback is performed with the fixed state determined by the value of the tail bit as the starting state.

In this way, the initial path metric value of each state is set to a value weighted based on the initial value of the convolutional encoder, and when the path metric operation reaches the last operation, the fixed state determined by the value of the tail bit is obtained. , The data string is decoded one bit at a time every time one step traceback is performed, whereby the path metric can be accurately calculated and the number of tracebacks can be reduced.

[0028]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below in detail with reference to the drawings.

In FIG. 1, reference numeral 10 denotes a communication terminal device of a cellular radio communication system of, for example, a CDMA system to which the present invention is applied. For example, voice signals can be transmitted / received to / from another communication terminal device having the same configuration as that of the communication terminal device 10 via the communication terminal device. In the communication terminal device 10, during a call, the user's voice collected by the microphone 11 is converted into a voice signal S 10 and transmitted to the handset 12, and the voice signal S 10 is transmitted to the handset 12. Accordingly, the data is interface-converted and sent to the audio codec 13.

The voice codec 13 has a transmission speed of 9600 [bp]
[s]], and digitizes the audio signal S10 at a data rate corresponding to the data rate, and sends the resulting audio data D1 to the channel encoder 15 constituting the channel codec 14.

The channel encoder 15 performs a convolutional encoding process on the audio data D2 based on the control data D2 sent from the controller 16, performs an interleave process on the encoded data obtained as a result, and then performs the encoding process. A part of the data is replaced with another control information data D3 (for example, control information data indicating transmission power or the like) received from the controller 16, and the transmission symbol D4 thus obtained is replaced.
To the transmitter 17.

The transmitter 17 receives the carrier signal S11 from the synthesizer 18, performs a predetermined modulation process on the transmission symbol D4 based on the carrier signal S11, generates a transmission signal, and converts the transmission signal into a transmission band. By performing frequency conversion, a transmission signal S12 is generated and output to the antenna 20 via the duplexer 19. Thereby, the transmission signal S12 is transmitted to the base station (not shown) via the antenna 20.

On the other hand, the signal transmitted from the base station is received by the antenna 20 and input to the receiver 21 via the duplexer 19 as the received signal S13. The reception signal S13 has the same format as the transmission signal S12 transmitted by the communication terminal device 10 by performing the same process as the transmission process of the communication terminal device 10 at the time of transmission. The receiver 21 receives the carrier signal S14 from the synthesizer 18, performs a frequency conversion process on the received signal S13 based on the carrier signal S14, extracts a baseband signal, and performs a predetermined demodulation process on the baseband signal. Thus, the digital reception symbol D6 is extracted. Incidentally, the control information data D7 included in the received symbol D6 is separated here by the replacement processing and sent to the controller D7.

The channel decoder 22 of the channel code 14 first performs an information erasure process on a portion of the received symbol D6 from which the control information data D7 is extracted, based on the control data D8 output from the controller 16, The received symbol D6 is subjected to a deinterleave process, and subsequently the received symbol D6 is subjected to a Viterbi decoding process, whereby the audio data D transmitted through the base station is transmitted.
9 is restored.

The audio codec 13 converts the audio data D9 output from the channel decoder 22 into an analog audio signal S15, and outputs this to the speaker 23 via the handset 12. Thereby, the voice transmitted from the communication terminal device of the communication partner is output from the speaker 23, and the voice communication with the communication partner is established.

Incidentally, the controller 16 generates communication control data D5 at the time of call origination and the like, transmits it via the channel encoder 15 and the transmitter 17, and transmits the communication control data D10 transmitted from the base station to the channel. The data is received via the decoder 22, and based on the communication control data D5 and D10, the call is set, released, and maintained, and the I / O control of the key / display 24 is executed. In addition, the controller 16 controls the synthesizer 18 that generates the carrier signals S11 and S14 to control the transmission and reception frequency bands. Further, the controller 16
Is adapted to control the transmission power of the transmission signal S12 during transmission based on the control information data D7.

Here, the channel encoder 15 and the channel decoder 22 constituting the channel code 14 will be specifically described with reference to FIG.

First, the audio data D1 output from the audio codec 13 is input to the CRC generator 30 of the channel encoder 15. CRC generator 30
Based on the control from the controller 16, first, a predetermined bit CRC code is added to the predetermined bit audio data D 1 transmitted in frame units to generate transmission data D 20, which is output to the convolutional encoder 31. The convolutional encoder 31 performs control based on the control from the controller 16.
Transmission data D of a predetermined bit transmitted in frame units
After a tail bit having a constraint length of k-1 bits is added to the end of the transmission symbol D20, the transmission data D20 is subjected to a convolution operation to obtain a transmission symbol D2 composed of convolutionally encoded data.
1 is generated and output to the interleaver 32.

The interleaver 32 has a memory therein, stores the transmission symbols D21 in the memory in a predetermined order under the control of the controller 16, and stores the transmission symbols D21 in a different order from the writing order.
Is read from the memory to generate a transmission symbol D22 whose order is rearranged, and
Output to The replacement processing circuit 33 replaces a predetermined bit of the transmission symbol D22 with another control information data under the control of the controller 16, and sends the transmission symbol D4 obtained as a result to the transmitter 17.

On the other hand, the received symbol D6 output from the receiver 21 is first sent to the erasure processing circuit 3 of the channel decoder 22.
5 is input. The erasure processing circuit 35 includes the controller 1
6, the data part lost by the extraction processing of the control information data D7 by the receiver 21 is replaced with the lost data indicating the data lost part, and the resulting received symbol D25 is decoded. Interleaver 36
Output to The deinterleaver 36 has a memory therein, and stores the received symbols D25 in the memory in a predetermined order based on the control from the controller 16 and also stores the received symbols D2 in a different order from the writing order.
5 is read out, the rearrangement of the data performed on the transmission side is restored, and the resulting received symbol D26
To the Viterbi decoder 37.

The Viterbi decoder 37 decodes the audio data from the received symbol D26 using the Viterbi algorithm, and under the control of the controller 16,
By subjecting the received symbol D26 to Viterbi decoding, audio data D27 sent via the base station is decoded, and this is output to the error detector 38. Error detector 38
Extracts the CRC code added to the audio data D27 under the control of the controller 16, detects an error in the audio data D27 based on the CRC code, and notifies the controller 16 of the error, if any, through the controller 16. To the voice codec 13. The error detector 38
The voice data remaining after extracting the CRC code is output to the voice codec 13 as voice data D9.

Here, the data processing amount in the channel encoder 15 and the channel decoder 22 will be specifically described with reference to FIGS. In this communication terminal device 10, a time interval of a period of 20 [ms], that is, a frame is formed, and each data processing is performed in the frame unit, whereby data transmission is finally performed at 9600 [bps]. Has been made to do.

As shown in FIGS. 3 and 4, the audio codec 13 outputs 172 bits of audio data D per frame.
The CRC generator 30 outputs 172 bits of audio data D per frame.
1, the following equation:

[0044]

(Equation 1)

Generated by a generator polynomial as shown in
By adding a 12-bit CRC code, 18
The 4-bit transmission data D20 is generated and output to the convolutional encoder 31.

The convolutional encoder 31 first adds an 8-bit tail bit having a value "0" to the end of the 184-bit transmission data D20 per frame,
The transmission data of 192 bits is generated, and a convolution operation of a constraint length k = 9 and a coding rate R = 1/2 is performed on the transmission data to generate a transmission symbol D21 of 384 symbols per frame.

[0047] The interleaver 32
The transmission symbols D21 of 384 symbols are rearranged so as to be completed within a frame, and the resulting frame
The replacement processing circuit 33 replaces the transmission symbol D22 of 384 symbols.
Output to The replacement processing circuit 33
384 symbols of transmission symbol D22 are replaced with another control information data D3 at a rate of one symbol for every 12 symbols,
The resultant transmission symbol D4 of 384 symbols per frame is output to the transmitter 17. In this case, since 192 bits of information including the CRC code and the tail bit are transmitted per frame (20 [ms]), a transmission speed of 9600 (= 192 × 1 / 0.02) [bps] is realized. Will be.

On the other hand, as shown in FIG. 5, the receiver 21 outputs 384 received symbols D6 for each frame, and the erasure processing circuit 35 outputs the 384 received symbols for each frame. Of the D6, 32 symbols lost due to the extraction processing of the receiver 21 are replaced with other lost data, and the resulting 384 received symbols D25 per frame are output to the deinterleaver 36. In this case, the received symbol D6 output from the receiver 21 is formed by 16-value soft decision data in which one symbol consists of 4 bits.

The deinterleaver 36 rearranges the received symbols D25 of 384 symbols per frame so as to be completed within the frame and returns to the original order, and obtains the resulting received symbols D2 of 384 symbols per frame.
6 to the Viterbi decoder 37. Viterbi decoder 37
Is the received symbol D of 384 symbols per frame
26 using the Viterbi algorithm for the constraint length k =
9. Perform maximum likelihood decoding at an encoding rate of R = 1/2, and output the resulting 184-bit audio data D27 per frame to the error detector 38. In this case, the 8-bit tail bit added at the time of transmission is not output. The error detector 38 extracts a 12-bit CRC code from the 184-bit audio data D27 per frame, performs error detection, and outputs the resulting 172-bit audio data D9 per frame to the audio codec 13.

FIG. 6 shows the convolutional encoder 31 provided in the channel encoder 15 described above. This figure 6
As shown in (1), the convolutional encoder 31 includes a shift register 31A having eight stages of registers, and first and second exclusive OR circuits 31B for performing an exclusive OR operation on the value of a predetermined stage of the shift register. 31C. In this case, the first exclusive OR circuit 31B performs an exclusive OR operation on the value input to the first register and the output values of the second, third, fourth, and eighth registers. 1 coded data c1 and the second exclusive OR circuit 31C outputs the first
Output the second coded data c2 by performing an exclusive OR operation on the value input to the first register and the output value of the first, second, third, fifth, seventh and eighth registers. It has been made to be. Thus, the convolutional coder 31 outputs the coded data c1 and c2 every time one bit of the transmission data D20 is input, thereby transmitting the transmission symbol D2.
1 is generated.

Incidentally, in this case, the shift register 31A
Is eight, but the constraint length k is "9" because the value of the input stage is also used. Further, since the transmission symbol D21 of two bits is output each time one bit of the transmission data D20 is input, the coding rate R is "1/2".

In the convolutional encoder 31, by resetting the shift register 31A at the beginning of each frame, the initial value of each register of the shift register 31 is set to "0" to start the convolution operation. Has been made. When the transmission data D20 of 184 bits corresponding to one frame has been input, the constraint length k-1 bits, that is, eight "0" s are input as tail bits, thereby transmitting 384 symbols per frame. The symbol D21 is generated.

Subsequently, the Viterbi decoder 37 to which the present invention is applied
And its Viterbi algorithm will be specifically described. As described above, the receiver 21 receives the symbol D of the 16-value soft decision data in which one symbol is represented by 4 bits.
6 is output. As shown in FIG. 7, the 16-value soft decision data has the polarity of the symbol (that is, whether the data value indicated by the symbol is "0" or "1") according to the most significant bit (bit 3). Indicates the lower 3 bits (bit 2 to
Bit 0) indicates the reliability of the polarity. When the polarity is "0", the lower three bits are "111", indicating the highest reliability, and when the lower three bits are "000", the lowest reliability is indicated. ing. When the polarity is "1", the lower three bits of "000" indicate the highest reliability, and the lower three bits of "111" indicate the lowest reliability. I have.

Incidentally, the metrics BM0 and BM1 shown on the leftmost side of FIG. 7 indicate the probability that the symbol has the polarity "0" and the probability that the symbol has the polarity "1", respectively. In this case, the metric BM0
, And BM1 are represented in 16 steps with the value "0" being the maximum likelihood. Therefore, for example, "0111"
Is the highest reliability with polarity "0", the metrics BM0 and BM1 are represented by "0" and "F", respectively. For example, the symbol "1000" has polarity "1". Since some reliability is highest, the metrics BM0 and BM1 are represented by "F" and "0", respectively.

The received symbol D6 comprising such 16-value soft decision data is input to the erasure processing circuit 35, where erasure processing is performed. In this case, the erasure processing circuit 35
In order to indicate a part where data has been lost due to the control information data extraction processing of the receiver 21, the data of that part is set to "0000".
Is replaced with the lost data.

Therefore, the received symbol D25 output from the erasure processing circuit 35 becomes 14-value soft decision data as a meaning as shown in FIG. That is, in this case, originally, “0000” representing a symbol having the lowest reliability with the polarity “0” is assigned to the lost data, and “1000” representing the symbol having the highest reliability with the polarity “1” is assigned. Cannot be used. As a result, the remaining 14 values must represent the polarities “0” and “1”. Therefore,
Received symbol D25 output from erasure processing circuit 35
When the polarity “0” is expressed by the most significant bit (bit 3), the reliability is highest when the lower 3 bits (bit 2 to bit 0) are “111”, and when the lower 3 bits are “001”. In addition to the lowest reliability, when the polarity “1” is expressed by the most significant bit, the lower three bits are “001”.
, The reliability is highest, and the lower 3 bits are “111”.
In such a case, the conversion is performed in the erasure processing circuit 35 so that the reliability becomes lowest.

It should be noted that, in this case,
The metrics BM0 and BM1 are also expressed in 14 levels, with the value "0" indicating the highest probability and the value "D" indicating the lowest probability. By the way, in the case of the information lost data, the metrics BM0 and BM1 are both set to the value "0" in the sense of being distinguished from other data.

Thus, the received symbol D25 composed of the 14-value soft decision data passes through the deinterleaver 36 and is input to the Viterbi decoder 37 as the received symbol D26.

The Viterbi decoder 37, as shown in FIG.
Branch metric calculation circuit 40, ACS (Add-Compar
e-Select) arithmetic circuit 41, path metric storage unit 42,
It is composed of a maximum likelihood detector 43, a path selection information storage unit 44, and a data estimation circuit 45. The reception symbol D26 supplied from the deinterleaver 36 is first input to the branch metric calculation circuit 40.

The branch metric operation circuit 40 is configured as shown in FIG.
The received symbol D26, which is composed of 14-value soft decision data as shown in (1), is received. Based on the 4-bit value constituting each symbol of the received symbol D26, the metric B described above is used.
M0 and BM1 are obtained for each symbol. Then, since the coding rate R is 1/2, the branch metric calculation circuit 40 calculates the branch metric based on the metrics BM0 and BM1.
Two consecutive symbols of the received symbol D26 are (0,
0), (0,1), (1,0) and (1,1), ie, the branch metric BM (0,
0), BM (0, 1), BM (1, 0) and BM (1,
1) is calculated.

The operation of the branch metric will be described in detail. For example, two consecutive symbols A and B
And the metrics BM0 and BM1 of the symbol are BM0 (A), BM1 (A) and BM0, respectively.
(B) and BM1 (B), the branch metric calculation circuit 40 calculates

[0062]

(Equation 2)

By the operation shown in FIG.
And B are (0,0), (0,1), (1,0) and (1,1) branch metrics BM (0,0),
BM (0, 1), BM (1, 0) and BM (1, 1) are calculated.

Thus, the branch metric operation circuit 40
Performs the operation shown in equation (2) every time two received symbols D26 are input, and performs branch metrics BM (0, 0), BM (0, 1),
BM (1, 0) and BM (1, 1) are calculated and output to the ACS operation circuit 41 as branch data D30.

The ACS operation circuit 41 is a circuit for calculating path metrics of each state according to a trellis diagram.
In this case, since the constraint length k of the convolutional coding is set to “9”, the number of states is expressed by the following equation:

[0066]

(Equation 3)

As shown in the figure, there are 256 independent states.

The ACS operation circuit 41 first determines the state at the current time based on the branch metric given as the branch data D30 and the path metric at the previous time of each state read from the path metric storage unit 42 as the path data D31. The path metric of the two input paths is obtained, the maximum likelihood path input to each state is selected based on the path metric, and the path metric of the selected path is used as the path metric of the current time of each state. The data D32 is stored in the path metric storage unit 42.

Here, a specific example of this calculation will be described. 256
If each of the states is expressed using a two-digit hexadecimal number, it can be expressed as state 00 to state FF. Of these states, for example, for state 00, a first path a input from state 00 via branch (0, 0) and a second path a input from state 80 via branch (1, 1) There are two paths b. At this time, the path metric S00 of the first and second paths a and b (new
A) and S00 (new) b are path metrics S00 (old) and S00 of state 00 and state 80 at the previous time.
80 (old), branch metrics BM (0, 0) and B of branch (0, 0) and branch (1, 1)
It is determined by M (1,1). Therefore, the ACS operation circuit 41 outputs the branch metrics BM (0, 0) and BM (1, 1) given by the branch data D30 and the path metric S00 (old) given by the path data D31.
) And S80 (old), the following equation:

[0070]

(Equation 4)

The path metrics S00 (new) a and S00 (new) b of each path are obtained by performing the operation shown in FIG.

[0072]

(Equation 5)

By performing the judgment shown in FIG.
Of the paths a and b, the path having the smaller path metric is selected as the maximum likelihood path. And the ACS operation circuit 41
Sets the path metric of the path selected as the maximum likelihood path to the path metric of state 00 at the current time.

Thus, the ACS operation circuit 41 performs such processing for each state, calculates the path metric of each state at the current time, and stores this as path data D32 in the path metric storage unit 42.

In addition, the ACS operation circuit 41
The path metric of each state at the current time is stored in the path data D3.
3 is output to the maximum likelihood detector 43. Thus, the maximum likelihood detector 43 detects the maximum likelihood state among all the states at the current time based on the path data D33, and assigns the state number indicating the maximum likelihood state to the maximum likelihood state information D3.
4 is output to the data estimation circuit 45.

In addition, the ACS operation circuit 41
The path selection information D35 indicating the path selected from the two paths input to each state (this path selection information also includes path metrics) is output to the path selection information storage unit 44. The path selection information storage section 44 is a so-called path memory, and stores path selection information D35 at each time.
Are stored in order, so that the surviving path is stored. Note that the number of storage stages (that is, the path memory length) of the path selection information storage unit 44 is set to, for example, about 64 stages.

When a predetermined amount of data is stored in the path selection information storage unit 44, the data estimation circuit 45 determines the starting point of the trace back based on the maximum likelihood state information D34 output from the maximum likelihood detector 43 at that time. A state is determined, and a readout signal S20 is output to the path selection information storage unit 44 to sequentially obtain path selection information D36. By performing traceback sequentially from the starting state and following the surviving path, decoded data is obtained. And outputs the decoded data of the maximum likelihood as audio data D27.

Here, in the Viterbi decoder 37 having such a configuration, the following two parts are roughly divided.
The two processes are performed to increase the decoding characteristics of Viterbi decoding with high accuracy and to shorten the processing time. First, the first processing is to weight the initial value of the path metric of each state in consideration of the convolution characteristic. In the convolutional encoder 31 shown in FIG. 6, since the initial value of each register of the eight-stage shift register 31A is set to “0”,
"0" of the constraint length k-1 bit is added at the beginning of the transmission data D20.
Is equivalent to adding. Considering this fact, if the initial path metric of each state is set in advance to the path metric when data "0" is continuously input, and the ACS operation is performed starting from the path metric, the value of the path metric itself can be accurately obtained. can do. Based on this concept, in the Viterbi decoder 37, as shown in FIG. 10, a path metric of each state when data "0" is continuously input is calculated in advance, and this path metric is calculated by each operation. It is set as the initial value of the state.

In the second process, when the last ACS operation is completed (ie, when the last received symbol is received), data is decoded every time a traceback is performed by one step. Is set to the maximum likelihood state by the ACS operation,
It is set to. Convolutional encoder 3 shown in FIG.
In 1, the convolution operation is performed by adding a tail bit having a constraint length k-1 bit value "0" to the end of the transmission data D20, so that the final ideal state is state 00.
Should be reached. For this reason, when the last received symbol is received, the Viterbi decoder 37 performs a traceback starting from the state 00 of the ideal state which can be originally taken, instead of the maximum likelihood state by the ACS operation.

FIG. 11 shows a decoding algorithm of the Viterbi decoder 37 to which such first and second processes are added. As shown in FIG. 11, in the Viterbi decoder 37,
First, in step SP2 entered from step SP1, the initial value of the path metric of each state is shown in FIG.
Are set to the weighted values shown in. Specifically, the initial path metric of each state stored in the path metric storage unit 42 is set to the value shown in FIG.

In the next step SP3, the Viterbi decoder 37 performs an ACS operation on the basis of the received symbol D26, performs a path selection based on the ACS operation, and stores the path selection information D35. Specifically, first, the branch metric calculation circuit 40 outputs the branch metric B of the two symbols input as the received symbol D26.
M (0,0), BM (0,1), BM (1,0) and B
M (1,1) is calculated. The ACS operation circuit 41 stores the branch metric and the path metric storage unit 42.
The path metric of each path considered at the current time is calculated based on the path metric of the previous time stored in the path metric and the maximum likelihood path of each state is selected, and the path metric of the selected maximum likelihood path is stored in the path metric storage unit 42.
And path selection information D3 indicating the selected path.
5 is stored in the path selection storage unit 44.

At the next step SP4, the Viterbi decoder 3
7 judges whether or not the number of ACS operations is (path memory length + k-1) or less, and if the number of ACS operations is lower than the reference value, returns to step SP3 and repeats the processing.
When the number of ACS operations reaches its reference value, step SP5
Proceed to. This determination is made, for example, by the data estimating circuit 45, and is made by counting the number of outputs of the maximum likelihood state information D34. In this embodiment, since the constraint length k is “9”, the reference value is (path memory length + 8) times.

In the next step SP5, the Viterbi decoder 3
7 determines whether or not the currently performed ACS operation is the last ACS operation in the received symbol D26.
If it is not an S operation, the process proceeds to step SP6, where the last ACS
If it is a calculation, the process proceeds to step SP7. This determination is also made, for example, by the data estimation circuit 45.

At step SP6, the Viterbi decoder 37 sets the initial address of the trace back to the maximum likelihood state. That is, the data estimating circuit 45 sets the starting state of the trace back to the maximum likelihood state detected by the maximum likelihood detector 43.

In the next step SP8, the Viterbi decoder 3
7 is the path selection information D one time before.
36 is read from the path selection information storage unit 44 and traceback is performed for one step. In the next step SP9,
The data estimation circuit 45 determines whether or not the number of steps in the traceback has reached the path memory length. If the path memory length has not been reached, the process proceeds to step SP10, and if the path memory length has been reached, the process proceeds to step SP11.

At step SP10, the data estimation circuit 4
Reference numeral 5 creates a new trace back address based on the trace back performed previously, returns to step SP8, and repeats the process. That is, the data estimating circuit 45 sets the end point state of the trace back performed earlier to the start point state, and returns to step SP8 to perform the trace back again.

On the other hand, at step SP11, the data estimating circuit 45 determines that the trace back has been performed for the path memory length, and estimates one bit of the received data based on the finally reached state. Output as decoded data. When this process ends, the Viterbi decoder 37 returns to step SP3 and repeats the process.

On the other hand, when the process proceeds from step SP5 to step SP7 because of the last ACS operation, the data estimation circuit 45 sets the initial address of the traceback to the maximum likelihood state detected by the maximum likelihood detector 43. Instead of setting, set to state 00.

In the next step SP12, the data estimating circuit 45 reads out the path selection information D36 one time earlier from the path selection information storage unit 44 and performs traceback for one step. In the next step SP13, the received data is estimated for one bit based on the state reached in the traceback of one step, and is output as decoded data. In the next step SP14, the data estimating circuit 45 determines whether or not the number of steps of the trace back has reached the path memory length. If the path memory length has not been reached, the process proceeds to step SP15, and if the path memory length has been reached, the data is received. It is determined that all the decoded data has been decoded, and step SP16
To end the process.

At step SP15, the data estimation circuit 4
5 creates a new traceback address based on the one-step traceback performed earlier, and
Returning to P12, the process is repeated. That is, the data estimation circuit 45 sets the end point state of the trace back that has just been performed to the start state, and returns to step SP12 to perform trace back again. Thus, by executing such a Viterbi algorithm, the Viterbi decoder 37 decodes data in order from the received symbol D26.

In the above configuration, the communication terminal 1
0, the value of each register of the convolutional encoder 31 is set to “0” at the time of transmission, and the constraint length k−
The convolutional coding is performed by adding a 1-bit tail bit, and the resulting transmission symbol D21 is transmitted via the interleaver 32, the transmitter 17, and the like.

On the other hand, at the time of reception, a symbol generated by the same processing as the transmission processing is received via the receiver 21 and the deinterleaver 36 and the like, and the received symbol D26 is input to the Viterbi decoder 37. And decrypt the received data. In this case, the Viterbi decoder 37 converts the initial path metric of each state stored in the path metric storage unit 42 to a value weighted by focusing on the fact that the value of each register of the convolutional encoder 31 is initially “0”. After setting, the ACS operation is sequentially started from this state to calculate the path metric and select the path. Then, in the Viterbi decoder 37, the last ACS in the received symbol D26
Before performing the operation, traceback is sequentially performed for the path memory length starting from the maximum likelihood state having the smallest path metric value, and data is decoded one bit at a time every time the traceback for the path memory length is completed. When the last ACS operation is performed, data is decoded one bit at a time for each step trace back from the state 00 specified by the tail bit.

In this way, in the Viterbi decoder 37, the initial path metric value of each state is not set equally, but is set to a value weighted based on the initial value of each register of the convolutional encoder 31. As a result, the value of the path metric itself can be made more accurate than in the prior art, and data decoding can be performed more accurately, thereby improving the decoding characteristics of Viterbi decoding. In addition, in the Viterbi decoder 37, when the path metric operation is the last operation in the received symbol D26, one step trace back is performed with the state 00 determined by the value of the tail bit added at the time of convolutional coding as the starting state. Since the data is decoded one bit at a time, the number of traceback steps can be reduced as compared with the conventional case where traceback is performed by the path memory length every time, thereby speeding up the decoding process. In addition to this, traceback can be performed from an ideal state that can be originally taken, and decoding processing can be performed with higher accuracy.

FIG. 12 shows decoding characteristics when decoding is performed by the Viterbi decoder 37 according to the present invention. In FIG. 12, a curve A is a characteristic when decoding is performed based on the Viterbi algorithm according to the present invention. The initial path metric value of each state is weighted according to the initial value of each register of the convolutional encoder 31, and the path metric operation is performed. This is a characteristic when the state 00 determined by the tail bit at the time of completion is set as the traceback starting point state. Curve B is a characteristic obtained when decoding is performed based on the conventional Viterbi algorithm. The value of the initial path metric of each state is set uniformly to, for example, a value “0”, and the trace is always performed with the maximum likelihood state obtained by the path metric calculation as the starting point. This is the characteristic when backing up. Curve C shows the characteristics when the initial state value of each state is not weighted and the starting state is set to state 00 when the path metric calculation is completed. Curve D shows only the weighting of the initial path metric value of each state. This is the characteristic when the starting state is not set to state 00. As is clear from FIG.
As in the present invention, the value of the initial path metric of each state is weighted according to the initial value of the convolutional encoder, and the starting state when the path metric operation is completed is set to the state 00 determined by the tail bit. The bit error rate characteristics can be greatly improved.

According to the above configuration, at the time of Viterbi decoding, the initial path metric value of each state is weighted according to the initial value of each register of the convolutional encoder 31 and the value of the tail bit is obtained when the path metric operation is completed. By performing the trace back with the state 00 determined as the starting state, the number of trace backs can be reduced as compared with the conventional case, so that the decoding process can be performed at a high speed and the decoding characteristic can be compared with the conventional case. Can be improved.

In the above-described embodiment, a case has been described where the constraint length k at the time of convolutional coding is set to "9" and the coding rate R is set to "1/2".
The present invention is not limited to this, and the values of the constraint length k and the coding rate R may be other values.

In the above-described embodiment, FIG.
Although the case where the initial path metric value as shown in (1) is set has been described, the present invention is not limited to this, and other values may be set as the initial path metric value. In short, if the initial path metric value weighted based on the initial value of each register of the convolutional encoder is set as the initial value of each state, the same effect as in the above case can be obtained.

In the above-described embodiment, a case has been described where trace back is performed with state 00 as the starting state when the path metric operation is completed. However, the present invention is not limited to this, and the starting state is set to any other state. You may. The point is that if the starting state at the end of the path metric calculation is not set to the maximum likelihood state determined by the value of the path metric but to a fixed state determined by the value of the tail bit, the same as in the above case The effect of can be obtained.

[0099]

As described above, according to the present invention, the initial path metric value of each state is set to a value weighted based on the initial value of the convolutional encoder, and the tail bit is obtained when the path metric operation reaches the last operation. The fixed state determined by the value of
By decoding the data string one bit at a time each time a step traceback is performed, the path metric can be accurately calculated, the number of tracebacks can be reduced, and the decoding accuracy can be improved as compared with the prior art. In addition, a Viterbi decoding device and a Viterbi decoding method that can speed up the decoding process can be realized.

[Brief description of the drawings]

FIG. 1 is a block diagram showing an overall configuration of a communication terminal device to which the present invention is applied.

FIG. 2 is a block diagram showing a configuration of a channel code including a Viterbi decoder according to the present invention.

FIG. 3 is a block diagram for explaining a data processing amount of each block in a channel code;

FIG. 4 is a table showing a data processing amount in each block.

FIG. 5 is a block diagram for explaining a data processing amount of each block in a channel code;

FIG. 6 is a block diagram showing a configuration of a convolutional encoder provided in a channel code.

FIG. 7 is a table provided for explanation of 16-value soft decision data constituting a received symbol D6.

FIG. 8 is a chart provided for explanation of 14-level soft decision data constituting a received symbol D25.

FIG. 9 is a block diagram showing a configuration of a Viterbi decoder.

FIG. 10 is a table showing values of initial path metrics in each state.

FIG. 11 is a flowchart showing an algorithm of Viterbi decoding according to the present invention.

FIG. 12 is a characteristic curve diagram for describing decoding characteristics of Viterbi decoding according to the present invention.

FIG. 13 is a block diagram showing a configuration of a general convolutional encoder for explaining conventional Viterbi decoding.

FIG. 14 is a state transition diagram for explaining state transition in convolutional coding.

FIG. 15 is a trellis diagram obtained by expanding the state transition diagram in the time direction.

FIG. 16 is a trellis diagram for explaining a conventional Viterbi decoding algorithm.

FIG. 17 is a schematic diagram for explaining a trace back in the conventional Viterbi decoding.

[Explanation of symbols]

1, 31, a convolutional encoder, 2, 31A, a shift register, 3, 4, 31B, 31C, an exclusive OR circuit, 10, a communication terminal device, 11, a microphone, 12, a handset, and 13 ...... Voice codec, 1
4 ... channel code, 15 ... channel encoder, 16 ... controller, 17 ... transmitter, 18 ...
Synthesizer, 19: duplexer, 20: antenna, 21: receiver, 22: channel decoder, 23
... speaker, 30 ... CRC generator, 32 ...
Interleaver 33, replacement processing circuit 35, erasure processing circuit 36, deinterleaver 37, Viterbi decoder 38, error detector 40, branch metric calculation circuit 41, ACS calculation Circuit 42, a path metric storage unit 43, a maximum likelihood detector 44, a path selection information storage unit 45, a data estimation circuit

Claims (2)

[Claims] 1. A tail bit having a predetermined value of (k-1) bits is added to the end of a data string of a predetermined length, where k is a constraint length of a convolutional encoder, and the data string to which the tail bit is added is convolved with the convolution. Receiving a symbol sequence generated by setting the initial value of each register of the shift register of the encoder to a predetermined value and performing convolutional encoding using the convolutional encoder, and decoding the data sequence from the symbol sequence In the Viterbi decoding apparatus, a path metric value weighted based on the initial value of each register is set as an initial path metric value of each state, and each state is sequentially received each time the symbol string is received based on the initial path metric value. The path metric value is calculated, the surviving paths are stored in the path memory, and the path metric calculation is performed. Until the last operation in the symbol sequence is reached, the data sequence is decoded one bit at a time every time traceback is performed for the path memory length with the maximum likelihood state determined based on the path metric value as a starting state, When the path metric operation reaches the last operation in the symbol sequence, a decoding means is provided for decoding the data sequence one bit at a time for each step trace back from a fixed state determined by the value of the tail bit as a starting state. A Viterbi decoding device, characterized in that: 2. A tail bit having a predetermined value of (k-1) bits is added to the end of a data string of a predetermined length, where k is a constraint length of a convolutional encoder, and the data string to which the tail bit is added is convolved with the convolution. Receiving a symbol sequence generated by setting the initial value of each register of the shift register of the encoder to a predetermined value and performing convolutional encoding using the convolutional encoder, and decoding the data sequence from the symbol sequence In the Viterbi decoding method, a path metric value weighted based on the initial value of each register is set as an initial path metric value of each state, and each state is sequentially received each time the symbol sequence is received based on the initial path metric value. The path metric value is calculated, the surviving paths are stored in the path memory, and the path metric calculation is performed. Until the last operation in the symbol sequence is reached, the data sequence is decoded one bit at a time every time traceback is performed for the path memory length with the maximum likelihood state determined based on the path metric value as a starting state, When the path metric operation reaches the last operation in the symbol sequence, the data sequence is decoded one bit at a time for each step trace back from a fixed state determined by the value of the tail bit as a starting state. Viterbi decoding method.