COMPLETE WEIGHT ENUMERATORS AND PROBABILITY OF UNDETECTED ERROR FOR SOME REED-SOLOMON CODES by KAIMING HO k- B.A.Sc. (Electrical Engineering), University of Waterloo, Canada, 1993 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E DEGREE OF MASTER OF APPLIED SCIENCE in T H E FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA August 1995 © Kaiming Ho, 1995 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of bU-c^-caJC . b>A \ ^ sur. -O The University of British Columbia Vancouver, Canada Date M~<M,- i DE-6 (2/88) Abstract The Hamming weight enumerators for Reed-Solomon codes are known, but do not often adequately describe the structure of the codes. Complete weight enumerators, on the other hand, describe the code in more detail, but are more difficult to determine. A procedure described by Blake and Kith [1] is used to derive the complete weight enumerators for Reed-Solomon and extended Reed-Solomon codes of dimensions one, two and three. Binary codes may be obtained from Reed-Solomon codes over a field with q = 2 m elements. Many different bases may be used to obtain these binary codes. We analyse conditions under which two bases will yield binary codes with the same weight distribution. We also consider the probability of undetected error of these binary codes. It has been shown by Kasami and Lin that (n,k) Reed-Solomon codes used over a g-ary symmetric channel are proper. In this thesis, it is shown that the binary expansions of these codes and their extensions, when used on the binary symmetric channel, are not necessarily proper. In particular, the codes of rate less than [l — log 2 m + log2(m — 1)] are not proper. ii Contents A b s t r a c t i i Table of Contents . i i i L i s t o f Tables v Lis t o f Figures v Acknowledgmen t v i 1 In t roduc t ion 1 1.1 Communications and coding theory 1 1.2 Finite fields and coding theory 2 1.3 Definition of terms and conventions 2 1.4 Organization of thesis 3 2 N o n - b i n a r y channel e r ror cont ro l codes 4 2.1 Complete weight enumerators 4 2.2 Deriving the ewe of some RS codes 5 2.3 ewe for extended codes 15 2.4 Summary of ewe 17 3 Obta in ing b inary codes f rom non-binary codes 19 3.1 Bases of Wq over F 2 19 3.2 Mapping elements of Ft to m-tuples 20 3.3 Invariance properties 23 3.4 The binary weight distribution of certain RS codes 30 4 T h e p robab i l i ty of undetected er ror for cer ta in b ina ry R S codes 36 4.1 -Pud(e) and properness 36 4.2 The properness of k = 1 RS codes 38 4.3 Properness of higher dimensional codes and severity of improperness 41 4.4 -Pu(*(e) for some b ^ 1 RS codes 44 4.5 Properness of duals of some codes 47 4.6 Codes which are not invariant w.r.t. basis 49 4.7 Summary 50 5 Conclus ions 54 iii 6 Direc t ions for future work 56 Glossary 59 References 60 A p p e n d i x A 62 A p p e n d i x B 64 iv List of Tables 2.1 ewe for various Reed-Solomon codes with m = 3 15 2.2 Summary of ewe for various Reed-Solomon and extended Reed-Solomon codes .... 18 3.1 Mapping of F 8 (as defined by x3 + x + 1) using different bases 21 3.2 Binary weights of commonly occuring patterns 31 3.3 Binary weight distribution for various Reed-Solomon and extended Reed-Solomon codes 35 4.1 Severity of improperness for various binary expansions of k = 1 codes 41 4.2 Severity of improperness for the binary expansions of RS 0(n, n — 1) and RSi(n, n — 2) 49 4.3 Binary weight distributions for the RSi( 15,4) code 51 4.4 Improper binary expansions of RSi(15,4) 52 List of Figures 4.1 g-input, ^ -output symmetric, memoryless channel 37 4.2 Pud(e) for RSi(7,l) (over g-ary channel) and its binary expansion (over BSC) .... 39 4.3 Puti for binary expansions of RS codes, m = 4, k = 1, 2, 3 43 4.4 Graph of + H2(a) and 1 - f 46 4.5 -Pud(e) for the different binary expansions of RSi(15,4) 53 v Acknowledgment The author would like to gratefully acknowledge the support of Dr. Cyril Leung, whose guidance and advice were invaluable. This work was also partially supported by NSERC Grant OGP0001731. Finally, many thanks to my brother, with whom I had many discussions about this thesis. c vi 1 Introduction 1.1 Communications and coding theory Error control coding theory is the study of redundant codes, used to make communication more reliable [2, 3, 4]. Data is transformed into a suitable format and transmitted to its destination through some media (a wire, or free space, for example), which we model mathematically as a channel. The most common type of channel model is the binary symmetric channel (BSC). One bit (0 or 1) is transmitted through the BSC at a time, with a certain probability e of making an error (0 becomes a 1, and vice versa). The term symmetric refers to the fact that this probability is independent of whether a 0 or a 1 was transmitted. We often assume that the channel is memoryless. That is to say, the present and future performance of the channel is independent of its past behaviour. Other channel models exist [5, 6], but in this thesis, we only consider symmetric, memoryless channels. In block error control coding, redundancy bits are added to a block of k information bits, resulting in a new block (called a codeword) of re > k bits. The way in which this redundancy is added defines the encoding operation of the code. Since there are 2k different fc-tuples of information bits, not all 2 n binary re-tuples are valid codewords. The channel may introduce errors to the codeword by changing some of the co-ordinates in the re-tuple. The receiver takes the re-tuple, which may contain errors, and tries to determine the original k bits of information. If the received re-tuple is not a valid codeword, then errors must have occured. Some codes add enough redundancy such that some of these errors may be corrected. Others will simply detect the presence of errors, and ask for a re-transmission. Another possibility may arise. The errors may change the transmitted 1 n-tuple onto a different n-tuple which is also a valid codeword. In that case, the receiver has no way of knowing that an error occured. This is called an undetected error, and naturally, we want to minimize its probability. Since the birth of coding theory, much research has been devoted to finding the weight enumer-ator of codes [4, 7, 8]. This enumerator gives a description of how the weights of the individual codewords are distributed, and gives insight into how best to design a decoder. The probability of undetected error can be completely determined if the weight distribution is known. In general, determination of the weight enumerator is a difficult problem. Exhaustive enumeration of the codewords to find the weights is not feasible, if k and n — k are very large. 1.2 Finite fields and coding theory Abstract algebra plays an important role in the design and analysis of codes. We may generalize the binary digits (0 and 1) in the above discussion with a finite field of q elements [9, 10]. Codewords may be viewed as vectors over a finite field, and the code as a vector space over a finite field. Note that the set {0,1} is also a field. The counterpart to the binary symmetric channel is then the q-ary symmetric channel. Codes may then be defined over this field, with Reed-Solomon codes being the best known class of non-binary codes. Surprisingly, the Hamming weight enumerator for all Reed-Solomon codes is known [11, 12]. In this thesis, we derive the complete weight enumerator (which describes non-binary codes better) for some Reed-Solomon codes. 1.3 Definition of terms and conventions In this thesis the following conventions and symbols will be used, unless otherwise noted. Denote the field of q elements by Fq, with q = 2 m. Let n be the block length of a code C. Only Reed-2 Solomon codes are considered, so n = 2m — 1 is used throughout. The symbol a is used to denote a primitive element of Wq. A useful way of describing the elements of Fq is {a J , j £ B}, where the set B = 0,1,..., n — 1}, and a* = 0 by convention. The multiplicative group of the non-zero elements of F, is denoted F£ = {aj,j <= B*}, with B* = {0,1,..., n - 1} = B \ *. The Reed-Solomon code over Wq of length n, dimension k, and generator polynomial g(x) = (x - ab)(x - ab+1) •••(x- ah+n-k~l) (1.1) is RSJ(TI, k) and ERS ; , (g, k) is its extension [2]. When 6=1, the code is referred to as narrow-sense. Note that the dual [2, 4] of RSj(n, k) is RS„_)t+i,(n, n — k). 1.4 Organization of thesis Non-binary codes over Wq are discussed in chapter 2. Complete weight enumerators (ewe's), which give a more accurate description of the code than Hamming weight enumerators, are described. The ewe's of the various Reed-Solomon codes to be analysed in subsequent sections are derived. In chapter 3, the mapping of a non-binary code over F ? to a binary code over F 2 is described. This mapping depends on the choice of a particular basis of Wt over F2. It it shown that the weight distribution of the resulting binary code (called the binary expansion of the non-binary code) may vary depending on the choice of this basis. Furthermore, an equivalence relation is defined which partitions the bases, and reduces the number of distinct binary expansions. The binary expansions of various Reed-Solomon codes are examined in chapter 4. Although Reed-Solomon codes are proper over Fq [13], it is shown that their binary expansions are not necessarily proper. The rate, r*, below which all binary expansions of narrow-sense RS codes are improper is derived. 3 2 Non-binary channel error control codes Codes over non-binary fields such as ¥q are a simple extension of the more common binary codes. The concepts remain the same, but the mathematical operations are carried out in Wq, rather than F2. Reed-Solomon codes are perhaps the most well known class of non-binary codes. 2.1 Complete weight enumerators Often, a weight enumerator is used to describe the characteristics of a code. Although weight enumerators do not completely describe a particular code (i.e., given a weight enumerator, the individual codewords in the code cannot, in general, be deduced) they are sufficiently useful in analysis to warrant study. The most commonly used weight enumerator of a code, C, is the Hamming weight enumerator, a polynomial in an indeterminant, z, of degree of at most n. The coefficient of the zx term, Ai, is the number of codewords in C of Hamming weight i. While Hamming weight enumerators describe binary codes well, they do a poor job in describing non-binary codes, since in Wq, there are multiple non-zero elements which Hamming weight enumerators do not differentiate between. Complete weight enumerators, account for this, and are described below. Let c be a codeword in C, an (n,k) code over Wq. Its ewe describes the number of times each field element appears in c. The complete weight enumerator of the code C is the sum of the ewe of its individual codewords. In general, the ewe of c may be described as j€B where Sj is number of times a? occurs in c. Note that J2B sj — n-> a n d hence, the ewe is a 4 homogeneous form of order n in q variables. The ewe of C is a sum of these types of products. There are qk terms in this sum. Example: Consider the Reed-Solomon code over F 8 with k = 1, and generator polynomial 9(x) = Ui=i(x ~ a')- T h e s e t B associated with F8 is {•,0,1,2,3,4,5,6}. This is the RSi(7,1) code, and has the following codewords: CO deword ewe (0 0 0 0 0 0 0) z 7 * (1 1 1 1 1 1 1) (a a a a a a a) (a2 a 2 a 2 a 2 a 2 a 2 a2) (a 3 a 3 a 3 a 3 a 3 a 3 a3) Z7 (a 4 a 4 a 4 a 4 a 4 a 4 a4) Z7 (a 5 a 5 a B a 5 a 5 a 5 a5) Z7 (a 6 a 6 a 6 a 6 a 6 a 6 a6) Z7 z6 The ewe of the code is therefore *l + z7a + z\ + z\ + z73 + z\ + z\ + z76 = ^ 2 zj. 2.2 Deriving the ewe of some RS codes The problem of finding the ewe of a code is difficult in general1, and cannot be solved without explicitly enumerating the individual codewords, except in some simple cases. In this section, we describe the method used by Blake [1]. The ewe of some other codes, which are analysed in chapter 4, are derived, using the same methodology. Let f(x) be a polynomial over Wq and define v(/) to be the n-tuple v(/)=(/(l),/(a),...,/(a-1))eF;. (2.2) 1 See research problem 11.2 in [4]. 5 For a subset / C B*, let P(I) be P{I) = a ^ UgB* at- 6 Fj if i 6 / a,- = 0 otherwise In words, P(I) is the set of all polynomials with coefficients (s F,) corresponding to terms with degrees in /. If there are k elements in /, P(I) will contain qk polynomials, including the zero polynomial. It can be shown that [14, 1] RSb(n,k) = {v(f)\feP(Z)} (2.3) where Z is the set of zeros of the code (i.e., roots of the generator polynomial), and Z = B* \ Z. Note then, that Z is the set of zeros of the parity check polynomial. Also see [2]. For RS4(n, fc), Z = {b, b+ 1,..., b + n - k - 1}, and hence Z = {b - k, b - k + 1,..., b - 1). Let 0i= 1 a{ a2i ••• a^-1* From [2], the parity check matrix of RS;,(n, k) is then, H -1 a" a' 1 a*+1 a 2 ( * + 1 ) a ( n - l ) » a ( n - l ) ( 6 + l ) I ab+n-k-l a 2 ( i + n - f c - l ) . . . a(n-l)(b+n-k-l) 'b+n-k-l The corresponding generator matrix G can be worked out, since GH — 0 G @b-k Qb-k+l #6-1 6 Note that 0; is orthogonal to Oj if i + j' ^ 0 mod n, which follows from n - l 1=0 (=0 0 if i + j ^ 0 mod n. see eqn. (A.3) 1 otherwise Let f(x) from eqn. (2.3) be Clx»-k + c 2 x b - k + 1 + • • • + CkX1-1 = A codeword c would then be of the form C l • • • Cjfc - i - f c + l = /(«) • /(a"- 1) " 1 (a2)b-k • • • (a 1 ( a 2 ) » - * + 1 • •• (a" = C l • • * ] 1 • • ( a " 1 a 6" 1 ( a 2 ) 6 " 1 • •• (a ck G i _ i \ i _ j b , n - l \ » - l Each value of / corresponds to a codeword in the code. The ewe for the code is then determined by considering v(/) for all possible values of at. In the simple case for RSx(n, 1), P(Z) consists of the set of constants a0. Therefore, f(x) = a0, for any value of x, and v(/) = (a 0, a0,..., a0). The q codewords in the code are obtained by letting a0 vary over F?, and it is clear that each codeword is then an n-tuple with identical elements. So, ewe of RSi(n, 1) = y~] z". (2.4) 7 In general, things are more complicated, since f(x) is not necessarily a constant. We would like to examine the co-ordinates of v(/) in eqn. (2.2). To facilitate this, take a value of j € B, and the equation f(x) = aj. (2.5) The number of co-ordinates in the codeword corresponding to f(x) is the number of different x (as x is varied over the non-zero elements of F ?) for which eqn. (2.5) is true. So, the Sj in eqn. (2.1) are given by Sj = ^distinct solns of x to eqn. (2.5) over F£. (2-6) Applying this, we can derive the ewe of some simple codes. Lemma 2.1. The ewe for RSi(n,2)2 and RS2(n,2) are the same, and is equal to £ ^ + ^ £ 7 (2-7) j€B ieB z % with 7 = UjeBzj-Proof. For RSi(n,2), f{x) — a0 + d i X " - 1 , while for RS2(»,2), f(x) = a0 + axx. Therefore, Sj is equal to the number of solutions to the equation a0 + axxc = aj (2.8) whilst aQ and ax are varied over Fq, and c is either n — 1 (= —1 mod n) or 1. There are two cases to consider. Case I: ax ^ 0 2 T h i s case is given in [1]. 8 If ax 7^ 0, then + 1 a3 — a0 . m ,n x = = some constant m Wq. (2-9) ai Fixing ai, eqn. (2.9) will have one solution for x £ F£, provided a 0 ^ a?. If a 0 = a J, there will be no solutions for x, since x cannot be zero. So, Varying a 0, the contribution to the ewe becomes Z0Zi • • • Zn_i + Z^Zi • • • Zn-i + Z^Z\Zz • • • Zn_i + • • • + Z*Z0 • • • Zn_3Zn_i + Z±ZQ • • -z, ^ ' V V ' V >*» ' • - r, Z i * n - 2 = 7 £ ~ a 0 =0 a 0 = l a 0 = a a o = a " - 2 a 0 = a n _ 1 Since there are n non-zero values for a 1 ; the total contribution for Case I becomes wy^i€B j - . Case II: ai = 0 For this case, eqn. (2.5) becomes a0 = a3, and is independent of x. Therefore, x can take on any value in F£, and hence, { n if a0 = a3 0 if a0 ? a3 • So, the contribution for Case II is X^es when the sum is taken over all possible values of o0. Combining the two cases, the ewe becomes: jeB i6B • We now generalize the ewe given in eqn. (2.4) to values of b other than 1. 9 L e m m a 2.2. The ewe for RSb(n, 1) for 6=1 mod n is YLJZB zj'• Otherwise, it is equal to **+^ E n t (2-n) «=° je{Jd+i) where d = gcd(6 — l,n), and Jd is the set of elements in B* which are a multiple of d. The set {Jd + i} is obtained by adding i (modulo n) to every element in Jd. Note that if b — 1 and n are relatively prime (i.e., d = 1) eqn. (2.11) becomes + n^. There are n elements in B*, of which only one in d is a multiple of d. So Jd has n/d elements. Proof. The 6=1 case was given earlier in eqn. (2.4). Since a" = 1, values of 6 such that 6=1 mod n will give the same generator polynomial in eqn. (1.1). So, eqn. (2.4) is actually valid for values of 6=1 mod n. For other values of 6, consider the argument given below: The z" term corresponds to the all-zeros codeword, present in every linear code. For the other codewords, the equation to examine is axh~l = aj ae¥q. (2.12) The various possible values of a correspond to the different codewords in RSJ(TI, 1). Since a = 0 corresponds to the all-zeros codeword, restrict a to lie in FJ. Eqn (2.12) then becomes: xb~l = ^ 6 ^ l , a ^ 0 . (2.13) This equation has no solutions if j — Otherwise, there is a unique solution if 6 — 1 and n are relatively prime. If d = gcd(6 — l,n) ^ 1, there are d solutions when j is a multiple of d [9]. Therefore, the contribution for each a is Ylj€jd Zj. 10 Thus the ewe of RSj(?i, 1) is z*+^ Ji n zfif b ^ 1 m ° d n > a n d d = § c d ( 6 - n ) ewe of RSj(n, 1) = < nd~l i=oje{Jd+i} (2.14) y~] z" otherwise • The derivation of other ewe's requires application of some results from the theory of algebraic equations over finite fields[15]. Consider the RS3(TC, 2) code, which is the dual of RS^TC, n — 2) code. L e m m a 2.3. The ewe for RS3(n,2) is z» + 2n^ + nJ2^- (2-15) ~* k£B* Z* where B0 = {ilTria^^O} Bk = {k + B0} addition is modulo n, and j + • = • A = n-i jesk and for x G Fq, Tr[x) is the trace of x over F2 defined as Tr(x) — x + x2 + x4 + • —h a; 2™ - 1. Note that Tr(x)eF2 [4, ch. 4. §8.]. Proof. A well known fact [15] which will be useful in this proof is that the equation x2 + ax + b = 0 over Fq has solutions for x 6 Fq iff Tr(6/a2) = 0. When solutions exist, there will be two in number. The equation to consider for this code is: axx + a2x2 = OL3' (2.16) 11 Now, consider the following cases: Case I: ax = 0 With this restriction, the code reduces to the RS3(n, 1) code, and hence its ewe will be part of the ewe for RS3(n, 2). Case II: a2 = 0, ax ^ 0 Here, eqn. (2.16) becomes axx = a-7, which is similar to eqn. (2.13), and the corresponding ewe will be n-y/z*, when ax is varied over all possible non-zero values. Case III: all others When TT(aia2/al) = 0, eqn. (2.16) has solutions. If a* = 0 (or j = *), it is evident that the only non-zero solution to x is x — — a i / a 2 . For all other a-7, there will be two solutions for x € F£. For example, fixing ax = a2 = 1, Allowing a 2 to vary will shift the solution for Sj. For example, if a2 — a, the condition j 6 B0 Note that each product corresponds to a codeword (a particular value of a2 and a1;) and there are n terms in the sum, one for each non-zero value of a2. Varying ax over the n non-zero values yields a similar action, with terms being folded over. Eqn. (2.18) then becomes ' 1 i f j = * Sj = < 2 if j 6 -0O, but j ^ • 0 otherwise (2.17) becomes j + 1 £ B0. Therefore, as a 2 varies over F£, the ewe contribution becomes ife = 0 * ieB f c (2.18) 12 and the total ewe is (2.19) • It may seem like an easy extension to use the same methodology to obtain the ewe for codes with higher 6, or higher k, but in practice, this is not feasible. The main problem is the lack of knowledge (other than [15]) about the solution of equations of arbitrary degrees over finite fields. A mere condition on the existence of solutions (and number) would suffice, but [15] only gives these for equations of degree 2 and 3. As k is increased, the number of terms and degree of f(x) in eqn. (2.5) increases. Even increasing b, while fixing k will increase the degree of f(x), making analysis more difficult. For example, an increase of 6 to 5 in the previous example will result in considering to get the ewe of RS5(n, 2). Because of the constant term on the RHS of (2.20) can be non-zero, analysis of the general equation is difficult. Due to the fact that a" = 1, certain symmetries may be exploited. Fixing k, the ewe corre-sponding to different values of b come in pairs. For a given b, eqn. (2.5) is of the form aix3 + a2x4 = a? (2.20) f(x) = aioxio + a^x'1 + ••• + aihxik = aj (2.21) there will exist another b with a corresponding equation of the form /(*) = + atlx - » i -I + aikx (2.22) 13 If (2.21) has Sj solutions, then (2.22) will have the same number of solutions. An equation of the form in (2.21) can be obtained by making the substitution y = 1/x. Hence, if the ewe of RS;,(n, k) is known, there will exist a b' such that RSb>(n,k) has the same ewe. The relationship between b' and b is given in the lemma below: L e m m a 2.4. / / b + b' = (k + 1) mod n then RSb(n,k) and RSbi(n,k) have the same ewe. Proof. Let Z be the set of zeros of the RSj,(n, fc), i.e., the roots of g(x) in eqn. (1.1), and Z — B*\Z. For RS;,(n, k), Zb = {b-k,b-k + 1,...,6- 1}. Substituting b + b' = (k + 1) mod n for b, we obtain {1-6', 2-&',...,*-6'}. (2.23) Powers of x are negated in eqn. (2.22), so negating each element of the set in (2.23), we get {&' - 1, b' - 2,..., b' - k + 1, b' - k} = Zv. • Table 2.1 shows the ewe for various b for RSj(7, 2) codes. 14 Table 2.1: ewe for various Reed-Solomon codes with m = 3 code ewe RSi(7,l) {0} £*; RS t(7,l) {6-1} RSx(7,2) RS2(7,2) {6,0} {0,1} RS3(7,2) RS7(7,2) {1,2} {5,6} ' * k€B* * j€Bk RS4(7,2) RS6(7,2) {2,3} {4,5} k+147+ 7 z* E zi n zi > * keB* j€Bk ^ + 1 4X + 7 E l n ^ RS5(7,2) {3,4} Note: Bk = {*, 1,2,4} + Ak = {*,3,5,6} + & 2.3 ewe for extended codes Deriving similar equations for the ewe of extended RS codes is very similar to the method used for non-extended RS codes. In fact, the expressions obtained are sometimes easier to work with. Recall the definition of v(/) given in eqn. (2.2), i.e., v(/)=(/(l),/(a),...,/(a- 1)). Since /(l) + /(a) + h / ( a n _ 1 ) = /(0) 3, we can define a similar concept for extended codes. Let 3 See Appendix A for proof 15 v e(/) be defined as v e(/) = ( / (0),/(l),/(a),...,/(a n- 1)) G ¥\. (2.24) An extended Reed-Solomon code over Fq, with dimension k may then be obtained by changing v to v e in eqn. (2.3). The only consequence of this change is that the equations are now solved for i G F r The equation for Sj in (2.6) becomes Sj = ^distinct solns of x to eqn. (2.5) over Fq, (2.25) and J2B sj = ?• Making minor changes to the argument given for RSi(«, 1), the ewe of the extended code may be seen to be: ewe of ERS x(n, 1) = £ z). (2.26) As with the non-extended case, the ewe for ERSi(n,2) and ERS 2(n, 2) are the same. Since x may be zero, the Sj in eqn. (2.10) is simplified to Sj = 1 Vao. The ewe is then ewe of ERSj(n, 2) = ewe of ERS 2(n, 2) = £ z) + q(q - 1)7. (2.27) In a similar vain, we can show that ewe of ERS3(n,2) = z\ + 2{q - 1)7 + (q - 1) £ f3k. keB* 16 The equation for Sj in (2.17) must be changed slightly, since x may have zero as a solution. The new equation for Sj is g = | 2 if j G B0 3 1 0 otherwise For the ewe of ERS&(«, 1) with b ^ 1, the solution to eqn.(2.13) is 1 i f j = * d if j is a multiple of d . 0 otherwise So, the ewe is then n *f >=0j€{Jd+i} 2.4 Summary of ewe Table 2.2 below summarizes the ewe of various Reed-Solomon codes discussed in this section. Note that the b = 1, k = 3 cases were not derived here, but by Blake and Kith in [1]. It is included here to demonstrate how expressions for ewe get complicated quickly. 17 Table 2.2: Summary of ewe for various Reed-Solomon and extended Reed-Solomon codes code b k ewe non-extended extended 1 1 1 2 1 3 E*J E * ' + 9 ( « - 1 ) T jeB j€B Zi+k iPB Z i + k fees* t 1 2 2 3 2 <+5E n */ samej as RSi (n ,2) 4 + g - 1 d - l E n */ same as ERS i (n ,2 ) *« + 2 ( g - l ) 7 + ( ? - l ) £ ft Notations used: 5 = { * , 0 , l ) . . . ) n - l } |B | = q = 2 m B * = {,0 ,1 , . . . ,n -1} = n = 2 m - 1 7 Bo = {» | Tr(a ' ) = 0} Bo = B\B0 Bk = BQ + k addition is modulo n, and j + * Bk = B\Bk Pk = n*/ j€Bk h = I H f : 6 ^ 1 . If 6—1 and n relatively prime, then the ewe is z " + ny/z* for non-extended, and z\ + (q — 1)7 for extended. A l l values of 6 are taken modulo n. % : due to Lemma 2.4. Other codes with identical ewe are not shown. 18 3 Obtaining binary codes from non-binary codes In many applications, while the alphabet of the information symbols is non-binary, the channel to be used may be binary in nature. Hence, the non-binary codeword symbols must be converted, by some means, to binary bits. The methods discussed below show how an extension field of characteristic 2 may be mapped to the binary field. A general reference for the material in the first few sections is [4, ch. 10. §5]. 3.1 Bases of Fq over F 2 Wq may be viewed as an m-dimensional vector space over F2, and hence any m linearly independent elements in Wq may be used as a basis of this vector space. Let a0, a\, ..., a m _ i be m such elements, and a = {ao,a!,...,am_i} denote a basis of F, over F2. There are 0 = (2 m - l ) ( 2 m - 2)(2 m - 4).. .(2 m - 2m~l) such bases. If the channel being considered here is memoryless, the order of the a^s is immaterial, so only the fi' = fi/m! different order independent bases need to be considered. This shall always be the case in this thesis, and unless otherwise specified, the elements in a basis are order independent. Further, divide these 0' bases into equivalence classes, defined by the following equivalence relation. Two bases a and b, where a -- {a0,a!,.. . , c m _ i } , a8- 6 Wq b = {b0,b1,...,bm_1}, bi€Wq are said to be in the same equivalence class, written a ~ b, if 3c ^ 0 G Wq s.t. b, — ca( for all i = 0, 1, ..., m — 1. Note that if {a 0, a 1 ; ..., a m _ i } forms a linearly independent set, so does 19 {ca0, ca 1 ; ..., cam_!} if c ^ 0. The relation partitions the bases into £l'/n equivalence classes, consisting of n elements each. It is shown later in Theorem 3.2 that bases in the same equivalence class yield the same binary weight distribution. While this reduces the number of bases to consider, there is still an exponential growth in m, as shown below m Q,' Q,'/n classes 3 28 4 4 840 56 5 83328 2688 6 27.99 x 106 44416 3.2 Mapping elements of Fq to m-tuples If a is a basis of Wq over F 2 , then any element /3 6 F g can be written as: (3 = b0a0 + &iai + 1- 6 m _ia m _i, b{ € F 2 The basis a is said to map f3 into the binary m-tuple (b0, bx, . . . , &m_i). Chapter 4 examines some properties of the binary codes obtained this way, so it is important to look at the weights of the m-tuples generated. Let a' be mapped to an m-tuple of weight (i = 0, 1, ..., n — 1). The number of i's s.t. W{ — j is (™), and n—1 m / \ £ ^ = £ i P ) = m 2 ^ DM W M . i=o j=i \3 I Note that if the basis a is changed, W{ for a given i may change as well. Example: Let a and b be two different bases of F 8 over F 2 . The individual mapping of elements in F 8 is shown below: 20 Table 3.1: Mapping of F 8 (as denned by x3 + x + 1) using different bases a - {1, a, a 2} b = {1, a 5} i Wi i i i w{ * 0 -»• (000) 0 3 a 3 (110) 2 • 0 -»• (000) 0 3 a 3 -• (110) 2 0 1 -> (100) 1 4 a 4 -> (Oil) 2 0 1 - (100) 1 4 a 4 - > ( i o i ) 2 1 a -»• (010) 1 5 a 5 —• (111) 3 1 a (010) 1 5 a 5 -• (001) 1 2 a 2 -»• (001) 1 6 a 6 -> (101) 2 2 a 2 -(111) 3 6 a 6 -• ( o n ) 2 L e m m a 3.1. / / a anrfb are in the same equivalence class s.t. bt = a'a,-, and a. maps a* a binary m-tuple of weight wit then b will map a'+I to a binary m-tuple of weight Wi. Proof. Any element a' G Wq can be written as a' = x0a0 + x^ai -\ xm^am_x where the number of non-zero xts is wt. Multiplying by a, and choosing the basis {aa0, aa l f ..., a a m _ i ) a , + 1 = ax0a0 + ax^x + (- ax^xa^x = x0b0 + -) hx„1_i6m_i Hence, by repeated use of the above argument, a,+l will have the same weight when mapped using basis b. • By mapping each co-ordinate in each codeword of an (n,k) code C, a binary code, C2, may be formed. We will refer to C2 as the binary expansion of C and the weight distribution of C2 as the binary weight distribution of C. It should be emphasized that a particular non-binary code C may 21 give rise to many different binary weight distributions, depending on the basis chosen. Only in certain special cases will there be a unique binary weight distribution. If the ewe of C is WcO*, z0, z„_ i ) and given a basis which maps a1 to a vector of weight Wi, for i 6 B*, the weight enumerator of C2 is obtained by substituting z* = 1 Zi = xWi (3.1) into Wc. Hence fH(x) = W c(l, xw°, a;*"-1). Example : The ewe of RS 4(7, 2) is given in Table 2.1 as Wc = zl + U?-z* ZzZ$Z§ + 7^^2:42:6^0 + lz±Z2Zr,Z§Z\ -+- 1 Z^ZZZ^Z\Z2 +7' Z^Z\ZQZ2Z3 + 7z^z^ZiZ^z^ + 72^ 252:22:42:5. Using the bases a and b in the previous example, the binary weight distributions are: IH(X) = Wc(z* = l,z0 = X,Zi = x,z2 = x,z3 = X2,Zi - x2,z5 - x3,z6 = x2) = 7x14 + 21a:12 + 21a;10 + 14x8 + 1 with basis a (3.2) and IH{X) = Wc(l,x,x,x3,x2,x2,x,x2) = 42x12 + 21a:8 + 1 with basis b (3.3) 22 Note that these are the only two binary expansions of RS4(7,2). Of the 28 bases of F 8 over F2, twenty-one will give rise to the distribution given in (3.3), while seven will result in the distribution in (3.2). This was determined by exhaustive enumeration of all possible bases. 3.3 Invariance properties A mathematical description of an (n,k) linear code, C, over Wq would be as a ^ -dimensional sub-space of the vector space F£. This terse definition is not too useful, since it does not describe potential structure evident in C. Indeed, it is this structure which makes a code easy to analyse and implement. Certain properties in codes will translate to patterns (groups of terms) in its ewe. Some examples are given below: Property 1 : closure under scalar multiplication. If c = (c 0, C j , . . . , cn_j) G C, then for a G Wq ac = (aco, aci,..., cc„_i) 6 C Assume that the ewe of c is T[j€A z)3 for some A C S , and a = ak ^ 0. A particular co-ordinate Cj = a' 7^ 0 in c would become ac,- = al+k. Co-ordinates in c which were zero remain zero. Hence S(i+k)modn in ac is equal to s,- in c and remains unchanged. Given the ewe of c, the ewe of ac is then n ^ j€{A+k} where the sum {A + k} is done modulo n, with * + x = Therefore, the ewe of all such codes will comprise of terms of the form £ n (3-4) keB' je{A+k) 23 Note that all linear codes and some non-linear codes satisfy this property. Property 2 : cyclic codes. If c = (c 0, C i , . . . , cn_x) G C, then its right cyclic shift c' = ( c n _ i , c0,..., c n_ 2) G C If the ewe of c is l l f g A " 2 ^ ) s o i s the c w e °f c'• The cyclic shifts of c would contribute terms of the form v n ^ (3.5) to the cwe of C, where p is the period of c. Note that p divides n [16]. Combining this with property 1 would result in a multiplicative factor p for (3.4). Def in i t ion 3.1. Let <8 be the set of all bases of Fq over F2, and 3 be a subset of 2$. A code over F g is said to be invariant with respect to the bases in 3 if every basis in J maps the code to a binary code with the same weight distribution. If J = <8, the code is invariant w.r.t. to all bases, and we shall simply call this code invariant. T h e o r e m 3.2. A code C is invariant w.r.t. bases in the same equivalence class, provided C satisfies property 1 (closure under scalar multiplication). Proof. Let a and b be in the same equivalence class such that &,• = a'a8-. Lemma 3.1 states that a and b induce the following mappings4: f0: Zi —* xWi for basis a fi'.zi+j —> xWi for basis b 4 Integer addition is done modulo n 24 Consider the mapping of the typical term YIJ^A z'i3 u nder f0 and /(: s E i € A s ^ (3.6) /i(n*;0 - ^^ +<>^ =/0( n $\ (3.7) Basis a maps the shifted typical term fTj6{A+;} z'j' a n d basis b maps the typical term WJ^AZJ' in the same way. Since the ewe a code which satisfies property 1 contains only patterns with all possible shifted terms, a and b will map the code to the same binary weight distribution, regardless of/ 5. • Def in i t ion 3.2. For every basis a = {a l 5 a 2, am}, there exists another basis b = {bi, b2, ..., bm}, with ° I F ^ ' " (3.8) T*Mi ) = *« = { J o t h e r w i s e , called the complementary (dual) basis of a. If A is a subset of *8, and AL the set of complementary bases of A, Ax is well-defined, and contains the same number of elements as A, since b is unique [4, ch. 4. §8]. The trace operator is used often, and is known to have the following properties [10]. Let p be a prime, and m a positive integer. For elements x and y € FjJ1, and a G Fp. (T-i). Tr(z + y) = Tr(x) + Tr(y) (T-ii). Tr(az) = aTr(x) (T-iii). Trace is a linear transformation from F^1 onto F p (T-iv). Tr(x) takes on each value in F p equally often, i.e., p™-1 times. Note that the definition of the equivalence relation precludes / = *, and / = 0 implies that a = b. 25 (T-v). TT(X?) = Tr(x) L e m m a 3.3. If C is invariant w.r.t. all bases in A C S , then the dual code CL is invariant w.r.t. all bases in A1, the set of complementary basis of A. Note that in some cases, A = A1. Proof. Let a and b be complementary bases. If Ca is the binary expansion of C when basis a is used, and Cx is the the binary expansion of C 1 when b is used, then Ca and Cj X are duals. The proof for this is given in Kasami and Lin [14], and is repeated here for completeness. Let u2,..., un) 6 C and (vi, v2,..., vn) £ CL. Expanding using the respective basis obtains m Ui = £^«j«j (3.9) m 3 = 1 Since u and v are in dual codes, n n / m \ s m \ E ^ = E ( E ^ o > ) ( E v « 6 * ) = 0 ( 3 - n ) j=l t'=l v = i ' ^k=l ' Taking the trace of (3.11) • it in in \ ^ ( E E E W * ° A ) = 0 (3-12) ^8=1 7 = 1 * = 1 ' 3n ro m E E E w - * 1 ^ 0 ; 6 * ) = 0 ( 3 - 1 3 ) t=l j - l k=l n m E E " * 1 * ; = 0 (3-14) «=i j=i Eqn. (3.13) follows from trace property (T-i). The utj are the individual co-ordinates of a codeword in Ca, and t>,j are the co-ordinates of a codeword in . Thus, Ca and Ctx are dual codes. 26 Let a! and a 2 be two bases from A, with complementary bases aj and a^ respectively. The binary codes generated have the following relationship: n dual n±_ C«x » C a f r dual rx. Since Cai = Ca3, and because the dual of a code is unique, Cji = Cj i . A similar argument may be used to cover all bases in A. • Corollary 3.4. If C is invariant w.r.t. all bases, then the dual code CL is also invariant. Definition 3.3. A basis is called self-dual ii it is equal to its complementary basis. The order of the individual elements is considered irrelevant. More precisely, a = {a 1 ; a2,..., a n} is self-dual if 3c € S m, the symmetric group of permutations with m elements, such that rr ( \ R J 0 if i 7^ j Tr(aiaaU)) = 6{j = j ± . If the permutation a is the identity permutation, then the basis is termed strictly self-duaf. If all bases of a class and their complementary bases are in the same class, that class is said to be self-dual. Lemma 3.5. Given an equivalence class A, the following statements are equivalent: 1. A is a self-dual class. 2. A has exactly one self-dual basis. 3. Both basis a, and its complementary basis b are in A. 6 Standard references, such as [10, 4], simply refer to this as self-dual. 27 In addition, if A does not satisfy the above criteria, then A will have no self-dual bases. Proof. Let A be an equivalence class of bases, and a a basis in A. The basis b, complementary to a, is either in A, or another class B. To show that the three statements are equivalent, we will show that statement 1 implies statement 3 (and vice versa). Then, we show that statement 1 implies statement 2 (and vice versa). If b £ A, then showing that the duals of other bases in A are in B proves that A has no self-dual bases. The duality between a = {ai, a2,..., a m) and b = {bx, b2, • • •, bm} means that Consider then, another basis in A, such as eta = {aa 1 ? aa2,..., aa m}. The dual of this is easily determined, since TT(aaia~1bj) = Sij and hence, the dual of «a is a _ 1b 6 B. In a similar way, we may conclude that the duals of the other members of A lie in B, and therefore, A has no self-dual basis. If b G A, then we must show that the other two statements in Lemma 3.5 are also true. With both a. £ A and b 6 A, there must exist a unique integer /, and a permutation a such that b{ = alaa(iy So, Tr(a,a'aCT(j)) = 8{j. The dual of afca is then a~kb, since T r ^ a i C t ' - ^ y ) ) = SiS. 28 Because b £ A, then a~kb £ A too. Therefore, statement 3 implies statement 1. That the converse is true is obvious from the definition of a self-dual class. Because the powers of a are unique, and n is odd, the only time ak& is self-dual is when the equation k = I — k mod n is satisfied. For a given /, there is a unique solution for k, given by: ^ _ \ \l if / is even 1 j(Z + n) if / is odd. (remember n is odd also) So, statement 3 implies statement 2. We also need to show that if A has exactly one self-dual basis, then A is a self-dual class. To see this, let a be this one self-dual basis, and so, there exists a a £ S m such that Tr(o,aff(i)) = Sij. The other members of A, like aka. = {akai ,aka2,..., akam} will have duals in A, since Tr(a*a,a~*aa^\) = Sij: and so, the dual of ak& is a~ka. = an~ka. £ A. Hence, statement 2 implies statement 3, and all three statements are then equivalent. • There are two types of fields then to consider — fields where all classes are self-dual, and fields where there are some classes which are not self-dual. In the latter case, it would be useful to pair these classes with their duals. A class A which is not self-dual will have the duals of all its bases contained in a single class (call it AL.) 29 In situations where all classes are self-dual, then the following statement may be made. Let the code C satisfy property 1 (closure under scalar multiplication). 3 is then the union of equivalence classes, and the dual code CL will be invariant w.r.t. the same set J. The only known case of this is when m = 3, i.e., in F8. 3.4 The binary weight distribution of certain RS codes The code C is invariant when Wc is symmetric in its variables [17]. It is sufficient to examine groups of terms in Wc, as dictated by its structure, to determine if they are invariant. If all the individual terms in Wc are invariant, then C will be invariant. Note that symmetry in variables is a strong restriction, and there exists a weaker necessary condition. Commonly occuring patterns (see Table 2.2) which are invariant are listed below in Table 3.4. In interpreting the table, the structures may be taken over any extension field, as determined by m > 1. d is any positive, non-zero integer constant. All entries are invariant w.r.t. all bases, even though not all are symmetric. The discussion below shows how the CW weights were determined. s'gB This sum over i covers every possible value for elements in the field. Any given basis will map (™) field elements to binary m-tuples of weight i. Repeating d times yields the given binary weight distribution. 2. l/z* 7 is the product of all field elements, and hence has weight 30 Table 3.2: Binary weights of commonly occuring patterns # CW weights of CW wt. number symmetric q (A id . i = 0, 1, . . . . m w symmetric q Wm - i i = 0, 1, . . . , m X z+ not symmetric 1 Wm 1 £ & k£B* not symmetric n ( m - l ) 2m - 1 m m2 m _ 1 n — m k€B* not symmetric n ( m + l ) 2m - 1 m m2 m _ 1 n — m Notes: Wm = m2 m~ 1 B0 = {t | Trta') = 0} BK = BQ + k addition is modulo n, and j' + • = • CW : codeword z* has weight zero, and does not affect the overall weight. Combining case 1 and case 2, the weight of 7 must be reduced by an amount corresponding to the Zj. There are (™) of the Zj's with weight i, and hence (™) codewords with weight W m — i. 4- £ & = £ n a n d 31 n A k€B+ k€B* j€{B0+k} Cases 4 and 5 are by far the most difficult distributions to show; a few facts must be exploited for this proof. Each codeword may be mapped using one co-ordinate (in a given basis) at a time. Let c = (ci, c2,..., c„) with c,- € F ? be a vector to be mapped, using the basis {a x, a 2, ..., a m ) . Let {61, b2, • . . , 6m} be the dual basis. Mapping c with the co-ordinate a t yields the binary n-tuple [14] (Tr ( 6 l C l),Tr ( 6 l C 2 ) , . . . , Tr (6 l C „ ) ) Repeating the procedure with the other co-ordinates will yield m n-tuples, or a binary vector of length mn. Example: Over F8, let the vector to be mapped be c = (1 o? a5 0), and basis {1, a, a5}. The dual basis is {a 3, a 4, a} a3c = (a3 a5 a 0), Tr(a 3c) = (1100) a 4c = ( a 4 a 6 a 2 0 ) , Tr(a 4c) = (0100) ac = (a a 3a 60), Tr(ac) = (0110) Reading the binary vectors vertically, we can verify the mapping. With the given basis (see also Table 3.1), a 2 maps to (111), and a 5 maps to (001). L e m m a 3.6. Let v — (v l 5 v2,..., t\) be a vector over Wq consisting of all elements with trace zero, i.e., Tr(vj) — 0, j = I, 2, ..., i. Mapping v with any basis (using the method above) will yield a binary weight of either m2m~2 or (m — l ) 2 m - 2 . Similarly, if v consists of all elements with trace one, the corresponding binary weight is either m2m~2 or (m-\- l ) 2 m - 2 . 32 Proof. We will make use of the following fact. Given the set Z of all field elements with trace 0, i.e., Z = {a'\i G B0}, then multiplying every element in Z by a constant s £ Fq, s ^ 0, s 7^ 1, will result in a set with half the elements having trace 0 and the other half having trace 1. Note that there are 2 m _ 1 elements in Z, so 2 m _ 2 elements in the new set have trace 0, while the other 2 m _ 2 have trace 0. A proof for this is given in the Appendix B. Writing out the mapping for each possible value of (dual) basis co-ordinate, and taking the trace, we can see that the binary vectors will either have weight zero (if co-ordinate is 1), or 2 m - 2. For a given basis, there are m co-ordinates. If none of these co-ordinates are 1, then the binary weight of vector v will be m2m_2. Otherwise, it will be (m — l ) 2 m - 2 . This is shown in an example for F 1 6 (as generated by a 4+a+l), where v = (0,1,a,a2,a4,a8,a5,a1 V = (0 1 a a2 a 4 a8 a 5 a 1 0 ) , Tr(«) = (00000000) av = (0 a a 2 a3 a 5 a9 a 6 a 1 1 ) , Tr(av) - (00010111) o?v - (0 a 2 a 3 a4 a 6 a 1 0 a 7 a 1 2 ) , Tr(a2-y) (00101011) a3v = (0 a 3 a 4 a5 a7 a 1 1 a8 a 1 3 ) , Tr(a 3 u) - (01001101) 4 a v (0 a4 a 5 a6 a8 a 1 2 a9 a 1 4 ) , Tr(a 4 v) = (00010111) a5v (0 a 5 a 6 a7 a9 a 1 3 a 1 0 1), Tr(a 5 v) = (00111100) a6v (0 a 6 a 7 a 8 a10 a 1 4 a 1 1 a), T r ( a S ) - (01100110) a7v = (0 a7 a 8 a 9 a 1 1 1 a 1 2 a 2 ) , Tr(a7-!;) — (01011010) a8v = (o a8 a 9 a 1 0 a 1 2 a a 1 3 Tr(oV) = (00101011) Q a v = (0 a9 a 1 0 a 1 1 a 1 3 a2 a 1 4 a 4 ) , Tr(a 9 u) (01011010) a10v = (0 a 1 0 a 1 1 a 1 2 a 1 4 a3 1 a 5 ) , Tr(a 1 0-y) (00111100) auv - (0 a 1 1 a 1 2 a 1 3 1 a 4 a a 6 ) , Tr(a11v) - (01110001) a12v (0 a 1 2 a 1 3 a 1 4 a a 5 a 2 " ? ) , Tr(a 1 2-i;) — (01110001) a13v = (0 a 1 3 a 1 4 1 o? a 6 a 3 a 8 ) , Tr(a13<y) = (01100110) 14 a v — (0 a 1 4 1 a a3 a 7 a 4 a 9), TT(a14v) = (01001101) The m = 4 possible co-ordinates in the (dual) basis will select either three binary 8-tuples of weight 4, and the all zero 8-tuple, or four binary 8-tuples of weight 4. • Thus, we have shown that IljgBo zi n a s a b m a ry weight of either m2 m _ 2 or (m — l ) 2 m - 2 . The 33 terms /?0 = lTies,, zj n a v e binary weights two times as large. Due to Lemma 3.1, this fact may be extended to (5k = Y\j€{B0+k} z]i with k G B*. We now determine the breakdown between the two different weights (as k is varied.) Let x be the number of codewords with binary weight m2 m _ 1, and y the number with binary weight (m- l ) 2 m - 1 . Then, x + y = n. (3.15) Next, fixing j and varying k, each of the non-zero field elements is cycled through. Adding in this way, we get a weight of Wm. There are 2 m _ 1 — 1 possible non-zero values for j, and hence 2 W m x ( 2 m - 1 - l ) = m2 m~ 1x + (m- l)2m~ly m 2 m ( 2 m - 1 - l ) = m2m-1x + (m-l)2m-ly. (3.16) Solving (3.15) and (3.16), we obtain x = 2m — 1 — m = n — m y = m. Having shown the binary weight distribution of certain common occuring structures in ewe's, we may determine the binary weight distribution of the codes given in Table 2.2. The result is shown in Table 3.3, where At denotes the number of codewords of weight i. 34 Table 3.3: Binary weight distribution for various Reec -Solomon and extended Reed-Solomon codes code b k non-extended i Ai extended i Ai 1 1 1 2 1 3 jn (™) i=0,l , . . . ,m jn ( m) j=0,l,...,m m2m~1-j n(™) j=o,i,...,m jq ( m ) j=0,\,..,m jq ( m) j = 0,l , . , m m2 m- 1 gr(g - 1) jq ( 7 ) j=0,l , . . ,m ( m - l ) 2 m - 1 \q(q-l)m + lq(q-l)(q-l-m) ( m + l ) 2 m - 1 \q(q-l)m 3 3 m2 m- 1 n ( m - l ) 2 m _ 1 mn m2 m _ 1 w(n - m) + 2n m2 m _ 1 n ( m - l ) 2 m _ 1 mn m2 T n _ 1 - m) + 2n 35 4 The probability of undetected error for certain binary RS codes The probability of undetected error of a code is an important measure of code performance, espe-cially in determining error detection capabilities. We shall be considering the binary expansions of RS codes when used over the binary symmetric channel (BSC). In the following sections, & family of codes refers to all codes with the same dimension k, and 6. We obtain different codes by changing the field Fq (i.e., changing m). 4.1 -P«d(e) and properness Given a BSC, let e denote its cross-over probability (i.e., the probability of a bit error.) The probability of undetected error, Pud(e), for a code7 is the probability that the error vector matches one of the codewords, and is normally calculated as a function of e. If the PU(j(e) of a code is monotonically increasing with e, it is referred to as a proper code [18]. If there exists an e 6 [0, |] where p is the number of parity bits in the code, the code must be improper [2]. In the cases we consider here, p — m(n — k) for non-extended codes, while p = m(q — k) for the extended ones. If the Hamming weight enumerator [2, 4] of a code is known, Pud(c) can be easily calculated. Given a binary code of block length n and dimension k, let Ai denote the number of codewords of Hamming weight i in the code. Its Hamming weight enumerator is: such that (4.1) n A(z) = A0 + Axz + A2z2 + ••• + Anzn = J2A<zi-i = 0 When used solely for error detection. 36 Figure 4.1: o-input, g-output symmetric, memoryless channel The PU(j(e) of the code, when used solely for error detection, may be expressed in terms of A(z) since n Pud(e) = ^ ^ ( l - e ) " - ' (4.2) t=i = ^-^^{j^-il-eT (4.3) If B(z) is the Hamming weight enumerator of the dual code, P„d(e) may also be expressed in terms of B(z), using MacWilliams's identity [4] Pud(i)=^B{l-2e)-{l-eY. (4.4) Kasami and Lin [13] showed that RS codes are proper when used over the g-ary symmetric channel, shown in Figure 4.1. We shall show in Theorem 4.1 the surprising result that the binary expansions of RS codes are not necessarily proper. In fact, most of the codes examined in this thesis are improper, and for a given m, a rate is found such that all binary RS codes with rate below this are improper. A comparison of the Pud{() for RSi(7,l) over a g-ary channel, and the 37 Pud(c) of its binary expansion over the BSC is shown in Figure 4.2. 4.2 The properness of k = 1 RS codes In the previous chapter it was shown that the binary weight distribution of RSI(TC, 1) is A0 = 1 M Ain = 1^1 i = 1,2,.. .,m while for ERSi(<7,1)> the distribution is A0 = 1 Aiq = (™^J i = 1,2,.. .,m By letting N — n or q, the following discussion applies to the binary expansions of both non-extended and extended RS codes. Note that the block length of the binary expansion is then mN. From eqn. (4.3) the -PU(j(e) of these codes, when used solely for error detection, is then m / \ , v jN JUO = (i - (7) (737) - u - *rN- (4.5) At e = l/m, we have 38 Figure 4.2: P„d(e) for RSi(7,1) (over g-ary channel) and its binary expansion (over BSC) Note that lower bounding (4.8) by (4.9) is quite tight, since r"_ 1 approaches 1 as m increases. Taking log of both sides yields8: logP u d(l/m) > mTVlog — — TVlog(m-l) (4.10) = N[(m - l)log(m- 1) - mlogm]. (4.11) Because log2 - p = m(l — N), the binary expansion code is not proper if: N [(m - l)log(m - 1) - mlogm] > m(l - N), or equivalently N T m - 1, , J , , X llogm logfm - 1)1 < 1, m^O (4.12) iV — 1 N log m log(m — 1) m Since the first term in (4.12) monotonically decreases to 1 as m —> oo, and the second tends to 0, the product tends to 0. Differentiating the second term with respect to m yields: log(m-l) [ (m-l)log(m-1) = log(m - 1) m m 2 m 2 which is negative for m > 2. Hence, the LHS of (4.12) is monotonically decreasing, and it follows that if m' satisfies the bound (4.12), all m > m' will also satisfy (4.12). For this case, m' = 4. The cases where m < m' may be checked separately. When m = 3 (see Figure 4.2), the binary expansion is not proper, while for m = 2, it is. Thus, we have shown Theorem 4.1. The family of codes RSi(n, 1) and ERSi(q, 1) are not proper Vm > 3. 8 A l l logs are to base 2. 40 4.3 Properness of higher dimensional codes and severity of improperness For codes which are not proper, we wish to determine how improper. There exists an e 6 [0, ^ ) such that -P„d(e) is maximum. Define f - log 2 < log 2 (4.14) as the severity of improperness of the code. A code with a high severity of improperness may be exploited to show that codes over the same field of higher dimension have binary expansions which are also improper. Table 4.1: Severity of improperness for various binary expansions of k — 1 codes code £ e code £ e RSx(7,l) 0.3123 0.3362 ERSi(8,l) 0.5516 0.3347 RSi(15,l) 9.323 0.2500 ERSi(16,l) 10.07 0.2500 RSi(31,l) 40.42 0.2000 ERSi(32,1) 41.81 0.2000 RSi(63,l) 128.9 0.1667 ERSi(64,l) 131.0 0.1667 RSi(127,l) 358.8 0.1429 ERSi(128,l) 361.7 0.1429 Formalizing this concept, we have Lemma 4.2. Given £ for a code of dimension k over , and k' such that £ = mk! + r 0 < r < m. Then, the codes of dimension k + 1, k + 2, ..., k + k' are also improper. Proof. Ail the codewords in the binary expansion of RS(,(«, kx) are contained in RSj(n, k2), k2 > kx. This is because for kx < k2, the generator polynomial for RSj(ft, kx) is a multiple of the generator 41 polynomial for RSj(n, k2). As a consequence, the Pud(e) for RSJ(TC, ki) is always strictly less than the P„d(e) for RSj(n, k2), for all values of e S [0, |]. For the binary expansion of RSj(n, k), the 2~p bound is 2~ m(n — k) while for RS(,(n, k + Ak), it is 2~m(n — A: — Ak) ^ 2 _ m ( n —^) The bound for the higher dimensional code is 2mAk times that of RS&(n, k). Therefore, if the P„d(e) of RSj(ri, A;) exceeds its 2~p bound by at least 2mAk, the P„d(e) of RS6(n, k + Ak) must exceed its bound also. Hence, £ > mAk. Figure 4.3 illustrates this. • Note that there is no similar concept for proper codes. In general, the e, and hence £ are difficult to find. Using the £ for the k = 1, b — 1 codes in Table 4.1, we shall show: Theorem 4.3. For a given m, the binary expansion of Reed-Solomon and extended Reed-Solomon codes with b = 1 are not proper for rates r < l - l o g m H log(m - 1) = r*. (4.15) m Proof. 9 The bound in (4.12) may be generalized to higher values of k by changing the first term Again, the proof applies to both non-extended and extended case. N is the block length of the (non-binary) code in question. 42 Figure 4.3: Pud for binary expansions of RS codes, TO = 4, k = 1,2,3. The graph is normalized to 2 p for RSx(15,1), i.e., 2 56. Note how Pud for RSi(15,1) exceeds the 2-P bound for both RSX(15,2) and RSi(15,3). Eqn. (4.12) then becomes: N N -k log TO - m _ log(m - 1) m < 1. Rearranging for k yields k < N m — 1 1 — log m H — — log(m — 1) TO nr (4.16) • 43 4.4 Pud(t) for some 6^1 RS codes Staying with the one dimensional k = 1 case, we now examine the codes when 6 — 1 and n are relatively prime, whose binary weight distribution is (see Table 3.3) 4 a - ' = n. (4.17) It is known [18] that the maximum of A;e8'(l - e)" _ i occurs at e = i/n. So, for the weight distribution given in (4.17), P u d( e) = n e m 2 m " 1 ( l - € ) " m - m 2 m " 1 which has a maximum at m 2 m - i 2™-1 > 1/2. (4.18) m(2m - 1) 2m - 1 For the extended case, the same binary weight distribution applies, but the block length is mq — m2m. The e for which Pud(e) is maximum is then ^ — = 1/2. (4.19) m2m ' v ; So, the families of codes RSj(n, 1) and ERSj(n, 1) with 6 ^ 1, 6 — 1 and n relatively prime, have binary expansions which are proper for all values of m. The case where 6^1, but 6—1 and n are not relatively prime have binary weight distributions which depend on the basis chosen, and hence are not analysed. For the k = 2, 6 = 3 case, the binary weight distribution is An = 1 44 •4(m-i)2>»-i - mn (4.20) Am2m-i = n(n - m) + 2n and in general is not proper for large values of m. Using equations (4.20), the probability of undetected error is: Pud(e) = /i(m)(l - c)"»-«'i(»0 £»i("0 + / 2 ( m ) ( l - 6)"'»-«'»(™)€«'a(™) (4.21) with /i(m) = mn f2{rn) = 2n + n(n — m) wi(m) = (m-l)2 m _ 1 w2(m) = m2TO-1 We must show that there exists a value for e £ [0, |] such that PUd(e) exceeds the 2 _ m( n - 2) bound. Because the first term in (4.21) dominates, we try wi(m) m-12 m _ 1 nm m n = a(m) (4.22) Taking the log of eqn. (4.21) and substituting (4.22), l°g fi + (nm — w i ) l°g(l — a) + Wi log a > 2m — mn (4.23) log nm nm + f l - ^-)\og{l-a) + — loga > --1 (4.24) \ nm/ nm n loff TlTTl 2 6 + ( l - o ) l o g ( l - a ) + ologo > --1 (4.25) nm n log nm . . 2 . 6 + if 2(o) < 1 - - (4.26) nm n where H2(a) = -alog 2 a - (1 - a) log 2(l - a), is the entropy of a. Referring to Figure 4.4, we see that this inequality is true for 5 > m > 50. The trend certainly shows that the inequality in (4.26) continues to be true for larger m. This, unfortunately, could not be rigourously proved. Instead, we make the following conjecture. 45 Conjecture 4.1. The binary expansion of RS3(n, 2) over is not proper for values of m > Below is a table of £ for the RS3(?i, 2) family. m bin. wt. dist. e 5 A64 = 155 ^80 = 868 2.405 6 •4l60 = 378 ^192 = 3717 3.007 7 ^384 = 889 ^448 = 15494 7.707 8 -4889 = 2040 4^-1024 = 63495 16.79 9 ^2048 = 4599 ^2304 = 257544 33.92 10 ^4608 = 10230 ^5120 = = 1038345 65.92 Applying Lemma 4.2 to this family would then show that RS3(511, k) is improper for k = and 5, and RS3(1023, k) improper for k = 3 .. .8. 46 A common trait for codes which are improper is its asymptotic behaviour in m. If one member of the family is improper, then it will remain improper as m is increased. We venture to make the following (unproven) conjecture: Conjecture 4.2. Given a family of codes for which m! is the smallest value of m such that the binary expansion code is improper, then, the binary expansion codes for all m > ml are also improper. We see that this seems reasonable, since £ increases rapidly with m. Note also that e decreases as m increases. 4.5 P r o p e r n e s s o f dua l s o f some codes The P„d(e) for some high rate codes are now examined, using eqn. (4.4). Codes of dimension k = n — 1 are dual to the RSj(ri, 1) codes. When gcd(6 — l,n) = 1, we can use the binary weight distribution A0 = 1 A m 2 m - i = n = 2m - 1. If b = 2 (note that 1 and n are always relatively we get prime), we get the dual to RSi(n, n - l ) 1 0 . In general, the dual code is RS n_i + ( l(n, n - 1) = RSb^i(n,n - 1). Applying the restriction that gcd(6 — 1, n) = 1, we conclude that Lemma 4.4. All RSi(n,n — 1) codes, where gcd(6,n) = 1 and 6^0 have binary expansions which are proper. 1 0 See the last sentence of section 1.3. 47 Proof. The probability of undetected error is given by Pud{e) = 2~m f l + (2 m - 1)(1 - 2e )m 2 m _ 1 l - (1 - c)^ 2""- 1) (4.27) This probability function is monotonically increasing for e € [0, |], so the code is proper. To see this, we take the derivative of (4.27) pM = m(2 m - 1)(1 - c ) - 2 m — i - m ( 2 m - l ) ( l - 2 e ) m 2 m " 1 - 1 = m(2m-l)[(l-e)*-(i_2£)"] where x = m2m -m-1 y = m2 m _ 1 - 1 (4.28) (4.29) Now, (1 - e) 2 x = (1 - 2e + e2)* > (1 - 2e)r, so (1-e)' > ( l - 2 e ) f , Also y > x/2, so that (1 — 2e)a > (1 — 2c)y. Therefore, eqn. (4.29) is always greater than 0. • If b = 1, the binary weight distribution A0 = 1 must be used instead. In this case, m' i i i = 1,2,..., TO Pud(e) = 2" 1 + E ? ( 1 - 2 ^ " - ( 1 - 6 ) " = 2~m [1 + (1 - 2e)"]m - (1 - e ) m n . (4.30) (4.31) 48 Table 4.2: Severity of improperness for the binary expansions of RS0(n, n — 1) and RSi(n, n — 2) RS0(n, n-1) RSi(n, n-2) m I 6 e 3 0.01996 0.1816 — — 4 0.4642 0.04748 — — 5 1.079 0.0167 0.02375 0.0425 6 1.774 0.00655 0.12829 0.0132 7 2.519 0.00275 0.33113 0.00495 8 3.302 0.00115 0.64708 0.00185 is the probability of undetected error for the binary expansion of RS0(n, n — 1). Table 4.5 shows the values of £ for various m. The code is hence not proper for 3 < m < 8, and most likely for all m > 3. Similarly, the binary expansion of RS^n, n— 2) is obtained from the RS 3(n, 2) code (since it is the dual), and is not proper for all m > 5. 4.6 Codes which are not invariant w.r.t. basis All the codes mentioned so far have binary expansions which are invariant w.r.t. all bases. The uniqueness of the binary weight distribution makes analysis easier. Kasami and Lin [14] show that codes (with b = 1) of dimension k = 1, 2, and 3 are invariant. Those with k = 4 are invariant only for odd m. The properness/improperness of the invariant codes was discussed in previous sections. For the other codes, some mappings might result in proper binary weight distributions, whereas other may not. In fact, we are not aware of an easier way of determining the number of unique binary weight distributions, other than exhaustively trying all f i ' / n classes. The smallest non-trivial code which is not invariant to all bases is the RSi(15,4) code, which 49 yields 16 different binary weight distributions (from 56 equivalence classes.) Note that multiple classes may share the same distribution. Although these distributions are very similar, not all of them are proper. Table 4.3 shows the binary weight distributions for all possible bases. All expansions which are proper have A 1 5 = 4. While the higher weight codewords vary widely, the -Pud(e) are fairly close, as shown in Figure 4.5. The three expansions with A 1 5 = 9 are improper, but only slightly with £ « 0.02. Expansion #8 has a lower minimum distance, with AX2 — 5, and is much more improper with £ = 3.309. These results are not surprising, since it is the low weight codewords which dominate the probability of undetected error. Again, note that there is no way of predicting the number or weight distribution of the binary expansion codes. The most important point to note is that selection of basis may, in some cases, affect the properness of the binary expansion. There are cases, however, where codes are not invariant, but basis selection makes no difference to properness. All codes covered by Lemma 4.2 are improper, regardless of the basis chosen. The proof of the result does not depend in any way on the basis for the binary expansion. This fact, however, has not been verified by explicit enumeration of an example. The smallest codes for which this may be done are RSi(31,5) or RS!(63,4). 4.7 Summary A number of codes have binary expansions which are improper. They are: • RSi(n,l) and ERSi(?,l) Vm > 3 • the dual of the above, RSo(», n—1) Vm > 3 • RS3(n,2) Vm > 5 • the dual of the above, RSi(n, n — 2) Vm > 5 50 Table 4.3: Binary weight distributions for the RSi(15,4) code # bases 1^2 -423 Ms -424 -4l6 -4 2 5 A 1 7 A26 An A27 Aw A2i -42o -429 -421 -43o -42 1 {1, ot, « ' } {1, a, a 5} 0 4 0 0 35 90 225 500 780 {1> °>, {1, a 2 « 8 , a 1 1 } , a 1 0 } 1500 2375 2850 3285 4660 6585 6780 6136 2 {1, « « , a 9} {1. <*, a1 0 a 1 3 } 0 9 15 45 20 45 135 395 840 {1, a 2 {1, a 3 , <*"} , a"} 1545 2645 2955 3180 4715 6420 6675 6256 3 {1. a. a l a } {1, <*> a 2 , a9} 0 4 0 0 50 60 270 470 780 {1, <*, {1, a 2 oi\ a 1 2 } , a » > 1590 2330 2940 3150 4600 6615 6720 6376 4 {1, « . « 3 , *«} {1, a, <*\ a 1 0 } 0 4 0 0 70 60 90 560 1260 {1, a 2 {1, a 3 , oi6 , « 1 2 } , a 1 0 } 1560 1110 2700 5850 4600 2895 6900 10216 5 {1, « , « 8 , a 1 2 } {1, a, oi7, a1 3 } 0 9 15 45 20 30 165 410 780 {1, a, J l , a 2 « 9 , a 1 2 } , « 9 > 1620 2555 2880 3420 4565 6480 6825 5896 6 {1. o>h, «*"} {1. oi, « S , 0 4 0 0 50 90 255 500 750 {1, <*2 {1, a 2 , oJ a 7} 1500 2465 2850 3270 4660 6525 6780 6196 7 {1, <*> a 3 , {1. a 6 , « 7 } 0 9 15 45 20 30 180 380 750 {1, a 2 {1, a 3 a"} a"} 1710 2510 2880 3540 4325 6510 7005 5716 8 {1, « , a"} 5 64 15 0 0 0 60 320 1440 960 1060 3840 5760 6400 2954 5800 10176 9 {1, oi, « t t , « * } « 7 , 0 4 0 0 35 105 225 485 840 {1, a 2 a 4 a 1 2 } 1425 2465 2945 3045 4810 6525 6630 6496 {1. <*, « 2 , <f 10 {1. a. a 3 , a"} {1, oi, a 7 , a 1 2 } 0 4 0 0 50 105 210 455 780 {1. <*> {1, a 2 a 1 0 a* a 1 2 } a 9} 1515 2510 2925 3150 4570 6495 6810 6376 11 {1> a, « a , « 3 } {1, a, « 7 , ««}) 0 4 0 15 5 105 240 470 870 {1, a 2 {1, a 3 a 4 a 7 « 6 } « " } 1470 2420 2835 3195 4645 6555 6840 6196 12 {1. oi, « 3 , a 1 1 } {1> «> «5 , « 7 } 0 4 0 15 40 75 105 530 1290 {1, a, {1. oi, « 5 , « 9 , a 1 3 } « " } 1530 1065 2685 6000 4585 2925 6960 9916 13 {1. «a , a 1 1 } {1> oi, « S , a 9} 0 4 0 15 20 105 210 470 840 {1, a, {1, a 2 « 8 , a 4 a 1 3 } 1470 2510 2835 3180 4645 6495 6840 6256 14 {1, a 3 a" 0 4 0 0 70 60 105 500 1350 1500 1065 2940 5490 4840 2925 6540 10756 15 {1, a, a 1 0 } 0 4 0 0 55 90 75 590 1260 {1, a 2 a* a 1 2 } 1470 1155 2610 5985 4660 2865 6960 9976 16 {1> «a . a"} {1, a 1 2 } 0 4 0 0 20 135 225 485 810 {1, {1, a 2 a 6 , a 4 «•} « 9 } 1425 2465 2835 3300 4630 6525 6870 6076 Distributions are symmetrical, so A{ = A60-i. 51 Table 4.4: Improper binary expansions of RSi(15,4) # e 7 0.0252 0.3008 5 0.0239 0.3009 2 0.0276 0.3005 8 3.309 0.2106 Using Lemma 4.2, we may also conclude that • RSi(n,fc) and ERSi(g,A;) for all rates < 1 - log m + log(m - 1) • RS3(127,3) and RS3(255, k) for k = 3 and 4 • RS3(511,Jfe) for k = 3, 4, and 5 • RS3(1023,fc) for k = 3.. .8 have improper binary expansions. Although the number of codes with improper binary expansions is large, there are, nonetheless, some codes with binary expansions which are proper • RS6(n, 1) with gcd(6 — 1, n) = 1 • RSj(n, n — 1) with gcd(6, n) = 1 (dual of the above) One cannot help notice the relationship between dual codes. In general, the dual of a proper code is not necessarily proper [18]. However, there is no evidence of this here, suggesting perhaps that the structure of Reed-Solomon codes makes them an exception. 52 Figure 4.5: PUd(c) for the different binary expansions of RSi(15,4) Vertical axis is normalized to 2 p = 2 4 4 for the code. 53 5 Conclusions In this thesis, we have considered Reed-Solomon and extended Reed-Solomon codes over Wq. The complete weight enumerators for certain simple cases of these codes were derived. These expressions were obtained by considering the solutions to algebraic equations over Wq, a method which is not scalable to codes with large values of k. The expressions, although complicated, contain a great deal of structure. Complete weight enumerators for extended RS codes were found to be simpler to deal with than their counterparts for RS codes. In an effort to convert codes over Wq to binary codes, the bases of Fq over F 2 were considered. An equivalence relation was defined, which partitions the bases into equivalence classes. For all linear codes over F?, bases in the same equivalence class map the code to binary expansions with identical weight enumerators. Given the set of bases a code is invariant to, the dual code is invariant to the dual set of bases. This dual set is in general not equal to the original set of bases (except for m = 3), but is not difficult to calculate. A certain basis and its dual do not necessarily yield the same binary code. For codes which are invariant with respect to all bases (i.e., have a unique binary expansion), we have calculated the weight distribution of this binary expansion. The probability of undetected error for binary expansions was also considered. A majority of these were found to be improper, although specific examples of codes with proper binary expansions are given. For a given m, a rate r* was found such that all codes with rates less than r* are improper. This bound covers a great percentage of the codes, especially as m increases. Although the emphasis is on codes which are invariant with respect to all bases, an example of a code which is not invariant is given. It is important to remember that for such codes, the selection of basis 54 may affect the properness of the resulting binary expansion. The r* upper bound also affects codes which are not invariant with respect to all bases (i.e., for k > 5.) 55 6 Directions for future work Many interesting questions and problems are left unanswered in this thesis. First, the ewe's of Reed-Solomon and extended Reed-Solomon codes show considerable struc-ture. The method used to derive them involves analysing algebraic equations of the form f(x) = a3 (6.32) over finite fields, where f(x) is a polynomial in x. Thus, we are restricted to codes of dimension less than 3, since little is known if f(x) has degree greater than 3. However, equations like (2.20) should be easier to solve, since x may be factored out. Thus, if the solution to eqn. (6.32) is known, perhaps equations of the form xk f(x) = a3, k a positive integer could be solved by breaking it into two separate equations: xk = a3'* f(x) = a* These equations must be solved simultaneously for all integer i. Also, the ewe's of extended Reed-Solomon codes are simpler than those for non-extended Reed-Solomon codes. The reason for this is unknown, but this additional structure may aid in determining their ewe's. The bases of Fq over F 2 are numerous in number, and are partitioned into equivalence classes to ease analysis. All bases in the same class were found to yield the same binary weight distribution, 56 for all linear codes. Thus, the amount of work required to determine the invariance of a code is proportional to the number of classes. An alternative equivalence relation which partitions the bases into a smaller number of classes (more bases per class) would reduce this work. Although symmetry of the variables of the ewe of a code implies invariance w.r.t. all bases, the k = 3 case is a simple example where this requirement is not necessary. We have tried to consider weaker conditions on a ewe to conclude a code is invariant w.r.t. all bases, with no concrete results. Classical invariant theory, developed by Hilbert in the late 1800s [17], may prove useful. Invariant theory has been used by Sloane [19][4, ch. 19] to determine codes which are self-dual. We had a similar analysis in mind. The rate bound in Theorem 4.3 covers a large percentage of low rate codes. No similar bound was found for high rate codes, although there is evidence to suggest that many high rate codes are improper. Conjecture 4.1 remains to be verified. However, in all practical terms, values of m outside the range for which this inequality has been shown to be true are rarely used. Conjecture 4.2 is more interesting. If it is true, inequalities such as eqn. (4.26) need not be solved. Induction on m seems the most likely proof. Consider a family of codes with / weights for which there are non-zero A,-. The weight enumerator of the binary expansion would then be of the form l ^/ t(m)z w-( m) i = l with /,• and W{ monotonically increasing functions in m. Assuming that for some m> m' i Pud(e) = ^ 2fteWi(l - e)nm-w' > 2~m^-^ i = l 57 for some value of e 6 [0, |], we need to show that 3e € [0, ~] such that i £ fi(m + l)eWi^m+1\l - c jnfm+i j-K^m+i) > 2 - ( » » + i ) ( » - * ) . (6.33) 1=1 The restriction that and tu,- are monotonically increasing may be sufficient to show (6.33). If not, further restrictions on the differences /,(m + 1) — /,-(m) and Wi(m + 1) — Wi(m), which are simple to test, may cause (6.33) to be true. Showing conjecture 4.2, or determining testable conditions under which conjecture 4.2 is true will allow us to avoid examining inequalities for P„d(e) for each code we wish to consider. 58 Glossary Fq — the finite field with q elements. F£ — the non-zero elements of Wq. a — a primitive element of F?. B — the set {*, 0, 1, 2, ..., n — 1} B* — the set {0, 1, 2, ..., n - 1} <B — the set of all bases of Wq over W2 • — a subset of 2$ such that all bases in J yield a binary code with the same weight distribution. C — a linear (n,k) code. CL — the dual code of C. n — the block length of a code, n — 2m — 1. q — number of elements in a field, q = 2 m, where m £ {2,3,4,...}. — symmetric group of permutations with m elements. RS — Reed-Solomon code. ERS — Extended Reed-Solomon code. ewe — complete weight enumerator. Tr(x) — trace of a field element x £ Fq. — probability of undetected error. 59 References I. Blake and K. Kuth, "On the complete weight enumerator of Reed-Solomon codes," SIAM journal on Discrete Mathematics, vol. 4, no. 2, pp. 164-171, 1991. S. Lin and D.J. Costello, Jr., Error Control Coding : Fundamentals and Applications. Engle-wood Cliffs, N.J.: Prentice-Hall, 1983. W. Peterson and E.J. Weldon, Jr., Error Control Codes. Cambridge, M.A.: MIT Press, 1972. F. MacWilliams and N. Sloane, The Theory of Error-Correcting codes. Amsterdam: North-Holland, 1977. E. Gilbert, "Capacity of a burst-noise channel," Bell System Technical Journal, vol. 39, pp. 1253-1266, 1960. B. Fritchman, "A binary channel characterization using partitioned markov chains," IEEE Transactions on Information Theory, vol. IT-13, pp. 221-227, 1967. F. MacWilliams, "A theorem on the distribution of weights in a systematic code," Bell System Technical Journal, vol. 42, no. 1, pp. 79-94, 1963. V. Pless, "Power moment identities on weight distributions in error correcting codes," Infor-mation and Control, vol. 6, pp. 147-152, 1963. I. Herstein, Topics in Algebra. New York: Wiley, 1977. R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications. Cambridge: Cambridge University Press, 1986. E.F. Assmus, Jr., H.F. Mattson, Jr., and R. Turyn, "Cyclic codes," Tech. Rep. AFCRL-65-332, Air Force Cambridge Research Labs., 1965. T. Kasami, S. Lin, and W. Peterson, "Some results on weight distrbution of bch codes," IEEE Transactions on Information Theory, vol. 12, p. 274, 1966. T. Kasami and S. Lin, "On the probability of undetected error for maximum distance separable codes," IEEE Transactions on Communications, vol. COM-32, no. 9, pp. 998-1006, 1984. T. Kasami and S. Lin, "The binary weight distribution of the extended (2 m, 2 m -4) code of the Reed-Solomon code over GF(2 m)," Linear Algebra and its Applications, vol. 98, pp. 291-307, 1988. 60 [15] E. Berlekamp, H. Rumsey, and G. Solomon, "On the solution of algebraic equations over finite fields," Information and Control, vol. 10, pp. 553-564, 1967. [16] F. Mac Williams, "The structure and properties of binary cyclic alphabets," Bell System Tech-nical Journal, vol. 44, no. 2, pp. 303-332, 1965. [17] D. Hilbert, Theory of Algebraic Invariants. Cambridge: Cambridge University Press, 1993. [18] S. Leung-Yan-Cheong, E. Barnes, and D. Friedman, "On some properties of the undetected er-ror probability of linear codes," IEEE Transactions on Information Theory, vol. IT-25, pp. 110-112, Jan 1979. [19] N. Sloane, "Error-correcting codes and invariant theory: new applications of a nineteenh-century technique," American Math. Monthly, vol. 84, pp. 82-109, 1977. 61 Appendix A If f(x) is a polynomial of degree d < n with coefficients in the extension field Fj™, with m > 1, then /(l) + /(a) + /(a 2) + ... + /(a"- 1) = /(0). Let a be a primitive element of the field, and n — 2 m — 1, which is odd. Proof. Let f(x) = a0 + aix%- Consider: /(l) = a0 + aj + a2 + ... + ad /(a) = a0 + axa + a2a2 + ... + adad /(a 2) = a0 + axo? + a2a4 + ... + ada2d f(a{) = a0 + aja* + a2a2i + ... + adaid /(a"" 1) = ao + ^ a " " 1 + a 2 a 2 ^ + ... + a d a ^ d Summing the equations yields n —1 n —1 n —1 n —1 t'=0 t'=0 t' = 0 t = 0 Further, it is well known that for n > 2 n-1 £ V = l + a + e^ + .-. + a"-1 = 0 (A.2) t'=0 The sums in (A.l) may be written as i=0 i=0 where /? = a d, another field element in . All elements have orders which divide n, so (3n = 1. Multiplying eqn. (A.3) by /? yields n-1 0^>2 = P + (32 + f- / 3 n _ 1 + /?" 1=0 62 and therefore n-1 (!-/?)•£; = 1-/3" = 0 i=0 Since ft ^ 1, 52?= 0* = 0> a n d the s u m m (A-l) then simplifies to n —1 n —1 n —1 na 0 + ai £ a* + a 2 £ a 2' H + ad £ ad* = na 0 i = 0 8 = 0 t'=0 = a0 since n is odd, and the field has characteristic 2 /(0) 63 Appendix B Given the set of elements in Wq with trace 0, {a'\i £ B0}, the new set {o^a'li £ B0, k £ B \ {0,*}}, has elements evenly distributed between those with trace 0 and those with trace 1. There are 2 m _ 1 elements in these sets. Proof. By trace property (T-i), the set of all elements having trace 0 is closed. Multiplying each element of the set by ak does not change this closure property. In this new set, there is at least one element with trace 1. The zero element guarantees that there is at least one element with trace 0 in the new set. We assert that of the N = 2 m _ 1 elements, there must be exactly N/2 elements with trace 1. Elements have either trace 0, or trace 1 (property (X—iii)). Suppose there are A i elements with trace 1, and A 0 elements with trace 0. Taking an element with trace 1, and adding it to each element with trace 0 generates A 0 elements with trace 1. So, Ax > A 0. Similarly, taking an element with trace 1, and adding it to all other elements with trace 1 generates A i elements of trace 0. This implies that A 0 > A l 5 from which A 0 = A i = 2m~2. • 64
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Complete Weight enumerators and probability of undetected...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Complete Weight enumerators and probability of undetected error for some Reed-Solomon codes Ho, Kaiming 1995
pdf
Page Metadata
Item Metadata
Title | Complete Weight enumerators and probability of undetected error for some Reed-Solomon codes |
Creator |
Ho, Kaiming |
Date Issued | 1995 |
Description | The Hamming weight enumerators for Reed-Solomon codes are known, but do not often adequately describe the structure of the codes. Complete weight enumerators, on the other hand, describe the code in more detail, but are more difficult to determine. A procedure described by Blake and Kith [1] is used to derive the complete weight enumerators for Reed-Solomon and extended Reed- Solomon codes of dimensions one, two and three. Binary codes may be obtained from Reed-Solomon codes over a field with q = 2m elements. Many different bases may be used to obtain these binary codes. We analyse conditions under which two bases will yield binary codes with the same weight distribution. We also consider the probability of undetected error of these binary codes. It has been shown by Kasami and Lin that (n,k) Reed-Solomon codes used over a q-ary symmetric channel are proper. In this thesis, it is shown that the binary expansions of these codes and their extensions, when used on the binary symmetric channel, are not necessarily proper. In particular, the codes of rate less than [l — log[sub]2 m + m-1/m log[sub]2(m — 1)] are not proper. |
Extent | 2357356 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-01-21 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065007 |
URI | http://hdl.handle.net/2429/3835 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1995-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1995-0357.pdf [ 2.25MB ]
- Metadata
- JSON: 831-1.0065007.json
- JSON-LD: 831-1.0065007-ld.json
- RDF/XML (Pretty): 831-1.0065007-rdf.xml
- RDF/JSON: 831-1.0065007-rdf.json
- Turtle: 831-1.0065007-turtle.txt
- N-Triples: 831-1.0065007-rdf-ntriples.txt
- Original Record: 831-1.0065007-source.json
- Full Text
- 831-1.0065007-fulltext.txt
- Citation
- 831-1.0065007.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0065007/manifest