2
$\begingroup$

I am looking for (lossy or lossless) compression algorithms dedicated to complex signals. The latter could be composite data (like the left and right for stereo audio), a Fourier transformation, an Hilbert pair of signals...

[EDIT: I do apologize for the initial long and detailed answers] A little background: I have been working on real signal and image compression, and mildly on video and mesh coding. I have practiced adaptive lossless and lossy compression (RLS, LPC, ADPCM), Huffman and arithmetic coding, transforms (DCT, wavelets), etc. Using standard compression tools on each of the real and the imaginary parts is not the main aspect of the question. I am interested in compression-related specificities for complex data, for instance:

  • joint quantization of module and phase,
  • optimal quantization of 2D complex values: Loyd-Max is "optimal" for 1D data. I remember that 2D optimal quantization is generally more complicated. Are there 2D binnings dedicated to complex, or for instance Gauss integers?
  • entropy coding methods, arranging along complex "features" (angle, magnitude),
  • entropy calculation for complex data,
  • use of specific statistical tools (e.g. from Statistical Signal Processing of Complex-Valued Data: The Theory of Improper and Noncircular Signals)
  • integer transformations for Gauss integers.

I have not found much tools. My scarce references are:

I would be interested in more authoritative references. A compression file format dedicated to complex data would be a plus.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure I understand the point of this question. If you just join two arbitrarily related real signals to a complex signal, what kind of advantage do you expect from a complex encoding? I would expect some kind of complex structure to be present for a joint encoding to be sensible. So complex analyticity, complex boundedness, complex bandlimitedness, etc. Do you have a more specific use case maybe and an idea of what kind of answer you expect? $\endgroup$ – Jazzmaniac Nov 15 '16 at 8:56
  • $\begingroup$ @Jazzmaniac Excellent point. I became aware of the lack of context of my question reading the first answers. I have added some more background and details. Additional suggestions welcome $\endgroup$ – Laurent Duval Nov 15 '16 at 9:44
4
$\begingroup$

Complex signals are a special case of multidimensonal signals (where the dimension is two). A lossy approach tackling compression of multidimensional signals is vector quantization. A very good resource is the book:

"Vector Quantization and Signal Compression",

co-authored by Robert M. Gray.

Vector Qquantization is a classic lossy source coding technique that is used to quantize $M$-dimensional source vectors into a set of $N$-dimensional code vectors which is referred to as the codebook, and $N<M$. A scalar quantizer is a special case with $M = 1$.

A complex signal in general can be seen as two correlated sources. Of course, if you don't want to assume any correlation between the real and imaginary part, then the answer is trivial since the two sources can be compressed independently and separately (using the standard compression techniques of real signals).

If you are interested in information-theoretic aspects of lossy/lossless compression of correlated sources, Wyner-Ziv and Slepian-Wolf coding are the keywords. These schemes are refereed to as distributed source coding schemes. However, since a complex signal can be modeled by two correlated sources, they can be considered here as well.

Finally, for analytic signals, since the imaginary/real part can be perfectly reconstructed from the other one by using the hilbert transform, the compression problem boils down to compression of a single real signal, for which there are plenty of standard schemes.


In response to the updated question:

Loyd algorithm generalized for vector quentization is referred to as LBG Algorithm (abbreviation of the name of the authors of the following paper)

Y. Linde, A. Buzo and R. Gray, "An Algorithm for Vector Quantizer Design," in IEEE Transactions on Communications, vol. 28, no. 1, pp. 84-95, Jan 1980.

It was again extended in 1989 for entropy coded vector quantization:

P. A. Chou, T. Lookabaugh, R. M. Gray, “Entropy constrained vector quantization,” IEEE Transactions on Signal Processing, vol. 37, no. 1, pp. 3142, January 1989.

I can recommend visiting www.data-compression.com/vq for a descent explanation of the scheme. It works in a simple way:

  • Divide the vector space.
  • Update the partitions.
  • Repeat the procedure for the new partitions until the quantization error is acceptable.

