Right-cyclic Hadamard coding schemes and fast Fourier transformsfor use in computing spectrum estimates in Hadamard-transformspectrometry

Two computationally efficient spectrum-recovery schemes were recently developed for use by Hadamard-transform spectrometers that have static and dynamic nonidealities in their encoding masks. These methods make use of a left-cyclic Hadamard encodement scheme and the ability to express the left-cyclic W_D matrix in factored form as W_D =ST_D. The matrix W_D describes the dynamic characteristics of and the encodement scheme for the mask. This paper focuses on the use of a right-cyclic Hadamard pattern to encode the mask and computationally efficient methods that can be used to obtain the spectrum-estimate. The major advantage of right-cyclic over left-cyclic encodement schemes is due to the resulting right-cyclic nature of both W _D and W_D^-1. Fast algorithms, such as a fast Fourier transform (FFT) or a Trench algorithm, that take advantage of the right-cyclic nature of W_D can be used to obtain W_D^-1 directly. In general, the number of mask elements is not an integer power of two, and non-radix-2 FFT's must be used to compute W_D^-1. Since W_D^-1 is right-cyclic, the vector-matrix product of W_D^-1 and the measurement vector can be expressed as a circular correlation and implemented indirectly via FFT's. With appropriate zero-padding of the vectors, radix-2 FFT's can be used for this computation. Various algorithms were used at each step in the overall computation of the spectrum-estimate, and the total computation times are presented and compared. The size of the mask is important in determining which algorithms are the most efficient in recovering the spectrum-estimate