JPH10200421A - Adding/comparing/selecting processor for viterbi decoder - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide an adding/comparing/selecting processor for a Viterbi decoder which improves the area efficiency of hardware at the time of setting an ASIC(application specific integrated circuit). SOLUTION: A grouping part 410 mutually compares two path meters with two branch meters, a processing element 430 which outputs two deciding bits and two state meters which correspond to a comparison result is grouped into processing elements which use the same state meter and branch meter, a multiplexing part 420 multiplexes a path meter that is supplied in accordance with a grouped result into two path meters in accordance with a clock signal and outputs them to the element 430, a 1st demultiplexing part 440 demultiplexes two decision bits that are outputted from the element 420, and also a 2nd demultiplexing part 450 demultiplexes two state meters that are outputted from the element 430.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an adder / comparator / selector processor in a Viterbi decoder. More particularly, the present invention relates to an N-state processing element for N states.
tate metric) and the same branch meter
ic) is grouped into predetermined units of processing elements, and an addition / combination embodied to perform addition / comparison / selection processing for a plurality of states with one processing element.
It relates to a comparison / selection processor.

[0002]

2. Description of the Related Art Generally, maximum likelihood decoding (maximum l
As a highly practical and efficient method for ikelihood decoding, the Viterbi decoding algorithm is most widely used. The Viterbi decoding algorithm uses a trellis diagram, but compares the path lengths of two different paths encountered in an arbitrary state, selects a short path, that is, a path with a low error probability, and selects a surviving path. (Survivor path). A Viterbi decoder using such a Viterbi decoding algorithm has a very excellent random error correction capability, and is therefore used, for example, for error correction in a satellite communication system.

The above-mentioned Viterbi decoding algorithm is shown in FIG.
This will be described in more detail based on FIG. 1 (a) shows a trellis diagram in which the number of nodes, that is, the number of states is 2, where the vertical direction is the state (S _i , where i is 1, 2), and the horizontal direction is the time (t / t). T: where 1 / T indicates the transmission rate), and S _{i, k} indicates the i-th state at time k. The finite state machine selects an arbitrary path through the trellis diagram shown in FIG. 1 (a), and selects a branch meter for a time interval (k, k + 1) according to the observed state transition.
Calculate (λ). That is, according to the trellis diagram, the situation (S _{1, k} , S _{2, k} ) at time _k is determined by the respective branches for the time interval (k, k + 1) at the time (k + 1).
_{1, k + 1} , S2 _{, k + 1} ). At the time of Viterbi decoding, a distance between codes in a branch corresponding to a received signal, that is, a branch meter is calculated, and the branch meter becomes a hamming distance in the case of hard decision decoding, and is soft. Decision decoding (sof
t decision decoding) for the Euclidean distance (eucli
dean distance).

Using the branch meter calculated in this way, a new path metric for each node at time (k + 1) is calculated by comparing the path metric (γ) at time k with the time interval (k, k). This is calculated by the branch meter (λ) for +1), which will be described with reference to FIG.

In FIG. 1B, a node S at time k
_{1, k} , S2 _{, k} have path meters γ1 _{, k} , γ2 _{, k} , respectively _, which are accumulated values of branch meters, and have time intervals (k, k +
Let the branch meter for 1) be λ _{11, k} , λ _{12, k} , λ _{21, k} ,
Let λ _{22, k} be the new path meter γ _{1, k + 1} , γ _{2, k + 1} for nodes S _{1, k + 1} , S _{2, k + 1} at time (k + 1)
Is determined by the following equation 1.

[Equation 1] γ _{1, k + 1} = max [λ _{11, k} + γ _{1, k} , λ _{12, k} + γ _{2, k} ] γ _{2, k + 1} = max [λ _{21, k} + γ _{1, k} , λ _{22, k} + γ _{2, k} ] That is, since there are a plurality of types of routes coming to the node at the time (k + 1) according to the change of the state existing at the time k, the branch of the probability information Find the path meter using the meter. The process of calculating the path meter is cyclically performed for each time k to search for a final survival path.

On the other hand, when the trace of the survival route is
As shown in FIG. 1 (b), the routes merge at a very high probability at any time, and the number of time steps at which the routes merge at a very high probability is called a survival depth. Affects the waiting time for Viterbi decoding. In other words, when the path meter (γ) is updated for each node by the above equation 1, the state of each path corresponding to the survival depth becomes the same. Therefore, the previous state change of the survival depth obtained by such traceback is output as Viterbi decoded data.

