Huffman coding for infinite symbol sets

[0002] This present invention relates generally to lossless data compression, and more particularly to code design and code selection for infinite symbol sets.

[0003] Lossless compression or entropy coding is used in communication and storage of digital information. In the method generally referred to as Huffman coding, see David A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes”, Proc. of the IRE,vol. 40(10), September, 1952, doc. D1, the source data is separated into symbols 20 (see FIG. 1). The entropy coder 22 of FIG. 1 represents symbols 20 as variable length bit strings 26 (i.e., codewords) looked up in a codebook 24. Compression relies on assigning short codewords to frequent symbols and reserving longer codewords for infrequent symbols. The performance of a coder depends on its ability to match the probability distribution of symbols in the source with the probability distribution corresponding to the codebook.

[0004] A fundamental codebook design problem is how to design a codebook given the probability distribution of the source. Two methods are in general use, one for “finite” codes and the other for “infinite” codes. Finite codes can represent a known number of symbols, each symbol having a known non-zero probability of occurrence. Infinite codes, on the other hand, are infinite in the sense that they are “infinitely expandable”, i.e., a given infinite code can be expanded as far as needed to represent a desired set of input symbols. To be a valid infinite code, no codeword can be a prefix for any other codeword. An “infinite symbol set” is a set of symbols, which can be finite, that is represented by an infinite code.

[0005] Finite codebooks can be designed using the Huffman algorithm to generate a codebook matched to the source statistics. This algorithm constructs the set of codewords by starting from the least probable symbol and moving upward in probability. One suboptimal but reduced-complexity finite Huffman coding example is disclosed in U.S. Pat. No. 4,560,976, entitled “Data Compression” and issued Dec. 24, 1985 to Finn. Finn describes a finite codebook consisting only of one-, two-, and three-subword-long codewords. Finn uses a symbol-appearance-counting method to continuously re-rank his symbols and to decide which symbols should be assigned to which of his three lengths of codewords.

[0006] Finite-codebook methods such as those above are not well suited to infinite codes. One reason is that symbol appearance counting will not generally be able to adequately estimate the probability of occurrence of a large number of symbols having non-zero but near-zero symbol probabilities.

[0007] Several families of infinite codes have been developed based on regular structures or algorithms. Golomb codes are one such family of codes. See S. W. Golomb, “Run length encodings”, IEEE Trans. Inform. Theory,vol. 12, pp. 399-401, July, 1966. Geometrically distributed (i.e., exponential) codes are another such family. See R. Gallager and D. C. Van Voorhis, “Optimal source codes for geometrically distributed integer alphabets”, IEEE Trans. Inform. Theory,vol. 21, pp. 228-30, March, 1975. Other algorithmic infinite codes exist as well. See, e.g., N. Merhav et al., “Optimal Prefix Codes for Sources with Two-Sided Geometric Distributions”, IEEE Trans Inform. Theory,vol. 46, pp. 121-35, January, 2000; N. Merhav et al., “The LOCO-I Lossless Image Compression Algorithm: Principles and Standardization into JPEG-LS”, IEEE Trans. Image Processing,vol. 9, No. 8, August, 2000.

[0008] The regular-structured algorithmic approach provides a way to generate an infinite number of codewords but gives limited control over the resulting probability distribution. Another publication describes a method to generate an optimal codebook for an infinite distribution through a recursive sequence of calculations. A. Kato et al., “Huffman Coding with an Infinite Alphabet”, IEEE Trans. Inform. Theoryvol. 42, pp. 977-84, May, 1996. This approach serves more as a theoretical construction since the complexity of encoding and decoding this code can be significant.

[0009] An alternative to matching a probability distribution with a fixed code is to use adaptive coding. In adaptive coding, the codeword used to represent a symbol is changed dynamically while the encoder operates. Changes in the encoder are either signaled by introducing overhead, or tracked from the decoded data. Overhead subtracts from the compression efficiency, and tracking the encoder state from decoded data is error prone. In both cases, additional complexity is introduced into the encoding and decoding operations.

[0010] Arithmetic coding can also be used to efficiently code a general probability distribution but the additional complexity of an arithmetic coder can be a drawback in some applications.

