CoreFFTperimplementazionesuFPGA Universit`adegliStudidiPadovaDipartimentodiIngegneriadell’InformazioneCorsodiLaureainIngegneriaElettronica

Testo completo

(1)` degli Studi di Padova Universita Dipartimento di Ingegneria dell’Informazione Corso di Laurea in Ingegneria Elettronica. Core FFT per implementazione su FPGA (FFT core for FPGA implementation). Laureando: Francesco Verenini. Relatore: Prof. Daniele Vogrig. Anno accademico 2009/2010 - Padova, 23 Luglio 2010.

(2)

(3) !""#$%!. !" #$!%!&'! "()*$* +, -!%, . %'('* %),"/##('* ," !"# +, /& +,%#*%,',)* ,& 0$(+* +, %)*"0!$! "1("0*$,'2* 33-4 -("! !"# . 5*%','/,'* 6*&+(2!&'("2!&'! +(""( $%&&#'( *))!$* "1/&,'7 ($,'2!',5( +!""1("0*$,'2*4 8" +,%#*%,',)* . %'('* ,2#"!2!&'('*9 '$(2,'! ",&0/(00,* :;<=9 #!$ !%%!$! /',",>>('* %/ 3?@A +!""( )*+*,-4 =1/',",>>* +, '("! '!5&*"*0,( 5*&%!&'! +, *''!&!$! /& *00!''* $,5*&B0/$(C,"! &!""! %/! 0$(&+!>>! #$,&5,#(",4.

(4) !"#$% !"#$%&'()%"* !. !:. "#$%&'()*%#* +&,-*'*#(&* ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! /0(-1%&*2'% 3345 6,78&*)*%#, , 79% 92*-*))% ! ! ! ! ! ! ! !: 4,8#%-%1*( 3;<= ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! =#(-*7* '(2,'(2*8(! ?(--( ?34 (--( 334 ! ! ! ! ! ! ! ! ! ! ! !:! ?34 +,& 7,1#(-* +,&*%6*8* ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !:!: ?34 +,& 7,1#(-* ( 69&(2( A#*2(5 &,-()*%#, 2&( 4&(7$%&B '(2( 6* 3%9&*,& , ?34 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !. :!: :!.. C. 3(72 3%9&*,& 4&(#7$%&' D334E ! ! ! ! ! ! ! ! ! ! :! ! F%'+-,77*2G 6* 8(-8%-% 6,--( ?34 ! ! ! ! :! !: F%'+-,77*2G 6* 8(-8%-% 6,--( 334 ! ! ! ! :! !. 39#)*%#(',#2% 6,--( 334 *'+-,',#2(2(! !"#$%&'% ( )*+%'(,%#-* -*! &*'.# ! ! ! H2&9229&( *'+-,',#2(2*I( 6* J(7,!. ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !. : .. ! ! ! ! ! ! ! !. >. ! ! ! H2&9229&( *'+-,',#2(2( ! ! ! ! ! :!.! F%6*A8( ! ! ! ! ! ! ! ! ! ! :!.!: <,72*%#, 6,--0%I,&M%N ! ! !. ! ! ! !. /01 2'.!*'*-&(&%#- #3 ( 4*5+#-6"7$(8!* //9 ! ! ! !. ! ! ! !. ! ! ! !. ! ! ! !. ! ! ! !. ! ! ! !. ! ! ! !. ! ! ! !. ! ! ! !. ! ! ! !. ! ! ! !. ! ! ! !. + !/01*/*"#.()%"* 2345 * &*67$)()%"* &*1 &)60%6)#)8% .!. .!: .!.. . . > @ @. !. , -#$'##'$. :!. ! ! ! ! !. +. /( 87&&*$:; ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! .! ! H2&9229&( ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! .! !: HI*-9++% 6,- 8%6*8, , 9-2,&*%&* 7+,8*A8P, /, QRS5 '(++(29&( 6,* 8%,T8*,#2* WNk ! ! ! ! .!:! "'+-,',#2()*%#, , 8%6*8, ! ! ! ! ! ! ! ! .!:!: S(++(29&( 6,--, QRS ! ! ! ! ! ! ! ! ! ! Q=S5 ','%&*( 6,* 8('+*%#* ! ! ! ! ! ! ! ! ! ! ! .!.! "'+-,',#2()*%#, , 8%6*8, ! ! ! ! ! ! ! !. ! ! ! ! ! ! ! !. ! ! ! ! ! ! ! !. ! ! ! ! ! ! ! !. ! ! ! ! ! ! ! !. ! ! ! ! ! ! ! ! ! ! ! !. ! ! ! ! ! ! ! ! ! ! ! !. ! ! ! ! ! ! ! ! ! ! ! !. ! K ! C ! :L ! :: ! ! ! ! ! ! ! !. ,9. :O :O :C .. .. .O .@ .@.

(5) !/. ! !" #$%&%'(%&&'&%)$* +*((' ,*,)-%' ! ! ! ! ! ! ! ! 012$%34 +% 5)$3-)(() +*(() 63'7* ! ! ! ! ! ! ! ! ! ! ! !/!9 :()55) +% 7*$*-'&%)$* +*7(% %$+%5% ! ! ! ! ! ! !/!" :()55) +% 7*$*-'&%)$* +*% <*7$'(% +% 5)$3-)((). !"#$%&'"()" * +$)'"()&#*),( -*)*.&%* /!9. /!" /!. 6%,2('&%)$% +*% =()55>% ! ! ! ! ! ! ! ! ! /!9!9 !""#$%& ! ! ! ! ! ! ! ! ! ! ! ! ! /!9!" ?$%34 +% 7*$*-'&%)$* +*7(% %$+%5% /!9! ?$%34 +% 5)$3-)(() +*(() <3'7* ! 6%,2('&%)$* 7*$*-'(* +*( '($# ! ! ! ! ! 6%$3*<% +*( +%<A)<%3%B) ! ! ! ! ! ! ! ! ! !. ! ! ! ! ! !. ! ! ! ! ! !. ! ! ! ! ! !. ! ! ! ! ! !. ! ! ! ! ! !. ! ! ! ! ! !. ! ! ! ! ! !. ! ! ! ! ! ! ! ! ! !. ! ! ! ! ! ! ! ! ! !. ! ! ! ! ! ! ! ! ! !. ! ! ! ! ! ! ! ! ! !. ! ! ! ! ! ! ! ! ! !. ! . ! 8 ! /; ! / ! ! ! ! ! !. /. /. /. /8 @9 @ @@. 0 1()2%$3"()". 0/. 4"5%"(-.&6&. 78. @!9 @!" @!. C=%*33%B% -'77%2$3% ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! @. D-)=(*,% *<%<3*$3% * A)<<%=%(% <)(2&%)$% ! ! ! ! ! ! ! ! ! ! ! ! ! ! @E ?(3*-%)-* <B%(2AA) ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! @8. ".

(6) !"#$%&% ' ()$*%+,-#%). ! ! !. "#$%&'()*%#* +&,-*'*#(&* "#$%&'()*+' ,,-. /012()3)'40 0 15' 5*)%)33'. !" #$ %&'(#"& ))* +# #",#-."! /". +&'#& ,# .$0!'#%(# !%%#(#11.%# 2&' #$ -.$-!3 $! ,&$$. !"#$%!&"'" () *%+!),! ,#+-'&%.4 56.-'!"#(! ))* +#0"#7-. #"8.%%# *"#' *%+!),! !"-#$%!& & 9/!$& #",#-.'& /" 2'!-&,#(&"%! #" 0'.,! ,# &+&0/#'& 9&$!-&(&"%& #$ -.$-!$! ,&$$. *'.+8!'(.%. ,# )!/'#&' ,#+-'&%.4 :/&3 +%& %#2!$!0#& ,# .$0!'#%(# '#+/$%."! &++&'& (!$%! /%#$# #" ,#9&'+& .22$#-.1#!"#; ,.$$6&$.<!'.1#!"& "/(&'#-. ,&# +&0".$# ,#0#%.$#= .$$. +!$/1#!"& ,# &>/.1#!"# ,#83 8&'&"1#.$# .$$& ,&'#9.%& 2.'1#.$#= .0$# .$0!'#%(# 2&' (!$%#2$#-.'& "/(&'# #"%&'# ,# 0'.",& ,#(&"+#!"&4 ?" 2.'%#-!$.' (!,!= "&$ -.(2! ,&$$6&$.<!'.1#!"& "/(&'#-. ,&# +&0".$#= 9#&"& 8.%%! $.'0! /+! ,&$$. ))*; "&0$# !+-#$$!+-!2# & "&# ,#+2!+#%#9# /%#$#11.%# 2&' $& %&$&-!(/"#-.1#!"#4 @&' >/."%! '#0/.',. >/&+%# /$%#(#= $6.$0!'#%(! ))* 9#&"& #(2#&0.%!= #" 2.'%#3 -!$.' (!,!= "&$$. (!,/$.1#!"& A)BC D !"#$%$&'( )!*+,*&-. /0%0"'( 1,("02 3(*40&% E4 *.$& %#2! ,# (!,/$.1#!"& 2&'(&%%& ,# %'.+(&%%&'& /" +&0".$& #" (!3 ,! 2.'.$$&$! +8'/%%.",! /". +&'#& ,# +!%%!2!'%."%# !'%!0!".$# &, &>/#+2.1#.%& %'. $!'! D)#0/'. F4F.E= #" (!,! %.$& ,. -!2'#'& $6#"%&'. <.",. ,#+2!"#<#$& 2&' $. %'.+(#++#!"&4 !(& G 2!++#<#$& 9&,&'& ,.$$! +-H&(. D)#0/'. F4F<E= $6.$0!3 '#%(! ))* +9!$0& $. +/. .1#!"& .",.",! . 7$%'.'& #$ +&0".$& 2'&-&,&"%&(&"%& (!,/$.%! .%%'.9&'+! /" >/.$+#.+# +#+%&(. ,# (!,/$.1#!"& ,#0#%.$&4 ?" >/&+%! %#2! ,# .22$#-.1#!"& +# /%#$#11. $. ))* -!(& .$0!'#%(! ,# -!"9!$/1#!"&= >/&+%! %#2! ,# .22'!--#! 2&'(&%%& ,# &9#%.'& ,# ,!9&' /%#$#11.'& ,&# 7$%'# .".$!0#-#4 I8'/%%."! >/&+%! %#2! ,# (!,/$.1#!"&; $. %&$&9#+#!"& ,#0#%.$& %&''&+%'& DBJKE= .$-/"& %#2!$!0#& ,# -&$$/$.'#= $& -!""&++#!"# L#)# L#C.M & NO2&'$."4 P.

(7)

(8) !"#$% &#''# ()*#+!,))# 2 &( 3, (*(-( 4567. (,)( *+% '# &(-#+ # .)(*/ ',0(!"#1. ,), 8.()&( 0#)#+%' 3.+3, #9 () 0+%&, 3#+!(: &( # #+#. !,);0.+%*( 3#+ &(-#+ ( *(3( &( %33'(!%<(,)(9 (),'*+# ),) = +%+, !"# !,)*#)0%> ), %' ',+, ()*#+), %'!.)#. *+.**.+# !,$3'# # !,$# $,'*(3'(!%*,+( , ?',!!"(. &( @7A1 2) $,'*( !% ( -#)0,), .*('(<<%*( () B% # &( 3+,0#**%<(,)# &( 7C2DE B+.**%)&, 8.# *, *(3, &( *#!),',0(% = ()B%**( 3, (?('# -#+(;!%+# # .) !#+*, *(3, &( *+.**.+% ',0(!% +( .'*% B.)<(,)%+# !,++#**%$#)*#F .)% -,'*% #G#**.%> *# *.**# '# -#+(;!"# %'',+% ( 3.: 3% %+# %''% 3+,&.<(,)# &#''% *# % . 7C2D1. 4(0.+% H1IE C*+.**.+% &( .)% 4567 J ( *,), -%+(%*( *(3( &( 4567 !"# &(G#+( !,), *+% ',+, 3#+ (' ).$#+, # (' *(3, &( +( ,+ # &( !.( &( 3,)0,),1 2' &( 3, (*(-, 3+,0#**%*, () 8.# *% *# ( = *%*, -('.33%*, !,) 'K,?(#**(-, &( # #+# ($3'#$#)*%*, . .) 4567 &#''% B%$(0'(%. !"#$%& '. &#''%. ()*)&+1 D,$# = 3,. (?('# -#&#+# &%''% *%?#''% L4(0.+%. H1MN B%)), 3%+*# &( *%'# B%$(0'(% &(-#+ ( $,&#''(1 2 3+()!(3%'( 3%+%$#*+( !"# '( &(-#+ (;!%), ,),E ).$#+, &( ?',!!"( ',0(!( LDOPN9 ?(* &( $#$,+(% C@7A L&( *+(?.(*% # % ?',!!"(N9 ).$#+, &( $,'*(3'(!%*,+(9 ).$#+, &( *#+$()%'( &( 2QR &( 3,)(?('(1 O% *+.**.+% ()*#+)% &( .) ?',!!, ',0(!,9 !,$# = *%*, &#**,9 = !, *(*.(*% &% .)% #+(# &( !,$3,)#)*( LA.'*(3'#S#+9 O%*!"9 4'(3 4',3N !"# 3, ,), # #+# ()*#+!,))#. ( *+% ',+,F )#' !% , &( .)% DOP &#''% B%$(0'(%. !"#$"& '9. ( 3.:. &(+# !"# !,)*(#)# %' ., ()*#+), 8.%**+, $%!+,?',!!"( ,0).), &#( 8.%'( 3+#)&# (' ),$# &(. *),% L4(0.+% H1TN1 O# 8.%**+, -*),%-. 3,. #+# B%!('$#)*# !,))# # *+% ',+, # !,) '#. ,), #. T. 3+# #)*( %''K()*#+), &( .)% DOP. -*),% &#''# DOP !,);)%)*(9.

(9) . #!$ %&#!$'

(10) (.

(11) !"#. *1 #

(12) . #!$. +-

(13) +-

(14)

(15) ) $, )) #+ ./0& *+$ *+$ +

