Documentation

digitrevorder

Permute input into digit-reversed order

Syntax

y = digitrevorder(x,r)
[y,i] = digitrevorder(x,r)

Description

digitrevorder is useful for pre-ordering a vector of filter coefficients for use in frequency-domain filtering algorithms, in which the fft and ifft transforms are computed without digit-reversed ordering for improved run-time efficiency.

y = digitrevorder(x,r) returns the input data in digit-reversed order in vector or matrix y. The digit-reversal is computed using the number system base (radix base) r, which can be any integer from 2 to 36. The length of x must be an integer power of r. If x is a matrix, the digit reversal occurs on the first dimension of x with size greater than 1. y is the same size as x.

[y,i] = digitrevorder(x,r) returns the digit-reversed vector or matrix y and the digit-reversed indices i, such that y = x(i). Recall that MATLAB® matrices use 1-based indexing, so the first index of y will be 1, not 0.

The following table shows the numbers 0 through 15, the corresponding digits and the digit-reversed numbers using radix base-4. The corresponding radix base-2 bits and bit-reversed indices are also shown.

Linear Index

Base-4 Digits

Digit- Reversed

Digit- Reversed Index

Base-2 Bits

Base-2 Reversed (bitrevorder)

Bit- Reversed Index

0

00

00

0

0000

0000

0

1

01

10

4

0001

1000

8

2

02

20

8

0010

0100

4

3

03

30

12

0011

1100

12

4

10

01

1

0100

0010

2

5

11

11

5

0101

1010

10

6

12

21

9

0110

0110

6

7

13

31

13

0111

1110

14

8

20

02

2

1000

0001

1

9

21

12

6

1001

1001

9

10

22

22

10

1010

0101

5

11

23

32

14

1011

1101

13

12

30

03

3

1100

0011

3

13

31

13

7

1101

1011

11

14

32

23

11

1110

0111

7

15

33

33

15

1111

1111

15

Examples

collapse all

Obtain the digit-reversed, radix base-3 ordered output of a vector containing 9 values. Obtain the same result by converting to base 3 and reversing the digits.

x = (0:8)';

y = digitrevorder(x,3);

c1 = dec2base(x,3);
c2 = fliplr(c1);
c3 = base2dec(c2,3);

T = table(x,y,c1,c2,c3)
T=9×5 table
x    y    c1    c2    c3
_    _    __    __    __

0    0    00    00    0
1    3    01    10    3
2    6    02    20    6
3    1    10    01    1
4    4    11    11    4
5    7    12    21    7
6    2    20    02    2
7    5    21    12    5
8    8    22    22    8