FIG. 2 is a block diagram showing a general Viterbi decoder.
It comprises a comparison / selection processing section 200 and a live memory section 300.

In FIG. 2, a branch meter generation unit 10
Numeral 0 inputs the received convolutionally encoded data, calculates and outputs the branch meter (λ _{ij, k} ) which is the distance between codes in each branch corresponding to the received signal. At this time, the complexity of the branch meter generation unit 100 is directly related to the length of the received codeword, and the circuit becomes more complicated as the number of bits constituting the codeword increases. For example, if the codeword consists of 2 bits, then 2 ^2, or 4, comparison codewords are needed to compare the 2 bits of the received codeword. On the other hand, the code word is composed of 3 bits, 2 ³ in order to calculate a branch metric by comparing a received codeword, i.e. it is necessary to eight comparison code word. In addition, when the code word is longer, the calculated branch metric value is larger than when the code word is shorter. Eventually, the storage capacity of the memory for storing the branch meter is increased by an amount corresponding to the increase in the number of comparison codewords and the branch meter value, and the addition / comparison / selection processing unit 200 in the next stage becomes complicated. Become.

The addition / comparison / selection processing unit 200 inputs a branch meter from the branch meter generation unit 100 and adds it to the immediately preceding route meter to set a plurality of candidate routes. Next, after comparing a plurality of candidate routes and selecting a route having the shortest route meter, a determination bit as a comparison result with the selected new route meter is output. The addition / comparison / selection processing unit 200 updates the path meter using the branch meter provided from the branch meter generation unit 100 for each decoding cycle, and then transmits the N determination bits to the surviving memory unit 300 at the next stage. Output. Assuming a trellis diagram composed of a total of N states, N bits are obtained for each decoding cycle.

The survival memory unit 300 stores the decision bits provided from the addition / comparison / selection processing unit 200, and restores the original information sequence using the stored decision bits to obtain Viterbi-decoded data. Output.

FIG. 3 is a block diagram showing a processing element 310 constituting the addition / comparison / selection processing section 200 shown in FIG. 2. The processing element 310 includes a first processing section 320 and a second processing section 340. Consists of Here, the first processing unit 320
Are the first adder 322, the second adder 324, and the first comparator 326
And a first selector 328. The second processing unit 340 includes a third adder 342, a fourth adder 344, a second comparator 346,
And a second selector 348.

In FIG. 3, γ _X and γ _Y are path meters input to the processing element 310, and here, 6
An example composed of bits will be described. Of these, γ
_X is input to the first adder 322 of the first processing unit 320 and the third adder 342 of the second processing unit 340, and γ _Y is the second addition value of the first processing unit 320.
It is input to the adder 324 and the fourth adder 344 of the second processing unit 340. In addition, λ _X and λ _Y are branch meters provided from the branch meter generation unit 100 (see FIG. 2), and here, an example composed of 4 bits will be described. Among them, λ _X is the first adder 322 of the first processing unit 320 and the second processing unit
340 is input to a fourth adder 344, and λ _Y is input to a first processing unit 320.
Are input to the second adder 324 and the third adder 342 of the second processing unit 340. On the other hand, the first comparator 326 of the first processing unit 320 and the second comparator 326
The first determination bit and the second determination bit output from the second comparator 346 of the processing unit 340 are supplied to the surviving memory unit 300 (see FIG. 2) in the next stage.

Next, the operation for one processing element 310 constituting the addition / comparison / selection processing section 200 will be described with reference to FIG.

First, the first processing unit 320 will be described. A first adder 322 adds a path meter γ _X and a branch meter λ _X, and adds the added value to a first comparator 326 and a first selection unit, respectively. output to vessel 328, by adding the second adder 324 in the path metric gamma _Y and branch metric lambda _Y, and outputs the addition value first comparator 326 respectively to the first selector 328.

The first comparator 326 compares the added value from the first adder 322 with the added value from the second adder 324, and compares the first determination bit of the comparison result with the live memory unit 300 (FIG. 2
), While supplying it as a selection signal of the first selector 328. For example, as a comparison result in the first comparator 326, when the added value from the first adder 322 is larger than the added value from the second adder 324, the first determination bit is “0”.
In the opposite case, "1" is output.

