Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

H.264 is Magic

sidbala.com

Post reply on HN
Print view View original

141–150 of 230 posts

Re: H.264 is Magic

#141

Post by Dylan16807 »

nightcracker wrote: post #110
agumonkey wrote: post #105

Earlier quoted context omitted.

I never learned AC. It's on my overflowing stack of thing to read about.

AC is conceptually stupidly simple. All you do is encode a string of symbols into a range of real numbers. To start your range is [0, 1). For each symbol you want to encode you take your range and split it up according to your probabilities. E.g. if your symbols are 25% A, 50% B and 25% C, then you split up that range in [0, 0.25) for A, [0.25, 0.75) for B and [0.75, 1) for C. Encoding multiple symbols is just applyi…

Or on a more abstract level to compare to Huffman encoding: Huffman turns each symbol into a series of bits like "011". Arithmetic encoding lets you use fractional bits.

A Huffman tree for digits might assign 0-5 to 3 bits and 6-9 to 4 bits. Encoding three digits will use on average slightly more than 10 bits. Using AC will let you give the same amount of space to each possibility, so that encoding three digits always uses less than 10 bits.

Re: H.264 is Magic

#142

Post by andrepd »

qwertyuiop924 wrote: post #133
chrisseaton wrote: post #106

Earlier quoted context omitted.

> you would just transmit "H_10" with the universally agreed upon knowledge that "H" is "Heads" and "_" is number of times. Yes I get that the alphabet is already agreed upon. But if I only transmit H or T (uncompressed) that's just one bit needed per symbol. So I can transmit HHHHHHHHH in ten bits. If I introduce this simplified compression to the system and add 0-9 to the alphabet, that now needs four bits per symb…

But actually, no. Because you could set up HTTHTTTHHHHHHHHHH the format like this: 01001000 11001010 That's sixteen bits for 17 coinflips. With no continuous sequences longer than seven, this format takes up one extra bit every seven flips. How does it work? The first bit is a sign bit. If it's zero, the next seven bits are raw coinflips, 0 for tails, 1 for heads. If it's one, the second bit signifies whether the nex…

I know that, the point is that this kind of stuff needs some thought, it's not so simple as "HTHTHTHT" = "HT five times". The article kind of glosses over that.

Re: H.264 is Magic

#143

Post by Dylan16807 »

titanomachy wrote: post #138
nightcracker wrote: post #110

Earlier quoted context omitted.

AC is conceptually stupidly simple. All you do is encode a string of symbols into a range of real numbers. To start your range is [0, 1). For each symbol you want to encode you take your range and split it up according to your probabilities. E.g. if your symbols are 25% A, 50% B and 25% C, then you split up that range in [0, 0.25) for A, [0.25, 0.75) for B and [0.75, 1) for C. Encoding multiple symbols is just applyi…

Nice explanation. Can you explain how to remove ambiguity relating to string length? "0" = 0.0b = 0 falls in the range [0,0.25) so it's a valid encoding for "A"; but isn't it also a valid encoding for "AA", "AAA", etc.? AA = [0,0.25) * [0, 0.25) = [0, 0.125), and so on. It seems that adding "A"s to a string in general doesn't change its encoding.

You either reserve a symbol for "end of stream" or externally store the length.

It's the equivalent to pretending a Huffman stream never ends and is padded with infinite 0s.

Re: H.264 is Magic

#144

Post by titanomachy »

dluan wrote: post #109

By the way, this is an incredible example of scientific writing done well. It's very tangible jelly-like feeling that the author clearly has for the topic, conveyed well to the readers. This whole thread is people excited about a video codec!

> This whole thread is people excited about a video codec

That's not really a weird thing on HN though. Video codecs are exactly the kind of thing that we get excited about.

Re: H.264 is Magic

#145

Post by qwertyuiop924 »

andrepd wrote: post #142
qwertyuiop924 wrote: post #133

Earlier quoted context omitted.

But actually, no. Because you could set up HTTHTTTHHHHHHHHHH the format like this: 01001000 11001010 That's sixteen bits for 17 coinflips. With no continuous sequences longer than seven, this format takes up one extra bit every seven flips. How does it work? The first bit is a sign bit. If it's zero, the next seven bits are raw coinflips, 0 for tails, 1 for heads. If it's one, the second bit signifies whether the nex…

I know that, the point is that this kind of stuff needs some thought, it's not so simple as "HTHTHTHT" = "HT five times". The article kind of glosses over that.

Well, yes. Many programmers have trouble mapping ideas into bits: imagine how hard it is for people aren't in programming?

Re: H.264 is Magic

#146

Post by LASR »

dluan wrote: post #109

By the way, this is an incredible example of scientific writing done well. It's very tangible jelly-like feeling that the author clearly has for the topic, conveyed well to the readers. This whole thread is people excited about a video codec!

Thank you! It means a lot to me. Yes, I try to convey my sense of excitement about technology to other people.

Re: H.264 is Magic

#147

Post by eevilspock »

chrisseaton wrote: post #106
deanCommie wrote: post #102

Earlier quoted context omitted.

Not really - the knowledge of what an alphabet can be universally agreed upon and doesn't need to be transmitted with the data. The metaphor here is that software and hardware-based decoding can now be much more powerful because the hardware is more powerful than it used to be. And of course the truth is you would just transmit "H_10" with the universally agreed upon knowledge that "H" is "Heads" and "_" is number of…

> you would just transmit "H_10" with the universally agreed upon knowledge that "H" is "Heads" and "_" is number of times. Yes I get that the alphabet is already agreed upon. But if I only transmit H or T (uncompressed) that's just one bit needed per symbol. So I can transmit HHHHHHHHH in ten bits. If I introduce this simplified compression to the system and add 0-9 to the alphabet, that now needs four bits per symb…

You are entirely missing the point. His purpose isn't to give the reader a rigorous mathematical understanding. It is to convey a concept. It is an analogy, not a proof. And his analogy is perfectly good. Just do it: say "HHHHHHHHHH" and say "ten tosses, all heads" and get back to me which one transmits the info to another human in more compact form.

"To another human" is the key phrase, and sometimes I wonder if HN is populated with humans or androids. No offense intended to androids with feelings.

Re: H.264 is Magic

#149

Post by optimuspaul »

I enjoyed this for the most part and even learned a little. But it started out very simple terms and really appealing to the common folk. But then about halfway through the tone changed completely and was a real turn off to me. It's silly but this "If you paid attention in your information theory class" was the spark for me. I didn't take any information theory classes, why would I have paid attention? I don't necessarily think it was condescending, but maybe, it's just that the consistency of the writing changed dramatically.

Anyway super interesting subject.

Re: H.264 is Magic

#150

Post by syastrov »

An enjoyable, short and to the point article with many examples and analogies. But my favorite part was this:

"Okay, but what the freq are freqX and freqY?"

Post reply on HN