Я делаю свертку из двух целочисленных сигналов с помощью БПФ, но почему-то я не могу сделать это правильно.Я не уверен, что моя реализация FFT верна.Особенно математическая часть.
большое редактирование: я разместил весь код сейчас.Мои извинения за то, что не начали с этого.Я был уверен, что ошибка была только в части БПФ, но могут быть и другие проблемы, которые я пропустил.Я знаю, что код грязный и не чистый.Все немного фрагментировано и может быть запрограммировано более простым и понятным способом, но я тестировал постепенно.Что касается ввода, он читает два сигнала из командной строки.построить как число, указывающее, насколько большой сигнал, и сигнал представлен в виде целочисленного массива eq 2: [1, -1] и 10: [0,0,0,1,1,1,1,0,0,0].Затем он должен выполнить свертку сигналов, выполнив FFT для них обоих, а затем выполнить побитовое умножение.С обратным БПФ на результирующий сигнал.Печать его снова с длиной, а затем массивом, состоящим из целых чисел.Сама печать верна, но значения в результирующем массиве не верны.Надеюсь, теперь все прояснилось, мои извинения, и спасибо за вашу помощь.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <complex.h>
double PI;
int *readSignal(int *len) { //reads the signal
int *x;
char c;
scanf("%d:", len);
x = calloc(*len, sizeof(int));
do c = getchar(); while (c != '[');
if (len > 0) {
scanf("%d", &x[0]);
for (int i=1; i < *len; i++) scanf(",%d", &x[i]);
}
do c = getchar(); while (c != ']');
return x;
}
void printSignal(int len, int *x) { //prints the signal
printf("%d: [", len);
if (len > 0) {
printf("%d", x[0]);
for (int i=1; i < len; i++)
printf(",%d", x[i]);
}
printf("]\n");
}
void *padSignal(int len, int lenSig, int *x) { //ensures that the signal is of size 2^n by padding it with 0's
int *padded;
padded = calloc(len, sizeof(int));
for (int i=0; i < lenSig; i++) {
padded[i] = x[i];
}
return padded;
}
void fft(double complex signal[], int length, int power) {
if (length == 1) {
return;
}
double complex *signalODD = calloc((length/2+1), sizeof(double complex));
double complex *signalEVEN = calloc((length/2+1), sizeof(double complex));
int index1 = 0;
int index2 = 0;
for(int i = 0; i < length; i++) {
if(i % 2 ==0) {
signalEVEN[index1] = signal[i];
index1++;
}
else {
signalODD[index2] = signal[i];
index2++;
}
}
fft(signalEVEN,length/2, power+1);
fft(signalODD,length/2, power+1);
for(int i = 0; i<length/2-1; i++) {
signal[i] = signalEVEN[i] + cexp((I*2*PI*i)/length)*signalODD[i];
signal[i+length/2] = signalEVEN[i]-cexp((I*2*PI*i)/length)*signalODD[i];
}
free(signalODD);
free(signalEVEN);
}
void ifft(double complex signal[], int length, int power) {
if (length == 1) {
return;
}
double complex *signalODD = calloc((length/2+1), sizeof(double complex));
double complex *signalEVEN = calloc((length/2+1), sizeof(double complex));
int index1 = 0;
int index2 = 0;
for(int i = 0; i < length; i++) {
if(i % 2 ==0) {
signalEVEN[index1] = signal[i];
index1++;
}
else {
signalODD[index2] = signal[i];
index2++;
}
}
fft(signalEVEN,length/2, power+1);
ifft(signalODD,length/2, power+1);
for(int i = 0; i<length/2-1; i++) {
signal[i] = signalEVEN[i] + cexp((I*-2*PI*i)/length)*signalODD[i];
signal[i+length/2] = signalEVEN[i]-cexp((I*-2*PI*i)/length)*signalODD[i];
}
free(signalODD);
free(signalEVEN);
}
int checkPowerofTwo(double len) { //checks for the closed power of 2
double x = 1;
while(len > pow(2,x)) {
x++;
}
return pow(2,x);
}
int main(int argc, char *argv[]) {
int lenH, *H;
int lenX, *X;
int *paddedX;
int *paddedH;
double length;
H=readSignal(&lenH); //reads in the signal H
X=readSignal(&lenX); //reads in signal X
length = lenH+lenX-1;
paddedH=padSignal((length),lenH,H); //pads the signal to the length
paddedX=padSignal((length),lenX,X); // pads the signal to the length
double complex *signalX = calloc(length, sizeof(double complex)); //creats a complex signal X and fills it with paddedX
for (int i = 0; i<length; i++) {
signalX[i] = paddedX[i];
}
double complex *signalH = calloc(length, sizeof(double complex)); // same for H
for (int i = 0; i<length; i++) {
signalH[i] = paddedH[i];
}
fft(signalX, length, 1); //performs the fast fourier transform on X
fft(signalH,length, 1); // performs the fast fourier transfom on H
double complex *signalY = calloc(length, sizeof(double complex)); //makes complex signal Y
for (int i = 0; i<length; i++) { //performs the convolution
signalY[i] = signalX[i]*signalH[i];
}
ifft(signalY, length,1);
int *output = calloc(length, sizeof(int)); //creates the final output signal
for (int i = 0; i<length; i++) {
output[i] = creal(signalY[i]);
}
printSignal(length,output);
free(signalX);
free(signalH);
free(signalY);
free(H);
free(X);
free(paddedH);
free(paddedX);
free(output);
return 0;
}