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

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

© 1984-2012- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS