Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2007-10-08
2009-12-01
Williams, Howard (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
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.
Qualcomm Incorporated
Thiel Steven R.
Williams Howard
LandOfFree
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.
Profile ID: LFUS-PAI-O-4116746