On the Rudin–Shapiro transform

The Rudin–Shapiro transform (RST) is a linear transform derived from the remarkable Rudin–Shapiro polynomials discovered in 1951. The transform has the notable property of forming a spread spectrum basis for RN, i.e. the basis vectors are sequences with a nearly flat power spectrum. It is also orthogonal and Hadamard, and it can be made symmetric. This presentation is partly a tutorial on the RST, partly some new results on the symmetric RST that makes the transform interesting from an applicational point-of-view. In particular, it is shown how to make a very simple O(NlogN) implementation, which is quite similar to the Haar wavelet packet transform.