Reed–Solomon codes
In 1960, the mathematicians Irving S. Reed and Gustave Solomon published a paper with the title ‘Polynomial Codes over Certain Finite Fields’, which forms the basis for what has become one of the most widely used methods for error detection and correction. Reed–Solomon codes (RS codes), which are named after their inventors, are used for error detection and correction for data storage (e.g. bar codes, DAT, CD and DVD) and data transmission (e.g. DSL, satellite communications and space probes). Reed–Solomon codes are block-oriented error correction codes (ECCs) that can also correct burst errors. They are computed using the arithmetic of finite bodies (Galois fields, or GF). The characteristics of a Reed–Solomon code, in terms of the number of detectable and correctable errors for a specific data length, can be adapted to a particular application via the choice of generator polynomial.

For several years now, Reed–Solomon codes have been used by various smart card operating systems for error detection, and quite rarely for error correction, in order to secure data stored in EEPROM. The generator polynomials used are matched to the properties of EEPROM storage with regard to the occurrence of burst errors, thus yielding significantly more secure error detection than what is possible using the CRC method. For example, with an RS code using a 28 GF and two supplementary bytes in addition to the data to be protected, it is possible to detect two incorrect bytes or correct one incorrect byte. With three supplementary bytes, three incorrect bytes can be detected or one incorrect byte can be corrected, and with four supplementary bytes, four incorrect bytes can be detected or two incorrect bytes can be corrected. The size of the executable code in 8051 assembler is approximately 100 bytes, and the computation rate is approximately 10 ms/byte at 3.57 MHz. RS codes are also quite suitable for implementation in hardware.

Error correction
If it is necessary to not only detect changes in memory regions, but also to correct them if possible if they result from errors, error correction codes must be used. Since computing such codes is costly in terms of program code, using them to protect smart card memory is problematic. Furthermore, the algorithms in question are usually designed to correct only low error rates. Since EEPROM memory in smart cards is page-oriented, a whole page usually fails in the event of an error, so only methods that are capable of correcting burst errors are worth considering. Consequently, a different approach is taken for error correction. The technically simplest solution is to store the data in multiple, physically separate memory pages and use a majority-vote procedure when reading the data. Triple storage is commonly used, together with a 2-of-3 vote. A less memory-intensive variation of this method is to store the data in two locations with EDC checksum protection for each location. The occurrence of a memory error can be detected by checking the two EDC values. This also allows the memory region where the error occurred to be identified. The region with no detected error must then contain the valid data, which can be restored to the faulty region. Of course, a significant amount of extra memory is needed for these error correction methods, but for small quantities of data it is still well within acceptable limits. The main advantage is that no complicated, code-intensive algorithm is needed to evaluate the data. As an alternative to protection by multiple data storage, it is possible to use an error correction algorithm, such as the Reed–Solomon algorithm. This is particularly suitable for use with clustered errors, such as may occur in smart cards due to page failures. The algorithm occupies a few hundred bytes of memory when programmed in assembly language, and the size of theECCdata
depends primarily on probability with which errors must be detected and/or properly corrected.

Several basic remarks are in order here with regard to using error correction methods in smart cards. At first glance, it may be tempting to use these methods to correct errors that occur in the EEPROM. However, the presumed data security is bought at the price of several serious drawbacks. The required amount of memory space is enormous, and the time required to write data to memory also increases considerably, since data must be stored in multiple locations. Algorithms that can correct clustered errors on the scale at which they typically occur with page-based EEPROMs are complicated and require a large amount of memory space for the EDCs. However, there is an even more serious fundamental drawback. Even when an error correction algorithm is used, errors can in principle still be present in the corrected data, since the algorithm works properly only up to a certain number of errors. If an operating system corrects memory errors automatically, in principle it is never possible to be certain that the correction was made properly. For example, suppose that automatic error correction is applied to the balance in an electronic purse. The system operator can never be sure of what will happen to the credited amounts in the event of an error. The balance may be corrected properly, but there is a certain probability that it will be too high or too low after the correction. In this regard, it must be remembered that smart cards are inexpensive mass-produced articles, which can simply be replaced if they are faulty. As a rule, when problems occur with data contents, a higher level system that allows human intervention must decide what to do. For example, on the first instance of an error occurring in a smart card purse, the cardholder’s balance will most likely be manually restored. However, if the error recurs repeatedly, the system operator will be much less forthcoming with regard to the cardholder, since there is a possibility that the EEPROMhas been fraudulently manipulated. This cannot be handled by an error correction code in the card; instead, the system administrator must intervene.