# US 6,729,168 B2 · Circuit for determining the number of logical one values on a data bus

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

- Number: US 6,729,168 B2
- Document ID: US6729168B2
- Status: Granted
- Kind: B2
- Application number: 09/733,661
- Filed: 2000-12-08
- Published: 2002-06-13
- Granted: 2004-05-04
- Earliest claimed: 2000-12-08
- Assignees: STMicroelectronics S.r.l.
- Inventors: Razak Hossain
- Web page: https://patentgrep.com/patent/US6729168B2

## CPC

- 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)}
- Y10T 70/577: Locked stationary
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10T: TECHNICAL SUBJECTS COVERED BY FORMER US CLASSIFICATION

## Abstract

There is disclosed a circuit for determining the number of Logic 1 bits in a group of N data bits. The circuit comprises: 1) an input stage of 4:3 carry-save adders, each of the 4:3 carry-save adders receiving four of the N data bits on four input lines and generating three sum bits (S2, S1, S0) equal to a total number of Logic 1 bits on the four input lines, wherein the three sum bits have bit weights of S2=4, S1=2 and S0=1, respectively; 2) a first intermediate stage of 4:2 carry-save adders, each of the first intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of the S2 sum bits, the S1 sum bits, and the S0 sum bits and generating therefrom a carry-out (COUT) bit, a carry (C) bit and a sum (S) bit; and 3) a carry-propagate adder having a first input channel and a second input channel coupled to the first intermediate stage 4:2 carry-save adders and capable of generating a binary result equal to a total number of Logic 1 bits in the group of N data bits.

## Claims

### Claim 1

A circuit for determining the number of Logic 1 bits in a group of N data bits comprising:
an input stage of 4:3 carry-save adders, each of said 4:3 carry-save adders receiving four of said N data bits on four input lines and generating three sum bits (S2, S1, S0) equal to a total number of Logic 1 bits on said four input lines, wherein said three sum bits have bit weights of S2=4, S1=2 and S0=1, respectively;
a first intermediate stage of 4:2 carry-save adders, each of said first intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said S2 sum bits, said S1 sum bits, and said S0 sum bits and generating therefrom a carry-out (COUT) bit, a carry (C) bit and a sum (S) bit; and
a carry-propagate adder having a first input channel and a second input channel coupled to said first intermediate stage 4:2 carry-save adders and capable of generating a binary result equal to a total number of Logic 1 bits in said group of N data bits.

### Claim 2 (depends on 1)

The circuit for determining the number of Logic 1 bits as set forth in claim 1 wherein N equals 16 and said input stage comprises four 4:3 carry-save adders.

### Claim 3 (depends on 2)

The circuit for determining the number of Logic 1 bits as set forth in claim 2 wherein said intermediate stage comprises three 4:2 carry-save adders.

### Claim 4 (depends on 1)

The circuit for determining the number of Logic 1 bits as set forth in claim 1 wherein N equals 32 and said input stage comprises eight 4:3 carry-save adders.

### Claim 5 (depends on 4)

The circuit for determining the number of Logic 1 bits as set forth in claim 4 further comprising a second intermediate stage of 4:2 carry-save adders, each of said second intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said COUT bits, said C-bits, and said S-bits from said first intermediate stage 4:2 carry-save adders.

### Claim 6

A circuit for determining the number of Logic 1 bits in a group of N data bits comprising:
an input stage of 6:3 carry-save adders, each of said 6:3 carry-save adders receiving six of said N data bits on six input lines and generating three sum bits (S2, S1, S0) equal to a total number of Logic 1 bits on said six input lines, wherein said three sum bits have bit weights of S2=4, S1=2 and S0=1, respectively;
a first intermediate stage of 4:2 carry-save adders, each of said first intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said S2 sum bits, said S1 sum bits, and said S0 sum bits and generating therefrom a carry-out (COUT) bit, a carry (C) bit and a sum (S) bit; and
a carry-propagate adder having a first input channel and a second input channel coupled to said first intermediate stage 4:2 carry-save adders and capable of generating a binary result equal to a total number of Logic 1 bits in said group of N data bits.

