Biblio

This paper introduces the notion of one-way communication schemes with partial noisy feedback. To support this communication, the schemes suppose that Alice and Bob wish to communicate: Alice sends a sequence of alphabets over a channel to Bob, while Alice receives feedback bits from Bob for δ fraction of the transmissions. An adversary is allowed to tamper up to a constant fraction of these transmissions for both forward rounds and feedback rounds separately. This paper intends to determine the Maximum Error Rate (MER), as a function of δ (0 ≤ δ ≤ 1), under the MER rate, so that Alice can successfully communicate the messages to Bob via some protocols with δ fraction of noisy feedback. To provide a reasonable solution for the above problem, we need to explore a new kind of coding scheme for the interactive communication. In this paper, we use the notion of “non-malleable codes” (NMC) which relaxes the notions of error-correction and error-detection to some extent in communication. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message or a completely unrelated value. This property largely enforces the way to detect the transmission errors. Based on the above knowledge, we provide an alphabet-based encoding scheme, including a pair of (Enc, Dec). Suppose the message needing to be transmitted is m; if m is corrupted unintentionally, then the encoding scheme Dec(Enc(m)) outputs a symbol `⊥' to denote that some potential corruptions happened during transmission. In this work, based on the previous results, we show that for any δ ∈ (0; 1), there exists a deterministic communication scheme with noiseless full feedback(δ = 1), such that the maximal tolerable error fraction γ (on Alice's transmissions) can be up to 1/2, theoretically. Moreover, we show that for any δ ∈ (0; 1), there exists a communication scheme with noisy feedback, denoting the forward and backward rounds noised with error fractions of γ0and γ1respectively, such that the maximal tolerable error fraction γ0(on forward rounds) can be up to 1/2, as well as the γ1(on feedback rounds) up to 1.