jack06215
1/31/2018 - 4:11 AM

Digital Fourier Transform

import numpy as np
import matplotlib.pyplot as plt
import struct
import wave
import math


def iexp(n):
    return complex(math.cos(n), math.sin(n))

def is_pow2(n):
    return False if n == 0 else (n == 1 or is_pow2(n >> 1))

def fft_(xs, n, start=0, stride=1):
    "cooley-turkey fft"
    if n == 1: return [xs[start]]
    hn, sd = n // 2, stride * 2
    rs = fft_(xs, hn, start, sd) + fft_(xs, hn, start + stride, sd)
    for i in range(hn):
        e = iexp(-2 * math.pi * i / n)
        rs[i], rs[i + hn] = rs[i] + e * rs[i + hn], rs[i] - e * rs[i + hn]
    return rs


# Digital Fourier Transform (離散傅立葉轉換)
# 離散フーリエ変換
# In summary, DFT calculates the digital form of Fourier transform
# which brings a signal represented in time-domain to frequency-domain
# where each frequency bin (axis) has a magnitude and phase coefficient
def dft (N, g):
    G = [0.0] * N
    # for each frequency bin
    for k in range(N):
        # is the summation of the evaluated n-th sample complex values! (or Sin/Cos)
        for n in range(N):
            # As compared to its continuious version of FT
            # k/N is F (frequency)
            # n is t (time)
            real = np.cos(2 * np.pi * k * n / N)
            imag = - np.sin(2 * np.pi * k * n / N)
            G[k] += g[n] * complex(real, imag)
    return G

# sine wave generator 
# --------------------
# amplitude, base frequency, num of samples, sampling duration
def create_wave(A,f0,fs,t,num):
    data = []
    for n in np.arange(t * fs): # arange(): return evently spaced values
        y = (A / num) * np.sin(2 * np.pi * f0 * num * n / fs)
        # clip the amplitude to [-1 1]
        if y > 1.0: y = 1.0
        if y < -1.0: y = -1.0
        
        # C++ equivalence 'data.push_back(y)'
        data.append(y)
    return data

def main():
    
    # Generate square wave from sine waves
    data = create_wave(1, 261.63, 10000, 1, 1)
    for i in range(3,301,2):
        data = np.add(data, create_wave(1, 261.63, 10000, 1, i)) 

    data = data/np.max(data,0)
    N = 256                                       
    #G = dft(n0, N, data) 
    G = fft_(data,N)
    amp = [np.sqrt(c.real ** 2 + c.imag ** 2) for c in G]      
    phase = [np.arctan2(int(c.imag), int(c.real)) for c in G]   
    flist = [k * 10000 / N for k in range(N)]
   
   
    plt.figure(0)
    plt.plot(range(0, N), data[0:N])
    plt.axis([0, N, -1.0, 1.0])
    plt.xlabel("Time [sample]")
    plt.ylabel("Amplitude")


    #plt.subplot(312)
    plt.figure(1)
    plt.plot(flist, amp, marker='o', linestyle='-')
    #plt.axis([0, 10000/2, 0, 15])
    plt.xlabel("Frequency [Hz]")
    plt.ylabel("Amplitude spectrum")


    #plt.subplot(313)
    plt.figure(2)
    plt.plot(flist, phase, marker='o', linestyle='-')
    plt.axis([0, 10000/2, -np.pi, np.pi])
    plt.xlabel("Frequency [Hz]")
    plt.ylabel("Phase spectrum")
    plt.show()

if __name__ == '__main__':
    main()