Bit Reversed Addressing

Bit-reversed addressing is a special feature provided in the dsPIC® architecture to support efficient implementation of FFT algorithms. Given the address of a particular element in the array, the dsPIC hardware automatically computes the address of the next element in the bit-reversed sequence. Since FFT is typically performed on 16-bit fractional data, bit-reversed addressing is only supported for word mode operations. Also, bit-reversed addressing is only supported for write operations using indirect addressing with pre-increment or post-increment.

A Radix-2 FFT algorithm implicitly rearranges the data array being processed. Therefore, bit-reversed reordering of data is typically done either at the beginning or at the end of a Radix-2 FFT algorithm, so that in the end we obtain the data arranged in sequential order. Bit-reversed reordering can be performed by copying data words from a sequentially addressed array into a bit-reverse addressed array, as illustrated in the figure below. The DSP Library from Microchip contains easy-to-use and optimized functions for reordering FFT data using bit-reversed addressing. As can be seen from the figure, by reading the binary representation of each sequential array index in reverse order, one can determine the corresponding bit-reversed array index.

  • Used for calculating the ‘butterflies’ in the DFT algorithm
  • Address bit reversal is performed in hardware
  • Configuration controlled by MODCON and XBREV registers
  • Similar to modulo addressing but modifies the address bits
BitReversed.png

The XBREV register, as well as certain bits from the MODCON register, are used to configure a buffer for bit-reversed addressing. The BWM bits in MODCON are used to select the W register which is to be used as a pointer to the bit-reverse addressed buffer. Bit-reversed addressing is not supported for W15 because W15 is used as Stack Pointer; therefore, selecting W15 in the BWM field would effectively disable bit-reversed addressing.

MODCON: Modulo and Bit-Reversed Addressing Control Register

R/W-0 R/W-0 U-0 U-0 R/W-0 R/W-0 R/W-0 R/W-0
XMODEN YMODEN BWM3 BWM2 BWM1 BWM0
bit 15 bit 8

R/W-0 R/W-0 R/W-0 R/W-0 R/W-0 R/W-0 R/W-0 R/W-0
YWM3 YWM2 YWM1 YWM0 XWM3 XWM2 XWM1 XWM0
bit 7 bit 0

bit 15

XMODEN: X AGU Modulo Addressing Enable bit

1 = X AGU modulo addressing enabled
0 = X AGU modulo addressing disabled

bit 14

YMODEN: Y AGU Modulo Addressing Enable bit

1 = Y AGU modulo addressing enabled
0 = Y AGU modulo addressing disabled

bit 13-12

Unimplemented: Read as '0

bit 11-8

BWM<3:0>: X AGU Register Select for Bit-Reversed Addressing bits

1111 = Bit-reversed addressing disabled
1110 = W14 selected for bit-reversed addressing
1101 = W13 selected for bit-reversed addressing
.
.
0000 = W0 selected for bit-reversed addressing

bit 7-4

YWM<3:0>: Y AGU W Register Select for Modulo Addressing bits

1111 = Modulo addressing disabled
1110 = W10 selected for modulo addressing
1101 = W11 selected for modulo addressing

bit 3-0

XWM<3:0>: X AGU W Register Select for Modulo Addressing bits

1111 = Modulo addressing disabled
1110 = W14 selected for modulo addressing
.
.
0000 = W0 selected for modulo addressing

The BREN bit in XBREV is used to enable bit-reversed addressing for the selected register. The XB field in XBREV is initialized with the bit-reversed address modifier which is then used by the device to calculate the addresses of successive elements in the bit-reversed sequence. The dsPIC hardware automatically scales the assigned XB value by 2, to obtain the actual bit-reversed modifier. As can be inferred, the value of XB is a constant for a given buffer size. Refer to the Family Reference Manual for a table of typical XB values for various buffer sizes.

XBREV: X Write AGU Bit-Reversal Addressing Control Register

R/W-0 R/W-0 R/W-0 R/W-0 R/W-0 R/W-0 R/W-0 R/W-0
BREN XB14 XB13 XB12 XB11 XB10 XB9 XB8
bit 15 bit 8

R/W-0 R/W-0 R/W-0 R/W-0 R/W-0 R/W-0 R/W-0 R/W-0
XB7 XB6 XB5 XB4 XB3 XB2 XB1 XB0
bit 8 bit 0

bit 15

BREN: Bit-Reversed Addressing (X AGU) Enable bit

1 = Bit-reversed addressing enabled
0 = Bit-reversed addressing disabled

bit 14-0

XB<14:0>: X AGU Bit-Reversed Modifier bits

0x4000 = 32768 word buffer
0x2000 = 16384 word buffer
0x1000 = 8192 word buffer
0x0800 = 4096 word buffer
0x0400 = 2048 word buffer
0x0200 = 1024 word buffer
0x0100 = 512 word buffer
0x0080 = 256 word buffer
0x0040 = 128 word buffer
0x0020 = 64 word buffer
0x0010 = 32 word buffer
0x0008 = 16 word buffer
0x0004 = 8 word buffer
0x0002 = 4 word buffer
0x0001 = 2 word buffer

Example

This example shows how successive bit-reversed addresses are generated by the hardware, from the current bit-reversed address pointer value and the specified bit-reversed address modifier. The sequential (input) buffer in the example can be reordered, by reading the input buffer elements in sequential order and writing them to the output buffer using bit-reversed addressing. This reordering can also be done ‘in-place’, i.e. the same buffer is both read in sequential order by one W register and written in bit-reversed order by another W register. This helps to conserve RAM space.

ModuloAddressingExample2.png
© 2016 Microchip Technology, Inc.
Information contained on this site regarding device applications and the like is provided only for your convenience and may be superseded by updates. It is your responsibility to ensure that your application meets with your specifications. MICROCHIP MAKES NO REPRESENTATIONS OR WARRANTIES OF ANY KIND WHETHER EXPRESS OR IMPLIED, WRITTEN OR ORAL, STATUTORY OR OTHERWISE, RELATED TO THE INFORMATION, INCLUDING BUT NOT LIMITED TO ITS CONDITION, QUALITY, PERFORMANCE, MERCHANTABILITY OR FITNESS FOR PURPOSE. Microchip disclaims all liability arising from this information and its use. Use of Microchip devices in life support and/or safety applications is entirely at the buyer's risk, and the buyer agrees to defend, indemnify and hold harmless Microchip from any and all damages, claims, suits, or expenses resulting from such use. No licenses are conveyed, implicitly or otherwise, under any Microchip intellectual property rights.