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