# Demo entry 6646451

test

Submitted by anonymous on Oct 17, 2017 at 00:41
Language: Python. Code size: 4.1 kB.

```# Test out how the normal FFT combines samples
# in order to investigate how "supergroups"
# can interleave their samples in order to create an equivalent FFT
import math

numSamples = 16

def initialize():
samples = []
for i in range(0, numSamples):
samples.append(str(i))
return samples

def display(samples):
for i in range(0, numSamples):
print("["+samples[i]+"]")
print()

def fakeFFT(samples):
print("Fake Traditional FFT - Initial Status: ")
display(samples)
print()
N = len(samples)
NM1 = N - 1
M = int(math.log2(N))
for stage in range(1,M+1):
LE = 2**stage
LE2 = LE//2
for j in range(1, LE2 + 1):
jm1 = j - 1
for i in range(jm1, NM1 + 1, LE):
ip = i + LE2
# show ow the samples combined
tempIP = samples[ip]
tempI = samples[i]
samples[i] = samples[i]+","+tempIP
samples[ip] = samples[ip]+","+tempI
# show this stage's status and pause before next one
display(samples)
input()

def samplesToSuperGroups(samples):
superGroups = []
for i in range(0,numSamples,2):
temp1 = samples[i]
temp2 = samples[i+1]
superGroups.append([[temp1,temp2]])
print("Supergroups contents:")
for group in superGroups:
print(str(group) + "   ")
print()
return superGroups

#def interleave(superGroups):
#    pass

def fakeGroupedFFT(superGroups):
#print(superGroups)
N = numSamples
NM1 = N - 1
M = int(math.log2(N))
for stage in range(1,M+1):
LE = 2**stage
LE2 = LE//2

# butterfly happens in every group in every supergroup
for superGroup in superGroups:
for group in superGroup:
#print(group)
tempFirst = group
tempSecond = group
group = group + ","+tempSecond
group = group + ","+tempFirst

if len(superGroups) > 1:
# then interleave
for s in range(0, len(superGroups), 2):
for g in range(0, len(superGroups[s])): # step 2?
tempSample = superGroups[s][g]
superGroups[s][g] = superGroups[s+1][g]
superGroups[s+1][g] = tempSample

# at the end of the stage, a supergroup on the left
# absorbs the supergroup on its right
# Here, this implemented by just making a new supergroups
# list and adding two supergroups' content to it at
# each iteration
modifiedSuperGroups = []
for s in range(0, len(superGroups), 2):
modifiedSuperGroup = []
for g in range(0,len(superGroups[s])):
modifiedSuperGroup.append(superGroups[s][g])
for g in range(0,len(superGroups[s+1])):
modifiedSuperGroup.append(superGroups[s+1][g])
modifiedSuperGroups.append(modifiedSuperGroup)
superGroups = modifiedSuperGroups

for superGroup in superGroups:
print(superGroup, end='\n')
input()

# end stages
# Now there is only 1 supergroup.
# The final array will begin of the the first sample
# of every group and the end will be the last sample of
# every group.
finalSamples = [group for group in superGroups]
finalSamples.append([group for group in superGroups])
print(finalSamples)
return finalSamples

def main():
print("Investigate normal FFT sample combinations.")
samples = initialize()
fakeFFT(samples)
samples = initialize()
superGroups = samplesToSuperGroups(samples)
fakeGroupedFFT(superGroups)

if __name__=='__main__':
main()
```

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.