n~~~ V E R S I ~ N M A T R I C I A L PARA LOS ALGORITMOS RAPIDOS E N E L CAL-

CULO DE LA TRANSFORMADA DE FOURIER DISCRETA",

Resumen. El propdsito de este trabajo es obtener 10s

algoritmos cl6sicos directamente a partir de

factorizaciones de la matriz que define la

transformada de Fourier Discreta.

N O V I E M B R E 1 9 8 4

* F A C U L T A D D E C I E N C I A S , U N A M .

INTRODUCCION ,

La t r a n s f o r m a d a d e F o u r i e r e s a m p l i a m e n t e c o n o c i d a y se .

u s a p a r a descomponer una f u n c i d n como l a suma d e s e n o i d a l e s d e

d i f e r e n t e s f r e c u e n c i a s , h a s i d o u n a h e r r a m i e n t a a n a l i t i c a muy

i m p o r t a n t e e n a p l i c a c i o n e s a d i v e r s o s campos d e l a c i e n c i a c o -

- mo p o r e j e m p l o e n s i s t e m a s l i n e a l e s donde l a t r a n s f o r m a d a d e

F o u r i e r d e l a s e a a l d e s a l i d a e s t d d a d a p o r e l p r o d u c t 0 d e l a

f u n c i d n d e T r a n s f e r e n c i a d e l s i s t e m a y l a t r a n s f o r m a d a d e Fou - p i e r d e l a s e a a l d e e n t r a d a . L a s o l u c i d n d e e c u a c i o n e s d i f e -

r e n c i a l e s con v a l o r e s a l a f r o n t e r a s e puede r e d u c i r m e d i a n t e . .

l a Trans fo rmada d e F o u r l e r , ' s l mismo a p l i c d s u s m t t o d o s p a r a

l a s o l u c i d n d e l a e c u a c i S n d e c o n d u c c i S n d e l c a l o r . E l campo

d e a p l i c a c i d n d e l a n d l i s i s d e F o u r i e r e s muy a m p l i o e n l a m a t e - m a t i c a e i n c l u y e r amas d e l a f i s i c a como d p t i c a , mecdn ica cudn - tics, e t c .

S i queremos o h t e n e r l a t r a n s f o r m a d a d e F o u r i e r d e u n a f u n - 4 c i d n e l e m e n t a l debemos b u s c a r l a e n un manua l ; p e r o puede s u c e -

d e r que 10s v a l o r e s d e l a f u n c i d n e s t e n s o l a m e n t e d a d o s e n p u ~

t o s d i s c r e t o s d e l a v a r i a h l e i n d e p e n d i e n t e , como e n e x p e r i m e n -

t o s f f s i c o s h e c h o s a r n t e r v a l o s r e g u l a r e s d e t i e m p o . S i l a 'a

t r a n s f o r m a d a e s e v a l u a d a n u m t r i c a m e n t e e n una computadora s 6 -

l o t endremos s u s v a l o r e s e n p u n t o s d i s c r e t o s , p o r ' l o t a n t o , e s

n e c e s a r i a una t e o r f a m a t e s e t i c a a d e c u a d a p a r a e l t r a t a m i e n t o

r( 0) a a I a

a f u r ( tJ v) a a m h W m f i 3 m k a ~ k ~ m m a

