JP2002076924A - Viterbi decoder - Google Patents

Abstract

PROBLEM TO BE SOLVED: To simplify the branch likelihood computation processing of a Viterbi decoder for the enhancement of speed, provide a circuitry wherein soft decision likelihood information of decoded output is obtained, and propose a decoding method wherein the error rate of decoded output is improved in ranges at low input signal levels. SOLUTION: Branch likelihood for every code pattern is calculated in advance to create branch likelihood memory and, based on a code pattern arising from each state transition, the branch likelihood memory is referenced to accelerate branch likelihood computation. In addition, two sets of state likelihood memory are prepared and state likelihood before and after state transition are stored, so that soft decision likelihood information can be computed. Further, a decoding method of combination of most likelihood decoding and decoding by majority decision is used for path memory for storing the LSBs of state numbers to improve the error rate of decoding in ranges at low input signal levels.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an error correction code decoder, and more particularly to a Viterbi decoder effective for decoding a convolutional code.

[0002]

2. Description of the Related Art In order to improve the reliability of data transmission, an error correction technique for correcting a code error of transmission data occurring during transmission on a receiving side has been used in various fields. Among them, a Viterbi decoder capable of maximum likelihood decoding of a convolutional code is known to have a large error correction capability.

Prior to the description of the operation of a conventional maximum likelihood decoder, the concept of a state of a convolutional encoder and a trellis diagram which play an important role in maximum likelihood decoding will be described with reference to FIG.
3A is a block diagram illustrating a configuration of a convolutional encoder, FIG. 3B is a trellis diagram of eight states, and FIG. 3C is a trellis diagram of a basic unit.

The convolutional encoder shown in the block diagram of FIG. 3A comprises a shift register including exclusive OR gates 31 to 35 and 1-bit delay elements 36 to 38. Input data x ₀ is sequentially inputted to the 1-bit delay element 36 to 38, and sequentially outputs the delayed data _{x 1, x 2, x 3} . And depending on the connection of the exclusive OR gates 31~35, x ₀ x ₁ x ₂ takes the exclusive logical sum of x _3, generates an encoded output g ₀ and g _1, generated encoded output g ₀ and g to send _1. That is, in FIG. 3a, by the exclusive OR gates 31 and 32, x ₀ and x ₁ and x ₃ and are summed output Output _{g 0 (g 0 = x 0} + x 1 + x 3) , and the exclusive OR by the gate 33 and 34 and 35 and, the x ₀ and x ₁ and x ₂ and x ₃ and are summed output output _{g 1 (g 1 = x 0} + x 1 + x 2 + x 3).

[0005] The convolutional encoder shown in FIG.
Since two bits are output for each bit, the coding rate r = 1 /
2 Also, since a code is generated with 4 bits of input data, it is called a convolutional encoder with a constraint length K = 4.

The convolutional encoder shift registers 38, 37,
The 3 bits x ₃ x ₂ x ₁ held by 36 are called the state of the encoder. Since there are three bits, there are eight states from 000 to 111, and the encoding is performed while the eight states transit each time input data is input. FIG. 3B shows a transition state from the time point t _n-1 to the time point t _n (n is a natural number).

When the state of the encoder is state number x ₃ x ₂ x ₁ ,
Input data x ₀ is input to the convolutional encoder and shift register
Enter 36. At the same time, it enters from the shift register 36 to the shift register 37 x ₁ is outputted from the shift register 37 at the same time
x ₂ is output to the shift register 38 and the shift register
38 x ₃ is output from. Thus, the state of the encoder makes a transition to the state of the state number x ₂ x ₁ x _0.

