Method and device for obtaining sum of products using integrated circuit.

BACKGROUND OF THE INVENTION

Field of the Invention

0001The present invention relates to a method and a device for obtaining a sum of products using integrated circuits (IC's) and utilized in a picture (or image) processing system using a spatial filtering method, and in particular, to a method and a device for obtaining a sum of products using a predetermined number of multipliers and adders for summing the products.

Description of the Related Art

0002A device for obtaining a sum of products is used in a picture processing system or in radio commu­nication equipment. In the former, each pixel of a picture is processed by the device, and as a result, a smoother, enhanced, or contour-emphatic picture is obtained. This device is applied in the processing of a picture from a weather satellite, a parts inspection apparatus in a factory, a viewing robot, or the like. In the latter, the device is used as an element in a transversal equalizer, to increase the quality of the transmission signal.

0003A sum of products is obtained by calculating the products of pairs of multiplicands and multipliers, and then add the total products. When this calculation is performed by IC's, usually the number of devices used is in accordance with the scale of the operation. Namely, first a desired number of multipliers (number of pairs of the object to be multiplied) is provided. The products of these pairs are calculated by the multiplier and a plurality of products is obtained. The products are added two by two and a corresponding sum is obtained for each addition. Each sum is then further added two by two, and this calculation operation is repeated until the total sum of products is obtained.

0004When the above operation is performed, the only problem with the multipliers is the capacity of an IC to cope with the number of multipliers and the figure length of the operand applied to the multiplier. The "figure length", i.e., number of numeric characters, handled by this multiplier is determined by the figure length of the multiplicand and multiplier. On the other hand, for the adders, the sums to be calculated increase as the processing advances. This requires a change of the scale of the adder in response to the stage at which the adder is located. That is, an IC having the same rating cannot be used for all of the adders. The present invention has been created to solve this problem, and satisfies the above operation needs by using a plurality of IC's having the same rating.

SUMMARY OF THE INVENTION

0005An object of the present invention is to provide a method and a device for obtaining a sum of products by which the summing of products on an arbitrary scale can be carried out, without the limitation imposed by the capacity of an IC, by using a plurality of IC's each having a limited capacity and a certain rating.

0006Another object of the present invention is to provide a method and a device for obtaining a sum of products wherein each multiplier can be calculated the product by dividing the multiplicand and/or multiplier by a predetermined figure length, and thus the required number of multipliers can be accommodated in one IC.

0007In one aspect of the present invention, to accomplish the above-mentioned objects there is provided a method for obtaining a sum of products wherein, when products between a pair of operands to be multiplied are calculated for a plurality of pairs and the sum for the plurality of products is calculated, the sum of products is obtained by using a predetermined multiplier means and adders to sum the products; comprising the following steps of: dividing a portion of, or entire, operands to be multiplied into a plurality of divisions having a predetermined figure length; obtaining a sum of products from each pair of operands having the same figure position as a group; adding, by another adder, the obtained sums of products group by group by shifting the figure position of the sums corresponding to the figure position of the operands in the group.

0008In another aspect of the present invention, there is provided a device for obtaining a sum of products, comprising a plurality of integrated circuits each including a plurality of multiplier means, an adder group for adding products calculated by the multiplier means, and an adder having an external input, for adding the sum from the adder group to a calculation result from the preceding stage integrated circuit; wirings by which at least a portion of a multiplicand and a multiplier to be operated is divided by a predetermined number of figures, the divided figures are supplied to the multiplier means, and the products of the multi­plicand and the multiplier having the same figure position are added; and by which the results of sum of products in each integrated circuit are supplied to the external input of the next stage integrated circuit with a figure shift in response to the figure position of the multiplicand and the multiplier without lower figures.

0009Other features and advantages of the invention will be apparent from the following description in connection with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

0010<ul id="ul0001" list-style="none"><li>Figure 1 is a circuit diagram of a conventional device for obtaining a sum of products;</li><li>Fig. 2 is a circuit diagram showing a combination of a plurality of the devices shown in Fig. 1;</li><li>Fig. 3 is an outline diagram of wiring between IC's according to a first embodiment of the present invention;</li><li>Fig. 4A and Fig. 4B are detailed wiring diagrams of the embodiment shown in Fig. 3;</li><li>Fig. 5 is a circuit diagram of the IC shown in Fig. 3;</li><li>Fig. 6 is a circuit diagram of an example of a multiplier in the IC shown in Fig. 3;</li><li>Fig. 7 is a circuit diagram of an IC according to a second embodiment of the present invention;</li><li>Fig. 8 is a block diagram of a picture processing system to which the present invention is applied;</li><li>Fig. 9 is a block diagram of a portion carrying out a spatial filtering process in the system shown in Fig. 8;</li><li>Fig. 10 is a diagram explaining factors in the obtaining of a sum of products in the portion of the system shown in Fig. 9;</li><li>Fig. 11 is a block circuit diagram of a radio communication equipment to which the present invention is applied; and</li><li>Fig. 12 is a block circuit diagram of a transversal equalizer in the equipment shown in Fig. 11.</li></ul>

DESCRIPTION OF THE PREFERRED EMBODIMENTS

0011Prior to the description of the preferred embodiments, an example of an operation of this invention, and a conventional example thereof, are explained.

0012The present invention comprises a method and a device whereby, for example, the following operation is carried out. Note, this explanation is made by using concrete numerical decimal values, i.e. the following equation (1). 83 × 8 + 72 × 9 + 65 × 3 + 29 × 2 + 99 × 8 + 78 × 5 + 63 × 7 + 57 × 4 + 33 × 9      ... (1) First, the products of the highest figures of the multiplicands and multipliers are calculated, as follows. 8 × 8 + 7 × 9 + 6 × 3 + 2 × 2 + 9 × 8 + 7 × 5 + 6 × 7 + 5 × 4 + 3 × 9 = 345 (first sum of products) Then, the products of the lower figures of the multi­plicands and multipliers are calculated, as follows. 3 × 8 + 2 × 9 + 5 × 3 + 9 × 2 + 9 × 8 + 8 × 5 + 3 × 7 + 7 × 4 + 3 × 9 = 263 (second sum of products) The lowest figure, i.e. 3, is left as it is, as a lowest figure of the obtained result, and the first sum of products, 345, is added to the highest figures, 26, of the second sum of products, to obtain a total of 371. The lowest figure, i.e. 3, is then appended to the sum of the first sum of products and the highest figures of the second sum of products, to obtain a total of 3713 as a final result.

0013When the first sum of products is added to the second sum of products, the two numerical values are always 3 figures and 2 figures, and therefore, as long as the adder has the capacity to handle these figures, the adder will not overflow. In the present invention, the above-mentioned operating method is applied to the general operation for obtaining a sum of products. In the above example, although the multiplier comprises only one figure, if the multiplier comprises two figures, the multiplier can be divided in the same way as the multiplicand. In a practical device, binary numbers are used, and therefore, the operation is more complex than that of the above example. However, the calculation principle is the same.

0014When the operation for obtaining a sum of products is carried out, hitherto, the integrated circuit 61 shown in Fig. 1 has been used. In Fig. 1, the IC 61 comprises four multipliers 62, three adders 63, and an adder 64. The adder 63 adds the results of the multi­plied products, i.e., the products calculated by the multiplier 62, and the adder 64 adds the result of the adders 63 to a result from an external input. A pair of operands, i.e., a multiplicand and multiplier, are supplied to input terminals 65 and 66. The external input of the adder 64 is supplied to an external input terminal 67, and the operating result from another IC is also supplied to the terminal 67. The result of the sum of products is output from an output terminal 68.

0015When the IC 61 performs a spatial filtering using a 3 × 3 matrix in a picture (or image) processing system, the sum of nine products must be obtained, and therefore, three IC's 61, 71, and 81 are connected as shown in Fig. 2. In this example, the multiplicand corresponding to the value of the picture element and the multiplier corresponds to the factor. Also in this example, if the pairs of multiplicand and multiplier are increased, then another IC must be added.

0016As mentioned above, in the conventional method, when the amount of data to be processed is increased, the result obtained from another IC must be supplied to the adder 64 through the terminal 67, and the result obtained in that IC added to the result obtained from another IC, by setting the lowest figures thereof at the same position and using the adder 64. When the number of IC's is increased by one, the number of figures needed at the adder 64 becomes larger. Therefore, a problem arises in that the number of IC's must be limited to prevent an overflow of the obtained values at the adder 64. For example, assuming that the figure length of the multiplier 62 is 8 bits × 8 bits and the figure length of the adder 64 is 20 bits, then there must be an overflow because of the connection of four, or more than four, IC's 61.

0017Further, another problem arises in that the figure length at the multiplier 62 is also limited, e.g., more than 8 bits, and thus an amount of data over this limit cannot be processed. Accordingly, because the scale of an IC is limited, one IC cannot include the necessary number of multipliers having a required figure length to operate the operand needed to obtain a sum of products corresponding to the amount of data.

0018Figure 3 shows an outline diagram of the wiring of a device according to a first embodiment of the present invention.

0019An IC 1 comprises a plurality of multipliers 2-0 to 2-n, an adder group 3 adding the products obtained by the multipliers, and an adder 4 adding the addition result at the adder group 3 to a result obtained from another IC. In Fig. 3, X₀ to X_n are multiplicands. In the case of a spatial filtering using a 3 × 3 matrix, the number of multiplicands is nine. Each of the X₀ to X_n , for example, comprises 8 bits. The 8 bits are divided into four lots of 2 bits, and each lot of 2 bits is connected to a different IC, and thus, four IC's must be used. Note, (n + 1) multipliers are necessary for each IC. The multipliers Y₀ to Y_n are, for example, 4 bits, respectively. The multiplier calculates the product using the extended Booth algorithm, and therefore, an input of 5 bits is supplied to each multiplier as shown in Fig. 6. As mentioned above, the operand includes both the multiplicand and multiplier.

0020The following explanations show that, in this embodiment, the sum of products is obtained with reference to equations.

0021Assuming that the multiplier Y is 4 bits, the multiplicand X is positive number, and Y is a number indicated by a complement of 2, X is indicated as follows.     X = Σ x_i·2**i Where x_i is 0 or 1 and denotes the ith bit of X, and i is 0 at the lowest bit. 2**i indicates that i is an exponent of 2, i.e. 2**i indicates the ith power of 2.

0022Accordingly, the product X·Y is shown as follows.<maths id="math0001" num=""><img file="EP0260618A2_D0001.tif" /></maths> In this equation, the multiplicand X is divided by 2 bits, the products of each 2 bits and the multiplier Y are calculated, and each product is added by shifting two bits by two bits corresponding to the figure position before division. The above calculations are as follows. <maths id="math0002" num=""><img file="EP0260618A2_D0002.tif" /></maths> This equation shows that the following two operations (first and second operations) can obtain the same result. Where, in the first operation, the multi­plicands {X_k} (non-division) are multiplied by the multipliers {Y_k} and the products {X_k·Y_k} are added. In the second operation, the multiplicands {X_k} are divided by two bits, the divided two bits being at the same figure position are collected, the products {(x_k,i+1·2 + x_k,i)·Y_k} of the collected bits and the multiplier {Y_k} are obtained, the products are added with respect the same figure position, and the added products further added.

0023According to the above, X is divided by 2 bits which can be operated in the multiplier, and pairs of the divided multiplicand x_i+1 x_i (i = 0, 2, 4, ...) and the multiplier Y are formed. Similarly, other multiplicands are divided by 2 bits and pairs are formed. Then, pairs having the same figure position are collected and formed into groups. In each group, the multipliers calculate the products. In the extended Booth algorithm, the multiplier Y is divided by 3 bits, the multiplicands are multiplied by 0, ±1, or ±2 in response to the value (0 to 7) of the divided 3 bits, and the results are added together by shifting 2 bits by 2 bits. Therefore, although the multiplier is negative and indicated as a complement of 2, the multiplicand X can be multiplied independently by 0, ±1, or ±2. That is, in this multiplier, the multiplier Y can be divided. The division of Y is explained later with reference to Figs. 4A and 4B.

0024The products obtained at the multiplier 2-0 to 2-8 in the IC 1 are added together by the adder group 3, two by two.

0025The result of sum of products obtained at each IC 1 is added to the result obtained from another IC allotted to another group by the adder 4, and then the addition result is output through the output terminal as a final sum of products. At that time, in the adder 4, the result obtained from the other IC 1 is added by shifting certain figures in response to the figure position of the group belonging to the IC. Thus, since the addition is carried out by figure shifting, the lower figures are shortened in the adding operation. Therefore, even an adder having limited figures will not overflow during the processing of the operand. That is, the limitation of the figure length does not limit the figure length of the operand at the adder.

0026As shown in Fig. 3, in step 1 of the invention, a plurality of pairs having operands to be multiplied are divided into a plurality of divided pairs by dividing the operand in each pair to a predetermined figure length corresponding to the capacity of an IC.

0027In step 2, the divided pairs having the same figure position are collected to form a group. In each group the IC obtains a sum of products from the operand.

0028In step 3, the sum of products obtained in step 2 are added by another adder shifting the figure of the results corresponding to the figure position of each group.

0029Thus, the adding operation by the adder can be shortened for the lower figures shifted by moving the figure position. The figure length at the adder is less than a predetermined length, and therefore, if a plurality of IC's are connected together, the adder will not overflow. In addition, since the multiplier can calculate a multiplicand and multiplier having a small figure length, the number of multipliers and adders in one IC can be increased.

0030The first embodiment is now explained in detail with reference to Figs. 4A and 4B. In this case, the multiplier Y is divided by two. Data inputs D0 to D8 correspond to the multiplicands X₀ to X_n , and factors C0 to C8 correspond to the multiplier Y₀ to Y_n. The device in this embodiment comprises eight IC's which are denoted 1-1 to 1-8. Nine multipliers (2 bits × 4 bits) are provided in each IC.

0031Each 8 bits data of D0 to D8 is divided into lots of 2 bits and the divided lots of 2 bits are connected to the IC's 1-1 to 1-4, respectively. The factors C0 to C8 (8 bits) are divided into two portions. In IC 1, the multipliers are denoted 2-0 to 2-8. In IC 1-1, the lower (1 : 0) (8 bits are denoted from the lower figure to the higher figure as 0 to 7 and, for example, the bits from 0 to 1 denoted as 1 : 0) of the 8 bits of D0 is supplied to one input of the multiplier 2-0 and (4 : 0) of C0 supplied to the other input of the multi­plier 2-0. In IC 1-1, (1 : 0) of D1 is supplied to one input of the multiplier 2-1 and (4 : 0) of C1 is supplied to the other input of the multiplier 2-1. In IC 1-2, (3 : 2) of D0 is supplied to one input of the multiplier 2-0 and (4 : 0) of C0 is supplied to the other input of the multiplier 2-0. In IC 1-5, (1 : 0) of D0 is supplied to one input of the multiplier 2-0, and (8 : 4) of C0 is supplied to the other input of the multiplier 2-0. The remains follow similarly, as shown in Figs. 4A and 4B, and therefore the descriptions thereof are abbreviated. In each multiplier, the factors to be multiplied comprise 5 bits for using an extended Booth algorithm.

00329 : 2 of the output (9 : 0) of the preceding stage IC is supplied to one input of the adder 4. The rest (1 : 0) is supplied to the adder 9. The adder 9 is provided out of IC 1-1 to IC 1-8. The outputs of the adders 4 of IC 1-4 and IC 1-8 are supplied to the adder 9. That is, (1 : 0) of IC 1-1 output, (1 : 0) of IC 1-2 output, (1 : 0) of IC 1-3 output, (9 : 0) of IC 1-4 output, (1 : 0) of IC 1-5 output, (1 : 0) of IC 1-6 output, (1 : 0) of IC 1-7 output, and (9 : 0) of IC 1-8 output are supplied to the adder 9. The figure positions of the above input of the adder 9 are shown in Fig. 4B. Input (3 : 0) of the adder 4 bypasses the adder 9, and (3 : 0) is appended under the lowest figure of the addition result. The external input terminals of the adder 4 of IC 1-1 and IC 1-5 are not supplied with an input signal.

0033A detail of the above-mentioned IC 1 is shown in Fig. 5. A multiplier group 2 comprises nine multi­pliers 2-0 to 2-8. An adder group 3 comprises eight adders. The adder 4 is provided with a terminal 7 for receiving an output from another IC and the output terminal thereof is referred to as numeral 8.

0034As mentioned above, each multiplier calculates the divided multiplicand and the divided multiplier and obtains a product. The adders add the nine products from the multipliers, and add the inputs while shifting the figure thereof in response to the figure positions of the multiplicand and multiplier. The multipliers 2-0 to 2-8 have, for example, a figure length of 2 × 4 bits. The adder 4 has, for example, the figure length of 12 bits. The reference numerals 5 and 6 denote input terminals for the divided multiplicand and the divided multiplier.

0035Figure 6 shows a circuit diagram of an example of the multiplier. The multiplier calculates using the extended Booth algorithm. Reference numeral 21 denotes NAND circuit, 22 an AND circuit, 23 an OR circuit, 24 a NOR circuit, 25 an XOR (exclusive OR) circuit, 26 a NOT circuit, and 27 an adder of four bits.

0036Figure 7 shows a circuit diagram of an IC used in a second embodiment of the present invention.

0037This IC 11 comprises flip-flop circuits 19 at preceding and succeeding stages of the multipliers and adders, different from the IC of the first embodiment. By the provision of the flip-flop circuits 19, a pipeline operation in the operation of sum of products is possible.

0038In the pipeline operation, the processing flow of commands is divided into a maximum m steps and a maximum m commands are processed in parallel to realize a high speed processing.

0039Namely, in the first embodiment, the input of the multiplier must be held from input application until the obtained result is output from the final adder, however, in the second embodiment, since whenever one operation is carried out the obtained result is held, the holding of the input is not necessary after the obtained result is stored in the flip-flop. Therefore, the operation efficiency is increased.

0040A picture (image) processing system to which the present invention is applied is explained below with reference to Figs. 8 to 10. Figure 8 shows a block circuit diagram of the picture processing system.

0041A picture signal picked up through a camera is converted from analog to digital by an A/D converter, processed as a digital signal, and displayed on a monitor (MON.). The A/D converter is connected to a memory (MEM.), a convolution filter (CONV.), an operation apparatus (OPER.), and a first-in-first-out type memory (FIFO) through a data bus and control bus. The memory stores the picture signal, the picture signal is processed by a spatial filtering process through the convolution filter, and the apparatus obtains the picture signal. The FIFO stores the obtained results. The above elements or apparatus are controlled by a control board (CNTRL) through the control bus. The control board is connected to a control computer (COMP).

0042Below, the convolution filter is explained with reference to Fig. 9.

0043At first, a desired bus is selected by a bus selection device (BUS SEL.), the picture signal sent through the bus is supplied to an LSI, having a function of processing a sum of products obtained, directly or through a line memory (LINE M.) or line memories. Namely, the selected picture signal is directly supplied to an input "a", supplied to an input "b" through one line memory, and supplied to an input "c" through two line memories. In the LSI (sum of products calculating circuit), the digital picture signal value applied to the inputs "a", "b", and "c" is multiplied by factors ("F" input) stored in a ROM (read only memory) as shown in Fig. 10. The nine blocks in Fig. 10 denote that a digital value of a picture element is multiplied by the factor located at a center position, and digital values located adjacent to the picture element are multiplied by the factors located at the corresponding positions. Finally the nine products are added and the added value becomes the new data for the picture element. All of the picture element data is replaced by the new data, and thus the picture is made smooth, enhanced, or contours-enhanced by selection of the factor. The factors shown in Fig. 10 are three examples only.

0044A picture signal from CONV 1 (convolution filter 1) has been processed by a differential process, etc. The CONV 1 signal is added to the above-mentioned data (output "Z") processed by the LSI as an absolute addition. This processing is applied as a Sobel filter. The scaling device is a selector for obtaining the desired sum of products output.

0045Figure 11 and Fig. 12 show a digital type transversal equalizer in a QAM (quadrature amplitude modulation) radio communication equipment to which the invention is applied. A transmission portion is shown in the upper portion of Fig. 11. First, a transmission interface (TX INT) separates the transmission signal into an I channel digital signal and a Q channel digital signal. The two digital signals are D/A converted and quadrature amplitude modulated by a modulator (MOD.) and the modulated signal is output through a radio transmission equipment (RADIO TX EQP.) and an antenna.

0046The receiving side of the equipment is shown in the lower portion in Fig. 11. The signal received from an antenna is supplied to a demodulator (DEM) through a radio reception equipment (RADIO REC. EQP.). The signal is demodulated and supplied to an A/D converter (ADC). The output signal of the A/D converter is supplied to a transversal equalizer (TR. EQL), and the transversal equalizer outputs an I channel digital signal and a Q channel digital signal. These signals are sent to a reception interface (REC. INT.).

0047The details of the A/D converter and the transversal equalizer are shown in Fig. 12. The I and Q channel analog signals from the demodulator are supplied to four sum of products processing circuits through the A/D converters. After processing as shown in Fig. 12, the I channel digital signal and Q channel digital signal are obtained. The data signals at some moments from the A/D converter corresponds to multiplicands and the tap coefficients from a control portion (CONT) corresponds to the multipliers.