The first selector 328 selectively outputs the added value from the first adder 322 or the added value from the second adder 324 according to the selection signal. That is, the first selector 328 selects the added value from the second adder 324 when the first determination bit is “0” and outputs it as a state meter, and when the first determination bit is “1”, The added value from the first adder 322 is selected and output as a state meter.

On the other hand, the second processing section 340 will be described. In the third adder 342, the path meter γ _X and the branch meter λ _Y are added, and the added value is added to the second comparator 346 and the second selector 348, respectively. output, the fourth adder 344 in adds a path metric gamma _Y and branch metric lambda _X, and outputs the added value as that it second comparator 346 to the second selector 348.

The second comparator 346 compares the added value from the third adder 342 with the added value from the fourth adder 344, and compares the second determination bit of the comparison result with the live memory unit 300 (FIG. 2
), And is supplied as a selection signal of the second selector 348. For example, the comparison result in the second comparator 346,
When the added value from the third adder 342 is larger than the added value from the fourth adder 344, the second determination bit is output as "0", and when the opposite is true, it is output as "1".

The second selector 348 selectively outputs the added value of the third adder 342 or the added value of the fourth adder 344 according to the selection signal. That is, the second selector 348 selects the added value from the fourth adder 344 when the second determination bit is “0” and outputs it as a state meter, and when the second determination bit is “1”, The added value from the third adder 342 is selected and output as a state meter.

As shown in FIG. 3, two processing elements that use the same state metric can be grouped and bundled into one processing element. That is,
Since addition / comparison / selection processing for two states is performed by one processing element, in the case of 64 state modes, an addition / comparison / selection processor is implemented by 32 processing elements (PE0 to PE31). can do.

Although the add / compare / select processor as described above is embodied to process one state with one processing element, there is a need for further improvement. In other words, recently, as the technology for manufacturing an application specific integrated circuit (ASIC) or a dedicated integrated circuit has rapidly developed, a hardware that can process at least two or more states with one processing element has been realized. There is an increasing need to further improve the area efficiency.

[0023]

SUMMARY OF THE INVENTION The present invention has been devised to solve the above problems, and an object of the present invention is to add / compare / select a plurality of states with one processing element. An object of the present invention is to provide an addition / comparison / selection processor that can be implemented to perform processing and thereby improve the area efficiency at the time of ASIC design.

[0024]

According to a first aspect of the present invention, there is provided a Viterbi decoder for performing maximum likelihood decoding on a superimposed code.
Two path meters and two branch meters are input, the added values are compared with each other, and two processing bits for outputting two decision bits and two state meters according to the comparison result, and N processing elements are provided. A grouping unit for grouping the N processing elements for a state into processing units in K units using the same state meter and the same branch meter, and L supplied according to the grouping result (here, L Is a multiplexing unit for multiplexing 2K) path meters into two path meters according to a predetermined clock signal and outputting the multiplexed path meters to corresponding processing elements, and two determination bits output from the corresponding processing elements. , And demultiplexes the L decision bits according to the clock signal and outputs the result. And a second demultiplexer that receives the two state meters output from the corresponding processing elements, demultiplexes the state meters into L state meters according to the clock signal, and outputs the demultiplexed state meters. Features.

[0025]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, an embodiment of the present invention will be described in more detail with reference to the accompanying drawings.

FIG. 4 is a block diagram showing an addition / comparison / selection processor according to an embodiment of the present invention in a Viterbi decoder. The addition / comparison / selection processor comprises a plurality of processing elements. However, only one processing element will be described for convenience of explanation.

The addition / comparison / selection processor shown in FIG. 4 includes a grouping section 410, a multiplexing section (multiplexer) 420, a processing element 430, and a first demultiplexing section (first demultiplexer). ) 440, a second demultiplexer (second demultiplexer) 450, and a controller 460. Here, the input / output signals of each component will be described. PA0, PA1, PB0, PB1 are
20 is a 6-bit path meter input to 20 and γ
_X and γ _Y are path metrics in 6-bit units output from the multiplexing unit 420, and λ _X and λ _Y are processing elements 430
Is a 4-meter branch meter input to
DA0, DA1, DB0, and DB1 are determination bits output from the first demultiplexer 440, and are SA0, SA1, SB0,
SB1 is a 6-bit state meter output from the second demultiplexer 450.