That is, from state number x ₃ x ₂ x ₁ to state number x ₂ x ₁
since it is not a transition to _{x 0, m = x 2 x} 1 When (m = In 0～3,2 binary number m = 00-11) and for, when the x ₃ = 0 (0m, i.e. 000
011) and when x ₃ = 1 (1 m, that is, 100 to 111), x
₀ = when the 0 (m0, i.e., 000-110) and when x ₀ = 1 (m1,
That is, the state transits to the state of 001 to 111). That is, in decimal notation, m (x ₃ = 0, ie, “0m” in binary) and m + 4 (x ₃ = 1, ie, 2
2m (x ₁ = 0) and 2m + 1 ((x ₁ =
1)).

For example, when x ₃ = 0 (0 m), the state number
x ₃ x ₂ x ₁ is 0x ₂ x ₁ , and the transition from this state is to transit to the state of state number mx ₀ , and x ₀ = 0 (m0)
Or x ₀ = 1 (m1). Therefore m = 00
In the case of, the state changes from state number 000 to either state number 000 or state number 001. Similarly, when x ₃ = 1 (1 m), the state transitions from state number 100 to either state number 001 or state number 001. Further, for example, even in the case of m = 01, transition from the state is that a transition to a state of the state number _{mx 0, x 0 = 0 (} m0) or x ₀ = 1
(M1). Therefore, when x ₃ = 0 (0 m), state number 001 to state number 010 or state number 01
Transitions to either one. Similarly, when x ₃ = 1 (1 m), the state number 101 to the state number 010 or the state number 011
Transitions to either. Similarly, when m = 10, x ₃
When = 0 (0 m), transition from state number 010 to either state number 100 or state number 101, and when x ₃ = 1 (1 m), state number 110 to state number 100 or state number
Transition to one of 101. Similarly, when m = 11, when x ₃ = 0 (0 m), the state numbers 011 to 1
Transition to either 10 or state number 111, x ₃ = 1 (1
Also in the case of m), the state number 111 makes a transition to either the state number 110 or the state number 111. That is, the 8-state trellis in FIG. 3B is a combination of four basic unit trellises in FIG. 3C.

The encoded outputs g ₀ and g ₁ are calculated by the code generator polynomial shown in the following equation (1).

(Equation 1) However, the addition in equation (1) is performed by exclusive OR. Also, x
^T indicates a transposed vector of x.

As described above, the codes g ₀ and g ₁ output in accordance with the state transition of FIG. 3C are expressed by the following equation (1): x ₃ m, mx ₀ (m = x ₂
x ₁ ), the following equation (2) is obtained.

(Equation 2) However, in equation (2), x 'indicates the logical inversion of x. As described above, the trellis structure of the convolutional code (the state numbers before and after the transition and the code to be output) are state numbers m = 0 to 2
^{Given K-2} -1 (K is the constraint length), it is uniquely determined.

In the maximum likelihood decoder on the receiving side, the transition paths (8 in the example of FIG. 3B) reaching all the states at the time point t _n are held as candidate paths, and are obtained from the received signals y ₀ and y _1. Sign
The decoding is performed while estimating the state transition of the encoder by selecting the most probable transition path as the state transition of the encoder of the transmitter using r ₀ and r ₁ as clues (maximum likelihood selection). Here, likelihood is used as a quantity that specifically represents the likelihood. The Hamming distance between the codes g ₀ and g ₁ output with the state transition from the state number m to m ′ and the actually received codes r ₀ and r ₁ is taken as the branch likelihood of the transition branch. The received codes r ₀ and r ₁ identify the received signals y ₀ and y ₁ , where r = 0 when y> 0 and r = 1 when y <0. Such a likelihood obtained from the decoded values determined as 0 and 1 is called hard decision likelihood.

On the other hand, code (g ₀ , g ₁ ) associated with state transition =
(0,0), (0,1), (1,0), (1,1) are converted to orthogonal signal point coordinates (I, Q) = (1,1), (-1,1), (1, -1) and (-1, -1), and calculate the Euclidean distance between the quadrature signal point (I, Q) and the received signal point (y ₀ , y ₁ ), or the sum of the absolute values of the differences between the quadrature and in-phase components. There is also a method of giving the likelihood. In this case, the obtained likelihood (real value) is rounded to an integer value of several bits to be the likelihood.

The branch likelihood thus obtained is called a soft decision likelihood. Therefore, the branch likelihood is given by the following equation (3).

(Equation 3) Here, d _H (x, y) in Equation (3) represents the Hamming distance between the codes x and y. In an actual maximum likelihood decoder, a branch likelihood calculation unit as shown in FIG. 2 calculates the branch likelihood of all transition branches every time a received code is input. A maximum likelihood decoder based on the Viterbi algorithm will be described with reference to FIG.

FIG. 2 is a block diagram showing a configuration of a conventional maximum likelihood decoder (Viterbi decoder) used for decoding an error correction code. 20 is a branch likelihood calculation unit, and 3 is an addition comparison selection operation (A
CS: Add, Compare, Select) unit, 4 is a state likelihood memory, 5 is a path memory, and 6 is a maximum likelihood decoding unit. The branch likelihood calculation unit 20 calculates the branch likelihood of all transition branches every time a received code is input, and supplies the calculated branch likelihood to the addition comparison selection operation unit 3. The addition / comparison / selection operation unit 3 calculates the state likelihood using the input branch likelihood.

The state likelihood is the sum of all the branch likelihoods of the transition path leading to each state. Actually, as shown in the trellis diagram of FIG. 3B, each state has two transition branches, and thus the likelihood of each transition branch is 1
Add to the state likelihood before the state (Add) and compare the likelihood (Compa
re) and select the more likely transition path. Since the branch likelihood of each option is actually represented by the Hamming distance, the smaller the state likelihood, the more likely (the higher the likelihood).

The state likelihood calculated by the addition / comparison / selection operation unit 3 is given to the state likelihood memory 4 and stored in the state likelihood memory 4 and the transition information selected by the ACS (addition, comparison, selection) operation Is given to the path memory 5. The path memory 5 stores transition paths leading to all states. A transition path leading to a state having the highest state likelihood (smallest as a numerical value) when data input is completed is estimated as a transition path of the encoder, and the maximum likelihood decoding unit 6 performs maximum likelihood decoding and outputs the result.

As described above, in the maximum likelihood decoding method, received input data is not immediately decoded, but the likelihood of information is held in the form of state likelihood, and a transition path over a plurality of transmission symbols is decoded. Therefore, it is possible to reduce the influence of a noise component mixed for each symbol and reduce errors.

It is known that in a Viterbi decoder, when soft decision likelihood is used as branch likelihood, error correction capability is increased and a code error rate is improved. The soft decision likelihood is
It can be obtained by (2) and equation (3). That is, the number m of the basic unit trellis shown in FIG. 3C (m = 0 to 2 ^K−2 −1)
From the state number before and after the state transition (m, m + 2 ^K-2 → 2m, 2m +
1) is obtained, and codes g ₀ , g ₁ accompanying the state transition are calculated according to equation (2).
Is calculated. Next, the branch likelihood can be obtained by substituting g ₀ and g ₁ into equation (3). However, these series of operations can be performed relatively easily when the constraint length K is small, but when K is large, the amount of operation increases exponentially,
Processing time becomes longer.

In the calculation of equation (3), in the case of a hard decision, the received signal amplitudes y ₀ and y ₁ are converted into identification codes r ₀ and r ₁ ,
The Hamming distance is obtained, and in the case of soft decision, codes g ₀ , g ₁
Needs to be converted to the orthogonal signal point coordinates (I, Q) to find the Euclidean distance, which makes the computation process considerably complicated.

Further, as the error correction technique using convolutional codes and Viterbi decoding is applied to various fields, soft decision likelihood information is required for Viterbi decoded output. A method for obtaining a soft decision likelihood output will be described with reference to FIG. FIG.
FIG. 4 is a diagram for explaining trellis transition and surviving paths. Column
t ₁ ~t ₆ the time, 0-7 of the row numbers represent the state. In addition, a mark “○” is a symbol indicating a state by a column at the time and a row of the state. At the position where the column at time t _{1 and the} row at state 1 cross each other ○
Mark represents the state 1 at time t _1. Further, a solid line indicates a surviving path of a state transitioning from each time point, and a broken line indicates a difference in state likelihood of each trellis.

The likelihood of a code is represented by the distance between codes. The inter-code distance of a convolutional code can be represented by a Hamming distance of a code obtained when an information sequence different by one bit is encoded. As an example, from state 0 (state likelihood ms ₀ ) at time t = t ₁ in FIG. 4, the trellis when the information sequence x _A = (0, 0, 0, 0) is coded as A, The trellis when the sequence x _B = (1, 0, 0, 0) is encoded is denoted by B. _A code sequence g _A = (00,00,00,00) is output for the information sequence XA, and t = t ₅
State likelihood at the time of the ms _A = ms _0. On the other hand, for trellis B, the code sequence is g _B = (11,01,11,11), and t =
state likelihood at time t ₅ becomes ms _B = ms ₀ +7. Here, for information sequences x _A and x _B that differ by 1 bit, code sequences g _A and g
_B differs by 7 bits, which is called the minimum free distance of the convolutional code. Trellis A at t = t ₅
And trellis B transition to state 0,
3 (see FIG. 2), the trellis A (ms
_A <ms _B ) is selected and survives, and trellis B joins trellis A and is discarded. Thus, of the surviving paths (solid lines) reaching all the states, the path with the smallest state likelihood (broken line) is the maximum likelihood path.

The maximum likelihood decoding output of the Viterbi decoder is determined by the current maximum likelihood path. Now, at the time of t = t _6, the state 5 is determined maximum likelihood state (smallest states of the state likelihood), trellis C is discarded, and the trellis D is selected as the survivor maximum likelihood path. At this time, the likelihood for the maximum likelihood decoded output is the difference between the state likelihood of trellis C and trellis D. That is, the likelihood (mo) of the decoded output is the two state likelihoods (ms (m ₁ ), ms (m ₂ ), and m (m ₂ ) one time before the transition to the maximum likelihood state (m _L = 5).
m ₁ = m _L / 2, m ₂ = m _L / 2 + 2 ^K−2 (where “/” represents integer division) and two branch likelihoods (mb (m ₁ , M
_L ) and mb (m ₂ , m _L )) are given by the following equation (4).

(Equation 4)

To calculate the likelihood of the decoded output given by equation (4), the maximum likelihood state with the smallest state likelihood is searched from the state likelihood memory, and the maximum likelihood state before transition to the maximum likelihood state is calculated. One state likelihood must be obtained, and a branch likelihood accompanying this transition must be obtained. However, in the structure of the conventional Viterbi decoder, the state likelihood before the transition is discarded because the state likelihood memory is updated and the maximum likelihood state is searched when the state likelihood after the transition is calculated. Thus, the likelihood of the decoded output cannot be obtained. Further, in a situation where the input signal level of the Viterbi decoder is low and there are many transmission code errors in the transmission path, the decoder itself causes a decoding error and the code error rate becomes worse than when no coding is performed. The Viterbi decoder does not immediately decode even if the maximum likelihood path is obtained, but performs decoding with a delay (truncation length of the path memory) of 5 to 6 times the constraint length. This is due to the trellis merging being sufficient and one surviving path
By waiting for decoding until it is in a book,
This is to improve the reliability of the decoding result, and also to reduce the storage capacity of the path memory. However, in a state where there are many transmission code errors, trellis merging is not sufficiently performed and a plurality of paths survive. In other words, there is a path having no likelihood difference with the maximum likelihood path. In such a case, even if decoding is performed for the maximum likelihood path, the bit error rate of the decoded output cannot be improved. That is, when the input signal level is low, the code error rate becomes worse.

[0025]

The above-mentioned prior art includes the following:
It has the following disadvantages. (1) The amount of computation in signal processing for obtaining soft decision branch likelihood is large. (2) The soft decision likelihood information of the decoded output cannot be easily obtained. (3) When the input signal level is low, the error rate cannot be improved. An object of the present invention is to eliminate the above-mentioned drawbacks, and
Another object is to reduce the amount of calculation in the signal processing of the branch likelihood. A second object is to provide a configuration of a Viterbi decoder capable of easily obtaining soft decision likelihood information of a decoded output. A third object is to configure a Viterbi decoder that can improve the bit error rate of the decoding result when the input signal level is low.

[0026]

In order to achieve the first object, the Viterbi decoder according to the present invention divides the calculation of the branch likelihood into two-stage processing, and firstly, processes all the code patterns and received codes. The Hamming distance or the Euclidean distance is calculated in advance and stored in the branch likelihood memory, and the branch likelihood calculation process is simplified by referring to this branch likelihood memory by a code pattern associated with each state transition branch. It is a thing. In order to achieve the second object, two state likelihood memories are provided and used alternately so that the state likelihood before the temporary point is always held. Further, in order to achieve the third object, a path memory configuration capable of easily outputting a decoding result for an arbitrary surviving path is provided, thereby easily outputting a decoding result for an arbitrary surviving path. Is made possible.

[0027]

DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of a Viterbi decoder according to the present invention will be described with reference to FIG. FIG. 1 is a block diagram showing a configuration of a Viterbi decoder according to the present invention. 1 is a branch likelihood preprocessor, 2 is a branch likelihood memory, and 3 is an addition comparison selection operation (AC
S) unit, 4 is a state likelihood memory, 5 is a path memory, and 6 is a maximum likelihood decoding unit. In the embodiment of FIG. 1, the branch likelihood calculation unit 20 of the conventional Viterbi decoder of FIG.
Branch likelihood memory 2 divided into other components 3 to 6
Since the configuration and operation up to this point are the same as those in FIG. 2, detailed description is omitted.

In FIG. 1, the branch likelihood used for Viterbi decoding is obtained by dividing a reception signal (or a reception code identifying the reception signal) input to the Viterbi decoder and a transmission code (or orthogonal code) output along with the state transition. (Transmission signal assigned to signal point)
And the Hamming distance (or the Euclidean distance, or the sum of the absolute values of the differences between the in-phase and quadrature components). There are 2 ^K-1 combinations (K is the constraint length) of the transmission code according to the state numbers before and after the state transition, as shown in Expression (2).

However, the transmission code itself is 2 ⁿ (n is the number of bits of the code word, and if n = 2, (g ₀ , g ₁ ) =
(0,0), (0,1), (1,0), (1,1)).
Therefore, in the branch likelihood preprocessing unit 1, the branch likelihood determined by the reception code and 2 ⁿ transmission codes is calculated in advance by the equation (3), and is written in the branch likelihood memory 2. M in addition / comparison / selection operation unit 3
For (= 0 to 2 ^K-2 ) basic unit trellis, the state numbers before and after the state transition are obtained, and the branch likelihood is calculated by the transmission code (g ₀ , g ₁ ) output according to the state transition according to equation (2). Degree memory 2
, The branch likelihood is obtained. That is, as in the conventional example, for all state numbers m, the equation (2) and the equation
There is no need to perform calculation using (3), and the time for branch likelihood calculation processing can be reduced.

A second embodiment according to the present invention will be described with reference to FIG. FIG. 6 is a block diagram showing the configuration of the Viterbi decoder according to the second embodiment of the present invention. Components having the same functions as those described above are denoted by the same reference numerals.
In addition, 61 is a first state likelihood memory, 62 is a second state likelihood memory, and 63 is an output likelihood calculator. In the embodiment of FIG. 6, two sets of the state likelihood memory 4 and the second state likelihood memory 62 of the first embodiment of the Viterbi decoder according to the present invention shown in FIG. And an output likelihood calculating section 63 is further provided. Components 1-3 and
The operations 5 and 6 are the same as those in the embodiment of FIG.

In the embodiment shown in FIG. 6, the addition / comparison / selection operation unit 3 performs signal processing by switching the state likelihood memory depending on the evenness of the operation of the Viterbi decoder. That is, at an even time point, the state likelihood before the state transition is read from the first state likelihood memory 61, the ACS operation is performed to obtain the state likelihood after the state transition, and the second state likelihood memory 62 It is stored (the data flow is indicated by a solid arrow), and at an odd-numbered time point, it is read from the second state likelihood memory 62 and the ACS operation result is written into the first state likelihood memory 61 (the data flow is indicated by a dotted arrow). Shown). As described above, when the two sets of state likelihood memories 61 and 62 are used, the state likelihood before the state transition is held, so that
The output likelihood calculating section 63 can read the state likelihood immediately before the transition to the maximum likelihood state.

Further, the branch likelihood associated with the transition to the maximum likelihood state is read out from the branch likelihood memory 2 and calculated by equation (4), so that the soft decision likelihood information of the decoded output can be easily obtained. . In the embodiment of FIG. 6, the use of two sets of memories eliminates the necessity of updating the state likelihood memory associated with the ACS operation, so that the processing time can be reduced as compared with the conventional Viterbi decoder.

A third embodiment of the present invention will be described with reference to FIGS. Normally, the path memory stores path transition information (state number before the temporary point at which transition to the maximum likelihood state at the present time) obtained by the ACS operation. However, in this method, it is necessary to perform maximum likelihood decoding by going back by the truncation length of the path memory (traceback processing). A path memory configuration method that avoids this drawback and can easily output a decoding result for an arbitrary surviving path is disclosed in
No. 315976, entitled "Viterbi Decoder".
This path memory configuration method will be described with reference to FIG.

In FIG. 5, 51 and 53 are path memories, 52 is a path operation circuit, and 510, 511, 512, 530, 531 and 532 are one-word storage areas in the path memory. Path memory 51, 52
Has a storage area with a number of words equal to the number of states 2 ^K-1 ,
Each word can store data of the number of bits equal to the path memory cutoff length. The path memories 51 and 52 store the transition information (the state number m before and after the state transition m) obtained from the ACS operation unit.
_{Based on 0} → m ₁ ), the surviving paths leading to each state are stored.
Reads the m ₀ th path information first from the first path memory 53 for storing the path before the transition, MSB path calculating circuit 52
Shift one bit to the side. Next, the LS of the state number m ₁ after the transition
The B bit is stored in the LSB of the path information. The obtained new path information is stored in a second path memory 51 for storing the path after the transition.
Is written as the _first path information of m. In the path information thus obtained, the LSB bits of the state number at each time are arranged in time series. In the description of FIG. 3c, the LSB bit (x ₀ ) of the state number (x ₂ x ₁ x ₀ ) after the transition is the input bit of the encoder when the state transition occurs in the encoder, and it is immediately , Decoded bits when the code is received. Accordingly, the path information stored in the path memory of FIG. 5 is a decoded output for each surviving path.

