2019/08/20 by Assaf Ben-Yishai, Ben-Yishai, Assaf, Young-Han Kim +5
Computer Science · Engineering · #Cellular Automata and Applications #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.1908.07367
openalex publication_date 2019/08/20 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
The essential interactive capacity of a discrete memoryless channel is\ndefined in this paper as the maximal rate at which the transcript of any\ninteractive protocol can be reliably simulated over the channel, using a\ndeterministic coding scheme. In contrast to other interactive capacity\ndefinitions in the literature, this definition makes no assumptions on the\norder of speakers (which can be adaptive) and does not allow any use of private\n/ public randomness; hence, the essential interactive capacity is a function of\nthe channel model only. It is shown that the essential interactive capacity of\nany binary memoryless symmetric (BMS) channel is at least 0.0302 its Shannon\ncapacity. To that end, we present a simple coding scheme, based on\nextended-Hamming codes combined with error detection, that achieves the lower\nbound in the special case of the binary symmetric channel (BSC). We then adapt\nthe scheme to the entire family of BMS channels, and show that it achieves the\nsame lower bound using extremes of the Bhattacharyya parameter.\n