WIXLIB

be used. Some of them are personal computers, industry computers, embedded systems, specific assembled hardware devices etc. Each of them arecharacterized by specific requirements and impose several contraints.Implementation of decoding algorithms both in hardware and softwaremay be accomplished in different ways. To construct decoder there can beused several mechanisms and algorithms which usually come from algebradomain. Algorithms are built with use of Galois field arithmetic which includes basic operations like addition, multiplication and calculation of fieldelements and operations which involve addition, multiplication, division andcalculation of division’s remainder for polynomials. There are vast of electronical elements, which may be used to construct hardware decoder.However this is not simple task to build efficient decoder, when thereare several ways to implement it. Furthermore, there are different typesof algorithms, including bounded distance decoding algorithms, list decoding algorithms and soft decoding algorithms and there may be confusion tochoose right one without knowing their characteristics of processing. Analysis of complexity and scalability is done to find out the main advantages anddisadvantages of algorithms. There will be processed evaluation of presentedsolutions of implementation of algorithms.1.1Structure of documentMaster thesis report is divided into several chapters. First is presented information about Galois fields. There are described what are Galois fields, howarithmetic operations work for them, how can be they represented in computer systems. Next chapter describes Reed-Solomon codes. There are giventwo definitions of Reed-Solomon code and is shown that these definitionsgenerate the same code. Next chapter presents decoding algorithms. First isgiven introduction to basic decoding methods like complete decoder, standardarray and syndrome decoding, then cyclic decoding, Peterson-GorensteinZierler algorithm, Berlekamp-Massey algorithm, Sugiyama algorithm. Thereare described also auxiliary like Chien search and Forney algorithm. Thereis described modified Sugiyama algorithm which employs decoding with erasures. Last sections in the chapter presents Guruswami-Sudan algorithm.Guruswami-Sudan algorithm can employ Kötter algorithm for polynomialinterpolation, Roth-Ruckenstein algorithm for polynomial factorization andKötter-Vardy algorithm for transformation of soft information to hard information. Next chapter gives overview how algorithms were implemented bothin software and hardware. Next, there are chapters which describe simula-7

tion environment, results from experiments and evaluation of results. Lastchapter includes conclusions and future work topics.1.2Research questionsThere are several decoding algorithms of Reed-Solomon code and theydiffer in their features like computional complexity and error-correction capability. Other factors which influence work of algorithms are number ofoccured error, codeword length, number of control elements etc. Constructing decoder, there can be defined several requirements like time of decoding,ability to decoding specific number of errors or complexity of algorithm. Firstresearch question which is used to solve this problem is:1. What are the features of scalability and complexity ofimplemented algorithms?Decoding algorithms usually consist of several steps. Some of these stepscan be executed by different algorithms. Algorithms may be also modifiedin order to improve their work. Question which is used to find what can bedone to improve algorithm work on algorithm level is:2. What mathematical functions and modifications on algorithmlevel can improve performance of decoding algorithms?Work of algorithms can be also improved by using features of softwareand hardware. Some steps of algorithms can be done by parallel units orfor instance some precomputed data may be used to decrease time of decoding. Question which is used to find what can be done to improve work ofalgorithms on software and hardware level is:3. Which features of software and hardware can improve performance of decoding algorithms?1.3Aims and objectivesAim of the master thesis is to evaluate implemented decoders of ReedSolomon code under criteria of scalability and complexity.There are following objectives which are fullfiled in order to answer research questions: preparation of mathematical functions which concern mainly Galoisfields, polynomial arithmetic, matrices and vectors. implementation of algorithms in software and hardware, finding out improvements for algorithms, simulation of proposed solutions in simulator,8