(16) /0& . . .

(17). . . .

(18). . . . . . . . . . .

(19) . . . . . . . . .

(20) . .

(21).

(22) .

(23) . .

(24)

(25) . . . . . . .

(26) .

(27). . .

(28) . . . . . . . . . . . .

(29). .

(30) . . . .

(31). . . .

(32) .

(33) . . .

(34) . . . . . . . . .

(35). . .

(36). .

(37) . . . . . . .

(38)

(39) . .

(40) .

(41) .

(42) . .

(43) . . . . . !"#$% &'() *+,,%$!+ -.//. $!0+$0. -."/! 123 -.//% 4%,!"/!% *5%$6%7 ( !7+/6$.8 5.$ +"7#7% -.//. -#. 9+55!. -! !"#$ 8 : 5$.0.76. #7% /!7.% -.-!9%6% %//% 6$%0,!00!+7. -./ #%&&' ;$!5+$6+< !7 ,+-+ 6%/. -% 9+70.76!$.8 -+5+ %=.$ 9+7>"#$%6+ !/ -!05+0!6!=+ 9+,. 0+,,%6+$.8 #7% 6$%0,!00!+7. =./+9. -./ #%&&'' ?"7! !"#$ 5$.0.76% %/ 0#+ !76.$7+ #7% 06$#66#$% 9+,5/.00% ; !"#$% &'@<) -#. /++A#5 6%B/. ;CDE< % F#%66$+ !7"$.00! ;,#/6!5/.G.$ ! 9#! !7"$.00! 0+7+ 9+//."%6! % 0!7"+/! B!6 -! ,.,+$!%<8 -#. ./.,.76! -! ,.,+$!% 9+7>"#$%B!/! 9+,. /!5 /+5 + C%69H8 I#/6!5/!.G.$8 /% /!7.% 5.$ !/ 6$%05+$6+ -./ 9%$$J . -.//% /+"!9% -.-!9%6% ;K?L< % 4#7M!+7! %$!6,.6!9H.' L!0#/6% .=!-.76. 9H.8 5+6.7-+ %"!$. 0#//. -!=.$0. !76.$9+77.00!+7! 6$% /. !"#$ : 5+00!B!/. ".7.$%$. /. 5!N 0=%$!%6. 6!5+/+"!. -! 9!$9#!6! -!"!6%/!'. !" #$%&'(' )%*+)%*',%! -%&&% -./ %&&% ../ !"! #$% &'( )'*+,-. &'(./0.1. 1.$ 5+6.$ -.09$!=.$. /. +5.$%M!+7! 0=+/6. -%/ -!05+0!6!=+ !7 .0%,. : 7.9.00%$!+ 9%5!$. F#%/ : /O+5.$%M!+7. ,%6.,%6!9% 9H. 06% %//% B%0. -./ 0#+ 4#7M!+7%,.7P 6+' Q#.06+ 9%5!6+/+ -! !76$+-#M!+7.8 7+7 =#+/. .00.$. #7% -.09$!M!+7. %55$+4+7P -!6% -.//O%$"+,.76+ ;% 6%/. 5$+5+0!6+ 0! $!,%7-% !/ /.66+$. %//% B!B/!+"$%>% RST< ,%8 0.,5/!9.,.76.8 H% !/ 9+,5!6+ -! $!9H!%,%$. %/9#7! 9+79.66! 9H!%=. -.//% E.+$!% -.! *."7%/! #6!/! 5.$ /% 9+,5$.70!+7. -./ /%=+$+ 0=+/6+'. S.

(44) . !"#$% &'() *+,-.% /-.01!2+%34 5-11% /3$#33#$% 5! #6% /1!+7.

(45) !"#$% &'() *+$#++#$% !,+-$,% .! #,% /01 .-22% 3%4!"2!% !"#$"%& /54- 6 ,5+57 8-$ ! 9-",%2! :5,+!,#! 6 8599!;!2- 5++-,-$- 2% <$%935$4%+% .! 5#$!-$ =<> ? %++$%@-$95 2A-98$-99!5,-) X(f ) =. Z. ∞. x(t)e−j2πf t dt −∞. B-$ ! 9-",%2! :5,+!,#! - 8-$!5.!:!7 +%2- -98$-99!5,- 9! $!.#:- %. #,% 9544%C +5$!% .! !48#29! +$%92%+! 9# .-+-$4!,%+- 3$-D#-,E- - 9:%2%+! 5885$+#,%4-,+:5, ! @%25$! .-22% *-$!- .! 5#$!-$) X(f ) =. +∞ X. F Xn δ(f − nF ). n=−∞. F =. 1 Tp. =&'&?. >5@- !2 δ 9! 5++!-,- .%2 3%++5 :F- 2% <> .! e−j2πnF t 6 %88#,+5 δ(f − nF ) - Xn 6 2A!,+-"$%2- 9#2 8-$!5.5 .-2 9-",%2- = Tp ? .! x(t)e−j2πnF T 5@@-$5 !2 :5-3C G:!-,+- .-22% *-$!- .! 5#$!-$' 0A58-$%E!5,- :F- !2 .!9859!+!@5 9@52"- =:!56 2% <? 6 -H-++#%+% 9# #, ,#4-$5 .! :%48!5,! %:D#!9!+! !, #, +-485 G,!+5 D#!,.! $!9#2+% -@!.-,+- :F8-$ :548$-,.-$,- !2 3#,E!5,%4-,+5 :! 9! .-@- :5,:-,+$%$- 9#22% =&'&?' I2 $!9#2+%+5 :F- 9! 5++!-,- .%22% =&'&? 6 .! +!85 :5,+!,#5 - D#!,.! ,5, 8#J -99-$"-,-$%+5 .% #, .!9859!+!@5 .!"!+%2-7 :F- 8#J 58-$%$- 952%4-,+- 9# 9-",%2! .!C K.

(46) !"#$%& '$$"()#" * *++*"$,-% (..%, $(/#-$% 0 +* %1%2# *$$#-#"# 23# +"# %*-# %- ."(4* 4% 5*"-%"# 6,#22( !7# )%#-# 4#8-%$( 9"( 5*"/($( :% !"#$( 4% ;*,"%#" <:;9=>. X(kF ) =. n0X +N −1. T · x(nT )e−j2πkF nt. <?&@=. n=n0. A,# $* $%+* 4% 9"( 5*"/($( 0 4% %/+*"$(-B( 5*-4(/#-$(2# +*%!7C 0 23,D -%!( !7# +,E # B%*-# !7#. #"# !(2!*2($( +#" )%( -,/#"%!( # 6,%-4% !* $%$,% !# 23*+#"(D. $( (22( 1( # 4#2 5,-B%*-(/#-$* 4#2 4% +* %$%)* %/+2#/#-$($*& F2. "% ,2$($* !7#. % *$$%#-# 4(22( <?&@= 0G 4($* ,-. Tp = N T G ,-( $"( 5*"/($( 4* Fc = 1/T = N F &. #.-(2# 4% !"#$* !*- +#"%*4*. +#"%*4%!( ( 5"#6,#-B( 4% !"#$(. X(kF ). !*- +#"%*D. :% $,$$% % +("(/#$"% !7# %-$#"!*""*-* -#2 4#$#"/%-("# 2( :;9G (2 8-# 4% *$$#D -#"# ,- "% ,2$($* !*""#$$*G 0 -#!# ("%* +*""# +("$%!*2("# ($$#-B%*-# ( HG $(2# )(2*"# 4#$#"/%-( %2 -,/#"* 4% !(/+%*-% ,$%2%BB($% +#" %2 !(2!*2*&. !"!" #$% &'( )'*+,-. , /0(,1, 2+.1,3 ('-,4.5+' 1(, %(,6 )75(8,1, /. $50(.'( ' #$% I*/# % #)%-!# 4(2 +("(."(5* +"#!#4#-$#G 2( <?&@= 0 2( $"( +* %B%*-# -#2 4*/%D -%* 4% !"#$* 4#22( <?&?= ,$%2%BB($( +#" %2 !(2!*2* 4#22( 9:; 4% #.-(2% +#"%*4%!%& H#2 !( * %- !,% 2( /#4# %/( # +"# %*-# )#-%. # ,$%2%BB($( +#" !(2!*2("# 2(. 9:; 4% ,- 6,(2,-6,# #.-(2#G -*- -#!# ("%(/#-$# +#"%*4%!* * , ,- -,/#D "* 4% !(/+%*-% !7# -*- !*+"# ,- -,/#"* 8-%$* 4% +#"%*4%G 0 #)%4#-$# !7# %2 "% ,2$($* $"*)($* % +*$"#11# !*- %4#"("# !*""#$$* *2(/#-$# # % (!!#$$( # ,- !#"$* #""*"# %-$"*4*$$* 4(22( -*- +#"%*4%!%$J 4#2 #.-(2# KLMGK?MGKNM& :($* !7# 2( $"( 5*"/($( %-)#" ( 4#22( <?&@= !*/# "% ,2$($* "# $%$,% !# ,- #.-(D 2# +#"%*4%!*G -#2 !( * %- !,% %2 #.-(2# (!6,% %$* -*- %( +#"%*4%!*G % +"#5#"% !# /*4#22("2* ($$"()#" * ,-( 8-# $"( 4% !(/+%*-(/#-$* <;%.,"( ?&N= $(2# 4( 5(". ;%.,"( ?&N> O$%2%BB* 4#22( 8-# $"( 4% !(/+%*-(/#-$*. P.

(47) !"#$%$! & '%"(&)*& %'+,& &-& ,* (!$&).) .!/ !0*%/! -! )1 2,! -) -&() .& %(($)''&) 3 &* 0$%.) .& $&.,$$! 0/& !$$)$& /!0%-& %//% *)* &.!%/&-4 .!/ !0*%/! *!& ')*5$)*-& .!//6! ($! &)*! ')* ',& 7&!*! '%/')/%-% /% ,% 89:1. ;<.

(48) !"#$%&% ' ($)*$$*)! !" #$%& #'()*+) ,)$-%.')/ 0##,1 !" #$ %&'(#"& ))* +# ,- '#,&'#(&"%! -. /"- +&'#& .# -$0!'#%(# 1&$!2# .# 2-$3 2!$! .&$$- 4)* #" 0'-.! .# '#./''& #$ "/(&'! .# !5&'-6#!"# -++!2#-%& -. /"%'-+,!'(-%- .# N = 2b 2-(5#!"#7 .- /" %&(5! .# 2-$2!$! 5'!5!'6#!"-$& - N 2 -. /"! 5'!5!'6#!"-$& - N · log2 N 8 9- 2-'-%%&'#+%#2- 5'#"2#5-$& .# :/&+%# -$0!'#%(# ; 2<& 5!++!"! &++&'& !%%&"/%# 2!(& /"=-55$#2-6#!"& .&$ 5'#"2#5#! !"#"$% %& '()%*+, 7 !11&'! /" 5'!>$&(5'#"2#5-$& 1#&"& +2!(5!+%! #" 5#? +!%%! 5'!>$&(# .# (#"!' .#(&"+#!"& @ !"#"$%, AB /"- 1!$%- '#+!$%# :/&+%# 5'!>$&(# C+&(5$#2#D7 # '#+/$%-%# 5-'6#-$# !%%&"/%# 1&"0!"! '#2!(>#"-%# @ '()%*+, A #" (!.! .- !%%&"&'& $- +!$/6#!"& .&$ 5'!>$&3 (- !'#0#"-'#!8 E$$=!5&'-6#!"& .# .#1#+#!"& ; 2<#-'-(&"%& -++!2#-%! /" 2&'%! 0/-.-0"! #" %&'3 (#"# .# 2!(5$&++#%F .# 2-$2!$! #$ :/-$& .&1& &++&'& 2!",'!"%-%! 2!" #$ 2!+%! $&0-%! -$$- '#2!(>#"-6#!"& &G! -$$- 2!+%'/6#!"& .# +!%%!5'!>$&(#8 H "&2&++-'#! 5!''& 5-'%#2!$-'& -%%&"6#!"& -$ ,-%%! 2<& -. !0"# +2&$%- .&$$5-'%#6#!"& .&$$=#"+#&(& .&# .-%# .# 5-'%&"6- #" +!%%!#"+#&(#7 2!''#+5!".& /" -$0!'#%(! .#1&'+!7 2!" 2!+%# .# 5-'%#6#!"&3'#2!(>#"-6#!"& .#1&'+#8. II.

