Ones counting circuit, utilizing a matrix of interconnected half-adders, for counting the number of ones in a binary string of image data

Claim 2

A circuit for counting the number of "ones" in a binary string of X N bits, comprising: a matrix of M rows and N columns of count cells, where M is equal to log 2 (X N =1) rounded up to the neareest integer and N is equal to X N , each count cell including: an AND gate having first and second inputs and an output forming a first output of said count cell; an XOR gate having first and second inputs and an output forming a second output fo said count cell; said first input of said AND gate connected to said first input of said XOR gate and forming a first input of said count cell, said second input of said AND gate coxnnected to said second input of said XOR gate and forming a second input of said matrix of cell circuit; said count cells in said matrix interconnected wherein said first input of each count cell is connected to said first output of a corresponding count cell in a prior row, said first input of each count cell in a first orw receiving a corresponding bit of said binary string, and said second input of each count cell is connected to said second output of a corresponding count cell in a a prior column, said second input of each count cell in a first column receiving a "zero"; and said matrix receiving said binary string and producing an output binary number at corresponding second outputs of a last column of said matrix indicative of the number of "ones" in said binary string.

Claim 3

The circuit, as set forth in claim 1, wherein: said binary string is input to said frist row of said matrix wherein a least significant bit of said binary string is supplied to said first input of said count cell in said first column of said matrix and a most significant bit said binary string is supplied to said first input of said count cell in said last column of said matrix.

Claim 4

The circuit, as set forth in claim 1, wherein: said output binary number is output from said last column of said matrix wherein a least significant bit of said output binary number is output from said second output of said count cell in said first row of said matrix and a most significant bit of said output binary number is output from second output of said count cell in a last row of said matrix.

Claim 5

A circuit for counting the number of "ones" in a binary string of X N bits, comprising: a minimized matrix of M rows and columns of count cells, where M is equal to log 2 (X N ) rounded up to the nearest integer, each row having X N -2 r count cells where r is a row number assigned to the row ranging from zero for a first row to M-1 for a last row, each count cell including: an AND gate having first and second inputs and an output forming a first output of said count cell; an XOR gate having first and second inputs and an output forming a second output of said count cell; said first input of said AND gate connected to said first input of said XOR gate and forming a first input of said count cell, said second input of said AND gate connected to said second input of said XOR gate and forming a second input of said count cell; said count cells in said minimized matrix interconnected wherein said first input of each count cell except for any count cell in a first row is connected to said first output of a corresponding count cell in a prior row, said first input of each count cell in said first row receiving a corresponding bit of said binary string, and said second input of each count cell except for any count cell in said first column is connected to said second output of a corresponding count cell in a prior column, said second input of each count cell in said first column of each row except for said count cell in said first row and said first column is connected to said first output of a count cell in a previous row and previous column, said second input of said count cell in said first row and said first column receiving a least significant bit of said binary string; and said matrix receiving said binary string and producing an output binary number at corresponding second outputs of said count cells of a last column of said matrix and said first output of said count cell of said last column of the matrix and a last row of said matrix indicative of the number of "ones" in said binary string.

Claim 6

A circuit for counting the number of "ones" in a binary string of X N bits, comprising: a minimized matrix of M rows and columns of count cells, where M is equal to log 2 (X N ) rounded up to the nearest integer, each row having X N -2 r count cells where r is a row number assigned to the row ranging from zero for a first row to M-1 for a last row, each count cell including: an AND gate having first and second inputs and an output forming a first output of said count cell; an XOR gate having first and second inputs and an output forming a second output of said count cell; said first input of said AND gate connected to said first input of said XOR gate and forming a first input of said count cell, said second input of said AND gate connected to said second input of said XOR gate and forming a second input of said count cell; said count cells in said minimized matrix interconnected wherein said first input of each count cell except for any count cell in a first row is connected to said first output of a corresponding count cell in a prior row, said first input of each count cell in said first row receiving a corresponding bit of said binary string, and said second input of each count cell except for any count cell in said first column is connected to said second output of a corresponding count cell in a prior column, said second input of each count cell in said first column of each row except for said count cell in said first row and said first column is connected to said first output of a count cell in a previous row and previous column, said second input of said count cell in said first row and said first column receiving a least significant bit of said binary string; and said matrix receiving said binary string and producing an output binary number at corresponding second outputs of said count cells of a last column of said matrix and said first output of said count cell of said last column of the matrix and a last row of said matrix indicative of the number of "ones" in said binary string.