evaluation of proposed solutions in terms of complexity and scalability.1.4Research methodologyTo get overview of current knowledge in decoding algorithms of ReedSolomon code area, background study is done. Main research method used inthe master thesis is an experiment. To get done experiment, algorithms fromgiven set must be implemented. Set consists of Peterson-Gorenstein-Zierleralgorithm, Berlekamp-Massey algorithm, Sugiyama algorithm, GuruswamiSudan algorithm. Hard-decision algorithms which include Peterson-GorensteinZierler algorithm, Berlekamp-Massey algorithm, Sugiyama algorithm, GuruswamiSudan algorithm are popular methods for decoding Reed-Solomon words [26]and Koetter-Vardy algorithm is a popular soft-decision algorithm [21]. Thatwas the criterion to complete the set. There is created list of criteria underwhich algorithms and decoders will be compared. Implementation is donein C programming language. First are implemented basic mathematicalfunctions which include arithmetic of Galois field, arithmetic of polynomials,functions needed for operations with matrices and vectors. After this step,implementation of selected decoding algorithms is done. To provide usefulinformation how algorithms work in software, simulator is created. Simulator allows to define Galois fields of characteristic 2 and of chosen exstension,create Reed-Solomon code of given number of information words and control words, choose number of random selected errors. The other advantageof simulator is that it can be used to validate correctness of implementedalgorithms. Simulator may gather information like time of decoding of received word, how much memory was used during decoding process, whetherreceived word was correctly decoded. Implementation of decoding algorithmsin hardware is preceded by design of decoder. The most popular decoding algorithms used in hardware employ error locator polynomials to compute theresult of decoding [27]. Peterson-Gorenstein-Zierler algorithm, BerlekampMassey algorithm, Sugiyama algorithm use error locator polynomials duringdecoding operation. There must be chosen which electronic elements canbe used and how to solve construction of decoder. Implementation is donein VHDL language. Correctness of developed algorithms is checked in ISimsimulator which provides valuable information about time of decoding, resultof decoding. Evaluation of decoding algorithms is mainly based on resultsdelivered in simulation process conducted in software and information gathered from simulator ISim.Independent variables of experiment are: length of codeword,9

number of control elements, number of occured errors, noise in the communication channel, number of threads.Dependent variables are: time of decoding, memory required, status of decoding (no errors, corrected, not correctable), quality of decoding (correctness of decoding, number of results in listdecoding), complexity of decoder (number of executed loops, number of electronicelements in circuit).To evaluate scalability of algorithms, independent variables of experimentare manipulated. Algorithms’ processing may (but not must) vary with different values of number of errors, length of codeword, number of controlelements etc. Threads may be used to lessen processing time of decoding.Number of control elements and length of codeword may affect complexityof hardware decoder, because mostly of length of registers. As a result ofexperiment there will be given an answer how these independent variablesaffect dependent variables. Simulator is used to provide information aboutprocessing of algorithms. Gathered data will be evaluated in relation toscalability and complexity.Threats to internal validity: implementation of algorithms is affected by programming skills of programmer, so the theoretical decoding process may be different thanreal life decoding process. That’s why there is not compared exacttime of decoding between different algorithms, but complexity - howworking of algorithms is affected by independent variables. there can occur confounding variables during testing, for example exchanging content of cache memory can affect working of big data structures, while it is not problem for small data structures.Threats to external validity: there is evaluated set of Reed-Solomon codes, but not all codes areincluded in this set, because there is no time to evaluate them all.Codes to evaluate are chosen so, that there are representatives fromReed-Solomon codes of length 7, 15, 31, 63. Using longer codes takestoo much time to evaluate them. algorithms are implemented on x86 machine and they use specific features of this hardware. However, there are no tested on other machines,whose features may affect decoding process.10

disrupting of received vector from communication channel is occuredby noise. The method used for noise generation is designed by authorof master thesis. However there are some “standard” channel models like AWGN (Additive White Gaussian Noise) etc., where decodingalgorithm can work differently.11

2.2.1Galois fieldsIntroductionReed-Solomon codes use as code symbols elements from extended fieldswhich are also known as extended Galois fields [9]. Galois field is a finiteset of elements with defined operations of addition and multiplication, whichhas following properties: result of adding or multiplying two elements in Galois field is an elementin the same Galois field, identity element of addition is 0, each element in Galois field has additive inverse, identity element of multiplication is 1, each element in Galois field hasmultiplicative inverse, addition and multiplication are commutative and associative, multiplication distributes over addition.Galois field which consists of q elements is denoted as GF (q). Number ofelements of GF (q) is pm , where p is a prime number which is called characteristic of field, and m is called extension order. Field A is extension of fieldB, if field B is a subfield of field A. Subfield of field A is field B, if eachelement of field B lies in the field A and properties of the field B are satisfiedfor operations of addition and multiplication which come from field A.Following set describes elements in GF (q):{0, α0 , α1 , . . . , αq 2 } {0, 1, α, . . . , αq 2 }Element α in GF (pm ) is the root of primitive polynomial w(x) of degreem with coefficients from field GF (p). A primitve polynomial w(x) is irreducible and divides polynomial xn 1, where n pm 1, and does not divideany polynomial xz 1, where z n. Polynomial w(x) of degree m is irreducible, if it is not divided by any polynomial of degree z, where 0 z m.Roots of polynomial w(x) of degree m with coefficients from GF (p) are allprimitive elements of GF (pm ). Primitive elements of GF (pm ) are definedas elements, which has multiplicative order equal to pm 1. Multiplicativeorder of element αi is such natural number r, which satisfies (αi )r 1 for0 i q 2. Reciprocal polynomials of primitive polynomials are alsoprimitive polynomials. Reciprocal polynomial for polynomial w(x) of degreem satisfies:mw (x) xw0 w( x1 )12