### Claim 7 (depends on 6)

The circuit for determining the number of Logic 1 bits as set forth in claim 6 wherein N equals 16 and said input stage comprises three 6:3 carry-save adders.

### Claim 8 (depends on 7)

The circuit for determining the number of Logic 1 bits as set forth in claim 7 wherein said intermediate stage comprises three 4:2 carry-save adders.

### Claim 9 (depends on 6)

The circuit for determining the number of Logic 1 bits as set forth in claim 6 wherein N equals 32 and said input stage comprises six 6:3 carry-save adders.

### Claim 10 (depends on 9)

The circuit for determining the number of Logic 1 bits as set forth in claim 9 further comprising a second intermediate stage of 4:2 carry-save adders, each of said second intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said COUT bits, said C-bits, and said S-bits from said first intermediate stage 4:2 carry-save adders.

### Claim 11

A circuit for determining the number of Logic 1 bits in a group of N data bits comprising:
an input stage of 8:4 carry-save adders, each of said 8:4 carry-save adders receiving eight of said N data bits on eight input lines and generating four sum bits (S3, S2, S1, S0) equal to a total number of Logic 1 bits on said eight input lines, wherein said four sum bits have bit weights of S3=8, S2=4, S1=2 and S0=4, respectively;
a first intermediate stage of 4.2 carry-save adders, each of said first intermediate stage 4.2 carry-save adders having four input lines for receiving selected ones of said S3 sum bits, said S2 sum bits, said S1 sum bits, and said S0 sum bits and generating therefrom a carry-out (COUT) bit, a carry (C) bit and a sum (S) bit; and
a carry-propagate adder having a first input channel and a second input channel coupled to said first intermediate stage 4:2 carry-save adders and capable of generating a binary result equal to a total number of Logic 1 bits in said group of N data bits.

### Claim 12 (depends on 11)

The circuit for determining the number of Logic 1 bits as set forth in claim 11 wherein N equals 16 and said input stage comprises two 8:4 carry-save adders.

### Claim 13 (depends on 12)

The circuit for determining the number of Logic 1 bits as set forth in claim 12 wherein said intermediate stage comprises two 4:2 carry-save adders.

### Claim 14 (depends on 11)

The circuit for determining the number of Logic 1 bits as set forth in claim 11 wherein N equals 32 and said input stage comprises four 8:4 carry-save adders.

### Claim 15 (depends on 14)

The circuit for determining the number of Logic 1 bits as set forth in claim 14 comprising a second intermediate stage of 4:2 carry-save adders, each of said second intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said COUT bits, said C-bits, and said S-bits from said first intermediate stage 4:2 carry-save adders.

### Claim 16

A data processor comprising:
an instruction execution pipeline comprising N processing stages, each of said N processing stages capable of performing one of a plurality of execution steps associated with a pending instruction being executed by said instruction execution pipeline, wherein at least one of said N processing stages comprises a counting circuit for determining the number of Logic 1 bits in one of a N-bit data bus and a N-bit register in said data processor, said counting circuit comprising:
an input stage of 4:3 carry-save adders, each of said 4.3 carry-save adders receiving four of said N data bits on four input lines and generating three sum bits (S2, S1, S0) equal to a total number of Logic 1 bits on said four input lines, wherein said three sum bits have bit weights of S2=4, S1=2 and S0=1, respectively;
a first intermediate stage of 4:2 carry-save adders, each of said first intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said S2 sum bits, said S1 sum bits, and said S0 sum bits and generating therefrom a carry-out (COUT) bit, a carry (C) bit and a sum (S) bit; and
a carry-propagate adder having a first input channel and a second input channel coupled to said first intermediate stage 4:2 carry-save adders and capable of generating a binary result equal to a total number of Logic 1 bits in said group of N data bits.

### Claim 17 (depends on 16)

The data processor as set forth in claim 16 wherein N equals 16 and said input stage comprises four 4:3 carry-save adders.

