Granted Patent B1

US 7,199,735 · App. 11/271,252 · Granted Apr 3, 2007

Abstract

Claims (65)

1. A method for performing entropy coding comprising the steps of:

receiving an input stream and side information;

analyzing said side information to determine all constraints associated with said side information;

replacing said input stream with an index to a list of a number of valid input streams that satisfy all constraints associated with each specific type of said side information; and

generating said list of the number of valid input streams that satisfy all constraints associated with each specific type of side information based on an amount of redundancy in a system.

2. The method according to claim 1 , wherein said input stream comprises one or more types of streams selected from a group consisting of bit streams, streams of symbols and numeric data streams.

3. The method according to claim 2 , wherein said side information comprises one or more parameters selected from a group consisting of a length of the bit streams in bits and a number of symbols contained in a received packet.

4. The method according to claim 3 , wherein said length of the bit streams in bits comprises a number of bits of a coded representation when said input stream is encoded using either variable length coding or adaptive coding.

5. The method according to claim 3 , wherein the length of the bit streams in bits is (i) communicated via a side channel, (ii) communicated through an individually encoded representation for length as overhead, or (iii) represented as part of an entropy coded combination of length and index information.

6. The method according to claim 1 , further comprising the step of entropy coding said index.

7. The method according to claim 1 , wherein said list is generated offline.

8. The method according to claim 1 , further comprising the steps of:

organizing the list of the number of valid input streams that satisfy all constraints in lexicographical order; and

identifying said index for said input stream via a predetermined recursive process.

9. The method according to claim 8 , wherein the predetermined recursive process comprises the steps of:

(A) setting said index to zero;

(B) determining a total length corresponding to a code word sequence that would have had to be transmitted or stored in a predetermined conventional system;

(C) incrementing said index by a value determined by the number of valid code word sequences from said predetermined conventional system starting with a current first code word and having a length equal to said total length less a length of said current first code word; and

(D) removing the current first code word from the sequence; and

(E) repeating the steps (C) and (D) until all code words in the sequence are processed.

10. The method according to claim 1 , wherein said side information comprises syntactic and semantic constraints.

11. The method according to claim 1 , further comprising the step of:

storing said list in a look-up table as a function of all specific types of side information.

12. The method according to claim 1 , further comprising the steps of:

organizing said list in lexicographical order; and

identifying each of a plurality of input streams with an input index.

13. The method according to claim 12 , wherein said input streams comprise one or more types of coded representations selected from a group consisting of variable length codes (VLCs), fixed length codes (FLC), arithmetic coded (AC) bit streams, adaptive AC bit streams and adaptive VLC streams.

14. The method according to claim 12 , wherein the step of identifying each input stream with said input index comprises the steps of:

determining the number of valid input streams of a predetermined length that start with a first code word or input symbol based upon the number of valid sequences of code words or input symbols having a length equal to said predetermined length minus a length of said first code word or input symbol; and

determining the number of the valid code word or input symbol sequences that begin with code words or input symbols smaller than a second code word or input symbol based upon a sum of the number of valid code word or input symbol sequences of said predetermined length that start with said first code word or input symbol for all first code words or input symbols smaller than said second code word or input symbol in lexicographical order.

15. The method according to claim 14 , further comprising the steps of:

determining the first code word or input symbol in the sequence of code words or input symbols associated with said input index by comparing said input index with the number of valid code word or input symbol sequences of said predetermined length that start with each code word or input symbol in a table of all code words or input symbols, wherein said first code word or input symbol in said sequence is determined as the smallest code word or input symbol such that said input index is less than the number of valid code word or input symbol sequences of said predetermined length that start with a code word or input symbol that is smaller than said first code word or input symbol;

removing said first code word or input symbol from the sequence of code words or input symbols associated with said input index by decreasing the predetermined length by the length of said first code word or input symbol and decreasing the input index by the number of valid code word or input symbol sequences of said predetermined length that start with the largest code word or input symbol in the table that is smaller than the first code word or input symbol just determined in lexicographical order; and

determining the remaining code words or input symbols in the sequence associated with the input index by repeating the above steps until the predetermined length is decreased to zero.

16. The method according to claim 1 , further comprising the step of:

generating conditional tables based upon each specific set of constraints and conditions.

17. The method according to claim 1 , wherein each input stream comprises multiple individual bit or symbol streams.

18. The method according to claim 1 , wherein an overall index for all valid input streams satisfying a variety set of conditions is constructed and entropy coded with static or adaptive variable length codes or arithmetic codes.

19. The method according to claim 1 , wherein said list of the number of valid input streams that satisfy all constraints associated with each specific type of said side information is generated by mapping a code book or a dictionary of input symbols to a polynomial function.

20. The method according to claim 1 , wherein said list of the number of valid input streams that satisfy all constraints associated with each specific type of said side information further comprises a number of code words or input symbols in each input stream that satisfies all constraints associated with each specific type of said side information.

21. A computer readable medium comprising instructions for performing the method according to claim 1 .

22. The computer readable medium according to claim 21 , further comprising instructions for generating said list of the number of valid input streams that satisfy all constraints associated with each specific type of said side information.

23. A method for performing entropy coding comprising the steps of:

receiving an input stream and side information;

analyzing said side information to determine all constraints associated with said side information; and

replacing said input stream with an index to a list of a number of valid input streams that satisfy all constraints associated with each specific type of said side information, wherein (i) said input stream comprises one or more types of streams selected from the group consisting of bit streams, streams of symbols and numeric data streams and (ii) said side information comprises one or more parameters selected from the group consisting of a length of the bit streams in bits and a number of symbols contained in a received packet.

24. A method for performing entropy coding comprising the steps of:

receiving an input stream and side information;

analyzing said side information to determine all constraints associated with said side information;

replacing said input stream with an index to a list of a number of valid input streams that satisfy all constraints associated with each specific type of said side information;

organizing said list in lexicographical order; and

identifying each of a plurality of input streams with an input index.

25. A method for performing entropy coding comprising the steps of:

receiving an input stream and side information;

analyzing said side information to determine all constraints associated with said side information;

replacing said input stream with an index to a list of a number of valid input streams that satisfy all constraints associated with each specific type of said side information; and

generating conditional tables based upon each specific set of constraints and conditions.

26. A method for performing entropy coding comprising the steps of:

receiving an input stream and side information;

analyzing said side information to determine all constraints associated with said side information; and

replacing said input stream with an index to a list of a number of valid input streams that satisfy all constraints associated with each specific type of said side information, wherein said list of the number of valid input streams that satisfy all constraints associated with each specific type of said side information is generated by mapping a code book or a dictionary of input symbols to a polynomial function.

27. A method for performing entropy coding comprising the steps of:

receiving an input stream and side information;

analyzing said side information to determine all constraints associated with said side information; and

replacing said input stream with an index to a list of a number of valid input streams that satisfy all constraints associated with each specific type of said side information, wherein said list of the number of valid input streams that satisfy all constraints associated with each specific type of said side information further comprises a number of code words or input symbols in each input stream that satisfies all constraints associated with each specific type of said side information.

Assignments (11)