Ersoy O.K. Diffraction, Fourier optics, and imaging (Wiley, 2006)(ISBN 0471238163)(427s) PEo

388 APPENDIX B: LINEAR VECTOR SPACES

Cn and Rn are the n-dimensional vector spaces over C and R, respectively. The

elements of Cn and Rn can be expressed as n-tuples.	u ¼ ½un& for
‘2 denotes the vector space over C of all complex sequences
n ¼ 1; 2 . . . 1 which satisfy
X
1	ðB:3-5Þ
junj2 < 1
n¼1

with componentwise addition and scalar multiplication, and with inner product given by

X1

ð	u; v	Þ ¼	u	v	ð	B:3-6	Þ
			n	n

n¼1

where v ¼ ½vn&. Componentwise addition means the following: if w ¼ u þ v, then

wn ¼ un þ vn for all n

ðB:3-7Þ

Scalar multiplication means the following: if w ¼ lu, l a scalar, then

wn ¼ lun for all n

ðB:3-8Þ

L2ða; bÞ denotes the vector space of continuous functions over C[a,b] (complex values in the interval from a to b) with the inner product

b
ðu; vÞ ¼ ða uðtÞv ðtÞdt	ðB:3-9Þ

Angle

The angle y between two vectors x and y is defined by

	cos	y ¼	ðu; vÞ	ð	B:3-10	Þ
			jujjvj

y also shows the similarity between u and v. y equal to 0 shows that u and v are the same. y equal to p=2 shows that u and v are orthogonal.

Cauchy–Schwarz Inequality

The inner product of two vectors u and v satisfy

jðu; vÞj jujjvj

ðB:3-11Þ

with equality iff x and y are linearly dependent (x ¼ ay, a a scalar).

HILBERT SPACES	389
Triangle Inequality
The vectors u and v also satisfy
ju þ vj juj þ jvj	ðB:3-12Þ
The triangle inequality is also often called Scwarz inequality.

Orthogonality

Let U ¼ ½u0; u1; . . . ; uN 1& be a set (sequence) of vectors in an inner-product space S. U is an orthogonal set if ðuk; u‘Þ ¼ 0 for k ¼6 ‘. U is orthonormal if

ðuk; u‘Þ ¼ dk‘.

EXAMPLE B.5 Let the inner-product space be L2ð0; 1Þ. In this space, the functions

ukðtÞ ¼ cosð2pktÞ

form an orthogonal sequence.

B.4 HILBERT SPACES

The theory of Hilbert spaces is the most useful and well-developed generalization of the theory of finite-dimensional inner-product vector spaces to include infinitedimensional inner-product vector spaces. In order to be able to discuss Hilbert spaces, the concept of completeness is needed.

Consider a metric space M with the metric d. A sequence [uk] in M is a Cauchy sequence if, for every e > 0 there exists an integer k0 such that dðuk; x‘Þ < e for k; ‘ > k0. M is a complete metric space if every Cauchy sequence in M converges to a limit in M. An example of a Cauchy sequence is the Nth partial sum in a Fourier series expansion (see Example B.5 below).

A Hilbert space is an inner-product space which is a complete metric space. For example, Cn, Rn are Hilbert spaces since they are complete.

Inner-product spaces without the requirement of completeness are sometimes called pre-Hilbert spaces.

EXAMPLE B.5 Consider a periodic signal uðtÞ with period T. The basic period can be taken to be T=2 t T=2. The Fourier series representation of uðtÞ 2 L2ð T=2; T=2Þ is given by

pX
1	ðB:5-1Þ
uðtÞ ¼ 2=T ½U1½k&q½k& cosð2pkFstÞ þ U0½k& sinð2pkFstÞ&
k¼0

390

APPENDIX B: LINEAR VECTOR SPACES

where Fs ¼ 1=T, and

p

k ¼ 0

q

k

& ¼

1=

2

½

1

otherwise

countable but infinitely many.p

p

The basis functions are

2=T cosð2pkFstÞ

and

2=T sinð2pkFstÞ. They are

Since they form an orthonormal set of basis functions,

the series coefficients U1[k] and U0[k] are given by

U

1½

k

& ¼ ð

ð

Þ

p ð

Þ

ð

2

p

s

Þ

u t

