Bit and digit reversal methods

Details Bit and digit reversal methods Bit and digit reversal methods

1999-02-04

2002-02-26

Mai, Tan V. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06351758

ABSTRACT:

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to methods for recordering data and more particularly to bit and digit reversal methods.
BACKGROUND OF THE INVENTION
Bit-reverse and digit-reverse routines are routines in which data is reordered based upon its index value from 0 to N-1, where N is the number of points to be bit/digit-reversed.
Discrete transforms are the main users of methods for bit-reverse and digit-reverse. Discrete transforms take discrete inputs in one domain and convert them to discrete inputs of another. For example, a fast fourier transform (FFT) takes a discrete time domain input and transforms it into the discrete frequency domain output (i.e. x(t)>→X(j&ohgr;t)). Many discrete transforms such as the FFT, discrete cosine transform (DCT), inverse DCT (IDCT), and discrete sine transform (DST), etc. are executed in-place, i.e., use the same memory locations for both the input and output. This is usually done to reduce both data size and complexity. To take full advantage of in-place methods there remains a need for bit/digit-reversing methods.
For example, if the in-place method uses decimation-in-frequency (DIF) decomposition (see for reference Robert D. Strum and Donald E. Kirk,
First Principles of Discrete Systems and Digital Signal Processing
, Addison-Wesley Publishing Company, 1989, pp. 512-516, hereinafter referred to as “Strum and Kirk”) the input would be normal order but the output would be in bit/digit-reverse order as depicted in FIG.
1
. In order to view the resulting output in normal order the results need to be bit-reversed. Also note that if the in-place discrete transform uses a decimation-in-time (DIT) (see for reference Strum and Kirk, pp. 495-512) decomposition, the inputs require bit/digit-reversing while the outputs are in normal order.
TABLE 1.1
Memory Location vs. Output, in Hex Format
Memory Location
Bit Reverse Order Output
mem[0]
X[0]
mem[1]
X[4]
mem[2]
X[2]
mem[3]
X[6]
mem[4]
X[1]
mem[5]
X[5]
mem[6]
X[3]
mem[7]
X[7]
TABLE 1.2
Memory Location vs. Output, in Bit Format
Memory Location
Bit Reverse Order Output
mem[000]
X[000]
mem[001]
X[100]
mem[010]
X[010]
mem[011]
X[110]
mem[100]
X[001]
mem[101]
X[101]
mem[110]
X[011]
mem[111]
X[111]
There is a direct correlation between the normal order and bit-reversed order which can be shown using the example of an in-place discrete transform as shown in FIG.
1
. The in-place discrete transforms' input is a normal order 8-point array, x[N] and the output is a bit-reversed ordered 8-point array, X[N]. The order of storage of the input array x[N] is in normal order so that the array elements x[0]-x[7] line up with their respective memory locations 0-7 as indicated in FIG.
1
. The order of storage of the elements in the output array X[N] is in bit-reversed order when compared to their respective memory locations. This is illustrated better in Tables 1.1 and 1.2, shown hereinabove, where the memory locations and the bit-reversed order output are displayed in hex format and bit format, respectively. It can be seen in Table 1.2 that the bit notation of the memory locations and the bit notation of the bit-reversed ordered output are swapped. This is seen even better, as illustrated by the exemplary tree diagram shown in
FIG. 2
, when viewing the resulting normal order sorting, shown at
22
, and bit-reverse order sorting, shown at
24
, of a tree
20
.
Normal order sorting, as depicted at
22
in the exemplary tree diagram of
FIG. 2
, is sorted by looking at the most significant bit, n
2
in this example, and if the most significant bit is a zero then it is placed in the upper half of the tree
20
. If the most significant bit is a one then it is placed in the lower half of the tree
20
. Then the top half and bottom half subtrees are sorted using the same criteria on the second most significant bit, n
1
in this example. This process is repeated until the array is completely sorted.
Bit-reversed order sorting, as illustrated at
24
in the exemplary tree diagram of
FIG. 2
, is sorted by looking at the least significant bit, m
0
, and if the least significant bit is zero then it is placed in the upper half of the tree
20
. If the least significant bit is a one then it is placed in the lower half of the tree
20
. Then the top half and bottom half subtrees are sorted using the same criteria on the second least significant bit, m
1
. This process is repeated until the array is completely sorted. From this one can see that to go from bit-reversed order to normal order or visa-versa one simply needs to “reverse the bits” of the desired value to produce the appropriate offset from a base memory location (i.e. for desired value X[n
2
n
1
n
0
] of a bit reversed array use offset of [n
0
n
1
n
2
] from the beginning of the array.) Since the base memory location is zero in this example, the offset is the memory location.
To perform the bit/digit-reversal of an array of data in-place requires the swapping of the values whose indices are the bit/digit-reversal of one another. When traversing an array during a bit/digit-reversal routine the values are not swapped twice (i.e. if memory location [001] is swapped with [100] then do not swap [100] with [001]) otherwise they are placed back in their original order. One way to avoid this is to set i to the bit-reverse of j and then only swap [i] with [j] if i<j; this ensures that a double swapping error does not occur.
Digit-reversal is similar to bit-reversal; actually, bit-reversal is the single digit case of digit-reversal. Digit reversal reverses digits instead of bits. For example, a radix-4 FFT produces an output whose results are in 2-digit digit-reverse order. To perform the needed 2-digit digit-reverse ordering, the two least significant bits are swapped with the two most significant bits, then the second pair of least significant bits are swapped with the second pair of most significant bits, and so on. An exemplary tree diagram of 2-digit digit-reverse order sorting is depicted in
FIG. 3
for a 16-point 2-digit digit-reversed order output.
It would seem easy to generate a quick routine to perform an in-place bit or digit-reverse routine. All one has to do is swap some bits or digits to produce a bit/digit-reversed order to be used as offsets from a base address and make sure that nothing is double swapped. This method produces satisfactory results for a small number of points, but to perform a bit-reverse on 16K (16×1024) points, for example, which is (2
14
), a total of 14 bits need to be manipulated, thus requiring that 7 bit pairs be swapped. Furthermore, this routine would require a central processing unit (“CPU”) cycle count on the order of Nlog
2
N cycles to complete, which is relatively slow.
Thus, what is needed is an fast, simple method to perform in-place bit and digit reversal.
SUMMARY OF THE INVENTION
The present invention is a method of performing bit reversal which comprising the steps of identifying number of points in an array to be bit-reversed and performing bit reversal using a common subtree lookup table accordingly.
In another aspect of the present invention, a method of performing digit reversal is provided which includes the steps of identifying the number of points in

Affiliated with

Also associated with

Rating

Bit and digit reversal methods does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Bit and digit reversal methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bit and digit reversal methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2971115