Return to search

On communication with Perfect Feedback against Bit-flips and Erasures

<p dir="ltr">We study the communication model with perfect feedback considered by Berlekamp (PhD Thesis, 1964), in which Alice wishes to communicate a binary message to Bob through a noisy adversarial channel, and has the ability to receive feedback from Bob via an additional noiseless channel. Berlekamp showed that in this model one can tolerate 1/3 fraction of errors (a.k.a., bit-flips or substitutions) with non-vanishing communication rate, which strictly improves upon the 1/4 error rate that is tolerable in the classical one-way communication setting without feedback. In the case when the channel is corrupted by erasures, it is easy to show that a fraction of erasures tending to 1 can be tolerated in the noiseless feedback setting, which also beats the 1/2 fraction that is maximally correctable in the no-feedback setting. In this thesis, we consider a more general perfect feedback channel that may introduce both errors and erasures. We show the following results:</p><p dir="ltr">1. If α, β ∈ [0, 1) are such that 3α + β < 1, then there exists a code that achieves a positive communication rate tolerating α fraction of errors and β fraction of erasures. Furthermore, no code can achieve a positive-rate in this channel when 3α + β ≥ 1.</p><p dir="ltr">2. For the case when 3α + β < 1, we compute the maximal asymptotic communication rate achievable in this setting.</p>

  1. 10.25394/pgs.25678176.v1
Identiferoai:union.ndltd.org:purdue.edu/oai:figshare.com:article/25678176
Date29 April 2024
CreatorsShreya Nasa (18432009)
Source SetsPurdue University
Detected LanguageEnglish
TypeText, Thesis
RightsCC BY 4.0
Relationhttps://figshare.com/articles/thesis/On_communication_with_Perfect_Feedback_against_Bit-flips_and_Erasures/25678176

Page generated in 0.0019 seconds