Referring to FIG. 4, a grouping unit 410 groups N processing elements for N states into processing elements of a predetermined unit using the same state meter and the same branch meter. In the case of 64 state modes, a case where the number of states that can be processed by one processing element, that is, the number of grouping units is four will be exemplified.

The multiplexing section 420 has four path meters (P
A0, PA1, PB0, PB1) are input to the multiplexing unit 420.
Is a two-meter meter according to the clock signal (CLK)
(γ _X , γ _Y = PA0, PA1 or PB0, PB1) is selected and output to the processing element 430.

The processing element 430 is the same as the general processing element 310 shown in FIG. 3, and includes two path meters (γ _X , γ _Y) supplied from the multiplexer 420.
) And two branch meters (λ _X , λ _Y ) supplied from the branch meter generation unit 100 (see FIG. 1), and two decision bits (first decision bit, second decision bit) and two states Output meters. A more detailed description has been given above for the prior art and will not be repeated here.

The first demultiplexer 440 receives the two decision bits (first decision bit and second decision bit) output from the processing element 430, and inputs the first demultiplexer 440.
Are four decision bits (DA0, D
A1, DB0, DB1).

The second demultiplexer 450 receives the two state meters output from the processing element 430,
The second demultiplexer 450 demultiplexes the four state meters (SA0, SA1, SB0, SB1) according to the clock signal and outputs the demultiplexed state meters.

Next, the operation and effect of the above-described addition / comparison / selection processor of the present invention will be described in more detail with reference to FIGS.

First, in the case of the 64 state modes, a program for converting an addition / comparison / selection processor composed of processing elements having the structure shown in FIG. 3 into an ASIC is as follows. The programming language used here is VHDL (V
ery High Definition Language).

