Hacker News Reader

Comment by tombert | Hacker News Reader

Very tangential, but I think a lot about how modern video compression has gotten so unbelievably good that if we went back in time with AV1 or HEVC or something, I'm wondering if we could have had passable video streaming at 240p with something like an ISDN connection.

It would be a tight fit, but I still think within feasibility. We've gotten so good at shrinking video that it kind of feels like wizardry to me. Granted, I'm not sure there existed a computer in the 90s that was powerful enough to encode or decode it.

View on HN

Many years ago, "8088 Domination" demonstrated full motion video on the original 1981 IBM personal computer:

https://trixter.oldskool.org/2014/06/19/8088-domination-post...

As it turns out, the video was encoded in such a way that it could be played back using the display bandwidth of the original PC, BUT doing that encoding required a modern computer to perform in a reasonable amount of time.

Ah, just like the Amiga Juggler, was compressed on a VAX for playback on the Amiga. Full ray tracing, but the tracing and compression was Mini-computer.

This account describes the original raytracing and compression as taking place on an Amiga: http://www.etwright.org/cghist/juggler.html

Old school by now. Claude came up with this https://os8088.com/spotlight/video-player/

in action on 16Mhz 286 Packard Bell Victory, fullscreen at 30FPS https://www.youtube.com/watch?v=fEJPLT_rSRY

Well, that's with an at least 6x faster CPU, VGA, and a sound card. 8088 Domination has to play sound using the PC speaker, which is CPU intensive.

Tangential to the tangent, but turbo codes/LDPC are algorithms for transmitting data over unreliable links with optimal redundancy for a target error rate. They underlie much of modern wireless data transfer, and were known to be possible since Shannon, but nobody had figured out how to actually do it in practise. When they were invented in the '90s everybody reacted with disbelief at first!

Your characterization seems... incorrect to me.

Reed Solomon codes are higher quality but much older and requires a matrix solve (LU decomposition plus yadda yadda, equivalent to inverting a matrix)

Turbo codes / LDPC are IIRC O(n) instead of O(n^2.5) or whatever the matrix turns out to be.

-------

Reed Solomon codes are closer to the Shannon limit but are not scalable, slower than linear and require quadratically or cubically more compute for the data.

Turbo Codes and LDPC do a shittier job but far far faster. So that makes them actually more ideal in practice even if they are worse than Reed Solomon codes.

