A low-complexity correlation algorithm

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.