Video filtering with Fermat number theoretic transforms using residue number system

We investigate image and video convolutions based on Fermat number transform (FNT) modulo q=2^M+1 where M is an integer power of two. These transforms are found to be ideal for image convolutions, except that the choices for the word length, restricted by the transform modulus, are rather limited. We discuss two methods to overcome this limitation. First, we allow M to be an arbitrary integer. This gives much wider variety in possible moduli, at the cost of decreased transform length of 16 or 32 points for M<32. Nevertheless, the transform length appears still to be useful especially with block-based image and video filtering applications. We call these transforms the generalized FNT (GFNT). The second solution is to use a residue number system (RNS) to enlarge the effective modulus, while performing actual number theoretic transforms with smaller moduli. This approach appears to be particularly useful with moduli q₁=2¹⁶+1 and q₂=2⁸+1, which allow transforms up to 256 points with a dynamic range of about 24 bits. We design an efficient reconstruction circuit based on mixed radix conversion for converting the result from diminished-1 RNS into normal binary code. The circuit is implemented in VHDL and found to be very small in area. We also discuss the necessary steps in performing convolutions with the GFNT and evaluate the integrated circuit implementation cost for various elementary operations.