JPH0575480A - Convolutional code decoder - Google Patents

Abstract

(57) [Abstract] [Purpose] The likelihood between the received code and the signal that may occur is taken, and the one with the larger likelihood addition value is selected for each state of the convolutional code to make the survivor path. In a combiner that estimates the received signal by going up the remaining path in the past, normalizes the state likelihood so that the maximum state likelihood obtained by addition is always the maximum value that can be expressed by a predetermined bit. Reduce the estimated error rate. [Effect] The output of the likelihood addition selection memory 46, which selects a path having a larger likelihood addition value for each state and outputs the addition value, is stored in the pre-normalization state likelihood memory 49, and the maximum value search memory The largest one is selected in 51, and the normalized memory 54
At that time, a variable value indicating the difference between the maximum value and the maximum value that can be expressed is calculated, and this variable value is subtracted from each added value to calculate the state likelihood of each state for the next survivor path selection. It is stored in the state likelihood memory 55 as a degree.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a convolutional code decoder, and more particularly to a redundant convolutional code such as a convolutional code for a data code to be transmitted in order to reduce code errors in transmission data. Using the characteristics of the convolutional code and the statistical characteristics of noise, the received signal obtained by transmitting it as a code is converted into the decoded value with the highest probability among the multiple received values predicted in reverse in the past. The present invention relates to a decoder (Viterbi decoder) having a decoded value.

[0002]

2. Description of the Related Art A Viterbi decoder is particularly effective when reception power is limited and reception is required in a state where the signal-to-noise ratio is small, such as in satellite communication, and is more effective than when a Viterbi decoder is not attached. The error rate can be reduced by two digits or more. From another point of view, the power required to achieve the same error rate can be reduced by about 3 to 4 dB, and the transmission power can be reduced accordingly.

The Viterbi decoding algorithm is described in Reference 1 "Erro".
r Boundsfor Convolutional Codesand Asymptotically
Optimum Decoding Algorithm ”AJ Viterbi IEEE Tra
ns.on Information Theory IT-13 No.2 pp.260-269 Ap
First introduced in ril 1967. Also, reference 2 “Viterb
i Decoding for Satellite and Space Communication ”
JA Heller IEEE Transaction COM-19 No.5 October
1971 pp835 to 848 describes Viterbi decoding simulation and hardware. The Viterbi decoding algorithm does not compare all possible data sequences with the received sequence and selects the most probable (most similar) data sequence, but rather a limited number of data sequences for each received symbol. The following is an algorithm that can significantly reduce the amount of calculation by not considering the data series filtered out by selection. It is proved in Document 1 that the performance is the same as that in the case of comparing all the data series and the reception series even in this case.

The general configuration of the convolutional code decoder is an analog-to-digital (A / D) converter for converting a received analog signal into a digital signal, and the output of the A / D converter and the convolutional code. Means for obtaining as a path likelihood the correlation with the code generated in the path transiting from the past state to the current state, which is considered by the rule, and the path likelihood and the past state likelihood are added to obtain each current state. Of the current state, the output is estimated from the time-series information of the surviving path, that is, the decoding output. It is composed of a logic circuit for obtaining

The Viterbi decoder (US
P. 3789360 CONVOLUTIONAL DECODE) requires a large number of circuits in the configuration circuit. That is, it is necessary to prepare as many basic circuits for calculating the state likelihood as the number of states, and if this is realized by a common circuit and time-division multiplexing is performed, many multiplexers and demultiplexers are required. , The effect of circuit scale reduction does not increase. Further, a large number of the above logic circuits are required. In general, if the number of states is N, the scale of the logic circuit is twice as large as the number N of states, which is a practical disadvantage.

[0006]

In the Viterbi decoder, since the state likelihood of each state is obtained by adding the past state likelihood and the path likelihood, the addition is performed for a certain period, that is, over a plurality of time-series paths. Doing so significantly increases the number of bits required to represent the state likelihood. Therefore, a normalizing means for performing an operation of normalizing the value of the state likelihood within a certain range is required.

