U
uche
Hi,
I have the following FFT python code and it doesn't seem to compile
correctly. To run it, please create a file called output.csv with
1,2,3,4,5,6,7,8. simply run the main function. I get an error such as
the following:
x[a], x = x[(a)] + W[(n % N)] * x[(b)], x[(a)] - W[(n % N)] * x
[(b)]
TypeError: list indices must be integers, not float
How can I fixe this problem ? I have tried puttin int on all of the
variables, but I don't think that is the intension of the person who
wore the original code.
#!/usr/bin/python
"""
FFT using Cooley-Tukey algorithm where N = 2^n. The choice of
e^{-j2\pi/N} or e^{j2\pi/N} is made by 'sign=-1' or 'sign=1'
respectively. Since I prefer Engineering convention, I chose
'sign=-1' as the default.
FFT is performed as follows:
1. bit-reverse the array.
2. partition the data into group of m = 2, 4, 8, ..., N data points.
3. for each group with m data points,
1. divide into upper half (section A) and lower half (section B),
each containing m/2 data points.
2. divide unit circle by m.
3. apply "butterfly" operation
|a| = |1 w||a| or a, b = a+w*b, a-w*b
|b| |1 -w||b|
where a and b are data points of section A and B starting from
the top of each section, and w is data points along the unit
circle starting from z = 1+0j.
FFT ends after applying "butterfly" operation on the entire data array
as whole, when m = N.
"""
def main():
array = []
array2 = []
import os
import time
os.path.exists("input.csv")
fin=open('input.csv', 'r')
for line in fin: #read the line from the file
array=line.split(',')
for a in range(len(array)): #convert into integers
array2.append((array[a]))
Ti=time.time()
print (fft(array2))
Tf=time.time()
print (("It took"),Tf-Ti,("seconds to calculate an FFT of
size"),len(array))
#end timer
"""
Find 2^n that is equal to or greater than.
"""
def nextpow2(i):
n = 2
while n < i: n = n * 2
return n
"""
Return bit-reversed list, whose length is assumed to be 2^n:
eg. 0111 <--> 1110 for N=2^4.
"""
def bitrev(x):
N, x = len(x), x[:]
if N != nextpow2(N): raise ValueError ('N is not power of 2')
for i in range(N):
k, b, a = 0, N>>1, 1
while b >= a:
if b & i: k = k | a
if a & i: k = k | b
b, a = b>>1, a<<1
if i < k: x, x[k] = (x[k],x)
return x
def fft(x, sign=-1):
from cmath import pi, exp
N, W = len(x), []
for i in range(N): # exp(-j...) is default
W.append(exp(sign * 2j * pi * i / N))
x = bitrev(x)
m = 2
while m <= N:
for s in range(0,N,m):
for i in range (int(m/2)):
n = i * N / m
a, b = s + i, s + i + m/2
x[a], x = x[(a)] + W[(n % N)] * x[(b)], x[(a)] - W
[(n % N)] * x[(b)]
m = m * 2
return x
I have the following FFT python code and it doesn't seem to compile
correctly. To run it, please create a file called output.csv with
1,2,3,4,5,6,7,8. simply run the main function. I get an error such as
the following:
x[a], x = x[(a)] + W[(n % N)] * x[(b)], x[(a)] - W[(n % N)] * x
[(b)]
TypeError: list indices must be integers, not float
How can I fixe this problem ? I have tried puttin int on all of the
variables, but I don't think that is the intension of the person who
wore the original code.
#!/usr/bin/python
"""
FFT using Cooley-Tukey algorithm where N = 2^n. The choice of
e^{-j2\pi/N} or e^{j2\pi/N} is made by 'sign=-1' or 'sign=1'
respectively. Since I prefer Engineering convention, I chose
'sign=-1' as the default.
FFT is performed as follows:
1. bit-reverse the array.
2. partition the data into group of m = 2, 4, 8, ..., N data points.
3. for each group with m data points,
1. divide into upper half (section A) and lower half (section B),
each containing m/2 data points.
2. divide unit circle by m.
3. apply "butterfly" operation
|a| = |1 w||a| or a, b = a+w*b, a-w*b
|b| |1 -w||b|
where a and b are data points of section A and B starting from
the top of each section, and w is data points along the unit
circle starting from z = 1+0j.
FFT ends after applying "butterfly" operation on the entire data array
as whole, when m = N.
"""
def main():
array = []
array2 = []
import os
import time
os.path.exists("input.csv")
fin=open('input.csv', 'r')
for line in fin: #read the line from the file
array=line.split(',')
for a in range(len(array)): #convert into integers
array2.append((array[a]))
Ti=time.time()
print (fft(array2))
Tf=time.time()
print (("It took"),Tf-Ti,("seconds to calculate an FFT of
size"),len(array))
#end timer
"""
Find 2^n that is equal to or greater than.
"""
def nextpow2(i):
n = 2
while n < i: n = n * 2
return n
"""
Return bit-reversed list, whose length is assumed to be 2^n:
eg. 0111 <--> 1110 for N=2^4.
"""
def bitrev(x):
N, x = len(x), x[:]
if N != nextpow2(N): raise ValueError ('N is not power of 2')
for i in range(N):
k, b, a = 0, N>>1, 1
while b >= a:
if b & i: k = k | a
if a & i: k = k | b
b, a = b>>1, a<<1
if i < k: x, x[k] = (x[k],x)
return x
def fft(x, sign=-1):
from cmath import pi, exp
N, W = len(x), []
for i in range(N): # exp(-j...) is default
W.append(exp(sign * 2j * pi * i / N))
x = bitrev(x)
m = 2
while m <= N:
for s in range(0,N,m):
for i in range (int(m/2)):
n = i * N / m
a, b = s + i, s + i + m/2
x[a], x = x[(a)] + W[(n % N)] * x[(b)], x[(a)] - W
[(n % N)] * x[(b)]
m = m * 2
return x