[0011] The present disclosure addresses the problem of developing an infinite code tailored to a given probability distribution. Using the methods described herein, it is possible to generate a low complexity code that provides good compression performance.

[0012] Generally, the described embodiments model a given probability using a combination of two or more existing infinite codes. Codes of low complexity are preferred. For instance, two Golomb codes may be selected, one that matches the source distribution well for symbol indices near zero, and another that matches the source distribution well for large symbol indices. The two codes are “grafted” together such that the first is used for the symbol indices near zero, and the second is used for all other indices. When properly grafted as taught herein, only a few parameters are needed to describe such a distribution.

[0013] The disclosure generalizes the idea as explained simply above to accommodate a wide range of existing infinite codes and any desired number of code intervals. The described embodiments pertain generally to constructing a grafted codebook, encoding symbols using a grafted codebook, and decoding codewords formed using a grafted codebook.

[0014] The invention may be best understood by reading the disclosure with reference to the drawing, wherein:

[0015] FIG. 1 illustrates the general block diagram of an entropy coder;

[0016] FIG. 2 shows a block diagram for a codebook generator according to an embodiment of the invention;

[0017] FIGS. 3 and 4 illustrate, respectively, linear and semi-log plots of a sample probability distribution used in the examples;

[0018] FIGS. 5 and 6 illustrate, respectively, linear and semi-log plots of a minimal redundancy exponential model of the sample probability distribution;

[0019] FIG. 7 illustrate a piecewise model of the sample probability distribution;

[0020] FIGS. 8 and 9 illustrate, respectively, linear and semi-log plots of a grafted code probability distribution generated according to an embodiment of the invention;

[0021] FIG. 10 contains a plot contrasting the original sample probability distribution, the minimal redundancy exponential model, and the grafted code probability distribution of FIGS. 8 and 9;

[0022] FIG. 11 plots redundancy v. bit-rate for a test video sequence, comparing a universal variable length code against a grafted code generated according to an embodiment of the invention;

[0023] FIG. 12 is a block diagram of an encoder capable of coding symbols according to a grafted codebook;

[0024] FIG. 13 is a flowchart for the operation of an encoder capable of coding symbols according to a grafted codebook;

[0025] FIG. 14 is a block diagram of a decoder capable of decoding symbols coded using a grafted codebook; and

[0026] FIG. 15 is a flowchart for the operation of a decoder capable of decoding symbols using a grafted codebook.

[0027] The following description pertains to entropy coders of the same general type shown in FIG. 1, i.e., coders that compress a sequence of symbols by using a codebook to convert symbols into variable length bit strings. The goal is to design a codebook that gives efficient compression. Three major operations are used in developing the codebook, as shown in FIG. 2. A distribution modeler 30 models an input probability distribution p(x) as a piecewise function built from a set of model distributions 32. Second, a model codebook generator 40 generates a set of codebooks, one codebook corresponding to each model distribution. A codebook grafter 50 then grafts the codebooks 40 into a single codebook 52 based on the piecewise decomposition of the original probability distribution.

[0028] The entropy of the source distribution $E=\sum _{i=0}^{\infty }-p\left(i\right){\log }_2\left(p\left(i\right)\right)$

[0029] provides a lower limit on the average bit rate per symbol in the encoder output. This is based on an ideal code that assigns −log₂(p(i)) bits to the i^thsymbol. The effectiveness of coding with a model

[0030] distribution {circumflex over (p)}(i) is evaluated by computing the coding redundancy $R=\sum _{i=0}^{\infty }-p\left(i\right){\log }_2\left(\hat{p}\left(i\right)\right).$

[0031] In general, R≧E for a given code, i.e., in practice the lower limit determined by the entropy E cannot be achieved. The difference, however, between the coding redundancy and the entropy determines the effectiveness of code.

[0032] A typical sample probability distribution p(x) is illustrated as line 70 on a linear plot in FIG. 3, and on a semi-log plot in FIG. 4. The semi-log plot of FIG. 4 illustrates the asymptotic decay of the distribution. This also shows the increase in length of the ideal entropy codewords. To minimize redundancy, the model distribution {circumflex over (p)}(i) should approximate the logarithm of the actual distribution p(i).

