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

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a technique relating to Viterbi decoding for decoding a trellis-coded modulated signal.

[0002]

2. Description of the Related Art As a conventional configuration for decoding a trellis-coded modulated signal, a Viterbi decoding device as shown in FIG. 13 has been proposed (see Japanese Patent Application Laid-Open No. Hei 5-335972).

FIG. 11 shows a trellis encoder to which this prior art is applied, and FIG. 12 is a trellis diagram relating to the trellis encoder shown in FIG. FIG. 11 shows a trellis encoder having a coding rate of 3/4 including one uncoded bit,
The constraint length is four. Therefore, the encoder has 2 ^(4-1) =
There are eight states, each of which corresponds to an encoder register D2,
According to the values {D2 D1 D0} of D1 and D0, respectively, {000}, {001}, {010}, {01}
1}, {100}, {101}, {110}, {11
It is expressed as 1｝. Also, the outputs {y2, y1,
A so-called subset is determined by the value of y0}, and a value obtained by directly viewing this bit string in binary notation is defined as a subset number. For example, {y2, y1, y0} = {1,
When 0, 1}, the subset number is "5", and this subset is represented as "subset s5". In addition,
In the conventional example, the subsets s0 to s7 are referred to as a subset A
ＨH.

The operation of the Viterbi decoding device shown in FIG. 13 will be described.

A branch metric generating circuit 601 obtains a Euclidean distance between a received signal and each transmission symbol, and calculates this as a branch metric BMs (s is a subset number from 0 to 7).
Value). Since one transmission subset includes two transmission symbol candidates, the branch metric corresponding to the uncoded bit “0” of the transmission symbol is represented by BMs0,
The branch metric corresponding to “1” is BMs1.

The subset maximum likelihood value determiner 602 selects and outputs the branch metric having the smaller Euclidean distance among the two transmission symbol candidates in the subset as the branch metric BMs for the subset.

[0007] The non-coded bit discriminator 603 extracts and outputs the non-coded bits of the selected transmission symbol candidate from the selection information output from the subset maximum likelihood value discriminator 602. The output non-coded bits are delayed by j stages corresponding to the number of delay stages in the path memory circuit 607 by the j-stage shift register 604.

In the trellis diagram shown in FIG. 12, the ACS circuit 605 determines the subset maximum likelihood value for the path metric of the surviving path of each state at the time t-1 at which the state transitions to the state at the time t. The branch metrics output from the unit 602 are added, and the value with the highest likelihood is selected from the added values as path metrics PM0 to PM7 of the surviving path. At the same time, the selected information is transmitted to the selection signal PS0.
It is output as .about.PS7.

FIG. 14 is a diagram showing a basic unit constituting the ACS circuit. FIG. 14 illustrates a basic unit corresponding to the state number i for simplifying the description. In the case of this conventional example, since the number of states is eight, eight basic units shown in FIG. 14 are arranged in parallel in the ACS circuit 605.

The adders 700a to 700d respectively include:
According to the trellis diagram of FIG.
To PMd and the branch metrics BMa to BMd are input, and the respective addition results are input to the comparator 701. The comparator 701 compares the addition results a to d, selects the value with the highest likelihood, and outputs a selection signal PSi according to the selection result.
Specifically, "0" is output when the addition result a is selected, and "1", "2", and "3" are output when the addition results b, c, and d are selected. Selection means 702
Receives the addition results a to d and outputs the corresponding addition result to the register 703 as a new path metric PMi for the state i according to the selection signal PSi.

[(PMa, BMa),
In the conventional example, the input order of (PMb, BMb), (PMc, BMc), (PMd, BMd)] is set as follows for each state. That is, <State 0> [(PM0, BM0), (PM2, BM4), (PM4, BM2), (PM6, BM6)] <State 1> [(PM0, BM4), (PM2, BM0), (PM4 , BM6), (PM6, BM2)] <State 2> [(PM0, BM2), (PM2, BM6), (PM4, BM0), (PM6, BM4)] <State 3> [(PM0, BM6), (PM2, BM2), (PM4, BM4), (PM6, BM0)] <State 4> [(PM1, BM1), (PM3, BM5), (PM5, BM3), (PM7, BM7)] <State 5 > [(PM1, BM5), (PM3, BM1), (PM5, BM7), (PM7, BM3)] <State 6> [(PM1, BM3), (PM3, BM7), (PM5, BM1), (PM5) PM7, BM5)] <State 7> [(PM1, BM7), (PM3, BM3), (PM5, BM5), (PM7, BM1)]

