Fast Walsh Transformation

800px-1010_0110_Walsh_spectrum_(fast_WHT).svg
In computational mathematics, the Hadamard ordered fast Walsh–Hadamard transform (FWHTh) is an efficient algorithm to compute the Walsh–Hadamard transform (WHT). A naive implementation of the WHT would have a computational complexity of O(N^2). The FWHTh requires only Nlog N additions or subtractions. It is easy to do a Fast Walsh Transform by hand. (Well, I say “easy,” then always struggle when I actually do it.) Let’s do the FWT of function f: (0 0 1 0 1 1 0 0): First note that f has a binary power length, as required. Next, each pair of elements is modified by an “in-place butterfly”; that is, the values in each pair produce two results which replace the original pair, wherever they were originally located. The left result will be the two values added; the right will be the first less the second. That is,

orginal 	0	0	1	0	1	1	0	0

Third		1 	1	-1	1	-1	-1	1	1
		^-------------------------------^
			^-------------------------------^
				^-------------------------------^
					^-------------------------------^
Second		0	0	0	2	2	2	-2	0
		^---------------^		^----------------^
			^---------------^		^---------------^
Second		0	2	0	-2	0	2	4	2
		^-------^	^-------^	^-------^	^-------^
Zero		2	-2	-2	2	2	-2	6	2

Code
====

/* Written by Giri
 * An implementation of Fast Walsh Algorithm */
#include "header.h"

/* A function to computer the FastWalshTransform */
long * FastWalshTransform ( long *f, ulong m1 ) {
	long  a, m = m1;
	ulong u, v, split, tempSplit, n = 1UL << m;

	for ( u = 0; u = 0; m--  ) {
    	split = 1UL << m ;
        for ( u = 0; u < n; u += 2 * split ) {
        	tempSplit = u + split;
			for ( v=u; v < tempSplit; v++ ) {
				a = f[v] + f[v + split];
				f[v + split] = f[v] - f[v + split];
				f[v] = a;
			}
		}
	} 
	return f;
}

int main ( ) {
	long *f;
	ulong m, i;
	printf ("Enter the number of variables in your boolean function : ");
	scanf ("%lu", &m);
	assert (m <= 30);
	ulong n = 1UL << m;
	f = allocate_long_table (m);
	for ( i = 0; i < n; i++ ) {
		printf ("Enter the value of [%lu] of boolean funciton: ", i);
		scanf  ("%ld", &f[i]);
		if ( f[i] != 0 && f[i] != 1 ) {
			printf ("Program accepts only binary values [0/1]\n");
			i = i - 1;
		}
	}
	f = FastWalshTransform (f, m);
	printf ("\n");
	for ( i = 0; i < n; i++ ) 
		printf ("%ld\t", f[i]);
	printf ("\n");
	return 0;
}

Sample output using the above given test case as an input.

$ ./question11 < testcase                                                                                                                                                       ✭ ✱
Enter the number of variables in your boolean function : Enter the value of [0] of boolean funciton: Enter the value of [1] of boolean funciton: Enter the value of [2] of boolean funciton: Enter the value of [3] of boolean funciton: Enter the value of [4] of boolean funciton: Enter the value of [5] of boolean funciton: Enter the value of [6] of boolean funciton: Enter the value of [7] of boolean funciton: 
2       -2      -2      2       2       -2      6       2
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s