JPH0722969A - Arithmetic unit - Google Patents

Abstract

PURPOSE:To provide an arithmetic unit in which the arithmetic amounts of the ACS calculation of a viterbi decoding can be reduced by the addition of a few hardware in a digital signal processor. CONSTITUTION:The content of an address indicated by the same pointer is read from first and second data memories 1 and 2, and inputted to one inputs of an ALU 10 and an adder 11. Then, the contents of plural registers 12-15 being a pair are inputted to the other inputs of the ALU 10 and the adder 11, and those data are added by the ALU 10 and the adder 11. Then, each arithmetic result is stored in first and second registers 18 and 19 selected by the arithmetic result of a size comparator 21, inputted also to the size comparator 21, and the compared result is stored in a shift register 23. The data are simultaneously added by the ALU 10 and the adder 11, so that ACS calculation can be attained by one step, and the arithmetic amounts can be sharply reduced without increasing a memory compared with a conventional practice.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an arithmetic unit used in a digital signal processor or the like for performing Viterbi decoding of convolutional coded data for error correction.

[0002]

2. Description of the Related Art In recent years, a digital signal processor (hereinafter abbreviated as DSP) has been attracting attention as a processor for incorporating the device into a mobile phone or the like in accordance with the movement of digitization in the mobile communication field. In data communication on a mobile radio line, bit errors frequently occur, and it is necessary to perform error correction processing. Some error correction methods use Viterbi decoding for the convolutional code, and DSP may be used for this error correction processing.

Viterbi decoding realizes maximum likelihood decoding of a convolutional code by repeating a simple process called addition, comparison, and selection called ACS calculation and a traceback operation for finally decoding data. In this Viterbi decoding, every time the decoded data (received signal) corresponding to one information bit is obtained, the metric of the path in each state at that time is calculated, and the surviving path is obtained.

FIG. 5 shows a state S [2i] at a certain time point in a convolutional encoder having a code rate 1 / N and a constraint length k.
For (i = 0 to 2 ^k-1 -1), the state S at the immediately preceding time point is
² representing a state transition from [i] and state S [i + 2 ^k-2 ]
It shows how the book path is extended. Where state S
When the number in [] is 2 ^k-1 or more, the remainder of 2 ^k-1 is taken. Finding a surviving path is the state S
The path metric of each of the two paths extending to [2i] is calculated, compared, and the path that is more likely is selected. The state S [i] and the state S [i at the previous time point
+2 ^k−2 ] for each path metric is P ^ [i],
Let P ^ [i + 2 ^k-2 ]. The distance between the original output of the convolutional encoder and the received signal at the time of transition from the previous state to the current state is called a branch metric, and is a metric of a path extending from each state to the state S [2i]. If the branch metrics are a and b, the state S
The path metric of two paths extending to [2i] can be expressed as P ^ [i] + a P ^ [i + ^2k-2 ] + b. Next, the two path metrics are compared, and the most likely one is selected. In general, a smaller path metric value is often selected, and the path metric P [2i] of the state S [2i] is as follows. P [2i] = min [(P ^ [i] + a), (P ^ [i + ^2k-2 ] + b)] Here, min [A, B] indicates that the smaller one of A and B is selected. . In this way, the processing for obtaining the path metric, the comparison of the path metric, and the selection of the path are performed for 2 ^k-1 states at each time point.

Further, the history of which path is selected in the path selection is stored in the path select signals PS [j], (j =
0 to 2 ^k-1 -1). If the number in [] of the state S [] immediately before the selected path is smaller than that in the other state, PS [j] = 0, otherwise PS [j] = 1. In the above case, i <i + 2
^{If k-2} (mod2 ^k-1 ), the path select signal PS
[2i] is as follows.

[Equation 1]

Since there are two paths extending in each state before the selection of a path, there are 2 · 2 ^k−1 branch metrics at a certain point in time, but it is assumed that the output of the convolutional encoder is N bits. Considering this, it is understood that the branch metric calculation at that time does not have to be performed 2 · 2 ^k−1 times, and can be performed 2 ^N times for the received signal and the 2 ^N kinds of output patterns.

