Patent ID: 6029187
Filing Date: 2000-02-22
Classification: G06F

Abstract:
A multiplication circuit, comprising:means, receiving an M-bit multiplicand and an N-bit multiplier, for forming N M-bit partial products, where M and N are integers greater than 8, each bit of each partial product having a bit-significance corresponding to a specified bit of an (M+N)-bit product; andaddition means for summing said N M-bit partial products such that bits of said partial products having the same bit-significance are added together, wherein said addition means is organized into an architecture that is characterized by a plurality of subarrays forming partial sums and a multistage main array adding said partial sums, said architecture having an asymmetric but non-inherently delay-balanced branching architecture in which a first main array stage receives partial sums from two subarrays and each subsequent main array stage receives partial sums from one previous main array stage and only one corresponding subarray, the subarray for each subsequent main array stage being successively larger than subarrays for previous main array stages to maintain balanced propagation delays for partial sums provided to each main array stage, at least one subarray including a four-to-two compressor circuit therein, each signal propagation path from a first stage of a subarray through subsequent stages of said subarray to a stage of said main array and through subsequent stages of said main array having an identical number of compressor circuits compared to all other signal propagation paths, andeach compressor circuit having four signal inputs connected to outputs from a previous stage and an extra carry input connected to a carry output from a same stage of next lower bit significance, and also having sum and carry signal outputs connected to signal inputs of a subsequent stage and an extra carry output connected to a carry input for a same stage of next higher bit significance, wherein a state of said extra carry output is derived from states of all four of said signal inputs but not from said extra carry input and states of said sum and carry signal outputs are derived from all four of said signal inputs and said extra carry input, said extra carry input operating on a result of operation upon all four signal inputs to derive said sum and carry signal output states, said sum signal output having a state set to 1 if the number of 1's in said four signal inputs and said extra carry input is odd, said sum signal output being set to 0 otherwise, said carry signal output and said extra carry output being both set to 1 if the number of 1's in said four signal inputs and extra carry input is 4 or 5, one and only one of said carry signal output and said extra carry output being set to 1 if the number of 1's in said four signal inputs and extra carry input is 2 or 3, and said carry signal output and said extra carry output being both set to 0 if the number of 1's in said four signal inputs and extra carry input is 0 or 1;a vector merging adder receiving a multibit sum word and a multibit carry word together representing a partial sum from a final main array stage of said addition means, said vector merging adder summing said sum word and carry word to produce said (M+N)-bit product.