# US 2020/0394017 A1 · Fast binary counters based on symmetric stacking and methods for same

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0394017 A1
- Document ID: US20200394017A1
- Status: Published application
- Kind: A1
- Application number: 16/610,761
- Filed: 2018-05-04
- Published: 2020-12-17
- Earliest claimed: 2017-05-04
- Assignees: The Research Foundation for The State University of New York
- Applicants: The Research Foundation for The State University of New York
- Inventors: Christopher FRITZ; Adly T. Fam
- Web page: https://patentgrep.com/patent/US20200394017A1

## CPC

- G06F 7/505: in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination
- G06F 7/607: {number-of-ones counters, i.e. devices for counting the number of input lines set to ONE among a plurality of input lines, also called bit counters or parallel counters (for applications thereof, see the relevant places, e.g. G06F7/49, G06F7/5013, G06F7/509, H03M1/00, H03M7/20)}
- G06F 7/48: using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F 7/50: Adding; Subtracting (G06F7/483 - G06F7/491, G06F7/544 - G06F7/556 take precedence)
- G06F 30/327: Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
- G06F 2113/02: Data centres
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

In this paper, binary stackers and counters are presented. In an embodiment, a counter uses 3-bit stacking circuits which group the T bits together, followed by a symmetric method to combine pairs of 3-bit stacks into 6-bit stacks. The bit stacks are then converted to binary counts, producing 6:3 and 7:3 Counter circuits with no XOR gates on the critical path. This avoidance of XOR gates results in faster designs with efficient power and area utilization. In VLSI simulations, the presently-disclosed counters were 30% faster and at consumed at least 20% less power than existing parallel counters. Additionally, using the presently-disclosed counter in existing Counter Based Wallace tree multiplier architectures reduces latency and improves efficiency in terms of power-delay product for 64-bit and 128-bit multipliers.

## Claims

### Claim 1

A method of stacking a 2b-bit binary vector, comprising:
splitting the 2b-bit vector into a first set of b bits, and a second set of b bits, wherein no bits of the 2b-bit vector are used in both the first set and the second set;
stacking the first set such that any bits having a value of ‘1’ occupy the least significant bits;
stacking the second set such that any bits having a value of ‘1’ occupy the most significant bits;
determining, for each bit of the first set and the second set, if a bit of the first set or a corresponding bit of the second set has a value of ‘1’, and setting a corresponding bit of a third set to ‘1’;
determining, for each bit of the first set and the second set, if a bit of the first set and a corresponding bit of the second set has a value of ‘1’, and setting a corresponding bit of a fourth set to ‘1’;
stacking the third set such that any bits having a value of ‘1’ occupy the most significant bits; and
stacking the fourth set such that any bits having a value of ‘1’ occupy the most significant bits.

### Claim 2 (depends on 1)

The method of claim 1, further comprising concatenating the stacked third set and the stacked fourth set to form an 2b-bit stacked output.

### Claim 3 (depends on 1)

The method of claim 1, wherein stacking the first set comprises:
stacking the first set such that any bits having a value of ‘1’ occupy the most significant bits; and
reversing the first set.

### Claim 4

A 2b-bit stacking circuit, comprising:
2b binary inputs, X0, . . . , X2b-1;
a first level of logic circuitry, comprising:
a first b-bit stacker configured to receive inputs X0, . . . , Xb-1 and provide stacked outputs H0, . . . , Hb-1;
a second b-bit stacker configured to receive inputs Xb, . . . , X2b-1 and provide stacked outputs I0, . . . , Ib-1;
a second level of logic circuitry, configured to provide a J vector, where J0=Hb-1+I0, . . . , Jb-1=H0+Ib-1, and a K vector, where K0=Hb-1I0, . . . , Kb-1=H0Ib-1;
a third level of logic circuitry, comprising:
a third b-bit stacker configured to receive inputs J0, . . . , Jb-1 and provide stacked outputs Y0, . . . , Yb-1; and
a fourth b-bit stacker configured to receive inputs K0, . . . , Kb-1 and provide stacked outputs Yb, . . . , Y2b-1.