FIG. 6 is a block diagram of a conventional arithmetic unit. Hereinafter, the arithmetic logic operation circuit is abbreviated as ALU.
In FIG. 6, 31 is a data memory for storing a path metric, a path select signal, etc., 32 is a data memory 3.
A bus connected to 1 for supplying data and storing operation results, 33 is a latch for temporarily storing a value on the right side of the ALU 35, 34 is a latch for temporarily storing a value on the left side of the ALU 35, and 35 is an arithmetic ALU that performs logical operations,
36, 37, 38, 39, 40, 41, 42 are registers for temporarily storing the operation result, 43, 44 are multiplexers for selecting register output, and 45, 46, 47, 48 are read addresses or storage addresses of the data memory 31. Is a pointer, 49 is a multiplexer for selecting the pointer output, and 50 is a barrel shifter for shifting the output of the ALU 35.

With respect to the arithmetic unit configured as described above, the operation of ACS calculation in 2 ^k-1 states at a certain time will be described. For simplicity, the description will be made assuming that N = 2 and k = 3. In the data memory 31, the path metric P ^ [i], (i = 0 to 3) of each state at the immediately preceding time point, and the path metric P [i], (i = 0 to 0) of each state obtained at the current time point are stored.
3) and the path select signals PS [i], (i = 0 to 0
An area for storing 3) is provided. FIG. 4 is a diagram showing an example of area allocation of the data memory 31. Pointers 45, 4
6, 47, and 48 are respectively set as a read address of P ^ [0], a read address of P ^ [2], a storage address of P [0], and a path select signal storage address as initial values.
FIG. 3 shows the transition from the previous state to the current state for all states. In FIG. 3, an example of the original output symbol of the convolutional encoder is shown for each path when the previous state transitions to the current state. The branch metric is calculated by calculating the distance between the received signal and each output symbol. If the output symbols are the same, the branch metrics are the same. Therefore, calculation is performed for 2 ² types of output symbols 00, 01, 10, 11. All you have to do is register 36, 37, 38, 39
Store 2 ² types of branch metrics already calculated in.

AC at 2 ² states at a certain time point
The outline of the S calculation operation will be described by dividing it into steps.

ACS calculation of state S [0] (1) The path metric P ^ [0] is read from the address of the data memory 31 pointed by the pointer 45 and stored in the latch 33. The ALU 35 allows the contents of the latch 33 to pass through and stores it in the register 40. (2) The content of the register 36 is stored in the latch 33. The content of the register 40 is stored in the latch 34. ALU35
Adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 40. This state is "P ^
The sum of [0] and the branch metric for output symbol 00 was determined. "It turns out that. (3) The path metric P ^ [2] is read from the address of the data memory 31 pointed by the pointer 46 and stored in the latch 33. The ALU 35 allows the contents of the latch 33 to pass therethrough and stores them in the register 41. (4) The content of the register 39 is stored in the latch 33. The contents of the register 41 are stored in the latch 34. ALU35
Adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 41. This state is "P ^
The sum of [2] and the branch metric for the output symbol 11 was obtained. "It turns out that. (5) The content of the register 40 is stored in the latch 33. The contents of the register 41 are stored in the latch 34. ALU35
Compares the contents of the latch 33 with the contents of the latch 34. (6) If the content of the latch 33 is smaller than or equal to (5), (7), (8) and (9) are executed. If the content of the latch 34 is smaller in (5), (7) '
(8) '(9)' is executed. (7) The contents of the register 40 are stored in the address of the data memory 31 pointed to by the pointer 47. (8) The content of the pointer 42 is stored in the latch 33. A
The LU 35 allows the contents of the latch 33 to pass through, shifts the left one bit by the barrel shifter 50, and stores the result in the register 42. (9) The fixed value 0 is stored in the latch 33. Register 42
The contents of the above are stored in the latch 34. ALU35 is latch 3
The contents of 3 and the contents of the latch 34 are added, and the result is stored in the register 42. (7) 'The content of the register 41 is stored in the address of the data memory 31 pointed to by the pointer 47. (8) 'The content of the register 42 is stored in the latch 33.
The ALU 35 allows the contents of the latch 33 to pass through, shifts the left one bit by the barrel shifter 50, and stores the result in the register 42. (9) 'Store the fixed value 1 in the latch 33. Register 4
The contents of 2 are stored in the latch 34. The ALU 35 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 42. This state means "comparison of path metrics, selection, and storage of path select signal".

