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-, XT- and G-ordering) are generated by block copy. XT- and G-ordering are deduced by extending the concept of up-down shift symmetry to that of up-down mirror image symmetry. XT-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.
展开▼
