# 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[0] tempSecond = group[1] group[0] = group[0] + ","+tempSecond group[1] = group[1] + ","+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][1] superGroups[s][g][1] = superGroups[s+1][g][0] superGroups[s+1][g][0] = 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[0] for group in superGroups[0]] finalSamples.append([group[1] for group in superGroups[0]]) 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.