Component T_ACS52 port (bmet_x, bmet_y: in, std_logic_vector (Bit_Branch-1 downto 0): pmet_x, pmet_y: in, std_logic_vector (Bit_State-1 downto 0): over_flag: out, std_logic:… overflow indicator a, b decision_a , decision_b: out, std_logic:… decision bit smet_a, smet_b: out, std_logic_vector (Bit_State-1 downto 0)); end component; begin PE_ASSIGN: process (bmet0, bmet1, bmet2, bmet3, pmet)… begin PE0: T_ACS52 port Map (bmet0, bmet3, pmet (0), pmet (1), over_flag (0), decision_a (0), decision_b (0), smet (0), smet (32)); PE1: T_ACS52 port Map (bmet1, bmet2, pmet (2), pmet (3), over_flag (1), decision_a (1), decision_b (1), smet (1), smet (33); PE2: T_ACS52 port Map (bmet0, bmet3, pmet (4 ), pmet (5), over_flag (2), decision_a (2), decision_b (2), smet (2), smet (34)); PE3: T_ACS52 port Map (bmet1, bmet2, pmet (6), pmet ( 7), over_flag (3), decision_a (3), decision_b (3), smet (3), smet (35)); PE4: T_ACS52 port Map (bmet3, bmet0, pmet (8), pmet (9), over_flag (4), decision_a (4), decision_b (4), smet (4), smet (36)); PE5: T_ACS52 port Map (bmet2, bmet1, pmet (10), pmet (11), over_flag (5), decision_a (5), decision_b (5), smet (5), smet (37)); PE6: T_ACS52 port Map (bmet3, bmet0, pmet ( 12), pmet (13), over_flag (6), decision_a (6), decision_b (6), smet (6), smet (38)); PE7: T_ACS52 port Map (bmet2, bmet1, pmet (14), pmet (15), over_flag (7), decision_a (7), decision_b (7), smet (7), smet (39)); PE8: T_ACS52 port Map (bmet3, bmet0, pmet (16), pmet (17), over_flag (8), decision_a (8), decision_b (8), smet (8), smet (40)); PE9: T_ACS52 port Map (bmet2, bmet1, pmet (18), pmet (19), over_flag (9) , decision_a (9), decision_b (9), smet (9), smet (41)); PE10: T_ACS52 port Map (bmet3, bmet0, pmet (20), pmet (21), over_flag (10), decision_a (10 ), decision_b (10), smet (10), smet (42)); PE11: T_ACS52 port Map (bmet2, bmet1, pmet (22), pmet (23), over_flag (11), decision_a (11), decision_b ( 11), smet (11), smet (43)); PE12: T_ACS52 port Map (bmet0, bmet3, pmet (24), pmet (25), over_flag (12), decision_a (12), decision_b (12), smet (12), smet (44)); PE13: T_ACS52 port Map (bmet1, bmet2, pmet (26), pmet (27), over_flag (13), decision_a (13), decision_b (13), sme t (13), smet (45)); PE14: T_ACS52 port Map (bmet0, bmet3, pmet (28), pmet (29), over_flag (14), decision_a (14), decision_b (14), smet (14) , smet (46)); PE15: T_ACS52 port Map (bmet1, bmet2, pmet (30), pmet (31), over_flag (15), decision_a (15), decision_b (15), smet (15), smet (47) )); PE16: T_ACS52 port Map (bmet2, bmet1, pmet (32), pmet (33), over_flag (16), decision_a (16), decision_b (16), smet (16), smet (48)); PE17 ： T_ACS52 port Map (bmet3, bmet0, pmet (34), pmet (35), over_flag (17), decision_a (17), decision_b (17), smet (17), smet (49)); PE18: T_ACS52 port Map (bmet2, bmet1, pmet (36), pmet (37), over_flag (18), decision_a (18), decision_b (18), smet (18), smet (50)); PE19: T_ACS52 port Map (bmet3, bmet0 , pmet (38), pmet (39), over_flag (19), decision_a (19), decision_b (19), smet (19), smet (51)); PE20: T_ACS52 port Map (bmet1, bmet2, pmet (40) ), pmet (41), over_flag (20), decision_a (20), decision_b (20), smet (20), smet (52)); PE21: T_ACS52 port Map (bmet0, bmet3, pmet (42), pmet ( 43), over_flag (21), decision_a (21), decision_b (21), smet (21), smet (53)); PE22: T_ACS52 port Map (bmet1, b met2, pmet (44), pmet (45), over_flag (22), decision_a (22), decision_b (22), smet (22), smet (54)); PE23: T_ACS52 port Map (bmet0, bmet3, pmet ( 46), pmet (47), over_flag (23), decision_a (23), decision_b (23), smet (23), smet (55)); PE24: T_ACS52 port Map (bmet1, bmet2, pmet (48), pmet (49), over_flag (24), decision_a (24), decision_b (24), smet (24), smet (56)); PE25: T_ACS52 port Map (bmet0, bmet3, pmet (50), pmet (51), over_flag (25), decision_a (25), decision_b (25), smet (25), smet (57)); PE26: T_ACS52 port Map (bmet1, bmet2, pmet (52), pmet (53), over_flag (26) , decision_a (26), decision_b (26), smet (26), smet (58)); PE27: T_ACS52 port Map (bmet0, bmet3, pmet (54), pmet (55), over_flag (27), decision_a (27 ), decision_b (27), smet (27), smet (59)); PE28: T_ACS52 port Map (bmet2, bmet1, pmet (56), pmet (57), over_flag (28), decision_a (28), decision_b ( 28), smet (28), smet (60)); PE29: T_ACS52 port Map (bmet3, bmet0, pmet (58), pmet (59), over_flag (29), decision_a (29), decision_b (29), smet (29), smet (61)); PE30: T_ACS52 port Map (bmet2, bmet1, pmet (60), pmet (61), over_flag (30), decision_a (30), decision_b (30), smet (30), smet (62)); PE31: T_ACS52 port Map (bmet3, bmet0, pmet (62), pmet (63), over_flag (31), decision_a (31), decision_b (31), smet (31), smet (63));… end process:… End of PE_ASSIGN In the above program, T_ACS52 is the name of the processing element when designing the ASIC, and pmet and smet are the path meter and Indicates a state meter. That is, the state meter (smet) is the meter of the state which is calculated and output in the processing element of the addition / comparison / selection processor, and the state meter is used as the path meter (pmet) at the next clock. Is applied to For example, one state meter of the output value of the 0th processing element (PE0) is input as one path meter of the input value of the 0th processing element (PE0), and another state meter of the output value. Is 16
One of the input values of the processing element (PE16) is input as a path meter. In addition, one state meter of the output value of the first processing element (PE1) is input as another path meter of the input value of the zeroth processing element (PE0), and another state of the output value is another state meter. Meter is the 16th processing element
It is input as another path meter of the input value of (PE16). Similarly, the remaining processing elements (PE
2 to PE31) are also connected to each other in a complicated manner as described above.

