Chapter 0 : What is Reed-Solomon code?
Reed-Solomon code is one of the error correction codes. Reed-Solomon codes are used in various fields such as digital terrestrial broadcasting, satellite communications, CD, DVD, HDD, and QR codes. In this section, the basics of Reed-Solomon codes are explained in the following chapters.
Chapter 1: Galois bodies and Galois extensions
To understand Reed-Solomon codes, it is essential to know about Galois bodies and Galois extensions. This is because a Reed-Solomon code is a code constructed based on Galois body theory, and its processing unit, a symbol, is the source of a Galois extension. A "body" is a special set, which is characterized by the fact that the four arithmetic operations are closed inside the set. For example, the whole real numbers and the whole complex numbers constitute a body. These bodies have an infinite number of elements, but there are also bodies with a finite number of elements, which are called Galois bodies (Galois fields). A Galois field can be constructed by the set of remainders of an integer divided by its prime. For example, the Galois field GF(5) is the set of remainders of an integer divided by 5 and consists of the five primes 0, 1, 2, 3, and 4. Addition and multiplication in GF(5) can be performed as in Tables 1-1 and 1-2.
To see whether subtraction can be performed, we can check whether all the roots have an inverse with respect to addition: the inverses of 0,1,2,3,4 are 0,4,3,2,1 respectively, which shows that GF (5) can be subtracted. Similarly, to check whether division can be performed, we can check whether the non-zero source has an inverse with respect to multiplication: the inverses of 1,2,3,4 are 1,3,2,4 respectively, so we know that GF(5) can be divided. Reed-Solomon codes are often constructed on the basis of GF (2); GF (2) has two originals, 0 and 1, which can be used to perform quadrature operations as in Equation 1-1.
【Equation 1-1】
Next, consider a polynomial whose coefficients are the origin of GF (2) (called a polynomial on GF (2)): the set of remainders of a polynomial on GF (2) divided by an irreducible polynomial on GF (2) is a Galois extension. For example, the set of remainders obtained by dividing a polynomial over GF (2) by an irreducible polynomial of degree 4 over GF (2) (Equation 1-2) contains all 16 polynomials over GF (2) of degree 3 or less, and constitutes a Galois extension GF (2^4) The source of GF (2^4) is shown in Table 1-3.
【Equation 1-2】
There are three types of original representations of Galois expansions: polynomial, power and vector representations. Since Galois expansions are also bodies, they can be used for quadratic operations. Polynomial representation is convenient for addition and subtraction, and power representation is convenient for multiplication and division.
*Supplement 1-1
The inverse of an element is the element that, when computed, becomes the unit element. For example, consider the inverse of 4 with respect to addition. From Table 1-1, when 1 is added to 4, it becomes 0 (unit source). Therefore, the inverse of 4 with respect to addition is 1. If the inverse source for addition exists, subtraction by that source is possible. This is because subtraction can be changed to addition by using the inverse source, as shown in Equation 1-3. From the above, subtraction can be performed if all of the sources have an inverse source related to addition. The same can be applied to multiplication. However, it should be noted that the unit element for multiplication is 1, and there is no inverse element of 0 (there is no division by 0).
【Equation 1-3】
*Supplement 1-2
An irreducible polynomial on GF (2) is a polynomial that cannot be factorized into a product of polynomials on GF (2).
※Supplement1-3
To construct Galois extensions, we need irreducible polynomials. However, to construct Galois expansions used in Reed-Solomon codes, it is not enough to use irreducible polynomials, but primitive polynomials are needed.
Chapter 2 : Coding and decoding of Reed-Solomon codes
The processing unit of a Reed-Solomon code, the symbol, is the source of the Galois extension GF(2^m). The symbol of a commonly used Reed-Solomon code is 8 bits and is the source of GF(2^8). For simplicity, we will take the Reed-Solomon code on GF(2^4) shown in Table 1-3 as an example to explain coding and decoding in the following.
2-1. Design of codes
Designing Reed-Solomon codes means determining the following two parameters.
- Number of information symbols (k): Unit of information to be encoded (k x 4 bits)
- Number of correctable symbols (t): Number of symbols that can be corrected for errors
When the number of corrected symbols is t, the number of redundant symbols required is 2t. When k and t are determined, the number of code symbols n is automatically determined (Equation 2-1).
【Equation 2-1】
Here, the maximum value of n of the Reed-Solomon code on GF(2^4) is 15, so k and t must be determined so that n is less than 15.
２－２． Encoding
The coding requires a generating polynomial, which is shown in Equation 2-2.
【Equation 2-2】
Coding is the task of finding redundant symbols, which can be obtained as the remainder of the information polynomial divided by the generator polynomial.
A concrete example of coding for the case of k=11 and t=2 is shown below. The information bit series to be encoded is converted into symbols (Figure 2-1) and expressed by an information polynomial (Equation 2-3).
【Equation 2-3】
The generating polynomial is expressed by Equation 2-4.
【Equation 2-4】
The redundancy polynomial is obtained as the remainder of dividing the information polynomial by the generation polynomial (Equation 2-5).
【Equation 2-5.】
From the above, the coded polynomial becomes Equation 2-6, and the bit series after coding can be obtained as shown in Figure 2-2.
【Equation 2-6.】
２－３． Decoding
The decryption procedure is shown below (Step1 to Step5)
Step1: Obtain the syndrome from the received series.
Step2: Find the error position polynomial using the syndrome.
Step3: Find the root of the error location polynomial, which indicates the error location.
Step4：The error evaluation polynomial is used to find the magnitude of the error.
Step5：The error position and magnitude obtained are used to perform the correction and obtain the decoding result.
The Peterson method, Berlekamp-Massey method, and Euclid method are known as the methods of Step 2. Compared with the Peterson method, the Berlekamp-Massey method or the Euclid method is often used because it is computationally inexpensive.
※Supplement 2-1
Regarding the design of Reed-Solomon codes, in addition to the number of information and correction symbols, it is actually necessary to choose the roots of the primal and generator polynomials. However, these choices do not affect the error correction capability itself and are not discussed here.
※Supplement 2-2
The maximum number of code symbols n of a Reed-Solomon code on GF(2^m) is 2^m -1.
Chapter 3 : Correcting Capability of Reed-Solomon Codes and Their Selection
リードソロモン符号の訂正能力tは、式3-1で表わされる。但し、nは符号シンボル数、kは情報シンボル数である。
【Equation 3-1】
Since n-k represents the number of redundant symbols, it can be seen that 8 redundant symbols should be added to correct an error of 4 symbols and 16 symbols to correct an error of 8 symbols. From this, the minimum distance dmin of Reed-Solomon code can be expressed by Equation 3-2.
【Equation 3-2】
We now consider the singleton limit equation (Equation 3-3).
【Equation 3-3】
The singleton limit formula means that the minimum distance is only less than "the number of redundant symbols + 1". From Equation 3-2 and Equation 3-3, the minimum distance of Reed-Solomon code is n-k+1. Therefore, the Reed-Solomon code satisfies the singleton limit equation with an equal sign, and in this sense, it is a very good code.
It should be noted that the error correction of Reed-Solomon codes is performed in units of symbols. n=15, k=11, t=2 for Reed-Solomon codes on GF(2^4), Figure 3-1 shows examples of correctable and uncorrectable codes. From Fig. 3-1, it can be seen that correctability is not determined by the number of error bits, but by the number of error symbols.
Finally, let us consider how to determine the correction capability of a Reed-Solomon code when it is applied to an actual system. The system has an error rate to be guaranteed, and the Reed-Solomon code is to have the correction capability t necessary to achieve it. The value can be obtained by calculating the error rate using Equation 3-4, where Ps is the symbol error rate occurring in the communication channel.
【Equation 3-4.】
However, Equation 3-4 is based on the assumption that symbol errors occurring in the communication channel are random. In reality, it is rarely completely random, and two or three consecutive symbol errors may occur frequently. In such cases, the error rate after decoding deteriorates significantly. It is not unusual for the degradation to be on the order of tens or hundreds of thousands of times. If the error rate calculated by Equation 3-4 is used as the basis for determining the correction capability, the user will be shocked when the system is put into operation. To avoid this, it is necessary to grasp the characteristics of the symbol error distribution and estimate the error rate using a formula that takes this into account.
If the selection of necessary Reed-Solomon is completed by referring to this technical explanation, the next step is to design RTL. Using the Reed-Solomon code generation tool provided by Siglead, RTL based on our IP (Si2520) is automatically generated by simply specifying various parameters of Reed-Solomon codes. Also, it is possible to specify the loss of error correction, external memory, and whether or not to limit the number of error correcting symbols.
Siglead offers a service to propose the most effective error correcting code among several error correcting codes including not only Reed-Solomon codes but also other existing error correcting codes and Siglead original error correcting codes. In combination with the contracted design service, a total solution including peripheral circuits can be provided.
※Supplement 3-1
The explanation of the minimum distance is given in "Technical Explanation of Error Correcting Codes".
※Supplement 3-2
A code that satisfies the singleton's limit formula with an equal sign is called a Maximum Distance Separable Code (MDS code).