Talk:Golomb coding

The first image

Exactly what is the image with q-1, q and q+1 supposed to show? What is the curved arrow at the top for? The 'r' is placed so it looks like a badly typeset $q^{r}$.

I'm sorry, but the whole image just seems confusing to me. /87.96.186.152 (talk) 10:23, 11 March 2008 (UTC)

Yes, the image isn't very clear, but I don't know how to make it better. I think is an illustration of the modulo operation. Any possible number length n (in inches) can be divided into 2 parts, q (the number of yardsticks I have to use), and r (the number of inches along the last yardstick). --68.0.124.33 (talk) 08:31, 12 September 2008 (UTC)

raghvendra

raghvendra

— Preceding unsigned comment added by 117.199.199.30 (talk) 05:24, 16 March 2015 (UTC)

I took it out. Hopefully the new image I added will be found to be more interpretable. Dicklyon (talk) 03:44, 12 July 2021 (UTC)

Question on Unary coding...

On the Unary Coding page it says 5 is represented as 11110 yet in the table on the Golomb coding page it says 5 is 111110. Where is the mistake? Or if Golomb coding does use 111110 as 5 and Unary coding uses 11110 as 5, then was it a mistake to say that Golomb uses Unary?

Eric.frederich 16:59, 9 March 2007 (UTC)

The paper "Optimal source codes for geometrically distributed integer alphabets" by Gallager and Van Voorhis (1975, IEEE Transactions on Information Theory IT-21(2):228-230) is the citation "Managing Gigabytes" gives for the probability distribution quoted in the article, but I haven't had a chance to read the paper myself, so I'm hesitant to add it to the refrences. I'll get to it eventually, but if someone else wants to read it and see if it should be refrenced, please do.Mark Tozzi 06:47, 20 December 2005 (UTC)

their paper is not so great. i can send it to you if you provide email.. []

Insufficient Context

This article could use a bit more introductory context to orient non-expert readers.

For example:

• 'entropy' is introduced without context (cryptanalysis? astrophysics? neoclassical economics? what sense of entropy is relevant here?). Which connotation is not necessarily obvious to those unfamiliar.
• a quick 1 sentence blurb about what this kind of coding is used for would help (eg data compression, natural language processing, lexical analysis, string functions, whatever). It is implied in the text, but intro could be beefed up a bit.

dr.ef.tymac 16:27, 19 November 2006 (UTC)

I agree with the comments above about insufficient context, but I'm also confused about Rice's contribution to Golomb-Rice codes. The introduction says Golomb's scheme (which references a paper dated 1966) generalized Rice's scheme which was developed earlier, except that the only reference to Rice's work is a paper dated 1979. If Rice really did invent something before 1966, where's the reference? Otherwise, why is Rice's name even associated with the codes?

Golomb's codes came first (for memoryless run-length codes which yield a geometric distribution of run lengths). Later they were proven optimal for any geometric distribution. Still later Rice showed how an adaptive code based the simplest Golomb code (those that were parametrized by powers of two). People call both Rice's method and his subset "Rice coding," thus the confusion. I hope I've clarified all that and more in the intro; if someone thinks it's clear enough to remove the context header, please do so. Calbaer (talk) 21:40, 6 March 2009 (UTC)

Question on alphabets

Quote from the article: "Golomb coding can also be used (as in Golomb's original article) to encode an alphabet of two symbols, where one is more likely than the other. In this case it can be thought of as a kind of run-length encoding."

As far as I have understood the concept of the code from reading the original paper of S. Golomb, the code ALWAYS operates via a two-symbols alphabet, as it is used to produce a binary representation of a given number; hence, it is a mapping of that particular number (i.e., 42) to a sequence of the both sybmols occuring in the alphabet (obviously, 0 and 1), and vice versa. The length of the sequence is determined by the probability for one of those symbols to arise (for the case M = 10, this probability is 2^(-1/10) = 0,933 for one of the symbols; it is a question of convention if it would be called 0 or 1). If we were to code a number in a ternary representation, our alphabet would contain a third symbol, i.e. the ternary digit 2.

In the light of the above thoughts, I think that there is a slight confusion in the article in the sense that the number to be coded is regarded as part of the alphabet.

The quote from the article is completely misleading and confusing; it can be interpreted as if the numbers we would like to code were only two; however, this is not the case; it should mean that the base (or alphabet) used to produce some output consists of only two symbols - which is already clear, since we are talking of a binary code.