On the other hand, in the above program, the input values of each processing element will be described.
12, PE14, PE21, PE23, PE27, PE29
Use (bmet0, bmet3) as a branch meter in common, and use PE1, PE3, PE13, PE15, PE20, PE
22, PE24, PE26 commonly use (bmet1, bmet2) as a branch meter, and PE4, PE6, PE8, P
E10, PE17, PE19, PE29, PE31 commonly use (bmet3, bmet0) as the branch meter,
5, PE7, PE9, PE11, PE16, PE18, PE2
8. The PE 30 commonly uses (bmet2, bmet1) as a branch meter. That is, states 0, 2, 12, 14, 2
1,23,27,29,32,34,44,46,53,55,5
7, 59 uses (bmet0, bmet3), and states 1, 3, 13, 15,
20, 22, 24, 26, 33, 35, 45, 47, 52, 54,
56,58 use (bmet1, bmet2), state 4,6,8,10,
17, 19, 29, 31, 36, 38, 40, 42, 49, 51,
61,63 use (bmet3, bmet0), state 5,7,9,11,
16, 18, 28, 30, 37, 39, 41, 43, 48, 50,
60 and 62 use (bmet2, bmet1).

In the addition / comparison / selection processor according to the present invention, the grouping unit 410 determines the grouping unit according to the maximum operation speed of the system and the characteristics of the ASIC cell library. For example, if an ASIC cell library having a chip size of 0.5 micron is used and the maximum operation speed is assumed to be 80 MHz or more, (bmet0, bmet
Eight processing elements using (3) into four groups, eight processing elements using (bmet1, bmet2) into four groups, eight processing elements using (bmet3, bmet0) into four groups, (bmet2 , bmet1) bundles the eight processing elements into four groups.

The multiplexing section 420 has four 6-bit path meters PA0, PA1, PB0, PB which are inputs of the two-unit processing elements grouped by the grouping section 410.
1, the path meters PA0 and PA1 or the path meters PB0 and PB1 are selected and output according to the clock signal (CLK). Here, the clock signal (CLK) is supplied from the control unit 460 and operates as a selection signal of the multiplexing unit 420. That is, when the clock (CLK) is at the “high” logic level, the path meters PA0 and PA1 are selected, and when the clock (CLK) is at the “low” logic level, the path meters PB0 and PB1 are selected and the processing elements are selected. Supplied to 430. Similarly, the opposite is true.

In the processing element 430, the path meter (γ _X , γ _Y = PA) selected and output from the multiplexing unit 420
0, PA1 or PB0, PB1) and the branch meter (λ _X , λ _Y ) from the branch meter generation unit 100 (see FIG. 2).
To output two decision bits (ie, a first decision bit and a second decision bit) and two state meters. Since the processing element 430 processes two states using the same state meter, two result values are generated respectively. That is, the first addition value is output after the path metric gamma _X and branch metric lambda _X are added, the path metric gamma _Y and branch metric lambda _Y is second added value is output after being added. On the other hand, the third added value is output after the path metric gamma _X and branch metric lambda _Y is added, the route metric gamma _Y and branch metric lambda _X is fourth added value is output after being added. The first addition value and the second addition value are compared with each other, and the third addition value and the fourth addition value are compared with each other, and then the first determination bit and the second determination bit are “0” or “1” according to the comparison result. Is output. First
The determination bit or the second determination bit is used as a signal for selecting one of the two additional values, but one additional value is selected according to the first determination bit or the second determination bit. Output as meters.