;

2=Tq k

cos

kF t

¼

2=TqðkÞ

Tð=2

uðtÞ cosð2pkFstÞdt

p

T=2

U

0½

k

& ¼ ð

ð

Þ; p

ð

2

p

s

t

Þ

u t

2=T sin

kF

p Tð=2

¼2=T uðtÞ sinð2pkFstÞdt

T=2

The Hilbert space of interest in this case is periodic functions which are squareintegrable over one period. The vectors consist of all such periodic functions. The Cauchy sequences of interest are the Nth partial sums in Eq. (B.5-1). The limit of any such sequence is xðtÞ.

Appendix C

The Discrete-Time Fourier Transform,

The Discrete Fourier Transform

and The Fast Fourier Transform

C.1 THE DISCRETE-TIME FOURIER TRANSFORM

The discrete-time Fourier transform (DTFT) of a signal sequence u½n& is defined as

		1	X
			1
Uðf Þ ¼	F		u½n&e j 2pfnTs	ðC:1-1Þ
			n¼ 1

u½n& is usually equal to a sampled signal uðnTsÞ, Ts being the sampling interval, and

F¼ 1=Ts. Ts and F are usually assumed to be 1 in the literature. The inverse DTFT is given by

u½n& ¼	Fð=2	Uð f Þe j2pfnTs df	ðC:1-2Þ
	F=2

The existence conditions for the DTFT can be written as

X1

E1 ¼ jjujj1 ¼	ju½n&j < 1	ðC:1-3Þ
n¼ 1
If u½n& satisfies Eq. (C.1-3), it is also true that
E1 E2 ¼ jjujj2 ¼	1	ðC:1-4Þ
	ju½n&j2 < 1
	n¼ 1
	X

The properties of the DTFT are very similar to the properties of the Fourier transform discussed in Chapter 2.

Diffraction, Fourier Optics and Imaging, by Okan K. Ersoy

Copyright # 2007 John Wiley & Sons, Inc.

391

392

Signal

APPENDIX C: THE DISCRETE-TIME FOURIER TRANSFORM

1

0.8

0.6

0.4

0.2
0
	–20	–15	–10	–5	0	5	10	15	20
					Time
					(a)
	80
	70
	60
Transform	50
	40
	30
	20
	10
	0
	–10–10		–5		0		5		10
					Frequency
					(b)
	Figure C.1.		(a) Rectangular pulse signal for N ¼ 12, (b) the DTFT of the signal.

EXAMPLE C.1 Find the DTFT of

u½n& ¼

1 jnj N

0 otherwise

with Ts ¼ 1.

Solution: u½n& is shown in Figure C.1(a) for N ¼ 12.

THE RELATIONSHIP BETWEEN THE DISCRETE-TIME FOURIER TRANSFORM

393

We have

U

f

N

e j 2pfk

N

e j 2pf

ð

Þ ¼

¼

ð

k

k¼ N

Þ

k¼ N

X

X

Letting ‘ ¼ k þ N, this becomes

U

f

e j 2pfN

2N

e j 2pf

ð

Þ ¼

‘

k¼0

X

The summation on the right hand side is the sum of the first (2N þ 1) terms in a geometric series, which equals ð1 r2Nþ1Þ=ð1 rÞ, r being e j2pf . Thus,

Uðf Þ ¼ ej2pfN ½1 e j2pf ð2Nþ1Þ&

1 e j2pf

¼ sinð2pf ðN þ 1=2ÞÞ sinðpf Þ

Figure C.1(b) shows Uð f Þ for N ¼ 12. It is observed that Uð f Þ is similar to the sin function for small f, but becomes totally different as f approaches 1.

C.2 THE RELATIONSHIP BETWEEN THE DISCRETE-TIME FOURIER TRANSFORM AND THE FOURIER TRANSFORM

Consider the FT representation of an analog signal uðtÞ given by Eq. (1.2.2) as

	1	U0ð f Þe j2pftdf
uðtÞ ¼	ð		ðC:2-1Þ
	1

where U0ð f Þ is the FT of uðtÞ. The sequence u½n& is assumed to be obtained by sampling of uðtÞ at intervals of Ts such that u½n& ¼ uðnTsÞ. Comparing Eq. (C.2-1) to Eq. (C.1-2) shows that the DTFT Uð f Þ of u½n& is related to U0ð f Þ by