At the end, all data points that belong to a partition are quantized to the coordination of the center of partitions. The centers are indexed such that to represent all quantized values only the index is stored/sent.

Animated illustration from the same website for 2D Gaussian source:

                            enter image description here

$\endgroup$
2
$\begingroup$

Personally, I'd assume that coders that work well on real-valued data would work well on the separated imaginary and real parts too – and after those, another round of trying to compress by exploiting the fact that I and Q very often will have very similar derivatives.

Thus, my first action would be to try a DPCM coder on the separated real and imaginary parts. If that doesn't fit your needs, then do DPCM on the interleaved results, then do the huffman. Alternatively, go first from $\Re\{z\}+j\,\Im\{z\}$ to $|z|+e^{j\angle z}$ and compress $|z|$ based on a simple DPCM, and $\angle z$ with an elegantly wrapping linear predictor (reminds me a bit of the title of the '97 paper you cite).

In fact, I'm trying to remember all the details, but we had an interesting discussion on the topic on the GNU Radio mailing list not so long ago (SDR users sometimes run into problems like having a hard time finding storage that can write 100MS/s of int16 complexes…). I remember looking at FLAC for the purpose, and then not writing any code. I wonder why that is. Anyway, I'd really try to convince flac to compress your samples as audio (maybe just simply stereo) and see how well linear prediction gets the most of your signal's entropy :)


EDIT I remember why I didn't look into FLAC: zstd came up and distracted me.

So: I went ahead and generated a sum of sinusoids and noise: Sum of sines + noise

and saved everything as interleaved signed complex int16.

Then, I did a quick

flac --force-raw-format --channels 2 --bps 16 --sample-rate $((50*1000)) --endian little --sign signed -8 -o samples.flac samples.complex_sc16

(faking a 50 kHz sampling rate... but as far as I can tell, the FLAC coder doesn't care – the sampling rate info is just used to tell potential audio players what sampling rate to use).

The result was a 31% compression over the 191 MB of original data. Not that bad!

Zstd, on noise-ridden data, of course isn't that effective - a mere 5% compression was achieved (which is really meagre, considering that of the 16 bit per I and Q, most of the time, maybe 10 are used, and very few samples even came close to the maximum integer values, indicating that there should be significant runs of 0 and 1 in the bitstream. Anyway, as soon as I switched of noise, the 191 MB were immediately reduced to 12 MB – strength of a dictionary-based compressor on periodic data, especially since zstd uses a "modern PC-sized" dictionary size (and not the "oh, 16kB is soooo much" of gzip). Flac didn't do much better than on the noise-ridden signal.

$\endgroup$
1
$\begingroup$

to losslessly compress audio the simplest way is to use LPC (the LPC coefficients would be stored and updated for each frame of audio) to predict a sample and encode the difference between the LPC prediction and the actual sample. that difference should be reasonably white (otherwise the LPC could use knowledge of that color and make a better prediction).

so the LPC delta output is pretty white, but still mostly gaussian. so then something like Huffman coding can be done on the delta values because the p.d.f. of those values is not Uniform, so the more likely values have few bits encoded than the less likely values.

no, for complex data, like an analytic signal, then it can be represented as

$$ \begin{align} a_x(t) &= x(t) + j\hat{x}(t) \\ \\ &= r_x(t) e^{j \theta_x (t)} \\ \end{align} $$

and $\hat{x}(t)$ is the Hilbert transform of $x(t)$.

and $ \omega_x(t) \triangleq \frac{d \theta_x(t)}{dt} $.

if the bandwidth of the analytic signal is low, then $r_x(t)$ and $\omega_x(t)$ will have much less bandwidth than the real signal $x(t)$. in that case, many fewer bits (and many fewer samples) can be afforded $r_x(t)$ and $\omega_x(t)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.