loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Data Compression Conference (DCC '95)
Snowbird, Utah
March 28-March 30
ISBN: 0-8186-7012-6
Summary form only given. The existence of a noiseless, delayless feedback channel permits the transmitter to detect transmission errors at the time they occur. Such a feedback channel does not increase channel capacity, but it does permit the use of adaptive codes with significantly enhanced error correction capabilities. It is well known that codes of this type can be based on cooperative play of the game of "twenty questions with a liar". However, it is perhaps not so well appreciated that it is practicable to implement codes of this type on general purpose computers. We describe a simple and fast implementation in which the transmitter makes reference to a fully worked out game tree. In the worst case, storage requirements grow exponentially with block length. For many cases of interest, storage requirements are not excessive. For example, a 4-error correcting code with 8 information bits and 13 check bits requires only 103.2 kilobytes of storage. By contrast, an 8-error correcting code with 6 information bits and 25 check bits requires 21.2 megabytes of storage. However, no nonadaptive code is capable of correcting as many as 8 errors when 6 information bits are encoded in a block of length 31.
Index Terms:
adaptive codes; error correction codes; telecommunication channels; feedback; games of skill; game theory; adaptive error correcting codes; cooperative play; game; twenty questions with a liar; noiseless delayless feedback channel; transmission error detection; general purpose computers; game tree; storage requirements; block length; check bits; information bits
Citation:
E.L. Lawler, S. Sarkissian, "Adaptive error correcting codes based on cooperative play of the game of "twenty questions with a liar"," dcc, pp.464, Data Compression Conference (DCC '95), 1995
Usage of this product signifies your acceptance of the Terms of Use.