Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-01-09
2004-02-10
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06691142
ABSTRACT:
TECHNICAL FIELD
This application relates to built-in self-test (BIST) of semiconductor devices, and particularly to pseudo random address generators for testing of semiconductor cache memory devices.
BACKGROUND
Conventional cache memory devices are sized only in powers of two, e.g., 1024, 4096, etc. Self-testing of these devices is typically performed using an ordinary linear feedback shift register (LFSR) to generate pseudo random addresses over a corresponding range of a power of two. Hence, because there has been no prior motivation to develop a system or method to generate pseudo random addresses for testing a cache memory device having a size that is not a power of two, such systems and methods have not been taught or suggested.
For testing a cache memory size that is not a power of two, for example a 0.75M cache memory, although a conventional LFSR could have been used, illegal addresses would have been generated. An ordinary LFSR generates addresses in the hexadecimal range for example from 0 to 0×3fff (0 to 16383 decimal), whereas the hexadecimal range needed is from 0 to 0×2fff (0 to 12287 decimal). Thus it would be advantageous to develop a system and method of pseudo random address generation for cache testing, that avoids the upper quarter of an address range that otherwise would be a power of two.
SUMMARY OF THE INVENTION
The present invention is directed to a system for and method of generating pseudo random number sequences that exclude a predetermined upper fraction of a range that otherwise covers a power of two. The most significant N bits of each number are generated cyclically by unidirectionally shifting the bits of the previous number in the sequence from a first memory cell toward an Nth memory cell of a sequential register and generating a new bit in the first memory cell in response to a predetermined combination of the previous N most significant bits, such that always at least one of the N bits is a zero, thus excluding a predetermined upper fraction of a power of two range. For each number in the pseudo random sequence, the N most significant bits are matched with a least significant bits portion that is generated using conventional methodology, such that every value of the least significant bits portion is generated exactly once for each cyclic value of most significant bits.
In some embodiments the matching between most significant and least significant bits is discontinuously randomized by applying a shift control bit to the most significant bit portion obtained by ANDing the external shift control bit of the least significant bit portion with the bit value of a selected one of the least significant bits. Thus the most significant bits shift if and only if the values of both the external shift control bit and the selected least significant bit are high. In some embodiments the new value of the first of the most significant bits is obtained through feedback logic, for example by NORing the previous N most significant bits. The total number of bits in each pseudo random sequence number is not limited, but practical implementations are typically in the range from 4 to 64 bits. The number N of most significant bits can be selected in a range from two bits to the entire number of bits in the sequence number. This results in excluded upper range fractions of one-fourth, one-eighth, one-sixteenth, . . . , (one-half)
N
.
Pseudo random sequence generators according to the present invention can be right shifting or left shifting, which generate sequences in reverse orders. Other implementations include coupled right- and left-shifting configurations. Both hardware and software implementations are available.
This solution according to the present invention is simple, still quite random, and generates a unique and reversible sequence. The system and method according to the present invention can be applied, typically through a parallel output bus, to the testing of cache memory devices having address ranges that are not powers of two, for example a 12 k or a 0.75M cache memory.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims. The novel features which are believed to be characteristic of the invention, both as to its organization and method of operation, together with further objects and advantages will be better understood from the following description when considered in connection with the accompanying figures. It is to be expressly understood, however, that each of the figures is provided for the purpose of illustration and description only and is not intended as a definition of the limits of the present invention.
REFERENCES:
patent: 5079733 (1992-01-01), Antoine et al.
patent: 5105376 (1992-04-01), Pedron
patent: 5867409 (1999-02-01), Nozuyama
patent: 6263082 (2001-07-01), Ishimoto et al.
patent: 6430586 (2002-08-01), Williams
patent: 6442579 (2002-08-01), Hansson
Hewlett--Packard Development Company, L.P.
Mai Tan V.
LandOfFree
Pseudo random address generator for 0.75M cache does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pseudo random address generator for 0.75M cache, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pseudo random address generator for 0.75M cache will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3295884