Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2002-04-17
2004-05-18
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06738788
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to a system for storing and retrieving data in database records referenced by binary number keys having a few randomly-placed, non-deterministic bits.
2. Description of Related Art
U.S. Pat. No. 6,161,213 issued Dec. 12, 2000 to Lofstrom (incorporated herein by reference) describes an identification (ID) generation circuit embedded in an integrated circuit (IC) chip for generating a binary bit pattern that can serve as a chip ID. The ID generation circuit makes use of randomly occurring parametric variations inherent in the integrated IC manufacturing process when generating the ID in a way that ensures that the ID is highly likely to be unique for each IC chip in which the ID generation circuit is embedded, even though the same set of masks are used when fabricating the ID generation circuit in a large number of ICs. The ID generation circuit, which can be employed for example in any standard sub-micron CMOS process, does not require technologies such as EPROMs, flash memories, or poly fuses, or post fabrication techniques such as laser-trimmed fuses or links. These alternatives typically require more complex manufacturing process steps. Furthermore, each individual IC chip must be separately processed after manufacturing in order to load a unique ID into each IC chip. Since the embedded IC generation circuit requires no additional manufacturing process steps or expensive machinery to separately program each IC chip, the chip ID system it provides is less expensive to implement than other approaches.
The embedded ID generation circuit produces its output ID pattern based on the binary outputs of an array of ID cells, wherein each cell output is a function of random process variations in doping of transistor channels within the cell. Due to the analog nature of the transistor operating characteristic each cell measures when determining the state to which it sets its output bit, and due to such other effects as thermal and system noise, among the ID bits produced by the chip's ID circuit cells, a very small percentage of the bits of the chip ID may be “non-deterministic” in the sense that the cells do not always set their output bits to the same value each time they generate them. Thus sometimes a particular bit of an ID read out of an IC chip will be set to a “0”, while other times the bit will be set to a “1”. The bit locations within a cell's ID where such bit “drifting” might occur are randomly distributed across the IDs for a large collection of ICs. However while a few of the bits of any particular IC chip's ID may drift in this manner, if the ID is sufficiently large, the great majority of the bits of the ID are “deterministic” in that they will always have the same value whenever the ID generation circuit generates the chip's ID.
Thus by making the number of bits in the ID sufficiently large, the ID for any one IC chip can be statistically guaranteed, with a high degree of certainty, to be uniquely distinct from IDs generated by millions of other IC chips, even though all of the chips employ the same ID circuit to generate their IDs, and even though some of the bits of many of the IDs may drift.
Lofstrom teaches that given a population of previously retrieved non-deterministic IDs such as would be generated by ID generation circuits embedded in a large collection of IC chips, and given an incoming ID newly acquired from one IC, the new ID can be compared with the previously retrieved IDs to determine whether the new ID came from one of the collection of IC chips. Lofstrom further teaches that, if so, the identity of the IC chip from which the incoming ID can be determined even in the presence of bit drifting. One example technique for comparing ID bit patterns involves computing an absolute norm (also called the “Hamming Distance”, or “HD”) between the two ID bit patterns. The HD of any two bit patterns is simply the number of bit positions where the two ID patterns differ. In accordance with the technique, the HD between two chip ID bit patterns are compared with a predefined HD threshold HD
th
, and when the HD is less than HD
th
, then the two chip IDs must have come from the same IC, otherwise, they must have come from two separate ICs. This technique shall be referred to herein as the “HD-Matching” technique, and when two chip IDs have an HD less than HD
th
, they are considered to exhibit an “HD-Match”, as the term is used herein below.
An ID key produced by the embedded ID generation circuit may consist of two fields: a “typeID” field in which all bits are programmed at the mask level so that they are the same for all IC chips of the same type, and a “uniqueID” field that is generated by the aforementioned cells and which is unique for each chip. The appropriate bit width of the uniqueID field of the chip ID needed to ensure that all chips of the same type will have unique IDs depends largely on the number of chips of that type to be produced and the number of bits that can be expected to be non-deterministic.
An array of IC dice are typically manufactured on a wafer and then separated to form individual IC chips. However integrated circuit manufacturers test and make measurements on various operating parameters of the ICs while they are still in wafer form by using probes to access input/output pads on the surfaces of the die. When an IC tester tests ICs having the embedded ID generation circuits, it can also read out their IDs and store them in a database containing other information about the ICs. The ID read out of each die can serve as the unique, permanent identification for that particular die, throughout its life from “birth to death”, as the die passes through the various wafer-level measurement, testing, and burn-in processing steps, chip-level packaging and final testing, shipment to distributors and end-users, and assembly and use in an end-system, until the chip fails or is discarded.
It would be helpful to provide a database in which information about each chip could be stored in one or more databases, in records keyed to the chip's ID, so that the information could be retrieved when needed. However the difficulty in using a conventional database to store and retrieve information about the chip, is that some of the chips' ID's can have a few non-deterministic bits in randomly distributed bit locations. A conventional database system can only store a record using a key of a particular (fixed) value, and it can only retrieve that record if it is queried with a key having exactly the same value as the key under which the record was stored. Due to the non-deterministic nature of one or more bits of the ID read out of some of the IC chips, an ID newly read out of an IC chip may not exactly match any of the IDs previously read out of that same chip and supplied to the database when the database stored the information in the database. Thus using the ID read out of the chip as a key, a conventional database requiring deterministic ID keys will not be able to locate all of the records relating to a particular IC.
Even if a conventional database is retrofitted to deal with non-deterministic keys due to bit drifting, for example, by conducting the aforementioned HD-matching operation while trying to determine a key match, it still faces an efficiency problem. Conventional databases use such techniques as indexing, hashing, and the various sorting/searching schemes using the record keys to store and locate data records. But when presented with a new, potentially drifting key, all the indexing, hashing, and search techniques will break down. One way to resolve the problem is to create a record for each IC chip using the ID it generated when the record was first created as a key to the storage location of the record in the database. The keys to records for all chips are stored in a list. Thereafter, whenever it is necessary to read or write access the IC's record, the chip ID is read out of the IC and compared to each successive
Horng Chi-Song
Lofstrom Keith
Bedell Daniel J.
ICID, LLC
Mizrahi Diane D.
Smith-Hill and Bedell
Wu Yicun
LandOfFree
Database system using a record key having some randomly... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Database system using a record key having some randomly..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database system using a record key having some randomly... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3205077