If reciprocal polynomial is identical to original polynomial, then such polynomial is called self-reciprocal.2.2Representation of elements in GF (2m)Reed-Solomon codes are often based on Galois field of characteristic 2, because elements in GF (2m ) can be expressed as binary vectors, and arithmeticunits for binary elements in GF (2) can be used.2.2.1Polynomial representationElements in GF (2m ) can be expressed as [9]:iαi R(α ) (x) xi mod p(x) ,where p(x) is primitive polynomial over GF (2m ). Element αi in GF (2m ) canbe expressed as m-dimensional vector of binary coefficients of polynomiali(αi )(αi )(αi )(αi )R(α ) (x) (R0 , R1 , . . . , Rm 2 , Rm 1 ). This method is often used in digital technology. Element 0 R(0) (x) is represented as m-dimensional vectorfilled with zeroes.AdditionAdding two elements in GF (2m ) in polynomial representation can be donewith XOR function:ijα α m 1Xij(Rn(α ) Rn(α ) )xnn 0Furthermore:0 αi αi 0 αiChoice of primitive polynomial affects addition operations GF (2m ).Example 2.1.Field GF (8) can be created by primitive polynomials:p1 (x) x3 x 1 and p2 (x) x3 x2 1. Polynomial p2 (x) is reciprocalpolynomial of p1 (x). For field created by p1 (x) is true that α3 α 1, andfor field created by p2 (x) is true that α3 α2 1.13