When the path memory having the structure shown in FIG. 5 is used, a decoding result for each surviving path can be easily obtained.
When the input signal level is high, the surviving paths merge with the maximum likelihood path, so that all the path information in the path memory matches, but when the input signal level is low, multiple surviving paths Exist, and the respective decoded outputs are different.
Therefore, all the decoded outputs of the path memory are inspected, and the code with the larger ratio is regarded as the decoded output. If the input signal level is large, the decoding coincides with the maximum likelihood decoding, and if the input signal level is small, the majority decision is made. Decoding that matches decoding by determination can be performed.

FIG. 7 is a block diagram showing the configuration of the maximum likelihood decoder according to the third embodiment of the present invention. Components having the same functions as those described above are denoted by the same reference numerals.
In addition, 71 is a first path memory, 72 is a second path memory, 73 is a bit counter, and 74 is a decoding unit. In the embodiment shown in FIG. 7, the path memory 5 of the first embodiment of the Viterbi decoder according to the present invention shown in FIG. 1 is constituted by two sets of memories, a first path memory 71 and a second path memory 72. Further, a bit counter 73 and a decoding unit 74 are provided. Components 1-4
Is similar to that of the embodiment of FIG.

In FIG. 7, the first path memory 71 and the second
Path memory 72, as described in the description of FIG.
It has a storage area with the number of words equal to 2 ^K−1 , and each word can store data with the number of bits equal to the path memory truncation length. In the embodiment shown in FIG. 7, as in the embodiment shown in FIG. 6, signal processing is performed by switching the path memory depending on whether the operation of the Viterbi decoder is even or odd. That is, as described with reference to FIG. 5, at an even time, the path information before the temporary point is read from the first path memory 71, new path information is obtained in accordance with the transition information from the addition / comparison / selection operation unit 3, and the second path information is obtained. At the odd number, the second path memory 72
The path information before the temporary point is read from, and the obtained new path information is written to the first path memory 72. The bit counter 73 reads the bit at the bit position which is traced back from the path memory cutoff length of the 2 ^{K -1} surviving paths from the second path memory 72 at the even time and from the first path memory 71 at the odd time, The number of "0" (or "1") is counted. The counted value is input to the decoding unit 74, and the code with the higher counted value is used as the decoded output.

