DocumentCode :
923652
Title :
Uniformly reasonable source encoding is often practically impossible
Author :
Fine, Terrence L.
Volume :
21
Issue :
4
fYear :
1975
fDate :
7/1/1975 12:00:00 AM
Firstpage :
368
Lastpage :
373
Abstract :
The decoding of efficiently encoded messages, from either probabilistic, nonprobabilistic, or unknown message sources, is shown to be often practically impossible. If \\tau (S) is a running-time bound on the computational effort of a decoder \\Psi accepting a codeword P for message S , and \\gamma [K_{\\Psi }(S)] is an upper bound to acceptable codeword length \\mid P \\mid when the shortest codeword for S has length K_{\\Psi }(S) , then for many message sources mathcal{M} there exist messages S \\in mathcal{M} such that: 1) if the encoder satisfies \\gamma , then the decoder violates \\tau ; 2) if the decoder satisfies \\tau , then the encoder violates \\gamma . These conclusions remain valid even when we allow the decoder to reconstruct only an approximation S \\prime in a neighborhood \\delta (S) of S . The compatibility of these results with those of information theory rests upon the fact that we are inquiring into the detailed properties of coding systems for individual messages and not into the ensemble average properties.
Keywords :
Decoding; Source coding; Binary sequences; Computational complexity; Data compression; Decoding; Encoding; Frequency; Helium; Information theory; Intersymbol interference; Upper bound;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.1975.1055413
Filename :
1055413
Link To Document :
بازگشت