Patent ID: 7450492

Claim:
A correlation detection apparatus for detecting a first signal in a time domain including predetermined code, and a correlation between the first signal and the predetermined code, comprising: transform means for performing a Fourier transform comprising an N-stage butterfly operation by using M N (M is a radix in the Fourier transform; N=1, 2, . . . ) continuous storage regions on the first signal comprising M N time-series data; wherein the transform means comprises: data storage means for storing (I; I=0, 1, . . . , M N −1)th data into (M N−1 ([I/M 0 ]modM) +M N−2 ([I/M 1 ]modM) + . . . +M°([I/M N−1 ]modM); [X] is an integer not exceeding X; Y modZ is residue system of integer Y for integer Z)th storage region; first butterfly operation processing means for repeating processing of storing respective (MJ+H)th M pieces of data, obtained by performing a (J)th butterfly operation on data stored in (MJ+H; J=0, 1, . . . , M N−1 ,H=0 to M−1)th M storage regions, into (M N−1 H+M N−2 ([J/M 1 ]modM) + . . . +M°([J/M N−1 ]modM))th M storage regions, (N−1) times; and second butterfly operation processing means for performing processing of strong respective (MJ+H)th M pieces of data, obtained by performing a butterfly operation on the fata obtained as a result of the (N−1)th butterfly operation and stored in the (MJ+H)th M storage regions, into (M N−1 ([J/M 1 ]modM) + . . . +sM°([J/M N−1 ]modM)+H)th M storage regions; correlation-signal generation means for generating a correlation signal indicating a correlation between the predetermined code transformed to the frequency domain and the first signal transformed to the frequency domain; and correlation detection means for inverse-transforming the generated correlation signal into a signal in the time domain and detecting the correlation between the first signal and the predetermined code.