Reed-Solomon speed varies heavily. For the common case of worst-case recovery on moderately reliable foundations (e.g., file storage on disk) with reasonably sized codes, encoding is bottlenecked by RAM/disk/network bandwidth (wherever you're writing the results), typical decoding is blind concatenation, and worst-case decoding pulls an already solved matrix decomposition out of a cache to decode at line rate as well.

There's a trick in particular that allows you to rewrite the matmuls as a sequence of vectorized XORs, processing the same number of instruction words as other implementations (give or take control flow) but doing just a stream of zero-data-dependency vectorized math with lots of execution unit support. If you're feeling fancy you can do CSE and also choose the matrix constants minimizing XOR count.

Even without that, just basic AVX2 tricks get you a few GiB/s.

Unless the more expensive matrix math you're referring to is supposed to have n be the size of the code rather than the size of the data?

> and worst-case decoding pulls an already solved matrix decomposition out of a cache to decode at line rate as well.

I think this line says everything about your assumptions.

RAID-6 or other filesystems use extremely small ReedSolomon codes so these caching methods are possible.

But let's say you have a moderately sized (well, moderate for LDPC anyway) 65535-sized Reed Solomon problem (the maximum Reed Solomon that fits in 2^16 bits). Even with just 1% redundancy that's 655 parity.

Now consider the possible errors to solve for: 20 erasures means you have ~65535 choose 20 combinations of matricies to cache.

Or roughly 10^77 matricies you need to pre solve and cache to handle 20 erasures. Aka basically impossible.

----------

Now if you have 40 hard drives and are dealing with 3 or 4 errors tops, well sure caching is good and solves everything.

Reed Solomon is a perfect Maximally Distance code. For small n it's perfect.

For larger or even just moderate N (kilobytes for packets), it's too unwieldy. LDPC and Turbo Codes (which are imperfect codes) fill in the gap and allow for larger sizes as long as you give up on perfection.

Hm, I think I see. You're proposing using larger codes for larger data sizes? (as opposed to, e.g., the drive case where you typically have a stripe of data and assume that the failure mode to worry about is losing a whole hard drive, spreading stripes across drives)

Interestingly, for a lot of bit flip probabilities, iterating a smaller code has little additional overhead and better error handling (lower chance of that longer message having an uncorrectable error). With a 10% bit flip chance, even a 253+2 code over GF256 looks attractive comparatively (horrible overall, but better than the proposed larger code; I think your code makes more sense in practical regimes).

Basically yeah.

Ethernet frames are in the 1500 bytes MTU region. Maybe jumbo frames in the 8000 bytes or so.

Traditionally, "Fire Codes" could provide error correction at high speed over the whole packet (https://en.wikipedia.org/wiki/Burst_error-correcting_code#Fi...), not as well as Reed Solomon (or LDPC/Turbo codes), but that should give you an idea that the 1000 to 8000 bytes of "error corrected data" is actually quite pragmatic in the real world (ie: a lot of Cisco switches or routers that rely upon Fire Codes as forward error correction).

Note: A 32-bit fire code could only protect from errors that exist ALL within a singular 32-bits "burst". Its a "bad" code but very high speed. Fire Codes can never protect against two random errors spread far away, its "purely" a burst error correction scheme.

As we look towards more recent ethernet standards (ex: 802.11), they tend to use LDPC or Turbo Codes instead. I don't know the MTU of 802.11 but I assume its also in the 1000 to 8000 bytes region.

65535-sized is the limits to Parchive, which uses 16-bit Reed Solomon. It doesn't grow quite to that size in practice, but you're still dealing with error correction (or erasure-correction) codes far larger than what happens in RAID6 or other such scenarios.

---------

All are pragmatic. But the region where Turbo Codes / LDPC excels at are the much much larger codes where Reed Solomon's O(n^2.5) (or something) is a disqualification. I'd imagine that if "Pararchive" were rewritten with today's technology, it'd be a Turbo Code or LDPC.

I don't see how classic RS codes could beat Turbo Codes (or LDPC). One of the key innovations of the latter is that they handle soft decoding; i.e., different levels of uncertainty of the incoming bits. It's much better to say that you're only 51% confident that a bit is 0 (when it should be 1) than 100% confident! This is especially important for analog systems (like radios) where the incoming bits naturally come with a confidence value.

There are soft versions of RS codes, but these came much later and use the same iterative techniques that Turbo/LDPC decoders use.

That's irrelevant for the discussion of the Shannon Limit.

Reed Solomon codes are literally perfect, or more mathematically they are Maximum Distance Codes (https://en.wikipedia.org/wiki/Singleton_bound)

Turbo Codes and LDPC are provably imperfect, failing this property. However, they are very close to perfect (like 99.999999% perfect in practice).

Now the issue with Reed Solomon is that matrix factorization / effective matrix inverse. It's basically impossible to run Reed Solomon above say, 16 bits or 65536 elements or so (2 bytes at that point so 128kB). Because the matrix to solve this would be 65536 x 65536 x 2 bytes or like 8Gb or something.

Hmmm, I guess modern computers can handle 8GB lol. But you get the gist, the O(n^2) is a problem.

LDPC and Turbo Codes are linear. So a 4MB LDPC is gonna be you know... Actually possible on modern computers... While a 4MB Reed Solomon Code will need some number of exabytes to just build the damn decoding matrix. (32 bits times 4MB squared or something like that)

We had video conferencing on a single BRI (128k) with g728 and h264. It was CIF resolution so yes it is possible. And with that loss free ISDN connection the experience wasn't actually that bad. Though this was in the early 2010s where there was still a surprisingly large amount of ISDN around

I wonder where you'd hit the performance limits vs the algorithmic improvements. On our family pentium 120 playing an mp3 in Winamp took 10-15% of the CPU, so I'm not sure how much headroom there'd be.

But anecdotally I'll share that one of my brother's college roomies was a consultant for RealVideo and was behind their initial codecs. He came back to them with algorithmic improvements a bit later and they just cold shouldered him saying the existing codec was good enough.

So who knows if the biz side folks at the time would have even seen value in better codecs, as unbelievable as that seems to us now in the streaming and zoom call world.

> He came back to them with algorithmic improvements a bit later and they just cold shouldered him saying the existing codec was good enough.

I was involved in dial-up era 'postage stamp' video streaming. 240 pixels in 256 colors and it felt like visiting the future. Good times :-).

> who knows if the biz side folks at the time would have even seen value in better codecs

As someone who gradually went from code to the biz side, it's pretty likely they did understand it was better (at least at some levels of 'they'). A lot of times, saying "thanks, but what we have is good enough", especially to an outside contractor, isn't a technical or value judgement. It's more of a generic 'not interested right now'.

Consumer streaming as a business didn't really happen on one linear ramp. There was a period in the mid-90s I call 'proto-streaming' where there was a lot of early-adopter excitement and experimentation; but it mostly died out and then got rebooted a few years later. Although Real Networks as company did bridge the two eras, it was rough and they survived on corporate training use cases. The streaming reboot is the ramp that can be roughly traced through to today.

The reason proto-streaming didn't take off wasn't the early codecs, although it's true they weren't good enough yet to succeed. It was that the business models, content supply and distribution infrastructure weren't able to scale yet. So, Real Network's reply may have been the polite shorthand for an internal mtg that was more like a VP ranting "That's great but I got three fires burning the building down right now - and that ain't one of 'em!"

> Granted, I'm not sure there existed a computer in the 90s that was powerful enough to encode or decode it.

In software, quite possibly not[0].

But I'm sure we could have built hardware decoders that were up to decoding AV1 or HEVC back in the 90s no problem, had those codecs existed at the time.

[0] Somewhat later than the timeframe we're talking about, but I remember with pain the moment I realised my 600MHz Athlon, with 256MB RAM and 32MB GeForce 256 video card, was thoroughly obsolete because it couldn't decode and play the original Half Life 2 preview without stuttering, screen tearing and, indeed, crashing.

When meta released their EnCodec neural net audio compression codec I thought about how the 48khz stereo examples, compressed down to 6 kbps, sounded better than I remember streaming Internet Radio sounded like circa 2003, and would have been able to be streamed realtime, no buffering, on a 14.4 kbps dial up modem (what I was rocking at the time) with a bit of bandwidth to spare for browsin' teh warez sites and .... based on some napkin calcs and assuming a little MMX instruction magic I think completely possible to run the neural net decoder fully real-time on a period-correct AMD Athlon XP 2500+ Barton (overclocked to a 3200+ of course, as all did!).

Man that would have felt like magic...

I'm having trouble finding it but there was an article a while back comparing mp3 speed gains from hardware and software. The hardware was getting better at the pace of Moore's law but the (de)compression speeds for mp3s were far outpacing it, showing that mp3 decoding optimizations were giving orders of magnitude more speedup.

I think this is a common trend for algorithms that are in wide use, where you have Moore's law like behavior on the hardware side and then also software optimizations that give their own order of magnitude speedups.

h264 was used in a homebrew port of Dragons Lair for the Nintendo 64: https://www.youtube.com/watch?v=i89f_CMn7bw

You can technically have some then-contemporary FMV titles run on N64 with a 64MB cart. The hardware lends itself to it because it has the RSP, a secondary MIPS processor with re-programmable microcode. But the best video compression we had at the time was MPEG-2, which just wouldn't cut it.

To be fair, the N64 port of Resident Evil 2 is still unbelievably cool and impressive, even being stuck with MPEG-2.

Fairlight made an Amiga demo called "242" in 1993 which featured a few minutes of "full motion video" on a single floppy disk.

It was heavily compressed, monochrome, low frame rate, but used a clever upscaling algorithm on the frames to make it watchable.

https://youtu.be/wAJx5Ud0pLc

Though perhaps doing it on the Amiga is cheating. It was overpowered for its time.

I remember that Nickelodeon had a contest where the winner was given a videophone and was part of some gameshow. I suspect it ran on ISDN.

Edit: There was also video CD, but that was higher bandwidth than ISDN. I also used to download South Park episodes over my dialup modem. They weren't quite real time (IE, it took longer than the playback time to download,) but they were a low multiple. (IE, a 20 minute episode took ~30-40 minutes to download).

See too ISDN[0] album by The Future Sound of London.

[0] https://en.wikipedia.org/wiki/ISDN_(album)

> I remember that Nickelodeon had a contest where the winner was given a videophone and was part of some gameshow. I suspect it ran on ISDN.

I won a copy of Sonic the Hedgehog in that contest! AFAIK, it was just a retail copy and a letter; the game might still be at my parents' house, but I certainly don't have the letter. I was not selected to be on the show or anything. I remember watching the scrolling rules when they were doing the promotion and writing down a couple bits of the address every time.

Actual video CD is over a megabit per second. If you were downloading at half real time over a modem it wouldn't have been nearly as many bits, though maybe it was still MPEG 1? A lot of south park downloads were RealVideo, two generations more advanced than VCD (and two less advanced than HEVC).

They were RealVideo, very low bitrate

I've seen this in reality - compare the sound of an XM radio from 2003 to a modern one, same codec, same symbol rate, better audio quality. The same is true on digital two way radio (DMR, P25, TETRA, etc) the quality has improved because we can make the codecs do more intensive work, because the hardware is faster.

then why is voice calling still awful? in the 90s they made advertisements for "crystal clear voices" for their mobile networks, these days it is still a pipe dream...

Voice calling has several issues.

a) it's a legacy product that operators don't care about anymore.

b) latency is important for voice, but modern voice calls have terrible latency. POTS was digitized (for T1/PRI) with g.711 which provides a 8kHz sample rate and 13 or 14 bit samples encoded down to 8 bit. PRI lines were multiplexed one sample at a time. There's a small amount of algorithmic delay, but not much.