(49) !"!" #$%&'())*+, -* ./'.$'$ -(''/ 012. !"#$%%"!&' #()*+,)**$'!) &)##" -./ △. 2π. WNkn = e−j N X(k) =. N −1 X. x(n) · WNkn. dove. k = 0, 1, . . . , N − 1. 01234. n=0. x(n) ∈ C. 5 6"7$#) !'8",) 79) +), :!' ;:"#*$"*$ &)$ k <"#',$ &" 7"#7'#",)= *'!' !)7)*> *",$) N ?'#8$+#$7"%$'!$ ) N − 1 ≃ N *'??)= )!8,"?@) 7'?+#)**)2 /)!)!&' $! 7'!*$&),"%$'!) $# 6"88' 79) :! !:?),' 7'?+#)**' 5 &" 7'!*$&),",) 7'?) :!" 7'++$" &$ !:?),$ ,)"#$= $! 8),?$!$ &$ '+),"%$'!$ 0,)"#$4= *$ '88$)!)A 01214 " 7:$ <"!!' "BB$:!8$ "!79) B#$ "77)**$ $! ?)?',$" +), #" #)88:,"C*7,$88:," &)$ &"8$ 79) *'!'= ,$*+)88$<"?)!8)= N '+),"%$'!$ &$ #)88:," ) 1 &$ *7,$88:," +),7$D N∗C + N+C = 4 · N∗R + 2 · N+R + 2 · N+R = 4(N∗R + N+R ). '+),"%$'!$ &$ ,CE 012F4 7(5 $!'#8,) &" "BB$:!B),) $# 8)?+' &$ 7"#7'#' &)$ 6"88',$ WNkn ' $! 'B!$ 7"*' &$ "77)**' "##" GHI 79) #$ 7'!8$)!)2 J'!7#:&)!&'= $# !:?),' &$ '+),"%$'!$ &" *<'#B),) ,$*:#8" 7'?+'*8' &"A  N ?'#8$+#$7"%$'!$    N *'??) N '+),"%$'!$ &$ ,CE    N 6"88',$ WNkn ' "77)**$ "& :!" GHI +), :!" 7'?+#)**$8K 8'8"#) &$A N −1≃N. C = K∗C N 2 + K+C N 2 + Ka N 2 + Kw N 2 + 07"#7'#'. &)B#$ $!&$7$4 M# 7"#7'#' &$ N 7')O7$)!8$ ,$*:#8" ;:$!&$ +,'+',%$'!"#) " N 2 T (N ) = K · N 2. 31. 012L4 012P4.

(50) !"!. #$%&'())*+, -* ./'.$'$ -(''/ 001. !"# $ %&'&! ()#*#+#,&#"#,&# %*)-&&!. #%-%&!,! +-/#)%- '01!)-&"- (#) -0 *'02 *!0! +#00' 345 *6# 7&-0-88',! -0 "#&!+! !"#"$% %& '()%*+, . &'0- '01!)-&"+-9#)-%*!,! &)' 0!)! %!0'"#,&# (#) -0 &-(! +- (')&-8-!,# *6# %- :' +#00;-,%-#"# !)-1-,')-! +#- *'"(-!,-< =' *!"(0#%%-&> &#"(!)'0# $ (#)? 0#1'&' '0 &-(! +(')&-8-!,'"#,&! # +-9#)-%*# ' %#*!,+' +#00' +-"#,%-!,# "-,-"' +#10- -,%-#"+#- *'"(-!,-< @#))> &)'&&'&! %!0'"#,&# -0 *'%! -, *7- 0' +-"#,%-!,# "-,-"' +#10- -,%-#"- %-' 2. A7#%&! /'0!)# +#)-/' +'0 :'&&! *6#. 7&-0-88',+! +-%(!%-&-/- +-1-&'0-. )-%70&' %#"(0-*# 0'/!)')# *!, (!&#,8# # "70&-(0- +- 2. -,!0&)# &'0# %*#0&' )-%70&' #%%#)# 0' (-B #C*-#,&# -, &#)"-,- +- *!"(0#%%-&> &#"(!)'0#. %# %- !(#)' *!, 7, ,72 "#)! +- *'"(-!,- (')- N = 2b. *!"# ,#0 *'%! +#0 +-%(!%-&-/! -"(0#"#,&'&!< D, E'%# '0 ()-,*-(-! !"#"$% %& '()%*+, $ ,#*#%%')-! %*!"(!))# 0;-,%-#"# *!2 %&-&7-&! +'10- N *'"(-!,- -, -,%-#"- (-B (-**!0-. A7-,+-. %'(#,+! *6# N $ 7,' (!&#,8' 2. $ (!%%-E-0# +-/-+#)# N -, +7# -,%-#"- !1,7,! +#- A7'0- 6' +-"#,%-!,# N/2< N→. N N + 2 2. FG<HI. J# -0 &#"(! +- *'0*!0! '%%!*-'&! '0 ()!E0#"' *!, *')+-,'0-&> N $ (')- ' T (N ) ≃ N 2 '00!)'. +!(! -0 (')&-8-!,'"#,&!. '+ !1,7,! +#- +7# %!&&!-,%-#"*!, *')+-,'0-&> N/2 $ '%%!*-'&! 7, &#"(! +- *'0*!0! (')- ' T (N/2) = (N/2)2. A7-,+- )-*!"E-,',+! 0# %!078-!,- %- !&&-#,# -0 %#17#,&# &#"(! +- *'0*!0!K T (N ) = 2 · T. . N 2. . + R(N ). FG<LI. +!/# R(N ) $ -0 &#"(! ,#*#%%')-! '00' )-*!"E-,'8-!,# +#- )-%70&'&- !&&#,7&-< M-%70&' #/-+#,&# *6# %# R(N ) = O(N ). # %- )#-&#)' 0! %&#%%! ()!*#+-"#,&! N,! ' )'11-7,1#)# -,%-#"- +- +-"#,%-!,# "-,-"'. -0 &#"(! ,#*#%%')-! '0 *'0*!0! )-%70&'K T (N ) = O(N · log2 (N )). PQ. FG<OI.

(51) !"!# $%&'()&*+,&-) .,//* $$0 (+1/,+,&-*-*!. !"#$%&'% ( )*+%'(,%#-* -*! &*'.#. !"#$%&'("%! $) #!)$*! $"#$&+& %$ N ,(+-$!"$. ,!+& -'&,&%&"*&+&"*& $))/0 #*'(*!. )! #$ #/%%$1$%& $" %/& #!**!$"#$&+$ ,!" )( #*&##( ,('%$"()$*23 4" 5/&#*! ,(#!. -&' &6&**/('& )( #/%%&**( #/%%$1$#$!"&. #$ '(77'/--("! 8'( )!'! */**$ $ ,(+-$!"$ ,!" $"%$,& -('$ & */**$ 5/&))$ ,!" $"%$,& %$#-('$. $" +!%! *()& ,9& '$#/)*$: n=. . 2·r 2·r+1. ;**'(1&'#! (),/"$ -(##(77$ +(*&+(*$,$. < 8(,$)& 1&'$=,('& $"!)*'& ,9& WN2 = WN/2 5/$"%$ %())>&#-'&##$!"& %&))( ?@A #$ '$,(1(: X(k) =. N −1 X. 2π. x(n)WNnk. (WN = e−j N ). n=0. N/2−1. =. X. N/2−1. x(2r)WN2rk. +. r=0. X. =. |r=0. BC3DE. r=0. N/2−1. N/2−1. X. (2r+1)k. x(2r + 1)WN. x(2r)W N2rk +WNk 2. {z. G(k). X. |r=0. }. = G(k) + WNk H(k). x(2r + 1)W N2rk 2. {z. H(k). }. k = 0, 1, . . . , N − 1. %( ,/$ '$#/)*( &1$%&"*& ,9& $) ,(),!)! %&))( ?@A #/ N ,(+-$!"$. < #*(*! #,!+-!#*! "&) ,(),!)! %$ %/& ?@A &"*'(+F& #/ N/2 ,(+-$!"$3 A&"&"%! ,!"0 *! $"!)*'& ,9& )( ?@A < -&'$!%$,(. G(k) & H(k) #!"! (",9>&##& -&'$!%$,9& %$ -&'$!%! N/2. 5/$"%$ G(k) = G(k + N/2) & H(k) = H(k + N/2)3 G&$*&'("%! )>!-&'(H$!"& %$ #/%%$1$#$!"& $" #!**!$"#$&+$ 1$( 1$( -$I -$,,!0 )$. (% /" ,&'*! -/"*! B%$-&"%&"*& %() "/+&'! %$ ,(+-$!"$ %( &)(F!'('&E )>$"#$&+& +$"$+! #/ ,/$ )>()7!'$*+! !-&'( < %$ %/& #!)$ &)&+&"*$3 4) ,!+0 -$*! %&))>()7!'$*+! < $"8(**$ 5/&))! %$ ,(),!)('& X(k) = G(k) + WNk H(k) & X(k + N/2) = G(k) + WNk H(k). ( -('*$'& %( (),/"& ,!--$& %$ ,(+-$!"$ #,&)*& ,!''&**(+&"*& & %$ '&$*&'('& *()& !-&'(H$!"& -&' /" "/+&'! %$ 1!)*& -('$ () log2 N 3 ?( 5/&#*& &#-'&##$!"$ %&'$1( )( #*'/**/'( F(#& %&))>()7!'$*+! ,9& -'&"%& $) "!+& %$ !""#$%& & ,9& ,!#*$*/$#,& $"!)*'& -('*& $"*&7'("*& %&) %$#-!#$*$1! $+-)&+&"*(*!: JK.

(52) !"# #"#$#%&' ( ")*%+&, -'%.!$#%&!"# .+ /!"/'"' .#"")+%&#0' !"1'0+&$'2 3#0 /!"/'"!0#4 5#0 #6#$5+'4 "! 77 .+ *% 6#1%!"# .+ /*+ 6'%' 6&!&+ !/8*+6+9 &+ 8 /!$5+'%+4 ( %#/#66!0+' 6:+"*55!0# +" /!"/'"' 50#/#.#%&# 5#0 '1%*%' .#+ k = 0, 1, . . . , 7 /!$5+'%+; +" 0+6*"&!&' '&&#%*&'4 /'$# 6+ 5*< :#.#0# .!""! =7+9 1*0! >2?@4 ( "! 0+5#&+A+'%#4 6#/'%.' *% .#&#0$+%!&' 6/B#$! /B# .#0+:! .!""' 6:+"*55' $!&#$!&+/' .#"")!"1'0+&$'4 .#""! 6&0*&&*0! C*&&#0DE2 F+6*"&! #:+.#%&# /B# +" /!"/'"' .#" 0+6*"&!&'4 5*< #66#0# #G#&&*!&' +% $'.' !"#"$$%$&' 4 8*+%.+ ( 5'66+C+"# /!"/'"!0# 6+$*"&!%#!$#%&# 5+H .+ *% 0+6*"&!&' # 5#0/+< 0+65!0$+!0# &#$5'2 I#J%#%.' '1%*%' .#+ 10*55+ :#0&+/!"+ .+ C*&&#0DE *%' 6&!.+'4 +" %*$#0' .+ 6&!.+ .! #6#1*+0# ( 5!0+ ! log2 N 4 +% 8*#6&' /!6' 8*+%.+ 5!0+ ! 32 K! 5'6&! +%'"&0# *%! 5!0&+/'"!0# !&&#%A+'%# !. !"&0+ -!&&'0+ /B# /'%/'00'%' %#" .#&#0$+%!0# +" 0+6*"&!&'L 5#0 '&&#%#0#4 !" &#0$+%# .#"")#6#/*A+'%# .#"")+%&#0' !"9 1'0+&$'4 .#+ 0+6*"&!&+ '0.+%!&+ /'00#&&!$#%&# =/+'( .! X(0) ! X(7)@4 ( %#/#69 6!0+' /B# + /!$5+'%+ 5'6&+ !"")+%10#66' .#" C"'//' .+ /!"/'"' 6+!%' 5'6+A+'%!&+ 6#/'%.' *% '0.+%# .+:#06' .! 8*#""' %!&*0!"# =/+'( &#$5'0!"#@4 8*#6&' &+5' .+ '0.+%!$#%&' 50#%.# +" %'$# .+ &#()*"+%*,& " -), #&.%/0)",)2 M)&#()*"+%*,& " -), #&.%/0)",) 50#:#.# /B# "# 5'6+A+'%+ .#+ /!$5+'%+ !"")+%&#0%' .#" :#&&'0# /B# "+ /'%&+#%#4 :#%1!%' 6/!$C+!&# 50+$! .+ 6:'"1#0# ")!"1'0+&$'4 "# 5'6+A+'%+ +% /*+ '1%+ /!$5+'%# :! 5'6&' 6'%' .#&#0$+%!&# +%:#0&#%.' + C+& /B# /'$5'%9 1'%' "! 5!0'"! /B# +.#%&+J/! ")+%.+/# .#""! 5'6+A+'%# .+ '1%+ 6+%1'"' /!$5+'%#4 +% 8*#6&' /!6' 6+ '&&+#%#L 000 → 000 001 → 100 010 → 010 011 → 110 100 → 001 101 → 101 110 → 011 111 → 111. .! /*+. ?N. x(0) → x(0) x(1) → x(4) x(2) → x(2) x(3) → x(6) x(4) → x(1) x(5) → x(5) x(6) → x(3) x(7) → x(7).

