Discrete Fourier transform

Encyclopedia : D : DI : DIS : Discrete Fourier transform

---

Fourier transforms
Continuous Fourier transform
Fourier series
Discrete Fourier transform
Discrete-time Fourier transform
List of Fourier-related transforms>Related transforms [http://encycl.opentopia.com/ edit]

In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, to solve partial differential equations, and to perform other operations such as convolutions. The DFT can be computed efficiently in practice using a fast Fourier transform (FFT) algorithm.

The sequence of N complex numbers x₀, ..., x_N−1 are transformed into the sequence of N complex numbers X₀, ..., X_N−1 by the DFT according to the formula:

[X_k = \sum_^ x_n e^ k n} \quad \quad k = 0, \dots, N-1]

where e is the base of the natural logarithm, i is the imaginary unit ([i^2=-1]), and π is Pi. The transform is sometimes denoted by the symbol [\mathcal], as in [\mathbf = \mathcal(\mathbf)] or [\mathcal \mathbf].

The inverse discrete Fourier transform (IDFT) is given by

[x_n = \frac \sum_^ X_k e^ k n} \quad \quad n = 0,\dots,N-1.]

Note that the normalization factor multiplying the DFT and IDFT (here 1 and 1/N) and the signs of the exponents are merely conventions, and differ in some treatments. The only requirements of these conventions are that the DFT and IDFT have opposite-sign exponents and that the product of their normalization factors be 1/N. A normalization of [1/\sqrt] for both the DFT and IDFT makes the transforms unitary, which has some theoretical advantages, but it is often more practical in numerical computation to perform the scaling all at once as above (and a unit scaling can be convenient in other ways).

(The convention of a negative sign in the exponent is often convenient because it means that [X_k] is the amplitude of a "positive frequency" [2\pi k/N]. Equivalently, the DFT is often thought of as a matched filter: when looking for a frequency of +1, one correlates the incoming signal with a frequency of −1.)

In the following discussion the terms "sequence" and "vector" will be considered interchangeable.

Properties

Completeness

The discrete Fourier transform is an invertible, linear transformation

[\mathcal:\mathbf^N \to \mathbf^N]

with C denoting the set of complex numbers. In other words, for any N > 0, an N-dimensional complex vector has a DFT and an IDFT which are in turn N-dimensional complex vectors.

Orthogonality

The vectors exp(2πi kn/N) form an orthogonal basis over the set of N-dimensional complex vectors:

[\sum_^\left(e^ kn}\right)\left(e^ k'n}\right)=N~\delta_]

where δ_kn is the Kronecker delta.

The Plancherel theorem and Parseval's theorem

If X_k and Y_k are the DFTs of x_n and y_n respectively then we have the Plancherel theorem:

[\sum_^ x_n y^*_n = \frac \sum_^ X_k Y^*_k]

where the star denotes complex conjugation. Parseval's theorem is a special case of the Plancherel theorem and states:

[\sum_^ |x_n|^2 = \frac \sum_^ |X_k|^2.]

The shift theorem

Multiplying [x_n] by a linear phase [\exp(2\pi i n m/N)] for some integer [m] corresponds to a circular shift of the output [X_k]: [X_k] is replaced by [X_], where the subscript is interpreted modulo [N] (i.e. periodically). Similarly, a circular shift of the input [x_n] corresponds to multiplying the output [X_k] by a linear phase. Mathematically, if [\] represents the vector x then

if [\mathcal(\)_k=X_k]

then [\mathcal(\n m} \})_k=X_]

and [\mathcal(\\})_k=X_k e^k m}]

Periodicity

It is shown in the Discrete-time Fourier transform (DTFT) article that the Fourier transform of a discrete time sequence is periodic. A finite length sequence is just a special case. I.e., it is an infinite sequence of zeros containing a region (aka window) in which non-zero values may occur. So [X(\omega)\,], the DTFT of the finite sequence [x[n]\,], is periodic. Not surprisingly, the DFT is periodic; e.g. [X[k+N] = X[k]\,]. Less obvious, perhaps, is that the inverse DFT is also periodic; e.g., [x[n+N] = x[n]\,]. It is a periodically extended version of the finite sequence.