The path selection signals PS0 to PS7 output from the ACS circuit 605 are input to the path memory 607.
FIG. 15 shows the configuration of the path memory 607. The path memory 607 here basically has a configuration that embodies the transition to each node in the trellis diagram. The registers arranged at the positions corresponding to the respective nodes have the path selection signals PS0 to P
The one selected according to S7 is stored.

First, in the first stage, the subset number itself is selected by the path selection signal PSi, so that the subset number of each branch in the trellis diagram of FIG. For example, in state 0, when the path selection signal PS0 is “0”, (PM0 + BM0) has been selected, and the selection means 800 outputs the subset number “0” and stores it in the register 801. Similarly, when the value of the path selection signal PS0 is "1", "2", or "3", the selection means 801 outputs "4", "2", and "6" as the subset numbers, respectively. Similarly, for the states 1 to 7, the selection means 800 outputs the path selection signals PS1 to PS
7 to output a subset number x corresponding to the value of
01 is stored.

In the second stage, the value stored in the register corresponding to the node number in the first stage is selected. For example, for state 0, when the path selection signal PS0 is “0”, (PM0 + BM0) has been selected, so the selecting means 802 outputs the contents of the register corresponding to state 0 of the first stage and outputs the contents to the register 803. Store. Similarly, when the value of the path selection signal PS0 is “1”, “2”, or “3”, the selection unit 802 outputs the contents of the first-stage registers 4, 2, and 6, respectively. Similarly, for the states 1 to 7, the selecting means 802 outputs the contents of the register x of the first stage corresponding to the state number x corresponding to the values of the path selection signals PS1 to PS7 and stores the contents in the register 803.

In the third and subsequent stages, the same configuration as in the second stage is used.
It is repeated up to the stage. With such a configuration, the value stored in the register n of the j-th stage is such that the surviving path in the state n is the past at the j-th point by shifting the value between j clocks from the first stage to the j-th stage. This is the subset number in the passed state. The output of the final j-th register is input to the selector 608.

The maximum likelihood path determiner 606 is connected to the ACS circuit 60
5, the output PM0 of the register 703 in each basic unit
PM7 is input, and the state with the highest likelihood is detected from the input. Then, it outputs the status number and the corresponding register output. This register output value is the subset number at the time when the maximum likelihood path is j steps back. In the case of the encoder shown in FIG. 11, the upper two bits of the subset number are directly used as the encoded bits of the input information.
, The upper 2 bits of the subset number output as the decoded coded bits (x2, x1). The selector 609 selects the non-coded bit x3 for each subset number delayed by j stages according to the decoded subset number output from the selector 608. This uncoded bit x3 is output as a decoding result of the Viterbi decoding device together with the coded bit (x2, x1).

[0017]

However, the conventional configuration has the following problems.

First, conventionally, as shown in FIG. 15, a configuration representing a trellis diagram itself consisting of a combination of a selector and a register has been adopted as a path memory. Therefore, when the truncation length (j-th stage in the above example) increases or the number of states of the encoder increases,
The circuit scale of the path memory greatly increases. For this reason, the increase in the circuit area of the entire apparatus and the increase in power consumption become remarkable.

In the path memory as shown in FIG. 15, the connection to each selector is unique to each encoder. For this reason, it is very difficult to configure a general-purpose decoder that can support different encoders.

Conventionally, the path memory is configured to store the subset number itself. in this case,
For example, when the number of bits of the code is increased from 3 to 4 or 5 and the coding rate of the trellis encoder is reduced, the number of bits of the subset number increases.
The number of bits stored in the path memory increases. This also results in an increase in the circuit area of the entire device.

In view of the above problems, the present invention provides a Viterbi decoder for decoding a trellis-coded modulated signal so that a path memory can be constituted by a normal RAM,
It is an object to reduce a circuit scale and power consumption.

[0022]

