Digital audio (1D), image (2D), video (3D), and other multi-dimensional (4D or more) signal data are often processed by computing the Discrete Fourier Transform (DFT) of the signals. In some signal filtering applications, the DFT of the signals and the desired filters are computed, multiplied, and the inverse DFT of the result is computed. Transforms similar to DFT such as the Discrete Cosine Transform (DCT) are used in image/video compression. In this project, you will use multi-dimensional arrays to store and compute the forward and inverse DFT of signals up to 3 dimensions. Memory for arrays will be determined at runtime and must be allocated dynamically. The separable property of the DFT along different dimensions will be used in computing the transform coefficients.

The input format is:

n // number of dimensions of the signal n=1,2, or 3.

m1 // array dimension along the first dimension for n=1,2, or 3.

m2 // present when n>=2; array dimension along the second dimension for n=2 or 3.

m3 // present when n==3; array dimension along the third dimension for n=3.

Example of input data:

3 // n =3

10 // m1 = 10

8 // m2=8

16 // m3 = 16

Steps:

This will be explained for the three-dimensional case (n=3). Extrapolate this yourself to infer the explanation for n=2, and n=1.

Read input data. See the example above for the input format.

Dynamically allocate memory for the digital signal, d[m1][m2][m3], its forward DFT- FDFT[m1][m2][m3] [2], and the inverse DFT-- IDFT[m1][m2][m3].

Generate simulated signal data through random number generation. Let the data at each entry d[i1][i2][i3] be a random floating point number in the range 0.0 to 255.0 (this is the typical range of a digital signal sample represented by 1 byte or 8 bits per sample). Get this by generating a random integer and taking modulo or remainder with respect to 255, and type casting the result to float. This step will initialize the full array d[m1][m2][m3]. (In real applications, this data is read from a file or from the output of a camera/sensor).

Print the data generated in a suitable format.

Compute the forward DFT- FDFT[m1][m2][m3]. Use the separable property of the DFT along different dimensions in computing the transform coefficients (see the equation for computing the transform).

Print the forward DFT in a suitable format.

Compute the Inverse DFT- IDFT[m1][m2][m3]. Use the separable property of the inverse DFT along different dimensions in computing the transform coefficients.

Print the inverse DFT in a suitable format.

Compute and print the root-mean-square (RMS) error between the original signal d[m1][m2][m3] and the inverse DFT-- IDFT[m1][m2][m3]. This is done by finding the difference between each corresponding entry of the arrays, squaring and summing all the differences, dividing the sum result by the number of entries, and then computing the square-root of the result. In the ideal case of high-precision arithmetic operations, this error should be close to zero. In practice, this would be a small number.

In the following definitions, note that complex numbers with real and imaginary parts are used in the formulas. Also, note that

exp(jx) = Cos(x)+j Sin(x).

That is, Cos(x) is the real part and Sin(x) is the imaginary part.

Use the following program as needed for memory allocation/deallocation.

/***************************************************************

* Dynamic memory allocation for

* a multi-dimensional array.

***************************************************************/

#include

using namespace std;

#include // for rand(), srand()

#include // for time()

#include

#include // for sqrt(), etc.

// Use of new to dynamically allocate an array

// assumes older-style return of 0 for

// allocation error

struct cmpx { double rl; double im; }; // complex number with real and imaginary parts

// a sample routine for reading data

void read_data(struct cmpx*** data1, int s1, int s2, int s3)

{

int i, j, k;

srand((unsigned int)time(NULL));// seed rand() with system time

for (i = 0; i

for (j = 0; j

for (k = 0; k

// cin >> data1[i][j][k].rl; //input data from a file or console

// cin >> data1[i][j][k].im; //input data from a file or console

data1[i][j][k].rl = (float)(rand() % 100); // limit data to 0 to 99.

data1[i][j][k].im = (float)(rand() % 100); // limit data to 0 to 99.

}

}

}

}

int main()

{

int i, j, k;

int size1, size2, size3;

struct cmpx*** data; // 3-level pointer

cout

cin >> size1 >> size2 >> size3; // variables for the size of an array

assert(size1 > 0); // exit if non-positive

assert(size2 > 0);

assert(size3 > 0);

// testing

// double ad[2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][1][1][1][1][2];

// ad[1][1][1][0][1][0][1][1][1][1][1][1][1][1][1][0][0][0][0][1] = 3.0;

// cout

// double** ad1 = new double*[5];

// double**************************************** ad2;

// Memory allocation for the 3-D pointer "data"

data = new struct cmpx**[size1]; // allocate array of 2-level pointers

assert(data != 0); // data != 0 allocation OK

for (i = 0; i

{

data[i] = new struct cmpx*[size2]; // allocate array of double-type 2-level pointers

assert(data[i] != 0);

}

for (i = 0; i

for (j = 0; j

{

data[i][j] = new struct cmpx[size3]; // allocate array of double-type pointers

assert(data[i][j] != 0);

}

// read input to the array 'data'

read_data(data, size1, size2, size3);

// process your data here to compute the output from the input.

// A function call may be suitable

// print out the data array to check

for (i = 0; i

for (j = 0; j

for (k = 0; k

cout

}

cout

}

cout

}

// deallocation of the memory

for (i = 0; i

for (j = 0; j

delete[](data[i][j]);

for (i = 0; i

delete[] data[i];

delete[] data; // deallocate an array

cout

cin >> i; // make the program wait till this input is entered (otherwise the output window disappears)

return 0;

}

m1-1 m2-1 m3-1 exp 2 [a3 x3/m3]) * d(x1] [x2] [x3] }} x3 = 0 1DFTIu1][u2][L3]-(1/m1 m2 m2 )) * m1-1 exp(j 2 [u1x1 /m:1] ) * { m2-1 exp(j 2 lu2x2 /m2]) * { m3-1 exPU 2 [u3 x3/m3]) * FDFT[x1][x2][x3] }} m1-1 m2-1 m3-1 exp 2 [a3 x3/m3]) * d(x1] [x2] [x3] }} x3 = 0 1DFTIu1][u2][L3]-(1/m1 m2 m2 )) * m1-1 exp(j 2 [u1x1 /m:1] ) * { m2-1 exp(j 2 lu2x2 /m2]) * { m3-1 exPU 2 [u3 x3/m3]) * FDFT[x1][x2][x3] }}