(53) !"#$% &'() *+!,#--. /0,,1 2 341#,5!6% %55047!.40 +% -.85% %! 9.0:9!045! WNk ; !4 -%$5!9.,%$ 6./. %,< ,108-.40450 k 9=0 /050$6!4% !, +%,.$0 /0, 9.0:9!0450 85088.; /%5. 9=0 !, -%$%< 605$. N > ?88%5. % -$!.$! 0/ > -%$! %, 4#60$. /! 9%6-!.4!' @6-,06045%4/. ,1%,".$!56. $!8#,5% !4A%55! 409088%$!. 9%-!$0 9.60 0+.,+0 !, 50$< 6!40 k /#$%450 !, 9%,9.,.' *+!,#--%4/. ,108-$088!.40 B&'CD -0$ ."4! 9%6-!.40 8! .55!040 9.60 $!8#,5%5. 9=0; -0$ 5#55. !, -$!6. 85%/!.; k > 806-$0 -%$! % 0; /#$%450 !, 809.4/. 85%/!. !4+090 %9E#!85% +%,.$! -%$! % 0 0 2b−2 ; 6045$0 /#$%450 !, 50$7. 85%/!. > 0, 1, 2, 3 9=0 8.4. 5#55! +%,.$! /!85%47!%5! 5$% ,.$. /! 2b−3 ; !4 E#085. 9%8.B-0$ N = 8D -%$! % 1' @4 "040$%,0 E#!4/!; -$08! N = 2b 9%6-!.4!; -0$ ."4#4. /0",! i 85%/! Bi = 1, . . . , (log2 N ) − 1); ,% /!85%47% 5$% ! +%$! k > -%$! % 2b−1−i ' (F.

(54) !"#" $"#"%" &'#$' &(" k < N/2) &*+ ,* $%-./&" #"0 1-$$' &(" 2"% 0- %"-3 0*44-4*'#" ."0 .*,2',*$*5' ,'#' ,$-$" 2%"5*,$" ,$%/$$/%" *# 6%-.' .* &'#$"#"%" ,'0-7"#$" $/$$* * &'"8&*"#$* WNk &'# k ≤ (N/2)−19 :# '6#* &-,') -#&(" ," $-0* 5-0'%* 1',,"%' ,$-$* &-0&'0-$*) ,-%"!!" %*,/0$-$' ,/8&*"#$" 0*7*$-%,* - &-0&'0-%" ;/"00* 2"% &/* k ≤ (N/2) − 19. !. "#$%##%$& '()*+(+,#&#'-& .' /&0+!. !"# $%&'(%()*+*,-) -. + /(01-)2345+6'( 7. :#.*5*./-$* * 2-%-7"$%* .* !-," &(" &'#&'%%'#' -00' ,5'06*7"#$' ."00<-06'3 %*$7') 5*"#" .",&%*$$- '%- 0- ,$%/$$/%- .* !-," &'# &/* = ,$-$' %"-0*44-$' *0 .*,2',*$*5'9 >'5"#.' *#1-$$* /$*0*44-%" ,$%/$$/%" %*&'#?6/%-!*0* ;/-0* @ABC) &* ,* 2/+ %"#."%" 1-&*07"#$" &'#$' &(" ",*,$'#' ,5-%*-$" &'#?6/%-4*'#* *# 6%-3 .' .* ,5'06"%" *0 7".",*7' &'72*$') ,*- 5'0"#.' 2%".*0*6"%" 0- %-2*.*$D .* ","&/4*'#" ."00<-06'%*$7' ' 0- 7*#*7*44-4*'#" ."00<-%"- '&&/2-$- #"0 .*,2',*3 $*5' ,$",,' '22/%" -0$%* $*2* .* 6%-#."44"9 E"00- ,&"0$- ."00- ,$%/$$/%- = ,$-$' ;/*#.* 2%",' *# &'#,*."%-4*'#" 0<-%$*&'0' .* B('/F-G"0 " H'/I$ JKL9 :# $-0" 0-5'%' 5*"#" 7',$%-$- 0- 2',,*!*0" ,$%/$$/3 %- &',$*$/$*5- .* /# .*,2',*$*5' *# 6%-.' .* ,5'06"%" 0- @@M ,*- #"0 .'7*#*' N'720",,'O;/*#.* *#?#*$'P ,*- ,/ .'7*#* ?#*$* .* B-0'*,9 H<'!*"$$*5' .* ;/"3 ,$' $*2' .* %"-0*44-4*'#" = ;/"00' .* ."?#*%" /#' ,&("7- .* !-," &(" 2/+ 2'* ",,"%" ,5*0/22-$' ,*- #"0 &-,' *# &/* ,* 2%".*0*6- 0- 5"0'&*$D .* ","&/4*'#" " ;/*#.* 2"#-0*44-#.' 0<-%"- '&&/2-$-) ,*- ," ,* 2%"1"%*,&" *#5"&" '&&/2-%" 0<-%"7*#'%" " '55*-7"#$" *72*"6-%" 2*Q $"72' 2"% *0 &-0&'0'9. RS.

(55) !"##$%"&' (")*(+$+$, #*-+($ .$ -+(/++/($ .$ 0/$.' )('1'2' 34' ". 3$.3*.* -"$ -/22"1"-* "& log2 N !"#$ *%&/&* 2'" 0/$." 3*#)*-+* 2$ /&$ -'("' 2" '.'5 #'&+"6 78 .$ !""#$%& 6 )$(+' 9*&2$#'&+$.' 2" +/++* .* -+$%', 3*#' : -+$+* 1"-+* "& )('3'2'&;$, 3*-+"+/"-3' .!/&"+< $("+#'+"3$ 2'. 2"-)*-"+"1* -+'--*8 =$+* 34' .$ >>? *)'($ -/ -'%&$." 3*#).'--" $33'++$ $. -/* "&%('--* +(' 3*)5 )"' 2" -'%&$." ('$." ' 2*)* $1'(.' *))*(+/&$#'&+' '.$@*($+', ('-+"+/"-3' $..!/-3"+$ 2/' 3*))"' 2" -'%&$." ('$."8 A8 /&$ !"6 4$ ". 3*#)"+* 2" 3*&+'&'(' " 2$+" 34' 1'&%*&* '.$@*($+" 2$ *%&" -+$%', .$ -/$ 3$)"'&;$ : 0/"&2" +$.' 2$ #'#*(";;$(' +/++" " 3$#5 )"*&" $30/"-"+"8 B8 /&$. #"6 3*&+"'&' " 3*'C3"'&+" W. k N. &'3'--$(" $. 3$.3*.*8. D8 .!$%&'( )& *+%',+--+6 %'-+"-3' .* -1*.%"#'&+* 2'..' *)'($;"*&", " 2$+" 3*&+'&/+" &'..$ EFG 1'&%*&* "&9$++" .'++" 2$..' %"/-+' )*-";"*&" 2'..$ 7H.

(56) ! "#$%& '%((" )"$ %**+$(,#!--" .!**% !""#$%& ! $(/(!& .")" !--!#! -0%0$ !*%1"#%0$& '!(,"(" (2"'% !(0! ! "#$33%0$ (!**% 4567 8("*0#! .2#%(0! *+!*%1"#%3$"(! .!$ .%0$ .% )%#0! .!**% !""#$%&& $* 9"!:9$!(0! WNk )"-0" %* -2" $(,#!--" '$!(! )#!*!'%0" .%**% 4;6& 9$< -$ 0#%.29! (!* =%00" 9>! *+2($0? .$ 9"(0#"**" 9%*9"*% $* ,$2-0" $(.$#$33" .$ ! "#$% 9>! 9"(0$!(! $* 9"!:9$!(0! 9"##!00" )!# *+!*%1"#%3$"(! 9>! -$ -0% !@!002%(."7 A200% *+2($0? B % -2% '"*0% 9"(0#"**%0% .% 2(+ !"#$ %" &'!#('))' *)'+ ,-). *% C2%*! -$ "992)% .$ %.%00%#! "))"#02(% !(0! $ .%0$ %**+$(,#!--" .!* .$-)"-$0$'"& .$ $(-!#$#*$ (!**% 456 ! .$ %''$%#! *+!-!923$"(! .$ ",($ -0%,!7 D(% '"*0% !-!,2$0$ 0200$ ,*$ -0%,! *!,,! -!C2!(3$%* !(0! $* #$-2*0%0" 9"(0!(20" (!**% 456 ! *" #!-0$02$-9! 9" ! 2-9$0% .!* .$-)"-$0$'"7 E+$(0!#" .$-)"-$0$'" B )%#% !0#$33%0" -$% )!# C2%(0" #$,2%#.% *% C2%(0$0? .$ 9% )$"($ .% !*%1"#%#! -$% )!# *% #$-"*23$"(! .!$ 9% )$"($ -0!--$ C2$(.$ )!# $* (2 !#" .$ 1$0 9>! 9" )"(,"(" 2( 9% )$"(!7 !" #$%&$$&%' ()*+,),-$'$' F")" %'!# $(.$'$.2%0" *% -0#2002#% .$ 1%-! B (!9!--%#$" .!/($#! %*92(! .!**! -)!9$/9>! -!,2$0! (!**% )#",!00%3$"(! .!* .$-)"-$0$'"7 8((%(3$0200" *+",,!00" 9>! '$!(! )#!-!(0%0" $( C2!-0% 0!-$ 9"-0$02$-9! -"*%G !(0! $* '($# .!* .$-)"-$0$'" $( ,#%." .$ !-!,2$#! *+$(0!#" %*,"#$0 "& %(G 9% $(=%00$ .$ C2!**% )%#0! 9>! (!* )%#%,#%=" )#!9!.!(0! B -0%0% 9>$% %0% 2($0? .$ 9"(0#"**" ,*"1%*!7 H!**+$ )*! !(0%3$"(! -$ B -9!*0" .$ )#!.$*$,!#! 2(% -0#2002#% 9>! ="--! $( ,#%G ." .$ "992)%#! *% $("# C2%(0$0? .$ %#!%I. JK.

(57) !"# $% &#'# '())! $*+#"(, )-%./#0! '%$1!$%/%&! 2 *!$/%/3%/! '( 3. 3.%*! $/(4# *+# &%#.# %/#0(/!, 1#0 !4.3.! '#% log2 N $/('%, N/2 &!)/#5 6()# $/03//37 0( 0%$3)/( (&#0# 3.-!**31(8%!.# "%.%"(, 130 "(./#.#.'! ()/# )# 10#$/(8%!.% '#))-()4!0%/"! $/#$$!5 9%:#0#./#"#./# '())! $*+#"( "!$/0(/! .#))-(0/%*!)!, %) '%$1!$%/%&! 2 $/(/! %"1)#"#./(/! 1#0 1!/#0 #$#43%0# $!)("#./# )( ;;6 *)($7 $%*(, <3%.'% .#) '!"%.%! *!"1)#$$! =%.>.%/!?5 @( ABC 2 $/(/( '%&%$( %. '3# D(.*+% '%:#0#./%, %.E(//% %) /#0"%.# WNk ()/0! .!. 2 *+# 3. #$1!.#.8%()# *!"7 1)#$$! # <3%.'% )( *!11%( '% '3# &()!0% '% $#.! # *!$#.!5 @-%./#0! '%$1!$%/%&! 2 $/(/! $&%)311(/! 1#0 1!/#0 #$$#0# %"1)#"#./(/! $3))( D!(0' !"#$"% & '#))( '()(%*5 9!&#.'! 3/%)%88(0# 3. ;FGH $1#*%>*!, )# *(0(//#0%$/%*+# '% 0%*!.>430(D%)%/I $!.! $/(/# "(./#.3/# .#))( "(44%!0 1(0/# '#) '%$1!$%/%&!, *!. 3.-3.%*( #*7 *#8%!.# E(//( 1#0 <3#))# $/03//30# *+#, #$$#.'! %./#40(/# .#))( D!(0' $/#$$(, $!.! $/(/# 3/%)%88(/# '%0#//("#./#5 JE03//(.'! <3#$/% "!'3)% #"D#''#' 1#0K $!.! $/(/# D)!**(/# '% E(//! ()*3.# 40(.'#88#L • M3(./%/I '% *("1%!.%L 2 $/(/( 1!$/( ( N = 210 = 1024 •. M3(./%/I '% D%/ 1#0 *("1%!.#L (&#.'! ( '%$1!$%8%!.# "!)/%1)%*(/!0% #"7 D#''#' ( 18 D%/ $% 2 $*#)/! '% !1#0(0# *!. *("1%!.% *!$/%/3%/% '( 18 D%/ 1#0 )( 1(0/# 0#()# # 18 1#0 <3#))( *!"1)#$$(5. !"!# $%&'()*. A%$3)/( #&%'#./# *+# %) '%$1!$%/%&! %"1)#"#./(/! *!$/%/3%$*# 3.-3.%/I ('%D%/( () *()*!)! .3"#0%*!, %. <3(./! /()# 2 $/(/! .#*#$$(0%! '#>.%0# 3.( *!'%>*( .3"#0%*( %. 40('! '% #$10%"#0# () "#4)%! % &()!0% #)(D!0(/%5 F#0 1!/#0 (&#0# 3.( '%$*0#/( 10#*%$%!.#, "( (.*+# 3.( D3!.( &#)!*%/I '% *()7 *!)!, )( $*#)/( 2 0%*('3/( $3 3.( *!'%>*( '% /%1! E0(8%!.(0%! %. &%04!)( >$$(5 9!&#.'! %.!)/0# !1#0(0# *!. .3"#0% 1!$%/%&% # .#4(/%&%, $% 2 10#E#0%/! 3/%)%87 8(0# )( 0(110#$#./(8%!.# .3"#0%*( %. *!"1)#"#./! ( '3# 1!%*+N /()# $*#)/( 0#.'#&( $#"1)%*% )# !1#0(8%!.% (0%/"#/%*+# '( #$#43%0#, $%( '() 13./! '% &%$/( 10(/%*! =$/#$30( '#) *!'%*#?, $%( 1#0 <3(./! 0%43(0'( )-%"1)#"#./(8%!.# >$%*( %. <3(./! )( D!(0' *!./%#.# $/03//30# *+# $!.! E(*%)"#./# *!.>430(D%)% 1#0 <3#$/! /%1! '% 3/%)%88!5 J*#.'#.'! 1%O .#) '#//(4)%!L (&#.'! ( '%$1!$%8%!.# 18 D%/ # '!&#.'! 0(17 10#$#./(0# 1#0 % *!#P*%#./% WNk /3//% % &()!0% *!"10#$% /0( −1 # 1, 3/%)%88(.'! )( *!'%>*( E0(8%!.(0%( $!10(**%/(/(, 3. <3()3.<3# .3"#0! n *!. −1 ≤ n ≤ 1 1#0 #$$#0# 0(110#$#./(/! *!00#//("#./# '#&# #$$#0#L QR.