There should be a clear distinguishment between the set of numbers to be coded (i.e., 1, 2, ..., n), and the alphabet used to produce the code of the numbers in that set.

Nikolay Petkov 7c0[at]mail.com 22:27, 18 May 2007 (EET)

encoding an input that uses an alphabet of 2 symbols

I agree that sentence is confusing and easy to mis-interpret. What I *think* it is getting at is: Say we have a input file composed of 2 symbols, where each symbol in the sequence is more-or-less independent of the next (a Bernoulli process), but one symbol is vastly more likely than the other symbol -- for example, a recording of a Geiger counter, with occasional clicks ("1" bits) typically separated by long periods of silence (streams of "0" bits). Say I then partially compress that file with run-length encoding. This intermediate file contains the lengths of the runs of "0" bits (i.e., 0,1,2,... n). A length of "0" indicates consecutive "1" bits.

Further compressing that sequence of lengths with Golomb coding with the appropriate M parameter is the "most efficient" compression code. By "most efficient", I mean in the same way that Huffman coding is the "most efficent" compression code -- for this kind of file, both methods generate practically the same code. (My understanding is that arithmetic coding on the original file would give an even smaller compressed file).

The appropriate M parameter depends on the probability of the 2 symbols -- the more lop-sided the probability, the bigger M needs to be to get the most efficient compression.

Is this something that needs to be described in this article?

--68.0.124.33 (talk) 09:13, 12 September 2008 (UTC)

Example code

I don't think the example code belongs here. I suggest we remove it or maybe move it to Wikibooks(?). —ZeroOne (talk / @) 19:45, 25 June 2008 (UTC)

The code, furthermore, is an example of rice code. I think it's incorrect to describe a coding scheme and propose another one in the code example... --akbg (talk) 21:57, 12 September 2008 (UTC)

The example code was also incorrect - it inverted the remainder bit sequence for no apparent reason. I've deleted it per MOS:CODE. The existing pseudocode is enough to describe the algorithm. --dmmaus (talk) 23:57, 6 January 2014 (UTC)

Construction of code

What does "The final result looks like: $\left(q+1\right)r$" exactly mean? --201.253.134.203 (talk) 23:43, 5 October 2008 (UTC)

Oh, I got it. --201.253.134.203 (talk) 23:43, 5 October 2008 (UTC)

I don't get it... at least yet Micsthepick (talk) 10:40, 17 December 2020 (UTC)

Q: Use with signed integers?

Quote "This is an optimal prefix code only if both the positive and the magnitude of the negative values follow a geometric distribution with the same parameter." Question: Is it? Because the number of bits required grows twice as fast. It seems more efficient to separately encode the sign bit. Or I an not understanding it properly...

Encoding of quotient part
q	suggested	keeping sign (at LSB position)
0	0	10
1	10	010
-1	110	011
2	1110	0010
-2	11110	0011
3	111110	00010
-3	1111110	00011
$\vdots$	$\vdots$	$\vdots$

37.153.194.221 (talk) 10:59, 15 September 2015 (UTC)

Why is one subtracted from x

does x represent an unsigned integer? if so, what happens if x = 0? Micsthepick (talk) 10:41, 17 December 2020 (UTC)

better question, what does x represent? It is present after the image which uses N, without saying what x signifies, and not to mention that (if x=N) the two don't agree. Micsthepick (talk) 11:16, 17 December 2020 (UTC)

I think x was for a geometric distribution that starts with 1; I changed it to start with 0. Same meaning as N, I think. Please check and further unify. Dicklyon (talk) 04:42, 11 July 2021 (UTC)

The example appears to be incorrect?

The instructions say,

LET $b=\lfloor \log _{2}(M)\rfloor$

The example then states,

Set M = 10. Thus $b=\lceil \log _{2}(10)\rceil =4$. The cutoff is $2^{b}-M=16-10=6$

This b is different from the above b: the instructions calculate the floor, the example calculates the ceiling. AFAICT, though, the values in the tables use a b calculated with a floor, that is, they follow the instructions.

Is portion of the example in error?

I believe I have fixed the inconsistency. Please check. Dicklyon (talk) 05:44, 10 July 2021 (UTC)

Figure, p, and MPS

What is this p of MPS parameter on the abscissa?

