Fast, Practically Optimal Entropy Encoding

Abstract

An enumerator employs “indexing volumes” as the add-on values used to compute indexes for n-item ordered sets such as symbol sequences. Each indexing volume is associated with a different class into which the allowed ordered sets are partitioned. The indexing volumes all equal or exceed the number of ordered sets that belong to their respective classes. Additionally, the indexing volumes are quantized such that each volume V equals wr s , where r is an integer greater than unity, s is a non-negative integer, w is a positive integer whose resolution is less than required for some set counts. As a result, the addition operations used to compute the indexes can be performed with limited precision, and storage requirements for the add-on values can be relatively modest. By storing less than all the volumes needed but computing the remainder from those that are stored, the storage requirement can be reduced further.

1 . In an enumerative encoder, an index-computation circuit that: 
 A) for a plurality of symbol populations (i, k), where k is the number of occurrences of a given binary symbols in a binary sequence of length i, contains respective pre-stored volume values B(i, k) such that B is an integer greater than or equal to the sum of every indexing volume associated with a sequence-length-(i−1) symbol population that is a predecessor the symbol population (i, k) and B(i, k)=2 s ·w, where s is a non-negative integer, w is a positive integer less than 2 k−1 , and, for some sequence whose length is less than some length n, h is the number of binary digits in the smallest quotient that results from evenly dividing the sequence count of that symbol population by a positive-integer power of 2;    B) computes an index I(a 1 a2 . . . a n ) for an n-symbol symbol sequence (a 1 a 2  . . . a n ) by computing indexes I(a 1 a 2  . . . a t ) for successive values of t in accordance I(a 1 a 2  . . . a t )=I(a 1 a 2  . . . a t−1 )+b t ·B(t−1, k t ), where k t  is the number of occurrences of the given symbol in a 1 a 2  . . . a t , b t  equals zero if a t  has one of the symbol values, b t  equals one if a t  has the other of the symbol values, B(t−1, k t ) is obtained for some values of t by fetching the pre-stored value of B(t−1, k t ), and B(t−1, k t ) is computed in accordance with B(t−1, k t )=B(t−2, k t )+B(t−2, k t −1) for other values of t; and    C) generates an output from the index thus computed.    
   
   
       2 . A storage medium containing machine instructions readable by a computer system to configure it as an entropy encoder that: 
 A) for a plurality of symbol populations (i, k), where k is the number of occurrences of a given binary symbols in a binary sequence of length i, contains respective pre-stored volume values B(i, k) such that B is an integer greater than or equal to the sum of every indexing volume associated with a sequence-length-(i−1) symbol population that is a predecessor the symbol population (i, k) and B(i, k)=2 s ·w, where s is a non-negative integer, w is a positive integer less than 2 h−1 , and, for some sequence whose length is less than some length n, h is the number of binary digits in the smallest 1I quotient that results from evenly dividing the sequence count of that symbol population by a positive-integer power of 2;    B) computes an index I(a 1 a 2  . . . a n ) for an n-symbol symbol sequence (a 1 a 2  . . . a n ) by computing indexes I(a 1 a 2  . . . a t ) for successive values of t in accordance I(a 1 a 2  . . . a t )=I(a 1 a 2  . . . a t−1 )+b t ·B(t−1, k t ), where k t  is the number of occurrences of the given symbol in a 1 a 2  . . . a t , b t  equals zero if at has one of the symbol values, b t  equals one if a t  has the other of the symbol values, B(t−1, k t ) is obtained for some values of t by fetching the pre-stored value of B(t−1, k t ), and B(t−1, k t ) is computed in accordance with B(t−1, k t )=B(t−2, k t )+B(t−2, k t −1) for other values of t; and    C) generates from the index thus computed an output that represents an entropy code for the n-symbol sequence.    
   
   
       3 . A method of entropy encoding comprising: 
 A) for a plurality of symbol populations (i, k), where k is the number of occurrences of a given binary symbols in a binary sequence of length i, storing in a computer system respective pre-stored volume values B(i, k) such that B is an integer greater than or equal to the sum of every indexing volume associated with a sequence-length-(i−1) symbol population that is a predecessor the symbol population (i, k) and B(i, k)=2 s ·w, where s is a non-negative integer, w is a positive integer less than 2 h−1 , and, for some sequence whose length is less than some length n, h is the number of binary digits in the smallest quotient that results from evenly dividing the sequence count of that symbol population by a positive-integer power of 2; and    B) employ the computer system to: 
 i) compute an index I(a 1 a 2  . . . a n ) for an n-symbol symbol sequence (a 1 a 2  . . . a n ) by computing indexes I(a 1 a 2  . . . a t ) for successive values of t in accordance I(a 1 a 2  . . . a t )=I(a 1 a 2  . . . a t−1 )+b t ·B(t−1, k t ), where k t  is the number of occurrences of the given symbol in a 1 a 2  . . . a t , b t  equals zero if a t  has one of the symbol values, b t  equals one if a t  has the other of the symbol values, B(t−1, k t ) is obtained for some values of t by fetching the pre-stored value of B(t−1, k t ), and B(t−1, k t ) is computed in accordance with B(t−1, k t )=B(t−2, k t )+B(t−2, k t −1) for other values of t; and  
 ii) generate from the index thus computed an output that represents an entropy code for the n-symbol sequence.