Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-07-09
2004-09-07
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06789097
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to discrete transforms of data, and in particular to a real-time method for bit-reversal of large size data arrays.
BACKGROUND TO THE INVENTION
In information transfer systems, analog data received from a user are converted to an equivalent digital format represented by a succession of bits. Efficient digital data transmission and storage is often achieved using compression techniques. A common technique for compressing data includes converting digital data from a time domain format to a frequency domain format. Discrete transforms like the FFT (fast Fourier transform), DCT (discrete cosinus transform), IDCT (inverse discrete cosinus transform), DST (discrete sinus transform), Fast Walsh Transform (FWT), Fast Hadamard Transform (FHT), etc., take discrete inputs in one format and convert them to discrete outputs in another. For example, the FFT is typically used to transform digital data from the time domain to digital data format in the frequency domain.
Many discrete transforms are executed “in place” using the same memory locations for both the inputs and the outputs. This technique is used to reduce the memory needed for the execution of the transform and also to reduce the complexity of the transform algorithms. During certain steps in the FFT, and other discrete transform routines, a bit-reversed order representation of the data is produced, so that the data needs to be thereafter reversed to the normal order. Thus, the circuitry performing the discrete transform must include routines that perform complex operations such as shifting of data for bit-reversal, including transfer or moving. In digital telecommunications, bit-reversal routines are used for example for signal modulation/demodulation, signal features extraction, error detection and correction.
In general, a data terminal includes one or more Digital Signal Processors (DSP). A DSP is a special central processing unit (CPU) designed to manipulate data to perform a specific function on the input data. The DSP comprises a small internal memory for storing data and codes and also a number of internal registers for exchanging information with the external memory. DSPs generally operate in load-store mode, where the arithmetic and logic instructions use the internal registers. Data are retrieved (loaded) from the internal or external memory and loaded into the data registers using a LOAD instruction, and data are saved (stored) from the registers into the memory using a STORE instruction. Each load/store operation requires an address into the memory. These addresses are usually held in address registers. An address stored in a register is often referred to as a “pointer” because it points to a location in the memory, also referred as an index.
Bit-reverse and digit-reverse are routines in which the data is “re-ordered” by reversing the pointer value (the index) from 0 to (N−1), where “N” is the number of points to be digit/bit-reversed. The paper “Bit-Reverse and Digit Reverse: Linear-Time Small Look-up Table Implementation for the TMS320C6000”, by Chad Courtney, published May 1998, Texas Instruments Incorporated SPRA440, describes bit reversal and digit reversal routines which sort the indices of the addresses of the data in a memory using a sorting tree. The pointers are stored in an array of 2
N
registers of “N” bits. The pointers are sorted starting with the most significant bit (MSB) of the bit-reversed order and ending with the least significant bit (LSB) so that the sorting routine is repeated for (N−1) times. The size of the memory necessary for performing bit/digit reversal routine is denoted with “N” and includes besides the memory space occupied by the indices, the space occupied by a look-up table which occupies a multiple of “N” bytes.
As indicated above, the bit reversal operation is effected “in place” on the external memory, which stores the intermediate or final results of the respective discrete transform. In the case of a uni-processor platform, bit reversal is time consuming, due mainly to the load and store operations performed on each entry of the array. This is because in most cases, the size of the available internal memory is much smaller (2 to 100 times) than the size of the array to be reversed. In addition, the array needs to be randomly accessed, which involves use of large index tables. Furthermore, a large overhead compared to the available hardware is required to meet the real-time requirement when sorting large size data arrays.
Accordingly, there is a need for a real-time method for sorting large size data arrays using bit-reversal routines on uni-processor DSP platforms.
SUMMARY OF THE INVENTION
The present invention seeks to overcome the disadvantages of the prior art associated with real-time, bit-reversal of large size data arrays on uni-processor platforms.
According to one aspect of the invention, a method for bit reversal of large data array on a uni-processor platform is provided. In a first stage, the method comprises the steps of determining the ratio K between the size M×2
M
of the large data array stored in an external memory, and the size M×2
Q
of a small array, available on an internal memory, such that K+Q=M; performing an in-place bit reversal operation for K bits of the large data array on external memory. These steps are performed by a direct memory access controller (DMA). In a second stage, a central processing unit (CPU) performs a bit reversal operation of small array on internal memory.
According to another aspect of the invention, a digital signal processor (DSP) for bit-reversal of a large data array is provided. The DSP comprises a direct memory access (DMA) controller for in-place bit reversing a number of bits of the large size data array on an external memory and a central processing unit (CPU) for performing swapping of small size sub-arrays on internal memory.
Advantageously, the two-stage method according to the invention importantly reduces the real-time implementation for sorting large size data arrays on uni-processor DSP platforms, by extensively using the external memory and avoiding a random access to the internal memory. As well, the invention provides for improved dense integration and reduced costs when used in dense wavelength division multiplexing (DWDM) systems.
The “Summary of the Invention” does not necessarily disclose all the inventive features. The invention may reside in a sub-combination of the disclosed features.
REFERENCES:
patent: 4241411 (1980-12-01), Krasner et al.
patent: 4823297 (1989-04-01), Evans
patent: 5329474 (1994-07-01), Yamada
patent: 5369762 (1994-11-01), Wolf
patent: 5682340 (1997-10-01), Arends et al.
patent: 5724534 (1998-03-01), Boursier et al.
patent: 6073154 (2000-06-01), Dick
patent: 6351758 (2002-02-01), Courtney et al.
patent: 6609140 (2003-08-01), Greene
patent: 2003/0009467 (2003-01-01), Perrizo
Donnelly Victoria
Malzahn David H.
Tropic Networks Inc.
LandOfFree
Real-time method for bit-reversal of large size arrays does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Real-time method for bit-reversal of large size arrays, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Real-time method for bit-reversal of large size arrays will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3213264