Embed Size (px)
Citation preview
DI~FINITION A N A L Y T I Q U E S I M P L E D E S FONCTIONS D E W A L S H
ET A P P L I C A T I O N A L A D I ~ T E R M I N A T I O N E X A C T E
D E L E U R S P R O P R I i ~ T t ~ S S P E C T R A L E S *
pa r
Claude C A R D O T
hlgOlieur en chef des t~ldcommunications (e d ) **
RI~SUM~. - - L'auteur ~tablit des [ormules simptes el rapidemenl programmables permellant d'engendrer direc- tement les fonctions de Walsh & parlir du signe des fonclions trigonomdtriques, la seule donn~e ~lanl le rang de la /onction. Cet algorilhme est ulilisd~ pour ddlerminer le ddveloppemcnl exact en sdrie de Fourier d'une fonction de Walsh de rang quelconque. L'dlude des spectres ainsi obtenus permet de caracldriser numdriquement les propridtgs de transmission de s ignaux par l'inlermddiaire de porteuses Walsh : on ~vaIue I'af/aiblissemenl el la diaphonie rdsullanl de la limitation de la bande passanle de la voie de transmission par un fiIlre rectan- gulaire. On ddmonlre que Ies /onctions de Walsh peuvent $tre groupdes en classes d'dquivalence en ce qui c oncerne leur diaphonie mutuelle de filtrage el que routes ces classes peuvent ~tre ddcriles par la mdme matrice, dont les termes sont ]onction de la ]rdquence de coupure. La matrice de diaphonie de la cIasse contenant 2 ~ [onctions
poss~de 3 ~ lermes aislincls au signe pr~s.
PLAN. - - I : Introduction, 1.1. Gdnlralilds; 1.2. Notalions. �9 I I : D~]ini t ion analytique des fonctions de Walsh II .1. D~composition en /onctions de base; I I .2 . Expression analgtique des /onelions de base I I .3 . Programmalion. �9 I I I : Ddveloppement en sdrie de Fourier des fonctions de Waish I I I .1 . Gdndralit~s ; I I I .2 . Thdor~me pr~liminaire ; I I I .3 . Calcul de la sdrie de Fourier d'une porteuse Walsh. �9 IV : Application d l'~tude des consequences du ]iltra~e sur la transmission des signaux par l'intermddiaire d'une porteuse Walsh. Classes d'dquivalence et matrice universelle de diaphonie IV.1. Gdndralit~s; IV.2. Principe du calcuI; IV.3. Ddfinition des classes d'dquivalence diaphonique des [onclions de Walsh. �9 V : Etude de la matrice universelle de diaphonie; produits de convolution des fonctions de Walsh; nombre de termes dist incts de la matrice de diaphonie d'une classe d'~quivalence V.1. Gdn~ralil~s; V.2. Representation potgnomiale des [onctions de Walsh; V.3. Produits
de convolution des /onctions de Walsh. V I : Conclusion. Bibliographic (8 r6f.).
I . I N T R O D U C T I O N .
1.1. G~n6ralit~s.
Les fonc t ions de Walsh , d6riv6es des m a t r i c e s
de H a d a m a r d [1], su se i t en t un in t~r~t c ro i s san t darts
le d o m a i n e des t~16eommuniea t ions , en ra i son de la
poss ib i l i t6 de les p r o d u i r e e t de les m e t t r e en oeuvre
a v e e des d isposi t i fs f a i s an t appe l a u x t echno log ie s
d~jh ut i l is6es dans les ea l eu l a t eu r s num~r iques .
Les l i m i t a t i o n s de leur emplo i son t e s s e n t i e l l e m e n t
gouvern~es pa r leurs propr i~t6s spee t ra les , qu i per-
m e t t e n t de p r6vo i r les b a n d e s pas san t e s n~eessaires
h une b o n n e r e s t i t u t i o n de s i g n a u x t r a n s m i s p a r
l ' i n t e r m ~ d i a i r e de po r t euses Walsh .
Des t e n t a t i v e s o n t d~jh 6t~ fa i tes p o u r :
a) ob t en i r une d~f in i t ion s implif i~e e t r a p i d e m e n t
p r o g r a m m a b l e d ' u n e fonc t i on de W a l s h de r a n g quel-
conque , une fois connu ce rang , e t de man i~ re non rdcursive, c ' es t -h -d i re sans s t ockage en m~moi r e
d ' a u c u n e des fonc t ions pr~c~dentcs . P r a t t , K a n e e t
A n d r e w s [2] o n t m e n t i o n n d une te l le ddf in i t ion [for-
m u l e (13)], q u i a ~t~ expl ic i t~e p a r L a c k e y e t Me l t ze r
[3]. Ces d~f ini t ions p r ~ s e n t e n t les i nconvdn i en t s de
n~cess i ter une c o n v e r s i o n du r a n g de la f o n c t i o n en
code b ina i re r~fl5chi e t de ne pas r epose r sur une
p r e u v e r igoureuse , c o m m e l ' i n d i q u e n t les de rn ie r s
a u t e u r s en fin d ' a r t i c l e ;
b) ca rac t~r i se r e x a c t e m e n t leurs propr i~t~s spec-
t rales . Ceci a n o t a m m e n t ~t~ expos~ pa r H. H. Schre i -
be r [4], au m o y e n d ' u n e sui te d ' a p p r o x i m a t i o n s .
Nous p roposons dons la pr~sente ~ tude une d~fini-
t i on a n a l y t i q u e s imple , non r~curs ive , bas~e sur des
fonc t ions de R a d e m a c h e r d~cal6es, l aque l le d~f in i t ion
p e r m e t d ' a b o u t i r au calcul e x a c t de la sdrie de F o u r i e r
d ' u n e f o n c t i o n de W a l s h i nd~ f in imen t r~p~t~e (por-
t euse Walsh) .
Les r~su l ta t s o b t e n u s p e r m e t t e n t une ~ v a l u a t i o n
n u m ~ r i q u e precise de l ' a f f a ib l i s semen t e t de la dia-
phon ic r ~ s u l t a n t de la l i m i t a t i o n de la b a n d e t r ans -
raise, dans le cas d ' u n m u l t i p l e x , a v e c des po r t euses
Walsh .
On m o n t r e que les fone t ions de W a l s h p e u v e n t
~tre g r o u p i e s , au p o i n t de v u e de la d i aphon ie , en
* La pr6sente 6tude a 6t5 effectu6e dans le cadre du contrat de la DIRECTION DES RECItERCHES ET MOYENS D'ESSAIS de la D616gation Minist6rielle pour l 'Armement, sour le n ~ 71.34.065.00.480.75.01, ,, Exploration ties applications aux t616- communications des fonctions de \Valsh ),.
** Division des applications 61ectroniques, CIT-A.LCATEL, Marcoussis.
- - 31 - -
2/17 c . C A R D O T [ANNALES DES T~LI~COMMUNICATIONS
classes, toutes isomorphes, et l 'on 6tudie, au dernier chapitre, la matr ice universelle qui d6crit routes ces
classes. Le code binaire r6fl6chi est in t rodui t duns
cette derni~re partie, avec une just i f icat ion rigoureuse.
1.2. Notations.
L2 .1 . Le mot simple s ' en tend ici au sens de la langue courante et Re d6finit aucune propri6t6 math6- ma t ique particuli~re.
L 2 . 2 . Les fonctions de Walsh sont usuel lement d6fi- hies sur u n interval le ouver t ]-- T]2, T]2[, la variable
r6duite d6cr ivant cet interval le s ' appe lan t : 0 ---- t i T
et d6crivant, par cons6quent , l ' in terval le ouver t
]-- 1[2, 112[. Ce sont n o t a m m e n t les nota t ions que l 'on t rouve duns l 'ouvrage de base de H. F. H a r m u t h [5].
Pour simplifier la d6finit ion par l ' interm6diaire de sdries de Fourier, nous normaliserons l ' in terval le ouver t de d6finit ion des fonctions de Walsh h : ]-- 7:, n] et nous appellerons : x la variable r6duite qui d6crit cet intervalle. On a d o n c : x = 27:0.
L2 .3 . Nous 6crirons en outre : W(N, x) = fonct ion de Walsh de rang N, d6finie
de x = --~ ~ x = 7:;
N = rang de la fonct ion de Walsh ( N = 0,1, ... 2 k - -1 , pour le groupe des 2 �9 premieres fonctions de Walsh ordonn6es par s4quences croissantes) ;
s =- s~quence--= N[2 si N e s t pair et (N + 1)]2 si N e s t impair (c 'est donc N[2 arrondi ~ l'entier
sup~rieur) ;
i = - - 2 k-1 + 1 , . . . 0 , 1 , . . . 2 k-1 u n indice entier
p r e n a n t 2 k valeurs et 6num6ran t les intervalles suc- cessifs dont se compose une fonction de Walsh (la
moiti6 droite de la fonct ion est 6num6r6e par les valeurs : 1, 2, ... 2 k-1 de i). Cet indice est d6fini modulo 2 ~, pour une porteuse Walsh ;
2 i -- 1 : indice impair 6num6ran t les m~mes inter- valles en p r enan t les valeurs successives :
- - 2 k + 1 , - - 2 ~ + 3, . . . , - - 1, + 1, + 3 . . . . 2 ~ - - 1 ;
W~r(i) : valeur (+ 1 ou - - 1) de la N e fonct ion de Walsh sur l ' in terval le n ~ i ;
n : rang de l'harmonique dans la s6rie de Fourier
d 'une porteuse Walsh ;
a j : ent ier 6gal ~ 0 ou 1 dans la d~composition
binaire de N, c'est-h-dire que l 'on a :
N = ~ aj 2J-~ , ] = 1 , . . . k - - l ; J
]o : rang du premier 616ment binaire non nul dans l 'expression binalre de N, ~ par t i r de la droite ;
k o : rang du premier 616ment binaire n o r nul darts l 'expression binaire de s, ~ par t i r de la droite ;
(~) = somme directe, symbole de l ' addi t ion de deux
nombres 6crits dans le syst~me binaire, les dl6ments biuaires de m~me rang 6 tant ajout6s modulo 2 et sans re tenue ;
sal (s, x ) - - W ( 2 s - - 1, x), cal (s, x)---- W (2s, x),
sgn (y) = signe de y : fonct ion 6gale h + 1 si g :> 0, h - - 1 si y < 0 , discontinue pour g = 0.
Toutes les figures et t ab leaux du pr6sent article se r appor t en t (sauf la figure 6) au cas : k = 5 (groupe des 32 premieres fonctions de Walsh).
+ = C -- addition. Symbole de l ' add i t ion de deux C
nombres binaires a y a n t le m~me hombre d 'dl6ments, pour obtenir un nombre ternaire a y a n t ce m~me nombre d'616ments, les r~glos 6 tan t : 1 + 1 = + 1 ;
C
1 + O = O + 1 = 0 ; 0 + 0 = - - 1 . C r r
II . D ~ . F I N I T I O N A N A L Y T I Q U E D E S F O N C T I O N S D E W A L S H
II. i . D6composition en fonctions de base.
On salt ([5], w 1.1.4.) qu ' i l existe au signe pros une mani~re et une seule d 'o rdonner les fonctions de Walsh
selon le nombre croissant de 1curs passages par z6ro sur l ' in terval le de d6finition supposd ouvert. Les fonc- t ions de Walsh 6 tant ainsi ordonn6es, et en d6finis- san t le signe de chaque fonct ion par la condi t ion d 'e t re le signe + sur l ' in terval le i =- 1, le th6or~me fondamenta l :
(1) W ( J , x) W ( K , x) = W ( J (~) K , x ) ,
est valable (Fig. 1). L 'op6ra t ion (~) d6finissant un groupe ab61ien, la
recherche d ' u n ensemble min ima l simple p e r m e t t a n t de d6finir par mul t ip l ica t ion toutes les fouctions de
Walsh se ram~ne/~ celle d ' u n ensemble min imal simple de g6n6rateurs dudi t groupe.
Une base par t icul i~rement simple pour l 'op6rat ion Q est consti tu6e par les indices n'agant qu'un seul dldment binaire dgal ~ 1. Pour ces indices, l'addilion directe coincide avec l'addition ordinaire et peu t done 6tre ais6meut programm6e. Nous 6crirons donc, par exemple : 10011 = 10000 + 00010 + 00001 (le signe + p o u v a n t O.re 6crit au lieu de O) , et nous obt iendrons la fonct ion de Walsh, dont le num6ro
est, en binalre : N = 10011, en fa isant le produi t des (k au max imum) fonctions de base, cor respondant aux 616ments binaires qui f igurent dans N, et prises
dans la s6rie :
u 1 = W (00001, x)
u 2 = W (00010, x) . , ~ 1 7 6 1 7 6
uk = W (10000, x)
La fonction u 1 = sal (1, x) est la fonct ion de Rade- reacher d 'ordre uni t~ (fonction impaire). Avee les
32
t . 27, n ~ 1-2, 1972] D E F I N I T I O N A N A L Y T I Q U E D E S F O N C T I O N S D E VqALSII 3/17
0
1
2
3 j 4 I I I s ~ J i, , f ~ l F--
6 J i [ i --)
7 ~ l i i r~l ~ t _ _
~ ' - - G .... j i I ~ ~ i - - -
9 . _ . . . l ' ~ ' l I ~ I I F -
2o
22
"t,t
2s ~
27 ~ ~ -'L-.F'-'~....~"I-
3~ ~ ~ ~ _
FIG. 1. - - l.es 32 premieres Ionctions de \Yalsh.
pr6sentes no t a t i ons , les fonc t ions de R a d e m a c h e r son t :
- - 1 , pou r - ~ < x < 0 , s a l ( 1 , x ) = R ( 1 , x ) =
§ 1, pour 0 < . r < = ,
R ( p , x) = R ( 1 , x / 2 V - 1 ) .
Les fonc t ions u v pour p > 1 son t 6gales ~ W(2V-1, x)
ou cal (2v-2, x) et ce son t des fonc t ions qui ddrivent
de la /onc t ion de Rademacher d 'ordre p - - 2 par an
ddcalage cgclique (qui les t r a n s f o r m e de fonc t ions impa i res en fonc t ions paires).
Ce d6calage cyc l ique est de ~ [ 2 v pour la fonc t ion
de R a d e m a c h e r R(p, x) = sal (2v-1, x).
Nous voyons donc q u ' u n a lgo r i t hme s imple n ' u t i -
l i s an t que l ' a d d i t i o n ord ina i re pe rme t , fl pa r t i r de la
d6compos i t ion b ina i re du r a n g N, d ' a b o u t i r & engen-
drer t ou t e fonc t ion de Wal sh en m u l t i p l i a n t des
fonc t ions de R a d e m a c h e r d6cal6es (sauf la premi6re) :
si N = ~ a y 2i -~, (ay - 0 ou 1), on au ra :
(2) W ( N , x ) = [I u y , 1, .y ~ o
le p r o d u i t ne c o m p o r t a n t que les fac teurs cor respon-
d a n t a u x indices ] pour lesquels : a I =: 1.
I I . 2 . E x p r e s s i o n a n a l y t i q u e d e s f o n c t i o n s de b a s e .
P o u r explo i te r la for.mule (2), il suffit de m e t t r e sous une forme a n a l y t i q u e s imple les fonctio: ls p6rio- cliques uy :
O n a :
II 1 : sgn (sin x) -- sgn [cos ( x - ~ /2) ] ,
a 2 = sgn (cos x ) ,
(3) u 3 = sgn (cos 2 x ) ,
uk = sgn [cos 2 ~ - 2 x ] ,
ces formules r 6 s u l t a n t i m m 6 d i a t e m e n t de l ' iden t i f i - ca t ion des fonc t ions u i a u x fonc t ions de R a d e m a c h e r d6cal6es.
Nous r e m a r q u e r o n s , d ' a u t r e pa r t , pou r s implif ier les formules e t la p r o g r a m m a t i o n :
a) que l ' op6 ra t i on sgn ( ) c o m m u t e avec la m u l t i p l i c a t i o n ;
b) que cos 0 est 6gal ~ + 1,
Ce qui nous p e r m e t de m e t t r e la formule (2) sous la forme g6n6rale :
(4) W ( N , x ) = s g n e o s a l ( x - r ~ / 2 ) II eos(ay2Y -2x)
les ay v a l a n t 1 si l '616ment b ina i re de ee r a n g figure dans N, @ri t en sys t6me b ina i re , et 0 s ' i l n ' y figure
pas. (Le p remie r fae teur v a u t soit sin x, soit 1, selon qu ' i l s ' ag i t d ' u n e fonc t ion de W a l s h impa i re [sal] ou paire [call).
P o u r une p r o g r a m m a t i o n ais6e de la fo rmule (4), il est souha i t ab l e d ' 6v i t e r les po in ts de d i s con t inu i t6 de la fone t ion sgn ( ) et il est suffisanl de d6finir W ( N , x) sur ehaeun des in te rva l les suecessifs oil cet te fone t ion demeure eons tan te . E n i n t r o d u i s a n t les indices ent ie rs i et 2 i - - 1 d6finis au w 1.2.3. nous p o u v o n s @rire :
u 1 = sgn [sin (2 i 1) r~]2 ] sgn [cos ( 2 i - - 1 ) ~ / 2 ~ --7:]2)] ,
(5) u 2 = sgn [cos 2 (2 i - - 1) 7:12 k+l] ,
u k = sgn [cos 2 ~-1 (2 i -- 1) ~ 2 k+l] ;
et :
(6) \VN( i ) = sgn ~cos a 1 ((2 i - - 1) =12 k - =/2 ) •
j=k ] I I cos (as 2s-1 (2 i - 1) ~/2k+I)
. /=2
I I . 3 . P r o g r a m m a t i o n .
La fo rmule (6) p e r m e t de calculer , s a n s a u c u n
slockage prdalable, la va l eu r d ' u n e fonc t ion de Wa l sh de r ang donn6 N, h pa r t i r de la d6compos i t ion b ina i re de N. Elle p e r m e t donc de r6aliser de subs tan t i e l l e s 6conomies de m6moire dans t o u t calcul oh in te r - v i e n n e n t les fonc t ions de \Valsh, p o u r v u que le calcu-
l a t eu r dispose (ce qui est le cas g6n6ral) de sous-
p r o g r a m m e s t r i gonom6t r iques .
- - 3 3 - -
4/17 c . C A R D O T [ANNALES DES TIS3LI::COMr, IUNICAT[ONS
C'est en par t icul ier en ut i l i sant cette formule que
les t r en te -deux premieres fonctions de Walsh repr6-
sent6es figure 1 ont 6t6 trac6es avec une calculatr ice
de bureau ayan t une m6moire inf6rieure
1 000 octets (*).
La figure 2 est l ' o rgan igramme du p rogramme
correspondant .
Lire N I r
i x= l
m 1
m 2
I
m k
n~:l ~ oui
/ I~, =2J'1 t [ mj:O
' I ' I 1
l,:,+, i non
i = 1 - 2k-1
1_ f -
ind6finiment r6p6t6e (porteuse Walsh). Ce sigLlal
6tant p6riodique, il est possible de le d6velopper ea
s6rie de Fourier fi par t i r de la connaissauce de ses
valeurs sur l ' in terval le de d6finition 6gal h une p6riode.
Les th6or~mes g6n6raux sur les s6ries de Four ier
nous pe rm e t t en t d '6noncer les r6sultats suivants :
a) route fonction de Walsh de rang pair (cal) se
[ !
N=.X
I I I
D6composition binaire de N k
N-- ~mj 1
m] -- aj2J" 1 aj = 0 ou 1
Chargement du tableau des mj
I I 1
~t
7,
Calcut de W (N, i)
V=cOS m l ( 2 i _ l . 2k. l ) F[ . rf �9 I7 cos m 2 (21- 1) 2--~-~- T cos m3 (2 i -1) 2--~- ~. ,., cos mk (2i- l ! 2--~- i"
1 Arr~t ou changement |
de N i< oui
sgn(V) =WIN, i) ]'-'~ sortir W(N, i)
] ,=,+, J non
FIG. 2. - - Organigramme du programme de calcul d'une fonction de Walsh de rang donn6 N, & partir de la d@omposition binaire de N.
III . D ~ . V E L O P P E M E N T E N S ] ~ R I E D E F O U R I E R
D E S F O N C T I O N S D E W A L S H
I I I A . G 6 n 6 r a l i t 6 s .
Darts le pr6sent ehapitre , nous caleulons le d6ve-
loppement en s6rie de Four ier d 'une fonction de Walsh
(*) 9 100 B Hewlett-Packard avec table tra~ante.
d6veloppe en sdrie de cosinus & coefficients r&Is. En
effet, il s 'agi t d 'une fonction paire, ~ valeurs rdelles;
b) de m6me, tou te fonct ion de Walsh de rang
impair (sal) se d6veloppe en sdrie de sinus & coeffi- cients rdels.
Nous allons, en outre, 6tablir r igoureusement un
th6or~me pr61iminaire, qui appara i t h l ' examen d 'un
tableau de fonctions de \Valsh, et sera utile pour la
pr6sente 6rude.
- - 3 4 - -
t . 27 , n ~B 1 -o , 1972J D/~"FINITION ANALYTIQUE DES FONC'FIONS DE WAI,SH ~)/|7
I I I . 2 . T h 6 o r 6 m e p r 6 1 i m i n a i r e .
Toule /onction de Walsh de rang pair esl @ale h la ]onction impaire de mdme sOquence, cgcliquement d~cal~e.
111.2.1. Dt!monstration.
Soit ]o > 1, l ' indice de l'~16ment binaire non nul de poids le plus faible dans l 'expression binaire du rang N de la fonetion paire consid6r6e. Ce num6ro binaire se termine done par ]o -- 1 z6ros.
Le num6ro binaire de la fonction impaire de m6me s6quence, qui la pr6c~de imm6dia tement , se termine done par un z6ro suivi de ]o -- I unit6s.
Les 616ments binaires de rang sup6rieur h ]o sent les m6mes pour les deux fonetions.
Exemple : ]o = 2.
N = 6 = 00110, fonction : cal (3, x),
N = 5 = 00i01, fonction : sal (3, x).
La fonction paire a pour expression, d'apr6s (4) :
W(2 s, x) = sgn [Y(x) cos (2 i0 -~x) ] ,
avcc k
(6) Y(x) = I1 cos (aj 2J -~ x), j0+l
La fonction impaire a, de m6me, pour expression :
(7) W(2s -- 1, x) = sgn [Y(x) cos (2io--3 x) •
cos (2~o-~ x) ... cos x sin xl �9
La fonction Y(x) 6tant la meme que pour (6), puisque les 616meuts binaires de rang sup6rieur h ]o sent les m~mes pour les deux valeurs cons6cutives de N consid6r6es.
App l iquan t h (7) de droite h gauche, ]o -- 1 fois de suite, la formule
sgn [(sin x cos x)] = sgu (sin 2.r) ,
il v ient :
(7) W ( 2 s -- 1, x) = sgn [Y(x) sin (2 i0-2 x)] .
Posant z = 2io - z x , on voit que l 'on a :
W(2 s , z) = sgn [Y(z) cos z],
et
W ( 2 s - - 1, x) = sgn [Y(z) s in z] , /,
Y(z) ayau t la forme : 17I cos (aj 2 j - jo z). fo+i
Si Y(z) renferme le facteur cos 2 z, on a :
W(2s , z ) = W ( 2 s - - 1 , z - ~ z ] 2 ) (cas off al0+l = 1).
Si Y(z) ne renferme pas le facteur cos 2 z, mais commence par un facteur cos 4 z ou sup6rieur, on a :
W(2 s, z) = W(2 s -- 1, z ~-n]2) (cas o~ a/o+1 = 0) .
En effet, les cosinus ayan t un coefficient de z
6gal ou sup6rieur /~ 4 sent invar ian ts par un d6ca- lage de 7z[2 de z.
Darts l 'exemple ci-dessus :
] o = 2 ; z = x
cal (3, x) = sgn [cos 2 x cos x l ,
sal (3, x) = sgn [cos 2 x sin x ] , d'ofl :
cal (3, x) = sal (3, x - ~ / 2 ) .
111.2.2. Consdquences.
I1 r6sulte du ttt6orbme pr6c6dent que deux fonctions de m~me s6quence ind~finiment r~pdldes ne diff6rent l 'une de l ' au t re que par le choix de l 'origine des temps.
Elles ont done n6cessairement des coefficients de Fourier de m~me module pour chaque rang. Ces coeff- cients ne diff6rent que par le signe, puisqu' i ls sent r6els, lorsque l 'origine des temps est, comme darts la
d6finition utilis6e pr~sentement , telle que les fonc- tions soient paires ou bien impaires sur l ' in terval le de d6finition.
Remarque.
I1 ne resulte pas du fait que les deux fonctions de Walsh associ6es de m~me s6quence a ient m~mes coeffi- cients de Fourier, au signe pros, que ces deux fonctions se correspondent par la t ransformat ion de Hilbert , c'est-~-dire que le signal cal (n, x) + j sal (n, x) soit
un signal ana ly t ique au sens de Gabor et Ville (6). La transform6e de Hi lber t d 'une fonction de Walsh
pr6sente en effet des points infinis. Par exemple :
4 [ s i n Z x s i n 5 x ] sa l (1 , x ) = s i n x + .... 3 - + - - - ~ + . . . .
+ ~ c o s 3 x c os5x cal (1, x) = cos x 3 § 5 . . . .
La transform6e de Hilber t de sal (1, x) est, par contre :
? [ COS3X c0sSx ] sal * (1, x) = cosx + - - - ~ - - - + - - -~- - - - + ...
fonction qui pr6sente un point infini pour x = 0 et
pour x = kr:, k entier. Elle est @ale ~ (2j]r:) logeItg x/2], ainsi qu 'on peut l '6 tabl ir directement.
Le signal ana ly t ique dent sal (1, x) est la part ie r6elle a pour expression :
2 j loge tg x s a l ( l , x ) + j s a l * (1, x ) = 1 + r ( 2-"
Cette formule permet de calculer la phase instan- tande d 'un signal rectangulaire qui est dans le cas pr6sent :
q~(.v) = Arc t g ( 2 1 o g e t g ~ - 1 ,
et la /rdquence inslanlan@ du m6me signal :
d~ 2
d-~ = ~ s inx (1 + (4]~ 2) log~]tgx]21) "
I I I . 3 . C a l c u l d e l a s6r i e d e F o u r i e r d ' u n e p o r t e u s e W a l s h .
I I I . 3 . 1 . Au chapitre II, nous avons rendu directe- m e n t calculable la fonction WN(i) qui est la valeur de la
- - 3 5 - -
6 / 1 7 c. CAnDOT [ANNALES DES T~L~COMMLTNICATIONS
fouc t i on de W a l s h de r a n g N sur l ' i n t e r v a l l e n u m 6 r o i
de c h a q u e p6r iode (i v a r i a n t de 1 - - 2~-1 ~ 2k-~) .
P o u r ca lcu le r la s6rie de F o u r i e r de W ( N , x) ind6fi-
n i m e n t r6p6t6e, nous d~compose rons W ( N , x) en la
s o m m e de 2 ~-~ fonc t ions ~16mentaires qu i c h a c u n e
ne dif f6rent de z6ro, darts la p a t t i e d ro i te de c h a q u e
p~riode, que darts l ' i n t e r v a l l e n o i off elles v a l e n t + 1,
leur v a l e u r dans l ' i n t e r v a l l e s y m 6 t r i q u e de la pa r t i e
gauche de c h a q u e p6r iode s ' en d6du i san t en v e r t u
des propr i6 t6s de sym6t r i e (ou d ' a n t i s y m ~ t r i e ) de la
fonc t ion consid6r6e.
Si nous appe lons v~ ces fonc t ions de base qu i ne
di f fdrent de z6ro que sur d e u x in t e rva l l e s au t o t a l
darts c h a q u e p6r iode, nous aurons : i=,k- - I
W ( N , x ) = ~ W N ( i ) vi . i = l
I1 nous suffit donc de ca lcu le r les t r an s fo rm6es de
F o u r i e r des d e u x t y p e s de f o n c t i o n vi repr6sent6es
f igure 3, a : pa i r , e t b : impai r .
I f
I
I --n (1 - i ) -1
(1 - i ) -1
fl I 2 i n o
+1
I [
- - I cal (n, x)
ST
'b p,o j [ sal (n, x)
Fro. 3. - - l,es deux types de fonction v I : a pair, b impair.
L ' i n t6g ra l e de d6f in i t ion des coeffmients de F o u r i e r
sera 6 tendu ~ la moi t i6 d ro i t e de la p6r iode, c 'es t -h-
dire h l ' i n t e r v a l l e (0, x) .
111.3.2. S~rie de Fourier d'une porteuse Walsh paire.
L ' a p p l i c a t i o n des fo rmules de base de la t r ans fo r -
m a t i o n de F o u r i e r d o n n e :
cni = ( c o s n x ) v~ d x = Xn-- sin ' ni,) --
s i n ~ n ( i - - 1 ) .
D 'ol] : i-- ~. k - I n ~ o o
i W~s (i) cal ( s , x) = F, E Cn i = t n = t
n~co 2 i ~ 2 k - I
(8) c a L ( s , x ) - ~ - - c o s n x ~,, W 2 s ( i ) • n--i 7~t i=1
sin hi~) - - s i n / \ ~ n ( i - - / .
111.3.3. S~rie de Fourier d'une porteuse Walsh impaire.
Le calcul es t i den t ique . On a :
2fo [ i -~ (sin nx) vi dx= 2 7~ = - - - cos n ( i - 1 ) - S n 7~ n
et
(9)
cos ~ : V ni ,
n-oo 9, i=s k -~
s a l ( s , x ) : ~ - - s i n n x ~ \V2s 1(i) • . - I 7;n i~l
[ c o s - 2 ~ _ ( n ( i - - l ) - - c o s ~ n i .
La f igure 4 r ep r6sen te les spec t res des 16 p remie re s
fonc t ions impa i res sal (1, x) ~ sal (16, x), t rac6es a v e c
la ca lcu la t r i ce de b u r e a u p r 6 c 6 d e m m e n t m e n t i o n n 6 e .
| = �9 �9
i
, I , , ! , , , ~ 1 , , , ~ , , , ~ sal(2, x)
, I [ . . . . . . . ~-~ sal (3, x) [ . . . . . ! ,
. . . . . . . . . . I . . . . . . . ! sal (4, x')
I , f ! , I . . . . . . . . . sat (S,x) �9 , ]
J I . . . . . . . . . .
. . . . . . . . . . . . . . . . . . sal (8, x )
. . . . . [ , , , I , , , I~ , , , ~ ~ sal(lO, x)
" ' " l ' v ' , ' l ' l . . . . . I ,
' ' ' 1 . . . . . . . [ . . . . . . . ~ sal(12, x)
I ' �9 - ! ' ! sal(13, x) , | i i i i i - i i i i i ~ i 1
I
i J i i i T i J , - - i i [ i i i I i i ] " ~
n = l 5 10 15 20
sal (14, x)
sal (15, x )
sal (16, x )
FI6. 4. - - Speetres des 16 premieres fonetions impaires sal (1, x) h sal (16, x).
- - 36 - -
t. 27, n ~ 1-2, 1972] D E F I N I T I O N A N A L Y T I Q U E D E S F O N C T I O N S D E W A L S t I 7]17
IV. A P P L I C A T I O N A L ' ] ~ T U D E D E S CONSI- '2QUENCES D U F I L T B A G E
S U B L A T B A N S M I S S I O N D E S S I G N A U X P A B L ' I N T E B M ] ~ D I A I B E
D ' U N E P O I : t T E U S E W A L S H , C L A S S E S D ' ] ~ Q U I V A L E N C E
E T MATI: t ICE U N I V E I : t S E L L E D E D I A P H O N I E
IV.1 . G6n6ral i t6s .
Nous consid6rerons un mul t ip lex h porteuses Walsh repr6sent6 sur la figure 5.
I V . 2 . P r i n c i p e du ca l cu l .
Dans une p6riode, chaque fonction de Walsh est repr6sent6e par son d6veloppeme//t de Fourier :
/1~r ,r co~ 1ll; We(x )= F~e. l~ . ~ ,
les coefficients de Fourier 6taut ceux d6finis en 3 [formules (8) et (9)].
L ' in t6gra teur IT e recevant la porteuse W~ fournit , au bout d 'une p6riode, la tension :
1 II~l|lnax
w (x) dx = ,,E f,5. (11) D e e = 7:
S O o ( ~ - -
Wl Sl o- ~
,, I w i
I J WN.I
SN. I o
Wl ~ s,' 1
Zt
S'N. |
FIG. 5. - - Multiplex fl porteuse Walsh.
N 6chant/lions analogiques si sont multipli6s chacun par la fonction de Walsh de m6me num6ro : We(t) pendan t une p6riode. Les s ignaux obtenus sont ajout6s et t ransmis en ligne.
A l 'arriv6e, le d6multiplexage s'op~re en mul t ip l i an t le signal composite re~u par chacune des N fonctions
de Walsh, et en in t6grant le produi t penda n t une p6riode darts l ' in t6grateur 1T correspondant .
I1 est suppos6 :
- - q u e le synchronisme est parfait ,
- - q u e les int6grateurs sont vid6s au d6but de
chaque p6riode,
- - que l'effet de la ligne de t ransmiss ion peut 6tre ass/rail6 ~ celui du filtre passe-bas rectangulaire, dour
le d6phasage est suppos~ nul.
Darts ces conditions, les s ignaux resus sj sont li~s aux s ignaux 6mis s~ par un syst~me lin6aire :
i ,\" -1
(10) s ' j = ~ D e j s~, i : 0
l '6cart de la matr ice Des" par rappor t h la matr ice uni t6 (qui est sa forme l/mite en l 'absence de filtrage) mesure l'effet du filtrage op6r6 par la ligne sur la t ransmiss ion des N 6chant/lions.
Nous caract6risons cet effet par les coefficients sui- r a n t s en d6cibels, qui seront des fonctions de la bande
passante du filtre passe-bas F :
20 logl01Dei [ = affaiblissement de filtrage sur la por- teuse W~,
20 lOglolDey I = diaphonie de filtrage entre les por-
reuses We et W i .
Soumis ~ la porteuse W1, ce m~me int6grateur fourni t :
1 n--nmax
(12) DiJ = 2 E /nf /n l ,
si i e t ] sont de m6me par/t6 et 0 s'ils ne sont pas de meme par/t6, la sommat ion selon n 6taut arr6t6e
la valeur la plus dlevde qui passe dales le /iltre F, soit nma x . On voit imm6dia tement que Dil -- Die.
I1 r6sultc des propri6t6s d 'or thogonali t6 des fonc- t ions de Walsh, que l 'on a :
1 /l co
Dee(~) = ~ E /,~, = 1, pour tou t i , n = l
1 II - ~
D~j(n) = 2 ~] /hi/n3"= 0 pour toute paire i , / ; i ~ ].
C'est-~-dire que, s ' i l / / ' y a pas de filtrage (~Zm~ ~ = ~ ) , la matr ice D~ 3 se r6duit bien ~ la matrice unit6.
Nous nous proposons ci-apr6s de calculer les valeurs de Dej(n) t r adu i san t l 'effet d ' un filtrage rectangulaire qui 61/mine tous les harmoniques de rang sup6rieur
/ /max
IV .3 . D 6 f i n i t i o n des c l a s s e s d ' 6 q u i v a l e n c e d ia - p h o n i q u e des f o n c t i o n s de W a l s h .
IV.3.1. Nous venons d ' indiquer que si i et ] n ' o n t
pas la m6me paritY; l 'appl icat ion de l 'une de ces fonc- t ions ~ un int6grateur al iment6 par l ' au t re produira un
r6sultat nul quel que soil le filtrage (puisque la s6rie
- - 37 - -
8/17 c. CARDOT [ANNALES DES T~L~'COMMUNIeATIONS
de Fourier de l 'une se compose de sinus, et celle de l ' au t re de cosinus).
Nous disous que ces deux fonctions sont alors absolument orlhogonales, c'est-h-dire que leur orthogo- nalit6 subsiste quel que soit le filtrage que subissent l 'une ou l ' au t re de ees deux fonetions.
Le cas envisag6 ci-dessus n 'es t pas le seul, ear il est 6galement possible que les fr6quences qui figurent avec des coefficients non nuls dans la s6rie de Fourier
de l 'une des fonctions de figurent pas, avee des coeffi- cients non nuls, duns eelle de l 'autre .
Nous d6finirons done eomme absoIument orthogo-
nales deux fonctions de Walsh Wi et Wj relies que :
- - ou bien i et ] n ' o n t pas m6me parit6,
- - o u bien les fr6quenees qui figurent, avee des eoeffieients non nuls, dans le d6veloppement en s6rie de Fourier de l 'une ne figurent pas, avee des eoeffi- eients non nuls, dans eelui de l 'autre.
Pour deux fonetions abso lument orthogonales, on a ;
Dij(n) = 0 quel que soit n.
IV .3 .2 . Nous allons 6tablir que si deux fonetions de Walsh out une eomposante de Fourier en eommun, alors elles ont routes leurs eomposantes de Fourier en
commun (*) ; au t r emen t dit, la relat ion ne pas ~tre
absolument orthogonales est une relat ion d '6quiva- lenee qui permet de elasser les fonetions de Walsh en classes d'~qnioalences diaphoniques, telles que deux fonetions situ6es duns des classes diff6rentes soient
abso lument orthogonales, deux fouetions situ6es duns la m~me classe ne l ' 6 t an t pas.
A) TMordme. - - Si deux fonetions de Walsh d6ve- lopp6es en s6rie de Fourier sur une p6riode out une
eomposante de Fourier en eommun, elles ont toutes leurs eomposantes de Fourier eu eommun.
I1 nous suffit d '6tabl i r le th6or~me pour les/onctions de rang pair, puisque nous avons 6tabli, w III .2.2. , que toute fonction de rang impair a un d6veloppement de Fourier Oil i n t e rv i ennen t les memes /rdquenees que pour la fonetion paire de m6me s6quenee, les cosiuus 6tant remplac6s par des sinus, au signe prbs, et les modules des coefficients 6taut les m6mes pour ehaque fr6quence.
Consid6rant done u n i q u e m e n t les fonetions de rang pair (eal), posons, en rep renan t les nota t ions du w 111.2.1. :
]o > 1 = rang du premier 616ment binaire non nul dans l 'expression binaire du rang N.
Selon la formule (6), on a :
W ( 2 s , x) = sgn [Y(x) cos (2i0-2x)]
ou en posant : 2 /o-2x : z
(13) W(2 s, x) = sgn [Y(z) cos zl
(*) Avoir une composante de Fourier en commun signifiant avoir des termes trigonom6triques de m~me nature (cosinus ou sinus) a la mdme /rdquence, avec des coefficients tous deux non nuls.
La fonct ion Y(z) est un produi t de cosinus de mul- tiples de z par des puissances enti~res de 2. Dans ces conditions, le th6orbme de mul t ip l ica t ion des fonctions t r igonom6triques mont re que le crochet dans (13) est une somme de cosinus de multiples impairs de z. La fonction sgn ( ) n ' a l t6 ran t pas les pro- pri6t6s de sym6trie, le d6veloppement de Fourier de (13) ne comprendra que les cosinus des multiples impairs de
z : 2 io-2 x .
Sachant que, pour deux valeurs diff6rentes de ]o , les s6ries des mult iples impairs de 2 io-2x sont dis-
jointes, il en r6sulte que :
- - deux fonctions paires a ya n t la m~me valeur
de ]o on t toutes leurs composantes de Fourier en commun ;
- - d e u x fonctions paires n ' a y a n t pas la m6me valeur de 1o n ' o n t aucune composante de Fourier en commun et sont to ta lemeut orthogonales.
B) Nous voyons donc que les classes d '6quivalence
diaphonique sont d6termin6es par la valeur de ]o. Dans ee qui suit, nous poserons :
k o : ] 0 - - 1 : rang du premier 616ment binaire non nul dans l 'expression binaire de la sdquence, s.
IV .3 .3 . Les cons6quenees du th6or~me prdc6dent peuven t 6tre r6capitul6es comme suit :
a) toutes les fonctions de Walsla paires sont abso- l u m e n t orthogonales a toutes les fonctions de Walsh
impaires ; il existe done a u t a n t de classes d '6quiva- lence pour les fonctions paires que pour les fonctions impaires ;
b) deux fonctions sont dans la m~me elasse d '6qui- valence si, et seulement si, elles on t meme parit6 et
meme valeur de k o ;
c) les fonetions de la elasse d '6quivalenee k o on t pour eomposantes de Fourier la s6rie des fr6quenees mult iples impaires de 21~o-1 .
IV.3.4. Num~ro diaphonique. D~nombrement des classes.
Dans chaque classe d '6quivalence, nous pouvons ordonner, en s~quence croissante, les fonctions qui y sont contenues, au moyen des 616ments binaires de rang sup6rieur h k o dans l 'expression de leur s6qucnce. Ces 616ments binaires cons t i tuen t la repr6sentat iou binaire d ' u n nombre e que nous appellerons num~ro
diaphonique.
On voit ais6ment que k o peut aller de 0 ~ k dans le groupe des 2 ~ premi6res fonctions de Walsh, la valeur k n ' 6 t a n t a t te in te que par la derni~re fonet ion du groupe (sal 2~-1, x).
E n outre, k o n 'es t pas d6fini pour la fonct ion W 0 , qui const i tue une elasse ~ elle seule.
Le tableau I indique le eontenu des 10 classes
d '6quivalenee qui exis tent dans le cas de k = 5. I1
3 8 - -
t. 27, n ~ 1-2 , 1 9 7 2 ] D I ~ F I N I T I O N A N A L Y T I Q U E D E S F O N C T I O N S D E W A L S H 9/17
T A B L E A U l
Table(tu des 10 classes d'dquivalence diaphouique pour les 32 premidres /ouctious de Walsh (Les barres en trait fort s6parent les classes d'6quivalence)
Hang N
0
2 (i
10 14 18 22 26 30
4 12 20 28
8 24
1 l:onctions S6quence ko eo Fonctions Rang ; paires s f impaires N
I
cal ( 0, x) 0
cal ( 1, x) 1 0001 1 0 sal ( 1, x) 1 cal ( 3, x) 3 =: 0011 1 sal ( 3, x) 5
: cal ( 5, x) 5 === 0101 2 sal ( 5, x) 9 cal ( 7, x) 7 =: 0111 3 sal ( 7, x) 13
i cat ( 9, x) 9 , 1001 4 sal ( 9, x) 17 ] cal (11, x) 11 1011 I 5 sal (11, x) 21 il cal (13, x) 13 : 1101 6 sal (13, x) 25 i cal (15, x) 15 1111 7 sal (15, x) 29
I I i cal ( 2, x) 2 = 0010 2 0 sal ( 2, x) 3
cal ( 6, x) 6 = 0110 1 sal ( 6, x) 11 cal (10, x) 10 ~ 1010 2 sal (10, x) 19 cal (14, x) 14 := 1110 3 sal (14, x) 27
i
; cal ( 4, x) 4 = 0100 3 0 sal ( 4, x) 7 cal (I2, x) 12 1100 1 sal (12, x) 23
16 cal ( 8, x) 8 1000 4 0 sal ( 8, x) 15
16 ~ 10000 5 0 sal (16, x) 31
appara~t a v e c 6vidence "~ l ' e x a m e n de ce t a b l e a u qu ' i l
ex i s te t o u j o u r s 2k classes d ' ~ q u i v a l e n c e p o u r le g roupe
de 2 k fonc t ions de Walsh ,
I1 en r6sulte i m m 6 d i a t e m e n t q u ' u n m u l t i p l e x ut i l i -
s a n t s e u l e m e n t 2k por teuses W a l s h choisies dans le
g roupc des 2 ~ premiSres fonc t ions de Walsh , h ra i son
d 'une , e t d ' u n e seule, pa r classe d ' 6 q u i v a l e n c e , p e r m e t
duns le cas du module 6tudi6 de r6al iser une t r ans -
miss ion sarzs diaphollie, quel que soit le filtrage.
IV.3.5. lsomorphisme des classes. Matrice de d iaphon ie .
a) I1 r6sul tc de ce qui pr6cSde que Ies coeff icients
de d i a p h o n i e Di] de ia f o rmu ie (10) ne d i f fe ren t de
z6ro que si les fonc t ions de W a l s h c o r r e s p o n d a n t e s
se t r o u v e n t duns la m ~ m e classe d ' 6 q u i v a l e n c e
d i a p h o n i q u e .
Nous al lons m o u t r e r ci-apr6s que lotztes les classes
d'dquivalcizce diaphoniqac sont isomorphes, ce qui per-
m e t de d6fiuir une m a t r i c e u n i q u e De,e,(ll') qui donne les coeff icients de d i aphon ie par f i l t rage p o u r une
classe d ' d q u i v a l e n c e q u e l c o n q u e , en fonc t i ou d ' u u
p a r a m 6 t r e t~' qui es t uu sous -mu l t i p l e de n f i g u r a n t
dans la d6f in i t ion de D i j 0 0 , e t des seuls num6ros d i a p h o n i q u e s des d e u x fonc t ions de W a l s h consid6r6es.
b) Th6or~me. - - Totztcs les classes d'dquivalence diaphoniques so1~t isomorphes, au signe prds, el sont
ddcrites par la mgme mab'ice :
D~j00 , i e t ] 6 t a n t les rangs de d e u x fonc t ions de
la m ~ m e classe, ou
De,e , ( r / ' ) , e , e' 6 t an t les uumdros d i a p h o n i q u e s de
d e u x fonc t ions dans la m 6 m e classe.
C a s d e s c l a s s e s p a i r e s .
Si d e u x fonc t ious pai res on t m 6 m e n u m 6 r o dia-
p h o n i q u e , soi t e, dans des classes d ' d q u i v a l e n c e diff6-
ren tes , so ien t k o e t k 'o , on v o l t i m m 6 d i a t e m e n t en
e x a m i n a n t la f o rmu le (13) qu ' e l l es d 6 r i v e n t du p ro-
du i t des cosinus des m e m e s m u l t i p l e s de z e t q u e
seule la d6f in i t ion de z c h a n g e d ' u n e classe h l ' a u t r e :
z = 2 1 ' o - i x p o u r la classe d6finie p a r k o ,
z' = 2~eO-lx p o u r la classe d6finie pa r k ' o .
I1 en r6sul te que l ' o n passe de l ' u n e h l ' a u t r e de
ces fonc t ions p a r un c h a n g e m e n t de l '6chel le d e s
f r~quences darts le r a p p o r t 2 l~o-~''0, r a p p o r t qu i ne
d6pend que des d e u x classes consid6r6es.
P a r cons6quen t , si nous appe lons Dl~~ (n) le
coeff ic ient de d i aphon ie en t r e les fonc t ions de num6ros
d i a p h o n i q u e s e e t e' duns la classe k o , les s o m m a t i o n s
des fo rmules (11) e t (12) 6 t an t ar re t6es ~ la v a l e u r n
( incluse) de l ' i ud ice n, on a :
/~o 1,,0 (n12/,,o_,o) (14) D,,,e, (n) = De, e, .
Ce t te f o rmu le d tab l i t le t hdorbme annonc6 p o u r le cas des classes d ' 6 q u i v a l e n c e c o n t e n a n t des fouc t ions
paires .
C a s d e s c l a s s e s i m p a i r e s .
D e u x fonc t ions impa i r e s ont , au signe pr6s, e t p o u r t o u t e v a l e u r de n, le m ~ m e coeff ic ient d i a p h o n i q u e D L I
que les fonc t ions pai res de m ~ m e s6quence :
Di j (n ) = D ~ + l , t + l ( n ) ,
i, ] impa i r s e t c o r r e s p o n d a n t h des rungs situ6s duns
la m ~ m e classe d ' 6 q u i v a l e n c e (k).
I1 r6sul te , en effet , des r~su l ta t s du w I I I . 2 A . q u e
l ' o n a t o u j o u r s :
W ( 2 s - - 1 , z) = + W ( 2 s , z - r : 1 2 ) ,
a v e e z = 2 ho-1 x .
- - 3 9
10/17 c. CAP, DOT [ANN&LES DES T~I,~COMYIUNIC&TIONS
I1 en r6sulte que le produi t W(i, x) W(], x) coincide toujours, au signe pros, avec le produi t :
\V(i § 1, x) W(/ § 1, x ) ,
m o y c n n a n t un d@alage cyclique de ~/21'0-1 de la
variable x, m~me lorsque les fonctions de Walsh sont remplac6es chacune par leur s6rie de Fourier tronqu6e.
Ces deux produits ont donc, au signe pros, les m~mes coefficients de Fourier h chaque fr6quence, et l '6ncrgie int6gr6e jusqu 'h l ' h a r m o n i q u e n e s t la m~me, en valeur absolue, qucl quc soit n.
num6ros diaphoniques e, e' a ppa r t c na n t ~ la classe
de diaphonie (ko), avec k o > 1 sera, pour un filtrage coupant les fr6quences sup6rieures ~ n donn6 par la
formule :
k 0 1 , (15) De,e' (T/) = De,~ (T/J2r~-l).
IV.3.6. Application.
La figure 6 repr6sente les courbes de diaphonie en d6cibels pour la classe d '6quivalence compor tan t les num6ros 0, 1, 2, 3. Ces courbes pe rme t t en t douc
5O
I)ij (dB)
41) t 22 /
30 ~ / Ol
20
10
10 20 n
FIG. 6. - - Courbes de diaphonie de filtrage en d6cibels (les courbes 02 et 13 sont identiques).
Chaque classe impaire est doric isomorphe & la classe paire correspoT/daT/te, ce qui complete la d6monst ra t ion
du th6orbme annonc6.
c) Matrice universelle de diaphonie.
I1 r6sulte du th6orbme pr6c6dent que si l 'on connai t
l a matr ice 1
De, ~, (n ) ,
pour l a r de diaphonie : k o = 1, le coefficient de diaphonie entre deux fonctions de Walsh de
l '6valuat ion imm6diate de la diaphonie et de l'affai-
bl issement de filtrage pour les fonctions a p p a r t e n a n t au groupe des 16 premieres fonctions de Walsh.
IV.3.7. Cas d'un [iltre de caractdristiques quelconques.
Les r6sultats pr6c6dents supposent un filtre rectan- gulaire d d~phasage constant dour les seuls effets s o n t :
- - d e conserver sans changemen t les termes de
Fourier pour zz ~ T/ma x ;
- - 4 0 - -
t. 27, n ~ 1-2, 1972] D#:FINITION ANALYTIQUE DES FONCTIONS DE WALSH 11/17
- - de supprimer sans r6sidu les termes de Fonrier
pour n > //max"
Duns le cas d 'nn filtre h caract6rist iques diff6rentes, il y a lieu de tenir eompte de Fact ion du filtre stir
ehaque eomposante de Four ier sbpur6ment, et de
poursuivre la sommat ion jusqu 'h n oo ou, en pra-
t ique, jusqu 'h une valeur de n assez grande pour que
l '6nergie des termes supprim0s soit devenue nbgligeable.
I1 est 6vident que les propriHds des classes d'dqui- valence subsisleul, car eIles oa t Otb 6tublies d'apr~s
les propri6t~s des s6ries de Four ier avanl filtrage. Par eontre, lu forme des fonetions de diaphonie
De,e,(/e), [c 6taut une /rdquenee de coapure, earaet6-
r ist ique du filtre, sera ~videlnment fonetiou des
earaet6rist iques du filtre et ees fonetions ne pour ron t
~tre obtenues que par un p rogramme d ' in t6grat iou
off en t re ron t les paramOtres du filtre.
Nous estimons, par aualogie avee d 'aut res eas ana-
logues (par exemple, eourbes de scull en modula t ion
de fr6quence), que la forme du filtre ue dolt pus
influer trbs no tab lement sur celle des courl)es de
diaphonie.
V . ] ~ T U D E D E L A M A T F t I C E U N I V E F t S E L L E D E D I A P H O N I E ,
P R O D U I T S D E C O N V O L U T I O N D E S F O N C T I O N S D E W A L S H ,
N O M B F t E D E T E F t M E S D I S T I N C T S D E L A M A T F t I C E D E D I A P H O N I E D ' U N E G L A S S E D ' # , Q U I V A L E N C E
V . 1 . G b n ~ r a l i t b s .
V. I . 1 . Nous avons constat6 par la figure 6 que, lors-
que l 'on trace les courbes de diaphonie de filtrage cor-
respondant /~ une certaine classe d '6quivalenee, la
mOme eourbe se reproduisai t parfois (dans le eas des
la figure 6, les courbes 02 et 13 sont identiques).
L 'ob je t du pr6seut chapitre est de pr6eiser, par
l '6tude des produits de convolut ion des fonetions de
Walsh, eombien il existe de fonctions de diaphonie
dislinctes duns la classe d '6quivalenee universelle
limit6e h 2 k fonetions (num6ros d '6quivalence de 0 h
2 ~ 0 .
V . 1 2 . La fonct ion de diaphonie entre deux fonctions
de \Vaslh, WN et WN, est d6finie (formule 12 du w IV.2)
par :
( 1 6 ) DNN' ( I lm) = '2 ~ [rt [ 'n , [
/ n e t / 'n ~tant les coefficients des s6ries de Four ier
des deux fonetions de Walsh consid~r~es, celles-ei
~taut suppos6es (par l 'hypoth~se que les deux fone-
tions de Walsh sont dans la m~me elasse) avoir les
mOmes composantes de Fourier.
I1 r~sulte dn th~or~me de composi t ion que : n~cc
E / n / ' ~ c o s n~:, n--I
n'est autre que le d6veloppement eu s6rie de Four ier
du produi t de convolutio~l :
(17)
Q N N ' (X) = \ V ( N , it) \V( l~ r', a- x) da : W N -~ W N, 7~
des deux fonctions de ~Valsh consid6r6es, au signe
pr6s Oventuellement.
V.1.3. Deux couples form6s de fonetions de Walsh
qui ne sont pas absolument orthogonales auront done
la mOme courbe de diaphonie si, et seulement si, les
produits de convolut ion eorrespondants sont iden-
t iques au signe pros sur toute la p6riode.
Duns tou t ee qui suit nous n~gligerons le signe des
produits de convolut ion, puisque seule la valeur absolue des eoeflicients de diaphonie a une impor tance pra-
t ique en t6l~communications. De m6me, nous dispo-
serons a rb i t ra i rement du signe des fonetions de Walsh.
(I1 va de sol que lc signe est d6fini une fois pour routes
pour ehaeuue des fonctions consid6r6es.)
V.1.4. E t a n t donn6 deux fonctions de Waish, les
trois s i tuations suivantes sont seulcs possibles :
a) les deux fonctions sont duns la mdme classe
d'(!quivalence (m~me valcur de k o et m~me parit6).
Duns ce cas, elles ne sont p~ts absolument orthogonales et leur produi t de convolut ion n 'es t pus nul. I1 existe
uue fonction de diaphonie, qui s 'expr ime eu fonct ion
du d6veloppement en sSrie de Four ier de leur p rodui t
de convolut ion [formules (16) et (17)]. On r emarque ra
que le produi t de convohl t ion est roll pour x = 0,
puisque les deux fonctions sour orthogonales, h moins
que les deux fonctions ne soient identiques, auquel
eas on a :
QN,N(0) : 2 k;
b) les deux fonctions sont dans deax classes d'~qui-
valence correspondantes, l'une paire, l'autre impaire
(m~me valeur de k o ; parit6s diff~rentes). Dans ee eas,
elles sont absohlment orthogonales puisque, pour
chaque fr6quenee, p l 'une d'elles a la eomposante de
Fourier : cos px et l ' au t re la composante : sin px.
Leur produi t de convolut ion n 'es t pas nul. En rempla-
~ant l 'une des fonctions (par exemple la fonct ion
impaire) par la fonction paire agant mr numdro
d'Oquivalence darts sa classe (et qui eu r~sulte moyen-
nant un d~caluge eycliqne, comme il a 5t6 d6montr~
en w IV.3.5.b), on voi t que le produi t de convolut ion
n 'es t pas nul sur tou te la p~riode (reals seulement
nul a l 'origine) et que Yon pent l 'obteni r mogennant
an d~calage cgcliqae, h par t i r du produi t de eonvoln-
t ion des deux fonctions uyant les m~mes numdros
d '~quivalence dans la mdme clusse ;
c) les deux fonctions sont daus deux classes dYqui-
valence qui different par la valeur de k o . Darts ee eas,
elles sont absolument orthogonales et leur produi t de
convolut ion esl hal sur toute la p6riode.
- - 4 1 - -
12/17 c . CARDOT JAN.ALES DES TELeCOMMUNICATIOnS
V.2. Repr6sentation polyn6miale des fonc- tions de Walsh.
V.2.1 . Pour l '6tude des produits de convolutiotl des 25 premi6res fonctions de Walsh, nous disposerons du signe de celles-ci pour qu'elles va lent l 'un i t6 sur l ' interval le de gauche de la p~riode compl6te, c'est-h- dire pour que :
W ( N , - - ; : ) ~ 1, ou W~v(i) = 1 pour i = 1 - - 2 5 - 1 ,
avec les nota t ions prdc6dentes. Nous repr6senterons dans ces condit ions les fonc-
t ions de Walsh par des polyn6mes dans une ind6ter-
min6e y, d6finis modulo ( y ~ 5 1), les coefficients de ces polyn6mes 6tant pris dans le corps des rdels, sans l imi ta t ion, et va l an t + 1 pour les fonctions de Walsh.
L 'ensemble de ces polyn6mes consti tue un anneau,
mats non pas un corps. Le coefficient du terme yP est la valeur de la fonct ion sur l ' in terval le num6ro p + 1
h par t i r de la gauche. Nous allons d6montrer les propositions suivantes.
V.2.1.1. Les fonctions de Walsh sont repr6sent~es, dans ces conditions, par des polynbmes factor•
sous la forme :
(18) P(y) = (~ • ~) (1 • y2) (1 • ~) ... (1 • y 25-~) ,
(k facteurs).
Chaque fonction de Walsh correspond h u n certain choix des signes, parmi les 2 $ possibles, dans l 'expres-
sion (18).
V.2.1.2. Les polyn6mes factoris~s. & a n t ordonnds
comme ci-dessus par ordre de degr6 croissant, si l ' on
associe le chiffre binaire 0 au signe § et le chiffre binaire I au signe --, le choix des signes correspondant h une certaine fonct ion de Walsh fourni t un nombre binaire de k chiffres, qui n ' e s t autre que le rang N de la fonct ion de Walsh correspondante, dcrit en code
binaire r~fl~chi (code Gray).
V.2.1.3. E t a n t donn6 deux fonctions de Walsh repr6sent6es par les polyn6mes P(y) et P'(y)
modulo (g~g - - 1) le p rodu i t : P(y)P ' ( I [y ) du premier po- lyn6me en y par le second polyn6me en 1]y (produit effeetu6 dans le corps des r6els sans autre l imi ta t ion pour les coefficients) ddfinit par ses coefficients tes valeurs success• du produit de convolution des deux fonctions de Walsh correspondanles ~ la fin de chacun des inlervalles d'une pdriode.
(Les produits de convolut ion des fonctions de Walsh 6 tan t des fonctions form6es de segments de droite, la donn6e des valeurs d ' u n tel produi t ~ la fin de chacun
des intervalles d ' une p6riode suffit h le d6finir.)
D 6 m o n s t r a t i o n d e l a p r o p r i 6 t 6 V.2.1.1.
a) Les produits de la forme (18) oat 6v idemment une fois d6velopp6 un terme de chaque degr6, du degr6 O au degr~ 25 - - 1, et leurs coefficients sont
6v idemment 6gaux h • 1.
b) Si deux expressions de la forme (18) diffbrent par le signe d ' u n facteur, les fonctions correspondantes
sont orthogonales. Posons, en effet :
(19) P ( y ) ~ - a o § 2 4 7 2L1 ,
(20) P ' ( y ) ~ b o § b l y + b2Y2+... § b2k_ly2~-l(aj ,bj=•
et soit W(x), W'(x) les fonctions correspondantes de x, dont les valeurs sur les intervalles successifs d 'une
p6riode sont d6finies par a o , a I , ... a~L 1 et b 0 , b 1 . . . . b2L 1 respect ivement .
O n a : j~').k-- 1
(21) W(x) W'(x) dx = ~ a j b j . j=0
Supposons alors que, P e t P ' 6 tant mis sous la
forme (18), P cont ienne le facteur (1 + y2P) et P ' le
facteur (1 - - g2~). On voit en d6veloppant que l 'on aura, pour tou t i
inf6rieur h 25-P -- 1 :
ai+2/~ = a l ,
b/+2p -- b~,
d 'oh : a~+~p b i + 2 p - at b~.
Chacun des termes de la somme (21) est donc annul6 par le terme situs 2P rangs plus loin, la somme des 2P +x premiers termes est donc nulle, et il en va de m~me pour chacune des 2k-P -1 sommes analogues,
c o m m a n s a n t aux indices i mult iples de 2 p+l. I1 ea r6sulte que les 25 fonctions rectangulaires
engendr6es par les 2 k expressions (18) possibles out pour valeur § 1 ou -- 1 sur chacun des intervalles d ' une p6riode et qu'elles sont mutuellement orthogonales
deux ft deux, comme diff6rant par le signe 4 'au too•
u n facteur. Ce syst~me est donc identique ~ celui des
25 premieres fonctions de Walsh, h l 'ordre et au signe pr6s, en ver tu du caractbre orthogonal el complet du syst6me des 2 ~ premi6res fouctions de Walsh.
D 6 m o n s t r a t i o n d e l a p r o p r i 6 t 6 Y.2.1.2.
E t a n t donn6 un polyn6me de la forme P(y), nous appelons sdquence (*) de ce polyn6me le uombre de changements de signe entre deux coefficients succes- sifs, le polyn6me & a n t d6velopp6 sous la forme (19).
L ' in t roduc t ion du code Gray r6sulte de ce que si la s6quence d ' un polyn6me change d 'une unit6, le signe d ' u n facteur et d ' u n seul a chang6 dans l 'expression (18).
Consid6rons, en effet, une expression de ]a forme (18) arret6e au degr6 2p+1 -- 1, c'est-i~-dire :
P(y) = (1 • y)(1 • y2)...(1 • y~),
(p + 1 facteurs) ,
et soit S~ sa sdquence. Si Sp est pair, la fonction d6finie par P(y) a l e
m~me signe aux deux extr~mit6s de son interval le de
d6finition (comprenant 2~ +1 intervalles 616mentaires).
(*) La s6quence s de la fonction de Walsh correspondante est la moiti6 de ce nombre arrondie h l'entier sup6rieur, car la s6quence d'un polyn6me telle que d~finie ici correspond au hombre de passages par zdro de la ]onciion W (x) c~)rres- pondante, sur rintervalle de ddflnition ouvert :
- - 4 2
t . 27 , n ~ 1 - ~ 1 9 7 2 ] D E F I N I T I O N A N A L Y T I Q U E D E S F O N C T I O N S D E W A L S H 13/17
Si Sp est impair, cette m~me fonction a des signes oppos6s aux deux extr6mit6s de son interval le de d6finition.
Multiplier cette fonction par 1 + y2p+l revieut h la r6p~ter pour obtenir une fonction couvran t 2P +2 intervalles 616mentaires. La mult ipl ier par 1 -- yZp+l revient de m~me h la r@6ter apr~s l 'avoir ehang~e de signe.
Dans le premier eas, la s6quence Sp+ 1 de la fonetion obtenue sera : 2 S v si Sv est paire et 2S~ + 1 si Sp est impaire (car un changement de signe avec passage par z6ro in terv iendra au d6but du 2v +1 6me intervalle).
Dans le second eas, la s6quenee Sv+ 1 sera, pour la m6me raison, 2 S v si Sp est impaire et 2 Sp -t- 1 si
S v e s t paire :
i 2 S p , si S v e s t paire,
Sv+I = i 2 Sp § 1, si S v e s t impaire, (22)
2 S v , si Sp est impaire,
SP-+I= 1 2 S ~ + 1, si S v e s t paire.
Supposons m a i n t e n a n t que la s6quence du poly- n6me P(y) varie d 'une unit6 sans que son degr6 varie.
Ceci est possible :
- - soit si le facteur de degr6 2v a ehang~ de signe sans que la s6quence S~_~ des facteurs de moindre degr6 n ' a i t chang6,
- - soit si le facteur de degr6 2v u 'a pas chang6
et que la s~quence Sv_ 1 des facteurs pr6c6dents nit chang6 d 'une unit6.
(En effet, il r6sulte de l 'appl ieat ion des r6gles (22) que si ces deux circonstances se produisaient simulta- n6ment , la s6quence de P(x) var ierai t de 0 ou de 2 u n i t & )
En app l iquan t de proche en proche ce r6sultat de droite h gauche, et compte tenu du fait que si la
s6quence d ' u n produi t de facteurs ne varie pas aucun des signes de ses facteurs ne peut varier, on voit q u ' u n seul signe a vari6.
Pour ordonner par s6quences croissantes les 2k polyn6mes de la forme (18), nous commencerons donc par le polyn6me :
Po = (1 + y ) ( 1 + /12 ) ( 1 + y d ) . . . ( 1 + y2k-1)
ayan t k facteurs avec le signe + et den t la s6quence est 6videmment nulle (tous ses coefficients va lan t + 1).
Par appl icat ion de la r~gle (22), la s6quence deviendra 1 si nous changeons le signe du facteur de degr6 sup6rieur, d'ofl :
P1 = (1 + y ) ( 1 q- y 2 ) . . . ( 1 + y 2k-2)(1 - - g 2 k - 1 ) ,
et, r6p6tant cette proc6dure de proehe en proehe, nous voyons que, le signe § eorrespondant ~ 0 et le signe - - h 1, le choix des signes darts l'expression de la lorme (18) qui reprdsente une fonction de Walsh est d~fini par la representation de son rang, N, en code
binaire rdfldchi. Rappelons que, si la repr6sentat iou binaire d ' un
nombre est ak ak_, . . . . a 0 (a I = 0 ou 1), la repr6sen-
ta t ion en code binaire r6fl6chi est d6finie p a r :
bkbk_l. . , b o , avec :
b 0 = a 0 (~ a l ,
(23) b 1 = a 1 @ a2,
bk = ak ;
ou r6eiproquement :
ao ~- b o (~ b 1 (~ ... (~ bk ,
(24) a 1 = b 1 @ b~ (~)... 0 b/~, . . . . . . . . , . . . . ~ . . ,
ak = bl~.
D 6 m o n s t r a t i o n do l a p r o p r i 6 t 6 V.2.1.3.
L 'op6rat ion W* W', telle q u ' d l e est d6finie par la formule (2) est lin6aire par rappor t h chacun de ses composants.
Nous pouvons donc obtenir le produi t de convo- lut ion de deux fonctions de Walsh par la somme des produits de convolut ion 616mentaires des fonctions qui ne diff6ront de z6ro que sur un seul interval le et
den t chacune des fonctions de Walsh est la somme. Ces fonctions 616mentaires correspondent aux
termes successifs de la repr6sentat ion polyn6miale d6velopp6e de chaque fonction.
On volt imm6dia tement , en subs t i t uan t dans la formule (17) de telles fonctions quo le produi t de convolut ion d 'une fonct ion qui ne diff6re de z6ro que sur l ' in terval le p off elle vau t 1 par une fonct ion qui ne diff~re de z~ro que sur l ' in terval le q off elle v a u t 1 est une lonction triangulaire va lan t l ' un i t6 pour
i = p -- q, d6croissant l in6airement de par t et d ' au t re de cette valour pour a t te indre z6ro pour i = p - - q q- 1 et i = p - - q -- 1, ce produi t de convolut ion 6tant nul pa r tou t ailleurs (Fig. 7).
1.7 .... 7-t 7 N ' 1 2 3 1=~3 4 5 6 7 8 9 10 i
i Y!(Y)XW'(1/Y)=Y 3
Fro. 7. - - Produit de convolution 616mentaire.
Toute somme de telles fonctions tr iangulaires est 6v idemment ddfinie par la suite de ses valeurs aux extrdmilds des intervalles, la fonction elle-m6me 6tant obtenue en rel iant ces points de d6finition par des segments de droite.
Nous voyons donc que si :
W(x) = P(y),
W'(x) = P '(y) ,
on aura :
(25) O(x) = W * W' -= P(g) P ' ( l / g ) .
On remarquera que P*(y) 6taut le polyu6me
r&iproque de P au sens de Peterson [7], on a,
- - 4 3
14/17 c . C A R D O T [ A N N A L E S I)ES T I~L~COMMUNICATIONS
m o d u l o (y2~ -- 1) :
P ( I / y ) = g P * ( g ) .
V.3. Produi t s de c o n v o l u t i o n des f o n c t i o n s de W a l s h .
V.3.1. I1 r~sul te de ce qui pr6cSde que le p r o d u i t
de c o n v o l u t i o n de d e u x fonc t ions de W a l s h est d6fini
pa r le p r o d u i t des r ep r6 scn t a t i ons po lyn6mia l c s en g
e t 1/y de ces d e u x fonc t ions . E n d 6 v e l o p p a n t ce
p rodu i t , m o d u l o (g 2k - - 1), on o b t i e n d r a un p o l y n 6 m e
coeff icients r6els :
y2~-z Q(g) = c o + c l g + ... c2~ ~
c o es t la v a l e u r du p r o d u i t de c o n v o l u t i o n ~ l 'o r ig ine ,
c 1 sa v a l e u r h la fin de l ' i n t e r v a l l e n ~ 1, ... c2~_~, sa
v a l c u r A la fin de l ' i n t e r v a l l e n o (2k - - 1) qui es t le
de rn ie r de la p6r iodc.
Le p r o d u i t de c o n v o l u t i o n lu i -m6me sera repr6sen t6
pa r une l igne bris6e j o i g n a n t ces va l eu r s (Fig. 8).
+4-
sal 1 -- 1 + y- y2 y ! rood (x 4-1) = P (y)
cal 1 =- 1 + y + y2. y3 rood (x ~'- 1) = P'(y)
P'(1/y)=- 1-y+y2+y 3
sal l~cal 1 P(y) P'(I/y)=O-4y+O+4y ~
O- 2n
- 4 . - ~ I
FI~. 8. - - Produit de convolution de ('eux fonctions de Walsh.
V.3.2. Nous 6crirons alors les p o l y n 6 m e s P(y) e t P ' ( 1 / y ) sous la f o rme fac tor i s6e (18) et nous ef fec tue-
rons le p r o d u i t des f ac teu r s co r r e spondan t s , de m 6 m e
degr6 en g clans P(y) e t c n 1/y dans P ' ( 1 / y ) .
Le p r o d u i t ob t enu , qui dSfini t le p r o d u i t de convo-
l u t i on des fonc t ions de Wa l sh consid6r6es, sera le
p r o d u i t de k f ac teu r s de la f o rme :
F2v(Y) = [0 _+ y2V)(1 _+ ( l /y)~v)] .
Ces f ac t eu r s o u t a priori l ' une des q u a t r e f e rmes
s u i v a n t e s :
(26) (1 + g 2 v ) ( l § 1/y 2v) = 2 § g2P + 1/g2P,
(27) (1 - - y 2 V ) ( 1 § 1/g 2p) = (1/g 2p) - - y 2 v ,
(28) (1 + y2V)(1 - - 1/y ~v) = gzv _ l /g~P,
(29) (1 - - y 2p ) ( 1 - - 1 / y 2p) : 2 - - y 2p - - 1 / g 2p .
Les fo rmes (27) e t (28) son t identiques au signe pr~s.
Si donc nous n6gl igeons le s igne du p r o d u i t de convo-
lu t ion , chacun des k fac teurs d o n t il se compose ne
p e u t avo i r que trois /ormes 1
- - l a fo rme + 1 [ou (26)] s ' i l est le p r o d u i t de
2 f ac teu r s a y a n t le s igne + ;
- - la f o rme - - 1 [ou (29)] s ' i l es t le p r o d u i t de
2 f ac teu r s a y a n t le s igne - - ;
- - la f o rme 0 [c ' es t -~-d i re (27) ou (28) s ' i l es t le
p r o d u i t de 2 f ac teu r s a y a n t des s ignes cont ra i rcs .
Or les sigucs successifs qui f iguren t dans los po ly -
n6mes P(g) et P ' ( 1 / g ) son t les r e p r 6 s e n t a t i o n s en
code G r a y des t angs des fonc t ions de W a l s h corres-
p o n d a n t e s (+ c o r r e s p o n d a n t ~ 0 et - - ~ 1).
Si, dour , uous d6finissons c o m m e sui t la C-addition de deux hombres binaires de k chi/]res, pour obtenir
un hombre ternaire de k chif/res, ces dern iers p o u v a n t
va lo i r O, + i ou - - 1, pa r les rbgles d ' a d d i t i o n sui-
van t e s , chiffre p a r chiffre e t sans r e t e u u e :
1 + 1 = + 1 , c
(30) 0 + 0 = - - 1 , r
1 + 0 : 0 + 1 = 0 , r C
nous abou t i s sons au :
Th6orbme. - - Le produit ae convolution de dcux [onctions de Walsh est ddfini, au signe prds, par la C-somme de leurs rangs, dcrits en code binaire rdfldchi.
I1 en r6sul te i m m 6 d i a t e m c n t qu'i l ne peut exister que 3 k produits de convolution dislincts dans l'ensemble des 2 k premidres /onctions de Walsh, ce n o m b r c 6 t an t
celui des h o m b r e s t e rna i r e s diff6rcnts , de k chiffres
(le n o m b r e t o t a l des p r o d u i t s de c o n v o l u t i o n possibles
a priori 6 t a n t 4k).
V.3.3. D~inition des termes identiques clans la matrice universelle de diaphonie.
N o u s avons d6mon t r6 que , dans l ' e n s e m b l e c o m p l e t
des 2 ~ p remie res fonc t ions de Walsh , il p o u v a i t
ex i s t e r au plus 3~ p r o d u i t s de c o n v o l u t i o n d i s t inc t s
(an s igne pros). Mais nous savons qu ' i l ex i s te un cer-
t a i n de ces p rodu i t s qu i s o n t i d e n t i q u e m e n t nuls
(p rodu i t s de c o n v o l u t i o n en t r e fonc t ions a p p a r t e n a n t
h des classes de d i a p h o n i e a y a n t des va l eu r s diff6-
r en tes de k0). Nous al lons d 6 m o n t r e r que le n o m b r e
de p r o d u i t s de c o n v o l u t i o n d i s t inc t s est exactement 3 ~ pour une classe de diaphonie conlenant 2 ~ /onctions
de Walsh.
V.3.3.1. Le produit de convolution de deux [onctions de Walsh est identiquement nul si et seulement si le dernier chi//re ternaire de la C-somme de leurs rangs,
~crils en code Gray, est O.
E n effet, le calcul m o n t r e i m m ~ d i a t e m e n t que darts
le cas off la C- somme se t e r m i n e p a r un z6ro, le fac-
t e u r F2k - - l (y) darts le p r o d u i t Q(g) es t 6gal h 0
m o d u l o (y2k _ 1).
S i c e chiffre es t + 1, ce f a c t e u r es t 6gal h :
2 y2k-1 ;
- - 4 4 - -
t. 27, n ~ 1-2, 1972] D I ~ ] F I N I T I O N A N A L Y T I Q U E D E S F O N C T I O N S I ) E \ V A L S H 15/17
si ce chitIre est - 1, ce facteur est 6gal i~ :
- - 2 g ~ - i ,
et dans ces deux derniers cas, Q(g) tie peut pas etre iden t iquemeut nul, quelle que soit la forme des autres facteurs Fk(g) de degr6 infdrieur.
V.3.3.2. Deux polgndmes Q(y) non rods ne peuvent
~tre identiquemenl @aux s'ils onl un ou plusieurs
facteurs Fh(y) diffdrents ovec h ~ 2 k 2.
Ceei r6sulte du fait que, dans l ' anneau consid6rG un polyn6me de degrd in[drieur & 2 k ~ ne peut etre faetoris6 que d 'une seule mani6re : les crit6res de divisibilit6 de l 'algbbre ordinaire demeurent valables
t a n t q u ' a u e u n terme n ' a t t e i n t le degr6 2C
Si nous consid6rons m a i n t e n a n t un iquemen t les fonctions de Walsh appa r t enan t h une mdme elasse
de diaphonie, nous avons demontr6 que leurs produits de convolution mutuels n'dtaient pas nuls. Les C-sommes diff6rentes eorrespondront done ~ des produits de convolut ion diff6rents, et r6ciproquement, d l'int@ieur d'une m~me eIosse.
Les classes de diaphonic 6tant toutes isomorphes, nous 6tudions ci-apr6s lo premiOre elasse de /onctions
poires, c'est-h-dire la sdrie des fonctions eal (2 p + l , x) ayan t pour s6quence la s6rie successive des entiers
impairs.
Darts l 'expression binaire simple de leur rang, le dernier 616ment binaire est 0 (puisque ee sont des fonctions de Walsh paires) et l ' avan t -dern ie r 616ment binaire est 1 (puisque leur s6quence est impaire).
Les 616ments binaires suivants , h par t i r de l 'antd- penultiS-me, ddfinissent le mtm~ro d'dquivolenee e,
6erit en base binaire ordinaire.
I1 est ais6 de voir, au moyen des formules (23) que si l 'on @rit les rangs N en code Gray, le dernier 616-
m e n t binaire est toujours 1.
La s6quence de la fonetion va r i an t de 2 unit6s lorsque l 'on passe d 'une fonction h la suivante, il
r6sulte des memes [ormules que :
- - l ' avan t -dern ie r 616ment binaire de rang ecrit en Gray change de valeur,
- - un autre parmi les el6ments binaires pr6e6dant l ' avan t -dern ie r change aussi de valeur.
On volt done f inalement que l 'antOpdnulti6me 4le- men t binaire et eeux qui le pr6e6dent /~ gauche deft- nissent lo lranscriplion en code Grog du numdro d'dquivulence (la premi6re fonction ayan t pour num6ro d '6quivalence 0, lequel est represent6, en binaire simple eomme en binaire r6fl6chi par k -- 2 zeros, et un seul 616ment binaire dans ce groupe changeant de valeur lorsque l 'on passe d 'une fonction ~ la suivante).
I1 en r6sulte le
Theorbme. - - La C-somme des numdros dVquiva-
lence, dcrils en code binaire Mfldchi, ddfinit de mani@e univoque le produit de convohztion de deux /onclions de
Walsh appartena• d la mgme classe d'dquivalence dia-
phonique, et leur eourbe de diaphouie.
I1 existe done exactement 3 k fonctions de diaphonie distinetes (au signe prbs) dans la classe d '6quivalenee eon tenan t 2 k fonctions de Walsh.
I1 y a done 4 k - 3 k relations d'dgalit6 entre les termes de cette matriee, parmi lesquelles 2 2 k - 1 - - 2 k - 1
resul tent s implement (te la sym6trie de la matrice et :
N i t - - 2 2k-~ i- 2 k-1 - 3 k ,
rdsnl teut de l '6galit6 entre prodni ts de convolut ion de couples di[fi!rents de fonctions de Walsh.
V.3.4. P r o g r a m m a t i o n .
La figure 9 repr6sente Forganigramme d 'un pro-
gramme exploitable sur la calculatrice d6jh cit6e, qui permet de tracer les produits de diaphonie de la classe d '6quivalence eon tenan t 8 fonctions. On n ' a repr6sente qu ' un seul des produits 6gaux, tels que
PN,N" et PN'N. Cette classe est la plus grande dans le groupe des
32 premi6res fonetions de Walsh.
La figure 10 represente ces produits de convolut ion sur un quar t de pdriode. Chaque procluit de convo- lut ion dolt 6tre eompldt6 par ant isym6tr ie au tour de son extr4mit6 droite et par sym6trie autour de son
extrOmit6 gauctle.
H a r m u t h avai l pr6cedemment publi6 [5, pp. 152- 153] une table analogne relative h la classe d '6qui-
valence con tenan t 4 fonctions.
I/.3.5. E m p l a c e m e n t des re la t ions d'dgal i td .
La figure 10 correspond ~ la mollie inferieure de la matr ice (syn16triqne) dont chaque terme est un produi t de convolution.
Les relations d'egalit6 autres que eelles resu l tan t de la sym6tvie soul repr6sent6es par la figure 11 (denx eases reli6es par un t ra i t correspondent au meme produi t de convolut ion au signe prSs et h la
meme courbe de diaphonie).
L ' emplacemen t des relations d'6galit6 dans la matrice h 2P +1 lignes et colonnes, soil Ap+~, se dedui t de l ' emplacement desdites relations dans la matriee Ap par la construct ion r6cursive indiqu6e figure 12 : TAp represente la matr ice A v retournee (en 6crivant les colonnes daus l 'ordre inverse) et les deux matrices TAp qui s ' in t roduisent clans Ap+ 1 ont leurs 616ments sym6- tr iques reli6s par une relation d'egalit6 (puisque la
matrice Apq~ est sym6trique).
V.3.6 . Re la t ion avec la s o m m e di recte des rangs.
Si l 'on repr6sente semblablement les 6galit6s dans
la table d ' addi t ion directe N @ N' des 2~ premiers nombres binaires, soit A ' v , on constate que la meme construct ion rdenrsive peut etre appliqu6e, mais que la matriee A' 1 (Fig. 13 a) eomporte une relat ion de plus que la matrice A 1 (Fig. 13 b).
On obt ien t ainsi une d6monstra t ion gdomdtrique
simple du
- - 45 - -
16/17 c . C A R D O T [ANNALES DES T~L~:COMMUNICAT,ONS
[eiO oui non
' I ! e=e+l
t Calculer W (N, i)
e : : e ' = 0 ] -1 " t
I N:4e+2 d
I N'=4e'+2
h:O;P:O i"
i= -15 I
i '= i+h I l
ICalculerW'(N',i') I I
P--P +WW' 1
ti=,§ I
OUI non
OUI
[ e '=e '+ l ] . . L
(volt figure 2 t pattie inf6rieure)
non
sortir Pee'(h) = P
P = 0
t
Fro. 9. - - Organigramme d'un programme permettant de tracer les produits de diaphonie de la classe d'6quivalence contenant 8 fonctions.
Th6orbme. - - Pour que deux couples de /onctions de Walsh /ournissent le m~me produit de convolution
(au signe pros), une condition n6cessaire, mais non suffisante, est que la somme directe des rangs dcrits en code binaire simple soil la mgme pour ces deux couples.
VI. ~ O N C L U S I O N
L' in t roduc t ion d 'une repr6sentat ion t r igonom6tr ique
simple et d 'une repr6sentat ion polynomiale des fonc- t ions de Walsh a permis d ' about i r ~ u n calcul exact
de leur spectre de fr6quence et de leurs produits de convolut ion mutuels .
Ces r6sultats th6oriques conduisent h des formules p e r m e t t a n t d 'ob ten i r la diaphonie r6sul tant du filtrage
dans un mul t ip lex h porteuses Walsh.
Dans une prochaine 6tude, nous compl~terons ces r6sultats par la d6finition des coefficients d'influeuce de l 'erreur de synchronisat ion, coefficients que l 'on obt ient ~ par t i r de la pente au d6part des produits de convolut ion.
Les r6sultats essentiels du pr6sent t ravai l ont 6t6 pr6scnt6s h l 'Acad6mie des sciences par M. M. Ponte , le 20 d6cembre 1971 [8].
Manuscrit reeu le 22 novembre 1971.
R E 3 I E R C I E M E N T S .
L' auteur est heureux de remercier ici Monsieur Patrick
Lebail, Ingdnieur en chef, de son amicale collaboration.
- - 4 6 - -
t. 27, n ~ 1-2, 1972]
\ 0
D~:FINITION A N ALYTIQUE DES FONCTIONS Dig WALSl t
/ ' x 1 3 4 5 6
NUMEROS D'EOUIVALENCE
I"IG. 10. Produits de convolution sur un quart de p6riode.
76
5
4
A A 3 V V
. , , v v ~ 2
A ~ 1 w
7
17 /17
m
7
/ / Z
/ / '%/
/ /
/ % /
V> / / /
6
5
3
2
1
0
I:m. 11 - - I lepr6senta t ion matrMelle des relations d'6galit6.
0 1 2 3 A TAp 0 1 ~ 0
h p ~ l = P h l = ~ ~ A2 = 1 TAp Ap 2
3
Fro. 12. Construction par r@urrence de la nmtrice Ap+l.
0 1 0 1
FIG. 13. - - Matrices de d6part : A' 1 et A 1 .
B I B L I O G R A P H I E
[1] HADAMARD (J.). 1Rdsolution d 'une question relative aux d6terminants. Bull. Sci. math., Ft. (1893), s6rie 2, p. 171.
[2] PRATT (~r K.) , KANE (J.), ANDREV/S (H. C.). Hada- mard transform image coding (Codage des images l 'aide de la transformde de Hadamard). P.I.E.E.E., tr. S. A. (janv. 1969), 57, n ~ t, pp. 58-68.
[3] LACKEY (R. B.), MELTZER (D.). A simplified defini- tion of Walsh functions {Definition simplifide des fonc- tions de Walsh). I.E.E.E. Trans C, U . S . A . (fdvr. 1971), 20, n" 2, pl ). 211-213.
[4] SCHRE1BER (H. H.). Bandwidth rectuirement.~ for Walsh functions (Bande passante ndcessaire h la trans-
mission des fonctions de Walsh). I.E.E.E. Trans., IT, U . S . A . (juil. 1970), 16, no ~, pp. ~91-~93.
[5] HARMUTH (H. F.). Transmission of information by orthogonal functions (Transmission de l ' information par des fonetions orthogonales). Springer, New York (1969), 322 p.
[6] VILLE (J.) . Thdorie et applications de la notion (le sign'~l analytique. Cdbles et Transmis., Fr. (1948), 2, n ~ 1, pp. 61-74). (Hors commerce.)
[7] PETERSON (W. W.). Error correcting codes (Codes correcteurs d'erreurs). John Wiley, New York (1961), 285 p.
[8] CARDOT (C.). Ddfinition analyt ique non rdcursive des fonctions de Walsh-Hadamard. Application h la ddter- ruination de leurs propridtds spectrales. C.R. Acad. Sei., ,4, Fr. (3 janv. 1972), 274, n ~ 1, pp. 66-69.
- - 47 m