A Viterbi decoder (US
P 4015238 METRIC UPDATER FOR MAXIMUM LIKELIHOOD DE
In CODER), the normalizing means is configured to return a signal indicating that the state likelihood exceeds a certain fixed threshold value to the address of the ROM for addition / selection of the state likelihood and the path likelihood. ing. This means that the normalization is performed by subtracting a specific value from the state likelihood when the threshold value is exceeded, and the value indicating the state likelihood (4 bits
In that case, it cannot be said that the entire range of 0 to 15) is fully utilized, and the error rate characteristic is deteriorated.

A main object of the present invention is to effectively utilize the dynamic range of the state likelihood processing circuit of the decoder and attempt to improve the error rate characteristic.

[0009]

In order to achieve the above object, the present invention relates to a correlation (path likelihood) between a received signal of a convolutional code and a plurality of transmission path codes which may be generated by the convolutional code. For each of a plurality of states in the convolutional code, the output of the first means corresponding to a plurality of paths entering each state and the state likelihood of the state in which the path has occurred are added, Selects the surviving path having the maximum value among the plurality of added values corresponding to the plurality of paths, temporarily stores the added value corresponding to the selected surviving path as the state likelihood of the state, and selects Means for generating survivor path information indicating which of the plurality of paths enters each state, and survivor path information for each of the plurality of states in the convolutional code from the second means. Store In a convolutional code decoder having means for estimating the decoded value of the received signal that has gone up a certain time past from the time of existence, means for selecting the above surviving path and generating surviving path information, Furthermore, when the maximum addition value exceeds the maximum value that can be expressed by the number of bits assigned to the state likelihood, the variable value is subtracted from all the addition values to make each addition value less than or equal to the maximum value, and subtracted. Those having a negative result are characterized by having a value of zero and including a normalizing means for making the result the state likelihood of each state.

[0010]

As the variable value, the difference between the maximum value of the added values and the maximum value that can be expressed is typically used.
As a result, the maximum value of the state likelihood of each state temporarily stored for use in selecting the surviving path at the next time becomes the maximum representable value, and the result of subtraction becomes a negative state. The information on the difference between the likelihoods is stored as it is. Those with a small likelihood are less important for path selection, so
That is, regardless of the normalization, the dynamic range of the state likelihood can be fully used, and the survivor path selection with few errors can be performed. Instead of this, the smallest value of the added values is adopted as the variable value, and the subtraction is performed.
If the difference D between the maximum value and the minimum value of the added values exceeds the maximum value that can be expressed, the difference between the difference D and the maximum value that can be expressed is further subtracted from each value. May be. According to this, the maximum value of the state likelihood does not always become the maximum value that can be expressed, but it becomes a value close to this, and the dynamic range of the state likelihood is similar to the representative example described above. Can always be fully utilized.

[0011]

DESCRIPTION OF THE PREFERRED EMBODIMENTS First, in order to facilitate understanding of the present invention, the principle of encoding and decoding a convolutional code will be described with reference to the drawings.

FIG. 1 shows a typical communication system including a convolutional encoder and a decoder. The convolutional encoder 10 adds redundancy to the information bit (data to be transmitted) string output from the information source 1 and sends it to the transmission line 11. Noise 2 is added to the transmission line, and a symbol (received signal) c different from the transmission symbol (transmission line code) b output from the encoder 10 is received.

As shown in the figure, the information bit string a "010"
"" Is encoded by the encoder into a transmission code string b of "00, 11, 10 ...". The received signal c is "01, 11, 0.
This is an example in which the second "0" is changed to "1" due to noise. In the decoder 12, the convolutional code described below is applied regardless of the erroneous received signal. The source bit string a “010
... "is decoded and output to the output terminal 3.

In FIG. 2, r = 1/2 (r is called code efficiency and is represented by information bit length / transmission code bit length) K (constraint length) = 3 (K is the length of the encoder shift register) The following is an example of a convolutional encoder. The information bit string a is sequentially input to the 3-bit shift register 13 (shift register length ≧ constraint length). The modulo-2 adder 14 takes the modulo 2 of the first, second, and third bits of the shift register, and the other modulo-2 adder 15 takes the modulo 2 of the first, third bits of the shift register. Every time one bit is input to the shift register, the outputs of the two modulo-2 adders are alternately sent to the transmission line 11 by the switch 16.