F=2		1
ð	Uð f Þe j2pfnTs df ¼	ð	U0ð f Þe j2pfnTs df	ðC:2-2Þ
F=2		1

By expressing the right-hand integral as a sum of integrals, each of width F, Eq. (C.2-2) can be written as

Fð=2		U0ð f Þe j2pfnTsdf ¼	Fð=2 "‘		1	U0ð f þ ‘FÞ#e j2pfnTs df	ðC:2-3Þ
	F=2			F=2	X
					¼ 1

394 APPENDIX C: THE DISCRETE-TIME FOURIER TRANSFORM

Equating the integrands gives

X1

Uð f Þ ¼	U0ð f þ ‘FÞ	ðC:2-4Þ
	‘¼ 1
If U0ð f Þ has bandwidth less than F, we see that
U0ð f Þ ¼ U0ð f Þ		ðC:2-5Þ

In many texts, Ts is chosen equal to 1 for convenience. This means uðtÞ is actually replaced by uðtTsÞ. uðtTsÞ has FT given by 1=TsU0ð f =TsÞ by Property 16 discussed in Section 1.9. Hence, Eq. (C.2-4) can be written as

			X
U f	Þ ¼	1	1	U0	f þ ‘		ð	C:2-6	Þ
ð		Ts ‘¼ 1			Ts

where Uðf Þ is the DTFT of the sampled signal obtained from uðtTsÞ at a sampling rate equal to 1.

Equations (C.2-4) and (C.2-6) show that the DTFT of a signal which is not bandlimited is an aliased version of the FT of the continous-time signal. The resulting errors tend to be significant as f approaches F since UðFÞ equals Uð0Þ, and Uð0Þ is usually large.

C.3 DISCRETE FOURIER TRANSFORM

The orthonormalized discrete Fourier transform (DFT) of a periodic sequence u½n& of length N is defined as

1		X
		N 1	ðC:3-1Þ
U½k& ¼ pN		u½n&e 2pjnk=N
		n¼0
The inverse DFT is given by		X
1		N 1	ðC:3-2Þ
u½n& ¼ pN		U½k&e2pjnk=N
		k¼0

The DFT defined above is orthonormal. The equations can be further simplified if normality is not required as follows:

XN 1

U½k& ¼		u½n&e j2pnk=N	ðC:3-3Þ
	n¼0
		X
	1	N 1
u½n& ¼	N	U½k&e j2pnk=N	ðC:3-4Þ
		k¼0

FAST FOURIER TRANSFORM

395

The 2-D DFT is obtained from the 1-D DFT by applying the 1-D DFT first to the rows of a signal matrix, and then to its columns or vice versa. If the 2-D periodic sequence is given by u½n1; n2&, 0 n1 < N1; 0 n2 < N2, its 2-D DFT can be written as

N1

1 N2

1

n1k

n2k2

u½n1; n2&e 2pjh

1

þ

i

U½k1; k2& ¼

N1

N2

ðC:3-5Þ

n1

¼0

n2¼0

X X

The inverse 2-D DFT is given by

u½n1; n2& ¼ N11N2

X X

U½k1; k2

&e2pjh N1

þ N2

i

ðC:3-6Þ

1 N2

1

N1

n1k1

n2k2

k1¼0 k2¼0

C.4 FAST FOURIER TRANSFORM

The fast Fourier transform (FFT) refers to a set of algorithms for the fast computation of the DFT. An FFT algorithm reduces the number of computations for an N point transform from Oð2N2Þ to Oð2N log NÞ.

FFT algorithms are based on a divide-and-conquer approach. They are most

efficient when the number N of data points is highly composite and can be written as N ¼ r1 r2 . . . rm. When y00 ¼ c0 þ c1; y01 ¼ c0 þ c2, N equals rm, and r is called the radix of the FFT algorithm. In this case, the FFT algorithm has a regular

structure.

The divide-and-conquer approach is commonly achieved by either decimation- in-time (DIT) or decimation-in-frequency (DIF). To illustrate these two concepts, consider N ¼ 2m. In the DIT case, we may divide the data x(n) into two sequences according to

u1 n ¼ u½2n&