(58) ! "#$ "$%&' ()*' &)+,%"+%(',) "#$ 2b−n int bits − 1- .)/# n0int0bits 1 23 /'+)$# (4# %3.%(' 52'3,% .#% 18 6%, *)3) 2,%+%77',% "#$ $'""$#*#3,'$# +' "'$,# %3,#$' .#+ 32&#$) n # ,'+# /'+)$# .#/# #**#$# '+&#3) "'$% ' 1 ")%(48 +' $'""$#*#3,'7%)3# 1 %3 C2 # *# ,'+# /'+)$# 9)**# &%3)$# .% 1 *% "#$.#$#66# +:%39)$&'7%)3# $#+',%/' '+ *#;3) (4# *,' *2++: !. !". <! *2((#**%/'&#3,#- .)") '/#$ #=#,,2',) 23 '$$),)3.'&#3,) '++:%3,#$) "%> /%(%3) .#+ $%*2+,',) ),,#32,) '+ "23,) "$#(#.#3,#- *)+'&#3,# 3#+ ('*) %3 (2% n < 0- 1 3#(#**'$%) ,$'*+'$# %+ $%*2+,',) .% 2b "#$ "),#$+) $'""$#*#3? ,'$# ()$$#,,'&#3,# %3 C2! @ ")% ")**%6%+# ()3/#$,%$# %3 6%3'$%) %+ /'+)$# 32&#$%() ()*A ),,#32,)! B3 9)$&2+#C D'&"%)3# =. . *# n ≥ 0. n · (2b−n. int bits. − 1). n · (2b−n. int bits. − 1) + 2b *# n < 0. E. #*#&"%) %+ 32&#$) n10 = −0.273618926- .)") #**#$# *,',) *('+',) # ,$'*+',) F"#$ n0int0bits = 1G .%/#3,#$#66# 226280 52%3.% ()3/#$,#3.)+) %3 23 32&#$) 6%3'$%) *2 18 6%, *% ),,#$$#66# n2 = 110111001111101000! H/)+;#3.) +:)"#$'7%)3# %3/#$*' *% ")**)3) %3/#(# ,$)/'$# +# ()$$%*")3.#37# ,$' %+ 32&#$) #*"$#**) %3 ().%(# 6%3'$%) # +:#=#,,%/) /'+)$# $'""$#*#3,',)- "#$ #*#&"%) *# *% 4'33) ' .%*")*%7%)3# b = 3 6%, # n0int0bits = 1 *% ),,#3;)3) +# *#;2#3,% ()$$%*")3.#37#C  011 → 3/3     010 → 2/3     001 → 1/3    000 → 0 111 → −1/3     110 → −2/3     101 → −3/3    100 → −4/3 I' (2% $%*2+,' #/%.#3,# (4# ,'+# ().%J(' 1 *,',' *(#+,' %3 52'3,) )+,$# ' &'3,#3#$# K*#&"+%(%L +# )"#$'7%)3%- ()3*#3,# .% $'""$#*#3,'$# ,2,,% % /'+)$% ()&"$#*% ,$' −1 # 1!. <.

(59) !"! #$%&'()$ *$++,(-$./(0 !"#$!%&! '(! )**+#%&!,%- $# .%) /&,.&&.,) '-01-/&) $) $#"!,/# 2*-''(# ),#&3 0!&#'# 1-/&# #% /!,#!4 5 )*&- #* ,#/'(#- $# #%'-,,!,! #% .% -"!,6-7 $!# ,#/.*&)&#8 9%%)%:#&.&&- /# $!"! 1,!'#/),! '(! .&#*#::)%$- .%) '-$#;') <,):#-%),#)4 &)*! 1,-2*!0) /# "!,#;') /-*)0!%&! #% /!=.#&- ) /-00!>/-&&,):#-%#4 #%<)&&# # 0-*3 &#1*#')&-,# %-% 1-//-%- =!%!,),! -"!,6-7 1!,'(? #% -=%# ')/- /.**) *-,- ./'#&) 5 /!01,! 1,!/!%&! .% ")*-,! #%<!,#-,! ,#/1!&&- )# ")*-,# #% #%=,!//- @/# /&)%%0-*&#1*#')%$- #%<)&&# ")*-,# 0#%-,# - .=.)*# )**+.%#&AB8 C!, !"#&),! *+-"!,6-7 /-%- /&)&! .&#*#::)&! $.! /-*.:#-%# #% =,)$- $# 0#%#0#:3 :),! *) 1,-2)2#*#&A $!* /.- "!,#;'),/# ! $# ),=#%),*- %!* ')/- #% '.# /# "!,#;'(#8 /&)&- $!&&- '(! #* ')*'-*- !D!&&.)&- $)**) !""#$%& "#!%! ,!#&!,)&- /.# 0!$!/#0# ')01#-%# 1!, .% %.0!,- $# "-*&! 1),# ) log2 N 8 9% /!=.#&- )$ )*'.%! "!,#;'(! /1!,#0!%&)*# 5 /&)&- ,#/'-%&,)&- '(!4 )%'(! .&#*#::)%$- )**+#%=,!//$!* $#/1-/#&#"- /!=%)*# '-% )01#!::! 1#''-*!4 =#.%&# )$ .% '!,&- /&)$#- $!* ')*'-*- @'(! $#1!%$! 1,#%'#1)*0!%&! $)**+)01#!::) $!* /!=%)*! #% #%=,!//-B4 # ")*-,# #% ./'#&) $)**) !""#$%& @-""!,- *+.%#&A $# ')*'-*-B ,#/.*&)")%- /'-,,!&3 &#E !,) !"#$!%&! '(! *) ')./) $# F.!/&- !,,-,! !,) $) )&&,#2.#,! ) ")*-,# $!* /!=%)*! #% #%=,!//- &,-11- =,)%$# # F.)*# <)'!")%- /)&.,),! #* ,#/.*&)&-8 G) /-*.:#-%! ) F.!/&- &#1- $# 1,-2*!0) 5 /&)&) F.!**) $# $#"#$!,! ) 0!&A &.&&# # ")*-,# #% #%=,!//- )**) !""#$%&4 #% F.!/&- 0-$- /# ,#!/'! ) *#0#&),! #* "!,#;'),3 /# $!**+-"!,6-78 H)*! )D!,0):#-%! /),A 1#I '(#),) %!* 0-0!%&- #% '.# "!,,A )%)*#::)&) $!&&)=*#)&)0!%&! *) /&,.&&.,) $!# $#"!,/# 2*-''(# '(! '-/&#&.#/'-%#* '($#8 G) /!'-%$) /-*.:#-%! ,#=.),$) *) =!/&#-%! $!* ,#/.*&)&- %!* ')/- #% '.# /# $-"!//! "!,#;'),! .% -"!,6-78 %-&- $)**+)*=!2,) 2#%),#) '(!4 .&#*#::)%$.%) '-$#;') #% C2 !$ !D!&&.)%$- .%) /!,#! $# /-00!>/-&&,):#-%#4 5 %!'!/3 /),#- "!,#;'),! /-*)0!%&! )**) ;%! $# &.&&! *! -1!,):#-%# *) 1,!/!%:) $# .% 1-//#2#*! -"!,6-78 J#K '(! 5 /&)&- <)&&- 5 '-/&#&.#,! $!# /-00)&-,# ! /-&&,)&3 &-,# L/1!'#)*#M #% =,)$- $# ,#'-%-/'!,! #* "!,#;'),/# $!**+-"!,6-7 !4 %!* ')/- #% '.# #* ,#/.*&)&- -&&!%.&- /#) /'-,,!&&-4 /)&.,),*- )* ")*-,! 0)//#0- - 0#%#0!/1,#0#2#*! $)**) '-$#;') ) /!'-%$) $!* &#1- $# -"!,6-7 =!%!,)&-8 H)*# /&,.&3 &.,!4 '(! '(#),)0!%&! ()%%- .%+-''.1):#-%! $+),!) 0)==#-,! ,#/1!&&- )$ .% /-00)&-,! /!01*#'!4 /-%- /&)&! .&#*#::)&! /-*)0!%&! )* &!,0#%! $# .%) /!,#! $# /-00!>/-&&,):#-%#8 N-% 5 %!'!//),#- #%<)&&# '-%&,-**),! # ,#/.*&)&# #%&!,3 0!$# )**) /!,#! $# 2*-''(# /-00)>/-&&,):#-%! #% F.)%&-4 )%'(! /! =!%!,)%-"!,6-74 &)*! !,,-,! 1.K !//!,! L,#)//-,2#&-M $)# 2*-''(# /.''!//#"#8 C!, '(#)3 ,!::) "#!%! !/1-/&- .% !/!01#- %!* ')/- #% '.# "!%=)%- !D!&&.)&! $.! /-00! '-%/!'.&#"! /. %.0!,# !/1,!//# #% C2 ) 3 2#&4 *) 1,#0) $!**! F.)*# =!%!,) .% OO.

(60) !"#$ %& '( !) *" ++","#" (* #(-)*+.+ /"**. -"0)",+" "-1#"--( ,"2. n = n1 + n2 + n3 '.1",/ 34". .** #. #(-)*+"#52.  n1 = 2 → 010 n2 = 3 → 011  n3 = −2 → 110 n1 + n2 = 5. (* - 66.+ #" .!",/ . /(-1 -(7( ," - * 3 8(+ 0","#"#5 ), !"#$ %9 #": -+(+)",/ 3 6" #(-)*+.+ (* ,)6"# 101 → −3& ; <)"-+ 1),+ -( - 66. .* #(-)*+.+ ++",)+ /. n1 + n2 (* !.* #" n3 = −2& =)(,/(2 n1 + n2 = 5 (n1 + n2 ) + n3 = 3 (,>.++(. 1 1 0. 0 1 1. 1 0 1. + =. → −3 → −2 →3. ?(-)*+. "!(/",+" <)(,/( 34" *@ !"#$ % 34" -( !"#(A3. ,"**. 1#(6. - 6: 6.9 !("," #(3 61",-.+ /. ), )*+"#( #" !"#$ % ,"**. - 66. -)33"--(!.9 ++",",/ (, <)"-+ 6 / ), #(-)*+.+ 3 ##"++ &. BC.

(61) !"#$%&% ' ()"&*)*+$!,#%+* -./0 * 1*234#,#%+* 1*& 1#2"%2#$#5%. !"#$% &'() *+,-.% % /01++,! 2-0 2!3413!5!61 !.40-.-75%51 89!75-$1 !"# : !.40-.-75%51; !7 0!7"#%""!1 <=>8; 7-0 ?0- $%&'#()*+' @7%0!AA%721 2-55%"0!%5%.-75- 0% 3#% 35$#55#$%; !0 2!3413!5!61 4$-3-75% 6 !7B "$-33! - 2 #3+!5-; $!34-55!6%.-75-). CD.

(62) !"#$%%. •. !"#$%& !"#$%&'" % ()*+((" %($" ,-+.$" .+/&%(+ 0 !"..)1)(+ %1)()$%#+ (2-3 .4)$% #$%& !+# (% (+$$-#% '+) '%$)5. • '##(")!. 4"&.+&$+ ') )&*)%#+ %((% 678 /() )&')#)99) 4:+ .) *"/()"&" (+/3. /+#+; -&% *"($% %1)()$%$" )( .+/&%(+. • *&'(&. !"#$%&5. 0 )( .+/&%(+ 4:+ :% )( 4"<!)$" ') %**)%#+ "/&) .)&/"(" .$%/+;. !"#$%&'"(" % ()*+((" %($" !+# %(<+&" -& !+#)"'" ') 4("4= .) %**)% (2+.+3 4-9)"&+ '+((2)&$+#" .$%/+5. • (*&. !"#$%&'" % ()*+((" %($" ,-+.$" .+/&%(+ .) #+.+$$% (2)&$+#" .$%/+; ,-)&3. ') .) %99+#%&" ) #+/).$#) )& +.." 4"&$+&-$)5. • +. ,-+.$" .+/&%(+ !#"*)+&+ '%((2-&)$> ') 4"&$#"((" +' 0 !%#) %( &-<+#". '+((" .$%')" 4:+ .) .$% +.+/-+&'"; *% '%. • ,-.. 0. %. (log2 N ) − 15. .+/&%(+ ') 4("4=5. &%' ($. • #$%&. )& %44"#'" 4"& ) .+/&%(). !"#$%&. +'. '##(")!. #+.$)$-).4+; %' "/&). 4)4(" ') 4("4= )( 4"&$+&-$" '+((% 678 !#+.+&$+ %((2)&')#)99" .!+4)?4%$" )&. •. '##(")!5. $*. !"#$%&'".) % ()*+((" %($" .+/&%(% %((2-&)$> ') 4"&$#"((" /("1%(+ (2%*3. *+&-$% +.+4-9)"&+ ') -& )&$+#" .$%/+5. !" #$ !""#$%& !"!" #$%&$$&%' @)A 4:+ 4".$)$-).4+ (2-&)$> ') 4%(4"(" B"&'%<+&$%(+ '+((2)&$+#" %(/"#)$<"; 0 (%. )*++,-./5. C% .$#-$$-#% ') ,-+.$" 1("44" '+#)*% ')#+$$%<+&$+ '%((+ B"#<-(+ '+(. 4%!)$"(" !#+4+'+&$+; )& !%#$)4"(%# <"'" '%. DE.

