Data compression using variable-to-fixed length codes

Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C341S050000

Reexamination Certificate

active

07626522

ABSTRACT:
This disclosure is directed to techniques for memory efficient variable to fixed length (VF) coding techniques for a variety of applications, such as media coding. For example, such techniques may be applied to code digital video, image, audio, or speech data. The techniques described in this disclosure may utilize algebraic properties of VF coding trees constructed using Tunstall or Khodak algorithms, and employ combinatorial enumeration techniques for construction, encoding and decoding of codewords. For some applications, the VF coding techniques may be implemented within media encoders, decoders, or combined encoder-decoders (CODECs). Also, in some aspects, various attributes defining a VF coding tree constructed according to this disclosure may be provided in a memory efficient data structure stored in memory associated with a coding device.

REFERENCES:
patent: 5959560 (1999-09-01), Said et al.
patent: 6054943 (2000-04-01), Lawrence
patent: 6456209 (2002-09-01), Savari
Reznik et al. ,On the Average Redundancy Rate of Adaptive Block Codes under Mixed Sources, IEEE Data Compression Conference, 2003: Mar. 25-27, 2003 p. 447.
Ryabko et al., Fast Codes for Large Alphabet Sources and Its Application to Block Encoding, IEEE International Symposium on Information Theory, Jun. 29-Jul. 4, 2003, p. 112.
Reznik et al., Inproved Behaviour of Tries by the “Symmetrization” of the Source, 2002 IEEE Data Compression Conference, pp. 372-381.
Tjalkens et al., Variable-to-fixed length codes: a geometrical approach to low-complexity source codes, IEEE Data Compression Conference, Mar. 2000, p. 573.
Cover, “Enumerative source encoding”, IEEE Trans. Inf. Theory vol. 19 Issue: 1 Date: Jan. 1973, pp. 73-77.
Cover, “Element of Information Theory”, John Wiley & Sons, New York, 1991.
Drmota, et al, “Precise Asymptotic Analysis of the Tunstall Code”, IEEE International Symposium on Information Theory (ISIT06), Seattle WA, Jul. 9-14, 2006 pp. 2334-2337.
Jelinek, et al, “On variable-length-to-block coding”. IEEE Transactions on Information Theory, vol. 18, Issue 6, Nov. 1972, pp. 765-774.
Mudrov, Am algorithm for enumeration of combinations, Vyc. Math. and Math. Phys., 5 (4) (1965) 776-778 280-282.
Savari, et al. “Generalized Tunstall Codes for Sources with Memory”, IEEE Trans. Info. Theory, vol. IT-43, pp. 658-668, Mar. 1997.
Savari, “Variable-to-Fixed Length Codes for Predictable Sources”, Proc IEEE Data Compression Conference, Snowbird, UT, Mar. 30-Apr. 1, 1998 pp. 481-490.
Schalkwijk, “An Algorithm for Source Coding”, IEEE Trans. Inf. Theory, 18 (3) (1972). pp. 395-399.
Tjalkens et al, “Variable to Fixed-Length Codes for Markov Sources”, IEEE Trans Inf. Theory, IT-33, 246-257, 1987.
Tjalkens et al, “The Complexity of Minimum Redundancy Coding”, Proc. 21-th Symp. Inf. Theory in the Benelux (May 2000), pp. 247-254, only one page in IFW.
Tjalkens et al, “Implementation Cost of the Huffman-Shnnon-Fano Code”, Proc. Data Compression Conference (DCC'05), Snowbird, Utah, Mar. 29-31, 2005, pp. 123-132.
Thomas Wiegand, Gary Sullivan, Julien Reichel, Heiko Schwartz and Mathias Wien, “Joint Draft 6: Scalable Video Coding,” JVT-S 201, Apr. 2006.
Thomas Wiegand, Gary Sullivan, Julien Reichei, Heiko Schwartz and Mathias Wien, “Joint Draft 9 of SVC Amendment,” JVT-V 201, Jan. 2007, Marrakech Morocco.
TIA-1099, “Forward Link Only Air Interface Specification for Terrestrial Mobile Multimedia Multicast,” Mar. 2007.
ITU-T H.264, Series H: Audiovisual and Multimedia Systems Infrastructure of audiovisual services—Coding of moving video, “Advanced video coding for generic audiovisual services,” Nov. 2007: 7.3.5.3 Residual Data Syntax; and 9.2 CAVLC parsing process for transform coefficient levels.
Babkin, A Universal Encoding Method with Nonexponential Work Expenditure or a Source of Independent Messages UDC 621.391.15 (Translated from Problemy Peredachi Inf. vol. 7, No. 4., pp. 13-21 Oct. Dec, 1971 (Apr. 10, 1970).
Khodak, G. L., “Redundancy Estimates for the Literal Encoding of Messages Generated by a Bernoulli Source”, UDC 621,391.15, Translated from Problemy Peredach Informatsli, vol. 8., No. 2 pp. 21-32 Apr. Jun. 1972 (rev, Dec. 22, 1971).
Mudrov “An algorithm for numbering combinations,” Vyc. Math. and Math. Phys., 5 (4) (1965) 776-778.
R. E. Krichevsky, Universal Data Compression and Retrieval. (Kluwer Norwell, MA, 1993). Chapter 2.1 (Types of Codes) - pp. 27-33, and Chapters 3.1-3.4 - pp. 74-91.
Algra, T.: “Fast and Efficient Variable-to-Fixed-Length Coding Algorithm,” Electronics Letters, IEE Stevenage, GB, vol. 28, No. 15 (Jul. 16, 1992) pp. 1399-1401, XP000307687, ISSN: 0013-5194.
Reznik, Y.: “Memory-Efficient Decoding of Variable Length Codes for Monotonic Sources,” Data Compression Conference, 2007. DCC '07, IEEE, PI (Mar. 1, 2007) p. 398, XP031073840, ISBN: 978-0-7695-2791-8.
Tjalkens, T. J. et al.: “A Universal Variable-to-Fixed Length Source Code Based on Lawrence's Algorithm,” IEEE Transactions on Information Theory USA, vol. 38, No. 2 (Mar. 1992) pp. 247-253, XP002502684, ISSN: 0018-9448.
Xie, Y. et al.: “Code Compression for VLIW Processors Using Variable-to-Fixed Coding,” 15th International Symposium on System Synthesis. ISSS. Kyoto, Japan,'Oct. 2-4, 2002 [International Symposium on System Synthesis ISSS].New York, NY: ACM, US (Oct. 2, 2002) pp. 138-143. XP010655202, ISBN: 978-1-58113-576-3.
International Search Report. PCT/US2008/056225 - International Search Authority - European Patent Office, Dec. 12, 2008.
Written Opinion, PCT/US2008/056225 - International Search Authority - European Patent Office, Dec. 12, 2008.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Data compression using variable-to-fixed length codes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data compression using variable-to-fixed length codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression using variable-to-fixed length codes will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-4116746

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.