### Claim 18 (depends on 17)

The data processor as set forth in claim 17 wherein said intermediate stage comprises three 4:2 carry-save adders.

### Claim 19 (depends on 16)

The data processor as set forth in claim 16 wherein N equals 32 and said input stage comprises eight 4:3 carry-save adders.

### Claim 20 (depends on 19)

The data processor as set forth in claim 19 further comprising a second intermediate stage of 4:2 carry-save adders, each of said second intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said COUT bits, said C-bits, and said S-bits from said first intermediate stage 4:2 carry-save adders.

### Claim 21

A circuit for determining the number of Logic 1 bits in a group of N data bits comprising:
an input stage of 4:3 carry-save adders, each of said 4:3 carry-save adders receiving four of said N data bits on four input lines and generating three sum bits (S2, S1, S0) equal to a total number of Logic 1 bits on said four input lines, wherein said three sum bits have bit weights of S2=4, S1=2 and S0=1, respectively;
a first intermediate stage of compressors, each of said first intermediate stage compressors receiving selected ones of said S2 sum bits, said S1 sum bits, and said S0 sum bits and generating therefrom a reduced number of output bits equal to a total number of Logic 1 bits on said selected S2 sum bits, said selected S1 sum bits, and selected S0 sum bits; and
a carry-propagate adder having a first input channel and a second input channel coupled to said first intermediate stage compressors and capable of generating a binary result equal to a total number of Logic 1 bits in said group of N data bits.

### Claim 22

A circuit for determining the number of Logic 1 bits in a group of N data bits comprising:
an input stage of 6:3 carry-save adders, each of said 6:3 carry-save adders receiving six of said N data bits on six input lines and generating three sum bits (S2, S1, S0) equal to a total number of Logic 1 bits on said six input lines, wherein said three sum bits have bit weights of S2=4, S1=2 and S0=1, respectively;
a first intermediate stage of compressors, each of said first intermediate stage compressors receiving selected ones of said S2 sum bits, said S1 sum bits, and said S0 sum bits and generating therefrom a reduced number of output bits equal to a total number of Logic 1 bits on said selected S2 bits, said selected S1 bits, and said selected S0 bits; and
a carry-propagate adder having a first input channel and a second input channel coupled to said first intermediate stage compressors and capable of generating a binary result equal to a total number of Logic 1 bits in said group of N data bits.

### Claim 23

A circuit for determining the number of Logic 1 bits in a group of N data bits comprising:
an input stage of 8:4 carry-save adders, each of said 8:4 carry-save adders receiving eight of said N data bits on eight input lines and generating four sum bits (S3, S2, S1, S0) equal to a total number of Logic 1 bits on said eight input lines, wherein said four sum bits have bit weights of S3=8, S2=4, S1=2 and S0=1, respectively;
a first intermediate stage of compressors, each of said first intermediate stage compressors receiving selected ones of said S3 sum bits, said S2 sum bits, said S1 sum bits, and said S0 sum bits and generating therefrom a reduced number of output bits equal to a total number of Logic 1 bits on said selected S3 bits, said selected S2 bits, said selected S1 bits, and said selected S0 bits; and
a carry-propagate adder having a first input channel and a second input channel coupled to said first intermediate stage compressors and capable of generating a binary result equal to a total number of Logic 1 bits in said group of N data bits.

### Claim 24

A circuit for determining the number of Logic 1 bits in a group of 32 data bits comprising:
an input stage comprising eight 4:3 carry-save adders, each of said 4:3 carry-save adders receiving four of said N data bits on four input lines and generating three sum bits (S2, S1, S0) equal to a total number of Logic 1 bits on said four input lines, wherein said three sum bits have bit weights of S2=4, S1=2 and S0=1, respectively;
a first intermediate stage of 4:2 carry-save adders, each of said first intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said S2 sum bits, said S1 sum bits, and said S0 sum bits and generating therefrom a carry-out (COUT) bit, a carry (C) bit and a sum (S) bit;
a second intermediate stage of 4:2 carry-save adders, each of said second intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said COUT bits, said C-bits, and said S-bits from said first intermediate stage 4:2 carry-save adders; and
a carry-propagate adder having a first input channel and a second input channel coupled to said second intermediate stage 4:2 carry-save adders and capable of generating a binary result equal to a total number of Logic 1 bits in said group of 32 data bits.

