DocumentCode :
939517
Title :
Improvements of Winograd´s result on computation in the presence of noise (Corresp.)
Author :
Ahlswede, Rudolf
Volume :
30
Issue :
6
fYear :
1984
fDate :
11/1/1984 12:00:00 AM
Firstpage :
872
Lastpage :
877
Abstract :
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) for a,b \\in {0,1}^{k}) and \\epsilon n -error correcting, then the rate k/n \\rightarrow 0 as k \\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 again k/n \\rightarrow 0 as k \\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) for a \\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.
Keywords :
Computation theory; Error-correction coding; Combinatorial mathematics; Computational modeling; Decoding; Entropy; Error correction codes; Error probability; Information theory; Lattices; Welding;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.1984.1056974
Filename :
1056974
Link To Document :
بازگشت