Claim 7

The circuit, as set forth in claim 4, wherein: said binary string is input to said first row of said matrix wherein a least significant bit of said binary string is supplied to said second input of said count cell in said first column of said matrix, a second least significant bit of said binary string is supplied to said first input of said count cell in said first column of said matrix, and a most significant bit of said binary string is supplied to said first input of said count cell in said last column of said matrix.

Claim 8

The circuit, as set forth in claim 4, wherein: said output binary number is output from said last column of said matrix wherein a least significant bit of said output binary number is output from said second output of said count cell in said first row of said matrix, a second most significant bit of said output binary number is output from said count cell in a last row of said matrix and a most significant bit of said output binary number is output from said count cell in a last row of said matrix.

Claim 9

An image system, comprising: an imaging device for gathering image data, said image data consisting of binary strings of X N bits; an image data memory for storing said image data; an image processor connected to said image memory for recalling said image data, said image processor comprising a circuit for determining the number of "ones" in said binary strings of said image data including a matrix of M rows and N columns of count cells, where M is equal to log 2 (X N =1) rounded up to the nearest integer and N is equal to X N , each count cell including: an AND gate having first and second inputs and an output forming a first output of said count cell; an XOR gate having first and second inputs and an output forming a second output of said count cell; said first input of said AND gate connected to said first input of said XOR gate and forming a first input of said count cell, said second input of said AND gate connected to said second input of said XOR gate and forming a second input of said count cell; said count cells in said matrix interconnected wherein said first input of each count cell is connected to said first output of a corresponding count cell in a prior row, said first input of each count cell in a first row receiving a corresponding bit of one of said binary strings, and said second input of each count cell is connected to said second output of a corresponding count cell in a prior column, said second input of each count cell in a first column receiving a "zero"; and said matrix receiving said one of said binary strings and producing an output binary number at corresponding second outputs of a last column of said matrix indicative of the number of "ones" in said one of said binary strings.

Claim 10

An image system, comprising: an imaging device for gathering image data, said image data consisting of binary strings of X N bits; an image data memory for storing said image data; an image processor connected to said image memory for recalling said image data, said image processor comprising a circuit for determining the number of "ones" in said binary strings of said image data including a matrix of M rows and N columns of count cells, where M is equal to log 2 (X N =1) rounded up to the nearest integer and N is equal to X N , each count cell including: an AND gate having first and second inputs and an output forming a first output of said count cell; an XOR gate having first and second inputs and an output forming a second output of said count cell; said first input of said AND gate connected to said first input of said XOR gate and forming a first input of said count cell, said second input of said AND gate connected to said second input of said XOR gate and forming a second input of said count cell; said count cells in said matrix interconnected wherein said first input of each count cell is connected to said first output of a corresponding count cell in a prior row, said first input of each count cell in a first row receiving a corresponding bit of one of said binary strings, and said second input of each count cell is connected to said second output of a corresponding count cell in a prior column, said second input of each count cell in a first column receiving a "zero"; and said matrix receiving said one of said binary strings and producing an output binary number at corresponding second outputs of a last column of said matrix indicative of the number of "ones" in said one of said binary strings.

Claim 11

The circuit, as set forth in claim 7, wherein: said one of said binary strings is input to said first row of said matrix wherein a least significant bit of said one of said binary strings is supplied to said first input of said count cell in said first column of said matrix and a most significant bit of said one of said binary strings is supplied to said first input of said count cell in said last column of said matrix.

Claim 12

The circuit, as set forth in claim 7, wherein: said output binary number is output from said last column of said matrix wherein a least significant bit of said output binary number is output from said second output of said count cell in said first row of said matrix and a most significant bit of said output binary number is output from said second output of said count cell in a last row of said matrix.