FIG. 3 shows a state transition diagram of the convolutional code in FIG. In the figure, the state 20 that is wrapped in a circle is
It represents the front two bits of the shift register 13 of the convolutional encoder. The transition between states is represented by path d, the solid line path indicates the transition when the encoder input bit is “0”, and the broken line path indicates the transition when the encoder input bit is “1”. .. For example, the encoder input bit at the time of transition from state 11 to state 01 is "0". A 2-bit transmission line code (encoder output) corresponds to the path d. That is, when the state 11 transits to the state 01, the encoder outputs the channel code "01".

To clarify the time transition of the state transition diagram shown in FIG. 3, FIG. 3 is represented by the trellis diagram of FIG. In the figure, it means that the time goes to the right.

In FIG. 4, the only state 00 at time 0 is
This is because it is assumed that the initial state is 00. After time 2, the same pattern is repeated. Decoding (Viterbi decoding) of the convolutional code is performed by utilizing the repetitive nature of this same pattern. Next, how Viterbi decoding is specifically performed will be described with reference to FIGS. In Viterbi decoding, first, each state (00, 01, 10, 1
Correlation value in 1) (called state likelihood: state metric) e
Correspond to. In addition, an index (path likelihood) that represents the correlation between the received signal c = r ₁ r ₁ ′ and the transmission path code corresponding to the path p.
Corresponding f to each path). now,
Let us assume that at time n, each state likelihood e is all 0 (this assumption is given for convenience of explanation of Viterbi decoding operation). It is assumed that r ₁ r ₁ ′ is received between time n and n + 1. The path likelihood f corresponding to this received signal rr 'is illustrated in FIG. Next, at time n + 1, one of two paths entering each state is selected. The selection criteria are the starting point for each pass. The state likelihood e and the path likelihood f at time n are added to select the larger path, that is, the path having a stronger correlation, and this is called the surviving path. In addition, the added and selected likelihoods are the respective state likelihoods at time n + 1. A specific example will be described again. State 0 at time n + 1
Pay attention to 0. This state includes two paths p-1 and p-2, the starting point of the first path p-1 at time n is the state 00, and the starting point of the second path p-2 is the state. 01. In the case of the first pass p-1, state 00
State likelihood 0, path likelihood f 14 and total likelihood 1
It becomes 4. In the case of the second path p-2, the state likelihood of state 01 is 0, the path likelihood is also 0, and the total likelihood is 0. Therefore, the path p-1 is selected and the path p-2 is selected from the two paths entering the state 00 at the time n + 1. Pass p
-1 is the survivor pass. Also, the time n + 1 of state 00
The state likelihood at is 14.

The above-described operation is performed for all the states 00, 01, 10, 11 at time n + 1, one path is input to each state, and the state likelihood is stored.

After receiving r ₂ r ₂ ′ between the times n + 1 and n + 2, the exactly same operation is repeated at the time n + 2. FIG. 6 shows the surviving path and the state likelihood in the case of time n to n + 4.

As can be seen from FIG. 6, some of the surviving paths are cut off in the middle. Time n +
When tracing the survivor path q (shown by the thick line) from each state of 4, it can be seen that they merge into one at time n + 2. Before that, there was only one survivor pass,
An information bit corresponding to the surviving path (“0” if the path is a solid line, “1” if the path is a broken line) can be determined. That is, it is possible to determine which data series is correct and to determine the decoding output.

The survivor path information q is normally stored by storing which of the two input paths is selected for each state. For example, referring to FIG. 5, if the upper path p-1 of the two paths p-1 and p-2 entering the state 00 at time n + 1 is alive, it is "0", and the lower path p-. If 2 survives, "1" is stored. Storing the survivor path information in this way is equivalent to storing the second bit of the 2 bits (00, 01) representing the state at time n. Considering that the state represents the front two bits of the encoder shift register, it means that the encoder input bit one time before, that is, the information bit itself is stored.