Modern voice calling is packetized, and most systems have packets of at least 20ms, you have more encode/decode time, you probably have a significant sampling buffer, and you may have to wait for network access, so the receiver needs to add a jitter buffer to manage that. Additionally, echo cancelation needs processing time, and it's also harder with longer latency. Some systems use longer packet times to reduce network overhead.

c) codecs: g.711 has a terrible pass band, GSM codec takes the same inputs and compresses it harder. g.722.2 (amr-wideband) is better, but it requires proper call setup and that is problematic for calls from one carrier to another. If you're calling via apps, there's potential for more flexibility, but you likely get whatever the developer thought was good enough.

Full rate EVRC sounded amazing, even back then.

GSM.. the added comfort noise was weird to me the first time I heard it while roaming.

it depends on your carrier, I find voice quality to be great on cell calls, unless its verizon.

Wouldn’t you still need the CPU horsepower to decode it?

Read the last sentence of my comment :)

That sentence kind of makes the rest of it moot, though? Everyone knows HEVC and AV1 on bare (unaccelerated hardware) is rough even on modern machines.

It's rough if you're trying to decode 4K.

320x240 is less than 1% the size of 3840x2160

I don't think it does. It was only making the point that by at least one dimension it's conceivable that modern video could be sent over old connections because of modern advancement in compression.

In an alternate universe where HEVC existed in the 90's, conceivably intel could have included hardware to assist in decoding it.

Bill Joy once said in an interview that if you look at scientific computing it wasn't just hardware that advanced at a consistent rate, software also consistently made large speed gains over time.

He is not the only one...

https://holmesrpi.org/Books/NumComp2/WebPages/NumComp/Is%20T...

h.264 is shockingly clever when you get into the nitty gritty. The core transform is a bit like a jpeg frequency transform, but is designed to run entirely in 16 bit integer maths and on 4x4 blocks. Ergo, it would run on MMX.

So, in short, probably. Particularly if you could get a hardware accelerated surface that transformed YUV into RGB.

Well, those modern codecs also take a lot more compute and memory to both decode and encode..

Reply on news.ycombinator.com