ACS calculation of state S [1] (10) The path metric P ^ [0] is read from the address of the data memory 31 pointed by the pointer 45 and stored in the latch 33. The ALU 35 allows the contents of the latch 33 to pass through and stores it in the register 40. (11) The content of the register 39 is stored in the latch 33.
The content of the register 40 is stored in the latch 34. ALU3
5 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 40. This state is "P ^
The sum of [0] and the branch metric for the output symbol 11 was obtained. "It turns out that. (12) The path metric P ^ [2] is read from the address of the data memory 31 pointed by the pointer 46 and stored in the latch 33. The ALU 35 allows the contents of the latch 33 to pass therethrough and stores them in the register 41. (13) The contents of the register 36 are stored in the latch 33.
The contents of the register 41 are stored in the latch 34. ALU3
5 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 41. This state is "P ^
The sum of [2] and the branch metric for the output symbol 00 was obtained. "It turns out that. (14) The content of the register 40 is stored in the latch 33.
The contents of the register 41 are stored in the latch 34. ALU3
5 compares the contents of the latch 33 with the contents of the latch 34. (15) If the contents of the latch 33 are smaller or equal in (14), (16), (17) and (18) are executed. If the content of the latch 34 is smaller in (14), (16) '(17)' (18) 'are executed. (16) After incrementing the pointer 47, the contents of the register 40 are stored in the address of the data memory 31 pointed to by the pointer 47. (17) The content of the register 42 is stored in the latch 33.
The ALU 35 allows the contents of the latch 33 to pass through, shifts the left one bit by the barrel shifter 50, and stores the result in the register 42. (18) The fixed value 0 is stored in the latch 33. Register 4
The contents of 2 are stored in the latch 34. The ALU 35 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 42. (16) 'After incrementing the pointer 47, the register 41 is added to the address of the data memory 31 pointed to by the pointer 47.
Stores the contents of. (17) 'The content of the register 42 is stored in the latch 33. The ALU 35 allows the contents of the latch 33 to pass through, shifts the left one bit by the barrel shifter 50, and stores the result in the register 42. (18) ′ The fixed value 1 is stored in the latch 33. The contents of the register 42 are stored in the latch 34. The ALU 35 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 42. This state means "comparison of path metrics, selection, and storage of path select signal".

ACS calculation of state S [2] (19) After incrementing the pointer 45, the path metric P ^ [1] is read from the address of the data memory 31 pointed to by the pointer 45 and stored in the latch 33. AL
U35 allows the content of the latch 33 to pass through and stores it in the register 40. (20) The content of the register 37 is stored in the latch 33.
The content of the register 40 is stored in the latch 34. ALU3
5 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 40. This state is "P ^
The sum of [1] and the branch metric for the output symbol 01 was obtained. "It turns out that. (21) After incrementing the pointer 46, the path metric P ^ [3] is read from the address of the data memory 31 pointed to by the pointer 46 and stored in the latch 33. AL
U35 allows the content of the latch 33 to pass through and stores it in the register 41. (22) The contents of the register 38 are stored in the latch 33.
The contents of the register 41 are stored in the latch 34. ALU3
5 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 41. This state is "P ^
The sum of [3] and the branch metric for the output symbol 10 was obtained. "It turns out that. (23) The content of the register 40 is stored in the latch 33.
The contents of the register 41 are stored in the latch 34. ALU3
5 compares the contents of the latch 33 with the contents of the latch 34. If the contents of the latch 33 are smaller than or equal to (24) and (23), (25), (26) and (27) are executed. If the content of the latch 34 is smaller in (23), (25) '(26)' (27) 'are executed. (25) After incrementing the pointer 47, the contents of the register 40 are stored in the address of the data memory 31 pointed to by the pointer 47. (26) The contents of the register 42 are stored in the latch 33.
The ALU 35 allows the contents of the latch 33 to pass through, shifts the left one bit by the barrel shifter 50, and stores the result in the register 42. (27) The fixed value 0 is stored in the latch 33. Register 4
The contents of 2 are stored in the latch 34. The ALU 35 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 42. (25) 'After incrementing the pointer 47, the register 41 is added to the address of the data memory 31 pointed to by the pointer 47.
Stores the contents of. (26) ′ The content of the register 42 is stored in the latch 33. The ALU 35 allows the contents of the latch 33 to pass through, shifts the left one bit by the barrel shifter 50, and stores the result in the register 42. (27) ′ The fixed value 1 is stored in the latch 33. The contents of the register 42 are stored in the latch 34. The ALU 35 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 42. This state means "comparison of path metrics, selection, and storage of path select signal".

