
For FullText 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
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E90A
No.6
pp.11981203 Publication Date: 2007/06/01
Online ISSN: 17451337
DOI: 10.1093/ietfec/e90a.6.1198
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Coding Theory Keyword: list decoding, side information, function fields, algebraic geometric codes, hash families,
Full Text: PDF(134.8KB)>>
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, errorfree 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 ReedSolomon 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 GarciaStichtenoth tower and analyze the number of bits of side information required for the scheme.