This is confusing. I think the p or MPS (most probably symbol) probability is about the probability of repeats when doing run-length coding, and the run length is the variable with geometric distribution that is coded by the Rice or Golomb code. The guy who made the plot is no longer active, so I can't ask him for his code to see how he got there, or ask why this parameterization and terminology. Anybody got better insight into this? It would be good to make a better and more readable figure. Dicklyon (talk) 18:59, 10 July 2021 (UTC)

This prob(MPS) may be 1-p where p is the parameter of the geometric distribution? Dicklyon (talk) 03:21, 11 July 2021 (UTC)

Maybe this new figure can replace several in the article? Dicklyon (talk) 03:56, 11 July 2021 (UTC)

Golomb coding example for a source x with geometric distribution, with parameter p(0) = 0.2, using Golomb code with M = 3. The 2-bit code 00 is used 20% of the time; the 3-bit codes 010, 011, and 100 are used over 38% of the time; 4 bits or more are needed in a minority of cases. For this source, entropy = 3.610 bits; for this code with this source, rate = 3.639 bits; therefore redundancy = 0.030 bits, or efficiency = 0.992 bits per bit.

I gave the first figure 5X thicker lines (from 0.5 pt to 2.5 pt), in Inkscape, so they'd show up. I made most of the text bigger, too (not the numbers on the axes though; too tedious). And I edited the x axis label to say what I think it means. Dicklyon (talk) 02:34, 12 July 2021 (UTC)

I see the p problem now: that figure used to be in the run-length encoding section, where p and 1–p and reversed compared to where it's used now. So the x axis label, prob of most probable symbol, did make sense at one time. We still have the discrepancy between sections, but the figure has been fixed to work where I found it, I think. Dicklyon (talk) 15:45, 13 July 2021 (UTC)

MPS ist indeed the "most probable symbol" (p is the probability of the MPS; the probability of the MPS by definition starts at 0.5... in case of two symbols). The MPS Symbol is either a Zero or a One. The opposite of the MPS is the LPS (least probable symbol). This plot is basically axialy symmetric to 0.5. I decided to only plot one half and plot the redundancy only for the MPS - The most probable symbol. (because below 0.5 The MPS and the LPS basically change their meaning. I added 0.45 to 0.5 just for convenience, such that the symmetry around 0.5 can be seen.) If cou have a more probable symbol then that symbol is the one which produces more of its own symbols adjecent to each other. Having a p of 0.8 means that it produces 80% of the times the MPS symbol, and 20 percent the other (LPS). If you now check how long such a run-length of the MPS is, it follows a geometric distribution starting at 0 = p(LPS); 1 = p(MPS)*p(LPS); 2 p(MPS)*p(MPS)*p(LPS); and so on.

You can see how I calculated this graph, I digged for the code and added the octave code, after someone asked me, feel free to repoduce this graph using this code:

The code https://de.wikipedia.org/wiki/Benutzer_Diskussion:ThePacker

-- (can't logon...) - must check if i find my password. I never added my email... - ThePacker 19:41, 4 June 2022 (UTC)

Cryptic formulae

Back in 2005 a drive-by editor added formulae in this edit that I can't figure out how to interpret. This bit, where b means what we currently call M I think:

It uses a tunable parameter b to divide an input value into two parts: $q$, the result of a division by b, and $r$, the remainder. The quotient is sent in unary coding, followed by the remainder in truncated binary encoding. When $b=1$ Goloumb coding is equivalent to unary coding.

Formally, the two parts are given by the following expression, where $x$ is the number being encoded:

$q=\left\lfloor {\frac {\left(x-1\right)}{b}}\right\rfloor$

and

$r=x-qb-1$

The final result looks like:

$\left(q+1\right)r$

Note that $r$ can be of a varying number of bits.

What is this "final result" he speaks of, and what does that formula mean? Why the subtraction of 1 from x? Is he presuming that x is a natural number (> 0)? And why do we still not have a formula for the presumed geometric distribution related to the parameters of the code? The geometric distribution could be starting at 0 or 1. Dicklyon (talk) 23:28, 10 July 2021 (UTC)

I've revised that; got rid of the "final result" that I couldn't interpret. Working on a new figure to illustrate and explain. Dicklyon (talk) 03:20, 11 July 2021 (UTC)

@Matthiaspaul: it looks like you're the only knowledgeable editor who has touched this in recent years. Can you check what I'm doing? See also previous section. Dicklyon (talk) 04:38, 11 July 2021 (UTC)