### Claim 5

A method of counting a 6-bit binary vector, comprising:
splitting the 6-bit vector into a first set of 3 bits, and a second set of 3 bits, wherein no bits of the 6-bit vector are used in both the first set and the second set;
stacking the first set such that any bits having a value of ‘1’ occupy the least significant bits;
stacking the second set such that any bits having a value of ‘1’ occupy the most significant bits;
determining a parity of the 6-bit vector;
determining, for each bit of the first set and the second set, if a bit of the first set and a corresponding bit of the second set has a value of ‘1’, and setting a corresponding bit of a third set to ‘1’;
determine C1 as ‘1’ based on any one of the following:
at least one bit of the first set has a value of ‘1’ and at least one bit of the second set has a value of ‘1’;
all bits of the third set have a value of ‘0’; or
all bits of the first set and all bits of the second set have a value of ‘1’;
determine C2 as ‘1’ based on all bits of the third set having a value of ‘1’; and
providing a count output as C2C1S.

### Claim 6 (depends on 5)

The method of claim 5, wherein determining a parity of the 6-bit vector comprises:
determining a first parity of the first set;
determining a second parity of the second set; and
determining the parity of the 6-bit vector based on the first parity and the second parity.

### Claim 7

A 6:3 counter, comprising:
six inputs, X0, X1, X2, X3, X4, X5;
a first level of logic circuitry, comprising:
a first 3-bit stacker configured to receive inputs X0, X1, and X2, and provide stacked outputs H0, H1, and H2;
a second 3-bit stacker configured to receive inputs X3, X4, and X5, and provide stacked outputs I0, I1, and I2;
a S logic circuit configured to receive H0, H1, H2, I0, I1, and I2 as inputs, and provide output S=He⊕Ie, where He is a parity of the H bits, and Ie is a parity of the I bits;
a K logic circuit configured to receive H0, H1, H2, I0,I1, and I2, and provide outputs K0=H2I0,K1=H1I1, and K2=H0I2;
a C1 logic circuit configured to receive H0, H1, H2, I0, I1, I2, K0, K1, and K2 as inputs, and provide output C1=(H1+I1+H0I0)(K0+K1+K2)+H2I2;
a C2 logic circuit configured to receive K0, K1, and K2 as inputs, and provide output C2=K0+K1+K2; and
wherein C2C1 S is a binary representation of the number of ‘1’ input bits.

### Claim 8 (depends on 7)

A multiplier comprising the 6:3 counter of claim 7.

### Claim 9

A method of counting a 7-bit binary vector, comprising:
splitting the 7-bit vector into a first set of 3 bits, and a second set of 3 bits, and a seventh bit, wherein no bits of the 7-bit vector are used in more than one of the first set, the second set, or the seventh bit;
stacking the first set such that any bits having a value of ‘1’ occupy the least significant bits;
stacking the second set such that any bits having a value of ‘1’ occupy the most significant bits;
determining a parity of the 7-bit vector;
determining, for each bit of the first set and the second set, if a bit of the first set and a corresponding bit of the second set has a value of ‘1’, and setting a corresponding bit of a third set to ‘1’;
determining C1 as ‘1’ based upon the seventh bit has a value of ‘0’ and any one of the following:
at least one bit of the first set has a value of ‘1’ and at least one bit of the second set has a value of ‘1’;
all bits of the third set have a value of ‘0’; or
all bits of the first set and all bits of the second set have a value of ‘1’;
determining C1 as ‘1’ based upon the seventh bit has a value of ‘1’ and any one of the following:
at least one bit and not more than two bits of the first set and the second set has a value of ‘1’;
five bits of the first set and the second set has a value of ‘1’;
determine C2 as ‘1’ based upon one of the following:
the seventh bit having a value of ‘0’ and at least four bits of the first set and the second set have a value of ‘1’; or
the seventh bit having a value of ‘1’ and at least three bits of the first set and the second set have a value of ‘1’; and
providing a count output as C2C1S.
