Читать книгу Microprocessor 4 - Philippe Darche - Страница 34

Bit-reversed addressing makes it possible to manipulate materially the address without changing the source address. When the processor is set in this specific mode by the positioning of a flag (cf. § V3-3.1.5) in a control register, the address generator (AGU for Address Generation Unit, also called DAG for Data Address Generator or ACU for Address Computation Unit) generates bit-reversed addressing. This means that the LSbs (Least Significant bits) and MSb are exchanged, position 1 and m-2 bits are exchanged and so on (change from little- endian order to big-endian order or vice versa). This mode is used in implementation of the Fast Fourier Transform (FFT) algorithm (Cooley and Tukey 1965), an effective method for calculating a Discrete Fourier Transform (DFT), used for filtering or spectral analysis. Remember that the FFT makes it possible to change the time domain to the frequency domain and vice versa. The problem is that the result output order differs from that of the input or vice versa. This mode makes it possible to preserve the initial order of the data by choosing out-of-order input samples to keep the output order of the data results identical to that of the input. Figure 1.26 shows the details of the calculation of a DIT (Decimal-In-Time) FFT, which is characterized by the inversion placed at the start, compared to calculation of a DIF (Decimal-In-Frequency) FFT, where the inverter is at the end. Each node represents a complex addition (in an imaginary sense). Without going into detail, note the value of the sample indices before and after inverting the order of their binary digits. is the twiddle factor, also called a Fourier coefficient or an nth root of unity. The dsPIC^® microcontroller family from Microchip, DSP32xx from AT&T and DSPs from the SHARC^® (DSP-21xxx) family from Analog Devices with the instruction bitrev that reverse the content of a register are examples of components offering it. The mac instruction was introduced into DSPs for this type of calculation (cf. § 2.8.4.2).

Figure 1.26. Flow diagram of the algorithm of an 8-point FFT DIT in base 2

To carry out this inversion of the address bit order, Reverse-Carry Arithmetic (RCA) is used. The sub-set managing the address or AGU (cf. § V3-3.4.4) reverses the direction of the bits retained when an increment is added to the value of an address register. Two processors that implement it are DSP32xx from AT&T and DSP56000 (Motorola 1992). The AGU also implements linear and modulo arithmetic.