The DTFT of the periodically extended sequence is zero-valued except at the discrete set of frequencies sampled by the DFT. I.e., it is effectively identical to the DFT. The DTFT of the finite sequence has other non-zero values, but it is still identical to the DFT at the frequencies sampled by the DFT. So the approximation error of [X[k]\,], as an approximation to [X(\omega)\,], lies in the missing non-zero values, not in the [X[k]\,] coefficients. In terms of the inverse DFT, that approximation error becomes the periodic extension of the finite sequence.

• Commonly, [x[n]\,] is a modification of a longer, perhaps infinite, sequence, whose DTFT is only approximated by [X(\omega)\,]. In that case, of course, [X[k]\,] too is only an approximation to [samples of] the original DTFT.

• The shift theorem, above, is also an expression of the implicit periodicity of the inverse DFT, because it shows that the DFT amplitudes [|X[k]|\,] are unaffected by a circular (periodic) shift of the inputs, which is simply a choice of origin and therefore only affects the phase. Periodic boundary conditions play an important role in many applications of the DFT. When solving differential equations they allow periodic boundary conditions to be automatically satisfied, and thus can be a useful property. See also the applications section below.

Circular convolution theorem and cross-correlation theorem

The cyclic or circular convolution x*y of the two vectors x = x_k  and y = y_n  is the vector x*y with components

[(\mathbf)_n = \sum_^ x_m y_ \quad \quad n = 0,\dots,N-1]

where we continue y cyclically so that

[y_ = y_\quad\quad~~~~~~~~~~ m = 0, ..., N-1]

The discrete Fourier transform turns cyclic convolutions into component-wise multiplication. That is, if [z_n = (\mathbf)_n] then

[Z_k=X_k Y_k \quad \quad~~~~~~~~~~ k = 0,\dots,N-1]

where capital letters (X, Y, Z) represent the DFTs of sequences represented by small letters (x, y, z). Note that if a different normalization convention is adopted for the DFT (e.g., the unitary normalization), then there will in general be a constant factor multiplying the above relation.

The direct evaluation of the convolution summation, above, would require [O(N^2)] operations, but the DFT (via an FFT) provides an [O(N\log N)] method to compute the same thing. Conversely, convolutions can be used to efficiently compute DFTs via Rader's FFT algorithm and Bluestein's FFT algorithm.

See also: Convolution theorem

In an analogous manner, it can be shown that if [z_n] is the cross-correlation of [x_n] and [y_n]:

[z_n=(\mathbf)_n = \sum_^x_m^*\,y_]

where the sum is again cyclic in m, then the discrete Fourier transform of [z_n] is:

[Z_k = X_k^*\,Y_k]

where capital letters are again used to signify the discrete Fourier transform.

Relationship to trigonometric interpolation polynomials

The function

[p(t) = \frac + \frac e^ + \frac e^ + \cdots + \frac} e^]

whose coefficients f_k /N are given by the DFT of x_n, above, is called the trigonometric interpolation polynomial of degree N − 1. It is the unique function of this form that satisfies the property: p(2πn/N) = x_n for n = 0, ..., N − 1.

Because of aliasing, however, the form of the trigonometric interpolation polynomial is not unique, in that any of the frequencies can be shifted by any multiple of N while maintaining the property p(2πn/N) = x_n . In particular, the following form is often preferred:

[p(t) = \frac + \frac e^ + \cdots + \frac} \cos(Nt/2) + \frac} e^ + \cdots + \frac} e^]

for even [N] (where the Nyquist amplitude [f_] should be handled specially) or, for odd [N]:

[p(t) = \frac + \frac e^ + \cdots + \frac} e^ + \frac} e^ + \cdots + \frac} e^]

