Processing for compression - The MPEG - page 79

Figure 3.39: The input waveform is multiplied by the target frequency and the result is averaged or integrated. In
(a) the target frequency is present and a large integral results. With another input frequency the integral is zero as
in (b). The correct frequency will also result in a zero integral shown in (c) if it is at 90° to the phase of the search
frequency. This is overcome by making two searches in quadrature.
Figure 3.39 (c) shows that the target frequency will not be detected if it is phase shifted 90° as the product of
quadrature waveforms is always zero. Thus the discrete Fourier transform must make a further search for the
target frequency using a cosine basis function. It follows from the arguments above that the relative proportions of
the sine and cosine integrals reveals the phase of the input component. Thus each discrete frequency in the
spectrum must be the result of a pair of quadrature searches.
Searching for one frequency at a time as above will result in a DFT, but only after considerable computation.
However, a lot of the calculations are repeated many times over in different searches. The fast Fourier transform
gives the same result with less computation by logically gathering together all the places where the same
calculation is needed and making the calculation once.
The amount of computation can be reduced by performing the sine and cosine component searches together.
Another saving is obtained by noting that every 180° the sine and cosine have the same magnitude but are simply
inverted in sign. Instead of performing four multiplications on two samples 180° apart and adding the pairs of
products it is more economical to subtract the sample values and multiply twice, once by a sine value and once by
a cosine value.
The first coefficient is the arithmetic mean which is the sum of all the sample values in the block divided by the
number of samples. Figure 3.40 shows how the search for the lowest frequency in a block is performed. Pairs of
samples are subtracted as shown, and each difference is then multiplied by the sine and the cosine of the search
frequency. The process shifts one sample period, and a new sample pair is subtracted and multiplied by new sine
and cosine factors. This is repeated until all the sample pairs have been multiplied. The sine and cosine products
are then added to give the value of the sine and cosine coefficients respectively.