### Claim 25

A circuit for determining the number of Logic 1 bits in a group of 32 data bits comprising:
an input stage comprising six 6:3 carry-save adders, each of said 6:3 carry-save adders receiving six of said N data bits on six input lines and generating three sum bits (S2, S1, S0) equal to a total number of Logic 1 bits on said six input lines, wherein said three sum bits have bit weights of S2=4, S1=2 and S0=1, respectively;
a first intermediate stage of 4:2 carry-save adders, each of said first intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said S2 sum bits, said S1 sum bits, and said S0 sum bits and generating therefrom a carry-out (COUT) bit, a carry (C) bit and a sum (S) bit;
a second intermediate stage of 4:2 carry-save adders, each of said second intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said COUT bits, said C-bits, and said S-bits from said first intermediate stage 4:2 carry-save adders; and
a carry-propagate adder having a first input channel and a second input channel coupled to said second intermediate stage 4:2 carry-save adders and capable of generating a binary result equal to a total number of Logic 1 bits in said group of 32 data bits.

### Claim 26

A circuit for determining the number of Logic 1 bits in a group of 32 data bits comprising:
an input stage comprising four 8:4 carry-save adders, each of said 8:4 carry-save adders receiving eight of said N data bits on eight input lines and generating four sum bits (S3, S2, S1, S0) equal to a total number of Logic 1 bits on said eight input lines, wherein said four sum bits have bit weights of S3=8, S2=4, S1=2 and S0=1, respectively;
a first intermediate stage of 4:2 carry-save adders, each of said first intermediate stage 4.2 carry-save adders having four input lines for receiving selected ones of said S3 sum bits, said S2 sum bits, said S1 sum bits, and said S0 sum bits and generating therefrom a carry-out (COUT) bit, a carry (C) bit and a sum (S) bit;
a second intermediate stage of 4:2 carry-save adders, each of said second intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said COUT bits, said C-bits, and said S-bits from said first intermediate stage 4:2 carry-save adders; and
a carry-propagate adder having a first input channel and a second input channel coupled to said second intermediate stage 4:2 carry-save adders and capable of generating a binary result equal to a total number of Logic 1 bits in said group of 32 data bits.

### Claim 27

A data processor comprising:
an instruction execution pipeline comprising 32 processing stages, each of said 32 processing stages capable of performing one of a plurality of execution steps associated with a pending instruction being executed by said instruction execution pipeline, wherein at least one of said 32 processing stages comprises a counting circuit for determining the number of Logic 1 bits in one of a 32-bit data bus and a 32-bit register in said data processor, said counting circuit comprising:
an input stage comprising eight 4:3 carry-save adders, each of said 4:3 carry-save adders receiving four of said 32 data bits on four input lines and generating three sum bits (S2, S1, S0) equal to a total number of Logic 1 bits on said four input lines, wherein said three sum bits have bit weights of S2=4, S1=2 and S0=1, respectively;
a first intermediate stage of 4:2 carry-save adders, each of said first intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said S2 sum bits, said S1 sum bits, and said S0 sum bits and generating therefrom a carry-out (COUT) bit, a carry (C) bit and a sum (S) bit;
a second intermediate stage of 4:2 carry-save adders, each of said second intermediate stage 4:2 carry-save adders having four input lines for receiving selected ones of said COUT bits, said C-bits, and said S-bits from said first intermediate stage 4:2 carry-save adders; and
a carry-propagate adder having a first input channel and a second input channel coupled to said second intermediate stage 4:2 carry-save adders and capable of generating a binary result equal to a total number of Logic 1 bits in said group of 32 data bits.
