PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
January 1, 1973IEEE Transactions on Information Theory514 citations

Enumerative source encoding

View Full Paper
TCThomas M. Cover

Key Points

  • To establish an explicit scheme and inverse algorithm for indexing constrained binary sequences in lexicographic order to achieve data compression.
  • Formulated mathematical algorithms to map any binary n-sequence from a subset to its lexicographical index position.
  • Constructed a companion inverse algorithm to reconstruct the original sequence from its numerical index.
  • Derived specialized formulas for subsets of fixed Hamming weight and sequences characterized by empirical Markov properties.
  • Provided exact encoding and decoding formulas that map constrained binary sequences directly to compact indices.
  • Demonstrated that transmitting or storing sequence indices achieves an optimal data compression rate of (log |S|)/n.

Abstract

Let S be a given subset of binary n-sequences. We provide an explicit scheme for calculating the index of any sequence in S according to its position in the lexicographic ordering of S. A simple inverse algorithm is also given. Particularly nice formulas arise when S is the set of all n -sequences of weight k and also when S 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 () /n.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Thomas M. Cover (1973) studied this question.

synapsesocial.com/papers/6a11c2f3276e1b6925c909behttps://doi.org/10.1109/tit.1973.1054929
Ask AI
Helpful
Bookmark
Share
View Full Paper