For example, the surviving path information q at time n + 1 in FIG. 6 is 0, 0, 1, 0 for states 00, 01, 10, 11, respectively.

When the survivor path information is stored in this way,
When finally determining the decoder output, it is necessary to trace back the survivor path from the present to the past. An example of FIG. 6 will be described. At present, the time is n + 4. The paths that have survived to the present start from states 00 and 10 at time n + 3. Looking at the departure state at time n + 2 of the paths reaching states 00 and 10 at time n + 3, states 01 and 1
It is connected. After that, the time goes up to state 10 at time n + 1 and state 01 at time n.
You can see that the book paths are still alive. If there is only one surviving path, the information bit corresponding to the surviving path can be output.

Here, referring to FIG. 6, it can be seen that the state likelihood e of each state increases with time. This means that the number of bits required to store the state likelihood e will be infinite as it is. Therefore, in reality, an operation called normalization that keeps the state likelihood within a certain range is necessary.

In the decoder of the conventional example (US Patent 4015238), a signal indicating that the state likelihood exceeds a certain fixed threshold is used as the address of the ROM for addition / selection of the state likelihood and the path likelihood. Have returned to. This means that normalization is performed by subtracting a certain value from the state likelihood when the threshold value is exceeded, and all values (0 to 15 for 4 bits) representing the state likelihood are normalized. It cannot be said that the range is fully used, and the error rate performance is deteriorated.

FIG. 7 is a diagram showing the configuration of an embodiment of a convolutional code decoder according to the present invention.

The received signal c is input to the input terminal 40 and converted into a digital signal by the analog-digital converter 41. Usually, this digital signal is quantized by 3 bits. As an example, r = 1/2 (r:
Efficiency of the code), in the case of a convolutional code with K = 3, two received signals (eg r ₁ and r ₁ ′ in FIG. 5) entering in series in time.
And r ₂ and r ₂ ′) are obtained, the decoding process is executed. That is, two 3-bit digital signals (total 6 bits) corresponding to the two received signals (r ₁ , r ₁ ′)
s-1 and s-2 will be used at the same time. The two digital signals s-1 and s-2 serve as addresses of the memory 43. The memory 43 is a ROM that stores the pulse likelihood that represents the correlation between the received signal and the transmission path code. Therefore,
The memory 43 outputs two kinds of path likelihoods (a total of eight kinds of path likelihoods) corresponding to each state each time the above two received signals r and r ′ are input.

The path likelihood f which is the output of the memory 43 is 4 bits (16 bits) in order to eliminate the performance deterioration due to the reduction of the number of bits.
Level), which is the address of the memory 46.

