System and method for providing memory bandwidth efficient correlation acceleration

• US 8,516,028 B2
• Filed: 08/03/2010
• Issued: 08/20/2013
• Est. Priority Date: 08/03/2010
• Status: Active Grant

• Current Assignee: Beijing Xiaomi Mobile Software Co., Ltd. (Xiaomi Corp.)
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Yu, Meng-Lin
• Primary Examiner(s): Malzahn, David H
• Application Number:
  US12/849,142
• Publication Number:
  US 20120036174A1
• Time in Patent Office: 1,113 Days
• Field of Search: None
• US Class Current: 708/422
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: H04B 1/709 Correlator structure

Abstract

A system and method for providing memory bandwidth efficient correlation acceleration. A correlation accelerator or correlator (e.g., an X*Y correlator) can be configured in association with a processor of a wireless communication system for correlating an input signal data sequence (X) and its shifted versions with a reference data sequence. Shifted versions (including the 0-shifted or the original) with respect to the input signal data sequence can be generated for each column (Y columns) of a sliding window in the correlator in order to reduce an input bandwidth requirement. Each input signal data and the shifted versions can be concurrently multiplied with the reference signal data and the results can be summed together in order to generate an output signal data profile. The output signal data profile can be stored into an accumulator register in order to reduce an output bandwidth requirement.

Claims

1. A method for providing a memory bandwidth efficient (cross) correlation acceleration, said method comprising:

generating a plurality of shifted versions with respect to an input signal data sequence for each column of a sliding window associated with a correlator in order to reduce an input bandwidth requirement;

multiplying concurrently said input signal data sequence and said plurality of shifted versions with a reference signal data sequence and summing a multiplication result with respect to each column of said sliding window in order to generate an output signal data profile; and

storing said output signal data profile into an accumulator register of an array of accumulators that acts as adders for summing an output data signal profile of said each column in said sliding window of said correlator in order to reduce an output bandwidth requirement and thereby provide a memory bandwidth efficient correlation acceleration across a wide range of wireless communication systems.

2. The method of claim 1 further comprising:

generating said plurality of shifted versions with respect to said signal data sequence for each column of said sliding window associated with said correlator in order to reduce said input bandwidth requirement; and

multiplying concurrently said reference signal data sequence and said plurality of shifted versions with said input signal data sequence and summing a multiplication result with respect to each column of said sliding window in order to generate said output signal data profile.

3. The method of claim 1 further comprising summing said multiplication result at each column of said sliding window via at least one adder among said adders.

4. The method of claim 3 further comprising:

dividing a computation array associated with said sliding window of said correlator into a plurality of blocks in order to compute a partial correlation with respect to said plurality of blocks in said sliding window; and

iteratively summing an output signal data from said plurality of blocks in said sliding window with a previous partial computation result utilizing said at least one in order to thereafter accelerate correlation computation.

5. The method of claim 1 wherein said correlator comprises a two-dimensional X*Y correlator.

6. The method of claim 1 further comprising configuring said correlator to include at least one of the following components:

at least one adder among said adders;

at least one multiplexer;

at least one complex carry save adder; and

at least one accumulator, wherein said array of accumulators comprises said at least one accumulator including said accumulator register.

7. The method of claim 6 wherein said at least one adder comprises a 40-bit accumulator.

8. The method of claim 1 further comprising configuring said correlator in association with a processor capable of being adapted for use with a wireless communication system.

9. The method of claim 8 further comprising integrating said correlator into a data path of said processor for providing an intrinsic operation in said wireless communication system.

10. The method of claim 8 wherein said processor comprises a co-processor.

11. The method of claim 8 wherein said processor comprises a digital signal processor.

12. The method of claim 8 wherein said processor comprises a vector processor.

13. The method of claim 8 further comprising configuring said processor in association with said correlator in an FIR application with input reuse and output reduction.

14. A system for providing a memory bandwidth efficient (cross) correlation acceleration, said system comprising:

at least one processor;

at least one data bus coupled to said at least one processor; and

a computer-usable medium embodying computer code, said computer-usable medium being coupled to said at least one data bus, said computer program code comprising instructions executable by said at least one processor and configured for;

generating a plurality of shifted versions with respect to an input signal data sequence for each column of a sliding window associated with a correlator in order to reduce an input bandwidth requirement;

an adder;

integrating said correlator into a data path of said processor of said wireless communication system for providing an intrinsic operation in said wireless communication system.

15. The system of claim 14 wherein said instructions are further configured for:

generating said plurality of shifted versions with respect to said signal data sequence for each column of said sliding window associated with said correlator in order to reduce said input bandwidth requirement; and

multiplying concurrently said reference signal data sequence and said plurality of shifted versions with said input signal data sequence and summing a multiplication result with respect to each column of said sliding window in order to generate said output signal data profile.

16. The system of claim 14 wherein said instructions are further modified for configuring said correlator in association with said at least one processor, wherein said at least one processor comprises a processor capable of being adapted for use with a wireless communication system.

17. The system of claim 16 wherein said instructions are further configured for:

summing said multiplication result at each column of said sliding window via output bandwidth requirement and thereby provide a memory bandwidth efficient correlation acceleration across a wide range of wireless communication systems.

18. The system of claim 16 wherein said instructions are further configured for:

dividing a computation array associated with said sliding window of said correlator into a plurality of blocks in order to compute a partial correlation with respect to said plurality of blocks in said sliding window; and

iteratively summing an output signal data from said plurality of blocks in said sliding window with a previous partial computation result utilizing at least one adder among said adders in order to thereafter accelerate correlation computation.

19. A computer-usable for providing a memory bandwidth efficient (cross) correlation acceleration, said computer-usable medium embodying computer program code, said computer program code comprising computer executable instructions configured for:

generating a plurality of shifted versions with respect to an input signal data sequence for each column of a sliding window associated with a correlator in order to reduce an input bandwidth requirement;

multiplying concurrently said input signal data sequence and said plurality of shifted versions with a reference signal data sequence and summing a multiplication result with respect to each column of said sliding window in order to generate an output signal data profile; and

storing said output signal data profile into an accumulator register of an array of accumulators that acts as adders for summing an output data signal profile of said each column in said sliding window of said correlator in order to reduce an

multiplying concurrently said input signal data sequence and said plurality of shifted versions with a reference signal data sequence and summing a multiplication result with respect to each column of said sliding window in order to generate an output signal data profile; and

storing said output signal data profile into an accumulator register of an array of accumulators that acts as adders for summing an output data signal profile of said each column in said sliding window of said correlator in order to reduce an output bandwidth requirement and thereby provide a memory bandwidth efficient correlation acceleration across a wide range of wireless communication systems.

20. The computer usable medium of claim 19 wherein said embodied computer program code further comprises computer executable instructions configured for:

generating said plurality of shifted versions with respect to said signal data sequence for each column of said sliding window associated with said correlator in order to reduce said input bandwidth requirement; and

multiplying concurrently said reference signal data sequence and said plurality of shifted versions with said input signal data sequence and summing a multiplication result with respect to each column of said sliding window in order to generate said output signal data profile.