You should be looking at the generation of a Walsh code as a recursive problem. First you generate the 2x2; from that you generate the 4x4, etc. Each time, the next block is generated from the previous one by adding two copies of the lesser-order block in the top-right and bottom-left quadrant, and its inverse in the bottom right hand quadrant. You can do this by creating the matrix once, and working your way through it in increasing block sizes. Here is how that works
UPDATED so it produces the 1 -1
version of the code that you saw on wiki;
UPDATED AGAIN to make it capable of taking an input for the size of the matrix and generate a Walsh matrix of arbitrary size; includes all kinds of error checking and other cool tricks:
FINAL(?) UPDATE Ryyker pointed out that there was a memory error in my code. I found and fixed it - and checked it with valgrind
to be sure. It seems to be working fine now.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int **twoDmatrix(int m, int n) {
// create a 2D matrix of arbitrary dimensions
int ii, **M;
M = malloc(m * sizeof(int**));
M[0] = malloc(m*n*sizeof(int*));
for(ii=1; ii<m; ii++) {
M[ii] = M[0] + ii * n;
}
return M;
}
void free2D(int** M) {
// free memory allocated by twoDmatrix()
free(M[0]);
free(M);
}
int isPow2(int n) {
// return 1 if the argument is a valid (positive) power of 2
if(n<=1) return 0;
while(n>1) {
if (n%2==1) return 0;
n = n/2;
}
return 1;
}
void emptyBuf(void) {
while(getchar()!='\n');
return;
}
int main(void) {
int **W;
int N;
int power = 1;
int i,j,k,l,p=0;
while(1==1) {
printf("enter the size of the matrix - must be a positive power of 2\n");
if(scanf("%d", &N)!=1) {
printf("unable to scan input\n");
emptyBuf();
continue;
}
if (!isPow2(N)) {
printf("%d is not a valid power of 2\n", N);
continue;
}
break; // valid input: go on
}
W = twoDmatrix(N,N); // allocate memory for 2D matrix
W[0][0]=1; // this is the 1x1 Walsh code...
while (power < N) {
for(i=0; i<2; i++) {
for(j=0; j<2; j++) {
if (!(i==0 && j==0)) {
for(k=0; k<power; k++) {
for(l=0; l<power; l++) {
if (i==1 && j == 1) {
W[i*power+k][j*power+l] = -W[k][l]; // invert signal
}
else {
W[i*power+k][j*power+l] = W[k][l]; // copy signal
}
}
}
}
}
}
power *=2; // double matrix and repeat
}
// print out result
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
printf("%2d ", W[i][j]); // <<<<< updated
}
printf("\n");
}
free2D(W); // always remember to free your memory...
}
output:
enter the size of the matrix - must be a positive power of 2
5
5 is not a valid power of 2
enter the size of the matrix - must be a positive power of 2
3
3 is not a valid power of 2
enter the size of the matrix - must be a positive power of 2
0
0 is not a valid power of 2
enter the size of the matrix - must be a positive power of 2
-4
-4 is not a valid power of 2
enter the size of the matrix - must be a positive power of 2
asdf
unable to scan input
enter the size of the matrix - must be a positive power of 2
asdfasdfasdfasdf
unable to scan input
enter the size of the matrix - must be a positive power of 2
16
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1
1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1
1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1
1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1
1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1
1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1
1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1
1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1
1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 -1 1 -1 1
1 1 -1 -1 1 1 -1 -1 -1 -1 1 1 -1 -1 1 1
1 -1 -1 1 1 -1 -1 1 -1 1 1 -1 -1 1 1 -1
1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1
1 -1 1 -1 -1 1 -1 1 -1 1 -1 1 1 -1 1 -1
1 1 -1 -1 -1 -1 1 1 -1 -1 1 1 1 1 -1 -1
1 -1 -1 1 -1 1 1 -1 -1 1 1 -1 1 -1 -1 1
For reference see http://my.fit.edu/~kostanic/Personal%20Communication%20Systems/ECE%205221%20-%20Lecture14.pptx - from which I took the following:
POSTSCRIPT
A note about the twoDmatrix()
function. I wrote this function because there is no direct way to allocate a 2D matrix of unknown size in C. So this function creates an array of pointers to int
- one pointer for each row in the matrix; and it also allocates a block of memory - one for each element in the array. It then associates one pointer with the start of each row in the matrix, so that you can access the elements with the usual W[i][j]
indexing. This makes it look like the first row of the array is really long (it points to the entire NxN block), the second row is a little shorter, etc. But it's just a trick so you can access the elements of the array with the usual syntax. Imagine that you have a 3x3 array filled with the numbers 0 to 8 - then things look like this:
pointer values
W[0] 0 1 2
W[1] 3 4 5
W[2] 6 7 8
But another way of looking at it is this:
0 1 2 3 4 5 6 7 8
^ W[0]
^W[1]
^W[2]
What this means is that you could access the element W[0][6]
- its value would be the same as W[1][3]
which again is the same as W[2][0]
.
When you no longer need the function, you have to free the two blocks of memory - first the data block, and then the pointer block. This is the role of the free2D() function.