A low-complexity correlation algorithm

Author

Cheng, Kuang-Fu ; Chen, Sou-Gee

Author_Institution

Dept. of Electron. Eng., Nat. Chiao Tung Univ., Hsinchu, Taiwan

Volume

5

fYear

2003

Abstract

For the consideration of low power, and fast code acquisition, four new low-complexity correlation algorithms are proposed in this work. Among them, the one derived by combing the differential coding scheme and a fast filtering algorithm has the lowest complexity. The new algorithm reduces the direct N addition operations to 5N/16. As a result, close to 70% reduction is obtained. When compared with the fast correlation algorithm based on the differential coding scheme, which costs N/2 addition operations, close to 40% reduction is obtained. The new algorithm can be further combined with the sub-expression sharing techniques for a much significant complexity reduction. The proposed design is best suited for DSP realization.

Keywords

FIR filters; convolution; correlation methods; correlators; digital arithmetic; encoding; low-power electronics; DSP realization; addition operation reduction; complexity reduction; correlators; differential coding scheme; fast FIR convolution algorithm; fast code acquisition; fast filtering algorithm; low power correlation algorithms; low-complexity correlation algorithm; sub-expression sharing techniques; Batteries; Convolution; Correlators; Costs; Digital signal processing; Filtering algorithms; Multiaccess communication; Power engineering and energy; Signal processing algorithms; Wireless communication;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 2003. ISCAS '03. Proceedings of the 2003 International Symposium on

Print_ISBN

0-7803-7761-3

Type

conf

DOI

10.1109/ISCAS.2003.1206261

Filename

1206261