The two models described in this paper having as ingredients feedback resp. localized errors give possibilities for code constructions not available in the standard model of error correction and also for probabilistic channel models. For the feedback model we present here a coding scheme, which we call the rubber method, because it is based on erasing letters. It is the first scheme achieving the capacity curve for q ges 3. It could be discovered only in the g-ary case for q ges 3, because the letter zero is not used as an information symbol, but solely for error correction. However an extension of the method from using single zeros to blocks of zeros also gives Berlekamp's result - by a different scheme. In the model with feedback and localized errors the help of feedback is addressed. We give an optimal construction for one-error correcting codes with feedback and localized errors
The two models described in this paper having as ingredients feedback resp. localized errors give possibilities for code constructions not available in the standard model of error correction and also for probabilistic channel models. For the feedback model we present here a coding scheme, which we call the rubber method, because it is based on erasing letters. It is the first scheme achieving the capacity curve for q ges 3. It could be discovered only in the g-ary case for q ges 3, because the letter zero is not used as an information symbol, but solely for error correction. However an extension of the method from using single zeros to blocks of zeros also gives Berlekamp's result - by a different scheme. In the model with feedback and localized errors the help of feedback is addressed. We give an optimal construction for one-error correcting codes with feedback and localized errors
In this paper, the problem of correction of a single error in q-ary symmetric channel with noiseless feedback is considered. We propose an algorithm to construct codes with feedback inductively. For all prime power q we prove that two instances of feedback are sufficient to transmit over the q-ary symmetric channel the same number of messages as in the case of complete feedback. Our other contribution is the construction of codes with one-time feedback with the same parameters as Hamming codes for q that is not a prime power. We also construct single-error-correcting codes with one-time feedback of size qn−2for arbitrary q and n ≤ q + 1, which can be seen as an analog for Reed-Solomon codes.
The theory of zero-error communication is re-examined \nin the broader setting of using one classical channel to \nsimulate another exactly in the presence of various classes of nonsignalling correlations between sender and receiver i.e., shared randomness, shared entanglement and arbitrary nonsignalling correlations. When the channel being simulated is noiseless, this is zero-error coding assisted by correlations. When the resource channel is noiseless, it is the reverse problem of simulating a noisy channel exactly by a noiseless one, assisted by correlations. \nIn both cases, separations between the power of the different classes of assisting correlations are exhibited for finite block lengths. The most striking result here is that entanglement can assist in zero-error communication. In the large block length limit, shared randomness is shown to be just as powerful as arbitrary nonsignalling correlations for exact simulation, but not for asymptotic zero-error coding. For assistance by arbitrary nonsignalling correlations, linear programming formulas for the asymptotic capacity and simulation rates are derived, the former being equal (for channels with nonzero unassisted capacity) to the feedback-assisted zero-error capacity derived by Shannon. \nFinally, a kind of reversibility between nonsignalling-assisted zero-error capacity and exact simulation is observed, mirroring the usual reverse Shannon theorem.
The theory of zero-error communication is re-examined in the broader setting of using one classical channel to simulate another exactly in the presence of various classes of nonsignalling correlations between sender and receiver i.e., shared randomness, shared entanglement and arbitrary nonsignalling correlations. When the channel being simulated is noiseless, this is zero-error coding assisted by correlations. When the resource channel is noiseless, it is the reverse problem of simulating a noisy channel exactly by a noiseless one, assisted by correlations. In both cases, separations between the power of the different classes of assisting correlations are exhibited for finite block lengths. The most striking result here is that entanglement can assist in zero-error communication. In the large block length limit, shared randomness is shown to be just as powerful as arbitrary nonsignalling correlations for exact simulation, but not for asymptotic zero-error coding. For assistance by arbitrary nonsignalling correlations, linear programming formulas for the asymptotic capacity and simulation rates are derived, the former being equal (for channels with nonzero unassisted capacity) to the feedback-assisted zero-error capacity derived by Shannon. Finally, a kind of reversibility between nonsignalling-assisted zero-error capacity and exact simulation is observed, mirroring the usual reverse Shannon theorem.
In the q-ary online (causal) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1, . . . , xn) ∈ {0, 1, . . . , q - 1}nsymbol-by-symbol via a channel limited to at most p*n errors (symbol changes) and p*n erasures. The channel is "online" (i.e., "causal") in the sense that at the ith step of communication the channel decides whether to corrupt the ith symbol or not only based on its view of the symbols (x1,. . . , xi). This is in contrast to the classical adversarial channel in which the corruption is chosen with full knowledge of the sent codeword x. In this work we extend the results obtained in [1]-[4] (in which the capacities of binary online bit-flip-only channels, and separately binary online erasure-only channels were characterized). We here extend those prior results in two important ways. First, we obtain the capacity of q-ary online channels for general q (rather than just q = 2). Second, we analyze combined error-erasure corruption models (rather than studying them separately). Characterization of this much broader class of symmetric online channels gives a fuller understanding of the effects of causality on jamming adversaries. The extensions in this paper require novel approaches for both optimal code designs, and matching information-theoretic converse arguments.
The binary case was studied in [1], but the method used there doesn't give the tight answer for nonbinary cases and we presented in [2] another method for the corresponding result.Here we formulate the main theorem and prove the auxiliary statements used in [2].During the transmission of q-ary words of length n over the channel at most t errors occur, and the encoder knows the set E of t positions, where these errors are possible.The decoder doesn't know anything about these positions.Let E t = E | E ⊆ {1, 2, . . ., n}, |E| = t be the set of all subsets from {1, 2, . . ., n} of size t and let M be a set of messages (|M| = M ) .A code word x(m, E) depends not only on the message m ∈ M but also on the configuration of possible errors E .So there exists the natural correspondence between the message m ∈ M and the list of code words E∈E t x(m, E) , which we use for the transmission of this message.Thus the code X for the set of messages M represents a collection of M lists E∈E t {x(m, E)}, m ∈ M .Sinde we can use the same word for different configurations, the size of a list can be essentially smaller than the size of the setLet us define the cylinder C(a, A) with the base a = (a, . . ., a n ) and the support A A ⊆ {1, 2, . . ., n} as the set of words (y 1 , . . ., y n ) with y i = a i , if i / ∈ A .It is clear that the size of the cylinder C(a, A) is equal to q |A| and the number of different cylinders with the same support A is equal to q n-|A| .As a result of the transmission of the codeword x(m, E) every word of C x(m, E), E can appear as output of the channel.The code X corrects t localized errors, if the decoder can correctly recover every message m ∈ M .The following condition is necessary and sufficient for it: