用於nxn矩陣的walsh表C

Question

我一直在嘗試理解n維的walsh表矩陣，因爲我需要編寫一個代碼來生成任意給定順序的walsh矩陣。到目前爲止，我沒有寫出工作代碼。任何人都可以幫助我的算法，還是建議一些關於我下面的程序：（它爲2×2和4×4，但未能爲8×8）

#include<stdio.h> 
#include<conio.h> 
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 
     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; 
     } 
     else     
       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"); 
     } 
     getch(); 
     } 

Answer 1

你應該尋找的沃爾什代碼生成的遞歸問題。首先你生成2x2;從中生成4x4等等。每次，下一個塊都是從前一個塊生成的，方法是在右上角和左下角象限中添加兩個較低階塊的副本，並在右下角添加兩個相反的塊象限。你可以通過創建一次矩陣來完成這個工作，並且通過增加塊大小來完成它。這是如何工作

UPDATED所以它產生的代碼，你看到的wiki上的1 -1版本;

UPDATED再次使其能夠輸入的矩陣大小和生成任意大小的沃爾什矩陣;包括各種錯誤檢查和其他很酷的技巧：

最終（？）更新 Ryyker指出，我的代碼中有一個內存錯誤。我找到並修復了它 - 並確認與valgrind對照。現在看起來工作正常。

#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... 
} 

輸出：

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 

更多信息參見http://my.fit.edu/~kostanic/Personal%20Communication%20Systems/ECE%205221%20-%20Lecture14.pptx - 從我採取了以下：

後記

的注意事項有關功能twoDmatrix()。我寫了這個函數，因爲沒有直接的方法來在C中分配一個未知大小的二維矩陣。所以這個函數創建了一個指向數組的指針 - 一個指針指向矩陣中的每一行;它還分配一塊內存 - 一個用於數組中的每個元素。然後它將一個指針與矩陣中每一行的起始位置關聯起來，以便您可以使用通常的W[i][j]索引訪問元素。這使得它看起來像數組的第一行非常長（它指向整個NxN塊），第二行比較短，等等。但這只是一個技巧，所以你可以用數組訪問數組的元素通常的語法。試想一下，你擁有一個充滿數字0到8一個3x3的陣列 - 那麼事情是這樣的：

pointer  values 
W[0]   0 1 2 
W[1]   3 4 5 
W[2]   6 7 8 

但看它的另一種方式是這樣的：

0 1 2 3 4 5 6 7 8 
^ W[0] 
     ^W[1] 
      ^W[2] 

這意味着的是，你可能訪問元素W[0][6] - 它的值將與W[1][3]相同，其值與W[2][0]相同。

當你不再需要這個功能時，你必須釋放兩塊內存 - 首先是數據塊，然後是指針塊。這是free2D（）函數的作用。

Answer 2

改性您的代碼：有三件事情我做：

1）格式化多個塊{...}爲了可讀性
2）初始化數組a[100][100]所有元素使用memset()

3）增加了額外的getchar()（我的系統使用的是不是getch()），並評論clrscr()

它跑了4x4和8x8（但輸出看起來不正確的，你有更多的在那裏工作）：

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(); 
}