Even–Rodeh coding: Difference between revisions

Revision as of 14:28, 21 February 2020

Latest revision as of 23:56, 5 December 2024

(4 intermediate revisions by 4 users not shown)

Line 1:

'''Even-RodehEven–Rodeh code''' is a [[Universal code (data compression)|universal code]] encoding the non-negative integers developed by [[Shimon Even]] and [[Michael Rodeh]].<ref name="EvenRodeh"/>

== Encoding ==

To code a [[non-negative integer]] ''{{var|N''}} in Even-RodehEven–Rodeh coding:

# If ''{{var|N''}} is not less than 4 then set the coded value to a single <code>0</code> bit. Otherwise the coded value is empty.

# If ''{{var|N''}} is less than 8 then prepend the coded value with 3 bits containing the value of ''{{var|N''}} and stop.

# Prepend the coded value with the [[binary numeral system|binary]] representation of ''{{var|N''}}.

# Store the number of bits prepended in step 3 as the new value of ''{{var|N''}}.

# Go back to step 2.

To decode an Even-RodehEven–Rodeh-coded integer:

# Read 3 bits and store the value into ''{{var|N''}}.

#* If the first bit read was <code>0</code> then stop. The decoded number is ''{{var|N''}}.

#* If the first bit read was <code>1</code> then continue to step 2.

# Examine the next bit.

#* If the bit is <code>0</code> then read 1 bit and stop. The decoded number is ''{{var|N''}}.

#* If the bit is <code>1</code> then read ''{{var|N''}} bits, store the value as the new value of ''{{var|N''}}, and go back to step 2.

== Examples ==

Line 67:

== References ==

{{Reflist|refs=

<ref name="EvenRodeh">{{cite journal |author-first1=Shimon |author-last1=Even |author-link=Shimon Even |author-first2=Michael |author-last2=Rodeh |title=Economical encoding of commas between strings |journal=[[Communications of the ACM]] |volume=21 |issue=4 |pages=315–317 |date=April 1978 |doi=10.1145/359460.359480|doi-access=free }}</ref>

}}

{{Compression Methods}}

{{DEFAULTSORT:Even-Rodeh coding}}

[[Category:Lossless compression algorithms]]

[[Category:Entropy coding]]

[[Category:LosslessData compression algorithms]]