% % Discrete Fourier transform (MATLAB) % by Project Nayuki, 2017. Public domain. % https://www.nayuki.io/page/how-to-implement-the-discrete-fourier-transform % % % Computes the discrete Fourier transform (DFT) of the given complex vector. % 'input' can be a row vector or a column vector. The returned output has the same dimensions. % function output = compute_dft_scalarized(input) assert(isvector(input)); n = numel(input); output = NaN(size(input)); for k = 0 : n - 1 % For each output element s = 0; for t = 0 : n - 1 % For each input element s = s + input(t + 1) * exp(-2i * pi * t * k / n); end output(k + 1) = s; end end % % (Alternate implementation using matrix arithmetic.) % Computes the discrete Fourier transform (DFT) of the given complex vector. % 'input' can be a row vector or a column vector. The returned output has the same dimensions. % function output = compute_dft_vectorized(input) assert(isvector(input)); n = numel(input); matrix = exp(-2i * pi / n * (0 : n-1)' * (0 : n-1)); if size(input, 1) == 1 % Row vector output = input * matrix; elseif size(input, 2) == 1 % Column vector output = matrix * input; end end