a 0 k a d a y l m o m w a a o c a c m m a 1 0 -4 d + ' + ' E * d C k m 1 a J L J 1 Q) a - c ( m

6 4 ' 1 m m a 0 r( r( r l m u a m

a +' * . Q) m ' d m c a J

C a r( m m I m w r ( r ( + J 1 z r l ' m d . 'd v) - a w a a a

a o v a k c '4 4 'd 0 0)

a 0 \ m r ( a ~ - c c a a x m o -I m m a a ~ m

k 'd ' '4 11 a m ~ J ' L J ~ ( k

3 a ~ a o m a N Q r( V)

Id m 0 a J m a m a b O $ u . . - k a ~ c a a m

Y Z ' d m m a J C a 3 m a k w a c C1 E 0 r( v) 0

3 -d k 1 l d a J a J - d V) a m cn c LJ

'44 IaJ d 0 m r 0 I 0) 0 r ( . Q * d CJ IW IL . 2 C M (d LJ * d Z -n 412 or( 2 k " a

+ ' A 1 0) '4 11 rl E k o a + '

Q, m J W d 0 4

z v) n m ck 3 Q) C a J - d u l B

u c 4 - 1 a a m .<W ' U) r(

3% e m r( (Y

m m k ~ a h a m 4 .aJ 0 d 1

0) - d a o +' a. . a . k f U C L J a l El 34'."r(9)a 0 O * d k y c k g a CL( a a .a

n a H

rl aJ I * ' I m l g

I 0 0 c 'd

(a " B O G

a 1 vl

0 0 o aJ r ( C ' a h d -d a aJ Q) 0 a a u m c l c +'

1 u d m 1 o $ r ( r ( a J . d

k t m I d e a

w 1 0 u LJ N n 3 -4 e $ .I m *r( a a a 0 0 1 f i k ~

* k E n r ( 0 - 0 0 'Y 4 ' - m + ' b V E O O d C L ( $ LJ + ' h Q k * a J a m 0 *rl ' d o b e Y I d G k h m W Q 0) 0 Q, r ( m r ( w r ( c m J r ( m E

k U r ( 0 m m m a c m o o a c a c

0 E Q O -4 c r( k 0 .d 0 ' 4 4 1 9 ) a J L J o o a a

'3 -4 r ( k o a m * C k m 1 0 4' aJ

0 m 7 0 u a - IQ, a ~ L J O O E ~ ( O ~ E 1

c C L ( a \ m k a l I0 m k O & C

0 ' 2 c * d o a -4 0 1 z a a k d h ' d 6 k 0) al LJ C d a m w 0 Id a

2 C

L J f i * d a m r c o c m m m k k b O * d m a g

0 0 ) - m a r ( m 0 a + ' r ( m a k a m o k u d o k -I a 4 m O Z C m J C , I 0

c m 0 r( a 'd m k C 1 m r o m r ( m m 1 E o

E 0

Q I a J a J a J C , O O C d k Q V C a J E Q *A

0 c a o a m 0 m n k Z t v

+ ' a d = k 0

c m m + ' . a o m & M a m w + ' c ~ m o o

= r ( a J a J a Fl M Q ) ~ r ( + ' o m 4 a a a J v , l d a J v ) k ~ a I

a c k a o a o c * m r ( + ' d o + '

~ c r n a ~ r c * d a W * d LJ - r ( m a a a 1

.c 0 w ~ m a ~ a m

a C 0

0 1 a 1 0 0 -4 GI Q E Q O ' W G a

h a l a p a r t e f i n a l d e e s t e t r a b a j b s e tiace n o t a r q u e 10s .

a g t o d o s que usamos p e r m i t e n o b t e n e r o t r a s f a c t o r i z a c i o n e s ,

p o r e jemplo , en e l c a s o N - pq con p y q p r i m o s r e l a -

t i v o s , dando l u g a r a nuevo.5 a l g o r i t m o s .

'LA TRANSFORMADA DE FOURIER DISCRETA

La r e p r e s e n t a c i b n d e F o u r i e r de una f u n c i 6 n f ( x ) d i -

f e r e n c ' s a b l e 2 n - p e r s b d i c a es b i e n conoc ida y e s t d dada

p o r :

E Zkx . f Cxl =,p-mCke

donde

Las c* . son l l a m a d a s c o e ' f i c i e d t e s d e F o u r i e r d e l a f u n -

2n Dados N v a l o r e s ' {xt,f ( x l l 1 ,L = 0,. . . , N - l , x l = ~ l,

c a l c u l a r aproximadamente 10s c o e f i c i e n t e s d e F o u r i e r ck.

P a r a o b t e n e r una s o l u c i d n es u s u a l a p r o x i m a r l a i n t e g r a l

que d e f i n e ck m e d i a n t e l a r e g l a d e l T r a p e c i o , o b t e n i g n d o s e

donde

rc.

Es f S c i 1 v e r q u e l a s u c e s i b n (ckf es N - p e n i S d i c a , p o r rr rc.

l o t a n t o b a s t a c o n c a l c u l a r 1 ~ 0 0 ~ 1 #cN-, 1. En t s r m i n o s

d e matrices l a a p r o x i m a c i d n a n t e r i o r toma l a fo rma

Abordaremos e n un c o n t e x t 0 mds g e n . e r a 1 e l p r o b l e m a d e

o b t e n e r l a s Zk.

Problema 2

h C a l c u l a r d e manera e f i c i e n t e 2 , d a d a p o r .

L a i g u a l d a d a n t e r i o r r e c i b e e l nombre d e T r a n s f o r m a d a

d e F o u r i e r d i s c r e t a T.F.D.

E l nGmero d e m u l t i p l i c a c i o n e s a 1 , e v a l u a r d i r e c t a m e n t e e l

p r o d u c t o ' que d e f i n e a 1 v e c t o r es d e l o r d e n d e N ~ .

Usando adecugdamente l a s p r o p i e d a d e s d e l a m a t r i z WN Lo-

g ra remos una r e d u c c i b n c o n s i d e r a b l e d e l niimero d e multiplies-

c i o n e s , cuando N e s un nGmero c o m p u e s t o .

- Propiedades de la fiatriz W~

b ) La i n v e r s a d e WN e s c a s i l a m a t r i z c o n j u g a d a , e s d e c i ?

2 N-1 C) La suces - i6n {I, wN wN, ...., w 1. f o r m a un g r u p o c l c l i c ~ N

d e o r d e n N , i s o m o r f o a 1 g r u p o ZN de 10s e n t e r o s mbdc lo

N. [Fr]. .3

.-' d ) Si N = N l N 2 e n t o n c e s 'N2

s o n s u b g r u p o s d e = N

y s i adembs (N1,N2) 1 e n t o n c e s ZN e s e l p r o d u c t o d i -

r e c t o d e z ~ 2 9 e s d e c i r ,

P r i m e r o c o n s i d e r s r e m o s 10s c a s o s c u a n d o N e s p a r o p o t e n -

c i a d e d o s p a r a p r e s e n t a r l a s i d e a s b d s i c a s d e l a r e d u c c i b n .

E l c a s o g e n e r a l s e d e d u c e d e m a n e r a s e m e j a n t e . ,

Caso P a r .

S i N = 2 m r e o r d e n a m o s l a s c o l u m n a s d e WN, c o l o c a n d o p r i m e -

r o l a s d e l n d i c e p a r y d e s p u s s . l a s d e i n d i c e i m p a r p a r a o b t e -

n e r

d o n d e Im e s l a m a t r i z i d e n t i d a d d e o r d e n m, P2m e s l a m a t r i z

t d e p e r m u t a c i 5 n , y Dm =diag (u2m) , l = O,l, . . . ,m-1. P a r a o b t e n e r l a e x p r e s i d n f a c t o r i z a d a d e WZmPZrn s e u s a n

l a s r e l a c i o n e s

E s p o s i b l e e x p r e s a r e n f o r m a c o m p a c t a l a f a c t o r i z a c i 6 n

u t i l i z a n d o e l p r o d u c t o d e K r o n e c k e r [GO] d e d o s m a t r i c e s A y

B d e f i n i d o como

Con e s t e p r o d u c t 0 l a e x p r e s i d n W2* P2m se e s c r i b e coI?b

d o n d e

G e n e r a l i z a c i b n d e l c a s o p a r .

k Cuando N e s u n a p o t e n c i a d e d o s N = 2 s e t i e n e l a r e l a -

c i b n

k P 2 k = F 2 k diag h ( w k - l ) 8

2 2

l a m a t r i z F e s 2

d o n d e

e D2k- 1 = diag (o k ) , 1 = O, . . . , z k - ' - l [ Au-Ba] . 2

I t e r a n d o l a r e l a c i d n a n t e r i . 0 ~ c o n l a s m a t r i c e s

V2r = diag I F r ) , 2

Qk = P diag(P k-l). . . diag (P 2 ) 2k 2 2

p o r l o t a n t o

t t t Q: =diag(p 2) ... diag (P k-l) P 2 2 2

o b s e r v e m o s q u e

REVERSION BINARIA.

V i s u a l i c e m o s e l e f e c t o d e l a m a t r i z Q~ p a r a e l l o e s n e - k'

t c e s a r i o e n t e n d e r como o p e r a l a m a t r i z d e p e r m u t a c i b n P .

+ -: 2'

S e a

p o r c o m p o n e n t e s

t l a f u n c i d n q r ( s ) a s o c i a d a a l a p e r m u t a c i d n P s e d e f i n e c o -

2 mo

--* - -- I , II__CII_-.L. .- -- I..

P I Q)

Q) U 7 a Q) a 0) V)

k 0 '4 k Q ) . C, c Id

a m . a 0) rl E4 0 & c4

N o t a .

LI LI

La d i f e r e n c i a e n t r e l a s f u n c i o n e s 'P y Pr e s que Pr o p e r a r

s o b r e cada b loque d e tamafio 2' como o p e r a PI.

T e o r e m a .

t S i p (S) e s l a f u n c i b n a s o c i a d a a l a p e r m u t a c i b n Q k k Y

e n t o n c e s

La p ( . I e s l l a m a d a f u n c i b n de r e v e r s i b n b i n a r i a en k - b i t s . k

Ademds

DIAGRAMA DE FLUJO PARA EL CALCULO DE LA T. F . D . CUANDO N = 2k.

Conwbase en l a f a c t o r i z a c i b n a n t e r i o r e s p o s i b l e o b t e n e r

un d iagrama p a r a e l c d l c u l o de l a TFD e s una p r i m e r a v e r s i b n .

diagrama 1 . Cdlculo de la TFD de orden N = 2 k

Entrada (N, z)

z c- Qk

Para r =1,2,...,k

L zc-v z 2'

c >increment0 r

l z z + - 2k

Salida z

Nota. t '

En computacidn usamos el slmbolo " + " para indicar que

el valor en la expresidn de el lado derecho se guarda en la

variable de el lado izquierdo.

Ahora especificaremos con detalle la construccidn de la

operacidn V z. 2r

Como la matriz

V = diag (F =) 2r 2

r opera con vectores de orden 2 necesitamos regrupar el vector

z en vectores de este orden, as5

donde en zStr e l i n d i c e s denota e l b loque s - 8 s i m o y e l

Sndice r que e l orden de cada b loque e s zr.

Por l o t a n t o

D e t a l l e d e l d iagrama 1 p a r a e l c l l c u l o de V2r

C S l c u l o de V2r z

Para s = Oilf . . . # 2k-5 1

Z~ , r C -F2r [:"

r-]

2s+l ,r-1

i n c r e m e n t a (s)

A 1 d e s a r r o l l a r l a . e x p r e s i b n zStr por e l e m e n t o s , un . .' , , c d l c u l o s e n c i l l o p r o p o r c i o n a

Ahora si desglosamos exactamente el product0 F r zStr 2

recordando que

t D r-1 = diag (02 r ) 2

r-1 e=0,1, ..., 2 - 1 tenemos

. . . . . m rn I m a UI w . . . N e . . N

UI N N N N N . . . N

Observemos q u e e l r e n g l 6 n s 0 2 ~ + t y e l r e n g l 6 n

r- 1 s.2' + 2 + t s o l o d i f i e r e n p o r un s i g n o , e n t o n c e s c o n s o l o

c a l c u l a r l a m i t a d d e e s t o s r e n g l o n e s t e n e m o s t o d o e l p r o a u c -

t o F2r zSPr, a q u l e s d o n d e e s t a r e a l m e n t e e l g r a n a h o r r o q u a

h a b i a m o s p r o p u e s t o como o b j e t i v o a1 p r i n c i p i o d e e s t e d e s a r r o

110.

Diaqrama 3 I 1

sir c Cdlculo de F Z r Z

a; 4 s.2r

r- 1 P a r a t = 0 , 1 , . . . , 2 -1

g u a r d a n d o t empora1 ,mente un p r o d u c t 0 e n l a v a r i a b l e a p a r a d e s - p u g s h a c e r u n a s i m p l e suma y r e s t a .

I n s e r t a m o s 10s d i a g r a m a s a n t e r i o r e s e n e l p r i m e r y obte-

nemos . ' :3

C d l c u l o d e l a T.F.D. d e o r d e r , N = 2 k

E n t r a d a (N, 2)

2 * Q k Z

P a r a r = 1 , 2 , * * * , k

C d l c u l o d e V r z 2

P a r a s = 0 , 1 , . . . , ~ ~ ' ~ - 1

C d l c u l o d e F2.r z S t r

e 4 ** -.

r- 1 P a r a t = 0 , 1 , . . . , 2 -1.

t a 4-02r ~ e + ~ r - l + t-

Ze+2r-'+t ze+t-a

L 9 + t + V + t + a

> i n c r e r n e n t a t

> i n c r e r n e n t a s

3 i n c r e r n e n t a r - - - - - . -- - - - - - - - - - - - - - -

I z 2 4 -

2k

S a l i d a z

CALCULO DE LA PEZMUTACION Q k .

E l c a l c u l o d e l a f u n c i d n p k ( t ) , a s o c i a d a a l a p e r m u t a -

c i d n Qk se r e a l i z a d e manera s i m u l t a n e a a 1 c d l c u l o d e l d e s a -

r r o l l o b i n a r i o p a r a e l ndmero t , u t i l i z a n d o e l e s q u e m a d e

- C d l c u l o d e pk (t) a p a r t i r d e t

j c t

b + O

P a r a e=0,1, ..., k - 1 -4

+ [dl b + 2-b + ( j -2m) -

j + m

L> i n c r e m e n t a e '

s a l i d a p + b

E l d i a g r a m a que p r e s e n i a m o s a c o n t u n u a c i d n e s c o n o c i d o - ~ . ----,- - - -- - --- -

como l a v e r s i d n d e S a n d e - T u k e y .

C d l c u l o d e p k ( t ) a p a r t i r d e t

k P a r a t = O , . . . , 2 -1

b - o

P a r a 4. = 0 , . . . ,k-1

b - 2 . b + (j-2m)

j 4-m

> i n c r e r n e n t a 1 -

P 4 b

I n t e r c a r n b i o z <->z P t

s i ( p G t) i n c r e r n e n t a t

T + z P

2 4- Zt P

z + T t

> i n c r e m e n t a t --.. - - - -, ,--- --- - -- -

-*

--

L

A l g o r i t m o g l o b a l p a r a l a T.F.D. d e o r d e n 2 k

k E n t r a d a (N = 2 , z )

d

-- -

4,)

VARIANTE DEL ALGORITMO DE SANDE-TUKEY.

La f a c t o r i z a c i e n

W2k = V2k V2k-1 ... V2 Qk

p r o p o r c i o n a o t r o mgtodo p a r a e l c d l c u l o d e l a T . F . D . , e s t e

s e o b t i e n e d e l a s i m e t r i a d e W k y Q 2 k'

Tomando l a t r a n s p u e s t a e n l a f a c t o r i z a c i d n a n t e r i o r q u e -

e n e s t a v a r i a n t e t e n e m o s

t V:K = diag ( F 2 r )

p r o c e d i e n d o como e n e l c a s o a n t e r i o r o b t e n e m o s e l s i g u i e n t e

d i a g r a m a [ A u - Ba]

Cdlculo de QZ

- Algoritmo modificado para la T.F.D. de orden 2 k

CSlculo de p k ( t ) a partir de t

k Para t = 0 , ..., 2 -1

j + t

b + O

Para & = o , ..., k-1

b + 2 - b + (j-2m) -

j + m

> incrementa &

P + b

k Entrada (N = 2 , z )

* -.

- -

Intercambio z P* Zt

si ( p < t) incpementa t

T + z P - -- ------

Z + z P t

Z t +T

> increments t

4;)

Para u = O , l , . . . , k - 1

r + k - u

Cdlculo de V2r z

u Para S = O , . . . , 2 - 1

Ca lcu lo de F r z S t r r

-> incrementa t

I. > incrernenta s

-> incrernenta u

A S a l i d a z * - z ,k

ALGORITMOS DE COOLEY -TUKEY.

Otras variantes para la factorizacidn de W2k que se han

encontrado en la prdctica, las consideraremos ahora.

Tenemos

algunas veces es mds conveniente hacer un reordenamiento de

las columnas y renglones de las' matrices V2r ( r = 1 8 2 8 . . . , k )

lo que da lugar a la factorizaci6n siguiente

donde U 2 r = Q k V 2 r Q k * 1 C r C k .

Para entender claramente este nuevo reordenamiento nece-

sitamos la estructura de las matrices U2r, esta se obtendrd

como consecuencia del lema siguiente cuya demostracidn es

... - .--- - -- --- " - - --- -- - inmediata.

Si p (u) es la reversidn binaria del ntimero u en r bits, r

y r C k entonces

O<u<2 k-r implica

b ) s i v = C - 2 k-r y 0 < < 2r i m p l i c a

C ) s i u y v s a t i s f a c e n a ) y b ) i m p l i c a

Un c d l c u l o d i r e c t o p e r m i t e o b t e n e r l a s f b r m u l a s s i g u i e n -

t e s [ A u -Ba] .

k-r U2r e k-r+l = e k-r+l + e 2k-r+l + 2

s+t-2 s+X-2 s+C* * -. qr- (X'

"2' es+t.2 k-r+l k-r =

(es+e. 2 k-r+l - e

s+e 2 k-r+l k-r] o

+2 +2 zr

donde e s+L. 2k-r+1 Y es+~.2 k-r+l+2k-r s o n 10s v e c t o r e s d e l a

b a s e c a n d n i c a

€eo 9 - ,e,k-, 1 , p o r l o t a n t o l a e s t r u c t u r a d e l a s m a t r i c e s

queda

en bloques

donde

1 2 k - 2

; t = 0 , 1

en general

En forma compacta l a U r e s 2

donde

a p a r t i r de e s t a Gltima e x p r e s i 6 n s e o b t i e n e e l a l g o r i t m o s i -

g u i e n t e .

Algoritmo de Cooley-Tukey para T.F.D.

k Entrada (N = 2 , z )

Para r = l , . . . f k

6

4 3

Cdlcu lo de U r z r P 4 0

r-1 Para l = 0 , ..., 2 -1

c CBlculo de G2k-r+l z t , r

b + 13,-, (11 -.

b 2 I a * W r

-

v

.A k-r Para t = 0 , 1 , . . . , 2 -1

a + a + z ~ + 2 k - r + t

Zp+2k-r+t * z p + t - a

z p + t 'p+t + a

I--> increment: t

P + P + ~ k-r+l - - - - - . - -

> incrementa

> incrementa r

c a l c u l o d e Q=

I n t e r c a m b i o z

P a r a t=O , . . . ,N-1 b+pk(t)

s i (b < t) incrementa t

T * Zb

2 + z b t

> i n c r e m e n t a t

l z S a l i d a z +-

2k

F u n c i d n p, (t)

j + t

P + Q

P a r a 1 =0, ..., s-1

p + 2p + (j-2m)

j + m

S a l i d a p

Comentarios . Los a l g o r i t m o s a n t e r i o r e s [Co -Tu] ,[Go] s o n c o n o c i d o s

e n l a l i t e r a t u r a b a j o e l nombre d e T r a n s f o r m a d a d e F o u r i e r

r d p i d a , s e u s a n l a s i n i c i a l e s F .F .T . S i l a r e v e r s i 6 n b i n a r i a

s e a p l i c a a 1 p r i n c i p i o s e d i c e q u e e l a l g o r i t m o o p e r a c o n d e -

c i m a c i 6 n e n e l t i e m p o y s i s e a p l k c a a l f i n a l , q u e o p e r a c o n

d e c i m a c i 6 n e n l a f r e c u e n c i a .

FACTORIZACION DE W YATRIZ WN, EM EL CASO GENERAL N =mn.

S e a Pmn l a permutac idn d e l a s c o l u m n a s d e Wmn que a g r u -

pa p o r b l o q u e s l a s co lumnas s e g d n s u r e s i d u o m6dulo n , e s d e -

c i r

e n t o n c e s l a f u n c i S n 9 a s o c i a d a a l a p e r m u t a c i d n n o s queda mn

s i a s u v e z formamos b l o q u e s d e d i m e n s i d n m c o n 10s r e n g l o n e s

d e l a m a t r i z permutada o b t e n e m o s

A continuacibn veremos como queda explicitamente cada blo - que. Si 10s bloques son de la forma

entonces 10s e1emer:tos para cada bloque estardn 'dados por la

donde r y c son 10s Pndices de el rengldn p y la columna q en

W respectivamente. mn

El rengldn r estd dado por la expresidn

debido a que el elemento a ( s 0 e ) pertenece a1 s-(simo bloque P t q

de renglones y estd en e1,lugar p-gsimo, por otro lado ya

vimos que la expresidn para las columnas es

entonces

. pqn + s t m + pX mn

por lo tanto expllcitamente cada bloque es

= w ~e t n diag (w:,) (0Eq)

e n t o n c e s

s u s t i t u y e n d o e n WN PN e s i n m e d i a t o o b t e n e r [ Au - Ba] .

e n t e r m i n o s d e l p r o d u c t 0 d e K r o n e c k e r l a f a c t o r i z a c i d n q u e d a

t WN PN = (wn @ Im) diag (DN1 (In @ Wm)

Caso N = n k

La r e l a c i b n a n t e r i o r p a r a N = nk n o s d a

W n k Pnk = F n k diag (Wnk-I)

donde L r k = (W @ Ink-1) diag (Dnk) n n

= (Bs,t), 0 Cs,t < n

c a d a B k- 1 e s un b l o q u e d e o r d e n n d a d o p o r l a i g u a l d a d s,t

C k- 1 ~ ~ k - 1 = diag (onk), 0 C L < n

ademds l a f u n c i 6 n p (c) a s o c i a d a a l a p e r m u t a c i b n P k e s k n

vk(c) = rn k-l + s

'=:

De manera a n l l o g a a 1 c a s o c l S s i c o N = 2k, se o b t i e n e l a

f a c t o r i z a c i i j n

donde

Vnr = diag (Fnr), :5

l a m s t r i z d e p e r m u t a c i S n e s

Qk = Pnk diag(Pnk-1) . . . diag (Pn2) diag (P ) n