Array multiplier adapted for tiled layout by silicon compiler

A digital multiplier constructed along the surface of a monolithic integrated circuit die, which surface is bounded by four substantially straight sides of said monolithic integrated circuit, a first and a third of which four sides are parallel to each other, a second and a fourth of which four sides are parallel to each other and perpendicular to the first and third sides, said digital multiplier constructed as an array of chunks each for multiplying an N-bit multiplicand signal segment by a 2M-bit multiplier signal segment, M and N being respective positive integers that may be the same or may differ from each other, M*N being the product of the integers M and N, the bits of said multiplicand signal segment supplied to each chunk being identified by respective ones of the consecutive ordinal numbers zeroeth through (N-1).sup.th assigned in order of ascending significance, each chunk of said digital mutiplier comprising:

• means for appending a bit as least significant bit to said 2M-bit multiplier signal segment to form an extended multiplier signal segment;
• a plurality M in number of Booth encoder cells arranged in a column extending along the surface of said monolithic integrated circuit die in a direction parallel to its first side, each Booth encoder cell responding to three bits of said extended multiplier signal segment to generate respective C0 and C1 and C2 code bits, said Booth encoder cells being identified by respective ones of the consecutive even ordinal numbers zeroeth through 2(M-1).sup.th, each said Booth encoder cell identified by a higher ordinal number encoding bits of said extended multiplier signal segment of signifiance equal or greater than the bits encoded by said encoder identified by next lower ordinal number;
• respective zeroeth and first and second Booth-code lines extending from each said Booth encoder cell along the surface of said monolithic integrated circuit die in a direction parallel to its second and fourth sides, for applying the C0 and C1 and C2 code bits from that said Booth encoder cell;
• M*N Booth decoder/adder cells, a respective row of N said Booth decoder/adder cells associated with each said Booth encoder cell being identified by the same ordinal number as said Booth encoder cell with which it is associated, being located along said zeroeth and first and second Booth-code lines extending from said Booth encoder cell with which it is associated, and connecting from said zeroeth and first and second Booth-code lines, the N said Booth decoder/adder cells in each row being identified by respective ones of the consecutive ordinal numbers zeroeth through (N-1).sup.th assigned in order of the serial locations of each N said Booth decoder/adder cells within a said row, each Booth decoder/adder circuit receiving as an input signal thereto the bit of said multiplicand signal segment identified by a corresponding ordinal number as supplied thereto from a respective multiplicand bit bus extending in said first direction, each Booth decoder/adder cell capable of receiving first and second summand bits and a carry-in bit, each Booth decoder/adder cell capable of generating a sum bit, a first carry-out bit of twice the significance of its sum bit and a second carry-out bit;
• a plurality 2M in number of adder cells arranged in a column paralleling said column of M Booth encoder cells, each adder cell capable of receiving first and second summand bits and a carry-in bit, each adder cell capable of generating a sum bit and a carry-out bit of twice the significance of its sum bit, said adder cells identified within their column by consecutive ordinal numbers zeroeth through (2M-1).sup.th ;
• a plurality N in number of further adder cells arranged in a row extending along the surface of said monolithic integrated circuit die in a direction parallel to its first side, each further adder cell capable of receiving first and second summand bits and a carry-in bit, each further adder cell capable of generating a sum bit and a carry-out bit of twice the significance of its sum bit, said further adder cells identified within their row by consecutive ordinal numbers zeroeth through (N-1).sup.th ;
• means for applying the complement of the respective C0 code bit generated by each of said zeroeth through 2(M-1).sup.th Booth encoder cells as the first summand bit of the adder cell in said column of adder cells that is identified by the same ordinal number as the Booth encoder cell generating that C0 code bit;
• electrical connections within each said row for applying the second carry-out bit of each of said zeroeth through (N-2).sup.th Booth decoder/adder cells as the carry-in bit of the Booth decoder/adder cell with next higher ordinal number;
• and
• a respective electrical connection for applying the first carry-out bit of each of said first through (N-1).sup.th Booth decoder/adder cells in each said row except said 2(M-1).sup.th row, as the first summand bit of said Booth decoder/adder cell that is identified by ordinal number next lower than the ordinal number of the Booth decoder/adder cell supplying its first carry-out bit thereto and that is located in said row identified by the ordinal number two higher than the row of the Booth decoder/adder cell supplying its first carry-out bit thereto;
• a respective electrical connection for applying the respective sum bit of each of said second through (N-1).sup.th Booth decoder/adder cells in each said row except said 2(M-1).sup.th row, as the second summand bit to said Booth decoder/adder cell that is identified by ordinal number two lower than the ordinal number of the Booth decoder/adder cell supplying its sum bit thereto and that is located in said row identified by the ordinal number two higher than the row of the Booth decoder/adder cell supplying its sum bit thereto;
• a respective electrical connection for applying the sum bit of said zeroeth Booth decoder/adder cell in each said row, as the second summand bit of said adder cell in said column of adder cells that is identified by the same ordinal number as that identifying the row in which said zeroeth Booth decoder/adder cell is located;
• a respective electrical connection for applying the first carry-out bit of said zeroeth Booth decoder/adder cell in each said row, as the first summand bit of said adder cell in said column of adder cells that is identified by the ordinal number one higher than that identifying the row in which said zeroeth Booth decoder/adder cell is located;
• a respective electrical connection for applying the respective sum bit of said first Booth decoder/adder cell in each said row, as the second summand bit of said adder cell in said column of adder cells that is identified by the ordinal number one higher than that identifying the row in which said first Booth decoder/adder cell is located;
• in said column of zeroeth through (2M-1).sup.th adder cells, a respective electrical connection for applying the respective carry-out bit of each of said zeroeth through 2(M-1).sup.th adder cells as the respective carry-in bit of the one of said first through (2M-1).sup.th adder cells identified by next higher ordinal number;
• in said row of zeroeth through (N-1).sup.th further adder cells, a respective electrical connection for applying the respective carry-out bit of each of said zeroeth through (N-2).sup.th further adder cells as the respective carry-in bit of the one of said first through (N-2).sup.th further adder cells identified by next higher ordinal number;
• a first control line for receiving a ONE indicative that said multiplier chunk is on a side of an array of similar multiplier chunks such that its first side is not adjoined by the third side of another multiplier chunk;
• a second control line for receiving a ONE indicative that said multiplier chunk is on a side of an array of similar multiplier chunks such that its second side is not adjoined by the fourth side of another multiplier chunk;
• a third control line for receiving a ONE indicative that said multiplier chunk is on a side of an array of similar multiplier chunks such that its third side is not adjoined by the first side of another multiplier chunk;
• a latch command line from which all hereinafter claimed latch cells receive respective latch instructions;
• respective latch cells for temporarily storing the first and second summand bits for said (N- 1).sup.th further adder cell in said row of further adder cells;
• a respective latch cell for temporarily storing the second summand bit for said (N-2).sup.th further adder cell in said row of further adder cells;
• a respective latch cell for applying the first carry-out bit of each of said first through (N-1).sup.th Booth decoder/adder cells in said 2(M-1).sup.th row, as the first summand bit of said further adder cell in said row of further adder cells that is identified by the ordinal number next lower than said Booth decoder/adder cell supplying its first carry-out bit thereto;
• a respective latch cell for applying the respective sum bit of each of said second through (N-1).sup.th Booth decoder/adder cells in said 2(M-1).sup.th row, as the second summand bit of said further adder cell in said row of further adder cells that is identified by the ordinal number two lower than said Booth decoder/adder cell supplying its sum bit thereto;
• a respective latch cell for latching the most significant bit of said extended multiplier signal segment;
• a respective latch cell for latching the carry-out bit of said (2M-1).sup.th adder cell in said column of adder cells;
• a plurality of two-input multiplexer cells respectively identified by consecutive ordinal numbers zeroeth through 2M.sup.th, ones of said multiplexer cells identified by even ordinal numbers less than 2M.sup.th being connected for selecting the carry-in bit of said zeroeth Booth decoder/adder cell for said row identified by the same ordinal number, each of said multiplexer cells identified by even ordinal numbers less than 2M.sup.th responding to said first control signal bit being ONE to select the carry-in bit from the zeroeth Booth-code line extending from said Booth encoder cell identified by the same ordinal number, each of said multiplexer cells identified by even ordinal numbers less than 2M.sup.th responding to said first control signal bit being ZERO to select the second-carry-out bit from said (N-1).sup.th Booth decoder/adder cell located in any other multiplier chunk having its third side adjoining the first side of said multiplier chunk being specifically described in this recitation and more specifically located in said row identified by the same ordinal number as that said multiplexer cell, ones of said multiplexer cells identified by odd ordinal numbers less than 2(M-1).sup.th being connected for selecting the second summand bit of said (N-2).sup.th Booth decoder/adder cell for said row identified by the next higher ordinal number, each of said multiplexer cells identified by odd ordinal numbers less than 2(M-1).sup.th responding to said third control signal bit being ONE to select the second carry-out bit from said (N-1).sup. th Booth decoder/adder cell in said row identified by the next lower ordinal number, each of said multiplexer cells identified by odd ordinal numbers less than 2(M-1).sup.th responding to said third control signal bit being ZERO to select the sum bit of the zeroeth Booth decoder/adder cell located in any other multiplier chunk having its first side adjoining the third side of said multiplier chunk being specifically described in this recitation and more specifically located in its row identified by ordinal number one lower than said multiplexer cell, said (2M-1).sup.th multiplexer cell being connected for selecting to its respective latch cell the second summand bit of said (N-2).sup.th further adder cell in said row of further adder cells, said (2M-1).sup.th multiplexer cell responding to said third control signal bit being ONE to select the second-carry-out bit from said (N-1).sup.th Booth decoder/adder cell in said 2(M-1).sup.th row, and said (2M-1).sup.th multiplexer cell responding to said third control signal bit being ZERO to select the sum bit of the zeroeth Booth decoder/adder cell located in any other multiplier chunk having its first side adjoining the third side of said multiplier chunk being specifically described in this recitation and more specifically located in its 2(M-1).sup.th row, said 2M.sup.th multiplexer cell being connected for selecting the carry-in bit of said zeroeth further adder cell, said 2M.sup.th multiplexer cell responding to said first control signal bit being ONE to select a carry-out bit from said (2M-1).sup.th adder cell as stored in said respective latch cell to be the carry-in bit of said zeroeth further adder cell, and said 2M.sup.th multiplexer cell responding to said first control signal bit being ZERO to select a carry-out bit from the (N-1).sup.th further adder cell of any other multiplier chunk having its third side adjoining the first side of said multiplier chunk being specifically described in this recitation;
• a plurality of two-input further multiplexer cells respectively identified by consecutive ordinal numbers zeroeth through (N-1).sup.th, each said further multiplexer cell arranged for selecting the multiplicand bit for each of said Booth decoder/adder cells identified by the same ordinal number, each said further multiplexer cell responding to said second control signal bit being ONE to select the multiplicand bit for each of said Booth decoder/adder cells identified by the same ordinal number as said further multiplexer cell as supplied to a respective bond pad disposed along the surface of said monolithic integrated circuit die, and each said further multiplexer cell responding to said second control signal bit being ZERO to select the multiplicand bit for each of said Booth decoder/adder cells identified by the same ordinal number as said further multiplexer cell as supplied to any other multiplier chunk having its fourth side adjoining the second side of said multiplier chunk being specifically described in this recitation and as delayed by a respective latch cell;
• an AND gate having a respective output connection for supplying the least significant bit appended to said 2M-bit multiplier to form an extended multiplier signal segment, having a respective first input connection to which the logical complement of said second control signal bit is applied, and having a respective second input connection to which the most significant bit of any next less significant segment of the same multiplier signal is applied as delayed by a respective latch cell;
• a plurality of two-input AND gates having respective output connections for supplying the respective first summand bits for said Booth decoder/adder cells located in said zeroeth row, having respective first input connections to which the logical complement of said second control signal bit is applied, and having respective second input connections for receiving a first of the sum and carry-out bits, as delayed by respective latch cells, from respective ones of further adder cells in any other multiplier chunk having its fourth side adjoining the second side of said multiplier chunk being specifically described in this recitation;
• a plurality of two-input AND gates having respective output connections for supplying the respective first summand bits for each of said (N-1).sup.th Booth decoder/adder cells located in rows other than said zeroeth row, having respective first input connections to which the logical complement of said third control signal bit is applied, and having respective second input connections for receiving first carry-out bits from respective ones of zeroeth Booth decoder/adder cells located in any other multiplier chunk having its first side adjoining the third side of said multiplier chunk being specifically described in this recitation and more specifically located in its rows identified by ordinal numbers two lower than the rows in which said (N-1).sup.th Booth decoder/adder cells supplied respective second summand bits are located;
• an AND gate having a respective output connection for supplying the first summand bit for said (N-1).sup.th further adder cell in said row of further adder cells, having a respective first input connection to which the logical complement of said third control signal bit is applied, and having a respective second input connection for receiving the carry-out bit from the zeroeth Booth decoder/adder cell in the 2(M-1).sup.th row of any other multiplier chunk having its third side adjoining the first side of said multiplier chunk being specifically described in this recitation;
• an OR gate having a respective output connection for supplying the carry-in bit to said zeroeth adder cell in said column of adder cells, having a respective first input connection to which said second control signal bit is applied, and having a respective second input connection for receiving the carry-out bit, as delayed by a respective latch cell, from the (2M-1).sup.th adder cell in any other multiplier chunk having its fourth side adjoining the second side of said multiplier chunk being specifically described in this recitation;
• a plurality of two-input OR gates having respective output connections for supplying the respective second summand bits for each of said Booth decoder/adder cells located in said zeroeth row, having respective first input connections to which said second control signal bit is applied, and having respective second input connections for receiving a second of the sum and carry-out bits, as delayed by a respective latch cell, from respective ones of further adder cells in any other multiplier chunk having its fourth side adjoining the second side of said multiplier chunk being specifically described in this recitation;
• a plurality of two-input OR gates having respective output connections for supplying the respective second summand bits for each of said (N-1).sup.th Booth decoder/adder cells located in rows other than said zeroeth row, having respective first input connections to which said third control signal bit is applied, and having respective second input connections for receiving sum bits from first Booth decoder/adder cells located in any other multiplier chunk having its first side adjoining the third side of said multiplier chunk being specifically described in this recitation and more specifically located in its rows identified by ordinal numbers one lower than the rows in which said (N-1).sup.th Booth decoder/adder cells supplied respective second summand bits are located;
• and
• an OR gate having a respective output connection for supplying the second summand bit for said (N-1).sup.th further adder cell in said row of further adder cells, having a respective first input connection to which said third control signal bit is applied, and having a respective second input connection for receiving the sum bit from the first Booth decoder/adder cell in the 2(M-1).sup.th row of any other multiplier chunk having its third side adjoining the first side of said multiplier chunk being specifically described in this recitation.

