Static information storage and retrieval – Read/write circuit – Including signal comparison
Reexamination Certificate
1999-07-19
2001-03-06
Mai, Son (Department: 2818)
Static information storage and retrieval
Read/write circuit
Including signal comparison
C340S146200, 36
Reexamination Certificate
active
06198668
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to a memory cell array. More specifically, a memory cell array is disclosed that determines the minimum value of data stored in elements of the array and also determines the place in the array where the minimum value is stored without requiring sequential accessing of the elements of the array for comparing of the stored values.
BACKGROUND OF THE INVENTION
It is required in certain processes to determine which value in a set of values is the minimum value or the maximum value in the set. In most applications, it is sufficient to access each of the values in a stored set of data and to compare the values to each other to determine the minimum and maximum values.
FIG. 1
is a diagram illustrating eight memory registers
101
-
108
in which eight different values are stored. A number of methods are known for searching through the stored memory values to determine, for example, a minimum value. The registers may be searched sequentially until it is determined that the value 12 stored in memory register
106
is the minimum value.
One method is to compare the first register to the second and then compare the lesser or those two registers to the third and the lesser or that comparison to the fourth and so on. This method requires N−1 clock cycles to complete assuming one comparison is performed per clock cycle (If a comparison takes more than a clock cycle, then (N−1) would be multiplied by the appropriate number of cycles). This method is slow for large data sets and an improved method can be envisioned in which the cells are divided into pairs and each register of each pair is compared with another register in the pair with the lesser values from each pair being noted and paired again for comparison during a subsequent clock cycle. This parallel method would take fewer clock cycles than the first described method (log
2
N cycles compared to N−1 cycles), but would still require multiple cycles to derive the minimum stored value.
In certain applications, quickly determining a minimum stored value from among a group of values is important, and it would be desirable to determine such a minimum value within fewer clock cycles, and ideally, within a single clock cycle.
SUMMARY OF THE INVENTION
A memory cell array configured to determine the minimum or maximum value stored in a set of registers within the array is disclosed. The memory cell array compares the values stored in each of its registers and outputs the minimum or maximum value on a set of common indicator lines. In addition, each register has an output that indicates whether the register is a register that stores the minimum value. The comparison is made in parallel and can be made more quickly than a comparison made by sequentially accessing memory registers and computing sequential comparisons.
It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, a method, or a computer readable medium such as a computer readable storage medium or a computer network wherein program instructions are sent over optical or electronic communication lines. Several inventive embodiments of the present invention are described below.
In one embodiment, a memory cell having a memory cell state comprises a memory unit configured to store a bit of data wherein the bit of data determines whether the memory cell state is a first state or a second state and a common state indicator line configured to indicate a common state associated with a group of memory cells. The memory cell further includes a logic circuit configured to compare the memory cell state to the common state, and an output line configured to indicate the result of the comparison.
In another embodiment, a memory cell array having a plurality of memory cells having memory cell states and organized into subsets of memory cells having weights comprises a plurality of common state indicator lines configured to indicate a common state among individual memory cells in different subsets of memory cells. The individual memory cells associated with each common state indicator line have the same assigned weight within their respective subsets of memory cells. Each memory cell is configured to compare the memory cell state to the state indicated on a common state indicator line associated with the memory cell and each cell is configured to be enabled or disenabled by an enable line. Each memory cell is further configured to output a signal indicating the result of the comparison when the memory cell is enabled.
A method of identifying one or more value elements in a set of elements having value is disclosed. The method comprises storing the values in a memory cell array having a plurality of sets of memory cells, each value being stored in a set of memory cells. The stored values are compared to a set of common state indicator lines configured to indicate the minimum value stored in the memory cell array. The method further comprises noting which sets of memory cells store the minimum value.
These and other features and advantages of the present invention will be presented in more detail in the following detailed description and the accompanying figures which illustrate by way of example the principles of the invention.
REFERENCES:
patent: 5003286 (1991-03-01), Carbonaro et al.
patent: 5134384 (1992-07-01), Kokubun
patent: 5166660 (1992-11-01), Peterson et al.
Interval Research Corporation
Mai Son
Ritter, VanPelt & Yi
LandOfFree
Memory cell array for performing a comparison does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory cell array for performing a comparison, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory cell array for performing a comparison will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2531345