The memory 46 adds the path likelihood f and the state likelihood e and selects the larger of the added state likelihoods.
It is a ROM having three functions of storing the surviving path information g. As the address of the memory 46, the path likelihood f described above is used.
In addition, the two state likelihoods h-1 and h-2 one hour before
is necessary. This is because in order to obtain the current state likelihood e, two state likelihoods e, which are the starting points of the two paths entering the state, and the respective path likelihoods f are necessary (but Since the two path likelihoods are actually in a one's complement relationship with each other, only one path likelihood has to be connected to the address of the memory 46).

The output 47 of the memory 46 represents a certain state likelihood f ′ to be added and selected, which is stored in the readable / writable memory (RAM) 49. The other output of memory 46 represents survivor path information g, which is RA
Stored in M50.

Each state likelihood stored in the memory 49 is represented by 5 bits. If the state likelihood is returned to the address of the memory 46 as it is, the capacity of the memory 46 becomes too large, and at the next time, 6 The need to express in bits arises, and it will increase by one bit over time. To solve this, each state likelihood is limited to 4 bits each time (this is called normalization). This is done as follows. The maximum value in each state likelihood stored in the memory 49 (referred to as pre-normalized state likelihood) is found. The output of the memory 49 is used as the address of the memory (ROM) 51. The other address 53 of the memory 51 represents the maximum value of the state likelihood that was previously determined and stored in the flip-flop 52. The function of the memory 51 is to compare two address values and output the larger one.
In this way, the maximum value of all the state likelihoods stored in the memory 49 is obtained and stored in the flip-flop 52.

When the maximum values of all the state likelihoods have been obtained, each state likelihood represented by 5 bits is represented by 4 bits. This has a maximum value of 15
It is executed by subtracting a variable value of (maximum value −15) from each state likelihood so as to be (maximum value that can be represented by 4 bits). If the result of the subtraction is less than or equal to zero, it is forcibly set to zero. In this way, the normalized state likelihood maximum value is always 15 (maximum value that can be represented by 4 bits), and the entire range that can be represented by 4 bits can be fully utilized. Therefore, the error rate deterioration can be prevented.

As an example, four states (00,0)
1, 10, 11) each state likelihood before normalization is 27, 1
Suppose it was 0,22,19. When the maximum value 27 is obtained, 12 (= 27-15) is subtracted from all the state likelihoods so that the state likelihood becomes 15. However, the second state likelihood is 10 −12 = −2 and is less than or equal to zero, so it is forcibly set to zero. Therefore, the normalized memory 5
The output of 4 is 15, 0, 10, 7 in each state and is represented by 4 bits. Each state likelihood thus normalized and represented by 4 bits is stored in the state likelihood memory 55, and is used as an address of the memory 46 when the received signal is next obtained.

FIG. 7 shows an embodiment in which the Viterbi decoder is realized by the state-to-state multiplex processing of one basic circuit.
The above concept can be applied to a case where a large number of basic circuits are arranged in parallel and processed instead of multiple processing. FIG. 8 shows an example of a circuit when the maximum value search memory 51 and the normalization memory 54 are arranged in parallel and processed. In FIG. 8, the maximum value 53 is obtained by using three memories 51 (generally, the number of states-1) for obtaining the maximum value of the state likelihood 47 before normalization.
Bit normalization memories 54 are prepared for the number of states and normalization is performed. This circuit also has the same effect as described above.

There are some other methods for reducing the variable value each time as means for normalizing state likelihood (keeping it within a certain range), but only another method will be shown here. This is shown below. Step 1: The maximum value (MAX) and the minimum value (MIN) of the pre-normalization state likelihood are calculated. Step 2: Determine MAX-MIN = D. Step 3: The variable value called MIN is subtracted from the pre-normalization state likelihood. Step 4: When D < 15, the result of step 3 is set as the normalized state likelihood. When D> 15, (D-15) is further reduced from the result of step 3, and when it becomes negative, it is forcibly set to zero and the normalized state likelihood is set.

In this method, basically, the minimum value of the pre-normalization state likelihood is searched, and the normalization is executed by subtracting it from all the pre-normalization state likelihoods. However, according to this method, when the difference between the maximum value and the minimum value of the pre-normalization state likelihood is larger than 15, the maximum value of the state likelihood after normalization becomes 15 or more, so the correction shown in step 4 is performed. Is required.

Also by this method, it is possible to fully utilize the range that can be represented by the number of bits assigned to the state likelihood after normalization by reducing the variable value and executing normalization every time. ..

FIG. 9 shows the configuration of an embodiment of the normalizing section according to the above method. The minimum value search 80 and the maximum value search 51 of the pre-normalization state likelihood memory 49 are performed to find the maximum value and the minimum value first. The subtracter 83 subtracts the minimum value from the normalized likelihood. On the other hand, the difference 82 between the maximum value and the minimum value is obtained by the subtracter 81, and the difference between 84 (value of 15) is further obtained by the subtractor 85. If the sign bit of the result of 85 is 1, that is, the difference between the maximum value and the minimum value is smaller than 15,
The selection circuit 87 selects the output of the subtractor 83. When the sign bit of the result of the subtractor 85 is “0”, that is, when the difference between the maximum value and the minimum value is larger than 15, the subtractor 83
The result of the subtracter 85 is further subtracted from the result of If the result of the subtractor 86 becomes negative, the output of the selection circuit 87 is set to zero, otherwise the output of the subtractor 86 is set to the output of the selection circuit 87. The output 88 of the selection circuit 87 represents the state likelihood after normalization.

