M.Sc Student | Tal Ido |
---|---|

Subject | List Decoding of Lee Metric Codes |

Department | Department of Computer Science |

Supervisor | Professor Ronny Roth |

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.