(63) X(k) = G(k) + WNk H(k) X(k + N/2) = G(k) − WNk H(k) !"#$%& '$()*(+)& &( ,+*-)* .$%/+#* -$($ )+))& (+/*%& '$/0#*--&1 #" 0%&/" $0*%"2&$(* -!$#)" 3 -)")" ,+*##" 4& -'$/0$%%* #" 0%*'*4*()* *-0%*--&$(* &( 0"%)* %*"#* * 0"%)* &//"5&("%&"6 78$0*%"2&$(* 3 (*'*--"%&" &( ,+"()$ +)&#&29 2"(4$ +( 4&-0$-&)&!$ 4&5&)"#*1 ($( 3 0$--&:&#* %"00%*-*()"%* 4&%*))"/*()* +( (+/*%$ '$/0#*--$1 #8+(&'$ /$4$ 0*% 0$)*%#$ *-0%&/*%* 3 '$/* '$00&" 4& 4+* !"#$%& %*"#&6 ;!!&"/*()* & :#$''<& 4& *#":$%"2&$(* '$()*(+)& (*##". !""#$%&. -$9. ($ )"#& 0*% '+& ,+*-)" '$00&" (+/*%&'" !&*(* )%"))")" '$/* +( +(&'$ -*5("#* '$/0#*--$ '$/0$-)$ 4" 0"%)* %*"#* * 0"%)* &//"5&("%&"6 ="##" -'$/0$-&2&$(* -& $))&*(*>. ?6 0*% &# '$*@'&*()*. WNk 1. %&'$%4"(4$ '<*. 2π. WNk = e−j N k * '<* +( *-0$(*(2&"#* '$/0#*--$ "#)%$ ($( 3 '<* +(" '$00&" 4& -*5("#& %*"#&1 %&-0*))&!"/*()* '$-*($ * -*($1 4*%&!">. WNk. =e. k −j 2π N. . 2π 2π = cos − k + j sin − k N N. &($#)%* 4">. cos (α) = cos (−α) sin (−α) = − sin (α) %&-+#)". WNk. . 2π 2π =e = cos − k + j sin − k = N N 2π 2π k − j sin k = cos N N −j 2π k N. AB.

(64) ! "#$ %& "$'('))' H(k)WNk. H(k) = H(k)ℜ + jH(k)ℑ # 2π 2π k k − j sin k WN = cos N N "'*#*('. R(k) = H(k)WNk +% '))%#*# 2π 2π k + H(k)ℑ sin k R(k)ℜ = H(k)ℜ cos N N 2π 2π R(k)ℑ = H(k)ℑ cos k − H(k)ℜ sin k N N ,! %& $%+-&).)' /*.&# $%+-&). #++#$#. X(k)ℜ = G(k)ℜ + R(k)ℜ X(k)ℑ = G(k)ℑ + R(k)ℑ . X(k + X(k +. N ) 2 ℜ N ) 2 ℑ. = G(k)ℜ − R(k)ℜ = G(k)ℑ − R(k)ℑ. 0. 1-#+)# #+"$#++%'*% (#$%2. &' +34#5. . 6&'334% $#&.)%2' .&&. !""#$%&!. 7.

(65) !"# "!$%&'%! (#))! $*+#"', %')# -.$/!$.%.0! +' *!"# .(1&#$$. 3 *!//.# -. $#1('). *!"/)#$$. 23.(-. 6 $#1('). &#'). # &#$%.%3.$*# -!/! )4#)'5!&'6.!(# 2 *!/7 /.# -. $#1('). *!"/)#$$. # 23.(-. 4 $#1('). &#').8 9(!)%&# *!(%.#(# ') $3! .(%#&(! 3( "!)%./).*'%!&# # 3( $!""'%!&# #(%&'"5. *!"/)#$$.8 :#& 23'(%! &.13'&-' 23#$%43)%."!, ; $#"/).*#"#(%# *!$%.%3.%! -' -3# $!""'%!&. # -3# $!%%&'%%!&., /#& 23'(%! &.13'&-' .) "!)%./).*'%!&# .(0#*# )' $3' $%&3%%3&' &.$3)%' #$$#&# /.< '&%.*!)'%' # 23.(-. 0.#(# -#$*&.%%' -#%%'1).'%'"#(%# (#) /'&'1&'=! $#13#(%#8 ! "#!$%&!%'($#)* '#"&!*++#. 9) *!"/.%! -#) "!)%./).*'%!&#, (#) *')*!)! -#) &.$3)%'%! -#))' !""#$%&, ; 23#))! -. "!)%./).*'&# .) $#1(')# *+# ; $%'%! -#>(.%! H(k) /#& .) *!#?*.#(%# WNk 8 @3#$%! 5)!**!, #$$#(-! ' %3%%. 1). #A#%%. 3( "!)%./).*'%!&# *!"/)#$$!, ; $%'7 %! ."/)#"#(%'%! .( "!-! .(-./#(-#(%# &.$/#%%! '))4.(%#&' $%&3%%3&', .) *+# )! &#(-# 3( '//'&'%! -#) %3%%! 1#(#&.*! .( 1&'-! -. !/#&'&# '(*+# $3 ')%&. -.$/!$.%.0.8 :&!/&.! /#& .) "!%.0! $!/&'**.%'%! 0.#(# -#$*&.%%! ' /&#$*.(-#&# -'. $#1('). *!( *3. -#0# !/#&'&# B# *+# 23.(-. -#0# #)'5!&'&#C, (#))' $3**#$7 $.0' -#$*&.6.!(# 0#&&'((! .(='%%. 3%.).66'%. .(1&#$$. # 3$*.%# 1#(#&.*+# )# 23'). /#&"#%%!(! 3(' /.< *+.'&' #$/!$.6.!(# -#1). '&1!"#(%.8 !"# /#& )! $*+#"' 1#(#&')# -#))' !""#$%&, '(*+# /#& .) "!)%./).*'%!&# ; $%'%! (#*#$$'&.! $*!"/!&&# .) *')*!)! .( /'&%# &#')# # /'&%# .""'1.('&.'8 !($.-#7 &'(-! 3(' $#"/).*# "!)%./).*'6.!(# *!"/)#$$', 0!)#(-! "!)%./).*'&# %&' )!&! . -3# 0')!&. X # Y , ' /'&%.&# -'D X = xℜ + jxℑ. #. Y = yℜ + jyℑ. .) &.$3)%'%! -#) )!&! /&!-!%%! ; /'&. 'D Z =X ·Y. !00#&!. z ℜ = xℜ yℜ − xℑ yℑ z ℑ = xℜ yℑ + xℑ yℜ. -' *3. &.$3)%' #0.-#(%# *+# /#& /!%#& $0!)1#&# %')# !/#&'6.!(# $!(! (#*#$$'7 &. 23'%%&! "!)%./).*'%!&., 3( $!""'%!&# # 3( $!%%&'%%!&# B23.(-. 3( 3)%#&.!&# $!""'%!&#C8 E%.).66'(-! "!)%./).*'%!&. -. %./! #"5#--#- # 23.(-. /&#$#(%. .( 23'(%.%F ).".%'%' '))4.(%#&(! -#))' '($), ; $%'%! (#*#$$'&.! &.#)'5!&'&# )# GH.

(66) !"# !!$%&$ "# ' ( &)$ " # ' #'*# ($ +$,$)*# +-.)$+$//% ($ )*+$ ($!"%!$)$0$1 2&-%))$,* !%+./$%& 3 #$!.+)*)* !! # 4. ++* "#%"%!)* $& .&* !!"#$ %#&' '&%( ( ++* )#"#'* 56789 # +*)$0* *++-.)$+$//% ( $ ,%+)$"+$'*)%#$1 : + (%'., &)% !$ '%&; !$<+$*= " # #$(.## $+ &., #% ($ ,%+)$"+$'*)%#$ .)$+$//*)$ +-*# * %''."*)* 5'-3 (* ) & # '%&)% ( + >*))% '? $ ,%+)$"+$'*)%#$ ,@ (( ( ?*&&% .&-%''."*; /$%& &%& $&($A # &) 9= ($ ! <.$# +* ,%+)$"+$'*/$%& '%,"+ !!* .)$+$//*&(% !%+*, &) )# ,%+)$"+$'*)%#$ *+'.&$ @+%''?$ !%,,*B!%))#*/$%& 1 C& ) #,$&$ ,*) ,*)$'$= +-$) # '? "%#)* *++* !%+./$%& *(%))*)* 3 $+ ! <. &) D. Z = (xℜ + jxℑ ) · (yℜ + jyℑ ) ( E& &(%.  p = xℜ yℜ    q = xℑ yℑ r = (xℜ + xℑ ) · (yℜ + yℑ ) =    = xℜ yℜ + xℜ yℑ + xℑ yℜ + xℑ yℑ. *++%#*. z ℜ = p − q = xℜ y ℜ − xℑ yℑ zℑ = r − (p + q) = xℜ yℜ + xℜ yℑ + xℑ yℜ + xℑ yℑ − − xℜ yℜ − xℑ yℑ = xℜ yℑ + x ℑ yℜ '? #$!.+)* !! # +* !%+./$%& ( ++* ,%+)$"+$'*/$%& '%,"+ !!* )#* X Y < & #$'$1 F*++ >%#,.+ "# ' ( &)$ ( #$0* ($# ))*, &) +% !'? ,* * @+%''?$ ( + ,%+)$"+$'*)%# 5G$<.#* H1I91 J+ !.% $&) #&% !%&% "# ! &)$D $& .& "#$,% !)*($% (. ,%+)$"+$'*)%#$ ,@ (( ( (. !%,,*)%#$= $& .& ! '%&(% !)*($% +-.+)$,% ,%+)$"+$'*)%# .)$+$//*)%= .& !%,,*)%# .& !%))#*))%# $&E& = " # '%&'+.( # $+ '*+'%+% ( ++* "*#) $,,*<$&*#$*= !$ )#%0* .& .+)$,% !%,,*)%# 1 K* !)#.)).#* $,"+ , &)*)* 3 0$( &) , &) "$L '%,"+ !!* ?* "# !)*/$%&$ $&> #$%#$ 5$& ) #,$&$ ($ 0 +%'$)M ($ '%,".)*/$%& 9 #$!" ))% * '$N '? !$ !*# @@ "%).)% %)) & # .)$+$//*&(% 4.*))#% ,%+)$"+$'*)%#$= ,* #$!.+)* !! # .& @.%& '%,"#%, !!% )#* +* #*"$($)M ($ '*+'%+% +-%''."*/$%& ($ #$!%#! 1. !"!# $%&'())* +,' -*+&-, , ('.,/&*/& 0),-&1-2,. !"# $ %&'%('). K-$&) #* !)#.)).#* E&%#* ( !'#$))*= 0$!$@$+ & ++% !'? ,* 5G$<.#* H1H9= 3 !)*)* $,"+ , &)*)* & $ E+ !D IO.

(67) !"#$% &'() *+,-.% /-0 .102!30!+%21$- +1.30-441 • !""#$%&'()* 5 • +,-./#01-!/"'()* 5 • 2!-'()* 5 • 2! '()* 5. 67 8%4- %00% +1/!9+% /-97!2% 7-0 3%$%"$%:1 ('&';< = 42%21 3144!8!0- -42$%31> 0%$- !0 :#7?!17%.-721 @-$1 - 3$13$!1 A+!1= 8!2 % 8!2B /-00- 4!7"10- 13-$%?!17! /% 4@10"-$- 7-00% !""#$%&' C- 13-$%?!17! A%$!2.-2!+,-B 4@102- 4171) •. %//!?!17-. •. 4122$%?!17-. •. .102!30!+%?!17-. D-$ 0- 3$!.- /#-< 717 = 42%21 7-+-44%$!1 3$-/!431$$- %0+#7 2!31 /! .1/!9+% 1 +172$1001 4#! 8!2< !7:%22! #2!0!??%7/1 #7% +1/!9+% !7 @!$"10% 944%< %//!?!17- 4122$%?!17- @-7"171 4@102- %001 42-441 !/-72!+1 .1/1 !7 +#! @-7"171 -4-"#!27-0 +%41 /! #7% +1/!9+% !72-$%' E 4#331$21 /! 2%0- %F-$.%?!17- = 4#G+!-72:%$- #7 4-.30!+- -4-.3!1 7-0 +%41 !7 +#! A+1.- @!421 3$-+-/-72-.-72-B b = 3 - nHintHbits = 1' &I.

