Ones counting circuit, utilizing a matrix of interconnected half-adders, for counting the number of ones in a binary string of image data
First Claim
1. A circuit for counting the number of "ones" in a binary string of XN bits, comprising:
- a matrix of M rows and N columns of count cells, where M is equal to log2 (XN =1) rounded up to the neareest integer and N is equal to XN, 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.
1 Assignment
0 Petitions
Accused Products
Abstract
In an imaging system (5310), a histogram of images may be made by counting the number of "one" pixels in a matrix of image pixels. A ones counting circuit (5320) is provided to produce a binary number Y indicative of the number of "ones" in an input binary string X. The circuit (5320) comprises a matrix (5424) of counting cells (5426) arranged and interconnected in rows and columns. Each of the counting cells (5426) includes an AND gate (5428) coupled to an exclusive-OR (XOR) gate (5430). A binary string having XN bits may be thus counted employing a matrix having M rows, where M=log2(XN +1) rounded up to the nearest integer and N columns. An alternative embodiment employs a minimized matrix. This minimized matrix has M rows, where M=log2(XN +1) rounded up to the nearest integer. The minimized matrix has N=XN -2r elements in each row, where r is the row number ranging from zero for the first row to (M-1) for the last row.
177 Citations
12 Claims
-
1. A circuit for counting the number of "ones" in a binary string of XN bits, comprising:
a matrix of M rows and N columns of count cells, where M is equal to log2 (XN =1) rounded up to the neareest integer and N is equal to XN, 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. - View Dependent Claims (2, 3)
-
4. A circuit for counting the number of "ones" in a binary string of XN bits, comprising:
-
a minimized matrix of M rows and columns of count cells, where M is equal to log2 (XN) rounded up to the nearest integer, each row having XN -2r 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. - View Dependent Claims (5, 6)
-
-
7. An image system, comprising:
-
an imaging device for gathering image data, said image data consisting of binary strings of XN 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 log2 (XN =1) rounded up to the nearest integer and N is equal to XN, 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. - View Dependent Claims (8, 9)
-
-
10. An imaging system, comprising:
-
an imaging device for gathering image data, said image data consisting of binary strings of XN 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 log2 (XN) rounded up to the nearest integer, each row having XN -2r 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. - View Dependent Claims (11, 12)
-
Specification