A Simple Converse of Burnashev's Reliability Function
In a remarkable paper published in 1976, Burnashev determined the reliability function of variable-length block codes over discrete memoryless channels (DMCs) with feedback. Subsequently, an alternative achievability proof was obtained by Yamamoto and Itoh via a particularly simple and instructive s...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/52368 |
| _version_ | 1826196838798065664 |
|---|---|
| author | Berlin, Peter Nakiboglu, Baris Rimoldi, Bixio Telatar, Emre |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Berlin, Peter Nakiboglu, Baris Rimoldi, Bixio Telatar, Emre |
| author_sort | Berlin, Peter |
| collection | MIT |
| description | In a remarkable paper published in 1976, Burnashev determined the reliability function of variable-length block codes over discrete memoryless channels (DMCs) with feedback. Subsequently, an alternative achievability proof was obtained by Yamamoto and Itoh via a particularly simple and instructive scheme. Their idea is to alternate between a communication and a confirmation phase until the receiver detects the codeword used by the sender to acknowledge that the message is correct. We provide a converse that parallels the Yamamoto-Itoh achievability construction. Besides being simpler than the original, the proposed converse suggests that a communication and a confirmation phase are implicit in any scheme for which the probability of error decreases with the largest possible exponent. The proposed converse also makes it intuitively clear why the terms that appear in Burnashev's exponent are necessary. |
| first_indexed | 2024-09-23T10:38:45Z |
| format | Article |
| id | mit-1721.1/52368 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:38:45Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/523682022-09-30T21:59:17Z A Simple Converse of Burnashev's Reliability Function Berlin, Peter Nakiboglu, Baris Rimoldi, Bixio Telatar, Emre Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Nakiboglu, Baris Nakiboglu, Baris variable-length communication reliability function feedback discrete memoryless channels (DMCs) Burnashev's error exponent In a remarkable paper published in 1976, Burnashev determined the reliability function of variable-length block codes over discrete memoryless channels (DMCs) with feedback. Subsequently, an alternative achievability proof was obtained by Yamamoto and Itoh via a particularly simple and instructive scheme. Their idea is to alternate between a communication and a confirmation phase until the receiver detects the codeword used by the sender to acknowledge that the message is correct. We provide a converse that parallels the Yamamoto-Itoh achievability construction. Besides being simpler than the original, the proposed converse suggests that a communication and a confirmation phase are implicit in any scheme for which the probability of error decreases with the largest possible exponent. The proposed converse also makes it intuitively clear why the terms that appear in Burnashev's exponent are necessary. 2010-03-08T15:50:50Z 2010-03-08T15:50:50Z 2009-06 2007-12 Article http://purl.org/eprint/type/JournalArticle 0018-9448 INSPEC Accession Number: 10705686 http://hdl.handle.net/1721.1/52368 Berlin, P. et al. “A Simple Converse of Burnashev's Reliability Function.” Information Theory, IEEE Transactions on 55.7 (2009): 3074-3080. © 2009 Institute of Electrical and Electronics Engineers en_US http://dx.doi.org/10.1109/TIT.2009.2021322 IEEE Transactions on Information Theory Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | variable-length communication reliability function feedback discrete memoryless channels (DMCs) Burnashev's error exponent Berlin, Peter Nakiboglu, Baris Rimoldi, Bixio Telatar, Emre A Simple Converse of Burnashev's Reliability Function |
| title | A Simple Converse of Burnashev's Reliability Function |
| title_full | A Simple Converse of Burnashev's Reliability Function |
| title_fullStr | A Simple Converse of Burnashev's Reliability Function |
| title_full_unstemmed | A Simple Converse of Burnashev's Reliability Function |
| title_short | A Simple Converse of Burnashev's Reliability Function |
| title_sort | simple converse of burnashev s reliability function |
| topic | variable-length communication reliability function feedback discrete memoryless channels (DMCs) Burnashev's error exponent |
| url | http://hdl.handle.net/1721.1/52368 |
| work_keys_str_mv | AT berlinpeter asimpleconverseofburnashevsreliabilityfunction AT nakiboglubaris asimpleconverseofburnashevsreliabilityfunction AT rimoldibixio asimpleconverseofburnashevsreliabilityfunction AT telataremre asimpleconverseofburnashevsreliabilityfunction AT berlinpeter simpleconverseofburnashevsreliabilityfunction AT nakiboglubaris simpleconverseofburnashevsreliabilityfunction AT rimoldibixio simpleconverseofburnashevsreliabilityfunction AT telataremre simpleconverseofburnashevsreliabilityfunction |