For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On Hash Functions and List Decoding with Side Information
M. Prem Laxman DAS
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2007/06/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Coding Theory
list decoding, side information, function fields, algebraic geometric codes, hash families,
Full Text: PDF(134.8KB)>>
List decoding is a process by which a list of decoded words is output instead of one. This works for a larger noise threshold than the traditional algorithms. Under some circumstances it becomes useful to be able to find out the actual message from the list. List decoding is assumed to be successful, meaning, the sent message features in the decoded list. This problem has been considered by Guruswami. In Guruswami's work, this disambiguation is done by sending supplementary information through a costly, error-free channel. The model is meaningful only if the number of bits of side information required is much less than the message size. But using deterministic schemes one has to essentially send the entire message through the error free channel. Randomized strategies for both sender and receiver reduces the required number of bits of side information drastically. In Guruswami's work, a Reed-Solomon code based hash family is used to construct such randomized schemes. The scheme with probability utmost ε reports failure and returns the whole list. The scheme doesn't output a wrong message. Also, in Guruswami's work some theoretical bounds have been proved which lower bound the bits of side information required. Here we examine whether the gap between the theoretical bounds and existing schemes may be narrowed. Particularly, we use the same scheme as in Guruswami's work, but use hash families based on Hermitian curve and function fields of Garcia-Stichtenoth tower and analyze the number of bits of side information required for the scheme.