Even–Rodeh coding: Difference between revisions

Revision as of 14:47, 7 December 2015

Latest revision as of 23:56, 5 December 2024

(13 intermediate revisions by 9 users not shown)

Line 1:

'''Even-Rodeh Even–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">{{cite journal |first1=Shimon |last1=Even |first2=Michael |last2=Rodeh |title=Economical encoding of commas between strings |journal=[[Communications of the ACM]] |volume=21 |issue=4 |pages=315–317 |date=April 1978 |url=http://dl.acm.org/citation.cfm?id=359480 |doi=10.1145/359460.359480}}</ref>

== 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 48 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 35:

| 4 || <code>100&thinsp;0</code> || 1/16

|-

| 5 || <code>101&thinsp;0</code> || 1/16

|colspan=3 style="text-align: center;"| &#xFE19;

|-

| 6 || <code>110&thinsp;0</code> || 1/16

|-

| 7 || <code>111&thinsp;0</code> || 1/16

Line 43 ⟶ 45:

| 8 || <code>100&thinsp;1000&thinsp;0</code> || 1/256

|-

| 9 || <code>100&thinsp;1001&thinsp;0</code> || 1/256

|colspan=3 style="text-align: center;"| &#xFE19;

|-

|colspan=3 style="text-align: center;"| &#xFE19;︙

|-

| 15 || <code>100&thinsp;1111&thinsp;0</code> || 1/256

Line 51 ⟶ 55:

| 16 || <code>101&thinsp;10000&thinsp;0</code> || 1/512

|-

|colspan=3 style="text-align: center;"| &#xFE19;︙

|-

| 2761 || {{nowrap|<code>100&thinsp;1100&thinsp;101011001001&thinsp;0</code>}} || 1/1,048,576

|-

|colspan=3 style="text-align: center;"| &#xFE19;︙

|}

== References ==

<references/>

== See also ==

* [[Elias omega coding|Elias omega (ω) coding]]

== References ==

* [[Elias omega coding]]

{{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]]