In this paper, we consider encoding strategies for the Z-channel with noiseless feedback. We analyze the asymptotic case where the maximal number of errors is proportional to the blocklength, which goes to infinity. W...
详细信息
ISBN:
(数字)9783030581503
ISBN:
(纸本)9783030581503;9783030581497
In this paper, we consider encoding strategies for the Z-channel with noiseless feedback. We analyze the asymptotic case where the maximal number of errors is proportional to the blocklength, which goes to infinity. Without feedback, the asymptotic rate of error-correcting codes for the error fraction tau >= 1/4 is known to be zero. It was also proved that using the feedback a non-zero asymptotic rate can be achieved for the error fraction tau < 1/2. In this paper, we give an encoding strategy that achieves the asymptotic rate (1+ tau)(1- h(T/ (1+ tau))), which is positive for all tau < 1. Additionally, we state an upper bound on the maximal asymptotic rate of error-correcting codes for the Z-channel.
We address the problem of correcting a single error in an arbitrary discrete memoryless channel with error-free instantaneous feedback. For the case of a one-time feedback, we propose a method for constructing optimal...
详细信息
We address the problem of correcting a single error in an arbitrary discrete memoryless channel with error-free instantaneous feedback. For the case of a one-time feedback, we propose a method for constructing optimal transmission strategies. The obtained result allows us to prove that for a binary channel, two feedbacks are sufficient to transmit the same number of messages as in the case of complete feedback. We also apply the developed techniques to a binary asymmetric channel to construct transmission strategies for small lengths.
A new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Assume that the encoder transmits n binary symbols one by one over a channel in which some symbols...
详细信息
A new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Assume that the encoder transmits n binary symbols one by one over a channel in which some symbols can be deleted and some additional symbols can be inserted. After each transmission, the encoder is notified about insertions or deletions that have occurred within the previous transmission, and the encoding strategy can be adapted accordingly. The goal is to design an encoder that is able to transmit error-free as much information as possible under the assumption that the total number of deletions and insertions is limited by tn, 0 < t < 1. We show how this problem can be reduced to the problem of transmitting messages over the substitution channel. Thereby, the maximal asymptotic rate of feedback insertion-deletion codes is completely established. The maximal asymptotic rate for the adversarial substitution channel has been partially determined by Berlekamp and later completed by Zigangirov. However, the analysis of the lower bound by Zigangirov is quite complicated. We revisit Zigangirov's result and present a more elaborate version of his proof.
The Wnyi-Berlekamp-Ulam game is a classical model for the problem of determining the minimum number of queries to find an unknown member in a finite set when up to a finite number of the answers may be erroneous. In t...
详细信息
The Wnyi-Berlekamp-Ulam game is a classical model for the problem of determining the minimum number of queries to find an unknown member in a finite set when up to a finite number of the answers may be erroneous. In the variant considered in this paper, questions with q many possible answers are allowed, further lies are constrained by a bipartite graph with edges weighted by 0, 1, 2.... (the "channel"). The channel Gamma is an arbitrary assignment stipulating the cost of the different possible lies, i.e., of each answer j not equal i when the correct answer is i by Gamma(i, j). It is also assumed that a maximum cost a (sum of the cost of all wrong answers) can be afforded by the responder during the whole game. We provide tight asymptotic bounds for the number of questions needed to solve this problem. The appropriate searching strategies are actually provided. We also show that adaptiveness can be dramatically reduced when the channel satisfies certain symmetry constraints. (C) 2007 Elsevier B.V. All rights reserved.
consider the problem of searching for an unknown number in the search space U = {0, ..., M -1}. q-ary questions can be asked and some of the answers may be wrong. An arbitrary integer weighted bipartite graph Gamma is...
详细信息
consider the problem of searching for an unknown number in the search space U = {0, ..., M -1}. q-ary questions can be asked and some of the answers may be wrong. An arbitrary integer weighted bipartite graph Gamma is given, stipulating the cost Gamma(i.j) of each answer j not equal i when the correct answer is i, i.e., the cost of a wrong answer. Correct answers are supposed to be cost-less. It is assumed that a maximum cost e for the sum of the cost of all wrong answers can be afforded by the responder during the whole search. We provide tight upper and lower bounds for the largest size M = M(q, e, Gamma, n) for which it is possible to find an unlinown number x* is an element of U with n q-ary questions and maximum lie cost e. Our results improve the bounds of Cicalese et al. (2004) and Ahlswede et al. (2008). The questions in our strategies can be asked in two batches of nonadaptive questions. Finally, we remark that our results can be further generalized to a wider class of error models including also unidirectional errors.
暂无评论