(68) !"#$% &'&( )*+,-% *.-/0,1. 2,00% 3#11,45 6.0,72. /,$ ,8,-/!. .11,7,$, 1/3 = 2/3 − 1/3 9 8#:*!,71, 8;.0",$, #7% 8.-< -% 3!7%$!% 1$% 010 → 2/3 , 111 → −1/3= 2% *#! $!8#01% 010 + 111 = 001 → 1/3' >!;,$8. !7;,*, 9 !0 *%8. 2,! -.01!/0!*%1.$!= /,$ ! ?#%0! 9 81%1. 7,*,88%$!. *.-/!,$, #7. 81#2!. /!@ %//$.A.72!1.' B -.01!/0!*%1.$! /$,8,71! 7,00% 3.%$2 ./,$%7. 8# 8,"7%0! % b = 18 3!1 2! 1!/. !"#$% *!.9 8# 7#-,$! !71,$! $%//$,8,7< 1%1! !7 C2 , $,81!1#!8*.7.= *.-, ;%0.$, !7 #8*!1%= #7 8,"7%0, % 2·b = 18·2 = 36 3!1 8,-/$, $%//$,8,71%1. !7 C2' B0 $!8#01%1. *+, 8! .11!,7, 2%00% -.01!/0!*%< C!.7, 2! 2#, 7#-,$! !7 *.2!D*% A$%C!.7%$!% 9 E% /%$1!$, 2%00F G /%$! %0 n int bits /$.2.11. 2,! 2#, ;%0.$! 2!;!8. /,$ 2 !"# $%%"&"#" '& #()'*%+%$ ,$#-. !". !". #"%%$ . /'(&0( &","))+#($ 1#"*"2+#" (* #()'*%+%$ 3$22"#$ 1#"*"2+#". n6int6bits (& n6int6bits = 15:. 0()1$&(4(*(5 + 1+#%(#" 0+ ")"71($ 31"#. b=3. ". ;( 2'$*" 7$*%(1*(,+#". 1. −2/3 → 110. 1. 1. 1 0 1. !. ". #. 7"&$ #()1"%%$ +**8. 1"#. 1 0 1. 0 1 0. $. %. 4, 3, 2. " ,($. ( 1#(7(. b. 0"(. 2·b. 4(%. 9+,"&0$ '&. 1/3 → 001 · = &'()*)'+). 4(% + 1+#%(#" 0+*. !". 111 → −1/35 1#"&0"&4(% 3 −n6int6bits5. <+ ,'( . 1$))(4(*" #(,+2+#" (* #()'*%+%$ ,$##"%%$ 3 0$ ( 4(%. b. =8$1"#+>($&" +11"&+ (**')%#+%+ 2("&" )2$*%+ +**8'),(%+ 0"( 7$*%(1*(,+%$#( ,$&%"&'%( +**8(&%"#&$ 0"* 7$*%(1*(,+%$#" ,$71*"))$ "0 . 1$))(4(*" #(,$&$),"#*+ (&. ?@.

(69) ! "#$%&$$' (") *'(+*" *'!$"! $' !") ,)" !"#$%&'"($)*+,-- +! * + . ("#*%+$$' +) /')$+0)+*&$'%" #$"##'1 !" !# ! $. 2+#$+!3 4561 7"$'(' (+ 0%")+"8' ("+ 9+$ &)): #*+$& ("+ /')$+0)+*&$'%+. !" # $%& '()(*+,) -. - /*,/)*+,) '01/)0 '()(*+,) - /*,/)*+,) 2 3 3 4 $%& '()(*+,) -. - /*,/)*+,) '01/)0 '()(*+,) - /*,/)*+,) 25. . 67 !" # $%& '()(*+,) -. - /*,/)*+,) '01/)0 '()(*+,) - /*,/)*+,) 2 - 4 $%& '()(*+,) -. - /*,/)*+,) '01/)0 '()(*+,) - /*,/)*+,) 25 89 !" : $%& '()(*+,) -. - /*,/)*+,) - 5. '01/)0 '()(*+,) - /*,/)*+,) 2 -. . . ;'8" !"!#$%"& . ):"< +8&)"!$" (+ b "( + #"3!&)+ ' ( "( ) #'!' )" #*+$" ("+ $%" /')$+0)+*&$'%+5. ="% *'!*) ("%" < "#$& #">+'!"- )& .())%/01 . #$&$& %"#& #+!*%'!& !"+ *'!? @%'!$+ (+ ! #"3!&)" (+ *)'*A "#$"%!' *B" 0 C "##"%" &9+)+$&$' ' +!+9+$' $%&/+$" ):+!3%"##' *+ &!*B:"##' #+!*%'!'5 D3!+ 8')$& *B" +) #"3!&)" (+ *)'*A #+ 0'%$& & )+8"))' &)$'- "( +) #"3!&)" *+ . & ,-,- + (&$+ &)):+!3%"##' ("))& .())%/01 8"!3'!' ")&9'%&$+ " 0'%$&$+ &)): #*+$& %"#$&!(' (+#0'!+9+)+ ,!' &) # **"##+8' @%'!$" (+ *)'*A5. !"#$!%%! &'%%(!)'$*!+ E+0%"!("!(' < &!$' ("$$' !") 0&%&3%&@' F545F $ $$+ + 8&)'%+ +! +!3%"##' &)):+!$"? %& .())%/01 #'!' #$&$+ (+8+#+ 0"% ( " &$$%&8"%#' !' #B+@$ & ("#$%&GH'(+*" 45FI5 ="% < &!$' %+3 &%(& +!8"*" + #'//&$'%+J#'$$%&$$'%+ & #&$ %&>+'!" (") %+? # )$&$' +! *&#' (+ '8"%K'L- #'!' #$&$+ $+)+>>&$+ &)): #*+$& ("))& .())%/01 " 0%+/& ("+ /')$+0)+*&$'%+ G+! #'#$&!>& $ $$+ *')'%' *B" !"))& M+3 %& 454 #'!' *'!$%&##"3!&$+ (& ! &#$"%+#*'I5 2:&)3'%+$/' $+)+>>&$' 0"% ("$"%/+!&%" +) 8"%+,*&%#+ (+ ! '8"%K'L . /')? $' #"/0)+*"5 N+"!" "O"$$ &$& ):'0"%&>+'!" &%+$/"$+*& G#'//& ' #'$$%&>+'!"I# **"##+8&/"!$"- &!(&!(' &( &!&)+>>&%" #')' +) 0%+/' 9+$ ("+ ( " '0"%&!(+ " (") %+# )$&$' #+ ("$"%/+!& )& 0%"#"!>& (")):'8"%K'L !") #"3 "!$" /'(' G!") *&#' ("))& #'//&- &!&)'3' . < "))' ("))& #'$$%&>+'!"I1 • #" + ( " '0"%&!(+ #'!' "!$%&/9+ 0'#+$+8+ " +) %+# )$&$' %"#$+$ +$' . !"?. 3&$+8' &))'%& #+ . 8"%+,*&$' ! '8"%K'L " 8+"!" %"#$+$ +$' ! %+# )$&$' 0&%+ &) /&##+/' 8&)'%" 0'#+$+8' %&00%"#"!$&9+)" G*B" *'%%+#0'!(" &))& *'!,3 %&>+'!" 011 . . . 1I5. 4F.