In the decoded output according to this embodiment, when the input signal level is large, the surviving path merges with the maximum likelihood path, so that the decoded output read from the path memory matches the result of the maximum likelihood decoding. On the other hand, when the input signal level is low, a plurality of surviving paths exist even when the path memory truncation length goes back, so that the likelihood difference between the maximum likelihood path and the other surviving paths decreases. However, maximum likelihood decoding does not always output a correct result. However, in the decoding method according to this embodiment, even in such a case, decoding by majority decision is possible, and the probability of correct decoding increases. In the embodiment shown in FIG.
Is integrated for a certain period of time, the code error rate of the decoding result can be estimated.

As described above, the Viterbi decoder of the present invention has the following features. (1) The amount of calculation of the branch likelihood can be reduced, and the processing can be speeded up. (2) Since the soft decision likelihood information of the decoded output can be output, various applications are possible. (3) Since the decoder automatically switches the decoding according to the maximum likelihood decoding and the majority decision according to the input signal level, the code error rate can be improved when the input signal level is low. (4) The decoder itself can estimate the error rate of the decoded output. (5) Since the structure includes two sets of the state likelihood memory and the path memory, the memory does not need to be updated, and the calculation processing time can be reduced.

[0040]

As described above, according to the present invention,
The following effects can be obtained. (1) The branch likelihood processing is simplified, and the processing time can be reduced. (2) Soft decision likelihood information of the decoded output is obtained. (3) A Viterbi decoder that automatically switches between maximum likelihood decoding and decoding based on majority decision can be configured.