n

¼

0; 1; . . . ;

N

1

ð

C:4-1

Þ

u2½n&½ ¼& u½2n þ 1&

2

frequency components are considered in two batches as U 2k

&

In the DIF case, the

N

½

and U½2k þ 1&, k ¼ 0;

1; . . . ; 2 1.

We describe the DIT algorithm further. Eq. (C.1-1) can be written as

U½k& ¼ U1½k& þ e j

2pk

U2½k&

ðC:4-2Þ

N

X

2pkm

N2 1

x½2m&e j

U1½k& ¼

N2

ðC:4-3Þ

m¼0

X

2pkm

N2 1

u½2m þ 1&e j

U2½k& ¼

N2

ðC:4-4Þ

m¼0

396	APPENDIX C: THE DISCRETE-TIME FOURIER TRANSFORM

where N2 equals N/2. It is observed that U1½k& and U2½k& are computed by DFTs of size N/2 with the even and odd-numbered points of the original signal.

The procedure described above is continued iteratively until reaching size 2 DFT, which consists of adding and subtracting two points.

The radix-2 decimation-in-frequency algorithm can be similarly developed. However, its implementation turns out to me more complex.

The 2-D FFT is obtained from the 1-D FFT by applying the 1-D FFT first to the rows of a signal matrix, and then to its columns or vice versa.

References

Asakura, K. and T. Nagashima., ‘‘Reconstruction from computer-generated holograms displayed by a line printer,’’ Optics Communications 17, 273–276, 1976.

Besag, J. E. ‘‘Spatial Interaction and the Statistical Analysis of Lattice Systems,’’ Journal of Royal Statistical Society: Series B 36, 2, 192–236, May 1974.

Bennett, J. R., I. G. Cumming and R. A. Deane, ‘‘The Digital Processing of SEASAT Synthetic Aperture Radar Data,’’ Proceedings of the IEEE International Radar Conference, 168–174, Virginia, 1980.

Born, M. and E. Wolf, Principles of Optics, Pergamon Press, New York, 1969.

Bowden, M., L. Thompson, C. Wilson, eds., Introduction to Microlithography, American Chemical Soc., ISBN 0-8412-2848-5, 1983.

Boyer, A. L., ‘‘Formation of Images Using 5Mhz Ultrasound and a Computer,’’ IBM Publication 320.2403, May 19, 1971.

Boyer, A. L., P. M. Hirsch, J. A. Jordan, Jr., L. B. Lesem, D. L. Van Rooy, ‘‘Reconstruction of Ultrasonic Images by Backward Propagation,’’ IBM Technical Report, No. 320.2396, IBM Scientific Center, Houston, Texas, July 1970.

Brackett, C. A., A. S. Acampora, I. Sweitzcr. G. Tangonan. M. T. Smith, W. Lennon. K. C. Wang, and R. H. Hobbs. ‘‘A scalable multiwavelength multihop optical network: A proposal for research on all-optical networks.’’ J. Lightwave Technol., vol. II. pp. 736–753, May/June 1993.

Brackett, C. A., ‘‘Dense wavelength division multiplexing networks: Principles and applications.’’ IEEE J. Select. Areas Commun., Vol. 8, pp. 948–964. 1990.

Brackett, C. A., A. S. Acampora, I. Sweitzcr. G. Tangonan. M. T. Smith, W. Lennon. K. C. Wang, and R. H. Hobbs. ‘‘A Scalable Multiwavelength Multihop Optical Network: A Proposal for Research on All-Optical Networks.’’ J. Lightwave Technol., vol. II. pp. 736–753, May/June 1993.

Brigham, E. O., The Fast Fourier Transform, Prentice Hall, Englewood, CA, 1974.

Brown, B.R. and A.W. Lohmann, ‘‘Complex Spatial Filtering with Binary Masks,’’ Applied Optics, 5, 967–969, June 1966.

Bubb, C. E., Okan K. Ersoy, ‘‘Algorithms for Holographic Reconstruction of Three-Dimen- sional Point Source Images,’’ Technical Report TR-ECE-06-06, Purdue University, March 2006.

Diffraction, Fourier Optics and Imaging, by Okan K. Ersoy

Copyright # 2007 John Wiley & Sons, Inc.

397