HYBRID ARITHMETIC-COMBINATORIAL ENCODER

• US 20110156932A1
• Filed: 12/31/2009
• Published: 06/30/2011
• Est. Priority Date: 12/31/2009
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Ashley, James P., Mittal, Udar, Ramabadran, Tenkasi V.
• Granted Patent: US 8,149,144 B2
• Time in Patent Office: Days
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code

Abstract

Hybrid range coding/combinatorial coding (FPC) encoders and decoders are provided. Encoding and decoding can be dynamically switched between range coding and combinatorial according to the ratio of ones to the ratio of bits in a partial remaining sequence in order to reduce the computational complexity of encoding and decoding.

Claims

1. A method of encoding a binary sequence comprising:

determining a ratio of one-valued bits to a total number of bits in said binary sequence;

when said ratio is within a predetermined range, encoding said binary sequence using range coding; and

when said ratio is outside said predetermined range, encoding said binary sequence using combinatorial coding.

2. The method according to claim 1 wherein encoding said binary sequence using range coding comprises coding said binary sequence using arithmetic coding.

3. The method according to claim 1 wherein an upper bound of said predetermined range is between ½

and one and a lower bound of said predetermined range is between zero and ½

.

4. The method according to claim 1 wherein predetermined range is ¼

to ¾

.

5. A method of encoding a binary sequence comprising:

selecting at least a first portion of said binary sequence to be coded using combinatorial coding;

selecting at least a second portion of said binary sequence to be coded using range coding;

coding said first portion using combinatorial coding to obtain an combinatorial code;

coding said second portion using range coding to obtain an arithmetic code.

6. The method of encoding according to claim 5 further comprising:

adding said range code to said combinatorial code.

7. The method of encoding the binary sequence according to claim 5 wherein said first portion is selected such that a ratio of one-valued bits to a number of bits in said first portion satisfies at least one bound.

8. The method of encoding the binary sequence according to claim 6 wherein said at least one bound is altered after initially identifying a beginning of said first portion in order to effect a hysteresis so as to reduce switching back and forth between range coding and combinatorial coding.

9. The method according to claim 5 wherein coding said second portion using range coding comprises scaling down a range code generated by said range coding by applying an initial probability.

10. The method according to claim 9 wherein said initial probability is given by an approximation of a combinatorial function of a number of one bits and a total number of bits in a remaining bit sequence portion that includes said first portion, wherein said approximation of said combinatorial function is also used in said combinatorial coding.

11. The method according to claim 5 wherein said range coding comprises arithmetic coding and said combinatorial coding comprises factorial pulse coding.

12. A method of decoding a combined arithmetic/factorial pulse code, the method comprising:

(a) using a known number of ones represented in said combined arithmetic/factorial pulse code, iteratively evaluating an approximation of a combinatorial function using different postulated positions of a last one in order to determine a postulated position that yields a largest value that is less than said combined arithmetic/factorial pulse code;

(b) subtracting said largest value from said combined arithmetic/factorial pulse code to obtain a first remaining code value;

(c) testing if a ratio of a remaining number of one bits to a remaining total number of bits satisfies a bound for regulating transitioning from factorial pulse coding to arithmetic coding;

(d) when said bound for regulating transitioning between factorial pulse coding and arithmetic coding is satisfied decoding at least a portion of said remaining code value using arithmetic decoding;

(e) after each bit is decoded using arithmetic decoding testing if a bound for regulating transitioning from arithmetic coding to factorial pulse coding is satisfied;

(f) when said bound for regulating transitioning from arithmetic coding to factorial pulse coding is satisfied selecting a second remaining code value and returning to step (a)

(g) when said combined arithmetic/factorial pulse code is fully decoded ceasing.

13. A method of encoding a pulse vector comprising:

using arithmetic encoding, generating at least one arithmetic code component to represent at least one item of information selected from the group consisting of;

a set of locations of a set of non-zero pulses and a set of pulse magnitudes of said set of non-zero pulses;

combining said at least one arithmetic code component using a factorial pulse coding code combining formula.

14. The method of encoding according to claim 13 wherein said factorial pulse coding code combining formula is:

C=C_v+(P(n,v)C_μ

+C_π

)2^v+C_σ

where,

Cμ

is said code component representing said pulse magnitudes of said set of non-zero pulses;

Cπ

is said code component representing said set of locations;

Cσ

is a code component representing signs;

Cv is a code component representing a number of non-zero pulses.

15. The method of encoding according to claim 14 wherein Cπ

is an arithmetic codeword.

16. The method of claim 14 wherein Cπ

is determined by combinatorial coding when a ratio of a number of non-zero pulse to a total number of pulse positions satisfies a predetermined bound.

17. The method of encoding according to claim 14 wherein Cμ

is an arithmetic codeword.

18. The method of claim 14 wherein Cμ

selectively determined by combinatorial coding or arithmetic coding depending on how a ratio of one-bits to total bits in a binary vector representing said pulse magnitudes compares to at least one bound.

19. The method of encoding according to claim 15 wherein using arithmetic encoding comprises reducing an initial position in an AC code space by a applying a leading factor.

20. The method of claim 19 wherein the initial position in the AC code space is based on an upper bound on a number of extra bits to be used for AC with finite fixed precision length.

21. The method of claim 19 wherein the initial position in the AC code space is a function of an approximate combinatorial function.

22. A method of decoding comprising:

receiving a codeword representing an integer pulse sequence;

decoding a number of non-zero positions in said integer pulse sequence based on said codeword

comparing a ratio of said number of non-zero position to a total number of positions in said integer pulse sequence to a bound;

selectively decoding said codeword using arithmetic coding or combinatorial coding based on an outcome of said comparing.

23. The method according to claim 22 further comprising:

using an FPC combinatorial function to generate an initial code space position for use in decoding said codeword using AC.