[Brief description of the drawings]

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention.

FIG. 2 is a block diagram showing a configuration of a conventional Viterbi decoder.

FIG. 3 is a diagram illustrating a convolutional encoder and a trellis for explaining the operation of the Viterbi decoder.

FIG. 4 is an explanatory diagram of trellis transitions and surviving paths.

FIG. 5 is a diagram showing the principle configuration of a path memory used in the present invention.

FIG. 6 is a block diagram showing the configuration of an embodiment of the present invention.

FIG. 7 is a block diagram showing a configuration of one embodiment of the present invention.

[Explanation of symbols]

1: branch likelihood preprocessing unit, 2: branch likelihood memory, 3: addition / comparison / selection operation unit, 4, 61, 62: state likelihood memory, 5, 5
1, 53, 71, 72: path memory, 6: maximum likelihood decoder, 20: branch likelihood calculator, 31 to 35: exclusive OR gate, 36 to 38:
1-bit delay element, 52: path operation circuit, 510 to 512,
530 to 532: path memory storage area, 63: output likelihood calculation section, 73: bit counter, 74 decoding section.

Claims (6)

[Claims] 1. A branch likelihood of a Viterbi decoder for maximum likelihood decoding of a convolutional code having a coding rate r = k / n and a constraint length K for encoding k-bit information into an n-bit (n> k) code. In the arithmetic processing, a branch likelihood memory is provided in which a Hamming distance between all possible transmission codes and a reception code is stored as a branch likelihood, and the branch likelihood stored in the branch likelihood memory is provided. A Viterbi decoder which reads out a transmission code output in any state transition to perform the branch likelihood calculation process in all state transitions. 2. The Viterbi decoder according to claim 1, wherein
The branch likelihood memory stores, as branch likelihood, all possible transmission codes, Euclidean distances in the signal coordinate plane of the reception codes, or sums of absolute values of differences between in-phase components and quadrature components. And a Viterbi decoder. 3. The state likelihood of a Viterbi decoder that performs maximum likelihood decoding on a convolutional code having a coding rate r = k / n and a constraint length K for coding k-bit information into an n-bit (n> k) code. in the arithmetic processing, a first state likelihood memory, and a second state likelihood memory is provided, the even and odd state likelihood calculation processing time t _n, and the first state likelihood memory said second state using a likelihood memory alternately in the even time, t _n of the from the first state likelihood memory reads the state likelihood one time before (t _n-1), was carried out state likelihood calculation process The state likelihood at a point in time is written into the second state likelihood memory, and at odd points, the state likelihood before the temporary point (t _n−1 ) is read from the second state likelihood memory, and the state likelihood is read. The operation is such that the state likelihood at the time point t _n at which the arithmetic processing has been performed is written to the first state likelihood memory. Viterbi decoder. 4. The Viterbi decoder according to claim 1, further comprising: a soft decision likelihood output unit, wherein the first state likelihood is obtained at an even number time by an even / odd time of the state likelihood calculation processing time t _n. The maximum likelihood state (the state with the smallest state likelihood, the m-th state at the current time (t _n ) from the second state likelihood memory at the odd number time point and from the second state likelihood memory, where 0 ≦ m.
M ₁ = m / 2 before the temporary point (t _n-1 ) leading to ≦ 2 ^K−1 −1)
State likelihood ms (m ₁ ) and ms for the _2nd and m ₂ = m / 2 + 2 ^k−2 (where / indicates integer division) states
(M ₂₎ reads, the branch from the likelihood memory, branch likelihood mb with m from the _first state to transition to m-th state (m
₁ , m) and the branch likelihood mb (m ₂ , m) associated with the transition from the m ₂ state to the m th state, and mo = | ms (m ₁ ) −ms (m ₂ ) + mb ( m _1, m)
−mb (m ₂ , m) | (where | x | is the absolute value of x), and is output as soft-decision likelihood information for the decoding result at time point t _n . . 5. A Viterbi decoder for performing maximum likelihood decoding on a convolutional code having a coding rate r = k / n and a constraint length K for encoding k-bit information into an n-bit (n> k) code has a number of states. 2 ^Kk
The same number of path memories as described above are provided, and the LSB side k of the state number selected by the state likelihood calculation processing is stored at the position of the LSB side k bit which is obtained by shifting the storage content of the path memory by the MSB side by k bits. Write additional bit information,
In the Viterbi decoder configured to output overflow information as a decoded output by the shift operation of the path memory, the number of bits "1" (or "0") of the same digit in the ^2Kk path memories is counted. A Viterbi decoder having a counter and outputting a code having a larger count value of the counter as a decoding result. 6. The Viterbi decoder according to claim 5, wherein
A Viterbi decoder which accumulates a count value of the bit counter for a certain period of time and outputs the accumulated value as an estimated error rate of a decoded output.