טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentTal Ido
SubjectList Decoding of Lee Metric Codes
DepartmentDepartment of Computer Science
Supervisor Professor Ronny Roth


Abstract

Let  be a finite field and let  be a subset of , termed a code. A codeword  is transmitted over a noisy channel and distorted by an error vector . We are given , which is the distorted word () and wish to find out what  was.


A list- decoder  of decoding radius  with respect to a given metric  is a generalization of classical decoding. Given a received word , the output of the list- decoder, , is a list of at most  codewords. This list is guaranteed to contain all codewords in the sphere of radius  centered at . Under the assumption that no more than  errors occurred in , we are assured that  is in , and this is regarded as a decoding success.


In this work, we concentrate on coding for the Lee metric, which appears in applications such as phase shift keying (PSK) modulation. A polynomial-time list decoder in this metric is presented and analyzed for alternant codes, which are subfield sub-codes of generalized Reed-Solomon codes (GRS). We show a formula for the decoding radius as a function of  and the parameters of the underlying GRS code.


We also show that unlike the Hamming metric counterpart, the decoding radius of our list decoder is generally strictly larger than what one gets from the Lee metric version of the Johnson bound.