Means for Solving the Problems In order to solve the above-mentioned problems, a solution taken by the invention of claim 1 is a Viterbi decoding device for decoding a trellis-coded modulated signal, the method comprising the steps of: Subset selection for receiving, as an input, a received symbol point and a transmission symbol having the highest likelihood for each subset, and outputting a branch metric corresponding to the selected transmission symbol and a subset selection signal for specifying the selected transmission symbol , A delay unit for delaying the subset selection signal for a predetermined time, and an ACS which receives the branch metric as input, calculates a path metric according to a trellis diagram, and outputs a path selection signal for selecting a path with high likelihood
(Add Compare Select) section, a traceback memory for storing the path selection signal, and a trace for tracing back the path selection signal stored in the traceback memory by a predetermined traceback length starting from a start node number. Using the back unit and the number of the first node through which the maximum likelihood path obtained by the traceback unit passes, the coding bit and the subset number related to the transition to the first node are calculated according to a trellis diagram. A subset number generation unit to be output, and a selection unit that receives the subset number and the subset selection signal output from the delay unit, and outputs an uncoded bit related to a transition to the first node, The coded bits output from the subset number generation unit and the uncoded bits output from the selection unit are decoded together. And it generates a signal.

According to a second aspect of the present invention, the Viterbi decoding apparatus according to the first aspect receives a path metric calculated by the ACS unit as an input, detects a path having the highest likelihood from the path metric, and determines the path with the highest likelihood. It is provided with a maximum likelihood path determination unit that outputs a passing node number, and the traceback unit obtains the start node number based on the node number output from the maximum likelihood path determination unit.

According to a third aspect of the present invention, in the Viterbi decoding apparatus according to the first aspect, the subset number generating section includes the first number.
, And the number of the second node through which the maximum likelihood path has passed one time in the past of the first node, to generate the coded bit and the subset number.

According to a fourth aspect of the present invention, in the Viterbi decoding device according to the third aspect, the subset number generation section includes the first number.
And table data representing the relationship between the second node number, the coded bit and the subset number.

According to a fifth aspect of the present invention, in the Viterbi decoding device according to the first aspect, the subset number generation section includes the first number.
The encoded bit and the subset number are generated using the node number of the first node and the path selection signal corresponding to the first node.

According to a sixth aspect of the present invention, in the Viterbi decoding device according to the fifth aspect, the subset number generation section includes the first number.
, And table data representing the relationship between the coded bit and the subset number.

According to a seventh aspect of the present invention, the subset number generating section in the Viterbi decoding apparatus according to the third or fifth aspect is configured by an arithmetic unit that performs an operation based on a generator polynomial of an encoder. .

According to the invention of claim 8, the subset selecting section in the Viterbi decoding apparatus of claim 1 generates the subset selection signal so as to match an uncoded bit corresponding to the selected transmission symbol. And

According to a ninth aspect of the present invention, the ACS unit in the Viterbi decoding apparatus according to the first aspect further comprises:
It is assumed that the signal is generated so as to match the encoded bit relating to the transition to the node corresponding to the path selection signal.

According to a tenth aspect of the present invention, there is provided a Viterbi decoding method for decoding a trellis-coded modulated signal based on a received signal and a maximum likelihood of a received symbol point for each subset. Selecting a high transmission symbol, generating a branch metric corresponding to the selected transmission symbol and a subset selection signal for identifying the selected transmission symbol, and delaying the subset selection signal by a predetermined time, An ACS (Add Compare Select) step of receiving the branch metric as input, calculating a path metric according to a trellis diagram, and outputting a path selection signal for selecting a path with a high likelihood, and storing the path selection signal in a traceback memory Causing the path selection signal stored in the trace-back memory to start at a starting node number. Using the number of the first node through which the maximum likelihood path obtained by the traceback passes to transition to the first node according to the trellis diagram. Generating the coded bits and the subset number, and selecting an uncoded bit related to the transition to the first node based on the subset number and the delayed subset selection signal. , And generates the decoded signal by combining the coded bits and the non-coded bits.

[0032]

Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram showing a configuration of a Viterbi decoding device according to one embodiment of the present invention. The Viterbi decoding device shown in FIG. 1 is for decoding a trellis-coded modulated signal. Here, to simplify the explanation,
A signal subjected to trellis coded modulation by the trellis coder shown in FIG. 11 is targeted. That is, the number of uncoded bits k (= 1), the coding rate m / n (= 3/4)
Is assumed. Also, I-channel data Ich and Q-channel data Q
The ch is obtained by quantizing the amplitude value of each of two orthogonally demodulated demodulated signals.

