The Generation And Fast Algorithm Of Generalized Walsh Function In G Ordering

Based on Walsh functions, the Walsh transform has fast algorithms as like the fast Fourier transform (FFT). Due to the simple value for Walsh functions, the fast transform has the property of fast speed. Therefore, it can be widely used in signal processing and image processing. In history, the Walsh transforms with Hadamard (or H), Paley(or P), Walsh(or W) and X(or M) ordering are mainly discussed. But the Walsh transform with G ordering has not been well studied since it's presented recently. Walsh function in G ordering is symmetrical and needs few numbers of connection for its VLSI implementation. So it is good to apply it and worth to study.Generalized Walsh function is broadly used in multivalued logic design, pattern recognition and digital signal processing. Generalized Walsh function in G ordering is presented. It is generated with three kinds of technologies, taking three valued as an example. Based on the information of sequence code, it is generated with generalized rademacher function and the method of rotate right and generalized shift copy respectively. Based on matrix block copy , it is generated with Kronecker product. It turns out that the forms of Walsh function with G ordering generated by three different techniques coincide.Four kinds of fast algorithms, in which two is in-place and the other two is not, are designed with the method of matrix decomposition. When generalized Walsh transform only has two kinds of discrete value, it becomes Walsh transform. Then the four fast algorithms for generalized Walsh transform become fast algorithms for Walsh transfrom. And one of the in-place algorithms has appeared, but all the others do not. Finally, the performances of generalized Walsh function in G ordering and several other orthogonal transforms in application of Wiener filter are compared and analyzed.