Patent GB-1015175-A (GB)
Title: Improved fast multiply system
IPC: G06F7/52
Filed: 1963-04-26
Abstract: 1,015,175. Digital multipliers. SPERRY RAND CORPORATION. April 26, 1963 [May 9, 1962], No. 16449/63. Heading G4A. A binary multiplication circuit of the type in which successive pairs of multiplier digits control additive or subtractive entries of the multiplicand into the partial product has two multiplier registers each having an associated arithmetic circuit, the arrangement being such that two pairs of multiplier digits are effective during each iterative cycle of the multiplication operation. The arrangement shown comprises a multiplicand register 2, first and second multiplier registers 4, 6 and first and second arithmetic circuits 20, 22 (called " half-subtractors "), together with associated circuitry. The arrangement is effective to multiply a multiplicand by a 36-bit multiplier in 9 iterative cycles plus an end-correction cycle. Each " half-subtractor " circuit 20, 22 (Fig. 8, not shown), comprises logic for combining three 36-bit binary words comprising two operands and " borrow " digits from a previous operation applied in parallel and producing " difference " digits applied to respective registers 24, 26 and " borrow " digits applied to respective registers 28, 30. Set-up sequence.-The multiplier is entered into the circuit via the register 2 and transferred directly if positive and after complementing if negative to the Q and Q* registers 4, 6. The multiplicand is then entered into the register 2 and if negative is complemented. The signs of the multiplier and multiplicand are stored by means not shown, to provide an indication of the sign of the product. Multiply sequence.-An iteration counter (Fig. 12, not shown), is first set to binary 1010 (i.e. decimal 10), the count being reduced at each iterative cycle until zero is reached when an output from the iteration counter stops the multiplication operation. At phase 1 of each multiply cycle, Fig. 13b, the " 1st Q sensor " circuit 8 senses the lowest two multiplier digits and according to these are 00, 01, 10, 11, either does nothing; gates the multiplicand directly from the register 2 to an " X* " register 16; gates the multiplicand left shifted by one place to the X* register 16; or gates the complement of the multiplicand to the X* register 16 and also produces a " carry " to the " 2nd Q sensor " circuit 10. Subsequently, at phase 3 of each multiply cycle the contents of the X* register 16 is added (by complementation and halfsubtraction) to the contents of the 2nd difference digit storage register (the A register) 26, the contents of the 2nd borrow digit storage register (the B register) 30 being applied shifted left one place and subtracted from the result, the final result being a set of " difference " and " borrow " digits which are stored in respective registers 24, 28. Also at phase 3, the second Q sensor circuit 10 is effective in accordance with the next two higher order multiplier digits and with any " carry " C1 from the sensor circuit 8 to gate the multiplicand directly or left shifted, or the complement of the multiplicand, to an " XS " register 18, whence it is applied in complement form together with the A* difference digits shifted two places to the right and the B* borrow digits shifted one place to the right, from the registers 24, 28. At phase 1 of the next cycle, the output of the halfsubtract circuit 22 is gated and entered two places to the right, as difference and borrow digits to the A and B registers 29, 30. For each half-subtract operation in the circuits 20, 22, the borrow digits from the respective registers 28, 30 are shifted one place to the left before application to the circuits 20, 22. The normal borrow propagation time if the borrows were added in at each partial product accumulation is thus avoided. The contents of the highest stage A*36 of the A* register 24 is applied to both stages 35 and 34 of the AB half-subtractor 22. In order to provide the necessary " sign extension " when a negative number is shifted to the right, " forced end borrow " circuits 40, 42 are provided. The circuit 40 is conditioned each time that zero or a positive multiple of the multiplicand is to be added to the accumulated partial product in the A*B* half-subtractor 20 since it can be shown that under these conditions, the new partial product is negative and will require " sign extension " when shifted, the output of the circuit 40 being applied to stages A*36 and B*36 to store the anticipated negative sign, and the output of the circuit 42 being applied to stages A35, A34 and B34. A full subtractor circuit 32 receives in each cycle the two lowest order difference digits from the register 24 and various borrow digits and effects a full subtraction thereon to produce two product digits and a borrow digit. The product digits are stored temporarily in a buffer 36 and when the contents of the Q* multiplier register 6 are transferred with a right shift of four places to the Q multiplier register 4, the digits in the buffer 36 are entered into positions Q33 and Q34. The borrow digit from the full subtractor 32 is applied to a full subtractor 34. The borrow digits applied to the full subtractor 32 are firstly from the lowest order B*00 of the B* register 28, secondly from the forced end borrow circuit 40 and thirdly from the 2nd full subtractor buffer 38. The full subtractor 34 alternates with the full subtractor 32 in producing pairs of product digits, such digits from the subtractor 34 being transferred to the Q* multiplier register 6. When nine iterative cycles have been completed, all 36 multiplier digits have been sensed, and 36 product digits formed, the remaining final accumulated partial product being stored as a series of difference and borrow digits in the A and B registers 26, 30. During the end-correction cycle, these digits are applied to a " borrow pyramid and main adder " circuit 44 to produce an output representing the sign of the product and its 35 high order digits, this result being transferred to the A register, the 36 low order digits of the product being in the Q* register.