DocumentCode
930514
Title
On the algorithmic foundation of information theory
Author
Heim, Roland
Volume
25
Issue
5
fYear
1979
fDate
9/1/1979 12:00:00 AM
Firstpage
557
Lastpage
566
Abstract
The information content of binary sequences is defined by minimal program complexity measures and is related to computable martingales. The equivalence of the complexity approach and the martingale approach after restriction to effective random tests is used to establish generalized source coding theorems and converses. Finite state complexity and decomposable martingales are related to classical block codes and the relative frequency behavior of sequences.
Keywords
Computation theory; Information theory; Martingales; Sequences; Source coding; Binary sequences; Block codes; Bridges; Frequency; Information theory; Random sequences; Sequential analysis; Source coding; Testing;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/TIT.1979.1056080
Filename
1056080
Link To Document