—Reed-Solomon and related codes have recently be- come very important for erasure correction in large disk arrays used in data centers. In this paper, we will implement a 3- error correcting Reed-Solomon encoder and decoder over the ﬁeld GF(9) generated by the primitive polynomial D2+D+ 2 over GF(3) and the decoding is carried out by the Berlekamp. We simulate the encoder and decoder using Monte-Carlo simulations over the 9-ary symmetric channel that outputs the correct symbol with probability ( 1p), and outputs one of the other 8 possible incorrect symbols with probability p=8. Then, we compare the simulated probability of symbol error P(E)of out code with the union upper bound. Index Terms —Reed-Solomon Code, Berlekamp, Galois Field, Generator Polynomial, M-ary symmetric channel, union upper bound. I. I NTRODUCTION CHANNEL coding is basically from the class of signal transformations designed to improve the communication performance by enabling the transmitted signal to better resist the effects of various channel impairments such as noise fading and jamming [1]. The goal of channel coding is to improve the bit error rate (BER) performance of power limited and/or bandlimited channels by adding redundancy to the transmitted data [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18]. The mechanism by which Reed-Solomon codes correct errors is that the encoder adds redundant bits to the digital input data block. The decoder attempts to correct and restore the original data by removing the errors that are introduced in transmission, due to many reasons that might be the noise in the channel or the scratches on a CD. There are different families of Reed- Solomon codes and each has its own abilities to correct the number and type of errors [19], [20], [21], [22], [23], [24], [25], [26]. These codes are linear and a subsection of BCH codes and can be denoted as RS( n;k) with s-bit (Where s are symbols represented as a bit) symbols. An n-symbol codeword is made by the kdata symbols of s bits each and the encoder adds parity bits. Errors in a codeword can be corrected by the decoder up to tsymbols where, 2t=nk. II. D ESIGN SPECIFICATIONS In this project, the Reed-Solomon (RS) code has the fol- lowing speciﬁcations deﬁned by Table 1.1. Elyes Balti is with the Wireless Networking and Communications Group, Department of Electrical and Computer Engineering, The University of Texas at Austin, Austin, TX 78712 USA e-mail: ebalti@utexas.edu.TABLE I: Code Speciﬁcations Parameter Speciﬁed value Galois Field GF(9) p 3 m 2 n 8 k 2 t 3 Primitive polynomial 2 +D+D2 III. E LEMENTS OF GF(9) A. Representation The elements of GF(9) are represented in terms of powers, polynomials, and tuples representations as follows TABLE II: Representation of elements of GF(9) Power of Polynomial Tuple 0 0 0 0 01 0 1 1 1 0 22 +1 2 1 32 +2 2 2 42 0 2 52 2 0 6 +2 1 2 7 +1 1 1 B. Addition Table TABLE III: Addition Table + 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 4 7 3 50 2 6 7 51 4 60 3 2 2 2 51 6 5 70 4 3 3 5 4 7 2 61 0 4 40 6 5 21 3 7 5 5 20 7 6 3 41 6 6 30 1 7 4 2 5 7 7 6 2 40 1 5 3 2 C. Multiplication Table TABLE IV: Multiplication Table x 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 0 2 3 4 5 6 71 20 2 3 4 5 6 71 30 3 4 5 6 71 2 40 4 5 6 71 2 3 50 5 6 71 2 3 4 60 6 71 2 3 4 5 70 71 2 3 4 5 6 IV. MATLAB R EPRESENTATION During the MATLAB simulation, I adopt the power repre- sentation of the elements of GF(9). For the sake of simplicity, I also used the following representation. TABLE V: MATLAB Representation Powers MATLAB Representation 0 -1 0= 1 0 11 22 33 44 55 66 77 V. G ENERATOR POLYNOMIAL The generator polynomial g(D)of this RS-code has a degree of 2*t = 6, and 2*t+1 = 7 terms. The roots of g(D) are ; 2; 2; 3; 4; 5; 6. The generator polynomial can be factorized as follows: g(D) = (D )(D 2)(D 3)(D 4)(D 5)(D 6); (1) After expanding g(D), it can be written as follows g(D) = 5+ 4D+ D2+ 7D3+ 2D4+ 6D5+D6;(2) Note thatg(D)is a monic polynomial. In MATLAB, a given polynomial is represented by a vector having the coefﬁcients of the polynomial. I adopt representation each polynomial starting by the coefﬁcient relative to the lowest degree. For example, the generator polynomial is represented as follows g= [5 4 1 7 2 6 0] ; (3) VI. E NCODING In this project, I adopt the systematic encoding of the codeword. Assume that we have a polynomial message of two elements. To perform the systematic encoding, we need to go through the following steps 1) T(D) =D2t* message(D). 2) R(D) = T(D) mod g(D). 3) Tx(D) = T(D) - R(D).VII. 9-A RYSYMMETRIC CHANNEL This channel is designed so that various errors can be introduced into the transmitted codeword. Let is consider a random variable Xhaving the same length of the codeword (n = 8) that follows the Bernoulli distribution with probability prob if an error occurs and (1 - prob) if there is no error. Randomly, we generate the vector Xtaking ”1” if an error occurs and ”0”, otherwise. An example of the random variable X generated with prob = 0.4 is X= 0 1 1 1 0 1 1 0 (4) This is equivalent to there are 5 errors are introduced to the codeword at the positions 2, 3, 4, 6, 7. The output of the 9-ary symmetric channel is the received codeword Rx(D). VIII. D ECODING A. Syndrome Computation The syndrome polynomial has (2t = 6) terms and each coefﬁcientSiis given by Si=Rx( i);1i6; (5) IfSiare all zeros for 1i6, then there is no error in the received codeword Rx(D). We can also check whether the codeword is altered by error or no by computing the summation of all the coefﬁcients of the syndromes as follows h=6X i=1Si; (6) ifhis zero, the codeword is received without an error, otherwise, the codeword is corrupted by the errors introduced by the 9-ary symmetric channel. B. Error Locator Polynomial: Berlekamp Algorithm To perform the decoding, we need to compute the error locator polynomial (D)via the Berlekamp algorithm. The following ﬁgure illustrates the iterative way to compute (D). 3 Fig. 1: Berlekamp Algorithm [27]. C. Error Locations and Roots: Chien Search Algorithm The problem is to ﬁnd the roots of the error locator polynomial (D)over the ﬁnite ﬁeld GF(9). Chien substitutes the elements in the generator’s order 1, 2, 3,...etc, into the (D)of degreec. The Chien search is based on two observations Each non-zero may be expressed as i for somei , where is a primitive element of GF(9), i is the power number of primitive element . Thus the powers ifor 0i < 8cover the entire ﬁeld (excluding the zero element). The following relationship exists: ( i) =0+1( i) +2( i)2+:::+c( i)c = 0;i+ 1;i+ 2;i+:::+ c;i;(7) We deﬁne each ( i)as the sum of a set of terms f j;ij0 jcg, from which the next set of coefﬁcients may be derived by j;i+1= j;i j; (8) In this way, we may start at j;0=j, and iterate through each value ofiup to 8. If at any stage the resultant summation iszero, i.e.Pt j=0 j;i= 0, then( i) = 0 also, so iis a root. In this way, we check every element in the ﬁeld. Once the roots are found via the Chien Search algorithm, we determine the error locations errorlocas the inverses of the roots of(D). To illustrate the case, let’s take the following example 1)(D) = 5+D+ 3D2+ 2D3+ D4. 2) Apply Chien Search algorithm to ﬁnd the roots which are ; 2; 4; 5. 3) The error locations are the inverses of the roots which are 7; 6; 4; 3. In terms of polynomial, the error locations polynomial is L(D) =D3+D4+D6+D7. D. Error Evaluator Polynomial The error evaluator polynomial (D)is given by (D)S(D) = (D)modD2t; (9) (D)can be also interpreted as the convolution of (D)and S(D). E. Error Magnitude The error magnitude eivis the error magnitude in the iv position in the codeword, vis a value less than the error- correcting capability tof the code. eivcan be expressed as follows eiv= ( iv) 0( iv); (10) 0(D)is the formal derivative of the error locator polynomial, (D), and is the primitive element of the Galois ﬁeld GF(9). In our example, iv= 3;4;6;7. F . Error Pattern Polynomial Once we determine the error magnitudes at the error loca- tions, the error pattern polynomial e(D)is given by e(D) =X veivDiv; (11) G. Error Correction Checking This code can only correct 3 or fewer errors. To check whether the received codeword is correctly decoded or not, we need to compute the difference between the received codeword and the error pattern. If the difference is equal to the transmitted codeword, then the decoding is successful, otherwise, the code is unable to correct the errors. IX. T HEORETICAL SYMBOL ERROR PROBABILITY UPPER BOUND For a t-error-correcting block code is used strictly for error correction on a 9-ary symmetric channel with transition probability p, the probability that the decoder commits an erroneous decoding is upper bounded by [28, Eq. (3.26)] P(E)nX i=t+1n i pi(1p)ni; (12) 4 X. MATLAB S IMULATION A. Scenario Illustration We ﬁrst generate a message polynomial as follows Message = 5 6 (13) Then, perform the systematic encoding using the MATLAB function Systematic encoding as follows Tx= 7 0 1 2 3 4 5 6 (14) Using the function Nine Ary symmetric channel , we intro- duce random errors with probability 0.4 to the transmitted codeword. AT this simulation, Xand the received codeword Rx are given by X= 1 0 0 0 0 1 0 1 (15) Rx=1 0 1 2 3 3 5 4 (16) The next step is to compute the syndrome Sand Check sum using the Syndrome computation function. The result shows the following S= 6 3 6 6 4 3 (17) Checksum = 1 (18) Check sum is not zero (-1 over GF(9)), which means that the received codeword is corrupted by the error. After calling the function rsberlekamp , we get the error location polynomial (D)and the error evaluator polynomial (D). The results show the following (D) = 6 4 61 (19) (D) = 4 7 1 (20) To get the roots and the error locations, we call the function Chien search roots . The simulation results show that Roots = 1 7 (21) errorloc= 7 1 (22) Equivalently, the relative error locations polynomial is D+D7. We call the function error value to compute the error mag- nitude. The results shows that error = 0 1 (23) The next step is to compute the error pattern polynomial by calling the function error pattern . The result shows that errorpatternpoly = 31111 51 5 (24) To get the decoded codeword, we compute the difference between the received codeword and the error pattern poly, by calling the function subtraction . The results shows that Decoded = 7 0 1 2 3 4 5 6 (25) We observe that the decoded codeword is the same as the transmitted codeword. Hence, the decoding is successful. In addition, we can predict this result since the number of error is 3 with is equal to the error-correction capability t. What happens if more than terrors corrupt the transmitted codeword. Let’s illustrate this case by a simulation.For the same systematic transmitted codeword Tx used in the ﬁrst simulation, we generate the random variable Xthat introducing 6 errors (more than t= 3). The vector X is given by X= 1 1 0 1 1 0 1 1 (26) The received codeword Rx is Rx= 6 1 1 7 4 4 0 3 (27) The error pattern polynomial errorpatternpoly =11111 511(28) The decoded codeword in this case if given by decoded = 1 4 6 5 3 4 5 3 (29) Deﬁnitely, the decoded codeword is different from the trans- mitted codeword Tx. Hence the decoder failed to correctly decode the received codeword, since more than t errors (6 errors) corrupt the transmitted codeword. XI. C ODEWORD ERROR PROBABILITY To compute the symbol error probability, we create a vector of probability values of the 9-ary symmetric channel as follows prob = 0:1 : 0:1 : 1. For each value of a given probability, we generate 1000 messages/codewords, and compute the average total number of errors that are not corrected. Repeat this scenario for all the values of the probability of the 9-ary symmetric channel, so that to get the symbol error probability. 0 0:2 0:4 0:6 0:8 1104103102101100 9-Ary Symmetric Channel Error ProbabilityCodeword Error ProbabilityReed Solomon Code (8,2) Union Upper Bound Fig. 2: Codeword error probability. Figure 2 shows the variations of the symbol error probability with respect to the probability of the transition of 9-ary symmetric channel. Clearly, the decoder achieves better error performance compared to the upper bound of uncorrected symbol error probability of the linear block code. In addition, the upper bound is not the tightest to the error performance since there is a noticeable gap between the two curves. Clearly, the error performance achieved by the RS decoder with 3 error correcting is much better than for the linear block code. 5 XII. C ONCLUSION Reed-Solomon codes in comparison to linear block codes are difﬁcult to implement but their performance is much better and consistent than linear block codes since they can handle long bursts of errors. These codes showed good performance compared to the upper bound of the symbol error probability of linear block codes. Hence with the system that requires good performance but it can’t handle complex architecture then RS codes might be more suitable for the practical purpose.