ACS calculation of state S [3] (28) The path metric P ^ [1] is read from the address of the data memory 31 pointed by the pointer 45 and stored in the latch 33. The ALU 35 allows the contents of the latch 33 to pass through and stores it in the register 40. (29) The contents of the register 38 are stored in the latch 33.
The content of the register 40 is stored in the latch 34. ALU3
5 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 40. This state is "P ^
The sum of [1] and the branch metric for the output symbol 10 was obtained. "It turns out that. (30) The path metric P ^ [3] is read from the address of the data memory 31 pointed by the pointer 46 and stored in the latch 33. The ALU 35 allows the contents of the latch 33 to pass therethrough and stores them in the register 41. (31) The content of the register 37 is stored in the latch 33.
The contents of the register 41 are stored in the latch 34. ALU3
5 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 41. This state is "P ^
The sum of [3] and the branch metric for the output symbol 01 was obtained. "It turns out that. (32) The contents of the register 40 are stored in the latch 33.
The contents of the register 41 are stored in the latch 34. ALU3
5 compares the contents of the latch 33 with the contents of the latch 34. If the contents of the latch 33 are smaller than or equal to (33) and (32), (34), (35) and (36) are executed. If the content of the latch 34 is smaller in (32), (34) '(35)' (36) 'are executed. (34) After incrementing the pointer 47, the contents of the register 40 are stored in the address of the data memory 31 pointed to by the pointer 47. (35) The contents of the register 42 are stored in the latch 33.
The ALU 35 allows the contents of the latch 33 to pass through, shifts the left one bit by the barrel shifter 50, and stores the result in the register 42. (36) The fixed value 0 is stored in the latch 33. Register 4
The contents of 2 are stored in the latch 34. The ALU 35 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 42. (34) 'After incrementing the pointer 47, the register 41 is added to the address of the data memory 31 pointed to by the pointer 47.
Stores the contents of. (35) ′ The content of the register 42 is stored in the latch 33. The ALU 35 allows the contents of the latch 33 to pass through, shifts the left one bit by the barrel shifter 50, and stores the result in the register 42. (36) ′ The fixed value 1 is stored in the latch 33. The contents of the register 42 are stored in the latch 34. The ALU 35 adds the contents of the latch 33 and the contents of the latch 34, and stores the result in the register 42. This state means "comparison of path metrics, selection, and storage of path select signal". (37) The contents of the register 42 are stored in the address of the data memory 31 pointed to by the pointer 48. This state means that "the path select signal of each state at one time point is packed into one word and stored".

As described above, in the above conventional arithmetic unit, N
= 2 and k = 3, 2 at a certain time point ²In the state of
It takes about 37 steps to perform ACS calculation.
You can Further, in general, there are cases where N = N and k = k.
Point 2^k-1Of ACS calculation in each state
To (9 * 2^k-1Can be done in about +1) steps
Wear. However, N is large or the number of registers is limited.
If there is such a thing, it is necessary to expect some increase in steps.
It

[0015]

However, in the above-mentioned conventional arithmetic unit, convolutional coding is often applied to hundreds of bits in one frame in the field of mobile communication, and bit error of the line in mobile communication. Since the constraint length k of the convolutional code is often 5 or more, since A is poor, A is performed for each state at each time point.
There is a problem that the calculation amount of CS calculation increases.

The present invention solves such a conventional problem, and an object of the present invention is to provide an excellent arithmetic unit capable of significantly reducing the number of arithmetic steps for ACS calculation. .

[0017]

