This project has moved and is read-only. For the latest updates, please go here.

What Complex8 or Complex16 or Complex<T>?

Jul 23, 2013 at 10:26 PM
I am working on a project measuring spectrum usage. We are using the USRP N200 hardware for gathering the data. The data is in "time domain" and we need to get it to "frequency domain" through a Fast Fourier Transform. Additionally, we receive the data as a Complex<byte> (byte real, byte imaginary). (Technically, it's just a byte[], and we treat the data as a Complex by handling it in pairs.)

At first blush, I thought Math.Net Numerics was going to save the day when I learned that it has FFT support. After installing and browsing the namespace and classes though, it appears that it only supports System.Numeric.Complex which uses doubles, and Complex32 which uses floats.

I am curious why Complex32 isn't generic, accepting different integral types? How much effort would it be to plug in either a Complex8 or a Complex<T> class and get it working, or is there a technical reason for not having gone that route?

Thanks!
Jul 23, 2013 at 10:28 PM
Of course, I meant the title to be, "What ABOUT..." if an admin has the rights to change it...
Jul 24, 2013 at 9:16 AM
Hi

There are quite a few reasons why it is implemented the way it is:

We actually don't provide the Complex type ourselves but use the one provided in the .NET Framework in System.Numerics. We only reimplement it for (and only for) our portable builds because System.Numerics is not available in some environments like Windows Phone. We do provide Complex32 because no such type is provided by the framework, but align its members with the Framework's Complex type for obvious reasons.

Then, other than C++ templates, C#/IL generics don't work well with generic arithmetic (because they're not "inlined"/resolved at compile/linker time) and all workarounds I'm aware of (in C#, F# is much better here with its inline keyword) are either very complicated or very inefficient. So we'd end up having to implement concrete implementations anyway like we do in linear algebra. Note that these types are structs, not classes, so they can't inherit from some common generic base class. They could implement a generic interface, but we cannot modify the Complex type from System.Numerics so this won't work either.

There's also a problem with the algebraic structure: byte, int, long etc. are integer types and thus do not form an algebraic field (e.g. they lack a multiplicative inverse). Indeed, integer and fixed-point arithmetics is very different from floating point arithmetics and needs a lot of extra care to make sure every intermediate value is well conditioned. Also a lot of basic routines are only provided for floating point types in the framework.

Interestingly it seems even FFTW, likely the most robust and fast FFT implementation by far, only supports floating point types.

All that being said, it's certainly possible to implement fixed-point and integer FFT. For example, see this paper. I actually think it would be interesting to support integer FFT in Math.NET, although it may better fit to our signal processing library as opposed to Numerics, as integer samples are quite common in signal processing.

In the meantime, would it be reasonable in your situation to simply convert your samples to floats to perform the transform? Or would you be able to help us implement proper integer FFT?

Thanks,
Christoph
Marked as answer by cdrnet on 10/3/2013 at 5:37 PM
Jul 24, 2013 at 10:50 PM
Christoph,

Thank you for your excellent reply. I now have a better understanding of the current design and challenges of implementing my "simple" suggestions. ;-) Unfortunately, the math is over my head, and my project schedule probably isn't padded enough for me to do the implementation. I will try converting from byte to double and wasting 8x the space.