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

A circuit for counting the number of "ones" in a binary string of X.sub.N bits, comprising:

• a minimized matrix of M rows and columns of count cells, where M is equal to log.sub.2 (X.sub.N) rounded up to the nearest integer, each row having X.sub.N -2.sup.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.

An image system, comprising:

• an imaging device for gathering image data, said image data consisting of binary strings of X.sub.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.sub.2 (X.sub.N =1) rounded up to the nearest integer and N is equal to X.sub.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.

An imaging system, comprising:

• an imaging device for gathering image data, said image data consisting of binary strings of X.sub.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.sub.2 (X.sub.N) rounded up to the nearest integer, each row having X.sub.N -2.sup.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.