In order to achieve the above object, the present invention provides first and second data memories which can be addressed by the same pointer and which can be read and written at the same time, an arithmetic logic operation circuit, Compares the adder that performs addition in parallel with the arithmetic logic operation circuit, the multiple registers used in pairs when executing the arithmetic logic operation circuit and the adder at the same time, and the magnitude comparison of the output of the arithmetic logic operation circuit and the adder output. A large / small comparator to be executed, a shift register for storing a comparison result of the large / small comparator, a first and a second selected by the comparison result of the large / small comparator while temporarily storing the operation result of the arithmetic logic operation circuit and the adder. A register, and reads the contents of the address pointed by the same pointer from the first and second data memories, respectively, and uses them as one input of the arithmetic logic operation circuit and the adder, and The contents of a plurality of registers are used as the other input of the arithmetic operation circuit and the adder, respectively, and the arithmetic operation circuit and the adder perform the addition at the same time. The respective operation results are stored in the first and second registers, respectively. It is characterized in that it is also input to a comparator and the comparison result is stored in a shift register.

[0018]

Therefore, according to the present invention, the ALU and the adder can perform the addition at the same time, and the respective operation results can be compared in magnitude. Therefore, the addition and the comparison in the ACS calculation can be performed in one step, and the data can be compared. This has the effect that the number of calculation steps can be reduced without increasing the size of the memory.

[0019]

DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 1 is a block diagram showing the configuration of an arithmetic unit in one embodiment of the present invention. In FIG. 1, reference numerals 1 and 2 are first numbers for storing a path metric, a path select signal, and the like.
A second data memory 3 and 4 are connected to the data memories 1 and 2, respectively, and a bus 5 is provided for supplying data and storing operation results, and 5 is an input from the bus 4 and an input from a register described later. 6 is a latch for temporarily storing the value of the right input of the ALU 10, 7 is a latch for temporarily storing the value of the left input of the ALU 10, 8 is a latch for temporarily storing the value of the right input of the adder 11, 9 Is a latch for temporarily storing the value on the left side of the adder 11, 10
Is an ALU that performs arithmetic logic operation on the contents of latches 6 and 7, 11 is an adder that adds the contents of latches 8 and 9, and 12, 13, 14, and 15 are pairs that temporarily store the operation results of ALU 10 and adder 11. A plurality of registers, 16 and 17 are multiplexers for selecting the outputs of the registers 12 to 15, 18 is a first register for temporarily storing the operation result of the ALU 10, and 19 is a second register for temporarily storing the operation result of the adder 11. Register, 20 is register 18, 1
Multiplexer for selecting 9 output, 21 is ALU10
Of the ALU and the output of the adder 11 are compared, and the ALU
A large / small comparator that outputs a comparison result 0 when the output of 10 is small or equal, and a comparison result 1 when the output of the adder 11 is small, 22 is a path select signal that is the comparison result of the large / small comparator 21, 23 Is a shift register which receives the path select signal 22 as a shift input, 24, 25 and 26 are pointers indicating read addresses or storage addresses of the data memories 1 and 2, 27 is a multiplexer for selecting pointer output, and 28 is the path select signal 22. It is a delay device that delays by one step.

With respect to the arithmetic unit configured as above, the operation of ACS calculation in 2 ^k-1 states at a certain time will be described. For simplicity, N = 2 and k = 3. In the data memories 1 and 2, the path metric P ^ [i], (i = 0 to 3) of each state at the immediately preceding time point, and the path metric P [i], (i = 0 to
3) and the path select signals PS [i], (i = 0 to 0
An area for storing 3) is provided. FIG. 2 is a diagram showing an example of area allocation of the data memories 1 and 2. Pointer 24,
The initial values of 25 and 26 are (P ^ [0], P
A read address of ^ [2]), a storage address of (P [0], P [2]), and a path select signal storage address are set in advance.
FIG. 3 shows the transition from the previous state to the current state for all states. In FIG. 3, an example of the original output symbol of the convolutional encoder is shown for each path when the previous state transitions to the current state. The branch metric is calculated by calculating the distance between the received signal and each output symbol. If the output symbols are the same, the branch metrics are the same. Therefore, calculation is performed for 2 ² types of output symbols 00, 01, 10, 11. All you have to do is register 12, 13, 14, 15
Store 2 ² types of branch metrics already calculated in.

