La matrice de Walsh-Hadamard dispose de certaines propriétés mathématiques intéressantes, comme l’orthogonalité 2 à 2 des lignes de la matrice qui est exploitée dans les systèmes à accès multiple par répartition de codes (CDMA). Cependant, les méthodes de génération conventionnelles font assez facilement appel à la multiplication de deux matrices.

Je me suis donc intéressé à une méthode de génération qui utilise quasi exclusivement des opérations de base (décalage de bits pour les puissances de 2, additions et branchements logiques). Elle présente toutefois l’inconvénient de consommer 2 fois la mémoire nécessaire à stocker la matrice.

Le code qui vous est proposé est optimisable, notamment en terme de stockage, mais il a été réalisé dans un objectif d’universalité. Il est fonctionnel et a été vérifié avec les matrices H2, H4 et H1024. Attention, le code source suivant est en C99, n’oubliez pas de configurer correctement votre compilateur.

Fichier hadamard.h

#ifndef __HADAMARD_H
#define __HADAMARD_H

typedef struct matrix {
	size_t width;
	size_t height;
	unsigned char *data;
} matrix;

typedef struct smatrix {
	size_t width;
	size_t height;
	char *data;
} smatrix;

void print_smatrix( smatrix *mtx);

void __hadamard_increment( size_t iteration, matrix *mtx);

// Generates the hadamard matrix of dimention 2^k
smatrix* gen_hadamard_matrix( size_t k);

#endif // __HADAMARD_H

Fichier hadamard.c

#include <stdio.h>
#include <stdlib.h>
#include "hadamard.h"

void print_smatrix( smatrix *mtx) {
	for( size_t i = 0; i<mtx->height; ++i)
	{
		printf( "|");

		for( size_t j=0; j<mtx->width; ++j)
		{
			printf( ((int)mtx->data[mtx->width*i+j] < 0 ? " %d" : " +%d"), (int)mtx->data[mtx->width*i+j]);
		}
		printf( " |\n");
	}
}

void __hadamard_increment( size_t iteration, matrix *mtx)
{
	size_t powOfTwo = 1 << iteration;

	for( size_t y=0; y<mtx->height; ++y)
	{
		// If selected bit is not set, skip this column
		if( (powOfTwo & y) != powOfTwo )
			continue;

		for( size_t x=0; x<mtx->height; ++x)
		{
			if( (powOfTwo & x) != powOfTwo)
				continue;
			++(mtx->data[mtx->height*y+x]);
		}
	}
}

// Generates the hadamard matrix of dimention 2^k
smatrix* gen_hadamard_matrix( size_t k)
{
	matrix mtx;
	smatrix* smat = malloc( sizeof(smatrix));

	// To generate a hadamard matrix, without using the multiplication,
	// we use an additive transition matrix.

	mtx.width = mtx.height = 1 << k;
        mtx.data = malloc(sizeof(unsigned char)*mtx.width*mtx.height);

	size_t mtxSZ2D = smat->width*smat->height;
        for (size_t i=0; i<mtxSZ2D; ++i)
        {
                mtx.data[i] = 0;
        }

	// We iteratively apply the incrementation on cells where the k_th bit
	// is set on both y and x coordinates. Apply k times for a 2^k by 2^k
	// Hadamard matrix

        for( size_t i=0; i<k; ++i)
                __hadamard_increment( i, &mtx);

        smat->width = mtx.width;
        smat->height = mtx.height;
        smat->data = malloc(sizeof(char)*smat->width*smat->height);

	// Then we generate the hadamard matrix by converting odd cells to '-1'
	// from the transition matrix and even cells to '+1'.

	size_t smatSZ2D = smat->width*smat->height;
        for ( size_t i=0; i<smatSZ2D; ++i)
        {
                smat->data[i] = (char)( ((mtx.data[i]) & 1) == 0 ? 1 : -1 );
        }

	free(mtx.data);
	return smat;
}

Fichier main.c

#include <stdio.h>
#include <stdlib.h>
#include "hadamard.h"

int main(void)
{
	size_t k;
	matrix mtx;

	printf( "Calcul de H(2^k). Valeur de k? ");
	scanf( "%i", &k);

	smatrix* smat = NULL;

	smat = gen_hadamard_matrix(k);
	print_smatrix( smat);

	free(smat->data);
	free(smat);
	return 0;
}

Les explications seront publiées prochainement.

Publicités