Microprocessor 4. Philippe Darche

      Figure 1.22. Execution of an instruction in bit addressing

      1.2.4.4. MMR addressing

One possibility is to manipulate I/O registers as conventional addresses (MMR for Memory-Mapped Register, literally, registers projected into memory, cf. § V3-3.1.1 and V3-2.1.1.1) in reduced format (page zero addressing) with fast specialized access instructions. One example is the Digital Signal Processor (DSP), reference C5000 from Texas Instruments (TI).

      1.2.4.5. Addressing modes specific to the digital signal processor

      Other than indirect register addressing with post- or pre-increment/decrement, two other modes are particularly adapted to digital signal processing, which justifies their implementation in DSPs. This is circular addressing and (address) bit-reversed addressing.

      1.2.4.5.1. Circular addressing

      Digital signal processing consists of digitizing samples x_i (i ∈ [0, ∞]) of the signal that are stored in memory, then carrying out a mathematical processing such as filtering on them to then reconstruct the analog signal. To simplify the discourse, memorization of coefficients needed for the calculation is not attempted. The sample flow is of infinite length, and the calculation is only made on a limited number of consecutive samples on the sampled sequence. This set is called a “window”. Linear addressing of the buffer FIFO (First In, First Out) illustrated in Figure 1.23a is not well adapted as it is necessary to test whether the pointers have reached the end. Moreover, the size of the buffer is necessarily high. The circular buffer (ring or cyclic buffer, circular queue), that Figure 1.23b shows, is a much better solution as it makes it possible to decrease its size to that of the window of samples needed for the calculation.

      Figure 1.23. Window of five samples

Circular or modulo addressing makes it possible to implement a circular buffer in a Random Access Memory (RAM). As shown in Figure 1.24, it is necessary to have four pieces of information that are the size of the circular buffer L, the address of the base of buffer B, the index pointer of the buffer I and increment (relative integer) M. This addressing uses modular arithmetic where the extent of the values is finite to calculate the pointer addresses. The benefit of using it lies in the fact that a block of L contiguous memory words is addressed by a pointer that uses a modulo addressing L. This means that once a pointer arrives at the end of a buffer, it is reinitialized to point the other end (more precisely, modulo addressing is the capacity to memorize the buffer).

      Figure 1.24. Circular buffer

      This is conveyed in algorithmic form by:

      0 < |M| ≤ L

      I ← I + M

      if M > 0

      then

      1 if I ≥ B + L

      2 then I ← I - L; buffer overflow or overflow from above

      3 end_if

      otherwise

      1 if I < B

      2 then I ← I + L; buffer overflow or overflow from below

      3 end_if

      4 end_if

Management logic detects a buffer overflow when there is a wraparound. It then generates an interrupt request (see Chapter 5) to warn the handler. This automatic management avoids a costly rearrangement of data by shifting them (Figure 1.25(a)) and a permanent monitoring of the pointer value to know whether it has reached an end of the buffer in order to reinitialize it. It frees useful calculating power for processing. For example, as soon as the top of the buffer is reached, the following sample is stored at its start (Figure 1.25(b)).

      Figure 1.25. Comparison between linear and circular addressings (from Rao (2001))

      The use domain is digital signal filtering carried out by a DSP where digital values, the results of a quantification of an analog signal, are stored in a delay line that can be implemented with a circular buffer in place of carrying out costly temporal shifts. The DSP ADSP-210xx family from Analog Devices uses this mode. One example of use is implementation of a Finite Impulse Response (FIR) described in § V3-5.2.

      1.2.4.5.2. Reverse bit order addressing

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.

      1.2.4.5.3. Linear addressing

      The DSP56000 uses a – perhaps poorly named – address modifier.