[0033] As a comparison, a first example models the probability distribution on the entire interval [0, ∞) using a single one-sided exponential distribution: $m_{\mathrm{ck}}\left(i\right)=\{\begin{array}{cc}\left(1-k\right)·k^{\left(i+c\right)}& i\ge -c\\ 0& i<-c\end{array}$

[0034] Infinite codes exist that approximate the one-sided exponential distributions. See S. W Golomb, “Run length encodings”, IEEE Trans. Inform. Theory,vol. 12, pp. 399-401, July, 1966. The one-sided exponential distribution that gives minimal redundancy when coding the sample distribution of FIG. 3 has k=0.9 and C=0. FIG. 5 plots the sample probability distribution 70 of FIG. 3 against this minimal redundancy one-sided exponential distribution 80 on a linear plot. FIG. 6 shows the same distribution pairing on a semi-log plot.

[0035] In this example, the entropy and coding redundancy of the exponential code are Entropy=4.35985 and R_exponential=4.64767. Notice that on the semi-log plot of FIG. 6, the exponential model distribution 80 diverges significantly from the sample distribution 70, suggesting that a better model can be found. The design example below illustrates that using an embodiment of the present invention, a model distribution and a codebook for sample distribution 70 can be generated to give a lower coding redundancy than the exponential model.

[0036] The first step in developing a code tuned to the probability distribution is designing a model of the input probability distribution. One embodiment assumes a probability distribution that is supported in [0, ∞). Since in general the distribution will exhibit different characteristics on different ranges of inputs, the distribution modeler captures the behavior of the input probability distribution on these different ranges. The distribution modeler accepts (or calculates) a division of the interval [0, ∞) into a set of L+1 subintervals {I₀, I₁, . . . I_L}={[N₀, N₁), [N₁, N₂), . . . , [N_L, ∞)} (modeling intervals 34 in FIG. 2). Distribution modeler 30 uses a family of model distributions {m_k(x)} to construct a model of p(x) on each subinterval. As shown in FIG. 7, distribution modeler 30 models an input distribution 60 by a set of piecewise segments 62, 64, 66, 68, i.e. in general, $p\left(x\right)\approx \hat{p}\left(x\right)=\{\begin{array}{cc}{m}_0\left(x\right)& N_0\le x<N_1\\ m_1\left(x\right)& N_1\le x<N_2\\ \dots & \dots \\ m_L\left(x\right)& N_L\le x<\infty .\end{array}$

[0037] A model distribution match is performed for each interval [N_k, N_k+1). The set of model distributions is designed to minimize the total coding redundancy of Equation 1 subject to the constraints of Equation 2. $\begin{array}{cc}{R}_k=\sum _{i=N_k}^{i<N_{k+1}}-p\left(i\right)·{\log }_2\left(m_k\left(i\right)\right)R_{\mathrm{total}}=\sum _{k=0}^{k=L}{R}_k& \left(1\right)\\ \forall k\sum _{i=-\infty }^{\infty }{m}_k\left(i\right)=1\sum _{k=0}^{k=L}\sum _{i=N_{k-1}}^{i<N_k}{m}_k\left(i\right)=1& \left(2\right)\end{array}$

[0038] Minimization of the coding redundancy requires that a modeling function m_k(x) cannot be zero at any point in its interval N_kwhere p(x) is non-zero. The first constraint equation requires each model function to give a unit probability over the entire interval. The second constraint equation requires the piecewise model to give a unit probability over the entire interval. Distribution modeler 30 preferably generates the model distributions 32 by minimizing the total coding redundancy subject to these constraints.

[0039] In the previous step a model of the probability distribution 70 was determined using a piecewise collection of model distributions. With the model distributions specified, a code C_k(i) is developed for each model distribution. The codebook corresponding to each model distribution is preferably computed based on an existing infinite code. Codes with low encoding and decoding complexity can be used for the model distributions to limit the complexity of the resulting code.

[0040] As an example, the family of Golomb codes, {G_m(i)}, can be used. Details on these codes can be found in S. W. Golomb, “Run length encodings”, IEEE Trans. Inform. Theory,vol. 12, pp. 399-401, July, 1966; R. Gallager and D. C. Van Voorhis, “Optimal source codes for geometrically distributed integer alphabets”, IEEE Trans. Inform. Theory,vol. 21, pp. 228-30, March, 1975; N. Merhav et al., “Optimal Prefix Codes for Sources with Two-Sided Geometric Distributions”, IEEE Trans Inform. Theory,vol. 46, pp. 121-35, January, 2000. A brief summary of Golomb codes is given below.

[0041] Each Golomb code in the family is defined by a single parameter m. The codewords of G_mhave a regular structure. Each codeword is formed from a prefix and a suffix. The i^thcodeword is formed by selecting prefix i/m and suffix i%m. Prefix i/m is the unary representation of 1 using i/m bits. For the suffix corresponding to each prefix, there are m distinct values representing the binary representations of the possible remainders i%m. The number of bits used to represent each suffix depends on m and i%m, but for each code only m distinct suffix values are used. Sample prefix and suffix values are shown in Table 1. Codebooks for the first 8 Golomb codes are shown in Table 2.

[0042] In one embodiment, the model codebook constructor 40 of FIG. 2 selects a different Golomb code for each of the model distributions 32, e.g., the Golomb code best matching the input distribution on each modeling interval.

[0043] The codebooks C_k(i) corresponding to the model distributions are merged into a single codebook. The codebooks are merged by taking the section of codebook C_k(i) that corresponds to the symbols in interval I_k=[N_k, N_k+1). The interval I_kcontributes N_k+1−N_kcodewords to the grafted codebook. The codewords are selected from the codebook C_k(i) using an offset O_k. The grafted codebook is defined by selecting segments from each of the model codebooks via C(i)=C_j(i+O_j) where i I _j. The offsets are computed recursively using the cumulative probability of the preceding intervals [0, N_k). The first offset O₀is zero and successive offsets are computed recursively by solving the following for O_k: $\sum _{i=0}^{i<N_k+O_k}{\left(\frac{1}{2}\right)}^{\Vert C_k\left(i+O_k\right)\Vert }=\sum _{j=0}^{j=k-1}\sum _{i=N_j}^{i<N_{j+1}}{\left(\frac{1}{2}\right)}^{\Vert C_j\left(i+O_j\right)\Vert }\approx \sum _{i=0}^{i<N_k}\hat{p}\left(i\right)$

[0044] The norm ∥C_j(i+O_j)∥ denotes the length of codeword i+O_jin code j. The following example of combining codebooks uses the intervals [0,2), [2,4), and [4, ∞), with a respective selection for each interval of the Golomb codes G₂, G₄and G₇. Table 3 shows the first few elements for the Golomb codes G₂, G₄and G₇.

[0045] To determine the offsets, the codebook grafter computes the cumulative probability functions corresponding to each code. Since offset O₀is zero, the cumulative probability for calculating offset O₁the cumulative probability up to and including G₂(1), i.e., 0.50 as shown in Table 4. Examining the cumulative probabilities of G₂and G₄in Table 4, it can be seen that the cumulative probability of G₄(3) is equal to the cumulative probability of G₂(1), therefore O₁=2 the first codeword selected from G₄is G₄(4). Likewise, the cumulative probability for calculating offset O₂is the cumulative probability up to and including the last codeword selected from G₄(G₄(5)), i.e., 0.50 as shown in Table 4. Examining the cumulative probabilities of G₄and G₇in Table 4, it can be seen that the cumulative probability of G₇(9) is equal to the cumulative probability of G₄(5), therefore O₂=6 and the first codeword selected from G₇is G₇(10).

[0046] Table 5 shows the grafted codebook formed from G₂, G₄, and G₇using the offsets O₀, O₁, and O₂.

[0047] The following example illustrates a grafted codebook design for the sample distribution 70 presented earlier. The interval [0, ∞) is divided into two subintervals [0, ∞)=[0, 3)∪[3, ∞) at the distribution modeler. The distribution will be modeled by a piecewise function built from two distribution functions. $p\left(x\right)=\{\begin{array}{cc}{m}_0\left(x\right)& 0\le x<3\\ m_1\left(x\right)& 3\le x\end{array}$

[0048] The model distributions were chosen from the family of one-sided exponential distributions: $m_j\left(i\right)=\{\begin{array}{cc}\left(1-k\right)·k_j^{\left(i+C_j\right)}& i\ge -c_j\\ 0& i<-c_j\end{array}$

[0049] The constraint on the cumulative probability becomes: $\begin{array}{cc}\sum _{i=0}^{2}p\left(i\right)·\left(1-k_0\right)k_0^{\left(i+C_0\right)}+\sum _{i=3}^{\infty }p\left(i\right)·\left(1-k_1\right)k_1^{\left(i+C_1\right)}=1& \left(3\right)\end{array}$

[0050] The coding redundancy becomes: $\begin{array}{cc}R\left(C_0,k_0,C_1,k_1\right)=\sum _{i=0}^2-p\left(i\right){\log }_2\left(\left(1-k_0\right)k_0^{\left(i+C_0\right)}\right)+\sum _{i=3}^{\infty }-p\left(i\right){\log }_2\left(\left(1-k_1\right)k_1^{\left(i+C_1\right)}\right)& \left(4\right)\end{array}$

[0051] A small search through the parameter space (C₀, k₀, C₁, k₁) was conducted to minimize the redundancy of Equation 4 subject to the constraint of Equation 3. To reduce the search space, the parameters were restricted so that C₀=0 and $k_0,k_1\in \left\{{\left(\frac{1}{2}\right)}^{\frac{1}{m}}|m\in \left\{2,4,8\right\}\right\}$

[0052] with the value of C1 determined by the constraint of Equation 3. The search resulted in parameters $\left(C_0,k_0,C_1,k_1\right)=\left(0,{\left(\frac{1}{2}\right)}^{\frac{1}{4}},12,{\left(\frac{1}{2}\right)}^{\frac{1}{8}}\right).$

[0053] The corresponding probability distributions and cumulative distributions are shown respectively in FIGS. 8 and 9, where 70 is the original distribution, 90 is model distribution m₀, 92 is model distribution m₁, and 94 is the final grafted distribution.

[0054] The semi-log plot of FIG. 10 compares the original distribution 70, the exponential model distribution 80 developed in the comparative example, and the grafted model distribution 94.

[0055] The Golomb codes G₄and G₈are used with these model distributions. These codes were presented earlier in Table 2. The offset O₁=3 used to access G₈is determined by solving Equation 5: $\begin{array}{cc}\sum _{i=0}^{i<3+O_1}{\left(\frac{1}{2}\right)}^{\Vert G_8\left(i\right)\Vert }=\sum _{i=0}^{i<3}{\left(\frac{1}{2}\right)}^{\Vert G_4\left(i\right)\Vert }& \left(5\right)\end{array}$

[0056] Table 6 shows the cumulative distribution functions corresponding to G₄(i.e., m₀) and G₈(i.e., m₁). The right hand side of Equation 5 corresponds to the third element of column m₀of Table 6, i.e., the sum of the first three probabilities of G₄is 0.405396. The left hand side of Equation 5 corresponds to column m₁of Table 6. As can be seen, the sum of the first six probabilities of G₈is also 0.405396, therefore Equation 5 is satisfied for O₁=3. Thus the grafted codebook consists of the first three elements of G_4,followed by elements from G₈starting the seventh element. The first six elements of G₈are skipped in order to satisfy the constraint that the cumulative probability must equal one. The grafted codebook is shown in Table 7.

[0057] This model constructed by grafting the Golomb codes of order 4 and 8 results in a coding redundancy of R_grafted=4.47367. For comparison, the results of coding the sample distribution with several codes are illustrated in Table 8.

[0058] In Table 8, the entropy represents the lower limit. The exponential entry is the redundancy of the exponential model. Any code developed based on this model will have a slightly higher redundancy. The grafted entry is the redundancy of coding using the model constructed above by grafting the first three symbols of G₄and G₈. G₄and G₈are the redundancies of coding only with the Golomb codes of order 4 and 8, respectively. For a relative comparison we use $\frac{R_{\mathrm{grafted}}}{\mathrm{Entropy}}=1.025229\mathrm{and}\frac{R\mathrm{exponential}}{\mathrm{Entropy}}=1.066514.$

[0059] The grafted model gives 4% improvement over the model based on a single exponential function.

[0060] One of the primary advantages of a grafted codebook formed according to embodiments such as described above is that a grafted codebook can model many different types of probability distributions to achieve good compression, while at the same time placing only minimal demands on an encoder and decoder.

[0061] For instance, consider encoder 120 shown in FIG. 12. Encoder 120 comprises an interval selector 122, a regular-structure code generator 124, and an adder 126. The components of encoder 120 can be implemented in digital logic hardware, in software running on a programmable processor with attached memory, or in some combination of the two. Selection of the appropriate hardware is dependent on the application.

[0062] Interval selector 122 is responsible for determining which interval of the grafted codebook is pertinent to a received input symbol with index i. Selector 122 accepts several inputs to allow it to make this determination. First, the number of modeling intervals in the grafted codebook is supplied to selector 122 by the value L (note that a value of L corresponds to L+1 actual modeling intervals). A total of L interval endpoints N_kare also supplied to selector 122 to allow it to know the ranges of each modeling interval. A total of L+1 code family identifiers G_kare supplied to selector 122—the selector associates one of these code family identifiers with each modeling interval. When the code family is the family of Golomb codes, for example, the identifier G_kis equal to m for the desired Golomb code. Finally, a set of L offsets O_kis supplied to interval selector 122.

[0063] When a symbol with index i arrives at encoder 20, interval selector 122 compares the symbol to the interval endpoints N_kto find the appropriate interval for the symbol. Once the interval is located, the interval selector outputs the corresponding G_kand O_kvalues.

[0064] Summer 126 adds index i and offset O_kto determine an offset index j. Offset index j is supplied along with G_kto regular-structure code generator 124, which in one embodiment is a generalized Golomb code generator. Code generator 124 outputs the correct grafted codebook codeword for index i.

[0065] FIG. 13 illustrates a flowchart 130 corresponding to one way of performing the functions of encoder 120. At block 128, the encoder receives (or translates, in some embodiments) a symbol of index i. Block 132 sets k=1 in preparation for performing a search of the interval endpoints. Decision block 134 tests i against the currently indexed interval endpoint N_k. If i is greater, the correct modeling interval has been found, and control is transferred to block 140. Otherwise, block 136 increments k, and then decision block 138 tests k against L. If k is greater, i lies in the last interval, and control is transferred to block 140. Otherwise, control is transferred back to decision block 134 and the next interval endpoint is tested.

[0066] At block 140, the code identifier m is set to the input code identifier m_k−1. Also, the offset index j is set to i+O_k−1. The values m and j are then passed to block 142, which generates an output codeword G_m(j) from a regular-structure code family. The system is then ready to process the next symbol index i.

[0067] At the receiving end, a decoder must decode the output codeword G_m(j) to determine the symbol index i, reversing the process of the encoder. FIG. 14 shows a block diagram for a decoder 150 designed for this task. Decoder 150 comprises a grafting codebook indexer 152, a regular-structure code indexer 154, and an adder 156. The components of decoder 150 can be implemented in digital logic hardware, in software running on a programmable processor with attached memory, or in some combination of the two. Selection of the appropriate hardware is dependent on the application.

[0068] Grafting codebook indexer 152 accepts the same inputs as interval selector 122 of FIG. 12. The task of indexer 152 is somewhat more difficult, however, as at the time a codeword is received the indexer will not know the length of the codeword nor the specific one of the grafted codes used to generate that codeword. Nevertheless, using the prefix of the codeword as a clue, it is possible for the decoder to determine which of the grafted codes generated that codeword. Once this is determined, indexer 152 passes the appropriate code identifier m_kto regular-structure code indexer 154, and passes the appropriate offset O_kto adder 156.

[0069] Regular-structure code indexer 154 accepts the input codeword and the code identifier m_k. From these, indexer 154 can work backwards in a well-known manner to calculate the offset index j for the codeword. Adder 156 then subtracts offset O_kfrom offset index j to reconstruct symbol index i.

[0070] Decoder 150 can operate functionally in many different ways to accomplish the same function. One of these ways is illustrated in flowchart 160 of FIG. 15. In FIG. 15, block 162 precalculates a number of constants for later use. For each value of k between 0 and L, inclusive, a value P_kmin, equal to the minimum prefix length actually used for that value of k in the grafted codebook, is calculated. A similar maximum prefix length value P_kmaxis calculated as well for each value of k between 0 and L−1, inclusive. Finally, the suffix value for the first codeword actually used with code identifier m_k, Ski, is stored as well.

[0071] At block 164, a codeword G_?(?) of unknown order and length exists at the head of the codeword bitstream. Block 166 identifies the prefix for the codeword and calculates the prefix length p. Block 168 sets k=0 and then a search for the appropriate index k is begun.

[0072] Decision block 170 tests prefix length p to see if it is between P_kminand P_kmax. If not, block 172 increments k. Another decision block 174 tests the new value of k against the interval count L. If k equals L, the last interval has been reached, and the search can stop. Otherwise, the flowchart branches back to block 170 and the next interval is tested.

[0073] If the prefix length p is between P_kminand P_kmax, the search for k may not be over. It may be possible that prefix length p is shared between two neighboring intervals, in which case the suffix must be examined to determine which value of k is correct. To test whether this process is required, block 176 tests p to see if it is equal to P_(k+1)min. If not, the prefix length is not shared, and the correct value of k has been located. If block 176 evaluates true, however, control is passed to decision block 178 where the current suffix SUFF is compared to the stored value S_(k+1)min. If SUFF is less, the correct value of k has been located. If SUFF is greater than or equal, the codeword actually lies in the second of the intervals, and k is incremented accordingly at block 180.

[0074] Once k is known, block 182 can generate the offset index j corresponding to the codeword G_mk(?) using the now known code identifier m_k. Finally, the symbol index i is calculated at block 184 by subtracting offset O_kfrom offset index j. The value i is output and the process loops back to process the next codeword in the bitstream.

[0075] Note that a regular-structure code generator and code indexer refer to an infinite code that has a defined algorithm for calculating a codeword from a symbol index, and vice-versa. A generalized Golomb code generator and code indexer are examples of regular-structure coding devices that accept a Golomb parameter m and can calculate values from a Golomb distribution G_mtherefrom.

[0076] Not shown in the encoder and decoder is an optional translation table that may be needed in some implementations to translate actual symbols into their respective symbol indices i. It is also noted that the encoder and decoder shown are amenable to use in an adaptive coding process. Note that if a code modeler determines that an adaptation to a new grafted code is advantageous, the adaptation can be implemented by transmitting new values for L, N_k, m_k, and/or O_kto the encoder and decoder. This adaptation process is much easier and more efficient than calculating and transmitting a whole new non-regular-structure codebook, and is much less error-prone than adaptive methods that track the encoder state from the decoded data.

[0077] The coding gains possible with an embodiment of the invention are illustrated with an example taken from the H.26L video coding test model. The grafted encoder was tested on the video sequence “news” at a range of bit-rates, 10 kbps-320 kbps. In the comparison test model, symbols corresponding to transform coefficients are coded using a universal variable length code (UVLC). A grafted code was constructed from the Golomb codes G₂and G₈for encoding the same transform coefficient symbols. The grafted code was designed using a distribution captured from encoding the sequence “garden” at 300 kbps. The results of both codes are compared with the source entropy in FIG. 11 for a range of bit-rates, where the source entropy of the symbols is shown as line 100, the redundancy of the UVLC is shown as line 102, and the redundancy of the grafted code is shown as line 104. At higher bit-rates the grafted code 104 performs near the lower limit given by the source entropy 100. At very low bit-rates, the UVLC 102 gives some improvement over the grafted code 104, reflecting the fact that the grafted code 104 was designed using a sample distribution corresponding to a high bit-rate source. Similar results are seen using the same grafted code with a variety of video sequences. The grafted code switches between two Golomb codes, therefore the complexity is minimal.

[0078] One of ordinary skill in the art will recognize that the concepts taught herein can be tailored to a particular application in many other advantageous ways. In particular, those skilled in the art will recognize that the illustrated embodiments are but one of many alternative implementations that will become apparent upon reading this disclosure. For instance, a more general family of model distributions can be used. Other families of infinite codes than the Golomb codes can be used, such as exponential codes, or codes from more than one family can be grafted. Such minor modifications are encompassed within the invention, and are intended to fall within the scope of the claims.

[0079] The preceding embodiments are exemplary. Although the specification may refer to “an”, “one”, “another”, or “some” embodiment(s) in several locations, this does not necessarily mean that each such reference is to the same embodiment(s), or that the feature only applies to a single embodiment.