Deconvolution using Number Theoretic Transforms

JuliaDSP / Deconvolution.jl

A Julia package for deconvolution of digital signals

https://juliadsp.github.io/Deconvolution.jl/stable/

Other

48 stars 11 forks source link

Deconvolution using Number Theoretic Transforms #2

Open hrj opened 6 years ago

hrj commented 6 years ago

Hi,

I am a complete n00b to Julia and I am not a mathematician. While researching about deconvolution I stumbled upon these papers:

Precise deconvolution using the Fermat number transform
and k-dimensional error-free deconvolution using the fermat number transform which is an extension of the above by the same author.

The advantages of these methods are speed and deterministic behaviour (because they use only integer arithmetic). I don't think I can learn Julia and implement them at the same time in Julia.

Would you be interested in implementing them?

thanks, HRJ

giordano commented 6 years ago

Thank you for the pointer. Would be cool to have other methods to perform deconvolution, besides Wiener method. However, I don't have the time to work on this, so any help would be welcome.

hrj commented 6 years ago

BTW, there's one method based on Residual Number System and NTTs as described in this paper. It affords more flexibility in the choice of the prime numbers compared to the papers linked earlier, at the expense of more calculations.

jakubwro commented 4 years ago

I read these papers and I am interested in implementing this as they promise to eliminate ringing in the solution. If you have more resources about this topic please share.

jakubwro commented 4 years ago

To implement this we need a set of transforms analogous to fft / ifft. The most important is Fermat Number Transform, but also Mersenne Transform and general Number Theoretic Transform would be useful. I started to implement them (https://github.com/jakubwro/NumberTheoreticTransforms.jl). Please let me know if you think I am duplicating effort, I cannot see nothing similar in existing Julia packages.