Parallelization of Methods to Calculate Walsh Spectra for Logic Functions
Bogdan J. Falkowski
Spectral methods based on the Walsh transform provide very efficient representation of logic functions that uncovers the properties unseen in their original domain. The techniques based on the Walsh transform are particularly useful for analysis, synthesis and testing of circuits with big amount of linear part. In this article, various methods of calculation of the Walsh transform for logic functions are discussed and implemented on parallel computer. In particular, a new algorithm that extracts parallelism feasible on SIMD architecture in calculation of Walsh spectral coefficient from reduced representation of logic functions in the form of an array of cubes has been proposed. Detailed studies of the SIMD architecture and an analysis of the mechanism to map parallel algorithm into the SIMD architecture have been carried out. The experimental results comparing parallel and sequential implementations of various algorithms calculating the Walsh spectra on the MasPar-2101 computer have been shown.