Localized random and arbitrary errors in the light of AV channel theory

A central problem in coding theory consists in finding bounds for the maximal size, say N(n,2t+1,q), of a t-error correcting code over a q-ary alphabet with blocklength n. This code concept is suited for communication over a q-ary channel with input and output alphabet X={0,1,...,q-1}, when a word of length n sent by the encoder is changed by the channel in at most t letters. Neither the encoder nor the decoder knows in advance where the errors, that is changes of letters, occur. Bassalygo, Gelfand, and Pinsker introduced the concept of localized errors. They assume that the encoder, who wants to encode message m, knows the t-element set E⊂[n]={1,2,...,n} of positions, in which errors may occur. The encoder can make the codeword, representing m, dependent on E∈ℰ_t, the family of t-elements subsets of [n]. The authors call them a priori error pattern. The set of associated (a posteriori) errors is V(E)={eⁿ=(e₁,...,e_n)∈Xⁿ :e_t=0 for t∉E}. They introduce probabilistic communication models with localized errors and determine the optimal rates of codes, if a priori error patterns or actual errors or both occur at random according to uniform distributions. There are strong connections to the theory of arbitrarily varying channels. The authors also have new coding technique for additive arbitrarily varying channels