The embodiment of the state likelihood normalization method has been described above.

Returning to FIG. 7 again, the memory 50 stores the surviving path information g. That is, of the two paths entering each state, "0" is stored if the upper path survives, and "1" is stored if the lower path survives. In this case, it is necessary to go up from the present to the past and follow the survival path.

The flip-flop 56 is for storing the survivor path at each time when going up from the present to the past. The memory 57 is a ROM that outputs a state in which the surviving path has passed one hour before, using the state 60 in which the surviving path has passed at a certain time and the surviving path information 59 in each state at that time as addresses. .. 61 represents the decoder output. In the present invention, the signal 60 representing passing / non-passing of each state of the surviving path is 4 bits (for the number of states) in the past, but is 2 bits (log ₂ (the number of states)) in the present invention. This is about 5 ...
When K (K = constraint length) time goes up, the surviving paths are aggregated into a single path, and the probability that they are not aggregated is sufficiently smaller than the error rate caused by noise added in the transmission path. This means that no matter which state is started at the beginning, if the time is reversed by 5K, the state of the sudden destination is the same. In other words, in the process of going backwards in time, no matter which state is started first, the same state is always passed if the time goes back 5K times. In this way, there is always one surviving path at each time in the process of going backwards, and there is only one passing state. Therefore, at each time, there should be a signal indicating which state the surviving path is passing through. That is, it is not necessary to use a signal of 1 bit for each state, that is, a total of 4 bits (for the number of states) to indicate which state the survivor passes.
2 bits (log ₂ (number of states)) is enough. Now, let these two bits be p ₁ and p ₂ and have the same bit configuration as the previous 2 bits of the encoder shift register, that is, the 2 bits representing the state. That is, when p ₁ = 0, p ₂ = 0, the state 00 is passed, when p ₁ = 0, p ₂ = 1, the state 01 is passed, and when p ₁ = 1 and p ₂ = 0, the state 10 is passed p _{When 1} = 1 and p ₂ = 1 respectively, it means passing through the state 11.

In this case, 2 bits representing the state where the surviving path one hour before passes through p ₁ ′ and p ₂ ′, c
_{If 1} , c ₂ , c ₃ , and c ₄ are survivor path information, p ₁ ′,
p ₂ 'is represented by the following equation.

P ₁ ′ = p ₂ (Equation 1) p ₂ ′ = ¬p ₁ · ¬p ₂ · c ₁ + ¬p ₁ · p ₁ · c ₂ + p ₁ · ¬p ₂ · c ₃ + P ₁ · p ₂ · c ₄ (Equation 2) where ¬ is a logical indefinite, · is a logical product, and + is a logical sum.

What is expressed as the above equation is shown in FIG.
The trellis diagram of can be used to explain as follows. In this explanation, it is easy to understand if one time before is considered as time 3 and the present is considered as time 4.

First, (Equation 1) will be described.

The fact that the 1 bit p ₁ ′ before 2 bits representing the passage or non-passage of the surviving path one hour before is 1 means that the state 10 or 11 is passed one hour before. According to the trellis diagram of FIG.
Only if the state 01 or 11 is currently passed.
That is, 1 after the state where the surviving path is currently passing.
Only if bit (p ₂ ) is 1. According to the formula, p ₁ ′ = p ₂ . In this case, it has nothing to do with the survivor path information.

Next, (Equation 2) will be described.

Shows whether or not the surviving path has passed one time before
1 bit of the last 2 bits p₂′ Becomes 1
It means passing the state 01 or 11 one hour before.
To taste. There are four possible cases. The surviving path information c of the state 00 that has passed the current state 00
₁If = 1 (lower path survives), use logical expression
For example, ¬p₁・ ¬p₂・ C₁, The current state 01 is passed and the surviving path information c of state 01
₂= 1, if expressed by a logical expression ¬p₁・ P₂・ C₂  The surviving path information c of the state 10 that has passed the current state 10
₃In case of = 1, if expressed by a logical expression, p₁・ ¬p₂・ C₃  The surviving path information c of the state 11 that has passed the current state 11
_FourIn case of = 1, if expressed by a logical expression, p₁・ P₂・ C_Four  The logical sum of the above four cases is (Equation 2).

The memory 57 shown in FIG. 7 has contents that match the logical expressions of (Equation 1) and (Equation 2).

If p ₁ and p ₂ have the same bit configuration as the 2 bits representing the state, either p ₁ or p ₂ may be the decoder output. This is because the state represents the first two bits of the shift register that constitutes the encoder in the first place, and the input signal to the shift register is the transmission information itself.

That is, in FIG. 7, the decoder output 61 is p ₂ itself after going up the time.

By doing so, no extra logic is required to output the final decoded value.

This will be described with reference to the specific example shown in FIG.
The current time is n + 4. In addition, the initial state is set to 00 (p
_{1 = 0, p 2 = 0} ). 4 bits of the input terminal 59 are 0000 from the surviving path information 36 (c ₁ = c ₂ = c ₃ = c ₄ =
0). At time n + 3, the state where the surviving path passes is 00 from equations (5) and (6) (p ₁ ′ = 0, p ₂ ′ =
0). The survivor path information at time n + 3 is 1010,
At time n + 2, the surviving path passes through state 01. After that, the same operation is repeated.

As described above, the signal indicating whether or not the surviving path passes each state one time before may be 2 bits (p ₁ ′, p ₂ ′) and p ₁ can be used to obtain it. ，
Only 6 signals of p ₂ , c ₁ , c ₂ , c ₃ and c ₄ are required. Generally, the number of states is N, and lo
g ₂ N signals will be good.

When the decoder output is estimated from the survivor path information in this manner, the circuit scale is N, and (N +
It is proportional to log ₂ N) and is smaller than the conventional one. For example, when N = 8, the decoder output estimation circuit is
If you try to implement it using ROM, the address 16
Bit (2 × N) is required, but in this embodiment, address 1
1 bit (8 + 3) is enough. That is, it can be realized by one ROM.

FIG. 10 shows another decoder output estimation circuit. Here, 62 is a multiplexer (Multiplexer), (Equation 1) can be realized by a simple wiring 65, and (Equation 2) uses p ₁ and p ₂ as control signals of the multiplexer, and 4 bits (c ₁ , This can be realized by selecting 1 bit of c ₂ , c ₃ , c ₄ ). In the configuration of FIG. 10, the same parts as those of the configuration of FIG. 7 are designated by the same reference numerals and description thereof will be omitted.

The embodiments shown in FIGS. 7 and 10 show an example in which the decoder estimation function is realized by multiplex processing of one basic circuit, but the basic circuits are prepared and processed in parallel for the number of times of reverse rise. There may be cases. FIG. 11 shows a case where the ROM of the basic circuit of FIG. Figure 1
2 shows the case where the multiplexing circuit of the basic circuit of FIG.

In the embodiment of FIG. 7, the state likelihood 55, the pre-normalization state likelihood 49, and the survivor path information 50 are stored in one RAM (read / write memory) with different addresses for each state. It is (thick part). As this address, a signal for selecting an input signal to the basic circuit and a signal for determining an output storage destination can be used as they are. As a result, the RAM and the basic circuit can be directly connected, and the multiplexing circuit, which has been frequently used in the past, can be completely eliminated. Therefore, the effect of reducing the circuit scale by the multiple use of one basic circuit increases.

The ripple effect when the Viterbi decoder is performed by the multiplex processing of the basic circuit will be described below.

FIG. 13 is a block diagram of FIG. 7 of the present embodiment. That is, the function of converting the received signal into a digital signal, the conversion into the path likelihood, the state likelihood storage memory, the storage of the surviving path information and the decoding output estimation unit correspond to the data conversion and storage unit 70. Addition / selection of state likelihood and path likelihood, function to obtain the maximum value of state likelihood,
The normalization unit that keeps the state likelihood within a certain range corresponds to the basic calculation unit 71. The control unit 72 controls the data conversion and storage unit 7.
Generate a control signal applied to zero. The timing generator 73 generates a timing signal required for the controller 72.

