Complexity analysis of adaptive binary arithmetic coding software implementations

Evgeny Belyaev; Anton Veselov; Andrey Turlikov; Kai Liu

doi:10.1007/978-3-642-22875-9_54

Complexity analysis of adaptive binary arithmetic coding software implementations

Evgeny Belyaev, Anton Veselov, Andrey Turlikov, Kai Liu

Research output: Contribution to journal › Article › Scientific › peer-review

9 Citations (Scopus)

64 Downloads (Pure)

Abstract

This paper is dedicated to the complexity comparison of adaptive binary arithmetic coding integer software implementations. Firstly, for binary memoryless sources with known probability distribution, we prove that encoding time for arithmetic encoder is a linear function of a number of input binary symbols and source entropy. Secondly, we show that the byte-oriented renormalization allows to decrease encoding time up to 40% in comparison with bit-oriented renormalization. Finally, we study inﬂuence of probability estimation algorithm for encoding time and show that probability estimation algorithm using “Virtual Sliding Window“ has less computation complexity than state machine based probability estimation algorithm from H.264/AVC standard.

Translated title of the contribution	Complexity analysis of adaptive binary arithmetic coding software implementations
Original language	English
Pages (from-to)	598-607
Journal	Lecture Notes in Computer Science
Volume	6869
DOIs	https://doi.org/10.1007/978-3-642-22875-9_54
Publication status	Published - 2011
Publication type	A1 Journal article-refereed

Publication forum classification

Publication forum level 1

Access to Document

10.1007/978-3-642-22875-9_54

Belyaev complexity analysis of adaptive
The final publication is available at http://www.springerlink.com/content/3844j92q052g3g07/.

http://urn.fi/URN:NBN:fi:tty-2011092914825

Cite this

@article{47da3592ecde49f7935df708089feb1b,

title = "Complexity analysis of adaptive binary arithmetic coding software implementations",

abstract = "This paper is dedicated to the complexity comparison of adaptive binary arithmetic coding integer software implementations. Firstly, for binary memoryless sources with known probability distribution, we prove that encoding time for arithmetic encoder is a linear function of a number of input binary symbols and source entropy. Secondly, we show that the byte-oriented renormalization allows to decrease encoding time up to 40% in comparison with bit-oriented renormalization. Finally, we study inﬂuence of probability estimation algorithm for encoding time and show that probability estimation algorithm using “Virtual Sliding Window“ has less computation complexity than state machine based probability estimation algorithm from H.264/AVC standard.",

author = "Evgeny Belyaev and Anton Veselov and Andrey Turlikov and Kai Liu",

note = "ei ut-numeroa 9.11.2013<br/>Contribution: organisation=sgn,FACT1=1",

year = "2011",

doi = "10.1007/978-3-642-22875-9_54",

language = "English",

volume = "6869",

pages = "598--607",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - Complexity analysis of adaptive binary arithmetic coding software implementations

AU - Belyaev, Evgeny

AU - Veselov, Anton

AU - Turlikov, Andrey

AU - Liu, Kai

N1 - ei ut-numeroa 9.11.2013<br/>Contribution: organisation=sgn,FACT1=1

PY - 2011

Y1 - 2011

N2 - This paper is dedicated to the complexity comparison of adaptive binary arithmetic coding integer software implementations. Firstly, for binary memoryless sources with known probability distribution, we prove that encoding time for arithmetic encoder is a linear function of a number of input binary symbols and source entropy. Secondly, we show that the byte-oriented renormalization allows to decrease encoding time up to 40% in comparison with bit-oriented renormalization. Finally, we study inﬂuence of probability estimation algorithm for encoding time and show that probability estimation algorithm using “Virtual Sliding Window“ has less computation complexity than state machine based probability estimation algorithm from H.264/AVC standard.

AB - This paper is dedicated to the complexity comparison of adaptive binary arithmetic coding integer software implementations. Firstly, for binary memoryless sources with known probability distribution, we prove that encoding time for arithmetic encoder is a linear function of a number of input binary symbols and source entropy. Secondly, we show that the byte-oriented renormalization allows to decrease encoding time up to 40% in comparison with bit-oriented renormalization. Finally, we study inﬂuence of probability estimation algorithm for encoding time and show that probability estimation algorithm using “Virtual Sliding Window“ has less computation complexity than state machine based probability estimation algorithm from H.264/AVC standard.

U2 - 10.1007/978-3-642-22875-9_54

DO - 10.1007/978-3-642-22875-9_54

M3 - Article

SN - 0302-9743

VL - 6869

SP - 598

EP - 607

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

ER -

Complexity analysis of adaptive binary arithmetic coding software implementations

Abstract

Publication forum classification

Access to Document

Fingerprint

Cite this