EECS658 Fast Algorithms: Abstract: Wavelet Transforms in GF(p)

Eric Durant
Department of Electrical Engineering and Computer Science
The University of Michigan
Ann Arbor, MI, USA

Monday 13 December 1999


By extending the relationship between the DWT and the DFT over C to the NTT over GF(p), we find that the analog of the DWT is a wavelet transform in GF(p). System representations of this transform, such as filter banks, 2-circulant matrices, and a unitary transformation matrix are summarized. A detailed example with supporting MATLAB code is also given.


This paper presents a brief theoretical treatment of cyclic wavelet transforms in GF(p), where p is a Fermat prime [1]. Related practical and theoretical issues, such as principal square roots in GF(p) are also discussed. A detailed example is worked and MATLAB code is provided.


[1] Giuseppe Caire, Robert L. Grossman, and H. Vincent Poor. Wavelet transforms associated with Finite cyclic groups. In IEEE Transactions on Information Theory, number 4, pages 1157–1166, July 1993.