Improvements of Winograd's result on computation in the presence of noise (Corresp.)
Rudolf Ahlswede · IEEE Transactions on Information Theory · 1984
Winograd's result concerning Elias' model of computation in the presence of noise can be stated without reference to computation. If a code\varphi: \{0,1\}^{k} \rightarrow \{0,1\}^{n}is min-preserving(\varphi (a \wedge b) = \varphi (a) \wedge \varphi (b)fora,b \in \{0,1\}^{k})and\epsilon n-error correcting, then the ratek/n \rightarrow 0ask \rightarrow \infty. This result is improved and extended in two directions. \begin{enumerate} \item For min-preserving codes with {\em fixed} maximal (and also average) error probability on a binary symmetric channel againk/n \rightarrow 0ask \rightarrow \infty(strong converses). \item Second, codes with lattice properties without reference to computing are studied for their own sake. Already for monotone codes( \varphi (a) \leq \varphi (b)fora \leq b)the results in direction 1) hold for maximal errors. \end{enumerate} These results provide examples of coding theorems in which entropy plays no role, and they can be reconsidered from the viewpoint of multiuser information theory.