These latter two forms have the useful property that, if the [x_n] are all real numbers, then [p(t)] will be real for all [t] as well. They also use the smallest possible frequencies of the interpolating sinusoids (a balance of positive and negative frequencies instead of all positive frequencies), and consequently minimize the mean-square slope [\int |p'(t)|^2 dt] of the interpolated function.

The unitary DFT

Another way of looking at the DFT is to note that in the above discussion, the DFT can be expressed as a Vandermonde matrix:

[\mathbf =\begin \omega_N^ & \omega_N^ & \ldots & \omega_N^ \\ \omega_N^ & \omega_N^ & \ldots & \omega_N^ \\ \vdots & \vdots & \ddots & \vdots \\ \omega_N^ & \omega_N^ & \ldots & \omega_N^ \\\end]

where

[\omega_N = e^\,]

is a primitive Nth root of unity. The inverse transform is then given by the inverse of the above matrix:

[\mathbf^=\frac\mathbf^*]

With unitary normalization constants [1/\sqrt], the DFT becomes a unitary transformation, defined by a unitary matrix:

[\mathbf=\mathbf/\sqrt]

[\mathbf^=\mathbf^*]

[|\det(\mathbf)|=1]

where det()  is the determinant function. The determinant is the product of the eigenvalues, and therefore (see below) is always [\pm 1] or [\pm i]. In a real vector space, a unitary transformation can be thought of as simply a rigid rotation of the coordinate system, and all of the properties of a rigid rotation can be found in the unitary DFT.

The orthogonality of the DFT is now expressed as an orthonormality condition (which arises in many areas of mathematics as described in root of unity):

[\sum_^U_U_^*=\delta_]

If [\mathbf] is defined as the unitary DFT of the vector [\mathbf] then

[X_k=\sum_^ U_x_n]

and the Plancherel theorem is expressed as:

[\sum_^x_n y_n^* = \sum_^X_k Y_k^*]

If we view the DFT as just a coordinate transformation which simply specifies the components of a vector in a new coordinate system, then the above is just the statement that the dot product of two vectors is preserved under a unitary DFT transformation. For the special case [\mathbf = \mathbf], this implies that the length of a vector is preserved as well—this is just Parseval's theorem:

[\sum_^|x_n|^2 = \sum_^|X_k|^2]

Expressing the inverse DFT in terms of the DFT

A useful property of the DFT is that the inverse DFT can be easily expressed in terms of the (forward) DFT, via several well-known "tricks". (For example, in computations, it is often convenient to only implement a fast Fourier transform corresponding to one transform direction and then to get the other transform direction from the first.)

First, we can compute the inverse DFT by reversing the inputs:

[\mathcal^(\) = \mathcal(\\}) / N]

(As usual, the subscripts are interpreted modulo [N]; thus, for [n=0], we have [x_=x_0].)

Second, one can also conjugate the inputs and outputs:

[\mathcal^(\mathbf) = \mathcal(\mathbf^*)^* / N]

Third, a variant of this conjugation trick, which is sometimes preferable because it requires no modification of the data values, involves swapping real and imaginary parts (which can be done on a computer simply by modifying pointers). Define swap([x_n]) as [x_n] with its real and imaginary parts swapped—that is, if [x_n = a + b i] then swap([x_n]) is [b + a i]. Equivalently, swap([x_n]) equals [i x_n^*]. Then

[\mathcal^(\mathbf) = \textrm(\mathcal(\textrm(\mathbf))) / N]

That is, the inverse transform is the same as the forward transform with the real and imaginary parts swapped for both input and output, up to a normalization (Duhamel et al., 1988).

The conjugation trick can also be used to define a new transform, closely related to the DFT, that is involutary—that is, which is its own inverse. In particular, [T(\mathbf) = \mathcal(\mathbf^*) / \sqrt] is clearly its own inverse: [T(T(\mathbf)) = \mathbf]. A closely related involutary transformation (by a factor of (1+i)/√2) is [H(\mathbf) = \mathcal((1+i) \mathbf^*) / \sqrt], since the [(1+i)] factors in [H(H(\mathbf))] cancel the 2. For real inputs [\mathbf], the real part of [H(\mathbf)] is none other than the discrete Hartley transform, which is also involutary.

Eigenvalues and eigenvectors

The eigenvalues of the DFT matrix are simple and well-known, whereas the eigenvectors are complicated, not unique, and are the subject of ongoing research.

Consider the unitary form [\mathbf] defined above for the DFT of length [N], where [\mathbf_ = \omega_N^/\sqrt = \exp(-2\pi i mn/N)/\sqrt]. This matrix satisfies the equation:

[\mathbf^4 = 1.]

This can be seen from the inverse properties above: operating [\mathbf] twice gives the original data in reverse order, so operating [\mathbf] four times gives back the original data and is thus the identity matrix. This means that the eigenvalues [\lambda] satisfy a characteristic equation:

