Page 1 567 CHAPTER 31 Re X [ k ] ' 2 N j N & 1 n ' 0 x [ n ] cos ( 2 B k n / N ) Im X [ k ] ' & 2 N j N & 1 n ' 0 x [ n ] sin ( 2 B k n / N ) EQUATION 31-1 The real DFT. This is the forward transform, calculating the frequency domain from the time domain. In spite of using the names: real part and imaginary part , these equations only involve ordinary numbers. The frequency index, k , runs from 0 to N /2. These are the same equations given in Eq. 8-4, except that the 2/ N term has been included in the forward transform. The Complex Fourier Transform Although complex numbers are fundamentally disconnected from our reality, they can be used to solve science and engineering problems in two ways. First, the parameters from a real world problem can be substituted into a complex form, as presented in the last chapter. The second method is much more elegant and powerful, a way of making the complex numbers mathematically equivalent to the physical problem. This approach leads to the complex Fourier transform , a more sophisticated version of the real Fourier transform discussed in Chapter 8. The complex Fourier transform is important in itself, but also as a stepping stone to more powerful complex techniques, such as the Laplace and z-transforms . These complex transforms are the foundation of theoretical DSP. The Real DFT All four members of the Fourier transform family (DFT, DTFT, Fourier Transform & Fourier Series) can be carried out with either real numbers or complex numbers. Since DSP is mainly concerned with the DFT, we will use it as an example. Before jumping into the complex math, let's review the real DFT with a special emphasis on things that are awkward with the mathematics. In Chapter 8 we defined the real version of the Discrete Fourier Transform according to the equations: In words, an N sample time domain signal, , is decomposed into a set x [ n ] of cosine waves, and sine waves, with frequencies given by the N / 2 % 1 N / 2 % 1 Page 2 567 CHAPTER 31 Re X [ k ] ' 2 N j N & 1 n ' 0 x [ n ] cos ( 2 B k n / N ) Im X [ k ] ' & 2 N j N & 1 n ' 0 x [ n ] sin ( 2 B k n / N ) EQUATION 31-1 The real DFT. This is the forward transform, calculating the frequency domain from the time domain. In spite of using the names: real part and imaginary part , these equations only involve ordinary numbers. The frequency index, k , runs from 0 to N /2. These are the same equations given in Eq. 8-4, except that the 2/ N term has been included in the forward transform. The Complex Fourier Transform Although complex numbers are fundamentally disconnected from our reality, they can be used to solve science and engineering problems in two ways. First, the parameters from a real world problem can be substituted into a complex form, as presented in the last chapter. The second method is much more elegant and powerful, a way of making the complex numbers mathematically equivalent to the physical problem. This approach leads to the complex Fourier transform , a more sophisticated version of the real Fourier transform discussed in Chapter 8. The complex Fourier transform is important in itself, but also as a stepping stone to more powerful complex techniques, such as the Laplace and z-transforms . These complex transforms are the foundation of theoretical DSP. The Real DFT All four members of the Fourier transform family (DFT, DTFT, Fourier Transform & Fourier Series) can be carried out with either real numbers or complex numbers. Since DSP is mainly concerned with the DFT, we will use it as an example. Before jumping into the complex math, let's review the real DFT with a special emphasis on things that are awkward with the mathematics. In Chapter 8 we defined the real version of the Discrete Fourier Transform according to the equations: In words, an N sample time domain signal, , is decomposed into a set x [ n ] of cosine waves, and sine waves, with frequencies given by the N / 2 % 1 N / 2 % 1 The Scientist and Engineer's Guide to Digital Signal Processing 568 index, k . The amplitudes of the cosine waves are contained in , while Re X [ k ] the amplitudes of the sine waves are contained in . These equations Im X [ k ] operate by correlating the respective cosine or sine wave with the time domain signal. In spite of using the names: real part and imaginary part , there are no complex numbers in these equations. There isn't a j anywhere in sight! We have also included the normalization factor, in these equations. 2 / N Remember, this can be placed in front of either the synthesis or analysis equation, or be handled as a separate step (as described by Eq. 8-3). These equations should be very familiar from previous chapters. If they aren't, go back and brush up on these concepts before continuing. If you don't understand the real DFT, you will never be able to understand the complex DFT. Even though the real DFT uses only real numbers, substitution allows the frequency domain to be represented using complex numbers. As suggested by the names of the arrays, becomes the real part of the complex Re X [ k ] frequency spectrum, and becomes the imaginary part. In other words, Im X [ k ] we place a j with each value in the imaginary part, and add the result to the real part. However, do not make the mistake of thinking that this is the "complex DFT." This is nothing more than the real DFT with complex substitution . While the real DFT is adequate for many applications in science and engineering, it is mathematically awkward in three respects. First, it can only take advantage of complex numbers through the use of substitution . This makes mathematicians uncomfortable; they want to say: "this equals that," not simply: "this represents that." For instance, imagine we are given the mathematical statement: A equals B . We immediately know countless consequences: , , , etc. Now suppose we are 5 A ' 5 B 1 % A ' 1 % B A / x ' B / x given the statement: A represents B . Without additional information, we know absolutely nothing! When things are equal, we have access to four-thousand years of mathematics. When things only represent each other, we must start from scratch with new definitions. For example, when sinusoids are represented by complex numbers, we allow addition and subtraction, but prohibit multiplication and division. The second thing handled poorly by the real Fourier transform is the negative frequency portion of the spectrum. As you recall from Chapter 10, sine and cosine waves can be described as having a positive frequency or a negative frequency. Since the two views are identical, the real Fourier transform ignores the negative frequencies. However, there are applications where the negative frequencies are important. This occurs when negative frequency components are forced to move into the positive frequency portion of the spectrum. The ghosts take human form, so to speak. For instance, this is what happens in aliasing, circular convolution, and amplitude modulation. Since the real Fourier transform doesn't use negative frequencies, its ability to deal with these situations is very limited. Our third complaint is the special handing of and , the Re X [ 0 ] Re X [ N / 2 ] first and last points in the frequency spectrum. Suppose we start with an N Page 3 567 CHAPTER 31 Re X [ k ] ' 2 N j N & 1 n ' 0 x [ n ] cos ( 2 B k n / N ) Im X [ k ] ' & 2 N j N & 1 n ' 0 x [ n ] sin ( 2 B k n / N ) EQUATION 31-1 The real DFT. This is the forward transform, calculating the frequency domain from the time domain. In spite of using the names: real part and imaginary part , these equations only involve ordinary numbers. The frequency index, k , runs from 0 to N /2. These are the same equations given in Eq. 8-4, except that the 2/ N term has been included in the forward transform. The Complex Fourier Transform Although complex numbers are fundamentally disconnected from our reality, they can be used to solve science and engineering problems in two ways. First, the parameters from a real world problem can be substituted into a complex form, as presented in the last chapter. The second method is much more elegant and powerful, a way of making the complex numbers mathematically equivalent to the physical problem. This approach leads to the complex Fourier transform , a more sophisticated version of the real Fourier transform discussed in Chapter 8. The complex Fourier transform is important in itself, but also as a stepping stone to more powerful complex techniques, such as the Laplace and z-transforms . These complex transforms are the foundation of theoretical DSP. The Real DFT All four members of the Fourier transform family (DFT, DTFT, Fourier Transform & Fourier Series) can be carried out with either real numbers or complex numbers. Since DSP is mainly concerned with the DFT, we will use it as an example. Before jumping into the complex math, let's review the real DFT with a special emphasis on things that are awkward with the mathematics. In Chapter 8 we defined the real version of the Discrete Fourier Transform according to the equations: In words, an N sample time domain signal, , is decomposed into a set x [ n ] of cosine waves, and sine waves, with frequencies given by the N / 2 % 1 N / 2 % 1 The Scientist and Engineer's Guide to Digital Signal Processing 568 index, k . The amplitudes of the cosine waves are contained in , while Re X [ k ] the amplitudes of the sine waves are contained in . These equations Im X [ k ] operate by correlating the respective cosine or sine wave with the time domain signal. In spite of using the names: real part and imaginary part , there are no complex numbers in these equations. There isn't a j anywhere in sight! We have also included the normalization factor, in these equations. 2 / N Remember, this can be placed in front of either the synthesis or analysis equation, or be handled as a separate step (as described by Eq. 8-3). These equations should be very familiar from previous chapters. If they aren't, go back and brush up on these concepts before continuing. If you don't understand the real DFT, you will never be able to understand the complex DFT. Even though the real DFT uses only real numbers, substitution allows the frequency domain to be represented using complex numbers. As suggested by the names of the arrays, becomes the real part of the complex Re X [ k ] frequency spectrum, and becomes the imaginary part. In other words, Im X [ k ] we place a j with each value in the imaginary part, and add the result to the real part. However, do not make the mistake of thinking that this is the "complex DFT." This is nothing more than the real DFT with complex substitution . While the real DFT is adequate for many applications in science and engineering, it is mathematically awkward in three respects. First, it can only take advantage of complex numbers through the use of substitution . This makes mathematicians uncomfortable; they want to say: "this equals that," not simply: "this represents that." For instance, imagine we are given the mathematical statement: A equals B . We immediately know countless consequences: , , , etc. Now suppose we are 5 A ' 5 B 1 % A ' 1 % B A / x ' B / x given the statement: A represents B . Without additional information, we know absolutely nothing! When things are equal, we have access to four-thousand years of mathematics. When things only represent each other, we must start from scratch with new definitions. For example, when sinusoids are represented by complex numbers, we allow addition and subtraction, but prohibit multiplication and division. The second thing handled poorly by the real Fourier transform is the negative frequency portion of the spectrum. As you recall from Chapter 10, sine and cosine waves can be described as having a positive frequency or a negative frequency. Since the two views are identical, the real Fourier transform ignores the negative frequencies. However, there are applications where the negative frequencies are important. This occurs when negative frequency components are forced to move into the positive frequency portion of the spectrum. The ghosts take human form, so to speak. For instance, this is what happens in aliasing, circular convolution, and amplitude modulation. Since the real Fourier transform doesn't use negative frequencies, its ability to deal with these situations is very limited. Our third complaint is the special handing of and , the Re X [ 0 ] Re X [ N / 2 ] first and last points in the frequency spectrum. Suppose we start with an N Chapter 31- The Complex Fourier Transform 569 EQUATION 31-2 Euler's relation. e j x ' cos ( x ) % j sin ( x ) EQUATION 31-3 Euler's relation for sine & cosine. sin ( x ) ' e j x & e & j x 2 j cos ( x ) ' e j x % e & j x 2 sin ( Tt ) ' 1 2 j e j ( &T ) t & 1 2 j e j T t EQUATION 31-4 Sinusoids as complex numbers. Using complex numbers, cosine and sine waves can be written as the sum of a positive and a negative frequency. cos ( Tt ) ' 1 2 e j ( &T ) t % 1 2 e j T t point signal, . Taking the DFT provides the frequency spectrum contained x [ n ] in and , where k runs from 0 to N /2. However, these are not Re X [ k ] Im X [ k ] the amplitudes needed to reconstruct the time domain waveform; samples and must first be divided by two. (See Eq. 8-3 to refresh Re X [ 0 ] Re X [ N / 2 ] your memory). This is easily carried out in computer programs, but inconvenient to deal with in equations. The complex Fourier transform is an elegant solution to these problems. It is natural for complex numbers and negative frequencies to go hand-in-hand. Let's see how it works. Mathematical Equivalence Our first step is to show how sine and cosine waves can be written in an equation with complex numbers. The key to this is Euler's relation, presented in the last chapter: At first glance, this doesn't appear to be much help; one complex expression is equal to another complex expression. Nevertheless, a little algebra can rearrange the relation into two other forms: This result is extremely important, we have developed a way of writing equations between complex numbers and ordinary sinusoids. Although Eq. 31- 3 is the standard form of the identity, it will be more useful for this discussion if we change a few terms around: Each expression is the sum of two exponentials: one containing a positive frequency ( T ), and the other containing a negative frequency (- T ). In other words, when sine and cosine waves are written as complex numbers, the Page 4 567 CHAPTER 31 Re X [ k ] ' 2 N j N & 1 n ' 0 x [ n ] cos ( 2 B k n / N ) Im X [ k ] ' & 2 N j N & 1 n ' 0 x [ n ] sin ( 2 B k n / N ) EQUATION 31-1 The real DFT. This is the forward transform, calculating the frequency domain from the time domain. In spite of using the names: real part and imaginary part , these equations only involve ordinary numbers. The frequency index, k , runs from 0 to N /2. These are the same equations given in Eq. 8-4, except that the 2/ N term has been included in the forward transform. The Complex Fourier Transform Although complex numbers are fundamentally disconnected from our reality, they can be used to solve science and engineering problems in two ways. First, the parameters from a real world problem can be substituted into a complex form, as presented in the last chapter. The second method is much more elegant and powerful, a way of making the complex numbers mathematically equivalent to the physical problem. This approach leads to the complex Fourier transform , a more sophisticated version of the real Fourier transform discussed in Chapter 8. The complex Fourier transform is important in itself, but also as a stepping stone to more powerful complex techniques, such as the Laplace and z-transforms . These complex transforms are the foundation of theoretical DSP. The Real DFT All four members of the Fourier transform family (DFT, DTFT, Fourier Transform & Fourier Series) can be carried out with either real numbers or complex numbers. Since DSP is mainly concerned with the DFT, we will use it as an example. Before jumping into the complex math, let's review the real DFT with a special emphasis on things that are awkward with the mathematics. In Chapter 8 we defined the real version of the Discrete Fourier Transform according to the equations: In words, an N sample time domain signal, , is decomposed into a set x [ n ] of cosine waves, and sine waves, with frequencies given by the N / 2 % 1 N / 2 % 1 The Scientist and Engineer's Guide to Digital Signal Processing 568 index, k . The amplitudes of the cosine waves are contained in , while Re X [ k ] the amplitudes of the sine waves are contained in . These equations Im X [ k ] operate by correlating the respective cosine or sine wave with the time domain signal. In spite of using the names: real part and imaginary part , there are no complex numbers in these equations. There isn't a j anywhere in sight! We have also included the normalization factor, in these equations. 2 / N Remember, this can be placed in front of either the synthesis or analysis equation, or be handled as a separate step (as described by Eq. 8-3). These equations should be very familiar from previous chapters. If they aren't, go back and brush up on these concepts before continuing. If you don't understand the real DFT, you will never be able to understand the complex DFT. Even though the real DFT uses only real numbers, substitution allows the frequency domain to be represented using complex numbers. As suggested by the names of the arrays, becomes the real part of the complex Re X [ k ] frequency spectrum, and becomes the imaginary part. In other words, Im X [ k ] we place a j with each value in the imaginary part, and add the result to the real part. However, do not make the mistake of thinking that this is the "complex DFT." This is nothing more than the real DFT with complex substitution . While the real DFT is adequate for many applications in science and engineering, it is mathematically awkward in three respects. First, it can only take advantage of complex numbers through the use of substitution . This makes mathematicians uncomfortable; they want to say: "this equals that," not simply: "this represents that." For instance, imagine we are given the mathematical statement: A equals B . We immediately know countless consequences: , , , etc. Now suppose we are 5 A ' 5 B 1 % A ' 1 % B A / x ' B / x given the statement: A represents B . Without additional information, we know absolutely nothing! When things are equal, we have access to four-thousand years of mathematics. When things only represent each other, we must start from scratch with new definitions. For example, when sinusoids are represented by complex numbers, we allow addition and subtraction, but prohibit multiplication and division. The second thing handled poorly by the real Fourier transform is the negative frequency portion of the spectrum. As you recall from Chapter 10, sine and cosine waves can be described as having a positive frequency or a negative frequency. Since the two views are identical, the real Fourier transform ignores the negative frequencies. However, there are applications where the negative frequencies are important. This occurs when negative frequency components are forced to move into the positive frequency portion of the spectrum. The ghosts take human form, so to speak. For instance, this is what happens in aliasing, circular convolution, and amplitude modulation. Since the real Fourier transform doesn't use negative frequencies, its ability to deal with these situations is very limited. Our third complaint is the special handing of and , the Re X [ 0 ] Re X [ N / 2 ] first and last points in the frequency spectrum. Suppose we start with an N Chapter 31- The Complex Fourier Transform 569 EQUATION 31-2 Euler's relation. e j x ' cos ( x ) % j sin ( x ) EQUATION 31-3 Euler's relation for sine & cosine. sin ( x ) ' e j x & e & j x 2 j cos ( x ) ' e j x % e & j x 2 sin ( Tt ) ' 1 2 j e j ( &T ) t & 1 2 j e j T t EQUATION 31-4 Sinusoids as complex numbers. Using complex numbers, cosine and sine waves can be written as the sum of a positive and a negative frequency. cos ( Tt ) ' 1 2 e j ( &T ) t % 1 2 e j T t point signal, . Taking the DFT provides the frequency spectrum contained x [ n ] in and , where k runs from 0 to N /2. However, these are not Re X [ k ] Im X [ k ] the amplitudes needed to reconstruct the time domain waveform; samples and must first be divided by two. (See Eq. 8-3 to refresh Re X [ 0 ] Re X [ N / 2 ] your memory). This is easily carried out in computer programs, but inconvenient to deal with in equations. The complex Fourier transform is an elegant solution to these problems. It is natural for complex numbers and negative frequencies to go hand-in-hand. Let's see how it works. Mathematical Equivalence Our first step is to show how sine and cosine waves can be written in an equation with complex numbers. The key to this is Euler's relation, presented in the last chapter: At first glance, this doesn't appear to be much help; one complex expression is equal to another complex expression. Nevertheless, a little algebra can rearrange the relation into two other forms: This result is extremely important, we have developed a way of writing equations between complex numbers and ordinary sinusoids. Although Eq. 31- 3 is the standard form of the identity, it will be more useful for this discussion if we change a few terms around: Each expression is the sum of two exponentials: one containing a positive frequency ( T ), and the other containing a negative frequency (- T ). In other words, when sine and cosine waves are written as complex numbers, the The Scientist and Engineer's Guide to Digital Signal Processing 570 EQUATION 31-5 The forward complex DFT. Both the time domain, , and the frequency x [ n ] domain, , are arrays of complex X [ k ] numbers, with k and n running from 0 to N -1. This equation is in polar form, the most common for DSP. X [ k ] ' 1 N j N & 1 n ' 0 x [ n ] e & j 2 B k n / N X [ k ] ' 1 N j N & 1 n ' 0 x [ n ] cos ( 2 B k n / N ) & j sin ( 2 B k n / N ) EQUATION 31-6 The forward complex DFT (rectangular form). negative portion of the frequency spectrum is automatically included. The positive and negative frequencies are treated with an equal status; it requires one-half of each to form a complete waveform. The Complex DFT The forward complex DFT, written in polar form, is given by: Alternatively, Euler's relation can be used to rewrite the forward transform in rectangular form: To start, compare this equation of the complex Fourier transform with the equation of the real Fourier transform , Eq. 31-1. At first glance, they appear to be identical, with only small amount of algebra being required to turn Eq. 31-6 into Eq. 31-1. However, this is very misleading; the differences between these two equations are very subtle and easy to overlook, but tremendously important. Let's go through the differences in detail. First, the real Fourier transform converts a real time domain signal, , into x [ n ] two real frequency domain signals, & . By using complex Re X [ k ] Im X [ k ] substitution, the frequency domain can be represented by a single complex array, . In the complex Fourier transform, both & are arrays X [ k ] x [ n ] X [ k ] of complex numbers. A practical note: Even though the time domain is complex, there is nothing that requires us to use the imaginary part. Suppose we want to process a real signal, such as a series of voltage measurements taken over time. This group of data becomes the real part of the time domain signal, while the imaginary part is composed of zeros. Second, the real Fourier transform only deals with positive frequencies. That is, the frequency domain index, k , only runs from 0 to N /2. In comparison, the complex Fourier transform includes both positive and negative frequencies. This means k runs from 0 to N -1. The frequencies between 0 and N /2 are positive, while the frequencies between N /2 and N -1 are negative. Remember, the frequency spectrum of a discrete signal is periodic, making the negative frequencies between N /2 and N -1 the same as Page 5 567 CHAPTER 31 Re X [ k ] ' 2 N j N & 1 n ' 0 x [ n ] cos ( 2 B k n / N ) Im X [ k ] ' & 2 N j N & 1 n ' 0 x [ n ] sin ( 2 B k n / N ) EQUATION 31-1 The real DFT. This is the forward transform, calculating the frequency domain from the time domain. In spite of using the names: real part and imaginary part , these equations only involve ordinary numbers. The frequency index, k , runs from 0 to N /2. These are the same equations given in Eq. 8-4, except that the 2/ N term has been included in the forward transform. The Complex Fourier Transform Although complex numbers are fundamentally disconnected from our reality, they can be used to solve science and engineering problems in two ways. First, the parameters from a real world problem can be substituted into a complex form, as presented in the last chapter. The second method is much more elegant and powerful, a way of making the complex numbers mathematically equivalent to the physical problem. This approach leads to the complex Fourier transform , a more sophisticated version of the real Fourier transform discussed in Chapter 8. The complex Fourier transform is important in itself, but also as a stepping stone to more powerful complex techniques, such as the Laplace and z-transforms . These complex transforms are the foundation of theoretical DSP. The Real DFT All four members of the Fourier transform family (DFT, DTFT, Fourier Transform & Fourier Series) can be carried out with either real numbers or complex numbers. Since DSP is mainly concerned with the DFT, we will use it as an example. Before jumping into the complex math, let's review the real DFT with a special emphasis on things that are awkward with the mathematics. In Chapter 8 we defined the real version of the Discrete Fourier Transform according to the equations: In words, an N sample time domain signal, , is decomposed into a set x [ n ] of cosine waves, and sine waves, with frequencies given by the N / 2 % 1 N / 2 % 1 The Scientist and Engineer's Guide to Digital Signal Processing 568 index, k . The amplitudes of the cosine waves are contained in , while Re X [ k ] the amplitudes of the sine waves are contained in . These equations Im X [ k ] operate by correlating the respective cosine or sine wave with the time domain signal. In spite of using the names: real part and imaginary part , there are no complex numbers in these equations. There isn't a j anywhere in sight! We have also included the normalization factor, in these equations. 2 / N Remember, this can be placed in front of either the synthesis or analysis equation, or be handled as a separate step (as described by Eq. 8-3). These equations should be very familiar from previous chapters. If they aren't, go back and brush up on these concepts before continuing. If you don't understand the real DFT, you will never be able to understand the complex DFT. Even though the real DFT uses only real numbers, substitution allows the frequency domain to be represented using complex numbers. As suggested by the names of the arrays, becomes the real part of the complex Re X [ k ] frequency spectrum, and becomes the imaginary part. In other words, Im X [ k ] we place a j with each value in the imaginary part, and add the result to the real part. However, do not make the mistake of thinking that this is the "complex DFT." This is nothing more than the real DFT with complex substitution . While the real DFT is adequate for many applications in science and engineering, it is mathematically awkward in three respects. First, it can only take advantage of complex numbers through the use of substitution . This makes mathematicians uncomfortable; they want to say: "this equals that," not simply: "this represents that." For instance, imagine we are given the mathematical statement: A equals B . We immediately know countless consequences: , , , etc. Now suppose we are 5 A ' 5 B 1 % A ' 1 % B A / x ' B / x given the statement: A represents B . Without additional information, we know absolutely nothing! When things are equal, we have access to four-thousand years of mathematics. When things only represent each other, we must start from scratch with new definitions. For example, when sinusoids are represented by complex numbers, we allow addition and subtraction, but prohibit multiplication and division. The second thing handled poorly by the real Fourier transform is the negative frequency portion of the spectrum. As you recall from Chapter 10, sine and cosine waves can be described as having a positive frequency or a negative frequency. Since the two views are identical, the real Fourier transform ignores the negative frequencies. However, there are applications where the negative frequencies are important. This occurs when negative frequency components are forced to move into the positive frequency portion of the spectrum. The ghosts take human form, so to speak. For instance, this is what happens in aliasing, circular convolution, and amplitude modulation. Since the real Fourier transform doesn't use negative frequencies, its ability to deal with these situations is very limited. Our third complaint is the special handing of and , the Re X [ 0 ] Re X [ N / 2 ] first and last points in the frequency spectrum. Suppose we start with an N Chapter 31- The Complex Fourier Transform 569 EQUATION 31-2 Euler's relation. e j x ' cos ( x ) % j sin ( x ) EQUATION 31-3 Euler's relation for sine & cosine. sin ( x ) ' e j x & e & j x 2 j cos ( x ) ' e j x % e & j x 2 sin ( Tt ) ' 1 2 j e j ( &T ) t & 1 2 j e j T t EQUATION 31-4 Sinusoids as complex numbers. Using complex numbers, cosine and sine waves can be written as the sum of a positive and a negative frequency. cos ( Tt ) ' 1 2 e j ( &T ) t % 1 2 e j T t point signal, . Taking the DFT provides the frequency spectrum contained x [ n ] in and , where k runs from 0 to N /2. However, these are not Re X [ k ] Im X [ k ] the amplitudes needed to reconstruct the time domain waveform; samples and must first be divided by two. (See Eq. 8-3 to refresh Re X [ 0 ] Re X [ N / 2 ] your memory). This is easily carried out in computer programs, but inconvenient to deal with in equations. The complex Fourier transform is an elegant solution to these problems. It is natural for complex numbers and negative frequencies to go hand-in-hand. Let's see how it works. Mathematical Equivalence Our first step is to show how sine and cosine waves can be written in an equation with complex numbers. The key to this is Euler's relation, presented in the last chapter: At first glance, this doesn't appear to be much help; one complex expression is equal to another complex expression. Nevertheless, a little algebra can rearrange the relation into two other forms: This result is extremely important, we have developed a way of writing equations between complex numbers and ordinary sinusoids. Although Eq. 31- 3 is the standard form of the identity, it will be more useful for this discussion if we change a few terms around: Each expression is the sum of two exponentials: one containing a positive frequency ( T ), and the other containing a negative frequency (- T ). In other words, when sine and cosine waves are written as complex numbers, the The Scientist and Engineer's Guide to Digital Signal Processing 570 EQUATION 31-5 The forward complex DFT. Both the time domain, , and the frequency x [ n ] domain, , are arrays of complex X [ k ] numbers, with k and n running from 0 to N -1. This equation is in polar form, the most common for DSP. X [ k ] ' 1 N j N & 1 n ' 0 x [ n ] e & j 2 B k n / N X [ k ] ' 1 N j N & 1 n ' 0 x [ n ] cos ( 2 B k n / N ) & j sin ( 2 B k n / N ) EQUATION 31-6 The forward complex DFT (rectangular form). negative portion of the frequency spectrum is automatically included. The positive and negative frequencies are treated with an equal status; it requires one-half of each to form a complete waveform. The Complex DFT The forward complex DFT, written in polar form, is given by: Alternatively, Euler's relation can be used to rewrite the forward transform in rectangular form: To start, compare this equation of the complex Fourier transform with the equation of the real Fourier transform , Eq. 31-1. At first glance, they appear to be identical, with only small amount of algebra being required to turn Eq. 31-6 into Eq. 31-1. However, this is very misleading; the differences between these two equations are very subtle and easy to overlook, but tremendously important. Let's go through the differences in detail. First, the real Fourier transform converts a real time domain signal, , into x [ n ] two real frequency domain signals, & . By using complex Re X [ k ] Im X [ k ] substitution, the frequency domain can be represented by a single complex array, . In the complex Fourier transform, both & are arrays X [ k ] x [ n ] X [ k ] of complex numbers. A practical note: Even though the time domain is complex, there is nothing that requires us to use the imaginary part. Suppose we want to process a real signal, such as a series of voltage measurements taken over time. This group of data becomes the real part of the time domain signal, while the imaginary part is composed of zeros. Second, the real Fourier transform only deals with positive frequencies. That is, the frequency domain index, k , only runs from 0 to N /2. In comparison, the complex Fourier transform includes both positive and negative frequencies. This means k runs from 0 to N -1. The frequencies between 0 and N /2 are positive, while the frequencies between N /2 and N -1 are negative. Remember, the frequency spectrum of a discrete signal is periodic, making the negative frequencies between N /2 and N -1 the same as Chapter 31- The Complex Fourier Transform 571 between - N /2 and 0. The samples at 0 and N /2 straddle the line between positive and negative. If you need to refresh your memory on this, look back at Chapters 10 and 12. Third, in the real Fourier transform with substitution, a j was added to the sine wave terms, allowing the frequency spectrum to be represented by complex numbers. To convert back to ordinary sine and cosine waves, we can simply drop the j . This is the sloppiness that comes when one thing only represents another thing. In comparison, the complex DFT, Eq. 31-5, is a formal mathematical equation with j being an integral part. In this view, we cannot arbitrary add or remove a j any more than we can add or remove any other variable in the equation. Forth, the real Fourier transform has a scaling factor of two in front, while the complex Fourier transform does not. Say we take the real DFT of a cosine wave with an amplitude of one . The spectral value corresponding to the cosine wave is also one . Now, let's repeat the process using the complex DFT. In this case, the cosine wave corresponds to two spectral values, a positive and a negative frequency. Both these frequencies have a value of ½. In other words, a positive frequency with an amplitude of ½, combines with a negative frequency with an amplitude of ½, producing a cosine wave with an amplitude of one . Fifth, the real Fourier transform requires special handling of two frequency domain samples: & , but the complex Fourier transform does Re X [ 0 ] Re X [ N / 2 ] not. Suppose we start with a time domain signal, and take the DFT to find the frequency domain signal. To reverse the process, we take the Inverse DFT of the frequency domain signal, reconstructing the original time domain signal. However, there is scaling required to make the reconstructed signal be identical to the original signal. For the complex Fourier transform, a factor of 1/ N must be introduced somewhere along the way. This can be tacked-on to the forward transform, the inverse transform, or kept as a separate step between the two. For the real Fourier transform, an additional factor of two is required (2/ N) , as described above. However, the real Fourier transform also requires an additional scaling step: and must be divided by two Re X [ 0 ] Re X [ N / 2 ] somewhere along the way. Put in other words, a scaling factor of 1/ N is used with these two samples, while 2/ N is used for the remainder of the spectrum. As previously stated, this awkward step is one of our complaints about the real Fourier transform. Why are the real and complex DFTs different in how these two points are handled? To answer this, remember that a cosine (or sine) wave in the time domain becomes split between a positive and a negative frequency in the complex DFT's spectrum. However, there are two exceptions to this, the spectral values at 0 and N /2. These correspond to zero frequency (DC) and the Nyquist frequency (one-half the sampling rate). Since these points straddle the positive and negative portions of the spectrum, they do not have a matching point. Because they are not combined with another value, they inherently have only one-half the contribution to the time domain as the other frequencies.Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!