emLib ECC
Bit error correction for embedded devices
emLib ECC is a library that provides functions for detection and correction of data errors. The library can be employed to ensure the reliability of data transferred via digital networks or of the data stored on storage devices. The error detection and correction is performed using a BCH linear block code.
How emLib ECC works
A bit error occurs when the value of a data bit is unintentionally altered during the transmission over a communication channel or when the storage that holds the data is corrupted. Where bit errors are unavoidable, error correction has to be employed to correct them.
There are different ways to correct bit errors such re-sending data, data mirroring, parity check and so on. emLib-ECC uses parity checking to generate a check sum of the payload data that can be later used to correct the bit errors.
Key features
- High performance
- Modular design
- Low memory consumption
- Easy to use
Application usage
Typically, bit error correction requires complex algorithms to calculate, locate and correct the bit errors. For this reason, dedicated hardware is used to help perform these operations in a reasonable amount of time. On the other hand, having a dedicated hardware for bit error correction increases the cost of a system and is therefore available only on a few MCUs and storage devices. The vast majority of MCUs and storage devices do not have dedicated hardware for error correction and the target application is left to correct them in the software. emLib-ECC can help here by allowing an application to correct bit errors without the need of a dedicated hardware and thus to reduce costs.
A typical example is a system that uses a SLC NAND flash device as storage. Almost all modern SLC NAND flash devices require multi-bit error correction. There are NAND flash devices that are able to correct bit errors using an internal hardware ECC but they are more expensive in terms of price than the variants without internal hardware ECC. The difference in price becomes significant for high-volume systems where using a less expensive NAND flash device translates into large costs savings. emLib-ECC gives the possibility of using the less expensive NAND flash device without hardware bit error correction by allowing the target application to efficiently check and correct the bit errors in the software.
What is BCH?
BCH is a widely used linear block error-correcting code that is capable of detecting and correcting multiple random bit errors. The name of the code comes from the names of scientists that discovered this code: Raj Bose, D. K. Ray-Chaudhuri, and Alexis Hocquenghem. Error-correcting codes work by adding redundant parity-check bits to the information bits which have to be protected against bit errors.
The information bits together with the parity-check bits form a codeword. The parity-check bits are a linear combination (XOR and shift operations) of the information bits and are calculated by the means of a generator polynomial. The generator polynomial is chosen based on the capabilities of the BCH code such as number of correctable bit errors and the size of the data block.
The error correction process uses the property that the Hamming distance ( that is the number of bit positions that have different values) between any two different valid codewords (that is without bit errors) is exactly two times the number of bit errors that can be corrected plus one. Using this property the error correction procedure is able to map a codeword with bit errors to a valid codeword and thus to correct the occurred bit errors. The BCH code is also able to detect but not correct a number of bit errors equal to error correction capability plus one.
Given the capability of BCH code to correct random bit errors this error-correcting code is typically employed for the correction of data stored on NAND flash devices.
Using emLib ECC
The emLib ECC module has a simple yet powerful API. It can be easily integrated into an existing application. The code is completely written in ANSI-C.
To simply calculate the ECC of contiguous data block, the application would only need to call one function. If two or more distinct data blocks need to be protected by the same ECC, a separate API function can be called which can process a list of data blocks.
All functionality can be verified with standard test patterns using the validation API functions. The functions for generating the lookup tables that are used for different calculation are also included for full transparency.
Performance and resource usage
The following table contains performance values for an emLib ECC release build as tested on a Cortex-M7 running at 217 MHz using lookup tables.
Correction capability | Calculation speed | 1 bit correction speed | 2 bit correction speed | 3 bit correction speed | 4 bit correction speed | 8 bit correction speed | 24 bit correction speed | 40 bit correction speed |
---|---|---|---|---|---|---|---|---|
4-bit | 25 MB/s | 18.5 MB/s | 2.4 MB/s | 1.8 MB/s | 1.4 MB/s | - | - | - |
8-bit | 13 MB/s | 7.2 MB/s | 1.2 MB/s | 0.8 MB/s | 0.5 MB/s | 0.3 MB/s | - | - |
24-bit | 2 MB/s | 0.9 MB/s | 0.5 MB/s | 0.4 MB/s | 0.4 MB/s | 0.2 MB/s | 54 KB/s | - |
40-bit | 1.5 MB/s | 0.4 MB/s | 0.3 MB/s | 0.2 MB/s | 0.2 MB/s | 0.1 MB/s | 51 KB/s | 36 KB/s |
The following table contains resource usage values for an emLib ECC release build. The lookup tables can be disabled at compile time to reduce the ROM usage. Please note that disabling the lookup tables will reduce the performance of the ECC routines.
Correction capability | Code | Division table | GF tables | Total |
---|---|---|---|---|
4-bit | 8.2 KByte | 2 KByte | 32 KByte | 42.2 KByte |
8-bit | 9.3 KByte | 4 KByte | 32 KByte | 45.3 KByte |
24-bit | 9.3 KByte | 12.2 KByte | 64 KByte | 85.5 KByte |
40-bit | 9.4 KByte | 18.4 KByte | 64 KByte | 91.8 KByte |
Example code
Using the 4-bit ECC to correct bit errors
This sample shows how to use emLib ECC to correct bit errors. The sample starts by calculating the ECC. On the next step 4 bit errors are forced toggling some bits in the data block. The sample ends by correcting the bit errors using the previously calculated ECC.
void main(void) {
U8 abData[] = "SEGGER"; // Data to be protected by ECC
U64 ecc; // Calculated ECC
int r; // Correction result
printf("Start\n");
//
// Calculate the ECC of the original data.
//
printf("Calculate ECC...");
ecc = ECC_BCH4_GF13_Calc(abData, sizeof(abData));
printf("OK\n");
printf(" Data: %s\n", abData);
printf(" ECC: 0x%16llu\n", ecc);
//
// Force 4 bit errors in the data protected by ECC.
//
printf("Force bit errors...");
abData[1] ^= 0x20;
abData[2] ^= 0x20;
abData[3] ^= 0x20;
abData[4] ^= 0x20;
printf("OK\n");
printf(" Data: %s\n", abData);
printf(" Num. bit errors: 4\n");
//
// Correct the bit errors using ECC.
//
printf("Correct bit errors...");
r = ECC_BCH4_GF13_Apply(abData, sizeof(abData), &ecc);
if (r < 0) {
printf("Error (Too many bit errors)\n");
} else {
printf("OK\n");
printf(" Data: %s\n", abData);
printf(" Num. bit errors: %d\n", r);
}
printf("Finished\n");
while (1) {
;
}
}
Sample applications
emLib ECC includes sample applications to demonstrate its functionality and to provide an easy to use starting point for your application. The source code of these applications is included in the shipment. The following applications are delivered with emLib ECC:
Application name | Target platform | Description |
---|---|---|
ECCCalcApply.exe | Windows | Command line tool to calculate the ECC of a specified file and to correct the bit errors in a file using the calculated ECC. |
Download emLib ECC sample applications
ECCCalcApply
ECCCalcApply is a Windows command line tool to calculate the ECC for a specified file and to correct bit errors occurred in it. The calculated ECC is stored to a separate file. The bit correction capability and the block size are configurable.
Usage: ECCCalcApply [-a <ECCAlgo>] [-c] [-e <ECCFile>] [-h] [-q] <DataFile>
Parameter | Description |
---|---|
[-a <ECCAlgo>] | Specifies the error correction capability and the block size. Permitted values are:
|
[-c] | Used to indicate that error correction should be performed. If omitted the tool calculates ECC. |
[-e <ECCFile>] | Optional path to the file where the ECC is stored. If omitted the tool uses <datafile>.ecc as file name.</datafile> |
[-h] | Show usage information. |
[-q] | Do not display any information. |
<DataFile> | Path to the file that contains the data to be protected by ECC. |
The screenshot beneath shows how to calculate the ECC of the file "Test.txt" that contains the string "TTTTTTTT". The ECC value is stored in the file "Test.ecc".
The next screenshot shows how the bit errors can be corrected using the previously calculated ECC. First, 4 bit errors are generated by changing the contents of the file "Test.txt" to the string "UUUUTTTT". After the bit error correction is performed the contents of the file "Test.txt" changes back to "TTTTTTTT".