LINEAR BOUND ON LINEAR SOURCE CODING.

Abstract

Summary form only given, as follows. Let the sequences from a binary memoryless source be compressed by a linear encoder using a compression rate of R output digitals per source letter. The minimum average error per digit in recovering the source sequence is shown to be at least p(1-R/h) where p less than equivalent to 1/2 is the probability that the source emits the nonzero digit and h is its entropy. Moreover, the quantity p(1-R/h) is also the lower bound on the minimum per digit error in reconstructing the sequences of a linear code when the codewords carry (1-R) user digits per channel digit and are transmitted through a binary symmetric channel of crossover probability p. In both systems, equality is achieved with the given bound if and only if (1-R/h) of the digits are reproduced with an average distortion of p and the rest of the digits are reconstructed with zero distortion.