In FIG. 1, reference numeral 100 denotes a subset selection circuit, which includes a branch metric generation circuit 101 and a subset determination circuit 102. Subset selection circuit 1
00 receives the I channel data Ich and the Q channel data Qch, and selects a reception symbol point and a transmission symbol having the highest likelihood for each of 2 ^(nk) (= 2 ^(4-1) = 8) subsets. Then, branch metrics BM0 to BM7 corresponding to the selected transmission symbol and subset selection signals SSEL0 to SSE for specifying the selected transmission symbol.
L7 is output.

Reference numeral 103 denotes a delay unit for delaying the subset selection signals SSEL0 to SSEL7 output from the subset selection circuit 100 by a predetermined time, and 104 denotes a branch metric BM0 to BM7 output from the subset selection circuit 100.
An input / output (ACS) circuit for calculating path metrics PM0 to PM7 according to the trellis diagram shown in FIG. 12 and outputting path selection signals PS0 to PS7 for selecting a path having a high likelihood. Reference numeral 106 denotes an output of the ACS circuit 104. This is a trace-back memory that stores the path selection signals PS0 to PS7. The traceback memory 106 is, for example, a normal RAM
Composed of

Reference numeral 107 denotes a traceback circuit for tracing back the path selection signals PS0 'to PS7' stored in the traceback memory 106 by a predetermined traceback length starting from the start node number. Using the number ND1 of the first node through which the maximum likelihood path passes, according to the trellis diagram shown in FIG. 12, the coded bits CB {x1, x2} and the subsets related to the transition to the first node Number S
This is a subset number generation circuit that generates an SNO. Further, the selection circuit 109 includes a subset number generation circuit 108
The subset number SSNO output from the
03, the subset selection signal SSEL0 delayed by
To SSEL7, outputs an uncoded bit NCB {x3} relating to the transition to the first node.

The maximum likelihood path determination circuit 105 determines whether
The path metrics PM0 calculated by the circuit 104
With the input of PM7, the path metrics PM0 to PM7
, The path having the highest likelihood is detected, and the node number MND through which the path passes is output. Traceback circuit 10
7 obtains a start node number for traceback based on the node number MND output from the maximum likelihood path determination circuit 105.

The operation of the Viterbi decoder configured as described above will be described.

First, in the subset selecting circuit 100, the branch metric generating circuit 101 is, as in the prior art,
From the received signal, branch metrics BMs0 and BMs1 of each branch
(S is a subset number and is an integer from 0 to 7). Here, the Euclidean distance between the received signal and each transmission symbol is used as a branch metric. Then, the subset determination circuit 102 compares the branch metrics BMs0 and BMs1 of each subset, and selects the one with a higher likelihood. Then, the selected branch metrics BM0 to BM7 are output to the ACS circuit 104, and the subset selection signals SSEL0 to SSEL7 corresponding to the selected branch metrics are output to the respective delay units 103.

Here, the subset selection circuit 100
Shall generate the subset selection signals SSEL0 to SSEL7 so as to match the non-coded bits corresponding to the selected transmission symbol. This allows the subset selection signals SSEL0 to SSEL7 to be used as uncoded bits without any processing, thereby simplifying the configuration of the selection circuit 109. Here, for each subset s, the branch metric for the uncoded bit “0” is BMs0, and the branch metric for the uncoded bit “1” is BMs1, so that the subset selection signal S
As the SELs, “0” is given when the branch metric BMs0 is selected, and “1” is given when the branch metric BMs1 is selected.

The subset selection signal SSELs output from the subset determination circuit 102 is output to the selection circuit 109 after being delayed for a predetermined time by the delay unit 103. The delay time in the delay unit 103 is determined by the ACS circuit 10
4 is given the branch metrics BM0 to BM7, and then the subset number
This corresponds to the time required for processing until NO is generated.

The ACS circuit 104 selects a path that reaches each node using the branch metric BMs output from the subset determination circuit 102, and outputs a path selection signal PS.
0 to PS7 and path metrics PM0 to PM7 are updated. Although the internal configuration of the ACS circuit 104 is almost the same as that of the conventional example, in this embodiment, [(PMa, BMa), (PMb, BM) is input to the basic unit as shown in FIG.
b), (PMc, BMc), (PMd, BMd)] are input in a different order from the conventional example. Specifically, they are set as follows. <State 0> [(PM0, BM0), (PM4, BM2), (PM2, BM4), (PM6, BM6)] <State 1> [(PM2, BM0), (PM6, BM2), (PM0, BM4) ), (PM4, BM6)] <State 2> ｛(PM4, BM0), (PM0, BM2), (PM6, BM4), (PM2, BM6)] <State 3> [(PM6, BM0), (PM2) , BM2), (PM4, BM4), (PM0, BM6)] <State 4> [(PM1, BM1), (PM5, BM3), (PM3, BM5), (PM7, BM7)] <State 5> [State 5] [ (PM3, BM1), (PM7, BM3), (PM1, BM5), (PM5, BM7)] <State 6> [(PM5, BM1), (PM1, BM3), (PM7, BM5), (PM3, BM7)] <State 7> [(PM7, BM1), (PM3, BM3), (PM5, BM5), (PM1, BM7)]