Hereinafter, A in 2 ² states at a certain time point
An outline of the CS calculation operation will be described in steps.

ACS calculation of state S [0] (1) The path metrics P ^ [0] and P ^ [2] are read from the addresses of the data memories 1 and 2 pointed by the pointer 24,
The data is stored in the latch 6 and the latch 9, respectively. Register 12
The contents of the above are stored in the latch 7, and the contents of the register 15 corresponding thereto are stored in the latch 8. The ALU 10 adds the contents of the latch 6 and the contents of the latch 7 and outputs the result to the register 18
And the other side of the magnitude comparator 21. On the other hand, the adder 11 adds the contents of the latch 8 and the contents of the latch 9, stores the result in the register 19, and uses it as the other input of the magnitude comparator 21. Large and small comparator 21
Compares the output of the ALU 10 with the output of the adder 11 to generate a path select signal 22. The path select signal 22 is transferred to the shift register 23 and the delay unit 28.
Latched on. In this state, the sum of “P ^ [0] and the branch metric for the output symbol 00 is obtained, and the sum of P ^ [2] and the branch metric for the output symbol 11 is obtained. The path select signal has been stored. " (2) The contents of the register 18 or the register 19 selected by the output of the delay device 28 are stored in the address of the data memory 1 pointed to by the pointer 25.

ACS calculation of state S [1] (3) The contents of the register 15 are stored in the latch 7, and the contents of the register 12 paired therewith are stored in the latch 8. ALU1
For 0, the contents already stored in the latch 6 in step (1) and the contents of the latch 7 are added, the result is stored in the register 18, and the result is input to one of the magnitude comparators 21. On the other hand, the adder 11 adds the contents already stored in the latch 9 and the contents of the latch 8 in step (1),
The result is stored in the register 19 and used as the other input of the magnitude comparator 21. The size comparator 21 is the ALU1
The output of 0 and the output of the adder 11 are compared in size to generate a path select signal 22. Path select signal 22
Are latched by the shift register 23 and the delay unit 28. In this state, the sum of “P ^ [0] and the branch metric for the output symbol 11 is obtained, and P ^ [2]
Then, the sum of the branch metric for the output symbol 00 is obtained, the path metrics are compared, selected, and the path select signal is stored. "It turns out that. (4) After incrementing the pointer 25, the contents of the register 18 or the register 19 selected by the output of the delay device 28 are stored in the address of the data memory 1 pointed to by the pointer 25. (5) The content of the pointer 25 is returned to the storage address of (P [0], P [2]).

ACS calculation of state S [2] (6) After incrementing the pointer 24, the path metrics P ^ [1] and P ^ [3] are read from the addresses of the data memories 1 and 2 pointed to by the pointer 24, respectively. The data is stored in the latch 6 and the latch 9. The contents of the register 13 are stored in the latch 7, and the contents of the register 14 paired therewith are stored in the latch 8. The ALU 10 adds the contents of the latch 6 and the contents of the latch 7, stores the result in the register 18, and inputs it to one of the magnitude comparators 21. Meanwhile adder 1
1 adds the contents of the latch 8 and the contents of the latch 9 and stores the result in the register 19 and the magnitude comparator 21.
The other input of. The magnitude comparator 21 compares the output of the ALU 10 and the output of the adder 11 to generate a path select signal 22. The path select signal 22 is
It is latched by the shift register 23 and the delay device 28.
In this state, the sum of "P ^ [1]" and the branch metric for the output symbol 01 is obtained, and the sum of P ^ [3] and the branch metric for the output symbol 01 is obtained. The path select signal has been stored. " (7) The contents of the register 18 or the register 19 selected by the output of the delay device 28 are stored in the address of the data memory 2 pointed by the pointer 25.

