walsh table for nxn matrix in C

Question 1

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:

enter image description here

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.

Question 2

Modified Your code: There are three things I did:

1) formatted with more blocks {...} for readability
2) initialized array a[100][100] for all elements using memset()

3) added an extra getchar() (my system uses that instead of getch() ), and commented clrscr()

It ran for 4x4 and 8x8 (but the output does not look correct, you have more work to do there):

main()
{

    /* Program variables
    Dimension variable, n
    Loop variables i,j
    Two dimensional array for walsh table a[100][100] */

      int n,j,i,a[100][100];
      //clrscr();
      // User input to display walsh table

      memset(a, 0, 100*100);
      printf("enter the size ");
      scanf("%d",&n);

      // Iterate rows from 0 to 'n'
      for(i=0;i<n;i++)
      {

      // Iterate columns from 0 to 'n' for each row 'i'
            for(j=0;j<n;j++)
            {
                if(i%2==1 && j%2==1) // for both i & j not divisible by 2, initialize array elements with -1
                {
                        a[i][j] = -1;
                }
                else if(i/2==1 && j/2==1)
                {  // for both i & j, if completely divisble by 2 and dividend is 1
                    if(j == 3 && i == 3)
                    {
                        a[i][j]=1;
                    }
                }
                else
                {
                        a[i][j] = -1;
                }
            }
            a[i][j] = 1;        // default case initialized to 1
      }
      a[3][3] = 1;

      // Output complete walsh table
      for(i=0;i<n;i++)
      {
          for(j=0;j<n;j++)
          {
          printf("\t%d",a[i][j]);
          }
          // go to next line after every row 
          printf("\n");
      }
      getchar();
      getchar();
}