350 rub
Journal Achievements of Modern Radioelectronics №5 for 2016 г.
Article in number:
Method of building code trees for adaptive interleaving entropy coder
Authors:
K.R. Mudrak - Engineer, LTD «Special Technological Center» (St. Petersburg). E-mail: zzzmurdoczzz@bk.ru
Abstract:
In modern condition of information theory, only a few coders can compress a set of information from unknown source with unknown en-tropy to the state-of-art. Mostly because those coders works with set of alphabets with more than two symbols. This technique works well when coder knows every probability of incoming symbols in information message. However, when message is I.I.D, these type of coders have to make at least two passes through message to form an alphabet. By using an extremely small alphabet of single bits «0» and «1», and by using some technique of estimating probability that next bit arriving is «0», one can build a state-of-art coder. As known only two methods can be used to design such coder. One of them is arithmetic coder and the other one is adaptive interleaving entropy coder. While the complexity of arithmetic coder is very high, adaptive interleaving entropy coder can achieve redundancy as small, as designer wants. Main parts of that coder are codes, used to code input sequence and produce output bits with probability of zero value closer to 0,5, than source bits. By complexing this method with useful trees, described in this paper bits from any source with any proba-bility of zero can be compressed to theoretical limit.
Pages: 41-46
References
- William A. Pearlman, Amir Said Digital Signal Compression: Principles and Practice 2011. P. 41-76.
- JAglom A.M., JAglom I.M. Verojatnost i informacija. M.: Nauka. 1973.
- Sehlomon D. Szhatie dannykh, izobrazhenija i zvuka. M.: Tekhnosfera. 2004.
- Vorobev N.N. CHisla Fibonachchi. M.: Nauka. 1978. T. 39.
- Golomb S.W. Run-length encodings // IEEE Trans. Inf. Theory. 1966. № 3. IT-12. P. 399-401.
- Howard P.G., Vitter J.S. Arithmetic Coding for Data Compression // Proc. IEEE. June 1994.V. 82. № 6. P. 857-865.
- Bottou L., Howard P.G., Bengio Y. The Z-Coder Adaptive Binary Coder // Proc. IEEE Data Compression Conference. Snowbird. Utah. March 1998. P. 13-22.
- Howard P.G. Interleaving Entropy Codes // Proc. Compression and Complexity of Sequences 1997. Salerno. Italy. P. 45-55.
- Shannon C.E. A mathematical theory of communication. 1948.
- Kiely A.B., Klimesh M. A New Entropy Coding Technique for Data Compression // The InterPlanetary Network Progress Report 42‑146. April-June 2001. Jet Propulsion Laboratory. Pasadena. California. P. 1-48.
- Kiely A.B. Bit-Wise Arithmetic Coding for Data Compression // The Telecommunications and Data Acquisition Progress Report 42‑117. January-March 1994. Jet Propulsion Laboratory. Pasadena. California. P. 145-160.