Capabilities of Bounded Discrepancy Decoding
Aaron D. Wyner · Bell System Technical Journal · 1965
The following four channels are considered: (A) a class of discrete memoryless channels with q inputs and outputs, (B) the time-discrete, amplitude-continuous memoryless channel with additive Gaussian noise and amplitude constraint, (C) the same as channel B but with energy instead of amplitude constraint, (D) a class of time-discrete, amplitude-continuous memoryless channels with amplitude constraint and non-Gaussian noise. For each channel the theoretical capabilities of “bounded discrepancy decoding” are studied. The “discrepancy” between two vectors is a distance or distance-like quantity defined such that the optimal decoder is a “minimum discrepancy decoder.” For example, for channel A the discrepancy is the Hamming distance, and for channel B the discrepancy is the Euclidean distance. Bounded discrepancy decoding is a nonoptimal decoding scheme in which disjoint regions in the space of possible received vectors are constructed about each code word, each region consisting of those vectors within a fixed discrepancy of that code word. For example, in channels A and B the regions are spheres with centers at the code words and radius d/2 where d is the minimum distance between code words. If the received vector is in the region about code word i, it is decoded as code word i; otherwise the decoder announces an error. For all four classes of channels the following is shown to hold: There exists a fixed positive rate CBbelow which it is possible (asymptotically in n) to obtain exponentially small error probability using bounded discrepancy decoding. In many cases CBis shown to be strictly less than the channel capacity.