FFT 알고리즘이 512 또는 1024와 같이 2의 거듭 제곱 인 입력 배열 크기를 갖춰야한다는 것을 여러 곳에서 읽었습니다. FFT, Cooley-Tuckey 및 Bluestein (이 중 하나는 2,3,5,7과 같은 주요 요인을 따르는 숫자와도 작동합니다)과 같습니다.KissFFT와 Power of Two
음, KissFFT를 사용하고 길이 200의 배열을 입력하고 있습니다. 왜 작동합니까? 누군가이 사건에서 무슨 일이 일어 났는지 압니까? 크기를 128 (2^7)로 줄이거 나 다른 알고리즘을 사용하고 있습니까? 다른 알고리즘을 사용하고 있다면 올바른 답을 제공하지만 계산 시간이 오래 걸리나요? (시간이 경우에 나를 위해 실제로 문제가되지 않습니다.) 나는 마지막으로 몇 가지 유용한 정보를 발견
당신이 절대적으로 길이 FFT를 사용해야하는 경우 없습니다 합리적으로 효율적으로 할 수있는 적어도 두 가지 방법이있다 2의 거듭 제곱 :
(1)의 경우는 원하는 길이는 길이가 2의 정확한 제곱 인 경우 사용되는 방법을 일반화 할 수있는 작은 숫자의 곱입니다.
(2) 실제로 임의의 길이보다 긴 벡터로 이루어진 임의의 길이의 컨볼 루션으로 FFT를 만들 수 있습니다.이 긴 벡터의 길이는 2의 거듭 제곱 일 수 있으므로 FFT를 수행 할 수 있습니다. 2의 거듭 제곱에 의한 컨벌루션. 예를 들어 http://www.engineeringproductivitytools.com/stuff/T0001/PT11.HTM을 참조하십시오. 이것은 AB = (A-B)^2 - A^2 - B^2라는 정체성을 사용합니다. 당신은 f (Xi) exp (ij)와 같이 보이는 용어의 합계로 끝나기를 원합니다. 회선 (convolution)을 사용하면 f (Xi) exp (-i^2)와 exp ((ij)^2)를 결합하여 지수를 추가하여 exp (-2ij + j^2)를 부여 할 수 있습니다. 사후 처리 과정에서 j^2를 꺼내십시오. 참고 자료에서는 지수를 실제로 실제로 올바르게 작성하는 방법을 보여줍니다.
필자는 얼마 전 FFT를 구현할 때 데이터 길이를 2^n (그리고 "0"으로 채워진 "new cells") 크기로 조정 했으므로이 방법으로 구현할 수있었습니다 – fex