On Hash Functions and List Decoding with Side Information

M. Prem Laxman DAS  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.6   pp.1198-1203
Publication Date: 2007/06/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.6.1198
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Coding Theory
Keyword: 
list decoding,  side information,  function fields,  algebraic geometric codes,  hash families,  

Full Text: PDF>>
Buy this Article




Summary: 
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.