digitrevorder (Signal Processing Toolbox)

Permute input into digit-reversed order

Syntax

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

Description

digitrevorder is useful for preordering 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 uses 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
110
011
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

.

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	110	011	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

Obtain the digit-reversed, radix base-3 ordered output of a vector containing 9 values:

x=[0:8]';            % Create a column vector
[x,digitrevorder(x,3)]
ans =

     0     0
     1     3
     2     6
     3     1
     4     4
     5     7
     6     2
     7     5
     8     8

See Also

bitrevorder, fft, ifft

dftmtx diric