Abstract:
Digital signal processing often requires the fast summing of a chain of products. Known signal processors often use two separate dam buses via which the values to be multiplied are supplied in parallel, it being assumed that these values originate from different sources, for example from different memories. Because a product of two binary numbers has double the number of positions, therefore, an adder having double the word width is also used. In order to reduce this substantial expenditure at the expense of only a slight reduction in speed, an adder is provided having only the single word width and to process the most-significant and least-significant bits of the product during two successive clock periods. The values to be multiplied can then be supplied successively.

Description:
SUMMARY OF THE INVENTION 
     The invention relates to a method of forming the sum of a chain of products of each time two numbers which are successively supplied, each intermediate result of the summing operation being temporarily stored, and also relates to a device for forming the sum of a chain of products of each time a first and a second value, comprising a storage device for storing a number of values with a predetermined first number of bits, a clock-controlled control device for controlling the writing of values in registers, a first register device for storing each time two values to be multiplied by one another, a multiplier device comprising two inputs which are connected to the first register device, and a downstream product register which comprises an output for double the first number of bits, an adder device which comprises two sum inputs for each time the first number of bits, one of said inputs being connectable to the output of the product register, and a downstream sum register which consists of at least two partial sum registers for each time the first number of bits comprising an output which can be coupled to the other input of the adder device. 
     Methods of this kind are frequently used in digital signal processing, for example for the filming of signal waveforms and devices of this kind are used in many multipurpose signal processors. In order to enable the processing of signal sequences with a high frequency, customary signal processors comprise two data buses so as to enable the formation of a new product during each clock period. Because, moreover, this product contains double the number of bits, i.e. has double the word width, the adder device is also designed for double the word width. However, this represents a comparatively high expenditure. 
     It is an object of the invention to provide a method of the kind set forth which enables the formation of the sum of a chain of products with little expenditure and at the expense of only a slightly reduced speed. 
     This object is achieved in accordance with the invention in that the product produced by each separate multiplication is added to the intermediate result in two steps in that during the first step only the least-significant positions of the product are added to the corresponding positions of the intermediate result, the first partial sum thus formed being temporarily stored, whereas during the second step the remaining, more-significant positions of the product are added to the corresponding remaining positions of the intermediate sum and the carry of the first partial sum, the second partial sum thus formed being temporarily stored, during each step there being supplied another one of the numbers to be directly subsequently multiplied. 
     It is a further object of the invention to provide a device of the kind set forth which enables the formation of the sum of a chain of products with less expenditure and at the expense of only a slightly reduced speed. 
     This object is achieved in accordance with the invention in that the storage device is connected to the first register device via only one data bus for the first number of bits, and that the control device is conceived to operate alternately in a first and a second clock period and to apply, during the first clock period the first number of least-significant bits at the output of the product register and the contents of the second partial sum register to the inputs of the adder device, and to write, at the end of this clock period, one of the first values into the register device and the new partial sum appearing at the output of the adder device into the second partial sum register, and to apply, during the second clock period, the first number of most-significant bits at the output of the product register and the contents of the first partial sum register as well as a temporarily stored carry, to the adder device and to write, at the end of this clock period, one of the second values into the register device and the second partial sum appearing at the output of the adder device, into the first partial sum register as well as to write the product formed by the multiplier device into the product register. 
     Each complete partial sum is thus formed during two clock periods, so that overall the processing speed is halved. However, this requires only a single data bus via which the values to be processed are successively transferred and, moreover, it suffices to use an adder device for only the single word width which successively determines the partial sums during the two clock periods. Because initially only the partial sum is formed from the least significant bits, the carry from the first partial sum is always available for the formation of the second partial sum. Consequently, no rounding errors occur, because all positions present are indeed evaluated, and the exact result can ultimately be extracted from the second partial sum register. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     An embodiment of the invention will be described in detail hereinafter with reference to the drawing. Therein: 
     FIG. 1 shows a block diagram of significant parts of a device in accordance with the invention, and 
     FIG. 2 shows the succession in time of individual values occurring at different locations within the block diagram shown in FIG. 1. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     A control device 10 in FIG. 1 generates two control signals T1 and T2 on the leads 8 and 9, which signals cyclically alternate. On an output 11 the control device 10 also generates addresses for addressing a storage device 12. The connection 11 is shown to be double, because it actually consists of a number of parallel leads via which the bits of an address are transferred in parallel. This also holds for the data connections which are also shown to be double and which also consist of several leads via which the bits of each time one data word are transferred in parallel. 
     The data connection of the storage device 12 which may consist of a plurality of separate memories, including read-only memories, is connected to a data bus 14 whereto, in addition to further devices of a processor (not shown), the two registers 16 and 18 are connected in parallel. Write operations in these registers are controlled by control signals on the leads 8 and 9. 
     The outputs 17 and 19 of the registers 16 and 18, intended to store the factors to be multiplied by one another, are connected to the inputs of a multiplier device 20 which forms, within one clock period, the complete product of the two values supplied via the connections 17 and 19 and which outputs the product via the output 21. This product has double the word width, i.e. double the number of bits of the supplied factors. This is the only location within the device shown in FIG. 1 in which a double word width occurs, and the connection 21 is connected to the input of a product register 22 which is also designed for this double word width. 
     At the output side of the product register 22 there are connected two leads 23 and 29, the lead 23 carrying the most-significant bits whereas the lead 29 carries the least-significant bits, i.e. each lead has the single word width. The connections 23 and 29 lead to a multiplexer 24 which connects, under the control of a control signal on the lead 8, either the connection 23 or the connection 29 to an input 25 of an adder device 26. The other input 35 of the adder device 26 is connected to the output of the second multipliexer 34. 
     The sum output 27 of the adder 26 is connected in parallel to the inputs of two partial sum registers 30 and 32 which are alternately activated for writing via the control leads 8 and 9. The second partial sum register 32 is also provided with a carry memory 28 in which, in parallel with the second sum register, the carry occurring at the output 27a of the adder device 26 is written via the control lead 8. 
     The outputs 31 and 33 of the partial sum registers 30 and 32 lead to the two inputs of the multiplexer 34 which connects, controlled via the control lead 8, either the output 31 together with the output 37 of the carry memory 28 or the output 33 to the second input 35 of the adder device 26. Furthermore, the output 31 carries the desired sum at the end of the processing of the chain of products. 
     However, it is often desirable that the contents of the register 32 can also be read and applied to other elements. 
     The function of the device shown in FIG. 1 will now be described with reference to the time diagram of FIG. 2 in which the numbers preceding the individual lines denote the signals or values on the connections or the contents of the blocks denoted by the relevant references. The device shown inn FIG. 1 serves to determine scalar products, i.e. expressions of the form ##EQU1## The individual values A i  and B i  are present in stored form, because they are required at defined instants. The intermediate sums, arising after the summing of each new product P i  =A i  ·B i , are always temporarily stored, the preceding intermediate sum being erased thereby. The intermediate sum formed after the last product at the same time constitutes the final result. 
     In the time diagram of FIG. 2 it is initially assumed that the first products have already been processed and that the corresponding intermediate sum has been formed. Thus, the instant t 0  at the end of a second clock period T2 represents an arbitrarily selected instant during the processing of the chain of products. At this instant t 0  one factor A i  of the current product P i  to be formed, read from the storage device 12 during this clock period T2, is written into the register 16, i.e. by the ascending signal on the line 8 for the first clock period T1. At the same time the previous product P i-1 , formed in the multiplier device 20, is written into the product register 22. The partial sum registers 30 and 32 will be considered in detail hereinafter. 
     During the clock period T1, subsequent to the instant t 0 , the second value B i  of the product to be formed is read from the storage device 12 and applied to the input of the register 18 via the data bus 14. The signal on the control lead 9, being low during this clock period, controls the multiplexer 24 so that the connection 29, carrying the least-significant bits of the product P i-1 , is coupled to the input 25 of the adder device 26, and at the same time the output 33 of the partial sum register 32 is coupled to the input 35 of the adder device 26, via the multiplexer 34 which is controlled in the same way. The adder device 26 forms the partial sum S L   i-1  during the clock period T1 and outputs it via the output 27 near the end of the clock period T1. 
     At the end of the clock period T1, i.e. at the instant t 1  when the signal on the control lead 8 becomes low and that on the control lead 9 becomes high, the least-significant half of the partial sum thus formed is written into the second sum register 32 and at the same time the carry signal output via the output 27a is written into the carry memory 28. Moreover, the second factor B i  of the product to be formed is written into the register 18. Furthermore, the two multiplexers 24 and 34 are switched over so that now the input 25 of the adder device 26 receives the most-significant bits of the product P i-1  at the output 23 of the product register 22 whose contents have remained the same, and at the same time the input 35 of the adder device 26 receives the more-significant bits, stored in the first partial sum register 30, of the preceding partial sum as well as the carry, output via the output 37, from the carry memory 28, so that the most-significant part of the new intermediate sum is now formed in the adder device 26 and output via the output 27; at the same time the multiplier device 20 forms the next product P i , because both values A i  and B i  are present in the registers 16 and 18. Moreover, the control device 10 addresses the first value A i+x  for the next product P i+x  and applies this value, via the bus 14, inter alia to the register 16. 
     At the end of the clock period T2, i.e. at the instant 12, the control signal on the lead 8 becomes high, so that the value A i+1  is written into the register 16, and at the same time the product P i  output by the multiplier 20 via the output 21 is written into the product register 22; furthermore, the most-significant part of the previous intermediate sum S H   i-1  is written into the first partial sum register 30. The processing of the product P i-1  has thus been completed, and the product P i  then stored in the product register 22 can be further processed. 
     This takes place during the second clock period T1 shown, during which the multiplexer 24 is switched over again applies and the least-significant bits of the product P i  at the output 29 of the product register 22 to the input 25 of the adder device 26. At the same time the other input 35 of the adder device 26 receives the preceding partial sum S L   i-1 , via the multiplexer 34, from the output 33 of the second partial sum register 32, and the new least-significant partial sum S L   i  is formed at the output 27 of the adder device 26 and written into the second partial sum register 32 at the end of the clock period T1, i.e. at the instant t 3 . At the same time the second value B i+1 , read during the clock period T1, is written into the register 18. 
     During the third clock period T2 shown, the next valid product P i+1  is formed at the output 21 of the multiplier 20, and at the same time the most-significant bits from the product register 22 are applied to the input 25 of the adder device 26, the input 35 receiving the most-significant preceding partial sum S H   i-1  from the first partial sum register 30 as well as the carry signal from the carry memory 28, so that the new most-significant partial sum S H   i  is formed at the output 27 of the adder device 26. This partial sum is written into the first partial sum register 30 again at the end of the third clock period T2, shown. 
     This process is cyclically continued until all products of the chain have been calculated and processed by accumulation in the partial sum registers. As is shown in FIG. 2, processing takes place according to the pipeline principle, i.e. during the formation of one product at the same time the preceding partial sum is formed and the values of the next product are supplied. At the start, i.e. upon formation of the first product P 1 , therefore, some preliminary processing steps are required. 
     These steps can be seen from FIG. 2 when i=1 is assumed. This means that prior to the instant t 0  first one value A must be read and written into the register at the instant t 0 . Subsequently, the second value B 1  is read and written into the register 18 at the instant t 1 . Subsequently, the first product P 1  can be formed so as to be written into the product register 22 at the instant t 2 . The product P 1  can then be processed in the described manner; evidently, the partial sum registers 30 and 32 must have been erased during these preceding processing steps, i.e. they must contain the value zero. 
     The sum of a chain of products is thus formed while maintaining complete accuracy, without rounding errors, and requiring only an adder for the single word width.