Data processing system including means for detecting algorithm execution completion

Claim 2

A data processing system comprising: a memory having a plurality of addressable storage locations, each capable of containing an information item; a data processing unit in communication with said memory for selectively addressing said storage locations whereby selected information items may be retrieved from or stored in said storage locations; and an arithmetic means in communication with said data processing unit whereby information items may be delivered to said arithmetic means from said data processing unit, said arithmetic means capable of performing arithmetic computations upon information items delivered thereto, including the multiplication of a first information item in the form of a binary number representing a multiplicand by a second information item in the form of a binary number representing a multiplier in accordance with a multiplication algorithm which forms a product by recognizing prescribed configurations of binary bits in said multiplier to selectively perform addition, subtraction, and shifting operations, said arithmetic means including first storage means for retaining said multiplicand; second storage means for retaining said multiplier and a partial product during multiplication algorithm operatioNs and for retaining said product at algorithm termination, said second storage means adapted to shift information items contained therein a prescribed number of bit positions in response to shift signals applied thereto; combining means in communication with said first and second storage means whereby signals representing binary numbers stored therein may be transferred therebetween; means in conjunction with said combining means for performing said addition, subtraction and shifting operations on said multiplicand, partial product and multiplier; additional storage means in communication with said second storage means for receiving indicia from said second storage means during said shifting operations; and means for selectively placing a predetermined configuration of binary bits in said second storage means during a selected one of said shifting operations whereby the most significant bit of said multiplier and the least significant bit of said partial product are separated during said multiplication algorithm operations and whereby said predetermined configuration of binary bits in said additional storage means, after a predetermined number of shifting operations, effect the generation of final product binary bits, independently of the number of shifting operations performed when the last of the binary bits of said multiplier have been examined by said arithmetic means.

Claim 3

In a data processing system, an arithmetic unit capable of multiplying a first binary number representing a multiplicand by a second binary number representing a multiplier in accordance with a multiplication algorithm which forms a third binary number representing a product by recognizing prescribed configurations of binary bits in said multiplier to cause said arithmetic unit to selectively perform addition and subtraction operations with respect to a partial product and said multiplicand, and shifting operations with respect to said partial product and said multiplier, the improvement comprising: first storage means for retaining said multiplicand; second storage means for retaining said multiplier and said partial product during said multiplication algorithm and for retaining said product at the termination of said multiplication algorithm, said second storage means adapted to shift information contained therein a prescribed number of bit positions in response to shift signals selectively applied thereto; combining means in communication with said first and second storage means whereby signals representing binary numbers stored therein may be transferred therebetween; means in conjunction with said combining means for performing said addition, subtraction and shifting operations; additional storage means for receiving signals representative of binary bits from said second storage means; connecting means responsive to said shift signals for transferring the binary bits from said second storage means to said additional storage means when said shift signals are applied to said second storage means and said connecting means; means responsive to said shift signals for selectively placing a predetermined pattern of binary bits in said second storage means whereby said partial product is separated from said multiplier during said multiplication algorithm; and detection means in communication with said second and additional storage means for generating said shift signals in response to signals from said second and additional storage means representative of indicia store therein, said detecting means terminating said multiplication algorithm after a predetermined number of shift signals have been generated, said detection means further responsive to signals from said additional storage means representative of the presence of said predetermined pattern of binary bits in said additional storage means whereby the end of said multiplier is detected and the last binary bits of said product are placed into said second storage means upon the detection of said predetermined pattern independently of the termination of saiD multiplication algorithm by said detection means.

Claim 4