[\lambda^4 = 1.]

Therefore, the eigenvalues of [\mathbf] are the fourth roots of unity: [\lambda] is +1, −1, +i, or −i.

Since there are only four distinct eigenvalues for this [N\times N] matrix, they have some multiplicity. The multiplicity gives the number of linearly independent eigenvectors corresponding to each eigenvalue. (Note that there are N independent eigenvectors; the matrix is not defective.)

The problem of their multiplicity was solved by McClellan and Parks (1972), although it was later shown to have been equivalent to a problem solved by Gauss (Dickinson and Steiglitz, 1982). The multiplicity depends on the value of [N] modulo 4, and is given by the following table:

Multiplicities of the eigenvalues λ of the unitary DFT matrix U as a function of the transform size N (in terms of an integer m).

size N	λ = +1	λ = −1	λ = +i	λ = −i
4m	m + 1	m	m	m − 1
4m + 1	m + 1	m	m	m
4m + 2	m + 1	m + 1	m	m
4m + 3	m + 1	m + 1	m + 1	m

Unfortunately, no simple analytical formula for the eigenvectors is known. Moreover, the eigenvectors are not unique because any linear combination of eigenvectors for the same eigenvalue is also an eigenvector for that eigenvalue. Various researchers have proposed different choices of eigenvectors, selected to satisfy useful properties like orthogonality and to have "simple" forms (e.g., McClellan and Parks, 1972; Dickinson and Steiglitz, 1982; Grünbaum, 1982; Atakishiyev and Wolf, 1997; Hanna et al., 2004).

The choice of eigenvectors of the DFT matrix has become important in recent years in order to define a discrete analogue of the fractional Fourier transform—the DFT matrix can be taken to fractional powers by exponentiating the eigenvalues (e.g., Rubio and Santhanam, 2005). For the continuous Fourier transform, the natural orthogonal eigenfunctions are the Hermite functions, so various discrete analogues of these have been employed as the eigenvectors of the DFT, such as the Kravchuk polynomials (Atakishiyev and Wolf, 1997). The "best" choice of eigenvectors to define a fractional discrete Fourier transform remains an open question, however.

The real-input DFT

If [x_0, \ldots, x_] are real numbers, as they often are in practical applications, then the DFT obeys the symmetry:

[X_k = X_^* ,]

where the star denotes complex conjugation and the subscripts are interpreted modulo N.

Therefore, the DFT output for real inputs is half redundant, and one obtains the complete information by only looking at roughly half of the outputs [X_0, \ldots, X_]. In this case, the "DC" element [X_0] is purely real, and for even N the "Nyquist" element [X_] is also real, so there are exactly N non-redundant real numbers in the first half + Nyquist element of the complex output X.

Using Euler's formula, the interpolating trigonometric polynomial can then be interpreted as a sum of sine and cosine functions.

Generalized/shifted DFT

It is possible to shift the transform sampling in time and/or frequency domain by some real shifts a and b, respectively. This is sometimes known as a generalized DFT (or GDFT), also called the shifted DFT or offset DFT, and has analogous properties to the ordinary DFT:

[X_k = \sum_^ x_n e^ (k+b) (n+a)} \quad \quad k = 0, \dots, N-1]

Most often, shifts of [1/2] (half a sample) are used. While the ordinary DFT corresponds to a periodic signal in both time and frequency domains, [a=1/2] produces a signal that is anti-periodic in frequency domain ([X_ = - X_k]) and vice-versa for [b=1/2]. Thus, the specific case of [a = b = 1/2] is known as an odd-time odd-frequency discrete Fourier transform (or O² DFT). Such shifted transforms are most often used for symmetric data, to represent different boundary symmetries, and for real-symmetric data they correspond to different forms of the discrete cosine and sine transforms.

Another interesting choice is [a=b=-(N-1)/2], which is called the centered DFT (or CDFT). The centered DFT has the useful property that, when [N] is a multiple of four, all four of its eigenvalues (see above) have equal multiplicities (Rubio and Santhanam, 2005).

The discrete Fourier transform can be viewed as a special case of the z-transform, evaluated on the unit circle in the complex plane; more general z-transforms correspond to complex shifts a and b above.

Multidimensional DFT

The ordinary DFT computes the transform of a "one-dimensional" dataset: a sequence (or array) [x_n] that is a function of one discrete variable [n]. More generally, one can define the multidimensional DFT of a multidimensional array [x_] that is a function of [d] discrete variables [n_\ell = 0, 1, \cdots, N_\ell-1] for [\ell] in [1, 2, \cdots, d]:

[X_ = \sum_^ \left(\omega_^ \sum_^ \left( \omega_^ \cdots \sum_^ \omega_^\cdot x_\right) \right) \, , ]

where [\omega_ = \exp(-2\pi i/N_\ell)] as above and the [d] output indices run from [k_\ell = 0, 1, \cdots, N_\ell-1]. This is more compactly expressed in vector notation, where [\mathbf \equiv (n_1, n_2, \cdots, n_d)] and [\mathbf \equiv (k_1, k_2, \cdots, k_d)] are [d]-dimensional vectors of indices from 0 to [\mathbf - 1 \equiv (N_1 - 1, N_2 - 1, \cdots, N_d - 1)]:

[X_\mathbf = \sum_=0}^-1} e^ \cdot (\mathbf / \mathbf)} x_\mathbf \, ,]

where the division [\mathbf / \mathbf \equiv (n_1/N_1, \cdots, n_d/N_d)] is performed element-wise, and the sum denotes the set of nested summations above.

The inverse of the multi-dimensional DFT is, analogous to the one-dimensional case, given by:

[x_\mathbf = \frac^d N_\ell} \sum_=0}^-1} e^ \cdot (\mathbf / \mathbf)} X_\mathbf \, .]

The multidimensional DFT has a simple interpretation. Just as the one-dimensional DFT expresses the input [x_n] as a superposition of sinusoids, the multidimensional DFT expresses the input as a superposition of plane waves, or sinusoids oscillating along the direction [\mathbf / \mathbf] in space and having amplitude [X_\mathbf]. Such a decomposition is of great importance for everything from digital image processing ([d]=2) to solving partial differential equations in three dimensions ([d]=3) by breaking the solution up into plane waves.

Computationally, the multidimensional DFT is simply the composition of a sequence of one-dimensional DFTs along each dimension. For example, in the two-dimensional case [x_] one can first compute the [N_1] independent DFTs of the rows (i.e., along [n_2]) to form a new array [y_], and then compute the [N_2] independent DFTs of [y] along the columns (along [n_1]) to form the final result [X_]. Or, one can transform the columns and then the rows—the order is immaterial because the nested summations above commute.

Because of this, given a way to compute a one-dimensional DFT (e.g. an ordinary one-dimensional FFT algorithm), one immediately has a way to efficiently compute the multidimensional DFT. This is known as a row-column algorithm, although there are also intrinsically multidimensional FFT algorithms.

Applications

The DFT has seen wide usage across a large number of fields; we only sketch a few examples below (see also the references at the end). All applications of the DFT depend crucially on the availability of a fast algorithm to compute discrete Fourier transforms and their inverses, a fast Fourier transform.

Spectral analysis

When the DFT is used for spectral analysis, the [\\,] sequence usually represents a finite set of uniformly-spaced time-samples of some signal [x(t)\,], where t of course represents time. The conversion from continuous time to samples (discrete-time) changes the underlying Fourier transform of x(t) into a discrete-time Fourier transform (DTFT), which generally entails a type of distortion called aliasing. Choice of an appropriate sample-rate (see Nyquist frequency) is the key to minimizing that distortion. Similarly, the conversion from a very long (or infinite) sequence to a manageable size entails a type of distortion called leakage, which is manifested as a loss of detail (aka resolution) in the DTFT. Choice of an appropriate sub-sequence length is the primary key to minimizing that effect. When the available data (and time to process it) is more than the amount needed to attain the desired clarity, a standard technique is to perform multiple DFTs. If the desired result is a power spectrum, averaging the magnitude components of the multiple DFTs is often an effective use of the extra data. This technique is referred to as the Welch algorithm.

A final source of distortion (or perhaps illusion) is the DFT itself, because it is just a discrete sampling of the DTFT, which is a function of a continuous frequency domain. That can be mitigated by increasing the resolution of the DFT. That procedure is illustrated in the discrete-time Fourier transform article.

• The procedure is sometimes referred to as zero-padding, which is a particular implementation used in conjunction with the fast Fourier transform (FFT) algorithm. The inefficiency of performing multiplications and additions with zero-valued "samples" is more than offset by the inherent efficiency of the FFT.
• As already noted, leakage imposes a limit on the inherent resolution of the DTFT. So there is a practical limit to the benefit that can be obtained from a fine-grained DFT.

Data compression

The field of digital signal processing relies heavily on operations in the frequency domain (i.e. on the Fourier transform). For example, several lossy image and sound compression methods employ the discrete Fourier transform: the signal is cut into short segments, each is transformed, and then the Fourier coefficients of high frequencies, which are assumed to be unnoticeable, are discarded. The decompressor computes the inverse transform based on this reduced number of Fourier coefficients. (Compression applications often use a specialized form of the DFT, the discrete cosine transform or sometimes the modified discrete cosine transform).

Partial differential equations

Discrete Fourier transforms, especially in more than one dimension, are often used to solve partial differential equations, where again the DFT is used as an approximation for the Fourier series (which is recovered in the limit of infinite N). The reason is that it expands the signal in complex exponentials e^inx, which are eigenfunctions of differentiation: d/dx e^inx = in e^inx. Thus, in the Fourier representation, a linear differential equation with constant coefficients is transformed into an easily solvable algebraic equation. One then uses the inverse DFT to transform the result back into the ordinary spatial representation. Such an approach is called a spectral method.

Multiplication of large integers

The fastest known algorithms for the multiplication of large integers or polynomials are based on the discrete Fourier transform: the sequences of digits or coefficients are interpreted as vectors whose convolution needs to be computed; in order to do this, they are first Fourier-transformed, then multiplied component-wise, then transformed back.

Outline of DFT polynomial multiplication algorithm

Suppose we wish to compute the polynomial product c(x) = a(x) · b(x). The ordinary product expression for the coefficients of c involves a linear (acyclic) convolution, where indices do not "wrap around." This can be rewritten as a cyclic convolution by taking the coefficient vectors for a(x) and b(x) with constant term first, then appending zeros so that the resultant coefficient vectors a and b have dimension d > deg(a(x)) + deg(b(x)). Then,

[\mathbf = \mathbf * \mathbf]

Where c is the vector of coefficients for c(x), and the convolution operator [*\,] is defined so

[c_n = \sum_^a_m b_\ d} \qquad\qquad\qquad n=0,1,...,d-1]

But convolution becomes multiplication under the DFT:

[\mathcal(\mathbf) = \mathcal(\mathbf)\mathcal(\mathbf)]

Here the vector product is taken elementwise. Thus the coefficients of the product polynomial c(x) are just the terms 0, ..., deg(a(x)) + deg(b(x)) of the coefficient vector

[\mathbf = \mathcal^(\mathcal(\mathbf)\mathcal(\mathbf))]

With a Fast Fourier transform, the resulting algorithm takes O(N log N) arithmetic operations. Due to its simplicity and speed, the Cooley-Tukey FFT algorithm, which is limited to composite sizes, is often chosen for the transform operation. In this case, d should be chosen as the smallest integer greater than the sum of the input polynomial degrees that is factorizable into small prime factors (e.g. 2, 3, and 5, depending upon the FFT implementation).

Some discrete Fourier transform pairs

Some DFT pairs

[x_n\equiv\frac\sum_^X_k \cdot e^ ]	[X_k\equiv\sum_^x_n \cdot e^ ]	Note
[x_n \cdot e^ \,]	[X_\,]	Shift theorem
[x_\,]	[X_k \cdot e^ ]
[x_n \in \mathbf]	[X_k=X_^*\,]	Real DFT
[a^n\,]	[\frac }]
[\,]	[\left(1+e^ \right)^\,]

See also

Derivation of the discrete Fourier transform The DFT can be derived as the continuous Fourier transform of infinite periodic sequences of impulses.

References

• esp. section 30.2: The DFT and FFT, pp.830–838.

External Links

• [Mathematics of the Discrete Fourier Transform by Julius O. Smith III]

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Search Titles

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

?