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.

Delete this entry (admin only).