That is, in the present embodiment, each path selection signal is a coded bit {x} related to the transition of the selected path, that is, the transition to the node corresponding to the path selection signal.
ACS operation is performed so as to match 2, x1}.

For example, in the case of the state 0, the input order to the basic unit is set to ｛(PM0, BM0), (PM4, BM
2), (PM2, BM4), (PM6, BM6)}. At this time, the basic unit is (PMc, BMc) (= (P
M2, BM4)), the path selection signal P
S0 is "10". This is, as is clear from the trellis diagram shown in FIG. 12, the node number 2 ({010}).
Is equal to the coded bit {x2, x1} = {1, 0} relating to the transition from to the node number 0 ({000}). Alternatively, in the case of the state 4, the input order to the basic unit is set to ｛(PM1, BM1), (PM5, BM3), (PM3, BM) as described above.
5), (PM7, BM7)}. At this time, if the basic unit selects (PMb, BMb) (= (PM5, BM3)), the path selection signal PS4 becomes “01”. This is because the coded bits {x} related to the transition from node number 5 ({101}) to node number 4 ({100})
2, x1} = {0,1}.

The path selection signals PS0 to PS7 output from the ACS circuit 104 are stored in the trace back memory 106.

FIG. 2 is a diagram showing an example of the configuration of the traceback circuit 107 and the subset number generation circuit 108. In the configuration example of FIG. 2, the subset number generation circuit 108
Is the number ND1 of the first node through which the maximum likelihood path passes, output from the traceback circuit 107, and the number ND2 of the second node through which the maximum likelihood path passes one time earlier than this first node. , Coded bits CB ｛x1, x
2} and the subset number SSNO are generated. For this purpose, the subset number generation circuit 108 has a ROM 206, which stores first and second node numbers ND1 and ND2 and coded bits CB as shown in FIG.
It has table data representing the relationship between {x1, x2} and the subset number SSNO. The table data shown in FIG. 3 can be easily generated from the trellis diagram shown in FIG.

FIG. 4 is a flowchart showing the operation of the traceback circuit 107 and the subset number generation circuit 108. First, the node number MND of the maximum likelihood path output from the maximum likelihood path determination circuit 105 is input to the start node number generation circuit 201. Start node number generation circuit 201
Determines the first node number at which traceback is started, that is, the start node number, based on the node number MND, and inputs it to the second selection circuit 202 (S2). At the start of traceback, the second selection circuit 202 selects the output of the start node number generation circuit 201, and selects the output of the first selection circuit 203.
And to the node number calculation circuit 204.

The first selection circuit 203 outputs the path selection signals PS0 'to PS output from the trace back memory 106.
7 ', a path selection signal corresponding to the node number output from the second selection circuit 202 is selected and output to the node number calculation circuit 204 (S3). The node number operation circuit 204 is based on the current node number output from the second selection circuit 202 and the corresponding path selection signal output from the first selection circuit 203, based on the node number one time past. Is calculated (S4).

More specifically, since the path selection signal is generated so as to match the input coded bits {x2, x1} relating to the transition, in the case of the encoder shown in FIG. Is {D2, D1, D0}, the node numbers {D2 ′, D1 ′, D0 ′} at one time point in the past are D2 ′ = D1 ＾ x1, D1 ′ = D0２x2, D0 ′ = D2 (1) Becomes Here, ＾ indicates exclusive OR. The node numbers {D2 ′, D1 ′, D0 ′} one past time point are newly stored in the node number storage circuit 205 (S6).

The same processing is repeated until the number of times of tracing reaches a predetermined trace back length L (S1, S
5, S7). However, the second selection circuit 202 selects the output of the node number storage circuit 205 in which the current node number is stored except when the traceback is started.

As a result, from the traceback circuit 107, the number ND1 of the first node in the past L time points of the maximum likelihood path obtained as a result of the traceback and the maximum likelihood path passing one time point earlier than this The number N of the second node
D2 is output. Subset number generation circuit 108
Is obtained from the node numbers ND1 and ND2 with reference to the table data shown in FIG.
Generate coded bits CB {x1, x2} and subset number SSNO.

The subset number SSNO generated by the subset number generation circuit 108 is input to the selection circuit 109. The selection circuit 109 extracts the subset selection signal SSE corresponding to the subset number SSNO from the subset selection signal SSELs delayed by each delay unit 103.
Ls is selected and output. In the present embodiment, since the subset selection signal SSELs is generated so as to match the non-coded bit, the non-coded bit NCB {x3} is output from the selection circuit 109. Encoded bit CB output from subset number generation circuit 108
{X1, x2} and the non-encoded bit NCB {x3} output from the selection circuit 109 are combined with the decoded signal {x
1, x2, x3} are generated.

As described above, according to the present embodiment, in a Viterbi decoding device for decoding a signal subjected to trellis-coded modulation, the traceback memory can be constituted by a normal RAM, and the circuit scale can be reduced. In addition, power consumption can be reduced.

In the present embodiment, even when the number of states of the encoder increases, R
By increasing the number of bits of the AM, it is possible to easily implement a circuit, and it is possible to significantly reduce the circuit area as compared with the related art.

In this embodiment, the path selection signal is stored in the trace-back memory and depends only on the coded bits. Therefore, even if the number of subsets increases, the trace-back memory does not need to be increased. . Therefore, in the present embodiment, an increase in the circuit scale caused by the conventional configuration in which the subset number is stored for each node can be avoided.

FIG. 5 is a diagram showing another configuration example of the trace-back circuit and the subset number generation circuit. In FIG. 5, the trace-back circuit 107A has the same basic configuration as the trace-back circuit 107 shown in FIG. 2, but after the trace-back is completed, the maximum likelihood path obtained as a result of the trace-back at the time point L In that the path selection signal PSS corresponding to the first node is output together with the number ND1 of the first node. The subset number generating circuit 108A includes an arithmetic unit 300 instead of the ROM, and the arithmetic unit 300 converts the encoded bit CB from the node number ND1 and the path selection signal PSS based on the generator polynomial of the encoder. And an operation for generating the subset number SSNO.