The first demultiplexer 440 receives the first decision bit and the second decision bit output from the processing element 430, performs demultiplexing according to the clock signal (CLK), and performs four decision bits. (DA0, DA1, DB0, DB1)
Is output. That is, the first determination bit and the second determination bit are output as DA0 and DA1 while the clock signal (CLK) is at the “high” logic level, and the first determination bit and the second determination bit are output during the “low” logic level. Two decision bits are output at DB0 and DB1. Similarly, the opposite is true. At this time, the four determination bits (DA0, DA1, DB0, DB1) output per one clock cycle are stored in the surviving memory unit 300 (see FIG.
Then, the original information sequence is restored using the decision bit.

The second demultiplexer 450 receives the first state meter and the second state meter output from the processing element 430, performs demultiplexing according to the clock signal (CLK), and performs four state meters. (SA0, SA1, SB0, S
B1) is output. That is, while the clock signal (CLK) is at the “high” logic level, the first state meter and the second
The state meters are output at SA0 and SA1, and the first and second state meters are output at SB0 and SB1 while at the "low" logic level. Similarly, the opposite is true. At this time, four state meters (SA0, SA1, SB0, SB1) output per clock cycle.
Is supplied to the corresponding processing element.

The control section 460 generates and outputs a clock signal (CLK) for controlling the operations of the multiplexing section 420, the first demultiplexing section 440 and the second demultiplexing section 450, and outputs one clock cycle. The number of operations of the multiplexing unit 420 and the first and second demultiplexing units 440 and 450 is controlled. Here, the clock signal (CLK)
Is set to perform twice per cycle, but four times when using a smaller ASIC cell library technology or when operating at a frequency lower than the 80 MHz of the European Digital Video Broadcasting (DVB) standard. The above operation can also be performed.

As a result, in the case of the 64 state modes, two states using the same state meter were conventionally processed by one processing element, so that 32 processing elements were required. By grouping the processing elements using the same branch meter into two units for the 32 processing elements using the same state meter, only 16 processing elements are needed, and the area of the hardware is reduced. 50%
To a degree. This is not merely a reduction in area by reducing the number of processing elements. That is, ASI
C is composed of a cell area and a connection area, but the connection area is greatly reduced through the sharing of the branch meter in the processing element.

[0044]

As described above, according to the present invention, in the case of N state modes, N / 2 processing elements using the same state meter are grouped into L unit processing elements using the same branch meter. By doing so, only N / 2L processing elements are required, and the area of hardware required for the ASIC can be significantly reduced.

It is obvious that the present invention is not limited to the above-described embodiment, and that many modifications can be made by those skilled in the art within the technical idea to which the present invention belongs.

[Brief description of the drawings]

FIG. 1 is a diagram showing a trellis diagram used for a Viterbi decoding algorithm.

FIG. 2 is a block diagram showing a general Viterbi decoder.

FIG. 3 is a block diagram illustrating processing elements included in the addition / comparison / selection processor illustrated in FIG. 2;

FIG. 4 is a block diagram illustrating an addition / comparison / selection processor according to an embodiment of the present invention in a Viterbi decoder.

[Explanation of symbols]

 410 Grouping unit 420 Multiplexing unit 430 Processing element 440 First demultiplexing unit 450 Second demultiplexing unit

Claims (5)

[Claims] 1. A Viterbi decoder for performing maximum likelihood decoding on a superimposed code, comprising: two path meters and two branch meters are input, and the added values are compared with each other, and two determinations are made according to the comparison result. N processing elements for outputting bits and two state meters; and for grouping the N processing elements for the N states into processing units in K units using the same state meter and the same branch meter. A grouping unit, L supplied according to the grouping result (here,
L is a multiplexing unit for multiplexing 2K) path meters into two path meters according to a predetermined clock signal and outputting the multiplexed path meters to a corresponding processing element among the N processing elements; A first demultiplexer that receives two decision bits output from the element and demultiplexes and outputs the L decision bits according to the clock signal and outputs the result; and a second demultiplexer that outputs the corresponding processing element. And a second demultiplexer for receiving the two state meters, demultiplexing the L state meters according to the clock signal, and outputting the L state meters. . 2. The addition / comparison / selection processor includes a control unit that generates the clock signal and controls the number of operations of the multiplexing unit and the first and second demultiplexing units per clock cycle. The addition / comparison / selection processor in the Viterbi decoder according to claim 1, further comprising: 3. The addition / comparison / selection processor in the Viterbi decoder according to claim 1, wherein the grouping unit sets four grouping units for a total of 64 states. 4. The multiplexing unit according to claim 1, wherein said clock signal is
2. The addition / comparison / selection in the Viterbi decoder according to claim 1, wherein multiplexing is performed in accordance with a section having a "high" logic level and a section having a "low" logic level with respect to a clock cycle. Processor. 5. The first demultiplexer and the second demultiplexer respond to one clock cycle of the clock signal according to a section having a “high” logic level and a section having a “low” logic level. 2. The addition / comparison / selection processor in the Viterbi decoder according to claim 1, wherein demultiplexing is performed.