A digital multiplier constructed along the surface of a monolithic integrated circuit, said digital multiplier for multiplying N-bit multiplicands by 2M-bit multipliers, M and N being respective positive integers that may be the same or may differ from each other, M*N being the product of the integers M and N the bits of said multiplicand being identified by respective ones of the consecutive ordinal numbers zeroeth through (N-1).sup.th assigned in order of ascending significance, said digital mutiplier comprising:

• means for appending a bit as least significant bit to said 2M-bit multiplier to form an extended multiplier;
• a plurality M in number of Booth encoder cells arranged in a column extending in a first direction along the surface of said monolithic integrated circuit die, each Booth encoder cell responding to three bits of said extended multiplier to generate respective C0 and C1 and C2 code bits, said Booth encoder cells being identified by respective ones of the consecutive even ordinal numbers zeroeth through 2(M-1).sup.th, each said Booth encoder cell identified by a higher ordinal number encoding bits of said extended multiplier of signifiance equal to or greater than the bits encoded by said encoder identified by next lower ordinal number;
• respective zeroeth and first and second Booth-code lines extending from each said Booth encoder cell in a second direction along the surface of said monolithic integrated circuit die perpendicular to said first direction, for applying the C0 and C1 and C2 code bits from that said Booth encoder cell;
• M*N Booth decoder/adder cells, a respective row of N said Booth decoder/adder cells associated with each said Booth encoder cell being identified by the same ordinal number as said Booth encoder cell with which it is associated, being located along said zeroeth and first and second Booth-code lines extending from said Booth encoder cell with which it is associated, and connecting from said zeroeth and first and second Booth-code lines, the N said Booth decoder/adder cells in each row being identified by respective ones of the consecutive ordinal numbers zeroeth through (N-1).sup.th assigned in order of the serial locations of each of said Booth decoder/adder cells within a said row, each Booth decoder/adder circuit receiving as an input signal thereto the bit of said multiplicand identified by a corresponding ordinal number as supplied thereto from a respective multiplicand bit bus extending in said first direction, each Booth decoder/adder cell capable of receiving first and second summand bits and a carry-in bit, each Booth decoder/adder cell capable of generating a sum bit, a first carry-out bit of twice the significance of its sum bit and a second carry-out bit;
• a plurality of functional cells connected as a carry-select final adder for combining the first carry-out and sum bits of said zeroeth Booth decoder/adder cells in each of said zeroeth through 2(M-2).sup.th rows, the sum bits of said first Booth decoder/adder cells in each of said zeroeth through 2(M-2).sup.th rows, the complement of the C0 signal generated by each Booth encoder cell, and the sum and first carry out bits of said zeroeth through (N-1).sup.th Booth decoder/adder cells in said 2(M-1).sup.th row;
• and
• electrical connections of said cells for completing said digital multiplier.