Why does it take longer to compute the convolution in GF(2) when compared to an equivalent approach using FFT/IFFT?

I am trying to generate a lot of bits and code them using CRC-32. When comparing two approaches, convolution and FFT/IFFT, the answers are the same. However, the convolution approach takes significantly longer that the FFT/IFFT approach. For example, to generate 100 bits, convolution takes about 4 seconds while the FFT/IFFT takes only about 0.2 seconds. I would like to know the reason for the different computation times.

Answer 1

[MathWorks Support Team]

This is expected behavior. If implemented correctly, both approaches are equivalent. However, the FFT approach requires less mathematical operations and is therefore faster, especially for large data sets.

Answer 2

[Tasos Giannoulis]

While it is hard to give a precise answer without looking at the exact code that you are comparing, a possible explanation is that some MATLAB functions (e.g., FFT) may be particularly optimized and exploit multi-threading, while some other function do not. If you are using GFCONV, the implementation is in C++ but no multi-threading is exploited there.