(70) •. ! " #$! %&!'()#" %)% !)*'(+," )!-(*"." ! "/ '" $/*(*% '! *"*$"*% 0 &% "*"1 .% (//%'( " 0 .!'"23(*% $) %.!'4%5 ! 6$")#" ."!)! '! *"*$"*% $) '" $/*(*% &('" (/ +(. "+% .(/%'! )!-(*".% '(&&'! !)*(,"/! 738! 3%''" &%)#! (//(. 3%)2-$'(9"%)!. •. 100 . . . 0:;. )!" '! *()*" 3( " "/ '" $/*(*% '" $/*( !+&'! 3%''!**% !# ! !)*! #( %.!'1 4%5;. < '"&%'*(*% $) ! *'(**% #!/ 3%#"3! '!/(*".% (/ &'%3! % 38! -! *" 3! /( (1 *$'(9"%)! #!" .(/%'" #!/ %++(*%'! 7=%#"3! >;>:;. ?" *")- >;@A B !+&"% #" #"+!99(+!)*% #!/ !-)(/! (//C")-'! % #!//( !". !""#$%& . !"#$%%& " !'(" ") ")*+$,,& '--' ./(($+0-1 2$+ $3"('+$ &3$+0-&4 *+5, 6 !'('5."(, 78 9: *+ 6 !'('5."(, 78; ,$+3$ 2$+ #')($)$+$ "- ,$*)& *+5, 6 !'('5."(, < !&4)(& =8 9: *+ 6 !'('5."(, 7 !&4)(& 78;. . . ?" *")- >;>A D'%3! % #" (*$'(9"%)! #!/ !-)(/! ") $ 3"*( ") !-$"*% (# %.!'4%5 !# !$ %& %" %! %# %$ #& #" #! ## #$ '&. &40- > 2+&?$,, 6@ AB A C5DEF 8 .$*") "0 @6 !'('5."(, 78 : G=G (H$) "0 B6 !'('5."(, 78 : G=G (H$) "0 C5DEF 6 !'('5."(, 78 : G= G (H$) I 9: C5DEF ; $-,$ I6 !'('5."(, 78 9: G= G; ,'(/+& '- #',,"#& 2&,"("3& I6 !'('5."(, < !&4)(& =8 9: 6 &(H$+, :J G7 G8; $)! "0 ; $-,$ I 9: C5DEF ; $)! "0 ; $-,$ "0 B6 !'('5."(, 78 : G=G (H$) I 9: C5DEF ; $-,$ "0 C5DEF 6 !'('5."(, 78 : G= G (H$) I6 !'('5."(, 78 9: G7 G; ,'(/+& '- #',,"#& )$*'("3& I6 !'('5."(, < !&4)(& =8 9: 6 &(H$+, :J G= G8; $-,$ I 9: C5DEF ; $)! "0 ; $)! "0 ; $)! "0 ; $)! 2+&?$,, ;. . !" #$ %&'( )*++*,-.* /$0 12$310$4,0 WNk !"!# $%&'(%()*+,-.)( ( /.0-/( ?! #$! EFG 7'" &!**".(+!)*! &!' "/ 3% !)% ! "/ !)%: %)% *(*! "+&/!+!)*(*! 3%+! EFG -!)!'"38!H (//C")*!')% #!" 2/!A >>. .

(71) • !"#$%& • "'(#$%&. !"#$ %" %&'(!")&!& "* +,-."/-$#&-0/1 0!$ *2$*0!/ 3",00/'0/ '&#3*"(&1 %" 4,&'0" %"'3/'"0")" 5 6&-& !"(/!%$!& (7& *$ 3!&'&-.$ %&**& %,& 89: %&!")$ %$ WNk. =e. k −j 2π N. = cos. . 2π 2π k − j sin k N N. & 3/"(7; W = WN2 1 5 ',<("&-0& (7& "* -,#&!/ %" (/&<("&-0" 3!&'&-0" -&*= *& 89: '"$ '/*$#&-0& N2 1 3&!("> *& %,& 89: (/-0&-?/-/ N2 )$*/!" %" (/'&-/ & '&-/1 ($*(/*$0" &-0!$#6" 3&! 0 ≤ θ < π (/- θ = 2πk & 4,"-%" k = 0, . . . , N2 −1@ N N 2. A$ '0!,00,!$ "#3*&#&-0$0$ !"'3&((7"$ "- 3"&-/ *& +/!#,*& $33&-$ "**,'0!$0&1 /?-,-$ %&**& %,& 89: 3!&'&-0$ "-+$00"B •. ,- '&?-$*& %". •. ,- '&?-$*& WNk @. •. ,- '&?-$*& $% (7& $6"*"0$C%"'$6"*"0$ "* '&?-$*& %". •. ,- '&?-$*& 89:@. #. !" #. $**2"-?!&''/ 3&! "* '"-(!/-"'#/@. $**2"-?!&''/ (7& (/!!"'3/-%& $**2&'3/-&-0&. &'"(). k. 3!&'&-0& "-. !" #@. (7& (/'0"0,"'(& "* )$*/!& %&* (/&<("&-0& *&00/ -&**$. &! *2"#3*&#&-0$."/-& "- *"-?,$??"/ DEFA '" 5 '(&*0/ %" %&'(!")&!*& (/#& $!!$G %" *+,'-./0$'1%$+.2 3&4)4'56)789 &":;)" <= (/- %"#&-'"/-& 3$!" $ N2 @ A"'0"-? H@IB J!!$G (7& %&'(!")& *$ 89: !"# $%&'!"# () *++*! ,- . , )*/"0#) 123 453 .6 7'89:%;<=9>?='%$ , @* *9A( ) 45 @.BC . -3D. . !" !"". . K- &-0!$#6& *& #&#/!"& 5 3!&'&-0& ,- 3!/(&''/ (7& ?&'0"'(& *2$6"*"0$."/-& %&* !" # & (7& 3/!0$ ',**2,'("0$ &'"()1 $% /?-" +!/-0& %" '$*"0$ %&* (*/(L1 #) /33,!& − sin ( 2π #)1 $ '&(/-%$ (7& '" '0"$ "* )$*/!& (/!!"'3/-%&-0& $ cos ( 2π N N *&??&-%/ %$**$ 89: %&* (/'&-/ / %&* '&-/@ A"'0"-? H@MB N&'0"/-& %&* (*/(L & *&00,!$ %&" %$0" +#*@9+./ E "+.F#)) , F0G HG H $%& H =? 3 A#I(C (6 F0G J K5K *C@ F0G K #L#C M#C (6 =? J K5 K M#C. HI.

(72) !" #$. !"#$ %& '() * +",-!.,$/0/1 *2 334 .5 4 /, .5 4 /, 61"+/77 4 /,. . . !"!" #$%%$&'($ )*++* ,-# ! "#$%"& %' ()*$# $% +#)'%)& !* "#))&,,* -*..*,/)* $&!!& 0123 4 5,*,# (&'&6 )*,# *,,)*7&)5# /'# 5")%., 289:8; "#',&'/,# '&% <!&5. !"#$%. &. "&'#$%=. :# 5")%., 4 "#5,%,/%,# .)%'"%.*!-&',& $* /' "%"!# *!!>%',&)'# $&! ?/*!& 7&'(#6 '# "*!"#!*,% % 7*!#)% $% "#5&'# # 5&'#3 * 5&"#'$* $&! <!& "@& 5% /,%!%AA*3 /'* 7#!,* "*!"#!*,# ,*!& 7*!#)& 7%&'& 5*!7*,* 5/ /' <!& $% ,&5,# !* 5,)%'(* $% "#$%"& BCD: )&!*,%7* *! "#&E"%&',& "*!"#!*,#= .*)% *. N/2. ! '/-&)# $% %,&)*A%#'% "#-.%/,& 4. "%#4 .*)% *! '/-&)# $% !#"*A%#'% $% -&-#)%* $% #('% 012=. F&) %! "*!"#!# $&% "#&E"%&',% 7&'(#'# /,%!%AA*,& !& 5&(/&',% +#)-/!&G. ) · (2b−n dHout(k) = round cos( 2πk N dHout(k) = round − sin( 2πk ) · (2b−n N. − 1) bits − 1). •. .&) %! "#5&'#. int bits. •. .&) %! 5&'#. int. D#7&. round(). ,&)# .%I 7%"%'# &. %'$%"* "@& %! )%5/!,*,# #,,&'/,# 4 5,*,# *))#,#'$*,# *!!>%'6. (2b−n. int bits. − 1). 5&)7& .&) )*..)&5&',*)& "#))&,,*-&',& %!. 7*!#)& '&% "#'+)#',% $&!!* "#$%<"* /,%!%AA*,*= D* /' &5,)*,,# $&! "#$%"& 289:8; "% 5% ./J +*"%!-&',& )&'$&)& "#',# $&!!>#.&)*A%#'& 57#!,* $*!!# 5")%.,G. " %$ %&. :%5,%'( K=LG M&'&)*A%#'& $&% "#&E"%&',% $&! "#5&'#. 5"1 . &89* : ;<3 =*. 3& 1"#, ** +"7 *<> 6. >*. ?83; : 3; 2 3>*<@* A ? ,!.,$!A.$7 3 ?8334 /, 4 $"BC-/ & 5"6/, * D +"7 E $=$ DFDG D34 5"1 . &89* : ;<3 561.,$5 * $"BC-/ F D +",-!7$ !H"0.+!-/+$"1 *I F C$C!A.$7 3 F ?? I J, DF=*.3 F. ?834 /, 4. . . . "/% "#))%5.#'$#'#3 "#-& )%5/!,*,#3 /'* 5&)%& $% )%(@& %' BCD: $&! ,%.#G. . :%5,%'( K=NG O#$%"& BCD: (&'&)*,# $* "#5P=-. +",-!7$ !H"0.+!-/+$"1 * K(LMM F C$C!A.$7 3F ?? N:ONKL!P(KQRN(:L. . KQ. .

(73) !. "#$% &'&()*+ ,'* -+&.*(/*. ! !" #$%&'$'()*+,-(' ' .-/,.' ! "#$!$ %&!!' ()* + ,#&!!$ %- .&.$"-//'"& - 0'.1-$2- %&! 3&42'!& '0,#-3-5$ 1"-.' %- &33&"& &!'6$"'5- %'!!7'!4$"-5.$ & %- 0$25&2&"& - "-3#!5'5- -25&".&%- & 82'!- 4&2&"'5- %'!!7'!4$"-5.$ 35&33$9 :$.& "-3#!5' %'! 0'1-5$!$ 3&0$2%$ -2;'55-< !7'!4$"-5.$ ==> 1&".&55& %- &!'6$"'"& - ?'!$"- %-"&55'.&25& @3#! 1$35$A ,#-2%2$2 + 2&0&33'"-$ #5-!-//'"& .&.$"-& -25&".&%-& 1&" !7&!'6$"'/-$2&9 ! 2#.&"$ %- !$0'/-$2- %- .&.$"-' 0B& B' !' ()* + 1&"0-C 1'"- '! 2#.&"$ %- 0'.1-$2&!'6$"'5- %'!!7'!4$"-5.$ 35&33$ & ,#-2%-< 3&0$2%$ !' 2$5'/-$2& 82$"' #5-!-//'5'< 1'"- '. N9. D&" !7-.1!&.&25'/-$2& + 35'5' #5-!-//'5'< 0$.& 2&! 0'3$ %&- .$!5-1!-0'5$"-< #2' %&!!& ()* &.6&%%&%< $11$"5#2'.&25& 0$284#"'5' 0$.& .$%#!$ D9 E' .&.$"-' #5-!-//'5' + %- 5-1$. !"# $%&'< ,#&35$ 1&"0BF 3- + ?$!#5$ ;'"& -2 .$%$ (!'')&*+. 0B& !& 0$11-& %- ?'!$"- 1"&!&?'5& %'!!' ()* ;$33&"$ 1$"5'5& '!!'. 0$25&.1$"'2&'.&25&< 5'!& 3-35&.' 1&".&55& -2;'55- %- !&44&"& $ 30"-?&"& %#& %'5- 3# %#& !$0'/-$2- %- .&.$"-' %-G&"&25- 2&! .&%&3-.$ -35'25&9 :$.& 4-H %&55$< -! 2#.&"$ %- !$0'/-$2- + 35'5$ 1$35$ 1'"- ' 0'.1-$2& + 0$.1$35$ %'. N. .&25"&< %'5$ 0B& $42-. b 6-5 1&" !' 1'"5& "&'!& & b 6-5 1&" ,#&!!' -..'4-2'"-'< 2·b 6-59 ?'!$"- $55&2#5- ?&24$2$. $42- !$0'/-$2& %- .&.$"-' B' #27'.1-&//' %.&.$"-//'5- 2&! 3&4#&25& .$%$I. •. -. b. 6-5 1-J '!5-< 0-$+ %'!. (2 · b − 1)K&3-.$. '!. bK&3-.$. 6-5< 0$35-5#-30$2$ !'. 1'"5& "&'!& %&! 0'.1-$2& &!'6$"'5$9. •. -. b. 6-5 1-J 6'33-< 0-$+ %'!. (b − 1)K&3-.$. '! 6-5. 0<. 0$35-5#-30$2$ !' 1'"5&. -..'4-2'"-' %&! 0'.1-$2& &!'6$"'5$9. L#&35$ 5-1$ %- 3#%%-?-3-$2& 1&".&55& %- 30-2%&"& !& %#& 0$.1$2&25- %&! 3&42'!& 3&.1!-0&.&25& 0$25"$!!'2%$ !& -25&"0$22&33-$2- 5"' - %-?&"3- 6!$00B-9 3&42'!- %- 0$25"$!!$ %&!!' ()* 3$2$I. •. !"#. !"$. &. "-31&55-?'.&25& -! 3&42'!& %- 0!$0M %&!!' 1$"5' ) & ,#&!!$. %&!!' 1$"5' N9. • #%%&#. &. #%%&$<. -2%-"-//- %&!!& !$0'/-$2- ' 0#- ;'"& "-;&"-.&25$9. • %'(# & %'($< !-2&& 0B& 1$"5'2$ - 3&42'!- -2 -24"&33$ O,#-2%- -2 30"-55#"'P '!!' .&.$"-'9 QR.

(74) •. !"#$ !"#%! "#$ 1+""+ 3 3()#+4. %& '()*+$( #" , -$+" #$ .,%#*+ /0.#$1# #$ " **.)+2. • &'$. &'%! , -$+"# %& +5#"#*+$( ( #$#5#,%($( "+ ,%)#**.)+ 1 # 1+*#4. • '($. '(%! , -$+"# %& +5#"#*+$( ( #$#5#,%($( # %"(%6 1 "" 1. '()* 4. 7" 8.$9#($+3 $*( 1 " 1#,'(,#*#:( ; 0.#$1# 3("*( , 3'"#% ! +1 (-$# 8)($* 1# ,+"#*+ 1 " %"(%6! #" :+"() %($* $.*( +""<#$1#)#99( $ )$ ( $ )%! :# $ " **( '()*+*( ,."" )#,' **#: .,%#* 4 = #" , -$+" &'$ ( &'% ; +5#"#*+*( +""()+ :# $ ')#3+ " **+ "+ "(%+9#($ 1# 3 3()#+ ,.%% ,,#:+3 $* :# $ ,%)#**+ %($ #" :+"() %($* $.*( #$ *($ ( *(%4 7$ (-$# %+,( #" :+"() ) ,*#*.#*( +"" .,%#* !"# ; , 3') ) "+*#:( + 1+*# " **# 1+""+ 3 3()#+ $($ )#-.+)1+ 3+# #" :+> "() ,%)#**( $ " 3 1 ,#3( %#%"( 1# %"(%6! #$ +%%()1( %($ "<('9#($ ! "#$ %& /?#-.)+ @4A2 %& ; ,*+*+ +**)#5.#*+ +""+ 3 3()#+/BCD24. ! !" #$%&%'(%&&'&%)$* +*((' ,*,)-%' E(3 ; ,*+*( 1 ,%)#**( $ " '+)+-)+8( ) "+*#:( +""<#3'" 3 $*+9#($ 1 ""<#$* )( 1#,'(,#*#:(! +: $1( ) +"#99+*( .$ "!'& /0.#$1# .$+ ,*).**.)+ +$%()+ #$%(3'" > *+2! 3+$%+ "<.$#*F 1# %($*)(""( -"(5+" %& ,# (%%.'+ ("*) *.**( 1# #$#9#+"#99+) @G.

(75) !" #$%&'! (&)!*+,- !)).-/0+-1& 1- $%!12&. 3" #$%&'! 4&)).&,-)50+-1& 4&+ 6&21!)+ (&)!*+,!)).-/0+-1& 7- 8%!12&. !"#$% &'() *+,!-./ 0- 12%."/ 3% 456' 57/.8- 3% ./9/::!;< 8! /=/;;#%$/ 8/33/ :!>#3%,!-.! +/$ 7/$!?9%$/ !3 9-$$/;;- @#.,!-.%>/.;- 8/3 8!:+-:!;!7-A B :;%;- ./9/::%$!- !.!,!%3!,,%$/ C>%D .#%3>/.;/E 3% 456' 0/33% 9-.?"#$%,!-./ 8/3 >-8#3- FG B +-::!H!3/ !.:/$!$/ #. ?3/A -++-$;#.%>/.;/ :;$#;;#$%;-A 9-. /:;/.:!-./ '9-/A 9-.;/./.;/ ! 7%3-$! 8! !.!,!%3!,,%,!-./ 8/33% 456 IJK' 533L!.;/$.- 8! M#/:;- ?3/ ! 8!7/$:! 7%3-$! :-.- /:+$/::! !. @-$>%;- /:%8/9!>%3/ :/.,% :/".- M#!.8! +/$ %7/$/ 8/! $!:#3;%;! 9-$$/;;! B ./9/::%$!- 9-.7/$;!$/ ! 7%3-$! .#>/$!9! N!. H%:/ OPQ ;$%>!;/ !3 >/;-8- 8/:9$!;;- ./3 +%$%"$%@- $/3%;!D 7- %33% 9-8!?9% #;!3!,,%;%' G/$ $/.8/$/ +!R %"/7-3/ M#/:;% -+/$%,!-./ B :;%;#:%;- #.- :9$!+; 65ST5U 9-.;/.#;- ./3 ?3/ !"#$%&$'%()*+"' S%3/ :9$!+; +/$>/;;/ 8! 9-.7/$;!$/ 9-$$/;;%>/.;/ ! 7%3-$! !. !."$/::- 8%33% H%:/ 10 %33% H%:/ 16 !.-3;$/ -$8!.% 9-$$/;;%>/.;/ ! 7%3-$! +-:;! ./33% 456 :/9-.8- !3 9$!D ;/$!- ',$ %-% &% / !.?./ "/./$% !3 ?3/ !"#$%&$'%()*+).% 92/ 9-:;!;#!:9/ !3 ?3/ 8! !.!,!%3!,,%,!-./ 8/33% >/>-$!%' !" !# !$ !% !. T!:;!." &'J) 1-.7/$:!-./ / -$8!.%>/.;- H!;$/7/$:/ 8/! 7%3-$!. !" # $%& ' ( $ "!)*+ ,, -#* ,./ 0# / /,# 1%23 ' 23 4 2/,.5, 6 1 *7#*876#8- 2 1%229 # ( :$ ; <,# 2$ (9 =>-= <,# 2$ ( ?,.5 6 29 =*+ 9 =*+ 9 @ "#!"+#*! # ABC0#!*# A!""=88BC=*8= D 0=" 0!8=" = =88)B"= >B EEF # ABC0#!*# @ *!* +=G!*! =--="= +#-0!-8# #* !"+#*= 8=C0!"B>= D @ CB A!* >= 0!-#H#!*# B I 6#8 "!G=-A#B8# I < $ 6#8"=G!"+=" ,< 29. . #. T!:;!." &'V) W:/>+!- 8/3 ?3/ '9-/ 8! !.!,!%3!,,%,!-./ 8/33% >/>-$!%. 9 #*#H#B>#HHBH#!*= +=>>B "BC 0=" #> 8=-86=*AJ 9 #>= K=*="B8! B)8!CB8#ABC=*8= #* CB8>B6. &J. . .