ACS calculation of state S [3] (8) The contents of the register 14 are stored in the latch 7, and the contents of the register 13 paired therewith are stored in the latch 8. ALU1
For 0, the contents already stored in the latch 6 in step (6) and the contents of the latch 7 are added, the result is stored in the register 18, and the result is input to one of the magnitude comparators 21. On the other hand, the adder 11 adds the contents already stored in the latch 8 and the contents of the latch 9 in step (6),
The result is stored in the register 19 and used as the other input of the magnitude comparator 21. The size comparator 21 is the ALU1
The output of 0 and the output of the adder 11 are compared in size to generate a path select signal 22. Path select signal 22
Are latched by the shift register 23 and the delay unit 28. In this state, the sum of “P ^ [1] and the branch metric for the output symbol 10 is obtained, and P ^ [3]
And the branch metric for the output symbol 01 are obtained, the path metrics are compared, selected, and the path select signal is stored. "It turns out that. (9) After incrementing the pointer 25, the content of the register 18 or the register 19 selected by the output of the delay device 28 is stored in the address of the data memory 2 pointed to by the pointer 25. (10) At the address of the data memory 1 pointed by the pointer 26,
The contents of the shift register 23 are stored. This state is
That is, "the path select signal of each state at one time point is packed into one word and stored."

As described above, in the arithmetic unit of the above embodiment,
In the case of N = 2 and k = 3, ACS calculation in 2 ² states at a certain time can be performed in about 10 steps as compared with the conventional 37 steps. In addition, in general, when N = N and k = k, ACS calculation in 2 ^k-1 states at a certain time is performed by using the conventional (9 * 2 ^{k- 1)}
It can be performed in about (2 * 2 ^k-1 +1) steps as opposed to about +1) steps. However, N is large,
If there is a limit on the number of registers, it is necessary to expect some increase in steps.

[0027]

According to the present invention, as is apparent from the above embodiment, since the ALU and the adder simultaneously perform the addition and the respective operation results are compared in magnitude, the ACS is performed in one step.
Calculations can be added and compared, and the data memory is divided into two but the total size does not increase.
This has an advantage that the number of calculation steps of CS calculation can be significantly reduced.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of an arithmetic unit according to an embodiment of the present invention.

FIG. 2 is a schematic diagram showing an example of area allocation of a data memory for explaining the operation of the arithmetic unit.

FIG. 3 is a state transition diagram showing, for all states, a state of transition from the previous state to the current state for explaining the operation of the arithmetic unit.

FIG. 4 is a schematic diagram showing an example of area allocation of a data memory for explaining the operation of the arithmetic unit.

FIG. 5 is a state transition diagram showing a state of a state transition path of a convolutional encoder in Viterbi decoding for explaining the operation of the arithmetic unit.

FIG. 6 is a block diagram showing a schematic configuration of a conventional arithmetic unit.

[Explanation of symbols]

 1 First Data Memory 2 Second Data Memory 3 Bus 4 Bus 5 Multiplexer 6 Latch 7 Latch 8 Latch 9 Latch 10 ALU (Arithmetic Logic Operation Circuit) 11 Adder 12 Register 13 Register 14 Register 15 Register 16 Multiplexer 17 Multiplexer 18 First register 19 Second register 20 Multiplexer 21 Large / small comparator 22 Path select signal 23 Shift register 24 Pointer 25 Pointer 26 Pointer 27 Multiplexer 28 Delayer

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Minoru Okamoto 1006 Kadoma, Kadoma City, Osaka Prefecture Matsushita Electric Industrial Co., Ltd.

Claims (1)

[Claims] 1. A first and a second data memory capable of address designation by the same pointer and capable of simultaneous reading and writing, an arithmetic logic operation circuit, an adder for performing addition in parallel with the arithmetic logic operation circuit, and an arithmetic operation. Multiple registers used as a pair when executing the logic operation circuit and adder at the same time, a magnitude comparator that compares the magnitude of the output of the arithmetic logic operation circuit and the adder output, and a shift that stores the comparison result of the magnitude comparator The register and the first and second registers for temporarily storing the operation results of the arithmetic logic operation circuit and the adder and being selected by the comparison result of the magnitude comparator are provided, and the same data from the first and second data memories is provided. The contents of the address pointed to by the pointer are read out and used as one input of the arithmetic logic operation circuit and the adder, and the contents of a plurality of registers forming a pair are respectively calculated. The other input of the adder is added simultaneously by the arithmetic operation circuit and the adder. The respective operation results are stored in the first and second registers, respectively, and also input to the magnitude comparator, and the comparison result is shifted. An arithmetic unit characterized by storing in a register.