From what I've read so far (which admittedly isn't a lot) the key drawback towards using the Fourier transform is that these tend to not be accurate due to rounding error, and hence not exactly lossless

Hmm actually you would probably use an integer DCT instead of the DFT. For lossless the quantization noise is taken care of in the residual coding. For lossy you would use MDCT which has overlapping windows to reduce the blocking effect. The main drawback of transform coding is cost.

Quote from: JapanAudio on 2010-11-19 23:10:21

Hmm actually you would probably use an integer DCT instead of the DFT. For lossless the quantization noise is taken care of in the residual coding. For lossy you would use MDCT which has overlapping windows to reduce the blocking effect. The main drawback of transform coding is cost.

Not really sure what you mean by "cost", but I think the actual problem with frequency domain lossless coding is that theres no obvious way to exploit the frequency domain representation to gain in compression without loss.  The main advantage of frequency domain coding in the MDCT or subband codecs is that it enables you to relatively easily compute the masking thresholds and then hide your quantization noise in frequency bins that are masked.  But if you don't have any quantization noise because your compression is lossless, I don't know that theres any point in transforming.

Because depending on your algorithm you can exploit correlation in the frequency domain, plus the data compaction properties of the DCT come in handy. You could also apply linear prediction in the frequency domain.

There are many possibilities, but usually transform coding is more costly in terms of cpu cycles (say encoding time).

First, I never said you would get better compression results with transform coding; I said that it was slower.

Second, real-time isn't really fast; I wouldn't want to wait 4 minutes to encode a 4 min song.

Nobody wants to wait 10x longer for a 1% compression increase.

So when I refer to cost, I mean that linear predictive coding is faster than transform coding for similar results. Nobody wants to wait 10x longer for a 1% compression increase.

I should add that you can't really compare the time and frequency domains to determine which is "better". Because if you use transforms you've got both domains at hand, in a way revealing the naturally occurring two-dimensional features of audio data.

But the problem is that no general theory of 'decorrelation' has been formulated to find patterns within a general audio signal. With transforms, you can potentially exploit redundancy in subbands, on wider time spans, etc.,

but the cost compromise is just too much for little to no improvement over the simple and fast LPC.

Whatever man, I don't even know why I answered your post to begin with. I don't really want to argue with you.

That being said, I believe it is only a matter of time before more efficient and novel algorithms replace the primitive linear glottal model, that leads to LPC, which was meant for speech coding in the first place.

Or for a 4 minute track, it would take 3.4 milliseconds!

Of course, if you want to do the MDCT, you'd have to pre/post rotate your data, which might add another millisecond to that runtime! Hope you can spare it while you wait 5 minutes an album for FLAC's linear prediction and entropy coding.

Can you rephrase this more coherently? I'm not sure if you're just being scatterbrained or really have no idea what you're talking about.

Also, a common flaw I see here on HA audio is that people tend to think only of PC-based applications of audio codecs. On portable devices with relatively weak processors, battery life is critical, and the industry is looking for codecs with minimum decoder complexity. Now take a guess why e.g. APE hasn't reached that market. Nobody likes it when your portable's battery is empty after playing two lossless songs (if it can play them at all).

... which also leads to reduced seekability. In addition, if we're talking about 1024-sample DCTs, the matrix involved will be so much larger than regular matrices used in LPC (I think 32x32 is the maximum for FLAC) that encoding will take significantly longer even if we're not using the DCT (which would be comparatively fast anyway).

What I was thinking of was more along the lines of applying the DCT then coding the results of the transform directly.

Don't know what you mean by 32x32 and reduced seekability. FLAC's default block size is 4096 samples. I don't think that computing the LPC filter in FLAC via autocorrelation, and then applying the filter, is much faster than doing a, say, 1024-sample (M)DCT.

If you partition the DCT spectrum and use an integer DCT, then that should be possible. In fact, IIRC, that's what HD-AAC is doing in pure lossless mode.

Regarding your question whether this is much more efficient than time-domain compression: that probably depends on the signal. For tonal signals (e.g. harpsichord), it might be. For speech, it probably isn't.

Chris

The idea behind partitioning the spectrum is subband analysis. You can decompose it into equal segments or use logarithmic spacing to model hearing more accurately.

Quote from: JapanAudio on 2010-11-21 23:32:15

The idea behind partitioning the spectrum is subband analysis. You can decompose it into equal segments or use logarithmic spacing to model hearing more accurately.

Please correct me where I'm mistaken, but we're talking lossless here, not a perceptual lossy format.

What is the benefit of modeling (or mirroring) human hearing?

Doesn't HD-AAC use a lossy core and encode the difference?

Also, what do you mean by partitioning the spectrum? If I'm understanding you right (coding parts of the spectrum separately), how would doing so improve compressibility?

Thanks for the input! Now here's another crazy idea (as if we don't have enough already ): if we could somehow separate the "speech" part (highly compressible with LPC) and the "tonal" part (more compressible with DCT+entropy coding), this should produce somewhat better compression than either alone right? (The difficulty probably lies in the separation part.)

Quote from: JapanAudio on 2010-11-20 03:29:45

That being said, I believe it is only a matter of time before more efficient and novel algorithms replace the primitive linear glottal model, that leads to LPC, which was meant for speech coding in the first place.

Actually, LPC is not that primitive after all, as I found out during my work. But you're right about the novel algorithms: an integer MDCT is used in HD-AAC (which by the way can also operate in pure-lossless mode).

Quote from: saratoga on 2010-11-20 04:38:20

Or for a 4 minute track, it would take 3.4 milliseconds!

Of course, if you want to do the MDCT, you'd have to pre/post rotate your data, which might add another millisecond to that runtime! Hope you can spare it while you wait 5 minutes an album for FLAC's linear prediction and entropy coding.

A little more polite and careful, please, saratoga! An (M)DCT of a waveform alone doesn't give you any compression, it's just a transform. So for a fair comparison, you would have to either compare only (M)DCT vs. LPC analysis and filtering, or compare (M)DCT + entropy coding vs. LPC + entropy coding. From my work experience in that field I can tell you that most of the time, entropy coding is more expensive that LPC or T/F transform, especially in the encoder. That taken into account, LPC- and transform-based codecs are probably quite close to each other speed-wise (with LPC-based codecs probably being a little faster on decoder side since usually, no analysis operation is needed there).

Also, a common flaw I see here on HA audio is that people tend to think only of PC-based applications of audio codecs. On portable devices with relatively weak processors, battery life is critical, and the industry is looking for codecs with minimum decoder complexity.

Now take a guess why e.g. APE hasn't reached that market. Nobody likes it when your portable's battery is empty after playing two lossless songs (if it can play them at all).

Correct. I was thinking along the lines of FLAC, which segments the time-domain prediction residual and adapts its entropy coder to each segment. You could do the same in the frequency domain, for example like JapanAudio suggested (actually, you could use any arbitrary segmentation if it gives good compression).

Isn't that what I said?  You "might add another millisecond" to the minutes you'll spend on the rest of the codec.

I'd like to point out that I wrote much of the current rockbox iMDCT, which is as far as I am aware the fastest embedded open source iMDCT, so I think I am well aware of these constraints

True. Anyway, it's not your fault that APE decoding is so expensive.  I remember an Athlon 900 MHz having problems decoding APE files with highest compression in real-time while surfing the web. That's expensive! Then again, the developer probably didn't spend too much thought on that when he came up with APE, not knowing/expecting that it would become so popular.