SubtractionSubtraction is equivalent to addition in fields of characterstic 2.αi αj αi αjMultiplicationMultiplication of two elements in GF (2m ) for polynomial representationis done as follows:Furthermore, true is that:0 · αi αi · 0 0DivisionDivision of two elements in GF (2m ) for polynomial representation is doneas follows:αi αi · α jαjAdditive inverseEach element in GF (2m ) is also own additive inverse:αi αiMultiplicative inverseIn GF (2m ) multiplicative inverse can be expressed as:( mα2 1 i for 1 i 2m 2,α i 1for i 0.Element 0 doesn’t have multiplicative inverse.2.2.2Positive integer representationElements in GF (2m ) can be expressed as [9]:iαi N (α ) logα (αi ) 1 i 1Element 0 is express as N (0) 0.14

AdditionAddition of two elements in GF (2m ) in positive integer representation isas follows:(jij(N (α ) Z(N (α ) N (α ) ) 1) mod (2m 1) 1 for i j,αi αj 0for i j.iZ(N (α ) ) denotes Zech logarithm for element αi .Furthermore, true is that:0 αi αi 0 αiMultiplicationMultiplication of two elements in GF (2m ) in positive integer representation is as follows:ijαi · αj (N (α ) N (α ) 2) mod (2m 1) 1Furthermore, true is that:0 · αi αi · 0 0Principles for subtraction, division, additive inverse and multiplicativeinverse are the same as for polynomial representation.2.2.3Vector representationThere is given following primitive polynomial: Dany jest wielomian pierwotnyp(x) pm xm pm 1 xm 1 . . . p1 x p0 ,which can be used for creation of GF (2m ). With this primitive polynomialgenerated is periodic sequence, which can be used for representation of elements in GF (2m ) [9]. Equation for j m’s element sj m of periodic sequenceis as follows:sj m sj m 1 pj m 1 sj m 2 pj m 2 . . . sj pjAt the beginning of algorithm there must be stated which element initializes sequence. During writing this master thesis, following elements wereused:s0 1, s1 0, s2 0, . . . , sm 1 0.Representation of elements in GF (2m ) is as follows:15

element 0 is denoted as m-dimensional vector of zeroes – (0, 0, . . . , 0), {z}m element αi for 0 i 2m 2 is denoted as following vector –(si , si 1 , si 2 , . . . , si m 1 ).Addition in vector representation is done the same as for polynomialrepresentation, but method for multiplication for polynomial representationcannot be used for vector representation.2.3Zech logarithmsZech logarithms can be used for addition of elements in GF (2m ) in logarithmic domain [9]. Zech logarithm is defined as:αZ(x) 1 αxZ(x) logα (1 αx )Addition of two elements in GF (2m ) can be done as follows:αi αj αi (1 αj i ) αi αZ(j i) αi Z(j i)For GF (2m ) it is assumed that Z(0) and Z( ) 0.For GF (2m ) it is true that:(Z(x) x)2i mod (2m 1) Z((2m 1 x)2i mod (2m 1))Z(x)2i mod (2m 1) Z(2i x mod (2m 1))(2.1)(2.2)Using equations 2.1 and 2.2 there can be created table of Zech logarithms.Example 2.2.There will be computed table of Zech logarithms for field GF (8) created bypolynomial p(x) x3 x 1. It is true that:α3 α 1andαZ(x) αx 1,so Z(1) 3. Using equations 2.1 i 2.2 and assigning m 3, x 1, there canbe computed next Zech logarithms.Equation 2.1:dla i 0(Z(1) 1)20 mod (23 1) Z((23 1 1)20 mod (23 1))(3 1)1 mod 7 Z(6 · 1 mod 7)2 mod 7 Z(6 mod 7)2 Z(6)16

dla i 1(Z(1) 1)21 mod (23 1) Z((23 1 1)21 mod (23 1))(3 1)2 mod 7 Z(6 · 2 mod 7)4 mod 7 Z(12 mod 7)4 Z(5)dla i 2(Z(1) 1)22 mod (23 1) Z((23 1 1)22 mod (23 1))(3 1)4 mod 7 Z(6 · 4 mod 7)8 mod 7 Z(24 mod 7)1 Z(3)Equation 2.2:dla i 1Z(1)21 mod (23 1) Z(21 · 1 mod (23 1))3 · 2 mod 7 Z(2 mod 7)6 Z(2)dla i 2Z(1)22 mod (23 1) Z(22 · 1 mod (23 1))3 · 4 mod 7 Z(4 mod 7)5 Z(4)Z( ) 0Z(3) 12.3.1Z(0) Z(1) 3Z(4) 5Z(5) 4Z(2) 6Z(6) 2Imamura algorithmImamura algorithm is an iterative algorithm for computing Zech logarithms, which can be easily implemented programmatically [16].Imamura algorithm is as follows (logα (0) doesn’t exist and is denoted aslim logα x ):x 0m 21. Each element of GF (2m ) express as polynomial R(i) (x), where i {0, 1, α, . . . , α217}.

α α2 α3 α4 α5 α61 α α2 α3 α4 α5 α60 α3 α6 α α5 α4 α2 00011αα α3 0 α4 1 α2 α6 α5α2 α6 α4 0 α5 α α3 1α3 α 1 α5 0 α6 α2 α4α4 α5 α2 α α6 0 1 α3α2α3α410αα6 α6 α2 α5 1 α4 α3 α0α5 α5 α4 α6 α3 α2 1Table 2.1: Addition table for elements in GF (8) created by polynomialp(x) x3 x 1.2. For each polynomial R(i) (x) compute N (logα (i)) R(i) (2) in the fieldof integer numbers.3. Assign:(N (logα (i)) 1 for N (logα (i)) odd,N (Z(logα (i))) N (logα (i)) 1 for N (logα (i)) even.4. With values N (logα (i)) and N (Z(logα (i))), find Z(logα (i)).Example 2.3.Example of calculation of Zech logarithms for field GF (8) created by polynomial p(x) x3 x 1:logα (i) 0123456iR(i) (x) N (logα (i)) N (Z(logα (i))) Z(logα (i))000101110 αx233α2x24563αx 132142αx x675α 5 x2 x 176462αx 1542Results are the same as for example 2.2.18

·01α α2 α3 α4 α5 α60000101α α2 α3 α4 α5 α6α000000α α2 α3 α4 α5 α6 10 α2 α3 α4 α5 α6 1 αα2α3 0 α3 α4 α5 α6 1 α α2α4 0 α4 α5 α6 1 α α2 α3α5 0 α5 α6 1 α α2 α3 α4α6 0 α6 1 α α2 α3 α4 α5Table 2.2: Multiplication table for elements in GF (8) created bypolynomial p(x) x3 x 1. 01.α2001.α2α2m 2m 3α2mα2 2 1m 2m110.α2 3 1.0.0α2 2 mα2 3.α2 3 2m 2αm 3α22m 2m 3α2αm1 ααm 32m 3m1 2m 2α2m 20Table 2.3: Addition table for elements in GF (2m ).19

·01.0000101.0.m 3α20m 3α2m 3.m 2.m 30α2m 20α2α20m 2α2.m 3α2m 2α2.m 2α2α2·mα2 3mα2 3·2m 2α·mα2 3mα

do this step in a di erent way. They are called bounded distance decoding algorithms, because they produce one unique result. In 1997 Sudan developed algorithm for decoding Reed-Solomon code-words, which was improved by Sudan and Guruswami in 1999 [7]. This algorithm, in contradistinction to bounded distance decoding algorithms,