Patent ID: 8145694

Claim:
A fast Fourier transform circuit, comprising: a first buffer that accumulates 2 N (N is a natural number) digital signals and outputs a first buffer digital signal in which an order of bits is rearranged into a position of a bit reversed order where the order of the bits is reversed; a second buffer that accumulates 2 M (M is a natural number and is equal to or less than N) digital signals and outputs a second buffer digital signal in which an order of bits is rearranged into a position of a bit reversed order; a first fast Fourier transform processing section that performs first butterfly computation processing every 2 M−1 digital signals in (M− 1 ) steps on the first buffer digital signal and outputs a first butterfly processed digital signal and performs second butterfly computation processing every 2 M−1 digital signals in (M− 1 ) steps on the second buffer digital signal and outputs a second butterfly processed digital signal; a second fast Fourier transform processing section that performs third butterfly computation processing every 2 N digital signals in (N-M+1) steps on the first butterfly processed digital signal; and a third fast Fourier transform processing section that performs fourth butterfly computation processing every 2 M digital signals in one step on the second butterfly processed digital signal.