CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Arithmetic coding - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"0cdd2482-df98-4c1f-be44-209bb2aa8776","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Arithmetic_coding","wgTitle":"Arithmetic coding","wgCurRevisionId":1268711433,"wgRevisionId":1268711433,"wgArticleId":62545,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Use dmy dates from December 2019","Articles lacking in-text citations from September 2016","All articles lacking in-text citations","Webarchive template wayback links","Entropy coding","Data compression"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Arithmetic_coding","wgRelevantArticleId":62545,"wgIsProbablyEditable":true, "wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":40000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q2651","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false, "wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.math.popup","mediawiki.page.media","ext.scribunto.logs","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar", "ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.16"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Arithmetic_coding_example.svg/1200px-Arithmetic_coding_example.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="849"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Arithmetic_coding_example.svg/800px-Arithmetic_coding_example.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="566"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Arithmetic_coding_example.svg/640px-Arithmetic_coding_example.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="453"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Arithmetic coding - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Arithmetic_coding"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Arithmetic_coding&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Arithmetic_coding"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Arithmetic_coding rootpage-Arithmetic_coding skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Main menu" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Arithmetic+coding" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Arithmetic+coding" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Arithmetic+coding" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Arithmetic+coding" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Implementation_details_and_examples" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Implementation_details_and_examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Implementation details and examples</span> </div> </a> <button aria-controls="toc-Implementation_details_and_examples-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Implementation details and examples subsection</span> </button> <ul id="toc-Implementation_details_and_examples-sublist" class="vector-toc-list"> <li id="toc-Equal_probabilities" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Equal_probabilities"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>Equal probabilities</span> </div> </a> <ul id="toc-Equal_probabilities-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Defining_a_model" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Defining_a_model"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2</span> <span>Defining a model</span> </div> </a> <ul id="toc-Defining_a_model-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Encoding_and_decoding:_overview" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Encoding_and_decoding:_overview"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.3</span> <span>Encoding and decoding: overview</span> </div> </a> <ul id="toc-Encoding_and_decoding:_overview-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Encoding_and_decoding:_example" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Encoding_and_decoding:_example"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.4</span> <span>Encoding and decoding: example</span> </div> </a> <ul id="toc-Encoding_and_decoding:_example-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Sources_of_inefficiency" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Sources_of_inefficiency"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.5</span> <span>Sources of inefficiency</span> </div> </a> <ul id="toc-Sources_of_inefficiency-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Adaptive_arithmetic_coding" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Adaptive_arithmetic_coding"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Adaptive arithmetic coding</span> </div> </a> <ul id="toc-Adaptive_arithmetic_coding-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Precision_and_renormalization" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Precision_and_renormalization"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Precision and renormalization</span> </div> </a> <ul id="toc-Precision_and_renormalization-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Arithmetic_coding_as_a_generalized_change_of_radix" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Arithmetic_coding_as_a_generalized_change_of_radix"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Arithmetic coding as a generalized change of radix</span> </div> </a> <button aria-controls="toc-Arithmetic_coding_as_a_generalized_change_of_radix-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Arithmetic coding as a generalized change of radix subsection</span> </button> <ul id="toc-Arithmetic_coding_as_a_generalized_change_of_radix-sublist" class="vector-toc-list"> <li id="toc-Theoretical_limit_of_compressed_message" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Theoretical_limit_of_compressed_message"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Theoretical limit of compressed message</span> </div> </a> <ul id="toc-Theoretical_limit_of_compressed_message-sublist" class="vector-toc-list"> <li id="toc-Asymptotic_equipartition" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Asymptotic_equipartition"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.1</span> <span>Asymptotic equipartition</span> </div> </a> <ul id="toc-Asymptotic_equipartition-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-Connections_with_other_compression_methods" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Connections_with_other_compression_methods"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Connections with other compression methods</span> </div> </a> <button aria-controls="toc-Connections_with_other_compression_methods-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Connections with other compression methods subsection</span> </button> <ul id="toc-Connections_with_other_compression_methods-sublist" class="vector-toc-list"> <li id="toc-Huffman_coding" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Huffman_coding"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Huffman coding</span> </div> </a> <ul id="toc-Huffman_coding-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-History_and_patents" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#History_and_patents"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>History and patents</span> </div> </a> <ul id="toc-History_and_patents-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Benchmarks_and_other_technical_characteristics" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Benchmarks_and_other_technical_characteristics"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Benchmarks and other technical characteristics</span> </div> </a> <ul id="toc-Benchmarks_and_other_technical_characteristics-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">11</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table of Contents" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Arithmetic coding</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 14 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-14" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">14 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Aritmetick%C3%A9_k%C3%B3dov%C3%A1n%C3%AD" title="Aritmetické kódování – Czech" lang="cs" hreflang="cs" data-title="Aritmetické kódování" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Arithmetisches_Kodieren" title="Arithmetisches Kodieren – German" lang="de" hreflang="de" data-title="Arithmetisches Kodieren" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Codificaci%C3%B3n_aritm%C3%A9tica" title="Codificación aritmética – Spanish" lang="es" hreflang="es" data-title="Codificación aritmética" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%DA%A9%D8%AF%DA%AF%D8%B0%D8%A7%D8%B1%DB%8C_%D8%AD%D8%B3%D8%A7%D8%A8%DB%8C" title="کدگذاری حسابی – Persian" lang="fa" hreflang="fa" data-title="کدگذاری حسابی" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Codage_arithm%C3%A9tique" title="Codage arithmétique – French" lang="fr" hreflang="fr" data-title="Codage arithmétique" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%82%B0%EC%88%A0_%EB%B6%80%ED%98%B8%ED%99%94" title="산술 부호화 – Korean" lang="ko" hreflang="ko" data-title="산술 부호화" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Codifica_aritmetica" title="Codifica aritmetica – Italian" lang="it" hreflang="it" data-title="Codifica aritmetica" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Aritmetische_codering" title="Aritmetische codering – Dutch" lang="nl" hreflang="nl" data-title="Aritmetische codering" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E7%AE%97%E8%A1%93%E7%AC%A6%E5%8F%B7" title="算術符号 – Japanese" lang="ja" hreflang="ja" data-title="算術符号" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Kodowanie_arytmetyczne" title="Kodowanie arytmetyczne – Polish" lang="pl" hreflang="pl" data-title="Kodowanie arytmetyczne" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Codifica%C3%A7%C3%A3o_aritm%C3%A9tica" title="Codificação aritmética – Portuguese" lang="pt" hreflang="pt" data-title="Codificação aritmética" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5" title="Арифметическое кодирование – Russian" lang="ru" hreflang="ru" data-title="Арифметическое кодирование" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%BD%D0%B5_%D0%BA%D0%BE%D0%B4%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F" title="Арифметичне кодування – Ukrainian" lang="uk" hreflang="uk" data-title="Арифметичне кодування" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E7%AE%97%E6%9C%AF%E7%BC%96%E7%A0%81" title="算术编码 – Chinese" lang="zh" hreflang="zh" data-title="算术编码" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q2651#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Arithmetic_coding" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Arithmetic_coding" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Arithmetic_coding"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Arithmetic_coding&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Arithmetic_coding&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Arithmetic_coding"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Arithmetic_coding&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Arithmetic_coding&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Arithmetic_coding" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Arithmetic_coding" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Arithmetic_coding&oldid=1268711433" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Arithmetic_coding&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Arithmetic_coding&id=1268711433&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FArithmetic_coding"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FArithmetic_coding"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Arithmetic_coding&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Arithmetic_coding&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Arithmetic_coding" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q2651" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Form of entropy encoding used in data compression</div> <p class="mw-empty-elt"> </p> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-More_footnotes_needed plainlinks metadata ambox ambox-style ambox-More_footnotes_needed" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Text_document_with_red_question_mark.svg/40px-Text_document_with_red_question_mark.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Text_document_with_red_question_mark.svg/60px-Text_document_with_red_question_mark.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Text_document_with_red_question_mark.svg/80px-Text_document_with_red_question_mark.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article includes a list of <a href="/wiki/Wikipedia:Citing_sources#General_references" title="Wikipedia:Citing sources">general references</a>, but <b>it lacks sufficient corresponding <a href="/wiki/Wikipedia:Citing_sources#Inline_citations" title="Wikipedia:Citing sources">inline citations</a></b>.<span class="hide-when-compact"> Please help to <a href="/wiki/Wikipedia:WikiProject_Reliability" title="Wikipedia:WikiProject Reliability">improve</a> this article by <a href="/wiki/Wikipedia:When_to_cite" title="Wikipedia:When to cite">introducing</a> more precise citations.</span> <span class="date-container"><i>(<span class="date">September 2016</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p><b>Arithmetic coding</b> (<b>AC</b>) is a form of <a href="/wiki/Entropy_encoding" class="mw-redirect" title="Entropy encoding">entropy encoding</a> used in <a href="/wiki/Lossless_data_compression" class="mw-redirect" title="Lossless data compression">lossless data compression</a>. Normally, a <a href="/wiki/String_(computer_science)" title="String (computer science)">string of characters</a> is represented using a fixed number of <a href="/wiki/Bit" title="Bit">bits</a> per character, as in the <a href="/wiki/American_Standard_Code_for_Information_Interchange" class="mw-redirect" title="American Standard Code for Information Interchange">ASCII</a> code. When a string is converted to arithmetic encoding, frequently used characters will be stored with fewer bits and not-so-frequently occurring characters will be stored with more bits, resulting in fewer bits used in total. Arithmetic coding differs from other forms of entropy encoding, such as <a href="/wiki/Huffman_coding" title="Huffman coding">Huffman coding</a>, in that rather than separating the input into component symbols and replacing each with a code, arithmetic coding encodes the entire message into a single number, an <a href="/wiki/Arbitrary-precision_arithmetic" title="Arbitrary-precision arithmetic">arbitrary-precision</a> fraction <i>q</i>, where <span class="nowrap">0.0 ≤ <i>q</i> < 1.0</span>. It represents the current information as a range, defined by two numbers.<sup id="cite_ref-LiDrew2014_1-0" class="reference"><a href="#cite_note-LiDrew2014-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> A recent family of entropy coders called <a href="/wiki/Asymmetric_numeral_systems" title="Asymmetric numeral systems">asymmetric numeral systems</a> allows for faster implementations thanks to directly operating on a single natural number representing the current information.<sup id="cite_ref-PCS2015_2-0" class="reference"><a href="#cite_note-PCS2015-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Arithmetic_coding_example.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/8/82/Arithmetic_coding_example.svg/400px-Arithmetic_coding_example.svg.png" decoding="async" width="400" height="283" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/8/82/Arithmetic_coding_example.svg/600px-Arithmetic_coding_example.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/8/82/Arithmetic_coding_example.svg/800px-Arithmetic_coding_example.svg.png 2x" data-file-width="1052" data-file-height="744" /></a><figcaption>An arithmetic coding example assuming a fixed probability distribution of three symbols "A", "B", and "C". Probability of "A" is 50%, probability of "B" is 33% and probability of "C" is 17%. Furthermore, we assume that the recursion depth is known in each step. In step one we code "B" which is inside the interval [0.5, 0.83): The binary number "0.10<i>x</i>" is the shortest code that represents an interval that is entirely inside [0.5, 0.83). "<i>x</i>" means an arbitrary bit sequence. There are two extreme cases: the smallest <i>x</i> stands for zero which represents the left side of the represented interval. Then the left side of the interval is dec(0.10) = 0.5. At the other extreme, <i>x</i> stands for a finite sequence of ones which has the upper limit dec(0.11) = 0.75. Therefore, "0.10<i>x</i>" represents the interval [0.5, 0.75) which is inside [0.5, 0.83). Now we can leave out the "0." part since all intervals begin with "0." and we can ignore the "<i>x</i>" part because no matter what bit-sequence it represents, we will stay inside [0.5, 0.75).</figcaption></figure> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Implementation_details_and_examples">Implementation details and examples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=1" title="Edit section: Implementation details and examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Arithmetic_coding_visualisation.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/3/3a/Arithmetic_coding_visualisation.svg/300px-Arithmetic_coding_visualisation.svg.png" decoding="async" width="300" height="450" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/3a/Arithmetic_coding_visualisation.svg/450px-Arithmetic_coding_visualisation.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/3a/Arithmetic_coding_visualisation.svg/600px-Arithmetic_coding_visualisation.svg.png 2x" data-file-width="512" data-file-height="768" /></a><figcaption>Encoding the message "WIKI" with arithmetic coding <table> <tbody><tr> <th style="text-align:right; vertical-align:top;">1. </th> <td>The letter frequencies are found. </td></tr> <tr> <th style="text-align:right; vertical-align:top;">2. </th> <td>The interval [0, 1) is partitioned in the ratio of the frequencies. </td></tr> <tr> <th style="text-align:right; vertical-align:top;">3–5. </th> <td>The corresponding interval is iteratively partitioned for each letter in the message. </td></tr> <tr> <th style="text-align:right; vertical-align:top;">6. </th> <td>Any value in the final interval is chosen to represent the message. </td></tr> <tr> <th style="text-align:right; vertical-align:top;">2*–6*. </th> <td>The partitioning and value if the message were "KIWI" instead. </td></tr></tbody></table> </figcaption></figure> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Arithmetic_coding_visualisation_circle.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/8/81/Arithmetic_coding_visualisation_circle.svg/300px-Arithmetic_coding_visualisation_circle.svg.png" decoding="async" width="300" height="300" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/8/81/Arithmetic_coding_visualisation_circle.svg/450px-Arithmetic_coding_visualisation_circle.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/8/81/Arithmetic_coding_visualisation_circle.svg/600px-Arithmetic_coding_visualisation_circle.svg.png 2x" data-file-width="512" data-file-height="512" /></a><figcaption>The above example visualised as a circle, the values in red encoding "WIKI" and "KIWI" – in <a class="external text" href="https://upload.wikimedia.org/wikipedia/commons/8/81/Arithmetic_coding_visualisation_circle.svg">the SVG image</a>, hover over an interval to highlight it and show its statistics</figcaption></figure> <div class="mw-heading mw-heading3"><h3 id="Equal_probabilities">Equal probabilities</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=2" title="Edit section: Equal probabilities"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the simplest case, the probability of each symbol occurring is equal. For example, consider a set of three symbols, A, B, and C, each equally likely to occur. Encoding the symbols one by one would require 2 bits per symbol, which is wasteful: one of the bit variations is never used. That is to say, symbols A, B and C might be encoded respectively as 00, 01 and 10, with 11 unused. </p><p>A more efficient solution is to represent a sequence of these three symbols as a rational number in base 3 where each digit represents a symbol. For example, the sequence "ABBCAB" could become 0.011201<sub>3</sub>, in arithmetic coding as a value in the interval [0, 1). The next step is to encode this <a href="/wiki/Ternary_numeral_system" title="Ternary numeral system">ternary</a> number using a fixed-point binary number of sufficient precision to recover it, such as 0.0010110001<sub>2</sub> – this is only 10 bits; 2 bits are saved in comparison with naïve block encoding. This is feasible for long sequences because there are efficient, in-place algorithms for converting the base of arbitrarily precise numbers. </p><p>To decode the value, knowing the original string had length 6, one can simply convert back to base 3, round to 6 digits, and recover the string. </p> <div class="mw-heading mw-heading3"><h3 id="Defining_a_model">Defining a model</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=3" title="Edit section: Defining a model"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In general, arithmetic coders can produce near-optimal output for any given set of symbols and probabilities. (The optimal value is −log<sub>2</sub><i>P</i> bits for each symbol of probability <i>P</i>; see <i><a href="/wiki/Source_coding_theorem" class="mw-redirect" title="Source coding theorem">Source coding theorem</a></i>.) Compression algorithms that use arithmetic coding start by determining a <a href="/wiki/Model_(abstract)" class="mw-redirect" title="Model (abstract)">model</a> of the data – basically a prediction of what patterns will be found in the symbols of the message. The more accurate this prediction is, the closer to optimal the output will be. </p><p><b>Example</b>: a simple, static model for describing the output of a particular monitoring instrument over time might be: </p> <ul><li>60% chance of symbol NEUTRAL</li> <li>20% chance of symbol POSITIVE</li> <li>10% chance of symbol NEGATIVE</li> <li>10% chance of symbol END-OF-DATA. <i>(The presence of this symbol means that the stream will be 'internally terminated', as is fairly common in data compression; when this symbol appears in the data stream, the decoder will know that the entire stream has been decoded.)</i></li></ul> <p>Models can also handle alphabets other than the simple four-symbol set chosen for this example. More sophisticated models are also possible: <i>higher-order</i> modelling changes its estimation of the current probability of a symbol based on the symbols that precede it (the <i>context</i>), so that in a model for English text, for example, the percentage chance of "u" would be much higher when it follows a "Q" or a "q". Models can even be <i><a href="/wiki/Adaptive_coding" title="Adaptive coding">adaptive</a></i>, so that they continually change their prediction of the data based on what the stream actually contains. The decoder must have the same model as the encoder. </p> <div class="mw-heading mw-heading3"><h3 id="Encoding_and_decoding:_overview">Encoding and decoding: overview</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=4" title="Edit section: Encoding and decoding: overview"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In general, each step of the encoding process, except for the last, is the same; the encoder has basically just three pieces of data to consider: </p> <ul><li>The next symbol that needs to be encoded</li> <li>The current <a href="/wiki/Interval_(mathematics)" title="Interval (mathematics)">interval</a> (at the very start of the encoding process, the interval is set to [0,1], but that will change)</li> <li>The probabilities the model assigns to each of the various symbols that are possible at this stage (as mentioned earlier, higher-order or adaptive models mean that these probabilities are not necessarily the same in each step.)</li></ul> <p>The encoder divides the current interval into sub-intervals, each representing a fraction of the current interval proportional to the probability of that symbol in the current context. Whichever interval corresponds to the actual symbol that is next to be encoded becomes the interval used in the next step. </p><p><b>Example</b>: for the four-symbol model above: </p> <ul><li>the interval for NEUTRAL would be [0, 0.6)</li> <li>the interval for POSITIVE would be [0.6, 0.8)</li> <li>the interval for NEGATIVE would be [0.8, 0.9)</li> <li>the interval for END-OF-DATA would be [0.9, 1).</li></ul> <p>When all symbols have been encoded, the resulting interval unambiguously identifies the sequence of symbols that produced it. Anyone who has the same final interval and model that is being used can reconstruct the symbol sequence that must have entered the encoder to result in that final interval. </p><p>It is not necessary to transmit the final interval, however; it is only necessary to transmit <i>one fraction</i> that lies within that interval. In particular, it is only necessary to transmit enough digits (in whatever base) of the fraction so that all fractions that begin with those digits fall into the final interval; this will guarantee that the resulting code is a <a href="/wiki/Prefix_code" title="Prefix code">prefix code</a>. </p> <div class="mw-heading mw-heading3"><h3 id="Encoding_and_decoding:_example">Encoding and decoding: example</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=5" title="Edit section: Encoding and decoding: example"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Arithmetic_encoding.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Arithmetic_encoding.svg/400px-Arithmetic_encoding.svg.png" decoding="async" width="400" height="200" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Arithmetic_encoding.svg/600px-Arithmetic_encoding.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Arithmetic_encoding.svg/800px-Arithmetic_encoding.svg.png 2x" data-file-width="1100" data-file-height="550" /></a><figcaption>A diagram showing decoding of 0.538 (the round dot) in the example model. The region is divided into subregions proportional to symbol frequencies, then the subregion containing the point is successively subdivided in the same way.</figcaption></figure> <p>Consider the process for decoding a message encoded with the given four-symbol model. The message is encoded in the fraction 0.538 (using decimal for clarity, instead of binary; also assuming that there are only as many digits as needed to decode the message.) </p><p>The process starts with the same interval used by the encoder: [0,1), and using the same model, dividing it into the same four sub-intervals that the encoder must have. The fraction 0.538 falls into the sub-interval for NEUTRAL, [0, 0.6); this indicates that the first symbol the encoder read must have been NEUTRAL, so this is the first symbol of the message. </p><p>Next divide the interval [0, 0.6) into sub-intervals: </p> <ul><li>the interval for NEUTRAL would be [0, 0.36), <i>60% of [0, 0.6)</i>.</li> <li>the interval for POSITIVE would be [0.36, 0.48), <i>20% of [0, 0.6)</i>.</li> <li>the interval for NEGATIVE would be [0.48, 0.54), <i>10% of [0, 0.6)</i>.</li> <li>the interval for END-OF-DATA would be [0.54, 0.6), <i>10% of [0, 0.6)</i>.</li></ul> <p>Since 0.538 is within the interval [0.48, 0.54), the second symbol of the message must have been NEGATIVE. </p><p>Again divide our current interval into sub-intervals: </p> <ul><li>the interval for NEUTRAL would be [0.48, 0.516).</li> <li>the interval for POSITIVE would be [0.516, 0.528).</li> <li>the interval for NEGATIVE would be [0.528, 0.534).</li> <li>the interval for END-OF-DATA would be [0.534, 0.540).</li></ul> <p>Now 0.538 falls within the interval of the END-OF-DATA symbol; therefore, this must be the next symbol. Since it is also the internal termination symbol, it means the decoding is complete. If the stream is not internally terminated, there needs to be some other way to indicate where the stream stops. Otherwise, the decoding process could continue forever, mistakenly reading more symbols from the fraction than were in fact encoded into it. </p> <div class="mw-heading mw-heading3"><h3 id="Sources_of_inefficiency">Sources of inefficiency</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=6" title="Edit section: Sources of inefficiency"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The message 0.538 in the previous example could have been encoded by the equally short fractions 0.534, 0.535, 0.536, 0.537 or 0.539. This suggests that the use of decimal instead of binary introduced some inefficiency. This is correct; the information content of a three-digit decimal is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3\times \log _{2}(10)\approx 9.966}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>3</mn> <mo>×</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <mn>10</mn> <mo stretchy="false">)</mo> <mo>≈</mo> <mn>9.966</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 3\times \log _{2}(10)\approx 9.966}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5d4780a23f462bb1e772155685b1da606ee2667a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.558ex; height:2.843ex;" alt="{\displaystyle 3\times \log _{2}(10)\approx 9.966}"></span> <a href="/wiki/Bit" title="Bit">bits</a>; the same message could have been encoded in the binary fraction 0.10001001 (equivalent to 0.53515625 decimal) at a cost of only 8bits. </p><p>This 8 bit output is larger than the information content, or <a href="/wiki/Information_entropy" class="mw-redirect" title="Information entropy">entropy</a>, of the message, which is </p> <dl><dd><span class="mwe-math-element" data-qid="Q2651"><a href="/w/index.php?title=Special:MathWikibase&qid=Q2651" style="color:inherit;"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum -\log _{2}(p_{i})=-\log _{2}(0.6)-\log _{2}(0.1)-\log _{2}(0.1)=7.381{\text{ bits}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>∑</mo> <mo>−</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mo>−</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <mn>0.6</mn> <mo stretchy="false">)</mo> <mo>−</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <mn>0.1</mn> <mo stretchy="false">)</mo> <mo>−</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <mn>0.1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>7.381</mn> <mrow class="MJX-TeXAtom-ORD"> <mtext> bits</mtext> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \sum -\log _{2}(p_{i})=-\log _{2}(0.6)-\log _{2}(0.1)-\log _{2}(0.1)=7.381{\text{ bits}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4e964177a2eb4c866dc4fa7ad94657825ac5fbab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:64.52ex; height:3.843ex;" alt="{\displaystyle \sum -\log _{2}(p_{i})=-\log _{2}(0.6)-\log _{2}(0.1)-\log _{2}(0.1)=7.381{\text{ bits}}.}"></a></span></dd></dl> <p>But an integer number of bits must be used in the binary encoding, so an encoder for this message would use at least 8 bits, resulting in a message 8.4% larger than the entropy contents. This inefficiency of at most 1 bit results in relatively less overhead as the message size grows. </p><p>Moreover, the claimed symbol probabilities were [0.6, 0.2, 0.1, 0.1), but the actual frequencies in this example are [0.33, 0, 0.33, 0.33). If the intervals are readjusted for these frequencies, the entropy of the message would be 4.755 bits and the same NEUTRAL NEGATIVE END-OF-DATA message could be encoded as intervals [0, 1/3); [1/9, 2/9); [5/27, 6/27); and a binary interval of [0.00101111011, 0.00111000111). This is also an example of how statistical coding methods like arithmetic encoding can produce an output message that is larger than the input message, especially if the probability model is off. </p> <div class="mw-heading mw-heading2"><h2 id="Adaptive_arithmetic_coding">Adaptive arithmetic coding</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=7" title="Edit section: Adaptive arithmetic coding"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/Context-adaptive_binary_arithmetic_coding" title="Context-adaptive binary arithmetic coding">Context-adaptive binary arithmetic coding</a></div> <p>One advantage of arithmetic coding over other similar methods of data compression is the convenience of adaptation. <i>Adaptation</i> is the changing of the frequency (or probability) tables while processing the data. The decoded data matches the original data as long as the frequency table in decoding is replaced in the same way and in the same step as in encoding. The synchronization is, usually, based on a combination of symbols occurring during the encoding and decoding process. </p> <div class="mw-heading mw-heading2"><h2 id="Precision_and_renormalization">Precision and renormalization</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=8" title="Edit section: Precision and renormalization"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The above explanations of arithmetic coding contain some simplification. In particular, they are written as if the encoder first calculated the fractions representing the endpoints of the interval in full, using infinite <a href="/wiki/Precision_(arithmetic)" class="mw-redirect" title="Precision (arithmetic)">precision</a>, and only converted the fraction to its final form at the end of encoding. Rather than try to simulate infinite precision, most arithmetic coders instead operate at a fixed limit of precision which they know the decoder will be able to match, and round the calculated fractions to their nearest equivalents at that precision. An example shows how this would work if the model called for the interval <span class="texhtml">[0,1)</span> to be divided into thirds, and this was approximated with 8 bit precision. Note that since now the precision is known, so are the binary ranges we'll be able to use. </p> <table class="wikitable"> <tbody><tr> <th rowspan="2">Symbol </th> <th>Probability </th> <th colspan="2">Interval reduced to eight-bit precision </th> <th>Range </th></tr> <tr> <th>(expressed as fraction) </th> <th>(as fractions) </th> <th>(in binary) </th> <th>(in binary) </th></tr> <tr align="center"> <td>A </td> <td>1/3 </td> <td><span class="texhtml">[0, 85/256)</span> </td> <td><span style="font-family:monospace">[0.00000000, 0.01010101)</span> </td> <td><span style="font-family:monospace">00000000 – 01010100</span> </td></tr> <tr align="center"> <td>B </td> <td>1/3 </td> <td><span class="texhtml">[85/256, 171/256)</span> </td> <td><span style="font-family:monospace">[0.01010101, 0.10101011)</span> </td> <td><span style="font-family:monospace">01010101 – 10101010</span> </td></tr> <tr align="center"> <td>C </td> <td>1/3 </td> <td><span class="texhtml">[171/256, 1)</span> </td> <td><span style="font-family:monospace">[0.10101011, 1.00000000)</span> </td> <td><span style="font-family:monospace">10101011 – 11111111</span> </td></tr></tbody></table> <p>A process called <i>renormalization</i> keeps the finite precision from becoming a limit on the total number of symbols that can be encoded. Whenever the range is reduced to the point where all values in the range share certain beginning digits, those digits are sent to the output. For however many digits of precision the computer <i>can</i> handle, it is now handling fewer than that, so the existing digits are shifted left, and at the right, new digits are added to expand the range as widely as possible. Note that this result occurs in two of the three cases from our previous example. </p> <table class="wikitable"> <tbody><tr> <th>Symbol </th> <th>Probability </th> <th>Range </th> <th>Digits that can be sent to output </th> <th>Range after renormalization </th></tr> <tr align="center"> <td>A </td> <td>1/3 </td> <td><style data-mw-deduplicate="TemplateStyles:r886049734">.mw-parser-output .monospaced{font-family:monospace,monospace}</style><span class="monospaced"><b>0</b>0000000 – <b>0</b>1010100</span> </td> <td><b>0</b> </td> <td><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">0000000<b>0</b> – 1010100<b>1</b></span> </td></tr> <tr align="center"> <td>B </td> <td>1/3 </td> <td><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">01010101 – 10101010</span> </td> <td style="background: #EEE; color:black; vertical-align: middle; text-align: center;" class="table-cast">None </td> <td><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">01010101 – 10101010</span> </td></tr> <tr align="center"> <td>C </td> <td>1/3 </td> <td><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced"><b>1</b>0101011 – <b>1</b>1111111</span> </td> <td><b>1</b> </td> <td><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">0101011<b>0</b> – 1111111<b>1</b></span> </td></tr></tbody></table> <div class="mw-heading mw-heading2"><h2 id="Arithmetic_coding_as_a_generalized_change_of_radix">Arithmetic coding as a generalized change of radix</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=9" title="Edit section: Arithmetic coding as a generalized change of radix"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Recall that in the case where the symbols had equal probabilities, arithmetic coding could be implemented by a simple change of base, or radix. In general, arithmetic (and range) coding may be interpreted as a <i>generalized</i> change of <a href="/wiki/Radix" title="Radix">radix</a>. For example, we may look at any sequence of symbols: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {DABDDB} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">D</mi> <mi mathvariant="normal">A</mi> <mi mathvariant="normal">B</mi> <mi mathvariant="normal">D</mi> <mi mathvariant="normal">D</mi> <mi mathvariant="normal">B</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {DABDDB} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/55c50556506a64671c10b519c1b2bc589d587ae6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.361ex; height:2.176ex;" alt="{\displaystyle \mathrm {DABDDB} }"></span></dd></dl> <p>as a number in a certain base presuming that the involved symbols form an ordered set and each symbol in the ordered set denotes a sequential integer A = 0, B = 1, C = 2, D = 3, and so on. This results in the following frequencies and cumulative frequencies: </p> <table class="wikitable" style="text-align:center;"> <tbody><tr> <th>Symbol </th> <th>Frequency of occurrence </th> <th>Cumulative frequency </th></tr> <tr> <td>A </td> <td>1 </td> <td>0 </td></tr> <tr> <td>B </td> <td>2 </td> <td>1 </td></tr> <tr> <td>D </td> <td>3 </td> <td>3 </td></tr></tbody></table> <p>The <i>cumulative frequency</i> for an item is the sum of all frequencies preceding the item. In other words, cumulative frequency is a running total of frequencies. </p><p>In a positional <a href="/wiki/Numeral_system" title="Numeral system">numeral system</a> the radix, or base, is numerically equal to a number of different symbols used to express the number. For example, in the decimal system the number of symbols is 10, namely 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The radix is used to express any finite integer in a presumed multiplier in polynomial form. For example, the number 457 is actually 4×10<sup>2</sup> + 5×10<sup>1</sup> + 7×10<sup>0</sup>, where base 10 is presumed but not shown explicitly. </p><p>Initially, we will convert DABDDB into a base-6 numeral, because 6 is the length of the string. The string is first mapped into the digit string 301331, which then maps to an integer by the polynomial: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 6^{5}\times 3+6^{4}\times 0+6^{3}\times 1+6^{2}\times 3+6^{1}\times 3+6^{0}\times 1=23671}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>6</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msup> <mo>×</mo> <mn>3</mn> <mo>+</mo> <msup> <mn>6</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msup> <mo>×</mo> <mn>0</mn> <mo>+</mo> <msup> <mn>6</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msup> <mo>×</mo> <mn>1</mn> <mo>+</mo> <msup> <mn>6</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>×</mo> <mn>3</mn> <mo>+</mo> <msup> <mn>6</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>×</mo> <mn>3</mn> <mo>+</mo> <msup> <mn>6</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> <mo>×</mo> <mn>1</mn> <mo>=</mo> <mn>23671</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 6^{5}\times 3+6^{4}\times 0+6^{3}\times 1+6^{2}\times 3+6^{1}\times 3+6^{0}\times 1=23671}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eabc310011f9755b943c4b0d13786db42e7e1d8c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:60.43ex; height:2.843ex;" alt="{\displaystyle 6^{5}\times 3+6^{4}\times 0+6^{3}\times 1+6^{2}\times 3+6^{1}\times 3+6^{0}\times 1=23671}"></span></dd></dl> <p>The result 23671 has a length of 15 bits, which is not very close to the theoretical limit (the <a href="/wiki/Entropy_(information_theory)" title="Entropy (information theory)">entropy</a> of the message), which is approximately 9 bits. </p><p>To encode a message with a length closer to the theoretical limit imposed by information theory we need to slightly generalize the classic formula for changing the radix. We will compute lower and upper bounds <i>L</i> and <i>U</i> and choose a number between them. For the computation of <i>L</i> we multiply each term in the above expression by the product of the frequencies of all previously occurred symbols: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}L={}&(6^{5}\times 3)+{}\\&3\times (6^{4}\times 0)+{}\\&(3\times 1)\times (6^{3}\times 1)+{}\\&(3\times 1\times 2)\times (6^{2}\times 3)+{}\\&(3\times 1\times 2\times 3)\times (6^{1}\times 3)+{}\\&(3\times 1\times 2\times 3\times 3)\times (6^{0}\times 1){}\\={}&25002\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <mi>L</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> </mrow> </mtd> <mtd> <mi></mi> <mo stretchy="false">(</mo> <msup> <mn>6</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msup> <mo>×</mo> <mn>3</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mn>3</mn> <mo>×</mo> <mo stretchy="false">(</mo> <msup> <mn>6</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msup> <mo>×</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo stretchy="false">(</mo> <mn>3</mn> <mo>×</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>×</mo> <mo stretchy="false">(</mo> <msup> <mn>6</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msup> <mo>×</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo stretchy="false">(</mo> <mn>3</mn> <mo>×</mo> <mn>1</mn> <mo>×</mo> <mn>2</mn> <mo stretchy="false">)</mo> <mo>×</mo> <mo stretchy="false">(</mo> <msup> <mn>6</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>×</mo> <mn>3</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo stretchy="false">(</mo> <mn>3</mn> <mo>×</mo> <mn>1</mn> <mo>×</mo> <mn>2</mn> <mo>×</mo> <mn>3</mn> <mo stretchy="false">)</mo> <mo>×</mo> <mo stretchy="false">(</mo> <msup> <mn>6</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>×</mo> <mn>3</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo stretchy="false">(</mo> <mn>3</mn> <mo>×</mo> <mn>1</mn> <mo>×</mo> <mn>2</mn> <mo>×</mo> <mn>3</mn> <mo>×</mo> <mn>3</mn> <mo stretchy="false">)</mo> <mo>×</mo> <mo stretchy="false">(</mo> <msup> <mn>6</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> <mo>×</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> </mrow> </mtd> </mtr> <mtr> <mtd> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> </mrow> </mtd> <mtd> <mn>25002</mn> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}L={}&(6^{5}\times 3)+{}\\&3\times (6^{4}\times 0)+{}\\&(3\times 1)\times (6^{3}\times 1)+{}\\&(3\times 1\times 2)\times (6^{2}\times 3)+{}\\&(3\times 1\times 2\times 3)\times (6^{1}\times 3)+{}\\&(3\times 1\times 2\times 3\times 3)\times (6^{0}\times 1){}\\={}&25002\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5ece1bb92ee15232219757b8086a9e2b60cdb3d9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -10.838ex; width:35.285ex; height:22.843ex;" alt="{\displaystyle {\begin{aligned}L={}&(6^{5}\times 3)+{}\\&3\times (6^{4}\times 0)+{}\\&(3\times 1)\times (6^{3}\times 1)+{}\\&(3\times 1\times 2)\times (6^{2}\times 3)+{}\\&(3\times 1\times 2\times 3)\times (6^{1}\times 3)+{}\\&(3\times 1\times 2\times 3\times 3)\times (6^{0}\times 1){}\\={}&25002\end{aligned}}}"></span></dd></dl> <p>The difference between this polynomial and the polynomial above is that each term is multiplied by the product of the frequencies of all previously occurring symbols. More generally, <i>L</i> may be computed as: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L=\sum _{i=1}^{n}n^{n-i}C_{i}{\prod _{k=1}^{i-1}f_{k}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </munderover> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mi>i</mi> </mrow> </msup> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <munderover> <mo>∏</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L=\sum _{i=1}^{n}n^{n-i}C_{i}{\prod _{k=1}^{i-1}f_{k}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/370b599be53a683cafbb02c1c47812e877a0d751" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:20.929ex; height:7.343ex;" alt="{\displaystyle L=\sum _{i=1}^{n}n^{n-i}C_{i}{\prod _{k=1}^{i-1}f_{k}}}"></span></dd></dl> <p>where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle C_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle C_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/df705c5dd9cb12e0fa51e784ac1295910e45c0ef" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.8ex; height:1.843ex;" alt="{\displaystyle \scriptstyle C_{i}}"></span> are the cumulative frequencies and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle f_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle f_{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dad0521e664a790a89126a7e4329b75921ae7df5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.665ex; height:2.009ex;" alt="{\displaystyle \scriptstyle f_{k}}"></span> are the frequencies of occurrences. Indexes denote the position of the symbol in a message. In the special case where all frequencies <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle f_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle f_{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dad0521e664a790a89126a7e4329b75921ae7df5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.665ex; height:2.009ex;" alt="{\displaystyle \scriptstyle f_{k}}"></span> are 1, this is the change-of-base formula. </p><p>The upper bound <i>U</i> will be <i>L</i> plus the product of all frequencies; in this case <i>U</i> = <i>L</i> + (3 × 1 × 2 × 3 × 3 × 2) = 25002 + 108 = 25110. In general, <i>U</i> is given by: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U=L+\prod _{k=1}^{n}f_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>U</mi> <mo>=</mo> <mi>L</mi> <mo>+</mo> <munderover> <mo>∏</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U=L+\prod _{k=1}^{n}f_{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3678e026bad963eab9da89b3b9cfdb92a99c009c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:14.889ex; height:6.843ex;" alt="{\displaystyle U=L+\prod _{k=1}^{n}f_{k}}"></span></dd></dl> <p>Now we can choose any number from the interval [<i>L</i>, <i>U</i>) to represent the message; one convenient choice is the value with the longest possible trail of zeroes, 25100, since it allows us to achieve compression by representing the result as 251×10<sup>2</sup>. The zeroes can also be truncated, giving 251, if the length of the message is stored separately. Longer messages will tend to have longer trails of zeroes. </p><p>To decode the integer 25100, the polynomial computation can be reversed as shown in the table below. At each stage the current symbol is identified, then the corresponding term is subtracted from the result. </p> <table class="wikitable" style="text-align:center;"> <tbody><tr> <th>Remainder </th> <th>Identification </th> <th>Identified symbol </th> <th>Corrected remainder </th></tr> <tr> <td>25100 </td> <td style="text-align:right;">25100 / 6<sup>5</sup> = 3 </td> <td>D </td> <td style="text-align:right;">(25100 − 6<sup>5</sup> × 3) / 3 = 590 </td></tr> <tr> <td>590 </td> <td style="text-align:right;">590 / 6<sup>4</sup> = 0 </td> <td>A </td> <td style="text-align:right;">(590 − 6<sup>4</sup> × 0) / 1 = 590 </td></tr> <tr> <td>590 </td> <td style="text-align:right;">590 / 6<sup>3</sup> = 2 </td> <td>B </td> <td style="text-align:right;">(590 − 6<sup>3</sup> × 1) / 2 = 187 </td></tr> <tr> <td>187 </td> <td style="text-align:right;">187 / 6<sup>2</sup> = 5 </td> <td>D </td> <td style="text-align:right;">(187 − 6<sup>2</sup> × 3) / 3 = 26<span class="nowrap"> </span> </td></tr> <tr> <td>26 </td> <td style="text-align:right;">26 / 6<sup>1</sup> = 4 </td> <td>D </td> <td style="text-align:right;">(26 − 6<sup>1</sup> × 3) / 3 = 2<span class="nowrap"> </span><span class="nowrap"> </span> </td></tr> <tr> <td>2 </td> <td style="text-align:right;">2 / 6<sup>0</sup> = 2 </td> <td>B </td> <td>— </td></tr></tbody></table> <p>During decoding we take the floor after dividing by the corresponding power of 6. The result is then matched against the cumulative intervals and the appropriate symbol is selected from look up table. When the symbol is identified the result is corrected. The process is continued for the known length of the message or while the remaining result is positive. The only difference compared to the classical change-of-base is that there may be a range of values associated with each symbol. In this example, A is always 0, B is either 1 or 2, and D is any of 3, 4, 5. This is in exact accordance with our intervals that are determined by the frequencies. When all intervals are equal to 1 we have a special case of the classic base change. </p> <div class="mw-heading mw-heading3"><h3 id="Theoretical_limit_of_compressed_message">Theoretical limit of compressed message</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=10" title="Edit section: Theoretical limit of compressed message"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The lower bound <i>L</i> never exceeds <i>n</i><sup><i>n</i></sup>, where <i>n</i> is the size of the message, and so can be represented in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}(n^{n})=n\log _{2}(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo stretchy="false">)</mo> <mo>=</mo> <mi>n</mi> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \log _{2}(n^{n})=n\log _{2}(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a875558c1f90184f068a338b755402aaf220e4d5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.559ex; height:2.843ex;" alt="{\displaystyle \log _{2}(n^{n})=n\log _{2}(n)}"></span> bits. After the computation of the upper bound <i>U</i> and the reduction of the message by selecting a number from the interval [<i>L</i>, <i>U</i>) with the longest trail of zeros we can presume that this length can be reduced by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle \log _{2}\left(\prod _{k=1}^{n}f_{k}\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="0"> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mrow> <mo>(</mo> <mrow> <munderover> <mo>∏</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mrow> <mo>)</mo> </mrow> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \textstyle \log _{2}\left(\prod _{k=1}^{n}f_{k}\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/828c8bce8f36a625a9c2ba34d3e3696038426e3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.833ex; height:3.176ex;" alt="{\displaystyle \textstyle \log _{2}\left(\prod _{k=1}^{n}f_{k}\right)}"></span> bits. Since each frequency in a product occurs exactly the same number of times as the value of this frequency, we can use the size of the alphabet <i>A</i> for the computation of the product </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \prod _{k=1}^{n}f_{k}=\prod _{k=1}^{A}f_{k}^{f_{k}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <munderover> <mo>∏</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <mo>=</mo> <munderover> <mo>∏</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>A</mi> </mrow> </munderover> <msubsup> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mrow> </msubsup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \prod _{k=1}^{n}f_{k}=\prod _{k=1}^{A}f_{k}^{f_{k}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/25c4063d2bdb77d7516d57323c0bdc0516985c20" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:15.904ex; height:7.343ex;" alt="{\displaystyle \prod _{k=1}^{n}f_{k}=\prod _{k=1}^{A}f_{k}^{f_{k}}.}"></span></dd></dl> <p>Applying log<sub>2</sub> for the estimated number of bits in the message, the final message (not counting a logarithmic overhead for the message length and frequency tables) will match the number of bits given by <a href="/wiki/Entropy_(information_theory)" title="Entropy (information theory)">entropy</a>, which for long messages is very close to optimal: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -\left[\sum _{i=1}^{A}f_{i}\log _{2}(f_{i})\right]n=nH}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>−</mo> <mrow> <mo>[</mo> <mrow> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>A</mi> </mrow> </munderover> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> <mo>]</mo> </mrow> <mi>n</mi> <mo>=</mo> <mi>n</mi> <mi>H</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle -\left[\sum _{i=1}^{A}f_{i}\log _{2}(f_{i})\right]n=nH}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/804e17f0ea1b295f4ede317bfe6fbf0113372444" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:27.087ex; height:7.509ex;" alt="{\displaystyle -\left[\sum _{i=1}^{A}f_{i}\log _{2}(f_{i})\right]n=nH}"></span></dd></dl> <p>In other words, the efficiency of arithmetic encoding approaches the theoretical limit of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>H</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/75a9edddcca2f782014371f75dca39d7e13a9c1b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}"></span> bits per symbol, as the message length approaches infinity. </p> <div class="mw-heading mw-heading4"><h4 id="Asymptotic_equipartition">Asymptotic equipartition</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=11" title="Edit section: Asymptotic equipartition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>We can understand this intuitively. Suppose the source is ergodic, then it has the <a href="/wiki/Asymptotic_equipartition_property" title="Asymptotic equipartition property">asymptotic equipartition property</a> (AEP). By the AEP, after a long stream of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> symbols, the interval of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (0,1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (0,1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c79c6838e423c1ed3c7ea532a56dc9f9dae8290b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (0,1)}"></span> is almost partitioned into almost equally-sized intervals. </p><p>Technically, for any small <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon >0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ϵ</mi> <mo>></mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \epsilon >0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/568095ad3924314374a5ab68fae17343661f2a71" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.205ex; height:2.176ex;" alt="{\displaystyle \epsilon >0}"></span>, for all large enough <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>, there exists <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{nH(X)(1+O(\epsilon ))}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mi>H</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>O</mi> <mo stretchy="false">(</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{nH(X)(1+O(\epsilon ))}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6be17cda227aaa3c6781c3cf70e7279ff44f9e9e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.1ex; height:2.843ex;" alt="{\displaystyle 2^{nH(X)(1+O(\epsilon ))}}"></span> strings <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1:n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mo>:</mo> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{1:n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/22243edba296d9059dcd64505ca9252581a90ac9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.828ex; height:2.009ex;" alt="{\displaystyle x_{1:n}}"></span>, such that each string has almost equal probability <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Pr(x_{1:n})=2^{-nH(X)(1+O(\epsilon ))}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mi>r</mi> <mo stretchy="false">(</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mo>:</mo> <mi>n</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>n</mi> <mi>H</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>O</mi> <mo stretchy="false">(</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Pr(x_{1:n})=2^{-nH(X)(1+O(\epsilon ))}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9fb01be0d0a10b808b555d1a0ca2369477204402" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.908ex; height:3.343ex;" alt="{\displaystyle Pr(x_{1:n})=2^{-nH(X)(1+O(\epsilon ))}}"></span>, and their total probability is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-O(\epsilon )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>−</mo> <mi>O</mi> <mo stretchy="false">(</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1-O(\epsilon )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/28290757851a50223e00fd0315fd6de2a9fc3b65" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.53ex; height:2.843ex;" alt="{\displaystyle 1-O(\epsilon )}"></span>. </p><p>For any such string, it is arithmetically encoded by a binary string of length <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span>, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span> is the smallest <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span> such that there exists a fraction of form <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {?}{2^{k}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mo>?</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {?}{2^{k}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c06f788c993397e0be135ef41f57a0b467971b5d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:3.087ex; height:5.843ex;" alt="{\displaystyle {\frac {?}{2^{k}}}}"></span> in the interval for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1:n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mo>:</mo> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{1:n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/22243edba296d9059dcd64505ca9252581a90ac9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.828ex; height:2.009ex;" alt="{\displaystyle x_{1:n}}"></span>. Since the interval for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1:n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mo>:</mo> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{1:n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/22243edba296d9059dcd64505ca9252581a90ac9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.828ex; height:2.009ex;" alt="{\displaystyle x_{1:n}}"></span> has size <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{-nH(X)(1+O(\epsilon ))}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>n</mi> <mi>H</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>O</mi> <mo stretchy="false">(</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{-nH(X)(1+O(\epsilon ))}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/03194a94849a06562701c6657a0c9d53ee7bf7b6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.379ex; height:2.843ex;" alt="{\displaystyle 2^{-nH(X)(1+O(\epsilon ))}}"></span>, we should expect it to contain one fraction of form <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {?}{2^{k}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mo>?</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {?}{2^{k}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c06f788c993397e0be135ef41f57a0b467971b5d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:3.087ex; height:5.843ex;" alt="{\displaystyle {\frac {?}{2^{k}}}}"></span> when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=nH(X)(1+O(\epsilon ))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>=</mo> <mi>n</mi> <mi>H</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>O</mi> <mo stretchy="false">(</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k=nH(X)(1+O(\epsilon ))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f54c23146ef1b40db94e838b414dd7d191a16ea8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.896ex; height:2.843ex;" alt="{\displaystyle k=nH(X)(1+O(\epsilon ))}"></span>. </p><p>Thus, with high probability, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1:n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mo>:</mo> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{1:n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/22243edba296d9059dcd64505ca9252581a90ac9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.828ex; height:2.009ex;" alt="{\displaystyle x_{1:n}}"></span> can be arithmetically encoded with a binary string of length <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle nH(X)(1+O(\epsilon ))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mi>H</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>O</mi> <mo stretchy="false">(</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle nH(X)(1+O(\epsilon ))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f1a056e84413064e358f7eea3c3942a38d57c8e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.587ex; height:2.843ex;" alt="{\displaystyle nH(X)(1+O(\epsilon ))}"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Connections_with_other_compression_methods">Connections with other compression methods</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=12" title="Edit section: Connections with other compression methods"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Huffman_coding">Huffman coding</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=13" title="Edit section: Huffman coding"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Huffman_coding" title="Huffman coding">Huffman coding</a></div> <p>Because arithmetic coding doesn't compress one datum at a time, it can get arbitrarily close to entropy when compressing <a href="/wiki/Independent_and_identically_distributed_random_variables" title="Independent and identically distributed random variables">IID</a> strings. By contrast, using the extension of <a href="/wiki/Huffman_coding" title="Huffman coding">Huffman coding</a> (to strings) does not reach entropy unless all probabilities of alphabet symbols are powers of two, in which case both Huffman and arithmetic coding achieve entropy. </p><p>When naively Huffman coding binary strings, no compression is possible, even if entropy is low (e.g. ({0, 1}) has probabilities {0.95, 0.05}). Huffman encoding assigns 1 bit to each value, resulting in a code of the same length as the input. By contrast, arithmetic coding compresses bits well, approaching the optimal compression ratio of </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-[-0.95\log _{2}(0.95)+-0.05\log _{2}(0.05)]\approx 71.4\%.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>−</mo> <mo stretchy="false">[</mo> <mo>−</mo> <mn>0.95</mn> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <mn>0.95</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mo>−</mo> <mn>0.05</mn> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <mn>0.05</mn> <mo stretchy="false">)</mo> <mo stretchy="false">]</mo> <mo>≈</mo> <mn>71.4</mn> <mi mathvariant="normal">%</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1-[-0.95\log _{2}(0.95)+-0.05\log _{2}(0.05)]\approx 71.4\%.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6d67ecf0a07f6d1d6a34dc7730f5cfe74bc75e98" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:50.55ex; height:2.843ex;" alt="{\displaystyle 1-[-0.95\log _{2}(0.95)+-0.05\log _{2}(0.05)]\approx 71.4\%.}"></span></dd></dl> <p>One simple way to address Huffman coding's suboptimality is to concatenate symbols ("blocking") to form a new alphabet in which each new symbol represents a sequence of original symbols – in this case bits – from the original alphabet. In the above example, grouping sequences of three symbols before encoding would produce new "super-symbols" with the following frequencies: </p> <ul><li><samp style="padding-left:0.4em; padding-right:0.4em; color:var( --color-subtle, #666666);">000</samp>: 85.7%</li> <li><samp style="padding-left:0.4em; padding-right:0.4em; color:var( --color-subtle, #666666);">001</samp>, <samp style="padding-left:0.4em; padding-right:0.4em; color:var( --color-subtle, #666666);">010</samp>, <samp style="padding-left:0.4em; padding-right:0.4em; color:var( --color-subtle, #666666);">100</samp>: 4.5% each</li> <li><samp style="padding-left:0.4em; padding-right:0.4em; color:var( --color-subtle, #666666);">011</samp>, <samp style="padding-left:0.4em; padding-right:0.4em; color:var( --color-subtle, #666666);">101</samp>, <samp style="padding-left:0.4em; padding-right:0.4em; color:var( --color-subtle, #666666);">110</samp>: 0.24% each</li> <li><samp style="padding-left:0.4em; padding-right:0.4em; color:var( --color-subtle, #666666);">111</samp>: 0.0125%</li></ul> <p>With this grouping, Huffman coding averages 1.3 bits for every three symbols, or 0.433 bits per symbol, compared with one bit per symbol in the original encoding, i.e., <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 56.7\%}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>56.7</mn> <mi mathvariant="normal">%</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 56.7\%}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06adb85b86fefbc59396c0604358059e820324a1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.07ex; height:2.343ex;" alt="{\displaystyle 56.7\%}"></span> compression. Allowing arbitrarily large sequences gets arbitrarily close to entropy – just like arithmetic coding – but requires huge codes to do so, so is not as practical as arithmetic coding for this purpose. </p><p>An alternative is <a href="/wiki/Run-length_encoding" title="Run-length encoding">encoding run lengths</a> via Huffman-based <a href="/wiki/Golomb_coding" title="Golomb coding">Golomb-Rice codes</a>. Such an approach allows simpler and faster encoding/decoding than arithmetic coding or even Huffman coding, since the latter requires a table lookups. In the {0.95, 0.05} example, a Golomb-Rice code with a four-bit remainder achieves a compression ratio of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 71.1\%}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>71.1</mn> <mi mathvariant="normal">%</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 71.1\%}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0f4b0e574b7ca41182e827255f1ce83f4091c97e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.07ex; height:2.343ex;" alt="{\displaystyle 71.1\%}"></span>, far closer to optimum than using three-bit blocks. Golomb-Rice codes only apply to <a href="/wiki/Bernoulli_process" title="Bernoulli process">Bernoulli</a> inputs such as the one in this example, however, so it is not a substitute for blocking in all cases. </p> <div class="mw-heading mw-heading2"><h2 id="History_and_patents">History and patents</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=14" title="Edit section: History and patents"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Basic algorithms for arithmetic coding were developed independently by <a href="/wiki/Jorma_J._Rissanen" class="mw-redirect" title="Jorma J. Rissanen">Jorma J. Rissanen</a>, at <a href="/wiki/IBM_Research" title="IBM Research">IBM Research</a>, and by Richard C. Pasco, a Ph.D. student at <a href="/wiki/Stanford_University" title="Stanford University">Stanford University</a>; both were published in May 1976. Pasco cites a pre-publication draft of Rissanen's article and comments on the relationship between their works:<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <style data-mw-deduplicate="TemplateStyles:r1244412712">.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}</style><blockquote class="templatequote"><p> One algorithm of the family was developed independently by Rissanen [1976]. It shifts the code element to the most significant end of the accumulator, using a pointer obtained by addition and exponentiation. We shall now compare the alternatives in the three choices, and see that it is preferable to shift the code element rather than the accumulator, and to add code elements to the least significant end of the accumulator.</p></blockquote> <p>Less than a year after publication, IBM filed for a US <a href="/wiki/Patent" title="Patent">patent</a> on Rissanen's work. Pasco's work was not patented. </p><p>A variety of specific techniques for arithmetic coding have historically been covered by US patents, although various well-known methods have since passed into the public domain as the patents have expired. Techniques covered by patents may be essential for implementing the algorithms for arithmetic coding that are specified in some formal international standards. When this is the case, such patents are generally available for licensing under what is called "reasonable and non-discriminatory" (<a href="/wiki/Reasonable_and_non-discriminatory_licensing" title="Reasonable and non-discriminatory licensing">RAND</a>) licensing terms (at least as a matter of standards-committee policy). In some well-known instances, (including some involving IBM patents that have since expired), such licenses were available for free, and in other instances, licensing fees have been required. The availability of licenses under RAND terms does not necessarily satisfy everyone who might want to use the technology, as what may seem "reasonable" for a company preparing a proprietary commercial software product may seem much less reasonable for a <a href="/wiki/Free_software" title="Free software">free software</a> or <a href="/wiki/Open-source_software" title="Open-source software">open source</a> project. </p><p>At least one significant compression software program, <a href="/wiki/Bzip2" title="Bzip2">bzip2</a>, deliberately discontinued the use of arithmetic coding in favor of Huffman coding due to the perceived patent situation at the time. Also, encoders and decoders of the <a href="/wiki/JPEG" title="JPEG">JPEG</a> file format, which has options for both Huffman encoding and arithmetic coding, typically only support the Huffman encoding option, which was originally because of patent concerns; the result is that nearly all JPEG images in use today use Huffman encoding<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> although JPEG's arithmetic coding patents<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> have expired due to the age of the JPEG standard (the design of which was approximately completed by 1990).<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> <a href="/wiki/JPEG_XL" title="JPEG XL">JPEG XL</a>, as well as archivers like PackJPG, Brunsli and Lepton, that can losslessly convert Huffman encoded files to ones with arithmetic coding (or <a href="/wiki/Asymmetric_numeral_systems" title="Asymmetric numeral systems">asymmetric numeral systems</a> in case of JPEG XL), showing up to 25% size saving. </p><p>The JPEG <a href="/wiki/Image_compression" title="Image compression">image compression</a> format's arithmetic coding algorithm is based on the following cited patents (since expired).<sup id="cite_ref-t81_7-0" class="reference"><a href="#cite_note-t81-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </p> <ul><li><span><a rel="nofollow" class="external text" href="https://patents.google.com/patent/US4652856">U.S. patent 4,652,856</a></span> – (<a href="/wiki/IBM" title="IBM">IBM</a>) Filed 4 February 1986, granted 24 March 1987 – Kottappuram M. A. Mohiuddin, Jorma Johannes Rissanen – Multiplication-free multi-alphabet arithmetic code</li> <li><span><a rel="nofollow" class="external text" href="https://patents.google.com/patent/US4905297">U.S. patent 4,905,297</a></span> – (IBM) Filed 18 November 1988, granted 27 February 1990 – Glen George Langdon, Joan L. Mitchell, William B. Pennebaker, Jorma Johannes Rissanen – Arithmetic coding encoder and decoder system</li> <li><span><a rel="nofollow" class="external text" href="https://patents.google.com/patent/US4935882">U.S. patent 4,935,882</a></span> – (IBM) Filed 20 July 1988, granted 19 June 1990 – William B. Pennebaker, Joan L. Mitchell – Probability adaptation for arithmetic coders</li> <li><a rel="nofollow" class="external text" href="https://patents.google.com/patent/JPH02202267A/en">JP Patent 1021672</a> – (<a href="/wiki/Mitsubishi_Electric" title="Mitsubishi Electric">Mitsubishi</a>) Filed 21 January 1989, granted 10 August 1990 – Toshihiro Kimura, Shigenori Kino, Fumitaka Ono, Masayuki Yoshida – Coding system</li> <li><a rel="nofollow" class="external text" href="https://patents.google.com/patent/JPH0834434B2/en">JP Patent 2-46275</a> – (Mitsubishi) Filed 26 February 1990, granted 5 November 1991 – Fumitaka Ono, Tomohiro Kimura, Masayuki Yoshida, Shigenori Kino – Coding apparatus and coding method</li></ul> <p>Other patents (mostly also expired) related to arithmetic coding include the following. </p> <ul><li><span><a rel="nofollow" class="external text" href="https://patents.google.com/patent/US4122440">U.S. patent 4,122,440</a></span> – (IBM) Filed 4 March 1977, granted 24 October 1978 – Glen George Langdon, Jorma Johannes Rissanen – Method and means for arithmetic string coding</li> <li><span><a rel="nofollow" class="external text" href="https://patents.google.com/patent/US4286256">U.S. patent 4,286,256</a></span> – (IBM) Filed 28 November 1979, granted 25 August 1981 – Glen George Langdon, Jorma Johannes Rissanen – Method and means for arithmetic coding utilizing a reduced number of operations</li> <li><span><a rel="nofollow" class="external text" href="https://patents.google.com/patent/US4467317">U.S. patent 4,467,317</a></span> – (IBM) Filed 30 March 1981, granted 21 August 1984 – Glen George Langdon, Jorma Johannes Rissanen – High-speed arithmetic compression coding using concurrent value updating</li> <li><span><a rel="nofollow" class="external text" href="https://patents.google.com/patent/US4891643">U.S. patent 4,891,643</a></span> – (IBM) Filed 15 September 1986, granted 2 January 1990 – Joan L. Mitchell, William B. Pennebaker – Arithmetic coding data compression/de-compression by selectively employed, diverse arithmetic coding encoders and decoders</li> <li><a rel="nofollow" class="external text" href="https://patents.google.com/patent/JPS63281524A/en">JP Patent 11782787</a> – (<a href="/wiki/NEC" title="NEC">NEC</a>) Filed 13 May 1987, granted 18 November 1988 – Michio Shimada – Data compressing arithmetic encoding device</li> <li><a rel="nofollow" class="external text" href="https://patents.google.com/patent/JPS63314918A/en">JP Patent 15015487</a> – (<a href="/wiki/KDDI" title="KDDI">KDDI</a>) Filed 18 June 1987, granted 22 December 1988 – Shuichi Matsumoto, Masahiro Saito – System for preventing carrying propagation in arithmetic coding</li> <li><span><a rel="nofollow" class="external text" href="https://patents.google.com/patent/US4933883">U.S. patent 4,933,883</a></span> – (IBM) Filed 3 May 1988, granted 12 June 1990 – William B. Pennebaker, Joan L. Mitchell – Probability adaptation for arithmetic coders</li> <li><span><a rel="nofollow" class="external text" href="https://patents.google.com/patent/US4989000">U.S. patent 4,989,000</a></span> – (IBM) Filed 19 June 1989, granted 29 January 1991 – Dan S. Chevion, Ehud D. Karnin, Eugeniusz Walach – Data string compression using arithmetic encoding with simplified probability subinterval estimation</li> <li><span><a rel="nofollow" class="external text" href="https://patents.google.com/patent/US5099440">U.S. patent 5,099,440</a></span> – (IBM) Filed 5 January 1990, granted 24 March 1992 – William B. Pennebaker, Joan L. Mitchell – Probability adaptation for arithmetic coders</li> <li><span><a rel="nofollow" class="external text" href="https://patents.google.com/patent/US5272478">U.S. patent 5,272,478</a></span> – (<a href="/wiki/Ricoh" title="Ricoh">Ricoh</a>) Filed 17 August 1992, granted 21 December 1993 – James D. Allen – Method and apparatus for entropy coding</li></ul> <p>Note: This list is not exhaustive. See the following links for a list of more US patents.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> The <a href="/wiki/Dirac_(codec)" class="mw-redirect" title="Dirac (codec)">Dirac codec</a> uses arithmetic coding and is not patent pending.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </p><p>Patents on arithmetic coding may exist in other jurisdictions; see <a href="/wiki/Software_patent" title="Software patent">software patents</a> for a discussion of the patentability of software around the world. </p> <div class="mw-heading mw-heading2"><h2 id="Benchmarks_and_other_technical_characteristics">Benchmarks and other technical characteristics</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=15" title="Edit section: Benchmarks and other technical characteristics"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Every programmatic implementation of arithmetic encoding has a different compression ratio and performance. While compression ratios vary only a little (usually under 1%),<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> the code execution time can vary by a factor of 10. Choosing the right encoder from a list of publicly available encoders is not a simple task because performance and compression ratio depend also on the type of data, particularly on the size of the alphabet (number of different symbols). One of two particular encoders may have better performance for small alphabets while the other may show better performance for large alphabets. Most encoders have limitations on the size of the alphabet and many of them are specialized for alphabets of exactly two symbols (0 and 1). </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=16" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Asymmetric_numeral_systems" title="Asymmetric numeral systems">Asymmetric numeral systems</a></li> <li><a href="/wiki/Context-adaptive_binary_arithmetic_coding" title="Context-adaptive binary arithmetic coding">Context-adaptive binary arithmetic coding</a> (CABAC)</li> <li><a href="/wiki/Data_compression" title="Data compression">Data compression</a></li> <li><a href="/wiki/Entropy_encoding" class="mw-redirect" title="Entropy encoding">Entropy encoding</a></li> <li><a href="/wiki/Huffman_coding" title="Huffman coding">Huffman coding</a></li> <li><a href="/wiki/Range_encoding" class="mw-redirect" title="Range encoding">Range encoding</a></li> <li><a href="/wiki/Run-length_encoding" title="Run-length encoding">Run-length encoding</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=17" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-LiDrew2014-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-LiDrew2014_1-0">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFZe-Nian_LiMark_S._DrewJiangchuan_Liu2014" class="citation book cs1">Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 April 2014). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=R6vBBAAAQBAJ"><i>Fundamentals of Multimedia</i></a>. Springer Science & Business Media. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-319-05290-8" title="Special:BookSources/978-3-319-05290-8"><bdi>978-3-319-05290-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Fundamentals+of+Multimedia&rft.pub=Springer+Science+%26+Business+Media&rft.date=2014-04-09&rft.isbn=978-3-319-05290-8&rft.au=Ze-Nian+Li&rft.au=Mark+S.+Drew&rft.au=Jiangchuan+Liu&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DR6vBBAAAQBAJ&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></span> </li> <li id="cite_note-PCS2015-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-PCS2015_2-0">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/7170048/">J. Duda, K. Tahboub, N. J. Gadil, E. J. Delp, <i>The use of asymmetric numeral systems as an accurate replacement for Huffman coding</i></a>, Picture Coding Symposium, 2015.</span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPasco1976" class="citation thesis cs1">Pasco, Richard Clark (May 1976). <i>Source coding algorithms for fast data compression</i> (PhD). Stanford Univ. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.3377">10.1.1.121.3377</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Source+coding+algorithms+for+fast+data+compression&rft.inst=Stanford+Univ&rft.date=1976-05&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.121.3377%23id-name%3DCiteSeerX&rft.aulast=Pasco&rft.aufirst=Richard+Clark&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.faqs.org/faqs/compression-faq/part1/section-17.html">"What is JPEG?"</a>. <i>comp.compression Frequently Asked Questions (part 1/3)</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=comp.compression+Frequently+Asked+Questions+%28part+1%2F3%29&rft.atitle=What+is+JPEG%3F&rft_id=http%3A%2F%2Fwww.faqs.org%2Ffaqs%2Fcompression-faq%2Fpart1%2Fsection-17.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.itu.int/rec/T-REC-T.81-200401-I!Cor1/dologin.asp?lang=e&id=T-REC-T.81-200401-I!Cor1!PDF-E&type=items">"Recommendation T.81 (1992) Corrigendum 1 (01/04)"</a>. <i>Recommendation T.81 (1992)</i>. International Telecommunication Union. 9 November 2004<span class="reference-accessdate">. Retrieved <span class="nowrap">3 February</span> 2011</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Recommendation+T.81+%281992%29&rft.atitle=Recommendation+T.81+%281992%29+Corrigendum+1+%2801%2F04%29&rft.date=2004-11-09&rft_id=http%3A%2F%2Fwww.itu.int%2Frec%2FT-REC-T.81-200401-I%21Cor1%2Fdologin.asp%3Flang%3De%26id%3DT-REC-T.81-200401-I%21Cor1%21PDF-E%26type%3Ditems&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPennebakerMitchell1992" class="citation book cs1">Pennebaker, W. B.; Mitchell, J. L. (1992). <i>JPEG Still Image Data Compression Standard</i>. Kluwer Academic Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0442012721" title="Special:BookSources/0442012721"><bdi>0442012721</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=JPEG+Still+Image+Data+Compression+Standard&rft.pub=Kluwer+Academic+Press&rft.date=1992&rft.isbn=0442012721&rft.aulast=Pennebaker&rft.aufirst=W.+B.&rft.au=Mitchell%2C+J.+L.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></span> </li> <li id="cite_note-t81-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-t81_7-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.w3.org/Graphics/JPEG/itu-t81.pdf">"T.81 – DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES"</a> <span class="cs1-format">(PDF)</span>. <a href="/wiki/CCITT" class="mw-redirect" title="CCITT">CCITT</a>. September 1992<span class="reference-accessdate">. Retrieved <span class="nowrap">12 July</span> 2019</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=T.81+%E2%80%93+DIGITAL+COMPRESSION+AND+CODING+OF+CONTINUOUS-TONE+STILL+IMAGES+%E2%80%93+REQUIREMENTS+AND+GUIDELINES&rft.pub=CCITT&rft.date=1992-09&rft_id=https%3A%2F%2Fwww.w3.org%2FGraphics%2FJPEG%2Fitu-t81.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.faqs.org/faqs/compression-faq/part1/">"Frequently Asked Questions"</a>. <i>comp.compression</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=comp.compression&rft.atitle=Frequently+Asked+Questions&rft_id=http%3A%2F%2Fwww.faqs.org%2Ffaqs%2Fcompression-faq%2Fpart1%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://lwn.net/Articles/272520/">"Dirac video codec 1.0 released [LWN.net]"</a>. <i>lwn.net</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=lwn.net&rft.atitle=Dirac+video+codec+1.0+released+%5BLWN.net%5D&rft_id=https%3A%2F%2Flwn.net%2FArticles%2F272520%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text">For instance, <a href="#CITEREFHowardVitter1994">Howard & Vitter (1994)</a> discuss versions of arithmetic coding based on real-number ranges, integer approximations to those ranges, and an even more restricted type of approximation that they call binary quasi-arithmetic coding. They state that the difference between real and integer versions is negligible, prove that the compression loss for their quasi-arithmetic method can be made arbitrarily small, and bound the compression loss incurred by one of their approximations as less than 0.06%. See: <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHowardVitter1994" class="citation cs2">Howard, Paul G.; Vitter, Jeffrey S. (1994), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20131018025150/http://home.tiscali.nl/rajduim/Video%20Compression%20Docs/Arithmetic%20Coding%20For%20Data%20Compression%20(2).pdf">"Arithmetic coding for data compression"</a> <span class="cs1-format">(PDF)</span>, <i>Proceedings of the IEEE</i>, <b>82</b> (6): <span class="nowrap">857–</span>865, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F5.286189">10.1109/5.286189</a>, <a href="/wiki/Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1808%2F7229">1808/7229</a></span>, archived from <a rel="nofollow" class="external text" href="http://home.tiscali.nl/rajduim/Video%20Compression%20Docs/Arithmetic%20Coding%20For%20Data%20Compression%20(2).pdf">the original</a> <span class="cs1-format">(PDF)</span> on 18 October 2013<span class="reference-accessdate">, retrieved <span class="nowrap">17 October</span> 2013</span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+the+IEEE&rft.atitle=Arithmetic+coding+for+data+compression&rft.volume=82&rft.issue=6&rft.pages=%3Cspan+class%3D%22nowrap%22%3E857-%3C%2Fspan%3E865&rft.date=1994&rft_id=info%3Ahdl%2F1808%2F7229&rft_id=info%3Adoi%2F10.1109%2F5.286189&rft.aulast=Howard&rft.aufirst=Paul+G.&rft.au=Vitter%2C+Jeffrey+S.&rft_id=http%3A%2F%2Fhome.tiscali.nl%2Frajduim%2FVideo%2520Compression%2520Docs%2FArithmetic%2520Coding%2520For%2520Data%2520Compression%2520%282%29.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span>.</span> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=18" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMacKay2003" class="citation book cs1"><a href="/wiki/David_MacKay_(scientist)" class="mw-redirect" title="David MacKay (scientist)">MacKay, David J.C.</a> (September 2003). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20071222053346/http://www.inference.phy.cam.ac.uk/mackay/itila/book.html">"Chapter 6: Stream Codes"</a>. <i>Information Theory, Inference, and Learning Algorithms</i>. <a href="/wiki/Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-521-64298-1" title="Special:BookSources/0-521-64298-1"><bdi>0-521-64298-1</bdi></a>. Archived from <a rel="nofollow" class="external text" href="http://www.inference.phy.cam.ac.uk/mackay/itila/book.html">the original</a> <span class="cs1-format">(PDF/<a href="/wiki/PostScript" title="PostScript">PostScript</a>/<a href="/wiki/DjVu" title="DjVu">DjVu</a>/<a href="/wiki/LaTeX" title="LaTeX">LaTeX</a>)</span> on 22 December 2007<span class="reference-accessdate">. Retrieved <span class="nowrap">30 December</span> 2007</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Chapter+6%3A+Stream+Codes&rft.btitle=Information+Theory%2C+Inference%2C+and+Learning+Algorithms&rft.pub=Cambridge+University+Press&rft.date=2003-09&rft.isbn=0-521-64298-1&rft.aulast=MacKay&rft.aufirst=David+J.C.&rft_id=http%3A%2F%2Fwww.inference.phy.cam.ac.uk%2Fmackay%2Fitila%2Fbook.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPressTeukolskyVetterlingFlannery2007" class="citation book cs1">Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=1181">"Section 22.6. Arithmetic Coding"</a>. <i>Numerical Recipes: The Art of Scientific Computing</i> (3rd ed.). New York: Cambridge University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-521-88068-8" title="Special:BookSources/978-0-521-88068-8"><bdi>978-0-521-88068-8</bdi></a>. Archived from <a rel="nofollow" class="external text" href="http://apps.nrbook.com/empanel/index.html#pg=1181">the original</a> on 11 August 2011<span class="reference-accessdate">. Retrieved <span class="nowrap">18 August</span> 2011</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Section+22.6.+Arithmetic+Coding&rft.btitle=Numerical+Recipes%3A+The+Art+of+Scientific+Computing&rft.place=New+York&rft.edition=3rd&rft.pub=Cambridge+University+Press&rft.date=2007&rft.isbn=978-0-521-88068-8&rft.aulast=Press&rft.aufirst=WH&rft.au=Teukolsky%2C+SA&rft.au=Vetterling%2C+WT&rft.au=Flannery%2C+BP&rft_id=http%3A%2F%2Fapps.nrbook.com%2Fempanel%2Findex.html%23pg%3D1181&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRissanen1976" class="citation journal cs1"><a href="/wiki/Jorma_Rissanen" title="Jorma Rissanen">Rissanen, Jorma</a> (May 1976). <a rel="nofollow" class="external text" href="http://domino.watson.ibm.com/tchjr/journalindex.nsf/4ac37cf0bdc4dd6a85256547004d47e1/53fec2e5af172a3185256bfa0067f7a0?OpenDocument">"Generalized Kraft Inequality and Arithmetic Coding"</a>. <i>IBM Journal of Research and Development</i>. <b>20</b> (3): <span class="nowrap">198–</span>203. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1147%2Frd.203.0198">10.1147/rd.203.0198</a><span class="reference-accessdate">. Retrieved <span class="nowrap">21 September</span> 2007</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IBM+Journal+of+Research+and+Development&rft.atitle=Generalized+Kraft+Inequality+and+Arithmetic+Coding&rft.volume=20&rft.issue=3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E198-%3C%2Fspan%3E203&rft.date=1976-05&rft_id=info%3Adoi%2F10.1147%2Frd.203.0198&rft.aulast=Rissanen&rft.aufirst=Jorma&rft_id=http%3A%2F%2Fdomino.watson.ibm.com%2Ftchjr%2Fjournalindex.nsf%2F4ac37cf0bdc4dd6a85256547004d47e1%2F53fec2e5af172a3185256bfa0067f7a0%3FOpenDocument&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRissanenLangdon_G.G.,_Jr1979" class="citation journal cs1">Rissanen, J.J.; Langdon G.G., Jr (March 1979). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20070928023306/http://researchweb.watson.ibm.com/journal/rd/232/ibmrd2302G.pdf">"Arithmetic coding"</a> <span class="cs1-format">(PDF)</span>. <i>IBM Journal of Research and Development</i>. <b>23</b> (2): <span class="nowrap">149–</span>162. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1147%2Frd.232.0149">10.1147/rd.232.0149</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:39909636">39909636</a>. Archived from <a rel="nofollow" class="external text" href="http://researchweb.watson.ibm.com/journal/rd/232/ibmrd2302G.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 28 September 2007<span class="reference-accessdate">. Retrieved <span class="nowrap">22 September</span> 2007</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IBM+Journal+of+Research+and+Development&rft.atitle=Arithmetic+coding&rft.volume=23&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E149-%3C%2Fspan%3E162&rft.date=1979-03&rft_id=info%3Adoi%2F10.1147%2Frd.232.0149&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A39909636%23id-name%3DS2CID&rft.aulast=Rissanen&rft.aufirst=J.J.&rft.au=Langdon+G.G.%2C+Jr&rft_id=http%3A%2F%2Fresearchweb.watson.ibm.com%2Fjournal%2Frd%2F232%2Fibmrd2302G.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWittenNeal,_Radford_M.Cleary,_John_G.1987" class="citation journal cs1">Witten, Ian H.; Neal, Radford M.; Cleary, John G. (June 1987). <a rel="nofollow" class="external text" href="http://www.stanford.edu/class/ee398a/handouts/papers/WittenACM87ArithmCoding.pdf">"Arithmetic Coding for Data Compression"</a> <span class="cs1-format">(PDF)</span>. <i><a href="/wiki/Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a></i>. <b>30</b> (6): <span class="nowrap">520–</span>540. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F214762.214771">10.1145/214762.214771</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3343393">3343393</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20070928023306/http://www.stanford.edu/class/ee398a/handouts/papers/WittenACM87ArithmCoding.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 28 September 2007<span class="reference-accessdate">. Retrieved <span class="nowrap">21 September</span> 2007</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Communications+of+the+ACM&rft.atitle=Arithmetic+Coding+for+Data+Compression&rft.volume=30&rft.issue=6&rft.pages=%3Cspan+class%3D%22nowrap%22%3E520-%3C%2Fspan%3E540&rft.date=1987-06&rft_id=info%3Adoi%2F10.1145%2F214762.214771&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A3343393%23id-name%3DS2CID&rft.aulast=Witten&rft.aufirst=Ian+H.&rft.au=Neal%2C+Radford+M.&rft.au=Cleary%2C+John+G.&rft_id=http%3A%2F%2Fwww.stanford.edu%2Fclass%2Fee398a%2Fhandouts%2Fpapers%2FWittenACM87ArithmCoding.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></li></ul> <ul><li>Rodionov Anatoly, Volkov Sergey (2010) "p-adic arithmetic coding" Contemporary Mathematics Volume 508, 2010 Contemporary Mathematics</li> <li>Rodionov Anatoly, Volkov Sergey (2007) "p-adic arithmetic coding", <a rel="nofollow" class="external text" href="https://arxiv.org/abs//0704.0834v1">P-adic arithmetic coding</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arithmetic_coding&action=edit&section=19" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><span class="noviewer" typeof="mw:File"><span><img alt="Public Domain" src="//upload.wikimedia.org/wikipedia/en/thumb/6/62/PD-icon.svg/12px-PD-icon.svg.png" decoding="async" width="12" height="12" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/6/62/PD-icon.svg/18px-PD-icon.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/6/62/PD-icon.svg/24px-PD-icon.svg.png 2x" data-file-width="196" data-file-height="196" /></span></span> This article incorporates <a href="/wiki/Copyright_status_of_works_by_the_federal_government_of_the_United_States" title="Copyright status of works by the federal government of the United States">public domain material</a> from <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPaul_E._Black" class="citation cs1">Paul E. Black. <a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/arithmeticCoding.html">"Arithmetic coding"</a>. <i><a href="/wiki/Dictionary_of_Algorithms_and_Data_Structures" class="mw-redirect" title="Dictionary of Algorithms and Data Structures">Dictionary of Algorithms and Data Structures</a></i>. <a href="/wiki/NIST" class="mw-redirect" title="NIST">NIST</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Dictionary+of+Algorithms+and+Data+Structures&rft.atitle=Arithmetic+coding&rft.au=Paul+E.+Black&rft_id=https%3A%2F%2Fxlinux.nist.gov%2Fdads%2FHTML%2FarithmeticCoding.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AArithmetic+coding" class="Z3988"></span></li> <li><a rel="nofollow" class="external text" href="http://www.gtoal.com/wordgames/documents/arithmetic-encoding.mai">Newsgroup posting</a> with a short worked example of arithmetic encoding (integer-only).</li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20030228094950/http://planetmath.org/encyclopedia/ArithmeticEncoding.html">PlanetMath article on arithmetic coding</a></li> <li><a rel="nofollow" class="external text" href="http://ezcodesample.com/reanatomy.html">Anatomy of Range Encoder</a> The article explains both range and arithmetic coding. It has also code samples for 3 different arithmetic encoders along with performance comparison.</li> <li><a rel="nofollow" class="external text" href="http://hpl.hp.com/techreports/2004/HPL-2004-76.pdf">Introduction to Arithmetic Coding</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20201109031919/http://hpl.hp.com/techreports/2004/HPL-2004-76.pdf">Archived</a> 9 November 2020 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a>. 60 pages.</li> <li><a href="/wiki/Eric_Bodden" title="Eric Bodden">Eric Bodden</a>, Malte Clasen and Joachim Kneis: <a rel="nofollow" class="external text" href="http://www.sable.mcgill.ca/publications/techreports/#report2007-5">Arithmetic Coding revealed</a>. Technical Report 2007-5, Sable Research Group, McGill University.</li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/19990428180948/http://dogma.net/markn/articles/arith/part1.htm">Arithmetic Coding + Statistical Modeling = Data Compression</a> by Mark Nelson.</li> <li><a rel="nofollow" class="external text" href="https://marknelson.us/posts/2014/10/19/data-compression-with-arithmetic-coding.html">Data Compression With Arithmetic Coding</a> by Mark Nelson (2014)</li> <li><a rel="nofollow" class="external text" href="https://github.com/jkbonfield/rans_static">Fast implementation of range coding and rANS</a> by James K. Bonfield</li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Data_compression_methods223" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Compression_methods" title="Template:Compression methods"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Compression_methods" title="Template talk:Compression methods"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Compression_methods" title="Special:EditPage/Template:Compression methods"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Data_compression_methods223" style="font-size:114%;margin:0 4em"><a href="/wiki/Data_compression" title="Data compression">Data compression</a> methods</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Lossless_compression" title="Lossless compression">Lossless</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;"><a href="/wiki/Entropy_coding" title="Entropy coding">Entropy type</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Adaptive_coding" title="Adaptive coding">Adaptive coding</a></li> <li><a class="mw-selflink selflink">Arithmetic</a></li> <li><a href="/wiki/Asymmetric_numeral_systems" title="Asymmetric numeral systems">Asymmetric numeral systems</a></li> <li><a href="/wiki/Golomb_coding" title="Golomb coding">Golomb</a></li> <li><a href="/wiki/Huffman_coding" title="Huffman coding">Huffman</a> <ul><li><a href="/wiki/Adaptive_Huffman_coding" title="Adaptive Huffman coding">Adaptive</a></li> <li><a href="/wiki/Canonical_Huffman_code" title="Canonical Huffman code">Canonical</a></li> <li><a href="/wiki/Modified_Huffman_coding" title="Modified Huffman coding">Modified</a></li></ul></li> <li><a href="/wiki/Range_coding" title="Range coding">Range</a></li> <li><a href="/wiki/Shannon_coding" title="Shannon coding">Shannon</a></li> <li><a href="/wiki/Shannon%E2%80%93Fano_coding" title="Shannon–Fano coding">Shannon–Fano</a></li> <li><a href="/wiki/Shannon%E2%80%93Fano%E2%80%93Elias_coding" title="Shannon–Fano–Elias coding">Shannon–Fano–Elias</a></li> <li><a href="/wiki/Tunstall_coding" title="Tunstall coding">Tunstall</a></li> <li><a href="/wiki/Unary_coding" title="Unary coding">Unary</a></li> <li><a href="/wiki/Universal_code_(data_compression)" title="Universal code (data compression)">Universal</a> <ul><li><a href="/wiki/Exponential-Golomb_coding" title="Exponential-Golomb coding">Exp-Golomb</a></li> <li><a href="/wiki/Fibonacci_coding" title="Fibonacci coding">Fibonacci</a></li> <li><a href="/wiki/Elias_gamma_coding" title="Elias gamma coding">Gamma</a></li> <li><a href="/wiki/Levenshtein_coding" title="Levenshtein coding">Levenshtein</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;"><a href="/wiki/Dictionary_coder" title="Dictionary coder">Dictionary type</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Byte_pair_encoding" title="Byte pair encoding">Byte pair encoding</a></li> <li><a href="/wiki/LZ77_and_LZ78" title="LZ77 and LZ78">Lempel–Ziv</a> <ul><li><a href="/wiki/842_(compression_algorithm)" title="842 (compression algorithm)">842</a></li> <li><a href="/wiki/LZ4_(compression_algorithm)" title="LZ4 (compression algorithm)">LZ4</a></li> <li><a href="/wiki/LZJB" class="mw-redirect" title="LZJB">LZJB</a></li> <li><a href="/wiki/Lempel%E2%80%93Ziv%E2%80%93Oberhumer" title="Lempel–Ziv–Oberhumer">LZO</a></li> <li><a href="/wiki/LZRW" title="LZRW">LZRW</a></li> <li><a href="/wiki/Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski" title="Lempel–Ziv–Storer–Szymanski">LZSS</a></li> <li><a href="/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch" title="Lempel–Ziv–Welch">LZW</a></li> <li><a href="/wiki/LZWL" title="LZWL">LZWL</a></li> <li><a href="/wiki/Snappy_(compression)" title="Snappy (compression)">Snappy</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Other types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Burrows%E2%80%93Wheeler_transform" title="Burrows–Wheeler transform">BWT</a></li> <li><a href="/wiki/Context_tree_weighting" title="Context tree weighting">CTW</a></li> <li><a href="/wiki/Context_mixing" title="Context mixing">CM</a></li> <li><a href="/wiki/Delta_encoding" title="Delta encoding">Delta</a> <ul><li><a href="/wiki/Incremental_encoding" title="Incremental encoding">Incremental</a></li></ul></li> <li><a href="/wiki/Dynamic_Markov_compression" title="Dynamic Markov compression">DMC</a></li> <li><a href="/wiki/Differential_pulse-code_modulation" title="Differential pulse-code modulation">DPCM</a></li> <li><a href="/wiki/Grammar-based_code" title="Grammar-based code">Grammar</a> <ul><li><a href="/wiki/Re-Pair" title="Re-Pair">Re-Pair</a></li> <li><a href="/wiki/Sequitur_algorithm" title="Sequitur algorithm">Sequitur</a></li></ul></li> <li><a href="/wiki/Discrete_cosine_transform" title="Discrete cosine transform">LDCT</a></li> <li><a href="/wiki/Move-to-front_transform" title="Move-to-front transform">MTF</a></li> <li><a href="/wiki/PAQ" title="PAQ">PAQ</a></li> <li><a href="/wiki/Prediction_by_partial_matching" title="Prediction by partial matching">PPM</a></li> <li><a href="/wiki/Run-length_encoding" title="Run-length encoding">RLE</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Hybrid</th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em"> <ul><li>LZ77 + Huffman <ul><li><a href="/wiki/Deflate" title="Deflate">Deflate</a></li> <li><a href="/wiki/LZX" title="LZX">LZX</a></li> <li><a href="/wiki/Lempel%E2%80%93Ziv%E2%80%93Stac" title="Lempel–Ziv–Stac">LZS</a></li></ul></li> <li>LZ77 + ANS <ul><li><a href="/wiki/LZFSE" title="LZFSE">LZFSE</a></li></ul></li> <li>LZ77 + Huffman + ANS <ul><li><a href="/wiki/Zstd" title="Zstd">Zstandard</a></li></ul></li> <li>LZ77 + Huffman + context <ul><li><a href="/wiki/Brotli" title="Brotli">Brotli</a></li></ul></li> <li>LZSS + Huffman <ul><li><a href="/wiki/LHA_(file_format)" title="LHA (file format)">LHA/LZH</a></li></ul></li> <li>LZ77 + Range <ul><li><a href="/wiki/Lempel%E2%80%93Ziv%E2%80%93Markov_chain_algorithm" title="Lempel–Ziv–Markov chain algorithm">LZMA</a></li> <li>LZHAM</li></ul></li> <li>RLE + BWT + MTF + Huffman <ul><li><a href="/wiki/Bzip2" title="Bzip2">bzip2</a></li></ul></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Lossy_compression" title="Lossy compression">Lossy</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;"><a href="/wiki/Transform_coding" title="Transform coding">Transform type</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Discrete_cosine_transform" title="Discrete cosine transform">Discrete cosine transform</a> <ul><li><a href="/wiki/Discrete_cosine_transform" title="Discrete cosine transform">DCT</a></li> <li><a href="/wiki/Modified_discrete_cosine_transform" title="Modified discrete cosine transform">MDCT</a></li></ul></li> <li><a href="/wiki/Discrete_sine_transform" title="Discrete sine transform">DST</a></li> <li><a href="/wiki/Fast_Fourier_transform" title="Fast Fourier transform">FFT</a></li> <li><a href="/wiki/Wavelet_transform" title="Wavelet transform">Wavelet</a> <ul><li><a href="/wiki/Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li> <li><a href="/wiki/Discrete_wavelet_transform" title="Discrete wavelet transform">DWT</a></li> <li><a href="/wiki/Set_partitioning_in_hierarchical_trees" title="Set partitioning in hierarchical trees">SPIHT</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Predictive type</th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Differential_pulse-code_modulation" title="Differential pulse-code modulation">DPCM</a> <ul><li><a href="/wiki/Adaptive_differential_pulse-code_modulation" title="Adaptive differential pulse-code modulation">ADPCM</a></li></ul></li> <li><a href="/wiki/Linear_predictive_coding" title="Linear predictive coding">LPC</a> <ul><li><a href="/wiki/Algebraic_code-excited_linear_prediction" title="Algebraic code-excited linear prediction">ACELP</a></li> <li><a href="/wiki/Code-excited_linear_prediction" title="Code-excited linear prediction">CELP</a></li> <li><a href="/wiki/Log_area_ratio" title="Log area ratio">LAR</a></li> <li><a href="/wiki/Line_spectral_pairs" title="Line spectral pairs">LSP</a></li> <li><a href="/wiki/Warped_linear_predictive_coding" title="Warped linear predictive coding">WLPC</a></li></ul></li> <li>Motion <ul><li><a href="/wiki/Motion_compensation" title="Motion compensation">Compensation</a></li> <li><a href="/wiki/Motion_estimation" title="Motion estimation">Estimation</a></li> <li><a href="/wiki/Motion_vector" class="mw-redirect" title="Motion vector">Vector</a></li></ul></li> <li><a href="/wiki/Psychoacoustics" title="Psychoacoustics">Psychoacoustic</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Data_compression#Audio" title="Data compression">Audio</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bit_rate" title="Bit rate">Bit rate</a> <ul><li><a href="/wiki/Average_bitrate" title="Average bitrate">ABR</a></li> <li><a href="/wiki/Constant_bitrate" title="Constant bitrate">CBR</a></li> <li><a href="/wiki/Variable_bitrate" title="Variable bitrate">VBR</a></li></ul></li> <li><a href="/wiki/Companding" title="Companding">Companding</a></li> <li><a href="/wiki/Convolution" title="Convolution">Convolution</a></li> <li><a href="/wiki/Dynamic_range" title="Dynamic range">Dynamic range</a></li> <li><a href="/wiki/Latency_(audio)" title="Latency (audio)">Latency</a></li> <li><a href="/wiki/Nyquist%E2%80%93Shannon_sampling_theorem" title="Nyquist–Shannon sampling theorem">Nyquist–Shannon theorem</a></li> <li><a href="/wiki/Sampling_(signal_processing)" title="Sampling (signal processing)">Sampling</a></li> <li><a href="/wiki/Silence_compression" title="Silence compression">Silence compression</a></li> <li><a href="/wiki/Sound_quality" title="Sound quality">Sound quality</a></li> <li><a href="/wiki/Speech_coding" title="Speech coding">Speech coding</a></li> <li><a href="/wiki/Sub-band_coding" title="Sub-band coding">Sub-band coding</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;"><a href="/wiki/Audio_codec" title="Audio codec">Codec</a> parts</th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/A-law_algorithm" title="A-law algorithm">A-law</a></li> <li><a href="/wiki/%CE%9C-law_algorithm" title="Μ-law algorithm">μ-law</a></li> <li><a href="/wiki/Differential_pulse-code_modulation" title="Differential pulse-code modulation">DPCM</a> <ul><li><a href="/wiki/Adaptive_differential_pulse-code_modulation" title="Adaptive differential pulse-code modulation">ADPCM</a></li> <li><a href="/wiki/Delta_modulation" title="Delta modulation">DM</a></li></ul></li> <li><a href="/wiki/Fourier_transform" title="Fourier transform">FT</a> <ul><li><a href="/wiki/Fast_Fourier_transform" title="Fast Fourier transform">FFT</a></li></ul></li> <li><a href="/wiki/Linear_predictive_coding" title="Linear predictive coding">LPC</a> <ul><li><a href="/wiki/Algebraic_code-excited_linear_prediction" title="Algebraic code-excited linear prediction">ACELP</a></li> <li><a href="/wiki/Code-excited_linear_prediction" title="Code-excited linear prediction">CELP</a></li> <li><a href="/wiki/Log_area_ratio" title="Log area ratio">LAR</a></li> <li><a href="/wiki/Line_spectral_pairs" title="Line spectral pairs">LSP</a></li> <li><a href="/wiki/Warped_linear_predictive_coding" title="Warped linear predictive coding">WLPC</a></li></ul></li> <li><a href="/wiki/Modified_discrete_cosine_transform" title="Modified discrete cosine transform">MDCT</a></li> <li><a href="/wiki/Psychoacoustics" title="Psychoacoustics">Psychoacoustic model</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Image_compression" title="Image compression">Image</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Chroma_subsampling" title="Chroma subsampling">Chroma subsampling</a></li> <li><a href="/wiki/Coding_tree_unit" title="Coding tree unit">Coding tree unit</a></li> <li><a href="/wiki/Color_space" title="Color space">Color space</a></li> <li><a href="/wiki/Compression_artifact" title="Compression artifact">Compression artifact</a></li> <li><a href="/wiki/Image_resolution" title="Image resolution">Image resolution</a></li> <li><a href="/wiki/Macroblock" title="Macroblock">Macroblock</a></li> <li><a href="/wiki/Pixel" title="Pixel">Pixel</a></li> <li><a href="/wiki/Peak_signal-to-noise_ratio" title="Peak signal-to-noise ratio">PSNR</a></li> <li><a href="/wiki/Quantization_(image_processing)" title="Quantization (image processing)">Quantization</a></li> <li><a href="/wiki/Standard_test_image" title="Standard test image">Standard test image</a></li> <li><a href="/wiki/Texture_compression" title="Texture compression">Texture compression</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Methods</th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Chain_code" title="Chain code">Chain code</a></li> <li><a href="/wiki/Discrete_cosine_transform" title="Discrete cosine transform">DCT</a></li> <li><a href="/wiki/Deflate" title="Deflate">Deflate</a></li> <li><a href="/wiki/Fractal_compression" title="Fractal compression">Fractal</a></li> <li><a href="/wiki/Karhunen%E2%80%93Lo%C3%A8ve_theorem" class="mw-redirect" title="Karhunen–Loève theorem">KLT</a></li> <li><a href="/wiki/Pyramid_(image_processing)" title="Pyramid (image processing)">LP</a></li> <li><a href="/wiki/Run-length_encoding" title="Run-length encoding">RLE</a></li> <li><a href="/wiki/Wavelet_transform" title="Wavelet transform">Wavelet</a> <ul><li><a href="/wiki/Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li> <li><a href="/wiki/Discrete_wavelet_transform" title="Discrete wavelet transform">DWT</a></li> <li><a href="/wiki/Embedded_zerotrees_of_wavelet_transforms" title="Embedded zerotrees of wavelet transforms">EZW</a></li> <li><a href="/wiki/Set_partitioning_in_hierarchical_trees" title="Set partitioning in hierarchical trees">SPIHT</a></li></ul></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Data_compression#Video" title="Data compression">Video</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bit_rate" title="Bit rate">Bit rate</a> <ul><li><a href="/wiki/Average_bitrate" title="Average bitrate">ABR</a></li> <li><a href="/wiki/Constant_bitrate" title="Constant bitrate">CBR</a></li> <li><a href="/wiki/Variable_bitrate" title="Variable bitrate">VBR</a></li></ul></li> <li><a href="/wiki/Display_resolution" title="Display resolution">Display resolution</a></li> <li><a href="/wiki/Film_frame" title="Film frame">Frame</a></li> <li><a href="/wiki/Frame_rate" title="Frame rate">Frame rate</a></li> <li><a href="/wiki/Video_compression_picture_types" title="Video compression picture types">Frame types</a></li> <li><a href="/wiki/Interlaced_video" title="Interlaced video">Interlace</a></li> <li><a href="/wiki/Video#Characteristics_of_video_streams" title="Video">Video characteristics</a></li> <li><a href="/wiki/Video_quality" title="Video quality">Video quality</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;"><a href="/wiki/Video_codec" title="Video codec">Codec</a> parts</th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Discrete_cosine_transform" title="Discrete cosine transform">DCT</a></li> <li><a href="/wiki/Differential_pulse-code_modulation" title="Differential pulse-code modulation">DPCM</a></li> <li><a href="/wiki/Deblocking_filter" title="Deblocking filter">Deblocking filter</a></li> <li><a href="/wiki/Lapped_transform" title="Lapped transform">Lapped transform</a></li> <li>Motion <ul><li><a href="/wiki/Motion_compensation" title="Motion compensation">Compensation</a></li> <li><a href="/wiki/Motion_estimation" title="Motion estimation">Estimation</a></li> <li><a href="/wiki/Motion_vector" class="mw-redirect" title="Motion vector">Vector</a></li></ul></li> <li><a href="/wiki/Wavelet_transform" title="Wavelet transform">Wavelet</a> <ul><li><a href="/wiki/Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li> <li><a href="/wiki/Discrete_wavelet_transform" title="Discrete wavelet transform">DWT</a></li></ul></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Information_theory" title="Information theory">Theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Compressed_data_structure" title="Compressed data structure">Compressed data structures</a> <ul><li><a href="/wiki/Compressed_suffix_array" title="Compressed suffix array">Compressed suffix array</a></li> <li><a href="/wiki/FM-index" title="FM-index">FM-index</a></li></ul></li> <li><a href="/wiki/Entropy_(information_theory)" title="Entropy (information theory)">Entropy</a></li> <li><a href="/wiki/Information_theory" title="Information theory">Information theory</a> <ul><li><a href="/wiki/Timeline_of_information_theory" title="Timeline of information theory">Timeline</a></li></ul></li> <li><a href="/wiki/Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li> <li><a href="/wiki/Prefix_code" title="Prefix code">Prefix code</a></li> <li><a href="/wiki/Quantization_(signal_processing)" title="Quantization (signal processing)">Quantization</a></li> <li><a href="/wiki/Rate%E2%80%93distortion_theory" title="Rate–distortion theory">Rate–distortion</a></li> <li><a href="/wiki/Redundancy_(information_theory)" title="Redundancy (information theory)">Redundancy</a></li> <li><a href="/wiki/Data_compression_symmetry" title="Data compression symmetry">Symmetry</a></li> <li><a href="/wiki/Smallest_grammar_problem" title="Smallest grammar problem">Smallest grammar problem</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Community</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Hutter_Prize" title="Hutter Prize">Hutter Prize</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">People</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Mark_Adler" title="Mark Adler">Mark Adler</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Arithmetic_coding&oldid=1268711433">https://en.wikipedia.org/w/index.php?title=Arithmetic_coding&oldid=1268711433</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Entropy_coding" title="Category:Entropy coding">Entropy coding</a></li><li><a href="/wiki/Category:Data_compression" title="Category:Data compression">Data compression</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Use_dmy_dates_from_December_2019" title="Category:Use dmy dates from December 2019">Use dmy dates from December 2019</a></li><li><a href="/wiki/Category:Articles_lacking_in-text_citations_from_September_2016" title="Category:Articles lacking in-text citations from September 2016">Articles lacking in-text citations from September 2016</a></li><li><a href="/wiki/Category:All_articles_lacking_in-text_citations" title="Category:All articles lacking in-text citations">All articles lacking in-text citations</a></li><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 11 January 2025, at 04:35<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Arithmetic_coding&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" lang="en" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Arithmetic coding</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>14 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-b766959bd-mr48r","wgBackendResponseTime":146,"wgPageParseReport":{"limitreport":{"cputime":"0.465","walltime":"0.685","ppvisitednodes":{"value":3412,"limit":1000000},"postexpandincludesize":{"value":99054,"limit":2097152},"templateargumentsize":{"value":2913,"limit":2097152},"expansiondepth":{"value":17,"limit":100},"expensivefunctioncount":{"value":6,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":58779,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 492.083 1 -total"," 19.34% 95.174 6 Template:Navbox"," 18.61% 91.598 1 Template:Compression_Methods"," 15.72% 77.336 4 Template:Cite_book"," 14.45% 71.088 1 Template:Short_description"," 9.66% 47.518 2 Template:Pagetype"," 9.30% 45.748 1 Template:More_footnotes_needed"," 8.65% 42.576 1 Template:Ambox"," 6.13% 30.157 1 Template:Harvtxt"," 5.22% 25.694 11 Template:US_patent"]},"scribunto":{"limitreport-timeusage":{"value":"0.264","limit":"10.000"},"limitreport-memusage":{"value":6847684,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREFHowardVitter1994\"] = 1,\n [\"CITEREFMacKay2003\"] = 1,\n [\"CITEREFPasco1976\"] = 1,\n [\"CITEREFPennebakerMitchell1992\"] = 1,\n [\"CITEREFPressTeukolskyVetterlingFlannery2007\"] = 1,\n [\"CITEREFRissanen1976\"] = 1,\n [\"CITEREFRissanenLangdon_G.G.,_Jr1979\"] = 1,\n [\"CITEREFWittenNeal,_Radford_M.Cleary,_John_G.1987\"] = 1,\n [\"CITEREFZe-Nian_LiMark_S._DrewJiangchuan_Liu2014\"] = 1,\n}\ntemplate_list = table#1 {\n [\"Blockquote\"] = 1,\n [\"CNone\"] = 1,\n [\"Citation\"] = 1,\n [\"Cite book\"] = 4,\n [\"Cite journal\"] = 3,\n [\"Cite thesis\"] = 1,\n [\"Cite web\"] = 5,\n [\"Compression Methods\"] = 1,\n [\"DADS\"] = 1,\n [\"Figure space\"] = 3,\n [\"Harvtxt\"] = 1,\n [\"Main\"] = 1,\n [\"Math\"] = 4,\n [\"Mono\"] = 6,\n [\"More footnotes needed\"] = 1,\n [\"Nowrap\"] = 1,\n [\"Samp\"] = 8,\n [\"See also\"] = 1,\n [\"Short description\"] = 1,\n [\"US patent\"] = 11,\n [\"Use dmy dates\"] = 1,\n [\"Webarchive\"] = 1,\n}\narticle_whitelist = table#1 {\n}\nciteref_patterns = table#1 {\n}\n"},"cachereport":{"origin":"mw-api-int.codfw.main-5b65fffc7d-tk2vx","timestamp":"20250214040859","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Arithmetic coding","url":"https:\/\/en.wikipedia.org\/wiki\/Arithmetic_coding","sameAs":"http:\/\/www.wikidata.org\/entity\/Q2651","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q2651","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2001-05-26T02:52:49Z","dateModified":"2025-01-11T04:35:43Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/8\/82\/Arithmetic_coding_example.svg","headline":"form of entropy encoding used in lossless data compression"}</script> </body> </html>