Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
1999-12-17
2003-09-16
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S806000, C714S809000
Reexamination Certificate
active
06622284
ABSTRACT:
TECHNICAL FIELD
The invention relates to error detection. More particularly, the invention relates to methods and apparatus for efficiently detecting errors in one-hot words, which have only a single bit set in the absence of errors.
BACKGROUND ART
A binary one-hot word is a set of binary bits which have a single bit high and all others low, or a single bit low and all other bits high. For the sake of clarity, this document will refer to the single “hot” or “set” bit in a binary one-hot word as if it were nominally high while and all others are nominally low, even though it is equally possible that the set bit could be nominally low while all others are nominally high. One-hot words are utilized for example as the tag storage in a pre-validated cache. Other uses for one-hot words are apparent to those skilled in the art.
A one-hot word may be corrupted by errors in one or both of two ways generally. In a first form of corruption, the set bit is un-set (i.e., the single one bit is changed to zero). The result of this corruption is a word having all bits zero. As used herein, the term “miss” refers to this situation where all bits are zero. Depending upon the application, a miss may or may not be an erroneous condition. For example, a miss in a pre-validated cache is a valid, uncorrupted state, whereas in other applications, a miss is not valid. The other form of corruption of an one-hot word is the setting of one or more bits that should remain low. That is, a one-hot word so corrupted has two or more bits set. As used herein, the term “multihit” is used to refer to a word having two or more bits set, whereas the term “hit” is used to refer to a word having any one or more bit set.
FIG. 1
shows logic circuitry
100
for detecting certain types of errors in an eight bit one-hot word. The one-hot word has eight constituent bits D
0
, D
1
, . . . , D
7
, and the word is denoted D
0
:D
7
. The eight data bits D
0
, D
1
, . . . , D
7
are input to the logic circuitry
100
from the left, as shown in FIG.
1
. Exclusive-OR (XOR) gates
104
,
108
,
112
,
116
,
120
,
124
, and
128
are connected together so as to form an eight input exclusive-OR function. A signal ODD is output from the final exclusive-OR gate
128
. The signal ODD is high if the number of bits set in the word D
0
:D
7
is odd; the signal ODD is low if the number of bits set in the word D
0
:D
7
is even.
The logic circuitry
100
also includes NOR gates
140
,
144
,
148
, and
152
connected to NAND gates
156
and
160
, which are connected to a NOR gate
164
in such a way that a signal MISS output from the NOR gate
164
is high if and only if every bit of the word DO:D
7
is low. An inverter gate
170
is connected to the signal MISS, and a signal HIT is output from the inverter gate
170
. The signal HIT is high if one or more of the bits in the word D
0
:D
7
is high. The signals ODD and MISS are input into a NOR gate
174
. The output of the NOR gate
174
is a signal EVEN MULTIHIT, which is high when exactly two or exactly four or exactly six or all eight of the data bits D
0
, D
1
, . . . , D
7
are high. Thus, the logic circuit
100
is capable of detecting certain types of erroneous one-hot words. However, the logic circuit
100
is not capable of detecting all errors in the one-hot word D
0
:D
7
. In particular, the logic circuit
100
is not capable of detecting an error in which an odd number of bits is set in the word D
0
:D
7
. That is, the cases when exactly is three or exactly five or exactly seven bits in the word D
0
:D
7
are not detected as one-hot errors by the logic circuit
100
.
SUMMARY OF INVENTION
In one respect, the invention is an apparatus for use in detecting errors in one-hot words. The apparatus comprises a plurality of input signal lines, a plurality of switching devices connected to the input switch signal lines, a plurality of intermediate signal lines, and logic circuitry. The switching devices are connected to the input signal lines. The intermediate signal lines are also connected to the switching devices. The connection is in such a way that when a particular input signal line is set, all intermediate signal lines connected by a switching device to that particular input signal line are forced to a predetermined logic state. The intermediate signal lines are input to the logic circuitry, which outputs a signal indicative of whether at least two of the plurality of input signal lines are set.
In another respect, the invention is a method for detecting non-one-hot conditions in a group of M bits. The method encodes the group of M bits into at least 2·log
2
M encoded bits, such that each one-hot condition in the group of N bits generates a unique condition in the group of encoded bits. The method determines on the basis of the encoded bits whether the group of M bits are in a non-one-hot condition. It is preferable but not mandatory, that the at least 2·log
2
M encoded bits be two groups of at least log
2
M encoded bits each. For example (and not by way of limitation), the two groups of at least log
2
M encoded bits can be complement encodings of each other.
In yet another respect, the invention is a method for detecting one-hot errors in a group D of bits. The method first partitions the group D of bits into two non-intersecting subsets S
0
and NS
0
such that D is the union of S
0
and NS
0
. The method determines whether any of the bits in the subset S
0
are hot. The method also determines whether any of the bits in the subset NS
0
are hot. The group D is partitioned again into another two completely different non-intersecting subsets S
1
and NS
1
such that D is the union of S
1
and NS
1
. The method then determines whether any of the bits in S
1
are hot and whether any of the bits in NS
1
are hot. On the basis of the determinations made so far, the method determines whether the group D contains an error.
In comparison to the logic circuitry
100
, certain embodiments of the invention are capable of achieving certain advantages, including the following:
(1) Detection of all non-one-hot words (i.e., all multihits whether even or odd as well as misses if applicable) is possible with certain embodiments of the invention.
(2) Certain embodiments of the invention are capable of processing a one-hot word for the purpose of detecting errors with less delay than the logic circuitry
100
. In particular, there are seven gate delays in the logic circuit
100
going from the left side input to the right side output. (Gate delays are counted herein according to the typical convention in which XOR gates introduce two units of delay, while inverters or NAND gates introduce one unit of gate delay). Certain embodiments of the invention, on the other hand, have as little as four gate delays to do the same thing. Furthermore, the number of gate delays is largely independent of the size of (i.e., number of bits in) the one-hot word, whereas that is not the case with the logic circuitry
100
.
(3) Certain embodiments of the invention can be physically implemented using less semiconductor area than the logic circuitry
100
.
REFERENCES:
patent: 4498177 (1985-02-01), Larson
patent: 4912348 (1990-03-01), Maki et al.
patent: 5012246 (1991-04-01), Chung et al.
patent: 5859999 (1999-01-01), Morris et al.
patent: 5860017 (1999-01-01), Sharangpani et al.
patent: 6003154 (1999-12-01), Fisher
patent: 6034542 (2000-03-01), Ridgeway
patent: 6222893 (2001-04-01), Someya
patent: 6346906 (2002-02-01), Nakaigawa
“Scan Synthesis for One-Hot Signals” by Mitra et al. International Test Conference Proceedings. Nov. 1-6, 1997 pp. 714-722.*
“Metamorphosis: State Assignment by Retiming and Re-encoding” by Iyer et al. Computer-Aided Design, 1996. ICCAD-96. Digest of Technical Papers., 1996 IEEE/ACM International Conference on, Nov. 10-14, 1996 pp. 614-617.*
“Refined CPLD Macrocell Architecture for the Effective FSM Implementation” by Solovjev et al. EUROMICRO Conference, 1999. Proceedings. 25th , vol.: 1, 1999 pp. 102-109 vol. 1.*
“New Area Efficient Residue-to-Weighted Number System Converters” by Mat
Jones Kevin Lee
Naffziger Samuel D
Britt Cynthia
De'cady Albert
LandOfFree
Method and apparatus for detection of errors in one-hot words does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for detection of errors in one-hot words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for detection of errors in one-hot words will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3101130