The block configuration of FIG. 13 has several advantages. First, consider a case where the constraint length is changed from K = 3 to K = 4 with r = 1/2. In this case, the number of states changes from 4 to 8. In the conventional parallel processing circuit (the same circuit is prepared for the number of states and operated in parallel), the circuit amount is doubled, and most of the wiring must be changed. However, in the configuration of FIG. 7, it is only necessary to double the data storage unit memory capacity and change the control unit clock unit.

That is, there is an advantage that the specification change can be dealt with flexibly.

When it is desired to process two channels at the same time, the data storage memory section is prepared for two channels.
It can be dealt with only by changing the control unit.

Further, when a high data rate is required, it is possible to deal with it by preparing a plurality of basic arithmetic units.

As described above, the circuit structure is highly expandable and flexible.

[0066]

EFFECT OF THE INVENTION In the state likelihood normalization circuit, a specific value is not subtracted from the pre-normalization state likelihood only when a fixed threshold is exceeded, but the variable value is reduced each time, Make full use of the entire range of likelihood values,
It is possible to prevent deterioration of error rate characteristics (performance).

As one of the methods, the maximum value of the pre-normalized state likelihood is calculated and the [maximum value-threshold value (15 is the maximum value when the state likelihood is represented by 4 bits)] is used as the variable value. There is a method of matching the maximum value of the state likelihood after normalization with the maximum value that can be expressed (15 in the case of 4 bits).

[Brief description of drawings]

FIG. 1 is a block diagram showing a communication system to which the present invention is applied.

FIG. 2 is a block diagram showing an example of a convolutional encoder.

FIG. 3 is a state transition diagram of a convolutional encoder.

FIG. 4 is a trellis diagram of the state transition diagram.

FIG. 5 is a trellis diagram illustrating a Viterbi decoding operation.

FIG. 6 is a trellis diagram showing survivor paths.

FIG. 7 is a block diagram showing an embodiment of a decoder of the present invention.

FIG. 8 is a block diagram showing a main part of another embodiment.

FIG. 9 is a block diagram showing a main part of still another embodiment.

FIG. 10 is a block diagram showing a decoded output estimation circuit of still another embodiment.

FIG. 11 is a block diagram of a decoded output estimation circuit according to still another embodiment.

FIG. 12 is a block diagram of a decoded output estimation circuit according to still another embodiment.

FIG. 13 is a block diagram illustrating an effect of changing the specifications of the embodiment.

Claims (2)

[Claims] 1. A first means for obtaining a correlation (path likelihood) between a received signal of a convolutional code and a plurality of transmission path codes which may be generated by the convolutional code, and a plurality of states in the convolutional code. Is added to the output of the first means corresponding to a plurality of paths entering each state and the state likelihood of the state in which the path has occurred, and the maximum value among the plurality of addition values corresponding to the plurality of paths is calculated. A survivor path having a value is selected, the added value corresponding to the selected survivor path is temporarily stored as the state likelihood of the state, and the selected survivor path is one of the plurality of paths that enter each of the above states. Second to generate survivor path information indicating whether
Means and third means for estimating the decoded value of the received signal that has gone up a certain time past from the present by storing the survivor path information for each of the states in the convolutional code from the second means. And the second means subtracts the variable value from all the addition values when the maximum addition value exceeds the maximum value that can be expressed by the number of bits assigned to the state likelihood, and then adds each addition value. A convolutional code decompressor including a normalization means that sets the value to zero if the result is less than or equal to the maximum value and has a negative result, and the result is the state likelihood of each state. 2. The normalizing means temporarily stores the addition value before normalization, and the maximum value of the maximum addition value temporarily stored and the maximum value representable by the number of bits assigned to the state likelihood. 2. The convolutional code decompressor according to claim 1, further comprising means for calculating a difference between and as a variable value.