DocumentCode :
3334717
Title :
The use of asymmetric numeral systems as an accurate replacement for Huffman coding
Author :
Duda, Jarek ; Tahboub, Khalid ; Gadgil, Neeraj J. ; Delp, Edward J.
Author_Institution :
Inst. of Comput. Sci. & Comput. Math., Jagiellonian Univ., Cracow, Poland
fYear :
2015
fDate :
May 31 2015-June 3 2015
Firstpage :
65
Lastpage :
69
Abstract :
Entropy coding is an integral part of most data compression systems. Huffman coding (HC) and arithmetic coding (AC) are two of the most widely used coding methods. HC can process a large symbol alphabet at each step allowing for fast encoding and decoding. However, HC typically provides suboptimal data rates due to its inherent approximation of symbol probabilities to powers of 1 over 2. In contrast, AC uses nearly accurate symbol probabilities, hence generally providing better compression ratios. However, AC relies on relatively slow arithmetic operations making the implementation computationally demanding. In this paper we discuss asymmetric numeral systems (ANS) as a new approach to entropy coding. While maintaining theoretical connections with AC, the proposed ANS-based coding can be implemented with much less computational complexity. While AC operates on a state defined by two numbers specifying a range, an ANS-based coder operates on a state defined by a single natural number such that the x ∈ ℕ state contains ≈ log2(x) bits of information. This property allows to have the entire behavior for a large alphabet summarized in the form of a relatively small table (e.g. a few kilobytes for a 256 size alphabet). The proposed approach can be interpreted as an equivalent to adding fractional bits to a Huffman coder to combine the speed of HC and the accuracy offered by AC. Additionally, ANS can simultaneously encrypt a message encoded this way. Experimental results demonstrate effectiveness of the proposed entropy coder.
Keywords :
Huffman codes; arithmetic codes; computational complexity; data compression; entropy; Huffman coding; arithmetic coding; asymmetric numeral systems; computational complexity; data compression systems; entropy coding; symbol probabilities; Channel coding; Decoding; Entropy; Huffman coding; Probability distribution; Standards; Huffman coding; arithmetic coding; asymmetric numeral systems; data compression; entropy coding;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Picture Coding Symposium (PCS), 2015
Conference_Location :
Cairns, QLD
Type :
conf
DOI :
10.1109/PCS.2015.7170048
Filename :
7170048
Link To Document :
بازگشت