Scribd
Upload
19 views9 pages

Radix-2 FFT and DFT C Code Examples

The document contains a programming assignment on Digital Signal Processing by Utkarsh Dwivedi, featuring implementations of the radix-2 butterfly, Discrete Fourier Transform (DFT), and Fast Fourier Transform (FFT) in C. Each section includes code snippets for computing outputs and measuring execution time, with example outputs provided for both DFT and FFT. The assignment demonstrates the application of complex numbers and Fourier analysis techniques.

Uploaded by

Utkarsh Dwivedi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views9 pages

Radix-2 FFT and DFT C Code Examples

The document contains a programming assignment on Digital Signal Processing by Utkarsh Dwivedi, featuring implementations of the radix-2 butterfly, Discrete Fourier Transform (DFT), and Fast Fourier Transform (FFT) in C. Each section includes code snippets for computing outputs and measuring execution time, with example outputs provided for both DFT and FFT. The assignment demonstrates the application of complex numbers and Fourier analysis techniques.

Uploaded by

Utkarsh Dwivedi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Assignment-03 Digital Signal Processing

Name:- Utkarsh Dwivedi

Roll no:- 2022/B/11

1.
2.
The radix-2 butterfly combines two complex numbers with a twiddle factor W, using the
following equations

Where

#include <stdio.h>

#include <complex.h>

int main() {

// Define complex numbers for X1, X2 and twiddle factor W

double complex X1 = 2.0 + 3.0*I;

double complex X2 = 4.0 + 6.0*I;

double complex W = 0.25 - 0.75*I;

// Compute the radix-2 butterfly outputs


double complex X1_prime = X1 + W * X2;

double complex X2_prime = X1 - W * X2;

// Display the results

printf("X1' = %.2f %+.2fi\n", creal(X1_prime), cimag(X1_prime));

printf("X2' = %.2f %+.2fi\n", creal(X2_prime), cimag(X2_prime));

return 0;

Output

3.
4.
Discrete Fourier Transform (DFT) Code
#include <stdio.h>

#include <math.h>

#include <complex.h>

#include <time.h>

#define N 8 // DFT size

// DFT Function

void DFT(double complex x[], double complex X[]) {

for (int k = 0; k < N; k++) {

X[k] = 0;

for (int n = 0; n < N; n++) {

double angle = -2 * M_PI * k * n / N;

X[k] += x[n] * (cos(angle) + sin(angle) * I);


}

int main() {

// Input sequence

double complex x[N] = {1, 2, 3, 4, 5, 6, 7, 8};

double complex X[N];

// Time tracking

clock_t start, end;

start = clock();

// Compute DFT

DFT(x, X);

// Measure time

end = clock();

double time_taken = (double)(end - start) / CLOCKS_PER_SEC;

// Output DFT result

printf("DFT Results:\n");

for (int i = 0; i < N; i++) {

printf("X[%d] = %.2f + %.2fi\n", i, creal(X[i]), cimag(X[i]));

printf("DFT Execution Time: %.6f seconds\n", time_taken);

return 0;

Output
X[0] = 36.00 + 0.00i

X[1] = -4.00 + 9.66i


X[2] = -4.00 + 4.00i

X[3] = -4.00 + 1.66i

X[4] = -4.00 + 0.00i

X[5] = -4.00 - 1.66i

X[6] = -4.00 - 4.00i

X[7] = -4.00 - 9.66i

Fast Fourier Transform (FFT) Code


#include <stdio.h>

#include <math.h>

#include <complex.h>

#include <time.h>

#define N 8 // FFT size

// FFT Recursive Function

void FFT(double complex x[], int n) {

if (n <= 1) return;

double complex even[n/2], odd[n/2];

for (int i = 0; i < n/2; i++) {

even[i] = x[i*2];

odd[i] = x[i*2+1];

FFT(even, n/2);

FFT(odd, n/2);

for (int k = 0; k < n/2; k++) {

double complex t = cexp(-I * 2 * M_PI * k / n) * odd[k];

x[k] = even[k] + t;
x[k + n/2] = even[k] - t;

int main() {

// Input sequence

double complex x[N] = {1, 2, 3, 4, 5, 6, 7, 8};

// Time tracking

clock_t start, end;

start = clock();

// Compute FFT

FFT(x, N);

// Measure time

end = clock();

double time_taken = (double)(end - start) / CLOCKS_PER_SEC;

// Output FFT result

printf("FFT Results:\n");

for (int i = 0; i < N; i++) {

printf("X[%d] = %.2f + %.2fi\n", i, creal(x[i]), cimag(x[i]));

printf("FFT Execution Time: %.6f seconds\n", time_taken);

return 0;

Output
X[0] = 36.00 + 0.00i

X[1] = -4.00 + 9.66i

X[2] = -4.00 + 4.00i


X[3] = -4.00 + 1.66i

X[4] = -4.00 + 0.00i

X[5] = -4.00 - 1.66i

X[6] = -4.00 - 4.00i

X[7] = -4.00 - 9.66i

5.

You might also like