UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Coding theory and algebraic curves Edwards, Brandon Gary 1997

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_1997-0235.pdf [ 1.61MB ]
Metadata
JSON: 831-1.0079766.json
JSON-LD: 831-1.0079766-ld.json
RDF/XML (Pretty): 831-1.0079766-rdf.xml
RDF/JSON: 831-1.0079766-rdf.json
Turtle: 831-1.0079766-turtle.txt
N-Triples: 831-1.0079766-rdf-ntriples.txt
Original Record: 831-1.0079766-source.json
Full Text
831-1.0079766-fulltext.txt
Citation
831-1.0079766.ris

Full Text

CODING THEORY AND ALGEBRAIC CURVES by BRANDON GARY EDWARDS B.A. (Mathematics, Physics) Portland State University,(June 1993) A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES Department of Mathematics We accept this thesis as conforming to the required standard  THE UNIVERSITY OF BRITISH COLUMBIA April 1997 © Brandon Gary Edwards, 1997  In presenting this thesis in partial fulfillment 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 Mathematics The University of British Columbia Vancouver, Canada Date  A r\i ?  mi  Abstract In 1981 V.D. Goppa [9] used the evaluation of rational functions on algebraic curves to define a new and exciting class of error correcting codes now known as geometric Goppa codes. As with any other error correcting code however, this construction procedure alone was only the beginning of what was need in order that these codes could be used in practice. Procedures needed to be found to aid in both the explicit construction of certain geometric Goppa codes and the creation of efficient decoding algorithms. The problems surrounding these concerns have since motivated many coding theorists to become actively involved in the study of algebraic curves and have equally sparked the interests of algebraic geometers. In this paper I introduce the topic of coding theory and highlight the successes and failures that have occurred in the attempt to bring geometric Goppa codes to their full stage of implementation. In the first two chapters, I give a basic introduction to the theory of error correcting codes, assuming no previous knowledge of the subject. Chapter 3 is concerned with the construction of rational geometric Goppa codes for which no knowledge of algebraic curves is necessary. Various positive and negative aspects of these codes are discussed which motivates the introduction of the general class of geometric Goppa codes in the following two chapters. For the material in Chapters 4 and 5, I will assume that the reader is familiar with divisors and linear systems on non-singular projective curves. After I define the class of geometric Goppa codes, I go on to discuss the advances that have been made in the search for explicit constructions of some of the best codes in this class. Finally, I present some basic decoding algorithms for both rational and general geometric Goppa codes. These algorithms demonstrate how easy it is to develop efficient decoders in both of these cases.  ii  Table of Contents Abstract  ii  Table of Contents  iii  Acknowledgment  iv  Chapter 1. Error Correcting Codes 1.1 The Problem 1.2 Basic Definitions 1.3 The Problem Revisited 1.4 The Choice of ¥ q  1 1 2 4 4  Chapter 2. Linear Error Correcting Codes 2.1 Definition and Properties 2.2 The Singleton Bound  8 8 9  •  Chapter 3. Rational Geometric Goppa Codes 3.1 Definition and Properties  11 U  Chapter 4. Geometric Goppa Codes 4.1 Preliminaries 4.2 Definition and Parameter Bounds 4.3 Code Performance  15 15 16 17  Chapter 5. Decoding Algorithms for Geometric Goppa Codes 5.1 Basic Algorithm 5.2 Decoding Rational Geometric Goppa Codes 5.2.1 Algorithm 5.2.2 'C'-version of algorithm 5.2.3 Complexity 5.3 Decoding Geometric Goppa Codes  20 20 22 22 24 25 28  Bibliography  32  iii  Acknowledgment The basic ideas concerning geometric Goppa codes that I have expressed in this paper, (including the concepts and algorithm constructions of Chapter 5), were developed through reading a text on algebraic functionfieldsand coding theory written by Henning Stichtenoth [4]. For the material in Section 1.4, I am indebted to Joel Friedman for many clarifying discussions. Finally, for editing and guidance I would like to thank Bill Casselman, Kai Behrend, and Anne O'Halloran.  iv  Chapter 1 Error Correcting Codes  1.1  The Problem  Consider a battery powered space satellite orbiting a nearby planet and collecting data. Every hour the satellite observes whether or not a certain phenomenon has occurred and records the answer of 1 or 0, ('yes' or 'no'), in its memory. This satellite will never return to earth, so at some point the information must be transmitted back to its home country. To do so, it will pass the information to a battery-powered relay satellite halfway to earth. The relay satellite will then transmit the received message home. The problem lies in that the satellites are using weak transmission signals. There is a certain probability, both at the relay satellite and at home, that a transmitted 1 will be received as a 0 and an equal probability that a 0 will be received as a 1. We wish tofindan agreed upon 'coding' of the information that will minimize the probability of miscommunication while not wasting too much battery power in the process of sending and 'decoding' the messages. As a first attempt, we could use what is called a 'repetition code'. In this case every hour, the first satellite would record whether or not the phenomenon occurred and transmit the data, 'encoded' as say 101 repetitions of the appropriate signal. Therefore it will transmit either 1.. .1 or 0.. .0. The relay satellite would then simply count the number of l's and 0's in the received 101-tuple and 'decode' the message by taking the more frequently occurring symbol as the one intended. The decoded message, (either 1.. .1 or 0.. .0), would then be sent home, which would again be decoded upon receipt. Increasing the number of repetitions to 201, 401, and more; we could lower the probability of having an incorrect message after decoding to 1  Chapter 1. Error Correcting Codes  almost zero. However, the battery power required to transmit these lengthy messages as well as the increase power consumption due to the counting procedures needed to decode them would drain the batteries too quickly. The ratio of the number of signals required to send the original messages to number of signals used is called the information rate of a code. Therefore codes with lower information rates use up more time and energy and the problem with the repetition codes can be stated in the following way. Any repetition code whose corresponding probability of incorrect message reception is small will necessarily have a small information rate, therefore consuming too much time and energy. We are certainly forced to build the satellites so that their battery power can support the transmission of raw data for the duration of the mission, however it is clearly advantageous to keep the extra signals used for error control to a minimum. The development of the theory of error correcting codes depends mainly on constructing codes, C, which maximize the information rate and minimize both the probability of an incorrect message after decoding, (Pc), and labour in decoding.  1.2  Basic Definitions  We will base our analysis on a few practical assumptions. First of all, we will assume that information is being transmitted from one location to another as words of length n in an alphabet of q signals. To allow for the introduction of a field structure, (the specifics of which will be seen later), we assume that q = p  m  for some integer m and prime p. Finally, due  to week signal strength or some other physical problem, the received words will periodically contain some incorrect signals. We will assume that the probability of an error occurring while transmitting a signal is the same no matter what signal is being used and that the incorrect signal that is received can be any one of the q — 1 remaining signals with equal probability. We will start with a collection of vectors selected from the space  where ¥ denotes the finite q  field of order q. Every vector in this collection will represent a different message. In the case of the repetition code of length 101, this collection was {(0.. .0), (1.. .1)} C F^ . 01  2  Chapter 1. Error Correcting Codes  In addition, we require tools to aid in one of the most important aspects of our analysis: the determination of PQ- The value of Pc depends upon how many entries need to be changed in any given codeword to convert it into another codeword. The specific field entries that are involved in these changes are irrelevant due to our assumption on signal error above. In order to quantify these differences among codewords, we introduce a distance p to F£ given by /x(x,y) = { number of positions in which x and y differ }. It can be easily verified that (F^, p) is in fact a metric space. Before now, we have used the word 'code' in a vary loose sense. We can now introduce a precise definition.  D e f i n i t i o n 1 A code, C, is a subset of the metric space (F^, p) for some n.  To decode a given received vector x, we must then find a codeword, c, that is closest to x with respect to the distance p. In the case that the choice of c is not unique, we are forced to randomly select one out of the collection of 'closest codewords', all of which are equally likely to have been the intended message. One characteristic of C playing a vital role in the decoding process is called the minimum distance.  Definition  2 The minimum distance is defined as d — min{p(ci, c ) : C i , c € C , c\ ^ c } . 2  2  2  The importance of d in the decoding problem is due to the fact that any x £  whose distance  from C is less than ^, (where the distance from C to x is min{d(x, c) : c G C}), has a unique closest codeword. For a given code length n, we therefore would like the minimum distance to be as large as possible.  3  Chapter 1. Error Correcting Codes  1.3  The Problem Revisited  In this new language, it is relatively easy to address the problem of obtaining a low Pc value while keeping the information rate close to 1. Suppose we decide that the satellites in our example can only send 21 symbols per hour, lest their energy run out too quickly. Instead of using the repetition code of length 21, Ci, once every hour, it may be advantageous to use a 42 symbol code, C , once every two hours. In this case, C2 must consist of four codewords in 2  F2 to account for the messages 'no no', 'no yes', 'yes no', and 'yes yes'. Indeed, it turns out 2  that there are four word codes C C F , for which Pc is less than the probability of incorrect 4 2  2  2  message reception associated to using C i twice in one hour, Pc (2 — Pci)t  In fact, a basic result in coding theory called Shannon's theorem, (1948), tells us that the more information we send at one time, (for example in the above case, waiting four or five hours and more), the closer we can bring Pc to zero . 1  Nevertheless, there is still a lot of work to be done. Even though Shannon's theorem tells us that these codes have a low Pc value, there is no guarantee that there are efficient ways of decoding them. When a code lacks extra mathematical structure, the decoding procedure will amount to searching all of the codewords for the closest one to the received vector x. This can be a very lengthy process if the code is large. As we will see, the decoding procedures can be made more efficient when there is some order to the codeword distribution in F£. We will seek out the codes among the ones mentioned in Shannon's theorem that possesses this extra structure.  1.4  The Choice of ¥  q  In many applications, (satellites, telephones, computer modems, etc.), the information is being transmitted as words in only two signals, each of which can with equal probability p admit an error. Due to our assumptions in Section 1.2, we must therefore use the field F2 to construct codes for these cases. As a result, a large portion of the work in coding theory is focused on For a statement and proof of Shannon's theorem see [7]. 4  Chapter 1. Error Correcting Codes  codes.over F-j. In some of these applications, codes with lower PQ value and-or quicker decoding procedures are available if we allow ourselves to use fields other than F2. Therefore one may be tempted to use a code over another field such as F 4 , transmitting the F2 vector space equivalents of the elements in F 4 . In other words if F4 = {0, l,a, a }, then every time we want to send the 2  "signals" 0, 1, a, or a we simply just send the pairs of signals (0,0), (0,1), (1,0), or (1,1) 2  respectively. This effectively converts it from a code over F4 to a code over F2. If we do this, however, the resulting code over F2 will most likely not have the same PQ value as when the code was considered over F 4 . In addition, the ways in which the incoming messages are decoded will have to change considerably, which could result in an inefficient decoding procedure. In other words, the good qualities of the code as seen over F4 may not be preserved. To see this, we take as an example the simple two word repetition code over F4 of length 11 and compare the decoding procedure over F4 with the decoding that should occur if we send these codewords through a two signal channel as described above. Let C be the two word repetition code of length 11 over F 4 . Therefore C = { 0 , 1 } C F f where 0 = (0,... , 0) and 1 = (1,... , 1). If x 6 F 4 , let |x|i represents the number of ones in the entries of x and |x|n represents the 1  number of zeros. When receiving messages that were sent using C, it is then clear that any received vector in the set {x € F 4  : |x|i < |x|o} should be decoded as the message 0 and  1  any received vector in {x € F 4 : |x|i > |x|o} should be decoded as the message 1. Thus for 1  example the incoming message (a ,a , 2  2  a, a, a, a, a, a, a, 2  2  2  2  2  2  2  a ,0) 2  would be decoded as 0 and the message (a, a ,1, a , a, 0,a , l,a ,a:, a) 2  2  2  would be decoded as 1. 5  2  Chapter 1. Error Correcting Codes  Note that this decoding scheme is strongly dependent upon the assumptions laid out in Section 1.2. Let us examine the validity of these assumptions if we were to transmit the messages using only two signals '0' and '1'. First of all we notice that transmission can indeed occur with the use of four distinct "signals". These "signals" would be the pairs of signals (0,0), (0,1), (1.0) , and (1,1). Next, we see that assuming that the probability of error when transmitting any of the "signals" is the same no matter what "signal" you are transmitting is also valid. In particular, since we have assumed that a 0 or a 1 can error with equal probability p, it follows that each one of (0,0), (0,1), (1,0), and (1,1) can error with equal probability p' = 2p{l-p)+p =p{2  + p).  2  However, the last assumption is where we see a problem. That is, the assumption that transmission error will result with equal probability in any of the 3 remaining "signals". We can assume without loss of generality that we are attempting to transmit (0,0). If an error occurs, our assumption says that it is equally likely to result in the incorrect "signals" (1,0), (0,1), or (1.1) . The probabilities associated to these events are easily calculated however as p(l — p), p(l—p), and p respectively. For most applications, p is much less than a half. Therefore these 2  values differ significantly. This faulty assumption will have a strong impact on the effectiveness of our decoding procedure above. The problems due to "signal" dependent probabilities will magnify when considering these 11-tuple codewords. For example, we had agreed to decode the vector  x' = (a , a , a , a , a , a , a , a , a , a ,0) 2  2  2  2  2  2  2  2  2  2  as 0 = ((0,0), (0,0), (0,0), (0,0), (0,0), (0,0), (0,0), (0,0), (0,0), (0,0), (0,0)), whereas the actual F2 transmission of x', ((1,1), (1,1), (1,1), (1,1), (1,1), (1,1), (1,1), (1,1), (1,1), (1,1), (0,0)),  6  Chapter 1. Error Correcting Codes  was with much greater probability, (p (l - p ) n  1 1  as opposed to p (l -p) ), intended as the 20  2  message 1 = ((0,1), (0,1), (0,1), (0,1), (0,1), (0,1), (0,1), (0,1), (0,1), (0,1), (0,1)).  Similarly we can find many other 11-tuples that would be decoded incorrectly if we were to follow the decoding scheme based on the assumptions of Section 1.1. Therefore we see that our transition to ¥2 requires the reevaluation of our decoding procedure. In addition, since the value of Pc is strongly dependent on the ways in which incoming vectors can be decoded, it follows that our change to F2 will most likely bring about a different Pc value as well. The purpose of this section is not to drive us from the study of codes over fields other than F2. There are many uses to codes over these fields, even in cases where the information is being transmitted over a channel with only two signals. For example, there is a way of "combining" codes over F2 with codes over otherfieldsto make error correcting schemes that can be vary effective for communicating in two signals . What should be emphasized however is that codes 2  over arbitrary fields can be applied in the case of two signal channels only after much thought and hard work. Such applications should not be taken for granted.  2  These "combined codes" are called concatenated codes and are explained in detail in [3].  7  Chapter 2 Linear Error Correcting Codes  2.1  Definition and Properties  The subsets of F£ having the most natural structure are linear subspaces. Thefirststep in our move towards structured codes will be to limit our attention to codes C for which the codeword distribution is a linear subspace of F£.  Definition 3  subspace of  A code C is a linear code of dimension k if C = M.  C  where M. is a linear  of dimension k.  For the remainder of this paper, we will deal exclusively with linear codes. It is important to note that although a linear code is defined to be nothing more than a linear subspace of F£, it is characterized by much more than its linear structure. For example, the one dimensional linear subspaces in Z?> generated by (1,0,0) and (1,1,1) are linearly isomorphic and therefore equivalent as linear subspaces. However, the associated two word codes Mi and M.2 are far from equivalent, as their minimum distances are 1 and 3 respectively. The number of calculations required to obtain the minimum distance for linear codes is greatly reduced from that of an arbitrary code. This is due to the fact that the metric p, is invariant under affine translations. In particular if T is an affine translation of p(T{xi),T(x )) = /z(xi,x ). Let 2  then for any xi, x G F£, 2  be a linear code. Note that for any codeword c' € M, if  2  T is a translation taking c' to 0 then {c6C} = {T(c) : c G C}. 8  Chapter 2. Linear Error Correcting Codes Therefore due to the invariance of u under T we have that min{d(c',c) : c € C , c ^ c'} = min{ci(T(c'), T(c)) : c € C , T(c) ^ T(c')} = min{d(0,c) : c € C , c ^ 0 } , so that if d denotes the minimum distance for M then d = min {w(c) : c G M,c ^ 0} , where w(c) = u(c, 0) is called the weight of c. Thus to obtain d for linear codes, one only needs to calculate q distances where k is the dimension of C. This is a significant improvement to the k  ^-^2— number of calculations required in the general case, and is one of the many advantages to working with linear codes. Finally, along with the introduction of linear codes, it is useful to introduce a bilinear pairing on F£. If x and y are two vectors in F£, define n <  x,y  >  :=  ^ X i y i  .  i=l  We can then define the corresponding dual code of Jvi as  M* = (x € F£ : < x,c > = 0 V c e M } . This dual code can be very useful when analyzing the properties of M. In addition, taking the dual is a quick and easy way to produce new linear codes. It can turn out that M*, having parameters n' = n, k' — n — k, and d', is a better code than the M that it came from.  2.2  The Singleton Bound  In this section we discuss the problem of minimizing PM over all possible linear codes M of a given length n and dimension k. Recall from Chapter 1 that a low value of Pc is only one of the three main characteristics of a good code C. We know that to achieve this minimum for PM , we need to maximize the value of the minimum distance d. For the purpose of identifying codes whose parameters are optimal in this sense, we search for an upper bound on the value of d for any linear code of length n and dimension k. 9  Chapter 2. Linear Error Correcting Codes  Theorem 1 (SingletonBound) If M, is a linear code with parameters (n, k, d) then d < n - k + 1.  Proof. We have that M C I F ^ . Projecting M onto F £ in  by omitting the last entry of all vectors  _ 1  we obtain a new code of length n — 1. If d > 1, then no two of the codewords in M  could have differed in only their last entries. Therefore if d > 1, this new code has the same number of codewords, q , and so we obtain a code in F £ k  - 1  whose dimension is still k and whose  minimum distance is now greater than or equal to d — 1. Repeating this process d — 1 times gives us a code of dimension k in F^- + with minimum distance greater than or equal to 1. d  1  In other words this final code of dimension k fits inside W^~ . Thus k < n — d + 1 and so we d+1  obtain the Singleton bound d < n — k + 1.  • Therefore if a linear code M has parameters (n, k,d) where d = n — k + 1, it minimizes PM over all other linear codes of the same length and dimension. It should be noted however that for some values of n and k, no such code can be found. Therefore for some values of n and k, the Singleton bound is not a least upper bound for d . This bound will nevertheless be of l  great use to us. In Chapter 3 we will discover that all rational geometric Goppa codes have minimum distances that reach the Singleton bound and therefore these codes minimize PM- Due to the range of n and k for which we can produce rational geometric Goppa codes, this will in turn prove that that if n < q, the Singleton bound is a least upper bound for all values of k < n. For the construction of the general geometric Goppa codes in Chapter 4 we will see that the minimum distances come vary close to the Singleton bound, if not reaching it. This will provide us with proof of the fact that The fact that geometric Goppa codes in general lose little, if any, of the low PM values seen in the rational geometric Goppa codes.  For a more detailed discussion of this and other bounds on d, see [7]. 10  Chapter 3 Rational Geometric Goppa Codes  3.1  Definition and Properties  We will now present a simple construction of a class of codes whose minimum distances meet the Singleton bound. Consider Vk = {/ £ ¥ [x] : deg/ < k — 1}. This is a vector space of q  dimension k with basis {l  }.  k  1  Let P i , . . . ,P„ be distinct elements in ¥ and q  define the linear 'evaluation map' eWfc  :P ->F^:/^(/(P ),...,/(P )). fc  1  n  Definition 4 If k <n, the linear code Mk Q F£ is defined as Mk = Im(ev ). k  These codes are called rational geometric Goppa codes for reasons which will be given later. Note that since k < n it follows that for all / G Pfe, ev (f) = 0 if and only if / = 0. In other k  words evk is injective so that dim [Mk] = dim [Im (evk)] = dim [Vk] - k. Furthermore, the elements of Vk cannot have more than k-1 zeros in ¥ , (and we certainly can q  construct elements with exactly k-1 zeros), so that the minimum distance dk of M is given as k  d = n-(kk  1).  Therefore the minimum distance of Mk meets the Singleton bound and thus P^ is lower than fc  any other linear code of the same length and dimension. To see more specifically how these 11  Chapter 3. Rational Geometric Goppa Codes codes are implemented in practice we take as an example the rational geometric Goppa code over the  field  with maximum length n — q = 16 and dimension k — 12.  Let 3 be a primitive element of F 6. Then F 6 is a vector space over F generated by 1, 3, /3 , 2  X  X  2  and /3 . For calculations, it is useful to have a list of the vector representation of every element 3  in F i 6 corresponding to this basis. Using the minimal polynomial for 3 we can generate such a list. 0 =  (0,0,0,0), B  3  =  (0,0,0,1),  3  =  (0,1,1,1), 3  7  n  =  (1,1,0,1),  =  (0,0,1,1),  3°  =  (0,0,0,1), 3*  =  (1,0,0,1),  /3 =  (1,1,1,0), 3  3  =  (0,0,1,0),  3  -  (1,0,1,1),  3  =  (0,1,0,1), 3  13  = (0,1,1,0),  3  =  (0,1,0,0), /3  -  (1,1,1,1), 3  =  (1,0,1,0), 3  U  = (1,1,0,0).  1  2  5  6  8  9  W  12  The generators of M12 as a linear subspace of F}g are simply the images of the generators of V12 under evk- Therefore At 12 is generated by the vectors  ix = (1,1,1,1,1,1,1, i, 1,1,1, i, 1,1,1,1), 6 = (o, 1,..., p ), u  •& = ((0) ,(l) ,...,(/3 ) ), 2  2  14  2  6 2 = ((0) ,(l) ,(/3) ,...,(/3 ) ), 11  11  11  14  11  where of course the powers of 3 can be reduced modulo 15. The number of messages that this code is capable of sending is equal to 16 . Therefore in 12  practice we would represent the uncoded raw data as a 12-vector over F i 6 , say  ( 0 1 , 0 2 , . . . , 012).  When we were ready to transmit this raw data we would then "encode" it by calculating 12  c = Yl &o  1=1  It is during this calculation that we would utilize the list above and represent every vector entry as a linear combination of 1, 0, 3 , and /3 alone. 2  3  Finally, during transmittion there is of course a certain probability that a message will accumulate errors via some sort of noise in the communication channel. To evaluate the usefulness of this code we will compare this probability P M  12  with the probability that an incorrect message  would be received if no code were used. 12  Chapter 3. Rational Geometric Goppa Codes  Assume that the probability of signal error is p=.001. If we did not use any code, we would simply transmit the original 12-tuple representing our raw data. In this case the probability that our transmittion is received without error is (1—p) . Therefore the probability of incorrect 12  transmittion of our message is i NoCode 5  = l-(l-p)  1 2  = 0.0119.  When using the code Mu, our message will be received and any errors corrected as long as the number of errors is less than or equal to ^zl .= 2 ^ = 2. Let X denote the random variable associated to the number of signal errors in our transmittion. Then X has a binomial probability distribution with mean p = 16p and standard deviation a = -y/l6p(l — p). Correspondingly we have that P  M l 2  = P(X > 2) = P(X - p > 2 - p) = P(|X - p\ > 2 -  p),  where the last equality holds since X — p has probability zero of taking on any values less than —p  and —(2 — p) = —(2 — 16p) < —p.  Therefore Chebyshev's inequality tells us that P  M l 2  ) *)  = P ( | X - p\ >  < 77T\2 < ° -  V  a  0 0 4 L  )  Therefore we have decreased our chances of incorrect message reception by at least one order of magnitude while our information rate is still at a large value of y|. The main disadvantage of rational geometric Goppa codes is that the length n, and therefore the dimension k, is bounded above by the number of elements, q, in the finitefieldthat you're working with. This can be problematic in practice. Shannon's theorem tells us that to achieve the small values of Pc that we want, we may need to use codes of large length. Therefore if we need to use a specific finite field, we may be stuck with a large value of Pc- In the extreme case, suppose that for our purposes we are required to use the field F . The most 2  meaningful rational geometric Goppa code you can construct in this case will have parameters (n,k,d)  = (2,1,2). But for a given code with minimum distance d, we only have decoding 13  Chapter 3. Rational Geometric Goppa Codes  methods for incoming vectors whose distance from our code is strictly less than f. Since this code has minimum distance 1, only the codewords themselves can be "decoded". In other words this code is useless. It should be noted that despite this disadvantage, rational geometric Goppa codes are widely regarded as some of the best codes in coding theory. In addition to their simplicity, we will see in Chapter 5 that they can be decoded quickly and without difficulty. It is for this reason that in the case were longer codes are needed, we are motivated to generalize the definition of these codes to allow for better codes rather than discarding them and starting anew. This generalization, which we carry out in the next chapter, will give us the full class of geometric Goppa codes which preserve many of the positive aspects of rational geometric Goppa codes but allow for codes of arbitrarily large length over a given finite field.  14  Chapter 4 Geometric Goppa Codes  4.1  Preliminaries  In this chapter we will assume familiarity with the behavior of divisors and linear systems on non-singular projective algebraic curves. Although a few definitions will be given, many terms will be used without definition, for which the reader is referred to [4]. For rational geometric Goppa codes the restriction on the length of the code comes about from a limitation on the number of elements in F to use for evaluation. For the general geometric q  Goppa codes this problem is simply solved. Instead of evaluating polynomials on the elements of F , we generalize to the evaluation of rational functions on a selection of F -rational points q  q  of a non-singular projective curve C over F . In this way, all that is needed to produce longer q  codes is tofinda curve with more F -rational points, a process for which there are no theoretical q  limitations. Of course there is the problem of which rational functions to use. If P i , . . . , P are the evaluation n  points on C, we will need to insure that none of the rational functions that we use have any poles at any of the Pj. To do this, we select an F -rational divisor G on C with the property q  that supp G fl {Pi} = 0 for alH = 1,... , n. We then simply use the elements from £(G) for the domain of our evaluation map where £(G):={/€F  C  : / ^ 0, (/) >-G}  U {0}  and (/) denotes the principal divisor associated to the element / of the functionfieldFc associated to C. In this way, any poles that our functions may have are contained in the 15  Chapter 4.  Geometric Goppa Codes  support of G, which by assumption misses all of the Pi. Finally, note that the class of codes resulting from the construction describing above would indeed be a generalization of the class of rational geometric Goppa codes. As the name suggests, all rational geometric Goppa codes can be constructed in this way by choosing C as the rational curve P and using the F -rational divisor G equal to A; — 1 times the point at infinity. 1  g  4.2  Definition and Parameter Bounds  The definition of a geometric Goppa code, motivated by our discussions thus far, is given as follows. Let D = Pi + . . . + P„ be a divisor on C where P i , . . . , P„ are the evaluation points mentioned above. If G is a divisor on C such that supp G fl supp D = 0, define the linear map ev , : £ ( G ) ^ F ^ : / G  D  ^(/(Pi),....,/(P )). n  We have the following definition. D e f i n i t i o n 5 The geometric Goppa code associated to the divisors D and G, Cc{D, G), is  given as  C (D, G) := lm{ev ). C  GtD  These codes werefirstintroduced, (in a different form), by V.D. Goppa in 1981 [9].  1  We can easily express the parameters for C/;(D, G) in terms of D and G. The dimension, k, will be equal to the dimension of the vector space ^r^evc D)' ^ r  owever  > c e kei(eva,D) — £(G — D ) , sm  we have that k = dim£(G) - dim£(G - D ) . As discussed in Chapter 2, the minimum distance for Cc(D, G), d, is equal to the minimum weight over all of it's codewords. Therefore we obtain  d = n - max {/ : dim (£(G -  - . . . - P )) > 0} , i;  Note that in earlier work [8], V.D. Goppa introduced a different class of codes which are usually referred to as classical Goppa codes.  16  Chapter 4. Geometric Goppa Codes  and since for any divisor H, if degH < 0 then £(H) = {0}, it follows that d > n -  deg(G).  For the remainder of this paper, we will assume that G is chosen so that deg G < n. In this case deg(G — D) < 0 and again this implies that C(G — D) = {0}. Using this, and the Riemann-Roch theorem, we obtain the final pair of bounds k >  deg G + 1 — g , and d>n  —  deg G.  Putting these together, it follows that d > n — k + 1 — g. Therefore d is less than g + 1 away from the Singleton bound n — k + 1.  4.3  Code Performance  Shannon's theorem tells us that codes with arbitrarily small values of Pc exist if we are willing to consider codes with arbitrarily large lengths. As we discussed in Chapter 1, such codes would be useful provided that they have additional structure which allows them to be decoded quickly. Geometric Goppa codes are indeed rich in structure. The geometric objects with which they are constructed are proving to be useful in the construction of quick and effective decoding algorithms. Much progress has been realized in this area, and it looks as though decoding algorithms on par with the most efficient of today will be found for these new class of codes. As a result of the hopeful nature of the decoding problem, if sequences of geometric Goppa codes can be found whose Pc values converge to zero, these codes may be of great use to us. Shortly after the introduction of geometric Goppa codes, it was found that not only could sequences of geometric Goppa codes be found whose Pc values tended to zero, but that for some values of q, these sequences had Pc values which tended to zero faster than any other known code. In this section we briefly describe the processes involved in the discovery of these code sequences. In order to construct long geometric Goppa codes, we will need to use curves C with a large number of rational points. On the other hand to minimize Pc for a given length, we need to maximize the minimum distance d. Therefore the bound d>n — k + 1—g tells us that for a given length we would like to choose the curve with as small a genus as possible. Thus if we wish to find a sequence of geometric Goppa codes whose Pc values rapidly converge to zero, 17  Chapter 4. Geometric Goppa Codes  we will need to balance these needs for a large number of rational points and a small genus. In 1983 Drinfeld and Vladut [10] succeeded in determining a bound on the relative size of n with respect to g that is attainable in the limit of large values of g. They found that if N(g) denotes the maximum number of rational points that can exists on a curve of genus g over ¥  q  then limsup^^- < yfq-l. g-Kx>  g  Therefore we know that the the lowest genus we can achieve in the limit of large n would be realized in sequences of curves whose values of ^^Jl! converge to this limit. In 1982 Tsfasman, Vladut, and Zink [6] used modular curves to construct a sequence of curves converging to the Drinfeld-Vladut bound for the case where q is a square. For q > 49 they showed that the codes arising from these curves have Pc values which converge to zero quicker than any previously known code. Their constructions however were not simple and explicit enough to be used for the construction of actual codes. Finally, in 1995 Garcia and Stichtenoth [1] were able to construct, (simply and more explicitly), a sequence of curves converging to the Drinfeld-Vladut bound. Their construction was again done for the case where q was a square only. Although they did not construct any codes from these curves, it looks hopeful that such constructions will follow. It is important to note that although it is taking time to construct explicit codes demonstrating the fact that geometric Goppa codes can most rapidly approach small values of Pc for large n, there are many geometric Goppa codes that have been explicitly constructed that posses parameter values on par with the best codes of this day. We still haven't addressed the question of whether or not enough structure exists in these codes to allowfordecoding algorithms which are as efficient as decoding algorithms known for other codes. Recent advances in the search for such algorithms suggests that they will befound.A survey of these advances can be found in [5]. In the next chapter, we will present one of the landmark achievements in this effort due to A.N. Skorobogatov and S.G. Vladut. 18  Chapter 4. Geometric Goppa Codes  Note that when working with geometric Goppa codes, it will be useful to relax the notation for the bilinear pairing <, > on F£.  Definition 6 Suppose f is a function whose poles miss the support of D. i / x € F£, we then define (/,x> := (y,x) , where y = ( / ( P i ) , . . .  19  ,/(P„)).  Chapter 5 Decoding Algorithms for Geometric Goppa Codes  5.1  Basic Algorithm  Let C be some geometric Goppa code defined on a curve C C P , and having parameter values 2  n, k and d. Our goal in this section is to outline an algorithm for decoding any vector a whose distance from C is less than or equal to t, where t is an integer with t < | . As discussed in the first chapter, the objective in decoding a is to find a unique codeword, c, whose entries deviate from a's in the least number of positions. We shall call such a c the codeword associated to a. Equivalently we could search for a unique n-tuple e, having minimal weight, for which a — e is a codeword. Such an e shall be called the error vector associated to a. Let m\,... , m* _ be a basis for the dual code C*. Suppose a vector x' has the property that n  k  a —x' = c G M. Then for all? = 1,... ,n — k, we have < a, m* >—< c + x', m* >=< x', m* >.  Definition 7 The syndrome of a is given as a (a) := (< a, m\ >,... , < a, m* _ >). n  k  Then x' satisfies the system of equations: < x, m* >= s(a)j Vz = 1,... ,n — k. Conversely, if x' is a solution to 5.1, then < a — x', m* >= 0 for all i, so that a — x' is an element of (C*)* = C. In other words, c = a — x' is a codeword. Therefore a — x' € C if and 20  Chapter 5. Decoding Algorithms for Geometric Goppa Codes only if x' is a solution to 5.1. Thus finding a unique minimal weight solution to 5.1 is our goal in decoding a. The unique minimal weight solution to 5.1 could certainly be found by searching the finite number of solution vectors x for the one with minimal weight. This is as time consuming, however, as searching all of the codewords in C for the one closest to a, which is exactly the task we are trying to quicken. There are more timely methods forfindingthe minimal weight solution to 5.1, which involve predetermining a number of zero entries for x. The goal is to find enough zero entries in x so that since it further solves 5.1, it must be unique and of minimal weight. For the cases discussed in this paper, the predetermination of zero entries in x will take the amount of time needed to solve another system of linear equations such as 5.1. The idea is to find what is called an 'error locator function' for a. Let I•= {Pjj,... ,Pi } be the points on C corresponding to the set of error locations for a. In s  other words, ej ^ 0 if and only if j € {n,... ,i }, (note that \I\ < t < |). s  Definition 8 Let f be a function that is defined and not identically zero on the evaluation points P i , . . . , P . If J = {Pi : f(Pi) — 0} then f is an error locator function if I C J and n  \J\ < d. If such a function is found, we will know that the vector solution to 5.1 is zero in all of the entries i for which f{Pi) is not zero. We will therefore preset Xi = 0 for all Pj not in J. It is important to note that although I C J, in general I / J. Therefore / will not tell us every zero of e. However, since \ J\ < d, we will have a sufficient number of predetermined zeros. To see this, suppose that ei and e are two solutions of 5.1 with (ei)j = (e2)i = 0 for all i such 2  that Pi is not in J. Let ci = a — ei and c = a — e2 be the corresponding codewords. Then 2  w(c\ — C 2 ) = w(e\ — e ) < d so from the definition of minimum distance, it follows that ci = C 2 . 2  Thus ei = e is a unique solution and is subsequently of minimal weight. 2  21  Chapter 5. Decoding Algorithms for Geometric Goppa Codes  Therefore, our outline for decoding a vector a whose distance from C is less than or equal to t is as follows.  Basic Algorithm for decoding up to t < \ errors for geometric Goppa codes (i) (ii)  Obtain an error locator function, / , of a. Solve system 5.1 with the extra conditions: Xi — 0 for all Pi not in J.  (iii) The solution, e, in (ii) will be a unique minimal weight solution as we saw above. Set c = a — e, then c is the codeword associated to a. The specific means by which we will find the error locator function will be discussed in the following sections.  5.2 5.2.1  Decoding Rational Geometric Goppa Codes Algorithm  We will now see that the decoding problem for rational geometric Goppa codes is easily solved. Not only are the algorithms easily understood, but they will effectively decode a large number of errors. In particular, the algorithm constructed in this section will decoding any n-tuple, a, whose distance from the code is strictly less than 5, where d is the minimum distance for the code. In other words, in the notation of Section 5.1, we shall set t =  [l^yH]-  Let C = Mk be a rational geometric Goppa code over ¥ , as defined in Chapter 3. Let the q  length, n, be maximal so that {Pi,... , P } = ¥ . Thus C = Mk has parameter values n — q, q  k,  q  and d = q + 1 — k.  It will be useful to view C as the dual of another rational geometric Goppa code. As with any linear code, we have that [C*]* = C. Therefore, it would suffice to express C* as a rational code. Indeed it can be shown, (see Chapter II of [4]), that C* is expressible as another rational geometric Goppa code, Mk , with parameter values n' — q, k' — q — k, and d' = k + 1. 1  22  Chapter 5. Decoding Algorithms for Geometric Goppa Codes  Let a be an n-tuple whose distance from C is less than or equal to t, were t is given above. Following Section 5.1, we need to find an error locator function for a. Let e be the error vector associated to a. Since the number of non-zero elements in e does not exceed t, there will exist polynomials in Vt+i whose zeros contain the set of error locations, I. Since the number of zeros for any polynomial in Vt+i cannot exceed t, and t < d, it follows that any one of these polynomials will be an error locator function for a. In fact, these error locator functions can be found by solving a system of linear equations as follows.  Claim 1 A polynomial f = 2~^=\ n ~ £ Pt+i i a  if (xi,...  z i l  l  s  error locator function for  n  a if and only  ,xt+i) = (OJI, . . . , ett+i) satisfies the linear system  t+i ^(</-V,a>^)=0  Proof.  a  Suppose that /  = X^=\ ct^z^  1  Vi/ = 0 , . . . , f c ' - f - l .  (5.1)  is an error locator polynomial. Then for all  € Vt+i  v = 0,... , k' — t — 1 we have  ES=\ (<  ^ " V ,  a>  Q ) =< (£1=0 V - ) 1  z\  M  where the c term disappears since fz  v  a >= (fz», a) = (fz", e + c)  € Vk' is one of the defining functions for C*, and  the last equation holds from the definition of error locator functions. Therefore we have that {x\,... , xt+i) =  (OJI, . . . ,  cxt+i)  is a solution to System 5.2.  Conversely, suppose System 5.2 holds for (x\,... , £t+i) Furthermore, suppose there were a  =  ( i> • • • > t+i) a  a  a n  d / = Yf/^i  ^ M  2  ^  -  € I with f(Pi') ^ 0. Let g — X^=To* A" " ^ ^fc'-t _1  2  be such that g is zero on all of I except Py, (certainly such a g exists since its required zeros number | 7 | - l < t - l < d - t - 2 = fe'-t-l). Then from 5.2 we have k'-t-l  q  (0Af^,*)) = (f9,*) = (f9,e) =  0= i/=0  ^HPi)g(Pdei  =  f(PM  i=l  which is a contradiction since all of f(Pi'), g{Py), and e^ are non-zero. Thus / must be an error locator function which proves the claim. 23  1  -  Chapter 5. Decoding Algorithms for Geometric Goppa Codes  • Therefore, we have the following algorithm:  Decoding up to t <  errors for rational geometric Goppa codes  (i) Find a non-trivial solution, (cti,... locator function / = YA=\  ,at+\),  to the linear system 5.2, obtaining the error  i ~-  a  zl  l  (ii) Solve the linear system 5.1 for x, with the extra conditions: x\ = 0 for all i not in J , (where J is the zero set of / in ¥ ) . q  (iii) Set e = x, the decoded word is then c = a — e. 5.2.2  'C'-version of algorithm  As a demonstration of the results in Subsection 5.2.1, I have written a program implementation of the algorithm, written in C, for an arbitrary primefieldF . The program can be found on my p  web site at www.math.ubc.ca. It uses row reduction to solve the matrix equations associated to the linear systems 5.1 and 5.2. The program procedure is as follows: 1) Input an n-tuple a. 2) Find a non-trivial solution to the matrix equation: 7i -  ' 1 "  72  0  a  .1  Iq-k-t  where 71,... , j  q  -k-t  7i  . 1 .  are given by  a Pt  aiPt  l  1  1 A  P{  1 P2  P\  1 Pn  pt  q  24  Chapter 5. Decoding Algorithms for Geometric Goppa Codes  3) Set f(z) = YA=O i  a z%  a n  d determine J, (the zero set of / in F ). p  4) Find the unique solution, x, to the system of equations 1  ...  1  ... P  Pi  Q  pk Q  pk where x and b are given as  bj =  ^ ajP/ i=l  1  ,  and  Xj  ii j € J  0  otherwise  Xj = <  Finally, if either one of steps 2) or 4) cannot be performed, then the algorithm should terminate with the knowledge that a has more than t errors and therefore cannot be decoded.  5.2.3 Complexity As we have noted, the most basic decoding algorithm is performed by first computing the distances p(a., c) for all of the codewords c € C and subsequently decoding a as the codeword c that produces the smallest distance. To demonstrate the improved speed with which we can decode incoming vectors when using the algorithm presented in this section, we now compare the number of bit operations required in the algorithm of Subsection 5.2.1 with the number required in the basic decoding algorithm. Let Mk C Fq be a rational geometric Goppa code of length p over F for some prime p. We p  will assume that the information rate of Mk is greater than \ so that k > | . Let a € Fp be the vector that we wish to decode with d(a, C) <  where d is the minimum distance of Mk  so that indeed a can be decoded. For each of the decoding algorithms, we will estimate the number of additions-subtractions and multiplications-divisions that are required to decode a, (we will count reductions modulo p as one division). Assuming an average bit length of N = 5 log p for every number that is being 2  25  Chapter 5. Decoding Algorithms for Geometric Goppa Codes  operated on, we can then denote the number of bit operations required to perform one addition or subtraction as N. For simplicity we will assume that the slowest multiplication and division procedures are being used so that the number of bit operations for a multiplication or division will be i V . In this way, we will finally estimate the number of bit operations required in each 2  algorithm and compare. In the case of the basic decoding algorithm we need to calculate one distance for every codeword in Mk and subsequently compare that distance to the smallest distance that we had computed up to that point. Each distance will involve p subtractions and p additions and the comparison will involve one subtraction. Therefore since this is done for all of the p codewords, we can k  estimate the total number of bit operations as p (2p + 1)N > ppl (2p + 1)N so that 2  Number of bit operations required in basic algorithm > O (j}og p){p ^~\j E  2  •  For the algorithm of this section, there are five main steps that require the bulk of the computing time. These are (i) The computations required to set up the matrix associated to the first system of linear equations. (ii) The gaussian elimination needed to find the solution to this first system. (iii) The calculations required to determine the zero set of the error locator function. (iv) The computations required to set up the matrix associated to the second system of linear equations. (v) The gaussian elimination needed to find the solution to this second system. Using the information in Subsection 5.2.2, and the fact that gaussian elimination on an m by n matrix would require 0(m n) multiplications and 0(mn) additions, we can estimate that 2  the order with respect to the variables p,fc, and t of addition-subtractions and multiplicationsdivisions are respectively:  26  Chapter 5. Decoding Algorithms for Geometric Goppa Codes (i) : 0(p t - pkt - pt ) and 0(pH - p kt + p t 2  1  (ii) : 0(pt -kt-  2  2  - pk t - pkt - pt ),  2  2  t ) and 0(p t - pkt - pt + kt 2  2  2  2  2  3  +t ), 3  (iii) : 0(pt) and 0{t ), 2  (iv) : 0(p ) and 2  0{pk +p ), 2  3  (v) : 0(pk) and 0(pk ). 2  However, since § < k < q and 0 < t <  it follows that k — 0(q) and t < 0(q). Therefore  we can obtain upper bounds on the order of the expressions above. We then have: (i) : 0(p ) and 0(p ), 3  4  (ii) : 0{p ) and 0(p ), 2  3  (iii) : 0(p ) and 0{p ), 2  2  (iv) : 0(p ) and 0(p ), 2  3  (v) : 0{p ) and 0{p ). 2  3  Adding these together we see that in the decoding algorithm of this section, we require at most 0(p ) additions-subtractions and 0(p ) multiplications-divisions. From this we conclude: 3  4  Number of bit operations required for the algorithm in this section < O ((log p) p ) • 2  4  2  We see therefore that the algorithm in this section is indeed an improvement on the basic decoding algorithm, as it competes in polynomial time. Although for small values of p, this improvement we not be seen, the increased speed for large values of p is tremendous. We are particularly concerned with improved speed for large values of p since one of our main concerns is to endow the longer codes of Shannon's theorem with quick decoders and for rational geometric Goppa codes p is large if we are considering long codes.  27  Chapter 5. Decoding Algorithms for Geometric Goppa Codes  5.3 Decoding Geometric Goppa Codes Let C = C,c(D,G) be a geometric Goppa code defined for the rational divisors D and G on a non-singular projective curve C over ¥ . In this section, we will derive a decoding algorithm q  for C due to A.N. Skorobogatov and S.G. Vladut [2], following an idea of J. Justesen et al. As in Section 5.2, we will rely heavily on the dual of C which is again an algebraic geometric code. In particular, C* = C,c(D,H), where H is another rational divisors on C with the property that degH = degD - degG + 2# - 2, (see Chapter II of [4]). Unlike the case for rational geometric Goppa codes, the algorithm in this section will not necessarily be able to decode all vectors whose distance from C is less than half the minimum distance. To date, the best decoding algorithms for geometric Goppa codes can only guarantee the decoding of less than or equal to  errors, where d* = n — deg G is the design distance  of C, (see [5]). The algorithm in this section will fall somewhat short of that mark, with a guaranteed correction of any error vector having weight less than or equal to  d  ~  1 - g 2  where g  is the genus of C. Therefore the algorithm in this section will decode the maximal possible errors,  in the case that C = P where g = 0. In fact, the algorithm in Section 5.2 is the 1  application of this section to C = P . 1  Let a be the vector that we wish to decode. As in Section 5.2, we would like tofinda function space within which the error locator function of a can be determined by solving a system of linear equations. Let t be an integer with 0 < t <  and assume that the distance from a  to C is less than or equal to t. The following theorem will give conditions under which we can find such an appropriate function space.  Theorem 2 If there exists a divisor G\ on C such that supp G\ n supp D = 0, < deg d < d* - t, and  (5.2)  dim£(Gi) > t,  then C(G\) contains an error locator function for a. In particular, f G C{G\) is an error 28  Chapter 5. Decoding Algorithms for Geometric Goppa Codes locator function if and only if f =  X^=i »£n a  w  M  )=0  n  e  r  = ("l,-- - ,cth) is a non-  e  trivial solution to the linear system h  £«^,a)x  w/iere  Vi/ = 1,... ,Z ,  (5.3)  2  and {n\,... ,%} are basis of the spaces £ ( G i ) and C(H— Gi) respectively.  {£1,... ,  Proof. Suppose that I = {P^,... , P } is the set of error locations on D, (note that s < t). We is  wouldfirstlike to show that there exists a non-zero function in £ ( G i ) whose zero set contains all of I. Since the supports of Gi and D are disjoint, such functions will exist if and only if the linear system £ ( G i —  — . . . — PjJ is non-trivial. But Gi - P^ - . . . — P; < G i , so that 3  C{G --p -...-P )CC(G ). 1  il  it  1  Therefore we have that dim£(Gi) - dim£(Gi - P^ - . . . - P*J < d e g d - deg(G! - P  ix  - . . . - P ) = s, if  and since dim£(Gi) > t + 1, it follows that dim£(Gi - P - ... - P ) > t - s + 1 > 1. h  it  Hence £ ( G i ) does indeed contain non-zero functions whose zero sets contain I. In fact, these functions are error locator functions. To see this, suppose / is such a function and J  =  {Pj ,... 1  ,Pj } r  is it's corresponding set of zeros on D.  It then follows that  £(Gi - Pj! - . . . - P j J # {0}. If it were the case that \ J\ = r > d*, then deg(G! - P - ... - P ) = d e g d - r < -t < 0 h  jr  which is a contradiction. Therefore \J\ < d* < d so that / is in fact an error locator function for a. Now suppose that / G £(Gj) is an error locator function. Since can find an  (a\,...  ,  QJ/J  is a basis for £(Gi), we  e l * such that / = 2~^J!=i n(n- Note in addition that fn € £(H) 1  a  v  29  Chapter 5. Decoding Algorithms for Geometric Goppa Codes  for all v, and is therefore an element of the generating class of functions for C*. Therefore for all v we have h  h  X  )  n  =X  a  ) = (fVv> c + e) = (/T/„, e) = X f( i)v{Pi)ei = 0, p  a  n=l  /z=l  i=l  since / is an error locator function, and thus system 5.4 holds for (#i,... ,2^) = (ai,... ,o^). Conversely suppose that / = X ^ i  g  =  £(Gi)forsome solution (ai,... , a^) to the system  5.4. Assume that there is a Pj» G I with f(Pi') 7^ 0. As in Section 5.2, we will obtain a contradiction through the use of a function h G £ ( H — Gi) that is zero on all of I except Pj*. To show that such an h exists, we calculate - . . . - P<J = deg(D) - deg(G) + 2g - 2 - deg(Gi) - s  deg(H - G i -  > d* + 2g -  2 -  {d* - t) - t = 2g - 2.  Therefore, using the Riemann-Roch theorem to calculate the dimensions of the respective vector spaces, we can then verify the proper inclusion V i := £ ( H - Gi - P  - ... - P^)  h  £ ( H - G i - Pij - . . . - P  c  i s  + P?) =: V . 2  Hence, there exists a non-zero h G V 2 — V i C £ ( H — Gi). This h has the desired properties. From 5.4 we then have n  0 = (A, a) = (fh,e)  =  Y,f(P )h(P )e = f•(P ,)h(P ,)e , i  i  i  i  i  i  i=l  which is a contradiction since all of f(Pi'), /i(Pj')i  a n  d  are non-zero. Therefore if J is the zero  set of / in {P . . . , P }, then I C J and since / G £(Gi) it follows that \J\ < deg{G ) < d* < d. u  n  x  Hence f is an error locator function for a.  • Thus if we have a divisor Gi satisfying 5.3, we can use it to decode n-tuples, a, whose distances from C is less than or equal to t. All that remains is to determine values of t for which such a divisor can be found. The following theorem does exactly this.  Theorem 3 I/O < t < *~^~ , there exists a divisor Gi on C satisfying 5.3. d  s  30  Chapter 5. Decoding Algorithms for Geometric Goppa Codes  Proof. See Chapter VII of [4].  • Once we obtain the G i proven to exist in Theorem 3, we have the following algorithm.  Decoding up to t < ~ d  1 - g 2  errors for a geometric Goppa code C,c(D,G)  (i) Find a non-trivial solution, (a\,... , a^), to the linear system 5.4, obtaining the error locator function / = Yl^=i <V^(ii) Solve the linear system 5.1 for x, with the extra conditions: X{ — 0 for all i not in J, (where J is the zero set of / in ¥ ) . q  (iii) Set e = x. The codeword associated to a is then c = a — e. As with the decoding algorithm in Section 5.2, the majority of the computation in this algorithm involvesfindingsolutions to two main systems of linear equations. The time required to decode a vector will therefore be polynomial in q. Hence as in Section 5.2, for large values of q the algorithm in this section will help us to decode vectors much quicker than by using the basic decoding algorithm.  31  Bibliography [1] Garcia A. and Stichtenoth H. A tower of artin-schreier extensions of function fields attaining the drinfeld-vladut bound. Invent. Math., 121:211-222, 1995. [2] Skorobogatov A.N. and Vladut S.G. On decoding albebraic-geometric codes. IEEE Trans. Inform. Th., 36:1461-1463, 1990. [3] Jr. Forney D. G. Concatenated Codes, volume 37 of Research Monographs. The MIT Press, 1966. [4] Stichtenoth H. Algebraic Function Fields and Codes. Universitext. Springer-Verlag, 1993. [5] Hoholdt T. and Pellikaan R. On the decoding of algebraic-geometric codes. IEEE Trans. Inform. Th., 41(6), November 1995. [6] Vladut S.G. Tsfasman M.A. and Zink T. On goppa codes which are better than the gilbert-varshamov bound. Math. Nachr., 109:21-28, 1982.  [7] van Lint J.H. Introduction to Coding Theory, volume 86 of Graduate Texts in Mathematics Springer-Verlag, 1982. [8] Goppa V.D. A new class of linear error-correcting codes. Problems of Info. Transmition, 6:207-212, 1970. [9] Goppa V.D. Codes on algebraic curves. Soviet Math. Dokl, 24(1):170-172, 1981. [10] Drinfeld V.G. and Vladut S.G. Number of points of an algebraic curve. Func. Anal., 17:53-54, 1983.  32  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0079766/manifest

Comment

Related Items