In a data processing system, an arithmetic unit capable of multiplying a first binary number representing a multiplicand by a second binary number representing a multiplier in accordance with a multiplication algorithm which forms a third binary number representing a product by recognizing prescribed configurations of binary bits in said multiplier to cause said arithmetic unit to selectively perform addition and subtraction operations with respect to a partial product and said multiplicand, and shifting operations with respect to said partial product and said multiplier, the improvement comprising: first storage means for retaining said multiplicand; second storage means for retaining said multiplier and said partial product during said multiplication algorithm and for retaining said product at the termination of said multiplication algorithm, said second storage means adapted to shift information contained therein a prescribed number of bit positions in response to shift signals selectively applied thereto; combining means in communication with said first and second storage means whereby signals representing binary numbers stored therein may be transferred therebetween; means in conjunction with said combining means for performing said addition, subtraction and shifting operations; additional storage means for receiving signals representative of binary bits from said second storage means; connecting means responsive to said shift signals for transferring the binary bits from said second storage means to said additional storage means when said shift signals are applied to said second storage means and said connecting means; means responsive to said shift signals for selectively placing a predetermined pattern of binary bits in said second storage means whereby said partial product is separated from said multiplier during said multiplication algorithm; and detection means in communication with said second and additional storage means for generating said shift signals in response to signals from said second and additional storage means representative of indicia store therein, said detecting means terminating said multiplication algorithm after a predetermined number of shift signals have been generated, said detection means further responsive to signals from said additional storage means representative of the presence of said predetermined pattern of binary bits in said additional storage means whereby the end of said multiplier is detected and the last binary bits of said product are placed into said second storage means upon the detection of said predetermined pattern independently of the termination of saiD multiplication algorithm by said detection means.

Claim 5

An arithmetic portion of a data processing system for multiplying a first binary number representing a multiplicand by a second binary number representing a multiplier to generate a third binary number representing a product, each of said binary numbers consisting of a number of binary bits, said arithmetic portion comprising: a binary adder for receiving input signals representing binary numbers and for providing output signals in accordance with said input signals; a first storage means for retaining said multiplicand; a second storage means receiving output signals from said adder indicative of a partial product, said second storage means serving to hold said partial product and shift said partial product during the multiplication of said multiplicand by said multiplier; means interconnecting said adder with said first and second storage means whereby signals representing said multiplicand and said partial product may form input signals to said adder; said adder performing addition, subtraction and data transfer operations; first shifting means intermediate said adder and said second storage means whereby output signals from said adder representing said partial product may be transferred from said adder into said second storage means shifted a prescribed number of bit positions; a third storage means; connecting means connecting said second and said third storage means for transferring signals representing selected portions of said partial product; second and third shifting means associated, respectively, with said second and third storage means and for effecting the shifting of binary bit configurations within said second and third storage means for effecting, in conjunction with said connecting means the transfer of said signals representing selected portions of said partial product from said second to said third storage means; means for selectively inserting a prescribed configuration of binary bits into higher order bit positions of said third storage means; and additional storage means for receiving binary bits shifted from said third storage means upon shifting of said third storage means, said third storage means receiving said prescribed configuration of binary bits after successive operations of said second and said third shifting mean; and detection means in communication with said additional storage means for detecting the presence of said prescribed configuration of binary bits in said additional storage means whereby a last binary bit of said product is placed into said third storage means in a manner identical to all previous partial product binary bits and to terminate the multiplication operation.

Claim 6

An arithmetic portion of a data processing system for multiplying a first binary number representing a multiplicand by a second binary number representing a multiplier to generate a third binary number representing a product, each of said binary numbers consisting of a number of binary bits, said arithmetic portion comprising: a binary adder for receiving input signals representing binary numbers and for providing output signals in accordance with said input signals; a first storage means for retaining said multiplicand; a second storage means receiving output signals from said adder indicative of a partial product, said second storage means serving to hold said partial product and shift said partial product during the multiplication of said multiplicand by said multiplier; means interconnecting said adder with said first and second storage means whereby signals representing said multiplicand and said partial product may form input signals to said adder; said adder performing addition, subtraction and data transfer operations; first shifting means intermediate said adder and said second storage means whereby output signals from said adder representing said partial product may be transferred from said adder into said second storage means shifted a prescribed number of bit positions; a third storage means; connecting means connecting said second and said third storage means for transferring signals representing selected portions of said partial product; second and third shifting means associated, respectively, with said second and third storage means and for effecting the shifting of binary bit configurations within said second and third storage means for effecting, in conjunction with said connecting means the transfer of said signals representing selected portions of said partial product from said second to said third storage means; means for selectively inserting a prescribed configuration of binary bits into higher order bit positions of said third storage means; and additional storage means for receiving binary bits shifted from said third storage means upon shifting of said third storage means, said third storage means receiving said prescribed configuration of binary bits after successive operations of said second and said third shifting mean; and detection means in communication with said additional storage means for detecting the presence of said prescribed configuration of binary bits in said additional storage means whereby a last binary bit of said product is placed into said third storage means in a manner identical to all previous partial product binary bits and to terminate the multiplication operation.