DocumentCode :
918713
Title :
Enumerative source encoding
Author :
Cover, Thomas M.
Volume :
19
Issue :
1
fYear :
1973
fDate :
1/1/1973 12:00:00 AM
Firstpage :
73
Lastpage :
77
Abstract :
Let 
be a given subset of binary n-sequences. We provide an explicit scheme for calculating the index of any sequence in according to its position in the lexicographic ordering of . A simple inverse algorithm is also given. Particularly nice formulas arise when is the set of all 
-sequences of weight 
and also when is the set of all sequences having a given empirical Markov property. Schalkwijk and Lynch have investigated the former case. The envisioned use of this indexing scheme is to transmit or store the index rather than the sequence, thus resulting in a data compression of 
.
be a given subset of binary n-sequences. We provide an explicit scheme for calculating the index of any sequence in according to its position in the lexicographic ordering of . A simple inverse algorithm is also given. Particularly nice formulas arise when is the set of all -sequences of weight and also when is the set of all sequences having a given empirical Markov property. Schalkwijk and Lynch have investigated the former case. The envisioned use of this indexing scheme is to transmit or store the index rather than the sequence, thus resulting in a data compression of .Keywords :
Sequences; Source coding; Data compression; Encoding; Entropy; Graphics; Indexing; Statistics; Upper bound;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.1973.1054929
Filename :
1054929
Link To Document :