FIG. 6 is a diagram showing the configuration of the arithmetic unit 300. Since path selection signal PSS {S2, S1} matches input encoded bit {x2, x1}, encoded bit CB
{X2, x1} is the path selection signal PSS {S2, S
1｝ is output as it is. Also, the subset number SSN
O is the node number {D2 ', D1', D
0 ′}, it can be expressed as {x2, x1, D0 ′}. Therefore, the subset number SSNO {y
2, y1, y0}, {S2, S1, D2 (= D
0 ')｝ is output as it is. That is, the subset number SSNO is the same as the path selection signal PSS and the node number ND1.
Can be obtained by a simple operation of rearranging.
Therefore, as shown in FIG. 6, the subset number generation circuit 108 can be realized by an arithmetic unit having an extremely simple configuration, and the circuit scale and speed can be reduced.

Note that, similarly to the configuration of FIG.
, The node number ND1 and the path selection signal PS
A ROM storing table data representing the relationship between S, the encoded bit CB, and the subset number SSNO may be provided in the subset number generation circuit 108A. In this case, although the circuit scale increases as compared with the arithmetic unit, the configuration of the decoder can be flexibly changed for different encoders by exchanging the ROM.

FIG. 7 is a diagram showing another example of the trellis encoder, and FIG. 8 is a trellis diagram relating to the trellis encoder of FIG. In the trellis encoder shown in FIG. 7, the number of uncoded bits k (= 1), the coding rate m / n (= 3
/ 5), and the number of subsets is 16 (= 2 ^(nk) =
2 ^(5-1) ). Even when a signal subjected to trellis coded modulation by the trellis coder shown in FIG. 7 is targeted, the traceback circuit and the subset number generation circuit may be configured as shown in FIG. 2 or FIG.
However, table data stored in the ROM 206,
The internal configuration of the arithmetic unit 300 needs to be changed according to the configuration of the trellis encoder.

FIG. 9 is a diagram showing an example of table data stored in the ROM 206 in the configuration of FIG. 2 on the premise of the trellis encoder shown in FIG. The table data includes the number ND1 of the first node through which the maximum likelihood path passes, output from the traceback circuit 107, and the number of the second node through which the maximum likelihood path has passed one time in the past of the first node. Number ND2 and coded bits CB @ x
1, x2} and the subset number SSNO (4 bits are represented by decimal numbers). The table data shown in FIG. 9 can be easily generated from the trellis diagram shown in FIG.

FIG. 10 shows the arithmetic unit 30 in the configuration of FIG. 5 on the premise of the trellis encoder shown in FIG.
FIG. 3 is a diagram showing an example of the internal configuration of a 0. This arithmetic unit 300
Is the number ND1 of the first node output from the traceback circuit 107 and through which the maximum likelihood path passes, and the first node number ND1.
Performs an operation of generating encoded bit CB and subset number SSNO (4 bits) from path selection signal PSS corresponding to the node of. That is, even in this case, the subset number SSNO can be obtained by a simple operation of rearranging the path selection signal PSS and the node number ND1.

Further, instead of the current node number, the same encoding operation as that of the encoder is performed by using the node number in the past one time, which is the output of the node number operation circuit, and the input encoded bit corresponding thereto. , The subset number may be obtained directly. Also, the encoding operation is represented by R
By using the table data stored in the OM, the configuration of the decoder for different encoders can be easily realized, as described above.

When the symbol input is relatively slow,
The traceback processing can be completed for each symbol. In this case, the start node number generation circuit 201
It is desirable to output the node number MND of the path with the highest likelihood currently output from the maximum likelihood path determination circuit 105 as it is. Also, when symbol input speeds up, pipelined traceback is effective. In this case, as the start node number generation circuit 201, for example, JP-A-9-191258 (U.S. Pat. No. 6,041,433)
No.) By employing the configuration described in the gazette, it is possible to greatly reduce the number of trace-back memories.

In the present embodiment, an example in which the device is configured as hardware is shown, but the Viterbi decoding device of the present invention may be configured as software using a program. That is, instead of using the Viterbi decoding device, a software algorithm for implementing the Viterbi decoding method according to the present invention may be used.

[0065]

According to the Viterbi decoding of the present invention, the path memory can be constituted by a trace-back memory using a normal RAM, so that the circuit area can be reduced.
The power consumption of the device can be reduced. Further, it is possible to easily cope with a communication system using different encoders. Further, even when the number of subsets generated from code bits increases, the circuit scale does not increase.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a configuration of a Viterbi decoding device according to an embodiment of the present invention.

FIG. 2 is a diagram illustrating a configuration example of a trace-back circuit and a subset number generation circuit in the configuration of FIG. 1;

FIG. 3 is a diagram showing an example of table data stored in the subset number generation circuit of FIG. 2, which is based on the trellis encoder of FIG. 11;

FIG. 4 is a flowchart illustrating operations of a trace-back circuit and a subset number generation circuit.

FIG. 5 is a diagram showing another example of the configuration of the trace-back circuit and the subset number generation circuit in the configuration of FIG. 1;

FIG. 6 is a configuration example of a computing unit in FIG.
FIG. 2 is a diagram showing an example based on the trellis encoder of FIG.

FIG. 7 is an example of a trellis encoder.

FIG. 8 is a trellis diagram according to the trellis encoder of FIG. 7;

9 is a diagram showing another example of the table data stored in the subset number generation circuit of FIG. 2, which is based on the trellis encoder of FIG. 7;

10 is a diagram showing another example of the configuration of the arithmetic circuit in FIG. 5, which is based on the trellis encoder shown in FIG. 7;

FIG. 11 is an example of a trellis encoder.

FIG. 12 is a trellis diagram according to the trellis encoder of FIG. 11;

FIG. 13 is a block diagram illustrating a configuration of a conventional Viterbi decoding device.

FIG. 14 is a diagram showing basic units constituting the ACS circuit.

FIG. 15 is a diagram showing a configuration of a conventional path memory circuit.

[Explanation of symbols]

REFERENCE SIGNS LIST 100 subset selection circuit (subset selection unit) 103 delay unit 104 ACS circuit (ACS unit) 105 maximum likelihood path determination circuit (maximum likelihood path determination unit) 106 traceback memory 107, 107A traceback circuit (traceback unit) 108, 108A Subset number generation circuit (subset number generation unit) 109 selection circuit (selection unit) 206 ROM 300 arithmetic unit Ich, Qch reception signal BM0-BM7 branch metric SSEL0-SSEL7 subset selection signal PM0-PM7 path metric PS0-PS7, PS0'- PS7 'path selection signal ND1 number of first node ND2 number of second node PSS path selection signal corresponding to first node SSNO subset number CB coded bit NCB uncoded bit

──────────────────────────────────────────────────続 き Continued on the front page (58) Field surveyed (Int.Cl. ⁷ , DB name) H03M 13/00 H04L 1/00 G06F 11/10 330

Claims (10)

(57) [Claims] 1. A Viterbi decoding device for decoding a trellis-coded modulated signal, receiving a received signal as input, selecting a received symbol point and a transmission symbol having the highest likelihood for each subset, A subset selector that outputs a branch metric corresponding to the selected transmission symbol and a subset selection signal for specifying the selected transmission symbol; a delay unit that delays the subset selection signal by a predetermined time; An ACS (Add Compare Select) unit for calculating a path metric according to a trellis diagram as an input and outputting a path selection signal for selecting a path with a high likelihood; a traceback memory for storing the path selection signal; The path selection signal stored in the back memory is traced for a predetermined traceback length starting from the start node number. Using a traceback unit to perform a back-up, and using a number of a first node through which a maximum likelihood path obtained by the traceback unit passes, according to a trellis diagram, encoded bits related to transition to the first node, A subset number generation unit that outputs a subset number; a selection unit that receives the subset number and the subset selection signal output from the delay unit and outputs an uncoded bit related to a transition to the first node A Viterbi decoding device, comprising: generating a decoded signal by combining coded bits output from the subset number generation unit and non-coded bits output from the selection unit. 2. The Viterbi decoding device according to claim 1, wherein a path metric calculated by said ACS unit is input, a path with the highest likelihood is detected from the path metric, and a node number passing through the path is determined. A Viterbi decoding device, comprising: a maximum likelihood path determination unit for outputting; and the traceback unit obtains the start node number based on a node number output from the maximum likelihood path determination unit. . 3. The Viterbi decoding device according to claim 1, wherein the subset number generation unit is configured to determine a number of the first node and a second number of a maximum likelihood path of the first node that has passed one time in the past. A Viterbi decoding device for generating the coded bits and the subset number using a node number. 4. The Viterbi decoding device according to claim 3, wherein said subset number generation unit has table data indicating a relationship between said first and second node numbers, said coded bits and said subset number. A Viterbi decoding device, characterized in that: 5. The Viterbi decoding device according to claim 1, wherein the subset number generation unit performs the encoding using a number of the first node and a path selection signal corresponding to the first node. A Viterbi decoding device for generating a bit and a subset number. 6. The Viterbi decoding device according to claim 5, wherein said subset number generation unit has table data indicating a relationship between said first node number and path selection signal, and said coded bits and subset number. A Viterbi decoding device, characterized in that: 7. The Viterbi decoding device according to claim 3, wherein the subset number generation unit is configured by an arithmetic unit that performs an operation based on a generator polynomial of an encoder. Decoding device. 8. The Viterbi decoding device according to claim 1, wherein the subset selection unit generates the subset selection signal so as to match an uncoded bit corresponding to the selected transmission symbol. A Viterbi decoding device characterized in that: 9. The Viterbi decoding device according to claim 1, wherein the ACS unit generates the path selection signal such that the path selection signal matches an encoded bit relating to a transition to a node corresponding to the path selection signal. A Viterbi decoding device characterized in that: 10. A Viterbi decoding method for decoding a trellis-coded modulated signal, comprising: selecting a received symbol point and a transmission symbol having the highest likelihood for each subset based on a received signal; Generating a branch metric corresponding to the selected transmission symbol and a subset selection signal for identifying the selected transmission symbol; delaying the subset selection signal by a predetermined time; and inputting the branch metric as input. An ACS (Add Compare Select) step of calculating a path metric according to a trellis diagram and outputting a path selection signal for selecting a path with a high likelihood; a step of storing the path selection signal in a traceback memory; The path selection signal stored in the back memory is stored in a predetermined trace buffer starting from the start node number. Using the number of the first node through which the maximum likelihood path obtained by the traceback passes, according to a trellis diagram, and coding bits relating to the transition to the first node, Generating a subset number; and selecting an uncoded bit related to transition to the first node based on the subset number and the delayed subset selection signal. A Viterbi decoding method, comprising: generating a decoded signal by combining bits and the uncoded bits.