Claim 13

An imaging system, comprising: an imaging device for gathering image data, said image data consisting of binary strings of X N bits; an image data memory for storing said image data; an image processor connected to said image memory for recalling said image data, said image processor comprising a circuit for determining the number of "ones" in said binary strings of said image data includes a minimized matrix of M rows and columns of count cells, where M is equal to log 2 (X N ) rounded up to the nearest integer, each row having X N -2 r count cells where r is a row number assigned to the row ranging from zero for a first row to M-1 for a last row, each count cell including: an AND gate having first and second inputs and an output forming a first output of said count cell; an XOR gate having first and second inputs and an output forming a second output of said count cell; said first input of said AND gate connected to said first input of said XOR gate and forming a first input of said count cell, said second input of said AND gate connected to said second input of said XOR gate and forming a second input of said matrix cell circuit; said count cells in said minimized matrix interconnected wherein said first input of each count cell except for any count cell in a first row is connected to said first output of a corresponding count cell in a prior row, said first input of each count cell in said first row receiving a corresponding bit of one of said binary string, and said second input of each count cell except for any count cell in said first column is connected to said second output of a corresponding count cell in a prior column, said second input of each count cell in said first column of each row except for said count cell in said first row and said first column is connected to said first output of a count cell in a previous row and previous column, said second input of said count cell in said first row and said first column receiving a least significant bit of one of said binary strings; and said matrix receiving said one of said binary strings and producing an output binary number at corresponding second outputs of said count cells of a last column of said matrix and said first output of said count cell of said last column of the matrix and a last row of said matrix indicative of the number of "ones" in said one of said binary strings.

Claim 14

An imaging system, comprising: an imaging device for gathering image data, said image data consisting of binary strings of X N bits; an image data memory for storing said image data; an image processor connected to said image memory for recalling said image data, said image processor comprising a circuit for determining the number of "ones" in said binary strings of said image data includes a minimized matrix of M rows and columns of count cells, where M is equal to log 2 (X N ) rounded up to the nearest integer, each row having X N -2 r count cells where r is a row number assigned to the row ranging from zero for a first row to M-1 for a last row, each count cell including: an AND gate having first and second inputs and an output forming a first output of said count cell; an XOR gate having first and second inputs and an output forming a second output of said count cell; said first input of said AND gate connected to said first input of said XOR gate and forming a first input of said count cell, said second input of said AND gate connected to said second input of said XOR gate and forming a second input of said matrix cell circuit; said count cells in said minimized matrix interconnected wherein said first input of each count cell except for any count cell in a first row is connected to said first output of a corresponding count cell in a prior row, said first input of each count cell in said first row receiving a corresponding bit of one of said binary string, and said second input of each count cell except for any count cell in said first column is connected to said second output of a corresponding count cell in a prior column, said second input of each count cell in said first column of each row except for said count cell in said first row and said first column is connected to said first output of a count cell in a previous row and previous column, said second input of said count cell in said first row and said first column receiving a least significant bit of one of said binary strings; and said matrix receiving said one of said binary strings and producing an output binary number at corresponding second outputs of said count cells of a last column of said matrix and said first output of said count cell of said last column of the matrix and a last row of said matrix indicative of the number of "ones" in said one of said binary strings.

Claim 15

The circuit, as set forth in claim 10, wherein: said one of said binary strings is input to said first row of said matrix wherein a least significant bit of said one of said binary strings is supplied to said second input of said count cell in said first column of said matrix, a second least significant bit of said one of said binary strings is supplied to said first input of said count cell in said first column of said matrix, and a most significant bit of said one of said binary strings is supplied to said first input of said count cell in said last column of said matrix.

Claim 16

The circuit, as set forth in claim 10, wherein: said output binary number is output from said last column of said matrix wherein a least significant bit of said output binary number is output from said second output of said count cell in said first row of said matrix, a second most significant bit of said output binary number is output from said count cell in a last row of said matrix and a most significant bit of said output binary number is output from said count cell in a last row of said matrix.