The evolving generation and fast algorithms of Walsh transforms

Six orderings of Walsh function are derived evolutionally by means of "row copy" and "block copy". Two (Walshand Paley-ordering) are generated by row copy and other four (Hadamard-, X-, X^T- and G-ordering) are generated by block copy. X^T- and G-ordering are deduced by extending the concept of up-down shift symmetry to that of up-down mirror image symmetry. X^T-ordering is the transposed X-ordering, which is not symmetric as X-ordering; G-ordering is symmetric as the three known ones (Walsh- and Paley- and Hadamard-ordering). The four symmetric orderings construct an exactly symmetric Walsh function system. At last, two fast algorithms are proposed for G-ordering Walsh transform. The approaches introduced are applicable to other orderings Walsh transforms. Both algorithms have a regular recursive structure and are easy to be implemented on parallel computers. Furthermore, the method serves as a frame to design fast algorithms for discrete transforms.