Two n-point fast walsh transform sorting algorithms
Errol E. Wallingford, J.C. Culpepper · 2005
An in-place reversible sorting algorithm is used following a fast Walsh transform to sort coefficients into increasing sals followed by decreasing cals. This separation of the coeffic ients into those arising from odd sinelike time functions and those from even cosinelike functions is useful in signal processing applications. A second sort routine generates a relocating set for a remap sequency sorting. To be valid for all N this sort routine is done out-of-place. The separation of the transform and sort functions has resulted in simple implementations for each. To demonstrate the differences in the sort routines, transform results and their inverses are made on a linear ramp. For this application the transform results with sal-cal sorting has all zeros beyond the mid-point showing that, with the exception of the large d.c. term, the linear ramp is composed entirely of Walsh odd time functions.