Recommended Reading
Reed-Solomon Codes in Practical Implementations
In previous sections, we have considered the basic mathematics that serve as the foundation for Reed-Solomon codes. We have also investigated the simplest coder/decoder, capable of correcting single errors and working with two parity symbols. These correcting capabilities are catastrophically insufficient for the overwhelming majority of problems. Therefore, it becomes necessary to implement a more powerful coder /decoder.
The coder/decoder considered in this section is highly configurable and can be tuned for operation with any number of parity symbols. This means that under conditions of reasonable redundancy, it is capable of correcting any imaginable number of errors. However, this flexibility and universality comes with a cost. Therefore, the design of such a decoder is about 100 times more difficult. The independent development of Reed-Solomon decoders requires a fundamental knowledge of higher mathematics in general, and the nature of correcting codes in particular. Therefore, do not be afraid or confused if the material provided in this section is not easily understandable. These topics are difficult and there is no simple way to explain them.
On the other hand, for practical usage in correcting codes, it is possible to simply compile the source codes of the Reed-Solomon coder/decoder provided here without obtaining further insight into it. The same approach is the case if you use any ready-to-use library from third-party developers. As an alternative example, the concluding part of this chapter will briefly describe the interface of the 
ElByECC.DLL library developed by the Elaborate Bytes company and distributed along with the popular Clone CD program. The best-known CD burner everywhere, Ahead Nero Burning ROM, has the similar library (NEWTRF.DLL).
Legend
Let us recall the main notation used in this chapter. The number of characters of the message being encoded (also called the data word) according to generally adopted agreement is designated by the letter k; the complete length of the codeword including the data being encoded and parity characters is equal to n . Consequently, the number of parity characters is equal to n ” k . The maximum number of recoverable errors is designated by t. Since two parity symbols are required for correcting a single error, the total number of parity characters is equal to 2t . The RS (n, k) expression describes a specific sort of Reed-Solomon correcting code, operating with n -symbol blocks, in which k symbols represent useful data, while all other symbols are used for parity symbols.
The polynomial obtained on the basis of the primitive term ± is known as the generated polynomial.
Encoder
There are at least two types of Reed-Solomon codes: non-systematic and systematic encoders.
Non-systematic Reed-Solomon error-correcting codes are calculated by multiplying the data word by the generated polynomial. As a result, the codeword is generated that is absolutely different from the source information word and, therefore, not suitable for direct usage. For bringing the obtained data into their initial form, it is necessary to carry out the resource-consuming decoding operation, even if the data are not corrupted and do not require recovery!
When using systematic encoding, however, the source data word remains without changes, while the correcting codes (often called parity characters) are added to its end. Thanks to this, the decoding operation is needed only in the event of actual data destruction. Computation of non-systematic Reed-Solomon codes is carried out by the division of the data word by the generating polynomial. At the same time, all symbols of the data word are shifted by n-k bytes to the left, while the 2t bytes of the remainder are written to the released positions (see Fig. 2.1).
Fig. 2.1: Codeword structure
Since considering both types of encoders would require a lot of time, let us concentrate all of our attention on systematic coders, which are the most popular.
From the architectural point of view, the encoder represents the set of shift registers, joined by means of integrators and multipliers, operating according to the rules of Galois arithmetic. The shift register represents the sequence of memory cells , called bits, each of which contains one element of a Galois field GF(q) . The symbol, contained in a specific position, is transmitted to the output line as it leaves this position. Simultaneously, the symbol from the input line is loaded into position. Replacement of symbols takes place discretely, at strictly defined time intervals, known as clocks.
In hardware implementation of the shift register, its elements can be connected both sequentially and in parallel. In the case of sequential connection, the sending of a single m -bit symbol will require m clocks, while in implementations using parallel connection, this operation requires only one clock.
The low efficiency of software implementations of Reed-Solomon codes is due to the fact that the developer cannot connect elements of the shift register in parallel. On the contrary, software developers are forced to work with the bit width enforced by specific hardware architecture. However, developing a 4-element, 8-bit shift register of the parallel type on processors of the IA32 family is a realistic task.
Circuits based on shift registers are usually called filters. The flow chart of a filter that carries out the division of a polynomial by a constant is shown in Fig. 2.2. Don t be confused by the fact that division is implemented by means of multiplication and addition. This technique is based on solving the system of two recurrent equalities:
Formula 2.1: Dividing a polynomial by a constant by means of multiplication and addition
Fig. 2.2: Structure of the simplest Reed-Solomon encoder
Here: Q(r) (x) and R(r) (x) are the quotient and remainder at the r -th step or recursion, respectively. Since addition and modulo-2 computation are identical, for implementing the divider, we need only two devices ”addition and multiplication devices. The subtraction device is not necessary.
After n shifts, the quotient will appear at the register output, while the register itself will contain the remainder, which represents the calculated parity symbols (they are the same as Reed-Solomon codes), while multiplication coefficients from g0 to g(2t-1) directly correspond to the multiplication coefficients of the generated polynomial.
The simplest software implementation of this type of filter is provided below. It represents a ready-to-use Reed-Solomon encoder, suitable for practical use. It could certainly be improved if desired. However, in this case, the listing would become less compact and less illustrative .
| |
/*----------------------------------------------------------------------------- * * Reed-Solomon encoder * ======================== * * The data being encoded are transmitted via the data[i] array, where i = 0 (k - 1), * and generated parity symbols are placed into the b[0] b[2*t-1] array. * Source and resulting data must be represented in a polynomial * form (i.e., in standard form of machine data representation). * Encoding is carried out using feedback shift register, * filled with appropriate elements of the g[] array with the generated * polynomial inside. The procedure of generating this polynomial was already * discussed in the previous section. * The generated codeword is described by the following formula: * c(x)= data (x) *x^ (n-k)+b (x), where ^ stands for the operator of raising * the number into the power of exponent. * * Based on the source codes by * Simona Rockliff, from 26.06.1991 * distributed according * to the GNU license -----------------------------------------------------------------------------*/ encode_rs() { int i, j; int feedback; // Initializing the parity bit field by zeroes for (i = 0; i < n - k; i++) b[i] = 0; // Processing all symbols // of the source data from right to left for (i = k - 1; i >= 0; i--) { // preparing (data[i] + b[n - k -1]) for multiplication by g[i] // i.e., adding the next "captured" symbol of the source // data to the least significant symbol of the parity bits // (corresponding to the b2t-1 register, see Fig. 2.2) // and converting it into the index form, // storing the result in the feedback register. // As was already pointed out, the sum of the two indexes is // the product of polynomials. feedback = index_of [data[i] ^ b[n - k - 1]]; // Are there any more symbols for processing? if (feedback != -1) { // shifting the chain of bx registers for (j = n-k-1; j>0; j --) // If the current coefficient g is a real one // (i.e., non-zero) coefficient, then // multiplying feedback by the appropriate g coefficient // and adding it to the next element of the chain if (g[j]!=-1) b[j]=b[j-1]^alpha_to[ (g[j]+feedback) %n]; else // if the current coefficient g is equal to zero, // then carrying out only shift without // multiplication, by moving // the character from one m-register // to another m-register b[j] = b[j-i] // Looping the output symbol to the leftmost b0-register b[0] = alpha_to[ (g[0]+feedback) %n]; } else { // Division is complete, // carrying out the last shift of the register, // the quotient (which will be lost) // appears at the register output, // while the register itself // will contain the required remainder. for (j = n-k-1; j>0; j --) b[j] = b[j-1] ; b[0] = 0; } } }
| |
Decoder
Decoding of Reed-Solomon codes is a complicated problem, the solution to which results in a bulky, complicated, and extremely complex code requiring the developer to have extensive knowledge of many areas of higher mathematics. A typical decoding scheme known as auto-regressive spectral decoding method, comprises the following steps:
-
Determining error syndrome (syndrome decoder).
-
Building error polynomial, carried out either using the highly efficient, but rather sophisticated Berlekamp-Massey algorithm, which is hard to implement, or using the simple, but very slow Euclidean algorithm.
-
Finding the roots of this polynomial, which is usually carried out by means of trivial try-out (Chien search algorithm).
-
Determining the error type, which is carried out by building the bit mask calculated on the basis of Forney s algorithm or any other algorithm of matrix inversion.
-
Correcting erroneous symbols by means of superimposing the mask onto the data word and sequentially inverting all corrupted bits via XOR operation.
It is important to point out that this decoding scheme is neither the only one nor, probably, the best one. However, it is universal. In practice, there are about ten various decoding schemes, absolutely different from each other. As a rule, the choice of specific scheme depends on which decoder part is implemented programmatically, and for which part hardware implementation is chosen .
Syndrome Decoder
Roughly speaking, syndrome is the remainder from the division of the codeword c(x) by the generator polynomial g(x) . If this remainder is equal to zero, the codeword is considered to be correctly transferred. A non-zero remainder indicates that there is at least one error. The remainder from the division is the polynomial, independent from the source message, which is determined exclusively by the nature of the error.
The received codeword v comprising components v i = c i + e i , where i = 0, , n ” 1 , represents the sum of the codeword c and error vector e . The goal of decoding is the separation of the codeword from the error vector, which is decried by the syndrome polynomial and calculated according to the following formula: S i =v(a j+j0 “1 ), where j ranges from 1 to 2t , and a represents the prime member alpha, which we have discussed earlier. Once again, we express the division function via multiplication, because division is a very inefficient operation from the performance point of view.
A flow chart of the device that carries out syndrome computation is presented in Fig. 2.4. As can be seen from this illustration, it represents a typical filter (compare it to the scheme shown in Fig. 2.2), therefore, it doesn t require any additional comment.
Fig. 2.4: Flow chart of the syndrome computation circuit
Computation of the error syndrome is carried out iteratively, so that the computation of the resulting polynomial (also called the answer polynomial ) is completed directly at the moment when the last parity symbol passes through the filter. The total number of passes of the data being decoded through the filter is equal to 2t ”one pass per symbol of the resulting polynomial.
The example of the simplest software implementation of the syndrome decoder is provided in Listing 2.2 and is much more illustrative than any verbal description.
Error Locator Polynomial
The obtained syndrome describes the error configuration, but it still doesn t specify, which symbols of the received message were corrupted. Actually, the power of the syndrome polynomial equal to 2t is significantly lower than the power of the message polynomial, which is equal to n , and there is no direct correspondence between their coefficients. The polynomial that has coefficients directly corresponding to the coefficients of corrupted symbols is called the error locator polynomial and, according to commonly adopted agreement, is designated by (lambda).
If the number of corrupted symbols does not exceed t , the syndrome and error locator are related by unambiguous mapping, which can be expressed by the following formula: GCD[x n -1, E(x)]= (x) . Computation of the locator is reduced to the problem of finding the greatest common divisor. As a matter of fact, this problem was successfully solved by Euclid, and can be easily implemented both at the software and at the hardware level. However, the simplicity of implementation pays a price. In this case, the performance is sacrificed for simplicity, because the algorithm is very inefficient. In practice, the more efficient, but, at the same time, more sophisticated Berlekamp-Massey algorithm is used. A detailed description of this algorithm can be found in Volume 2 of the Art of Programming by Donald Knuth (see also Theory and Practice of Error Control Codes by Richard Blahut). The algorithm is reduced to the task of building a chain of shift registers with linear feedback, and, in its essence, is a kind of auto-regression filter, the multipliers in the vectors of which specify the polynomial .
A decoder created according to such an algorithm requires no more than 3t multiplication operations in each iteration, and the total number of iterations doesn t exceed 2t . Thus, the solution to this problem requires no more than 6t 2 multiplication operations. In fact, the computation of the locator is reduced to solving the system of 2t equations with t unknown quantities ”one equation per symbol of the syndrome. Unknown terms are positions of the corrupted symbols in the codeword v . As can be seen easily, if the number of errors exceeds t , the system of equations has no solution. In this case, it becomes impossible to recover the corrupted information.
The flow chart of the Berlekamp-Massey algorithm is shown in Fig. 2.5, and its complete software implementation can be found on the companion CD.
Fig. 2.5: Flow chart of the Berlekamp-Massey algorithm
Polynomial Roots
From what we know of the error locator polynomial, its roots determine the location of corrupted symbols in the received codeword. Now it only remains to find these roots. Most frequently, this is accomplished using the Chien search procedure, which by its nature is analogous to the inverse Fourier transform. In fact, it is reduced to exhaustive search and trying of all possible variants. All 2 m possible symbols, one by one, are substituted into the locator polynomial, and then the polynomial is computed. If the result is zero, then the required roots have been found.
Data Recovery
Thus, we know, which symbols of the codeword are corrupted. But, for the moment, we are not prepared to answer how . Using the syndrome polynomial and roots of the locator polynomial, it is possible to determine the character of corruption for each of the corrupted symbols. As a rule, the Forney algorithm is used for this purpose. This algorithm comprises two stages: first, by means of convoluting the syndrome polynomial by the locator polynomial , we obtain some intermediate polynomial, conventionally designated as . Then, based on the -polynomial, the zero error location is computed, which, in turn , is divided by the derivative of the -polynomial. As a result, the bit mask is obtained, in which each of the set bits corresponds to the corrupted bit. To restore the codeword to its initial state, all corrupted bits must be inverted, which is achieved by means of a logical XOR operation.
At this point, the procedure of decoding the received codeword can be considered accomplished. It only remains to discard n-k parity symbols, and the obtained data word is ready for use.
Source Code of the Decoder
The source code of a fully functional Reed-Solomon decoder, supplied with the necessary number of comments can be found on the companion CD. If you have difficulties when analyzing this listing, refer to the flow charts presented in Figs. 2.3, 2.4, and 2.5.
Fig. 2.3: Scheme of auto-regressive spectral decoder for Reed-Solomon correcting codes
Interface to the EIByECC.DLL Library
Software implementation of the Reed-Solomon encoder/decoder provided in Listings 2.19 and on the companion CD is sufficiently illustrative. However, it is characterized by very low performance and requires optimization. As an alternative variant, it is possible to use ready libraries supplied by third-party developers, included in software products in any way related to processing Reed-Solomon error-correction codes. The list of such products includes utilities for CD copying/burning/restoration, drivers for tape drives (from streamer to ARVID), various telecommunication complexes, etc.
As a rule, all of these libraries are an integral part of the software product itself, and, therefore, are not documented in any way. Restoring the prototypes of the interface functions is a non-trivial task, requiring the investigator not only to have the disassembling skills, but also a knowledge of higher mathematics, otherwise the sense of all bit manipulations will remain unintelligible.
Is such disassembling legal? In fact, the disassembling of third-party software products is prohibited , but is still legal . In this case, it is appropriate to provide the analogy with unsealing your TV set, which results in voiding the warranty, but cannot be prosecuted by law. In just the same way, no one prohibits you to call the functions of someone else s library from your program. Distributing this library as part of your software product is illegal. However, what prevents you from asking the user to install this library on his own?
Provided below is a brief description of the most important functions of the ElByECC.DLL library included as part of the well-known copier of protected CDs ” Clone CD. The shareware copy of this product can be downloaded from http://www.elby.ch/ . The Clone CD product itself will be functional only for 21 days, after which it will require you to register the copy. However, there are no limitations on the usage of the ElByECC.DLL library.
Despite the fact that the ElByECC.DLL is oriented towards operation with sectors of CDs, it is also suitable for other purposes, for instance, for building fault-tolerant disk arrays, mentioned earlier in this chapter.
A brief description of the main functions of this library is provided below.
Linking the ElByECC.DLL Library to Your Programs
There are at least two methods of linking DLLs to your programs. When using dynamic linking, addresses of the required functions are determined by means of GetProcAddress calls. In this case, the ElByECC.DLL library itself must be loaded previously using LoadLibrary . For instance, this may look as follows (error handling is omitted for the sake of simplicity):
| |
HANDLE h; int (__cdecl *CheckECCAndEDC_Model) (char *userdata, char *header, char *sector); h=LoadLibrary("ElbyECC.dll"); CheckECCAndEDC Model = GetProcAddress(h, "CheckECCAndEDC Model"); | |
Static linking assumes that a special lib-file is present, which can be automatically generated by the implib utility supplied as part of Borland C++ of any suitable version. This is a command-line utility called as follows: " implib.exe -a ElByECC.lib ElByECC.lib ".
GenECCAndEDC Model
The GenECCAndEDC_Model function generates error-correcting codes on the basis of a 2048-byte block of user data. This function has the following prototype:
| |
GenECCAndEDC_Mode1(char *userdata_src, // Pointer to the 2048-byte array char *header_src, // Pointer to the header struct RAW_SECTOR_MODE1 *raw_sector_model_dst)
| |
-
userdata_src is the pointer to the 2,048-byte block of user data, for which it is necessary to compute the error-correction codes. The user data itself remains unchanged in the course of function execution. They are automatically copied to the buffer of the target sector, where they are supplemented by 104+172 parity bytes and 4 bytes of the checksum.
-
header_src is the pointer to the 4-byte block containing the sector header. The first three bytes are taken for the absolute address written in the BCD form, while the fourth byte is responsible for the type of sector, to which it is necessary to assign the value 1, corresponding to the mode when correcting codes are enabled.
-
raw_sector_mode1_dst is the pointer to the 2,352-byte block, in which the generated sector will be written, containing 2,048 bytes of user data and 104+172 bytes of error-correction codes along with 4 bytes of the checksum. Raw sector is presented by the following structure:
| |
struct RAW_SECTOR_MODE1 { BYTE SYNC[12]; // Sync group BYTE ADDR[3]; // Absolute sector address BYTE MODE; // Sector type BYTE USER_DATA[2048]; // User data BYTE EDC[4]; // Checksum BYTE ZERO[8]; // Zeroes (not used) BYTE P[172]; // P parity bytes BYTE Q[104]; // Q parity bytes }; | |
Provided that the function has been completed successfully, it returns a non-zero value, otherwise it returns zero.
CheckSector
The CheckSector function checks the integrity of the sector by the checksum, and restores it using Reed-Solomon redundant codes, if necessary.
| |
CheckSector (struct RAW_SECTOR *sector, // Pointer to the sector buffer int DO); // Only checking/correcting
| |
-
sector ”the pointer to the 2,352-byte data block containing the sector being tested . The sector is recovered on the fly, i.e., immediately when the error occurs. If the number of corrupted bytes exceeds the correcting capabilities of the Reed-Solomon codes, the source data remains unchanged.
-
DO ”the flag, the zero value of which specifies that modifying the sector is prohibited. In other words, this value corresponds to the TEST ONLY mode. A non-zero value allows data recovery, if they actually were corrupted.
-
If the function terminates successfully, it returns a non-zero value. The function returns zero if the sector contains an error (in the TEST ONLY mode) or if the data recovery has failed (when calling the function in the data recovery mode). To prevent possible ambiguity, it is recommended that you call this function in two steps. First ”in the test mode for checking data integrity, and second, in the data recovery mode (if data recovery is needed).
Final
Provided below is an example of practical usage of error-correcting code, suitable for solving practical real-world tasks .
| |
/*----------------------------------------------------------------------------- * * Demonstration of ElByECC.DLL * ============================ * * This program demonstrates working with ElByECC.DLL library, * by generating redundant Reed-Solomon codes on the basis of * user data, and then deliberately corrupting and restoring them. * The number of bytes to be corrupted is passed in the first * command-line parameter (6 by default) -----------------------------------------------------------------------------*/ #include <stdio.h> #include "ElByECC.h" // Decompiled by #define _DEF_DMG 6 // Corrupt by default #define N_BYTES_DAMAGE ((argc>1) ?atol (argv[1]) :_DEF_DMG) // How many bytes to corrupt? main(int argc, char **argv) { int a; char stub_head[HEADER_SIZE]; // Sector header char user data[USER DATA SIZE]; // User data area struct RAW_SECTOR_MODE1 raw_sector_for_damage; // Sector for corruption struct RAW_SECTOR_MODE1 raw_sector_for_compre; // sector checksum. // TITLE //----------------------------------------------------------------------------- printf("= ElByECC.DLL usage demo example by KK\n"); // Initializing user data //----------------------------------------------------------------------------- printf("user data initialize..............."); for (a = 0; a < USER_DATA_SIZE; a++) user_data [a] = a; // User_data init memset(stub_head, 0, HEADER_SIZE); stub_head[3] = 1; // src header init printf ("+OK\n"); // Generating Reed-Solomon codes on the basis of user data //----------------------------------------------------------------------------- printf("RS-code generate..................."); a = GenECCAndEDC_Model(user_data, stub_head, &raw_sector_for_damage); if (a == ElBy_SECTOR_ERROR) {printf("-ERROR!\x7\n"); return -1;} memcpy(&raw_sector_for_compre, &raw_sector_for_damage, RAW_SECTOR_SIZE); printf ("+OK\n"); // Intentionally corrupting user data //----------------------------------------------------------------------------- printf("user-data %04d bytes damage........", N_BYTES_DAMAGE); for (a=0; a<N_BYTES_DAMAGE; a++) raw_sector_for_damage.USER_DATA[a] ^=0xFF; if(!memcmp(&raw_sector_for_damage, &raw_sector_for_compre, RAW_SECTOR_SIZE)) printf ("-ERR: NOT DAMAGE YET\n"); else printf ("+OK\n"); // Checking the integrity of user data //------------------------------------------------------------------------ printf("user-data check...................."); a = CheckSector((struct RAW_SECTOR*)&raw_sector_for_damage, ElBy_TEST_ONLY); if (a == ElBy_SECTOR_OK){ printf("-ERR:data not damage\x7\n"); return -1;} printf(".data damge\n"); // Recovering user data //------------------------------------------------------------------------ printf("user-data recorder................."); a = CheckSector((struct RAW_SECTOR*)&raw_sector_for_damage, ElBy_REPAIR); if (a == ElBy_SECTOR_ERROR){ printf("-ERR: NOT RECORVER YET\x7\n"); return -1;} printf ("-OK\n"); // Checking if recovery was successful //------------------------------------------------------------------------ printf("user-data recorver check..........."); if(memcmp(&raw_sector_for_damage, &raw_sector_for_compre, RAW_SECTOR_SIZE)) printf ("-ERR: NOT RECORVER YET\x7\n"); else printf ("+OK\n"); printf ("+OK\n"); return 1; } | |
EAN: 2147483647
Pages: 60