|
Software Patent Abstract
Methods to detect and correct bit errors in data include the steps
of specifying to a compiler a storage area with a variable wherein
the variable includes a data value corresponding to its data size
and an error checking code, calculating an error checking code value
indicative of the corresponding data structure value, storing the
variable with the error checking code value, retrieving the variable
upon demand, detecting an error on the data value using the error
checking code value, and correcting the error upon detection of
an error on the data value. Further steps may include storing and
retrieving the data structure directly onto the storage area without
additional encoding and decoding circuitry, encoding and decoding
the data structure without altering the data structure format during
storing and retrieving from the storage area, or detecting and correcting
double bit errors Software for the methods is provided on or in
a computer readable medium.
Software Patent Claims
1. A method to detect and correct bit errors in a data structure
with software or firmware instructions comprising the steps ofspecifying
to a compiler a storage area with a variable wherein the variable
includes a data value corresponding to its data size and an error
checking code;calculating an error checking code value indicative
of a corresponding data structure value,storing the variable with
the error checking code value;retrieving the variable upon demand;detecting
an error on the data value using the error checking code value,
andcorrecting the error upon detection of an error on the data value.
2. The method of claim 1, wherein the software or firmware instructions
store and retrieve the data structure directly onto the storage
area without additional encoding and decoding circuitry.
3. The method of claim 1, wherein the storage area includes volatile
and non-volatile memories.
4. The method of claim 3, wherein the volatile and non-volatile
memories include high density semiconductor integrated circuit memory
arrays.
5. The method of claim 3, wherein the non-volatile memories include
magnetic and optical storage media.
6. The method of claim 1, wherein the firmware instructions are
embedded in a microcontroller.
7. The method of claim 1, wherein the firmware instructions are
embedded in a field programmable gate array.
8. The method of claim 1, further comprising the steps of:encoding
and decoding the data structure without altering the data structure
format during storing and retrieving from the storage area.
9. The method of claim 1, wherein the error checking code comprises
checking data bits to encode and parity check the data value at
each data position.
10. The method of claim 1, wherein the error checking code comprises
checking data bits to parity check the data value at each data position.
11. The method of claim 9, wherein the error checking code further
comprises a checking data bit to parity check the entire data structure.
12. The method of claim 10, further comprising the step of:detecting
and correcting any double bit errors.
13. The method of claim 1, wherein the error checking code follows
an algorithm to detect and correct for a single-bit error.
14. The method of claim 12, wherein the algorithm is selected from
a group of methods consisting of a Hamming Code, a modified Hamming
Code, a Bose-Chaudhuri-Hocquenghem, a CRC parity checks, and combinations
thereof.
15. The method of claim 1, wherein the data structure is part of
a digital communication data stream.
16. The method of claim 1, wherein the storage area is a data buffer
or main memory storage device within an intelligent electronic device.
17. The method of claim 1, wherein a storage area is part of a
storage network.
18. The method of claim 16, wherein the intelligent electronic
device comprises one selected from a group consisting of: a computing
platform, an I/O processor, a network device, a storage network,
a communication equipment, an optical device, and a protection,
automation, metering, measurement or control device.
19. The method of claim 1, further comprising the step of:communicating
the data structure through wired or wireless communication.
20. The method of claim 1, further comprising the step of:communicating
the data structure through optical or magnetic devices.
21. The method of claim 1, wherein the data value is from raw data.
22. A method to store a data structure into memory with software
or firmware instructions comprising the steps of:specifying to a
compiler a storage area with a variable wherein the variable includes
a data value corresponding to its data size and an error checking
code;calculating an error checking code value indicative of a corresponding
data structure value; andstoring the variable with the error checking
code value.
23. The method of claim 22, said method further comprising steps
to retrieve the data structure from memory with software or firmware
instructions including the steps of:specifying to a compiler a storage
area with a variable wherein the variable includes a data value
corresponding to its data size and an error checking code;retrieving
the variable upon demand;detecting for an error on the data value
using the error checking code value; andcorrecting the error upon
detection of an error on the data value.
24. A method to encode a data structure on a data stream with software
or firmware instructions comprising the steps of:specifying to a
compiler a storage area with a variable wherein the variable includes
a data value corresponding to its data size and an error checking
code;calculating an error checking code value indicative of a corresponding
data structure value; andstoring the variable with the error checking
code value.
25. The method of claim 24, said method further comprising steps
to decode the data structure on a data stream with software or firmware
instructions including the steps of:specifying to a compiler a storage
area with a variable wherein the variable includes a data value
corresponding to its data size and an error checking code;retrieving
the variable upon demand;detecting for an error on the data value
using the error checking code value; andcorrecting the error upon
detection of an error on the data value.
26. In a method to detect and correct bit errors in a data structure
with software or firmware instructions, a step to store data, said
step to store data comprising the steps of:copying calling function
raw data into a temporary data structure;calculating checking data
from the temporary data structure;copying the checking data into
the temporary data structure; andcopying the temporary data structure
with the checking data into a memory data structure.
27. The method of claim 26, said method further comprising steps
to detect and correct bit errors in a data structure with software
or firmware instructions, a step to retrieve data, said step to
retrieve data including the steps of:copying the memory data structure
into a temporary data structure;calculating checking data from the
temporary data structure;determining if there is any error in the
temporary data structure;correcting any errors in the temporary
data structure; andcopying raw data from the temporary data structure
into calling function raw data.
28. A computer readable medium containing instructions that when
executed by a data processor performs steps, comprising the steps
of:specifying to a compiler a storage area with a variable wherein
the variable includes a data value corresponding to its data size
and an error checking code;calculating an error checking code value
indicative of a corresponding data structure value;storing the variable
with the error checking code value;retrieving the variable upon
demand;detecting an error on the data value using the error checking
code value; andcorrecting the error upon detection of an error on
the data value.
29. The computer readable medium of claim 28, further comprising
the step of:storing and retrieving the data structure directly onto
the storage area without additional encoding and decoding circuitry.
30. The computer readable medium of claim 28, further comprising
the step of:encoding and decoding the data structure without altering
the data structure format during storing and retrieving from the
storage area.
31. The computer readable medium of claim 28, further comprising
the step of:detecting and correcting any double bit errors.
32. The computer readable medium of claim 28, further comprising
the step of:communicating the data structure through wired or wireless
communication.
33. The computer readable medium of claim 28, further comprising
the step of:communicating the data structure through optical or
magnetic devices.
Software Patent Description
CROSS-REFERENCE TO RELATED APPLICATION
[0001]This patent application is a non-provisional of prior provisional
patent application Ser. No, 60/816,206, filed on 23 Jun. 2006, the
right of priority of which is hereby claimed for this patent application.
FIELD OF THE INVENTION
[0002]The present invention relates generally to software and methods
to detect and correct bit errors in data. More particularly, the
present invention relates to the use of such software and methods
in intelligent electronic devices.
BACKGROUND OF THE INVENTION
[0003]Data are stored and retrieved from memory devices including
volatile and non-volatile memories such as random access memory
(RAM), FLASH memory, erasable programmable read only memory (EPROM),
read only memory (ROM), magnetic and optical disks, or the like.
Memories made of high-density integrated circuits are susceptible
to transient single-bit errors caused by alpha particles, cosmic
rays and similar radiation Alpha particles are found in lead solder
and packaging materials These events cause transient single-bit
data errors, but do not cause permanent damage to the stored data.
The transient single-bit data error corruptions are widely known
as "Soft RAM Errors" if occurred in RAM memories. Soft
RAM Errors, if uncorrected, can produce significant impacts to certain
system operations For instance, corrupted data bits can cause an
intelligent electronic device (IED) such as a protection relay or
another IED connected to the protection relay in an electric power
grid to trip unnecessarily; disrupting manufacturing and causing
productivity losses in affected areas
[0004]Many previous inventions describe methods that add additional
electronic circuits to the semiconductor memory to detect and correct
errors in the data stored in the memory A disadvantage with these
inventions is that the additional circuits reduce the reliability,
and increase the cost of the memory system. In addition, these inventions
are usually inflexible since they are designed to correct one size
of data only.
[0005]A known method to safeguard data accuracy is to use additional
electronic hardware circuits to verify and correct data corruption
in data streams during sending and receiving data. Such circuit
functions include encoding, decoding, insertion of error codes into
the data streams, detecting and correcting data errors using elaborate
and complex algorithms that add delays. Some examples of such techniques
and circuits are disclosed in U.S. Pat. Nos. 6,983,414 and 5,844,918,
respectively. Using hardware circuits for data error correction
techniques in data communication is well established, but the implementation
is complex and costly. Also, these approaches are impossible to
implement when the memory is integrated with the central processing
unit (CPU) in the same electronic device It is therefore desirable
to have a method that checks and corrects data errors without added
unreliability and without added hardware cost.
[0006]A general object of the present invention is, therefore,
to therefore provide methods to detect and correct bit errors in
data.
[0007]Another object of the present invention is to check and correct
data errors in memory storage devices.
[0008]A further object of the present invention is to use known
algorithms to perform error check and error corrections
[0009]Yet another object of the present invention is to provide
single-bit error-detection and correction to the data without altering
the data format, thereby permitting un-encoded data to be accessed
quickly and easily
[0010]A still further object of the present invention is to provide
firmware programming to implement the methods of the present invention,
wherein the firmware may be embedded in a microcontroller or field
programmable gate array (FPGA).
[0011]Another object of the present invention is to implement the
methods of the present invention in an intelligent electronic device
(IED).
SUMMARY OF THE INVENTION
[0012]The present invention relates to using a software method
to detect and correct bit errors in data. In an embodiment, the
software method comprising the steps of 1) specifying to a compiler
a variable wherein the variable includes an error checking code,
2) calculating an error checking code value indicative of the variable;
3) storing the variable, 4) retrieving the variable upon demand;
5) performing an error check and error correction to the variable,
[0013]In an embodiment, the variable includes data of defined size
with the error checking code appended to the data. In another embodiment,
the error checking code includes data specific for performing error
checking and error correction to the data.
[0014]Yet in another embodiment, the method utilizes a variety
of algorithms to perform error check and error corrections on the
data. Such algorithms may include a Hamming Code, a modified Hamming
Code, a Bose-Chaudhuri-Hocquenghem (BCH) code and a CRC parity check.
[0015]In an embodiment, the method checks and corrects data errors
in memory storage devices. Memory storage devices may include volatile
and non-volatile memory devices such as RAM, FLASH, ROM, PROM, EPROM,
magnetic and optical disks, or the like.
[0016]In another embodiment, the method checks and corrects data
errors in digital communication data stream or in a computing platform
where a data buffer is available to store the data. Yet in another
embodiment, the method appends the error checking code with encoding
information that allows single-bit error-detection and correction
to the data without altering the data format; thus allowing the
unencoded data to be accessed quickly and easily.
[0017]Yet in another embodiment, the method is implemented through
firmware programming. In another embodiment, the firmware is embedded
in a microcontroller or FPGA.
[0018]In an embodiment, the method is implemented in an IED having
a data buffer Some of the IEDs include memory storage devices, computing
platforms, I/O processors, network devices, communication equipment,
protection and control devices, or the like.
[0019]This invention implements detection and correction of errors
in memory using a software approach The invention can be applied
to any computing architecture without affecting reliability or cost.
[0020]In a further embodiment, the present invention is directed
to software or firmware (collectively referred to as "software")
which may be stored on or in a computer readable medium. The computer
readable medium thus contains instructions or code segments, that
when executed by a data processor, perform steps relating to the
methods of detecting and correcting bit errors in data in accordance
with the present invention. The computer readable medium is used
by a data processor to carry out the method steps of 1) specifying
to a compiler a variable wherein the variable includes an error
checking code; 2) calculating an error checking code value indicative
of the variable; 3) storing the variable; 4) retrieving the variable
upon demand, 5) performing an error check and error correction to
the variable. Further code segments on the computer readable medium
may be used by a data processor to carry out the steps of storing
and retrieving the data structure directly onto the storage area
without additional encoding and decoding circuitry, encoding and
decoding the data structure without altering the data structure
format during storing and retrieving from the storage area, detecting
and correcting double bit errors, communicating the data structure
through wired or wireless communication, or communicating the data
structure through optical or magnetic devices.
BRIEF DESCRIPTION OF THE DRAWINGS
[0021]The invention, together with its objects and the advantages
thereof, may best be understood by reference to the following description
taken in conjunction with the accompanying drawings, in which like
reference numerals identify like elements in the figures, and in
which;
[0022]FIG. 1A illustrates a prior art data interface which performs
software tasks in an IED.
[0023]FIG, 1B illustrates another prior art data interface which
performs software tasks in an IED.
[0024]FIGS, 2A to 2C illustrate an embodiment of the present invention
within a memory where data of different sizes can be specified in
a software program.
[0025]FIGS. 3A to 3C illustrate an embodiment of the present invention
within a processor 250 in a microcontroller performing encoding
functions to various data sizes by an error checking code.
[0026]FIGS. 4A to 4C illustrate one of the unused checking data
bits in accordance with the present invention.
[0027]FIG. 5 illustrates an embodiment of specifying a function
to store data in accordance with the present invention.
[0028]FIG. 6 illustrates an embodiment of specifying a function
to receive data in accordance with the present invention.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
[0029]It will be understood that the present invention may be embodied
in other specific forms without departing from the spirit thereof.
The present examples and embodiments, therefore, are to be considered
in all respects as illustrative and not restrictive, and the invention
is not to be limited to the details presented herein.
[0030]Software tasks in an IED 100 perform a plurality of functions.
With reference to FIG. 1A, most frequently a Data Acquisition Process
104 acquires data 103 from a Data Interface 102. The data 105 is
stored in an allocated memory Acquired Data storage area 106. The
data 105 stored is usually the same size as the data 103 acquired.
[0031]A Filtering Process 108 runs at a similar rater or slower
than the Data Acquisition Process 104. The Filtering Process 108
retrieves new data 107 from the Acquired Data storage area 106,
and old results data 109 from a Filtered Data storage area 110,
and calculates a new data 109 that is stored in the Filtered Data
storage area 110. The data stored in Filtered Data storage area
110 is often larger than the input data 109.
[0032]A Calculation Process 112 can run at a similar rate, or slower
than the Filtering Process 108. A Calculation Process 112 retrieves
one or more data 111 items from the Filtered Data storage area 110,
and old results data 113 from a Processed Data area 114, and calculates
a new result data 113 that is stored in the Processed Data storage
area 114. The Calculation Process may be a null operation in some
operations. The data stored 113 is usually of similar size to the
input data 111.
[0033]A Decision Process 116 can run at a similar rate, or slower
than the Calculation Process 112. The Decision Process 116 retrieves
new data 115 from the Processed Data storage area 114, and compares
the new data 115 with a preset value to produce data 117 that is
stored in a Decision Result storage area 118. The data 117 stored
is usually only a few bits in size.
[0034]As a result of the speed of response normally required, all
of the storage areas 106, 110, 114 and 118 are located in a memory
200, such as a semiconductor memory. As noted elsewhere, data stored
in memory 200 can be corrupted by alpha particles and similar radiation
events. The probability of corruption is low, but nonzero. IEDs,
such as protective relays, are normally activated for extended periods
(often years in duration), so they are more likely to experience
a data corruption that could cause a false decision result. Thus,
one of the aspects of the present invention is directed to a method
of safeguarding all the critical data in storage areas 106, 110,
114 and 118 to be retrieved as data 119 in a Decision Execution
Process 120.
[0035]FIG. 1A also illustrates the relative time scale for each
task performed. In an embodiment, the Filtering Process 108, the
Calculation Process 112, the Decision Process 116 and the Decision
Execution Process 120 are performed in a microcontroller.
[0036]Any bit errors in the data whether caused by radiation or
noise jitter can be detected and corrected by software method by
first specifying error checking codes when storing data 105, 109,
113 and 1,17 in the corresponding storage areas 106, 110, 114 and
118. The error checking code checks and corrects bit error in the
data stream during data retrieval process The software bit error
correction method will be further described in FIGS. 3 and 4.
[0037]FIG. 1B illustrates another prior art data interface performed
by software tasks in an IED. In another embodiment, each software
task such as from a preceding process 152, current software process
160 and subsequent process 172 runs from time-to-time, depending
upon the application The software tasks 152, 160 and 172 may not
be synchronized, so data 154, 158, 164, 166 and 170 each created
by respective task may reside in a storage area 156, 162 and 168
for a long time before it is used by the next task,
[0038]The Software Process 160 reads new data 158 from the Input
Data storage area 156. The Software Process 160 will also read data
164 from its Local Data storage area 162. Local Data 164 may have
been created during previous iterations of the Software Process
160. The Software Process 160 creates new data 166 that is stored
in an Output Data storage area 168. The Software Process 160 will
also write new data 164 into the Local Data storage area 162 for
use by subsequent process iterations of the Software Process 160
[0039]FIGS, 2A to 2C illustrate an embodiment of the present invention
within a memory where data of different sizes can be specified in
a software program. Normally, a programmer would specify the data
size to a compiler, such as in `C` code, using instructions 220a,
240a and 260a similar to those shown on the left side of FIGS, 2A
to 2C specifying unprotected raw data. For illustration, UINT8 in
FIG. 2A would specify in the storage area 8 bits (1 byte) of raw
data 202. UINT16 in FIG. 2B would specify in the storage area 16
bits (2 bytes) of raw data 204, and UINT32 in FIG. 2C would specify
in the storage area 32 bits (4 bytes) of raw data 206. The names
used are not important; all that matters is that the compiler understands
that a particular name corresponds with only one size of data in
the storage.
[0040]A method of specifying protected data in the storage areas,
such as in memory 200 using instructions 220b, 240b and 260b, is
illustrated at the right side of FIGS. 2A to 2C. Each of these instructions
220b, 240b and 260b specifies functions and respective data variables
including raw data 202, 204 and 206 of corresponding data size,
and an additional byte of storage for error checking codes 212,
214 and 216 forming respective protected data structures 202a, 204a
and 206a. The order of the raw data 202 to 206 within the instructions
220b to 260b is not important.
[0041]The additional byte of storage, as error checking codes 212
to 216 in the instructions 220b to 260b, can contain a function
that checks the contents of the raw data 202 to 206 in the storage
area such as storage areas 106, 110, 114 and 118 shown in FIG, 1A;
allowing error detection and correction when the respective data
107, 109, 111, 113, 115, 117 and 119 are retrieved from the memory
200 This checking method includes encoding and parity checks that
are described below.
[0042]In order to store the protected data structure in memory
200, the programmer must create a function that accepts the respective
raw data 202 to 206, creates the respective error checking codes
212 to 216 (encoding and parity checks) that are executed in the
compiler through the respective instructions 220b to 260b; and then
stores the protected data structures 202a to 206a into the allocated
space in memory 200.
[0043]Similarly, to retrieve the respective raw data 202 to 206
from memory 200, the programmer must specify a function within instructions
220b to 260b that reads the protected data structures 202a to 206a
from the allocated spaces' checks the raw data 202 to 206 for errors
(decoding and parity checks), corrects any errors; and then passes
the respective raw data 202 to 206 to the calling function. Embedded
within the error checking codes 212 to 216 are checking data that
perform error detection and correction algorithms (encoding, decoding,
parity checks) If there is no error, the stored raw data 202 to
206 and the retrieved raw data 202 to 206 from the memory 200 will
be unchanged. Otherwise, any single-bit error in the retrieved raw
data 202 to 206 will be corrected through the function of retrieval
instruction.
[0044]There may be one or more functions to store protected data
(depending upon the data size and the programmer's style) and one
or more functions to retrieve protected data. Each of the specified
functions is included within the instructions, for example using
`C` code to specify functions to the compiler in the processor 250.
[0045]For illustration purposes, if the programmer wishes to allocate
storage for an 8-bit data variable that is unprotected, he/she would
write:
TABLE-US-00001 UINT8 variable_name;
[0046]Alternatively, if the programmer wishes to allocate storage
for an 8-bit data variable that is protected, he/she would write:
TABLE-US-00002 PROT_BYTE variable_name;
[0047]If the programmer wishes to allocate storage for a 16-bit
data variable that is unprotected, he/she would write:
TABLE-US-00003 UINT16 variable_name;
[0048]Alternatively, if the programmer wishes to allocate storage
for a 16-bit data variable that is protected, he/she would write.
TABLE-US-00004 PROT_WORD variable_name;
[0049]In an embodiment, an example below illustrates using these
functions to store and retrieve protected data structures 202a to
206a:
TABLE-US-00005 VOID put_protected_byte(PROT_BYTE*, UINT8); VOID
put_protected_word(PROT_WORD*, UINT16); VOID put_protected_long(PROT_LONG*,
UINT32*); and functions to retrieve protected data structures 202a
to 206a: RESULT get_protected_byte(PROT_BYTE*, UINT8*); RESULT get_protected_word(PROT_WORD*,
UINT16*); RESULT get_protected_long(PROT_LONG*, UINT32*);
[0050]These store and retrieve protected data functions can use
any error detection and correction algorithm or scheme desired.
In an embodiment, a modified Hamming Code is a common algorithm
to detect and correct single-bit errors. The only requirements are
that sufficient storage is allocated for the error checking code
with checking data, and that the same algorithm is used for storing
and retrieving a specific data size. Different data sizes can have
different encoding schemes, error detection and correction schemes.
[0051]FIGS. 3A to 3C illustrate an embodiment of the invention
within a porcessor 250 in a micro-controller performing encoding
functions to various data sizes by the error checking code. [0052]2
encoded byte (Hamming Code algorithm) [0053]3 encoded byte (Hamming
Code algorithm) [0054]4 encoded byte (Hamming Code algorithm) [0055]5
encoded byte (Hamming Code algorithm)
[0056]In an embodiment, the error checking codes 212 to 216 include
respective checking data bits 212a to 212h, 214a to 214h and 216a
to 216h, Each of the checking data bits 212a to 212d, 214a to 214e
and 216a to 216f in the respective error checking codes 212, 214
and 216 is a parity bit for a group of bits in the raw data 202,
204 and 206. For example, checking data bit 212a in FIG. 3A is a
parity bit to a group of five bits (bit 0,1,3,4,6) forming an encoding
sequence 212ah in the raw data 202. Similarly, checking data bit
212b is a parity bit to a group of five bits (bit 0, 2,3,5,6) forming
an encoding sequence 212bh; checking data bit 212c is a parity bit
to a group of four bits (bit 1,2,3,7) forming an encoding sequence
212ch; and checking data bit 212d is a parity bit to a group of
four bits (bit 4,5,6,7) forming an encoding sequence 212dh, and
so forth The encoding sequences 212ah to 212dh with the raw data
202 constitute a protected data structure 202a with an encoded byte
1. The encoding sequences 212ah to 212dh within the error checking
code 212 correspond to the type of algorithm selected by the programmer
In this embodiment, the algorithm selected for illustration is a
modified Hamming Code.
[0057]Similarly, for a 16 bit raw data 204, five checking data
bits 214a to 214e within the error checking code 214 correspond
to five encoding sequences 214ah to 214eh with the raw data 204
constituting a protected data structure of 204a with encoded bytes
1 and 2.
[0058]Similarly, for a 32 bit raw data 206, six checking data bits
216a to 216f within the error checking code 216 correspond to six
encoding sequences 216ah to 216fh constituting a protected data
structure 206a of encoded bytes 1 to 4.
[0059]Each applicable checking data bit 212a to 212d, 214a to 214e
and 216a to 216f is set to a value that gives even parity when combined
with the corresponding bits in the raw data 202, 204 and 206.
[0060]It is not important that the sequence of the encoding checking
data bits 212a to 212d in the error checking code 212 be consecutive.
The programmer can specify any sequence of checking data bits 212a
to 212h within the error checking code 212 to perform the data encoding
function in the protected data structures 202a to 206a.
[0061]FIGS, 4A to 4C illustrate an embodiment of the invention
within a processor 250 in a microcontroller performing an optional
parity check for the complete data structure.
[0062]FIGS. 4A to 4C also illustrate that one of the unused checking
data bits such as 212e, 214f and 216g can be used to perform respective
parity checks 212eh to 216eh for the complete data structures 202a
to 206a, The parity check functions 212eh to 216eh check the overall
parity including the prior checking data bits 212a to 212d, 214a
to 214e and 216a to 216f in the data structures 202a, 204a and 206a
The optional parity checks 212eh to 216eh provide detection of double
bit errors through instructions from software or firmware codes,
As shown, the encoding function in the instructions 220b, 240b and
260b is a modified Hamming Code designed such that the corruption
of any single-bit error will be detected, and the location of the
corrupt bit in the protected data 202a, 204a and 206a is indicated
by the pattern of check bits 212e, 214h and 216g; where an even
parity sum check for each raw data bit 202, 204 and 206 and the
check bits 212e, 214h and 216g are expected,
[0063]Any remaining unused checking data bits (212f to 212h, 214g
and 214h, 216h) in the error checking codes 212, 214 and 216 are
set to zero,
[0064]In an embodiment of the invention to store the protected
data in memory 200, the programmer can specify a compiler instruction
to include a function that accepts the raw data; creates the checking
data and adds it into the data structure; and then stores the completed
protected data structure into the allocated space in memory 200.
[0065]Similarly, to retrieve the protected data structure from
memory, the programmer must specify in the compiler instruction
to include a function that reads the data structure from the allocated
space from memory 200; checks the data structure for errors; corrects
any errors, and then passes the raw data to the calling code.
[0066]There may be one or more functions to store protected data
structure (depending upon the data size and the programmer's style)
and one or more functions to retrieve protected data structure.
[0067]One example uses the following functions to store and retrieve
protected data structure.
[0068]The function put_protected_byte stores one byte of raw data
into a PROT_BYTE data structure in memory It is called with two
parameters, the address of the PROT_BYTE data structure, and the
value of the raw data.
TABLE-US-00006 1 VOID put_protected_byte (PROT_BYTE *data_ptr,
UINT8 raw_data) 2 { i. PROT_BYTE temp_data; ii. UINT16 parity_data;
iii. UINT8 checking_data; iv. /* Put the raw data into a temporary
data structure */ v. temp_data.byte_pr = raw_data; vi. /* Initialize
the checking data to zeroes */ vii. temp_data.code_b_pr = 0; viii.
/* Calculate the hamming code */ ix. checking_data = hamming_check_byte
(&temp_data); x. /* Add checking data to the temporary data
structure */ xi. temp_data.code_b_pr = checking_data; xii. /* Adjust
double error check bit, as required */ xiii. parity_data = temp_data.byte_pr
{circumflex over ( )} temp_data.code_b_pr; xiv. if (calc_parity(parity_data)
!= 0) 1. temp_data.code_b_pr {circumflex over ( )}= 0x10; xv. /*
Then store the temporary data structure into memory */ xvi. *data_ptr
= temp_data; 3 }
[0069]The function get_protected_byte retrieves one byte of raw
data from a PROT_BYTE data structure in memory. It is called with
two parameters, the address of the PROT_BYTE data structure, and
the address of the raw data. The function returns a value of SUCCESS
or FAILURE.
TABLE-US-00007 1 RESULT get_protected_byte(PROT_BYTE *byte_ptr,
UINT8 *data_ptr) 2 { i. PROT_BYTE temp_data; ii. UINT16 parity_data;
iii. RESULT return_value; iv. UINT8 decode_result; v. /* get the
data structure from memory */ vi. temp_data = *byte_ptr; vii. /*
Check the data structure for errors */ viii. decode_result = hamming_check_byte(&temp_data);
ix. if (decode_result != 0) x. { 1. /* Soft error occurred, so report
it */ 2. diag_flag_set(DIAG_SOFT_RAM); 3. /* Correct any single
errors in the raw data */ 4. temp_data.byte_pr {circumflex over
( )}= Bit_Mask_Data[decode_result]; 5. /* Correct any single errors
in the checking data */ 6. temp_data.code_b_pr {circumflex over
( )}= Bit_Mask_Code[decode_result]; xi. } xii. /* Update the raw
data in the calling function */ xiii. *data_ptr = temp_data.byte_pr;
xiv. /* Check the data structure for multiple errors */ xv. parity_data
= temp_data.byte_pr {circumflex over ( )} temp_data.code_b_pr; xvi.
if (calc_parity(parity_data) == 0) xvii. { 1. /* No errors, so retrieval
was successful */ 2. return_value = SUCCESS; xviii. } xix. else
xx. { 1. /* Multiple errors detected, so failed retrieval */ 2.
return_value = FAILURE; xxi. } xxii. return return_value; 3 }
[0070]The function put_protected_word stores one word of raw data
into a PROT_WORD data structure in memory It is called with two
parameters, the address of the PROT_WORD data structure, and the
value of the raw data.
TABLE-US-00008 1 VOID put_protected_word (PROT_WORD *data_ptr,
UINT16 raw_data) 2 { i. PROT_WORD temp_data; ii. UINT16 parity_data;
iii. UINT8 checking_data; iv. /* Put the raw data into a temporary
data structure */ v. temp_data.word_pr = raw_data; vi. /* Initialize
the checking data to zeroes */ vii. temp_data.code_w_pr = 0; viii.
/* Calculate the hamming code */ ix. checking_data = hamming_check_word
(&temp_data); x. /* Add checking data to the temporary data
structure */ xi. temp_data.code_w_pr = checking_data; xii. /* Adjust
double error check bit, as required */ xiii. parity_data = temp_data.word_pr
{circumflex over ( )} temp_data.code_w_pr; xiv. if (calc_parity(parity_data)
!= 0) 1. temp_data.code_w_pr {circumflex over ( )}= 0x20; xv. /*
Then store the temporary data structure into memory */ xvi. *data_ptr
= temp_data; 3 }
[0071]The function get_protected_word retrieves one word of raw
data from a PROT_WORD data structure in memory. It is called with
two parameters, the address of the PROT_WORD data structure, and
the address of the raw data. The function returns a value of SUCCESS
or FAILURE.
TABLE-US-00009 1 RESULT get_protected_word(PROT_WORD *word_ptr,
UINT16 *data_ptr) 2 { i. PROT_WORD temp_data; ii. UINT16 parity_data;
iii. RESULT return_value; iv. UINT8 decode_result; v. /* get the
data structure from memory */ vi. temp_data = *word_ptr; vii. /*
Check the data structure for errors */ viii. decode_result = hamming_check_word(&temp_data);
ix. if (decode_result != 0) x. { 1. /* Soft error occurred, so report
it */ 2. diag_flag_set(DIAG_SOFT_RAM); 3. /* Correct any single
errors in the raw data */ 4. if (decode_result <= 12) 5. { /*
Correct single bit error in least significant byte of raw data */
temp_data.word_pr {circumflex over ( )}= 3 (UINT16)Bit_Mask_Data[decode_result];
1. } 2. else if (decode_result <= 21) 3. { /* Correct single
bit error in most significant byte of raw data */ a. temp_data.word_pr
{circumflex over ( )}= b. ((UINT16)Bit_Mask_Data[decode_result]
<< 8); 4. } 5. if (decode_result <= 21) 6. { a. /* Correct
any single errors in the checking data */ b. temp_data.code_w_pr
{circumflex over ( )}= c. Bit_Mask_Code[decode_result]; 7. } ii.
} iii. /* Update the raw data in the calling function */ iv. *data_ptr
= temp_data.word_pr; v. /* Check the data structure for multiple
errors */ vi. parity_data = temp_data.word_pr {circumflex over (
)} temp_data.code_w_pr; vii. if (calc_parity(parity_data) == 0)
viii. { 1. /* No errors, so retrieval was successful */ 2. return_value
= SUCCESS; ix. } x. else xi. { 1. /* Multiple errors detected, so
failed retrieval */ 2. return_value = FAILURE; xii. } xiii. return
return_value; 4 }
[0072]The function put_protected_long stores one long word of raw
data into a PROT_LONG data structure in memory. It is called with
two parameters, the address of the PROT_LONG data structure, and
the value of the raw data.
TABLE-US-00010 1 VOID put_protected_long (PROT_LONG *data_ptr,
UINT32 raw_data) 2 { i. PROT_LONG temp_data; ii. UINT16 parity_data;
iii. UINT8 checking_data; iv. /* Put the raw data into a temporary
data structure */ v. temp_data.long_pr = raw_data; vi. /* Initialize
the checking data to zeroes */ vii. temp_data.code_I_pr = 0; viii.
/* Calculate the hamming code */ ix. checking_data = hamming_check_long
(&temp_data); x. /* Add checking data to the temporary data
structure */ xi. temp_data.code_I_pr = checking_data; xii. /* Adjust
double error check bit, as required */ xiii. parity_data = (UINT16)
temp_data.long_pr 1. {circumflex over ( )} (UINT16)(temp_data.long_pr
>> 16) 2. {circumflex over ( )} temp_data.code_I_pr; xiv.
if (calc_parity(parity_data) != 0) 1. temp_data.code_I_pr {circumflex
over ( )}= 0x40; xv. /* Then store the temporary data structure
into memory */ xvi. *data_ptr = temp_data; 3 }
[0073]The function get_protected_long retrieves one long word of
raw data from a PROT_LONG data structure in memory It is called
with two parameters, the address of the PROT_LONG data structure,
and the address of the raw data. The function returns a value of
SUCCESS or FAILURE.
TABLE-US-00011 1 RESULT get_protected_long(PROT_LONG *long_ptr,
UINT32 *data_ptr) 2 { i. PROT_LONG temp_data; ii. UINT16 parity_data;
iii. RESULT return_value; iv. UINT8 decode_result; v. /* get the
data structure from memory */ vi. temp_data = *long_ptr; vii. /*
Check the data structure for errors */ viii. decode_result = hamming_check_byte(&temp_data);
ix. if (decode_result != 0) x. { 1. /* Soft error occurred, so report
it */ 2. diag_flag_set(DIAG_SOFT_RAM); 3. /* Correct any single
errors in the raw data */ 4. if (decode_result <= 12) 5. { /*
Correct single bit error in least significant byte of raw data */
temp_data.long_pr {circumflex over ( )}= 3 (UINT32)Bit_Mask_Data[decode_result];
1. } 2. else if (decode_result <= 21) 3. { /* Correct single
bit error in next significant byte of raw data */ a. temp_data.long_pr
{circumflex over ( )}= b. ((UINT32)Bit_Mask_Data[decode_result]
<< 8); 4. } 5. else if (decode_result <= 29) 6. { /* Correct
single bit error in next significant byte of raw data */ a. temp_data.long_pr
{circumflex over ( )}= b. ((UINT32)Bit_Mask_Data[decode_result]
<< 16); 7. } 8. else if (decode_result <= 37) 9. { /* Correct
single bit error in most significant byte of raw data */ a. temp_data.long_pr
{circumflex over ( )}= b. ((UINT32)Bit_Mask_Data[decode_result]
<< 24); 10. } 11. if (decode_result <= 37) 12. { a. /*
Correct any single errors in the checking data */ b. temp_data.code_w_pr
{circumflex over ( )}= c. Bit_Mask_code[decode_result]; 13.) ii.
} iii. /* Update the raw data in the calling function */ iv. *data_ptr
= temp_data.long_pr; v. /* Check the data structure for multiple
errors */ vi. parity_data = (UINT16) temp_data.long_pr 1. {circumflex
over ( )} (UINT16)(temp_data.long_pr >> 16) 2. {circumflex
over ( )} temp_data.code_I_pr; vii. if (calc_parity(parity_data)
== 0) viii. { 1. /* No errors, so retrieval was successful */ 2.
return_value = SUCCESS; ix. } x. else xi. { 1. /* Multiple errors
detected, so failed retrieval */ 2. return_value = FAILURE; xii.
} xiii. return return_value; 4 }
[0074]In an embodiment, the correction of single bit errors may
use two look-up tables One look-up table for errors in the raw data,
and another look-up table for errors in the checking data. The two
look-up tables are.
TABLE-US-00012 const static UINT8 Bit_Mask_Data[39] = { 0x00, /*
This is the no error case */ 0x00, /* Check bit 0 */ 0x00, /* Check
bit 1 */ 0x01, /* Data bit 0 */ 0x00, /* Check bit 2 */ 0x02, 0x04,
0x08, /* Data bits 1-3 */ 0x00, /* Check bit 3 */ 1. /* Data bits
4 - 10 */ 0x10, 0x20, 0x40, 0x80, 0x01, 0x02, 0x04, 0x00, /* Check
bit 4 */ 2. /* Data bits 11 - 18 */ 0x08, 0x10, 0x20, 0x40, 0x80,
0x01, 0x02, 0x04, 3. /* Data bits 19 - 25 */ 0.08, 0x10, 0x20, 0x40,
0x80, 0x01, 0x02, 0x00, /* Check bit 5 */ 4. /* Data bits 26 - 31
*/ 0x04, 0x08, 0x10, 0x20, 0x40, 0.80 }; const static UINT8 Bit_Mask_Code[39]
= { 0x00, /* This is the no error case */ 0x01, /* Check bit 0 */
0x02, /* Check bit 1 */ 0x00, /* Data bit 0 */ 0x04, /* Check bit
2 */ 0X00, 0X00, 0X00, /* Data bits 1-3 */ 0x08, /* Check the bit
3 */ 5. /* Data bits 4-10 */ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x10, /* Check bit 4 */ 6. /* Data bits 11 - 18 */ 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 7. /* Data bits 19 - 25 */ 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x20, /* Check bit 5 */ 8. /*
Data bits 26 - 31 */ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, };
[0075]FIG. 5 illustrates an embodiment of specifying a function
to store data. In the diagram of FIG. 5, the method is initiated
at bubble 502 by a put command. At block 504, calling function raw
data is copied into a temporary data structure. A function is performed
at block 506 to calculate checking data from the temporary data
structure. The checking data is then copied into the temporary data
structure at block 508 At block 510, the temporary data structure
is copied into a memory data structure. The method then returns
at bubble 512 to await the next put command.
[0076]FIG. 6 illustrates an embodiment of specifying a function
to receive data. In the diagram of FIG. 6, the method is initiated
at bubble 602 by a get command. At block 604, the memory data structure,
such as that provided at block 510 in FIG, 5, is copied into a temporary
data structure. A function is performed at block 606 to calculate
checking data from the temporary data structure. Decision block
608 then determines if there is any error in the temporary data
structure If so, data in the temporary data structure is corrected
at block 610. If not, or if the data was corrected at block 610,
the method proceeds to block 612 where the raw data from the temporary
data structure is copied into calling function raw data. The method
then returns at bubble 614 to await the next get command.
[0077]In view of the foregoing discussion of methods in accordance
with the present invention, it will be appreciated that the present
invention also encompasses software or firmware (collectively referred
to as "software") for performing the methods. For example,
the software may be stored on or in a computer readable medium,
such as on a compact disk (CD), volatile and non-volatile memories
such as random access memory (RAM), FLASH memory, erasable programmable
read only memory (EPROM), read only memory (ROM), magnetic and optical
disks, or the like. The computer readable medium contains instructions
or code segments, that when executed by a data processor, perform
steps relating to the methods of detecting and correcting bit errors
in data in accordance with the present invention. In one embodiment,
the computer readable medium is used by a data processor to carry
out the method steps of 1) specifying to a compiler a variable wherein
the variable includes an error checking code, 2) calculating an
error checking code value indicative of the variable; 3) storing
the variable, 4) retrieving the variable upon demand; 5) performing
an error check and error correction to the variable. In accordance
with other embodiments, further code segments on the computer readable
medium may be used by a data processor to carry out the steps of
storing and retrieving the data structure directly onto the storage
area without additional encoding and decoding circuitry, encoding
and decoding the data structure without altering the data structure
format during storing and retrieving from the storage area, detecting
and correcting double bit errors, communicating the data structure
through wired or wireless communication, or communicating the data
structure through optical or magnetic devices.
[0078]In an embodiment, this method of appending an error checking
code to the data uses software functions to perform encoding, single-bit
error detection using parity checks and error correction, and maintains
the format of the data and allows the un-encoded data to be accessed
quickly and easily. Yet in another embodiment, the method utilizes
a variety of known algorithms to perform error check and error corrections
on the data, including Hamming Codes, Bose-Chaudhuri-Hocquenghem
(BCH), CRC parity checks or modifications of encoding and decoding
algorithms.
[0079]In an embodiment, the method checks and corrects data errors
in memory storage devices The memory storage devices include volatile
and non-volatile memory devices such as RAM, FLASH, ROM, PROM, EPROM,
magnetic and optical disks, or the like.
[0080]In another embodiment not shown, the method can apply the
same principle to check and correct data errors in a digital communication
data stream or in a computing platform where a data buffer is available
to store the data.
[0081]Yet in another embodiment, the method may be implemented
through firmware programming. In another embodiment, the firmware
may be embedded in a microcontroller or FPGA.
[0082]In an embodiment, the method may be implemented in an IED
having a data buffer. Some of the IEDs include memory storage devices,
computing platforms, I/O processors, network devices, storage networks,
communication equipment, protection and control devices, or the
like. The present invention can be applied to any computing architecture
without affecting reliability or cost.
[0083]While particular embodiments of the invention have been shown
and described, it will be obvious to those skilled in the art that
changes and modifications may be made therein without departing
from the invention in its broader aspects. |