walsh table pour nxn matrix en C

Question

J'ai essayé de comprendre la matrice de table de Walsh pour n-dimension puisque je dois écrire un code qui génère la matrice de walsh pour n'importe quel ordre donné. J'ai jusqu'à présent échoué à écrire un code de travail. Quelqu'un peut-il me aider avec l'algorithme, ou suggérer quelque chose au sujet de mon programme ci-dessous: (cela fonctionne pour 2x2 et 4x4, mais échoue pour 8x8)

#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

Vous devriez regarder à la génération d'un code de Walsh comme un problème récurrent . D'abord vous générez le 2x2; à partir de ce que vous générez le 4x4, etc. Chaque fois, le bloc suivant est généré à partir du précédent en ajoutant deux copies du bloc d'ordre inférieur dans le quadrant supérieur droit et inférieur gauche, et son inverse en bas à droite quadrant. Vous pouvez le faire en créant la matrice une fois et en la parcourant en augmentant la taille des blocs. Voici comment cela fonctionne

MIS À JOUR afin qu'il produise la version 1 -1 du code que vous avez vu sur wiki;

MISE À JOUR pour le rendre capable de prendre une entrée pour la taille de la matrice et générer une matrice de Walsh de taille arbitraire; comprend toutes sortes de vérification d'erreurs et d'autres astuces cool:

FINAL (?) MISE À JOUR Ryyker a souligné qu'il y avait une erreur de mémoire dans mon code. J'ai trouvé et réparé - et vérifié avec valgrind pour être sûr. Cela semble fonctionner correctement maintenant.

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

sortie:

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 

Pour voir référence http://my.fit.edu/~kostanic/Personal%20Communication%20Systems/ECE%205221%20-%20Lecture14.pptx - dont je pris les éléments suivants:

POSTSCRIPT

Une note sur la fonction twoDmatrix(). J'ai écrit cette fonction parce qu'il n'y a aucun moyen direct d'allouer une matrice 2D de taille inconnue en C. Donc cette fonction crée un tableau de pointeurs à int - un pointeur pour chaque ligne de la matrice; et il alloue également un bloc de mémoire - un pour chaque élément dans le tableau. Il associe alors un pointeur au début de chaque ligne de la matrice, de sorte que vous pouvez accéder aux éléments avec l'indexation W[i][j] habituelle. Cela donne l'impression que la première rangée du tableau est vraiment longue (elle indique le bloc NxN entier), la deuxième rangée est un peu plus courte, etc. Mais c'est juste une astuce pour que vous puissiez accéder aux éléments du tableau avec le syntaxe habituelle. Imaginez que vous avez un tableau de 3x3 rempli avec les chiffres de 0 à 8 - alors les choses ressemblent à ceci:

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

Mais une autre façon de regarder est la suivante:

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

Ce que cela signifie est que vous pourrait accéder à l'élément W[0][6] - sa valeur serait la même que W[1][3] qui est de nouveau le même que W[2][0]. Lorsque vous n'avez plus besoin de la fonction, vous devez libérer les deux blocs de mémoire - d'abord le bloc de données, puis le bloc de pointeur.C'est le rôle de la fonction free2D().

Answer 2

modifié Votre code: Il y a trois choses que j'ai:

1) en forme avec plusieurs blocs {...} pour une meilleure lisibilité
2) tableau initialisé a[100][100] pour tous les éléments en utilisant memset()

3) ajouté un getchar() supplémentaire (mon système utilise qu'au lieu de getch()), et a commenté clrscr()

Il a couru pour 4x4 et 8x8 (mais la sortie ne semble pas correcte, vous avez plus travail à faire là):

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