FFT permutations

fft_permute.py

from veriutils import (
    check_intbv_signal, check_bool_signal)

from myhdl import Signal, intbv, always_comb, always

from math import log
import numpy as np

def FFTPermute(input_siglist, output_siglist, butterfly_index,
               clock_enable, clock):
    
    check_bool_signal(clock, 'clock')
    check_bool_signal(clock_enable, 'clock_enable')

    input_siglength = len(input_siglist[0])

    if len(input_siglist) != len(output_siglist):
        raise ValueError(
            'Input and output siglists should be the same length')

    if log(len(input_siglist), 2) % 1 != 0:
        raise ValueError(
            'Input and output siglists should have a length a power of two')
    
    max_butterfly_index = int(log(len(input_siglist), 2))
    check_intbv_signal(butterfly_index, 'butterfly_index', 
                       val_range=(0, max_butterfly_index))

    for n, (each_input, each_output) in enumerate(
        zip(input_siglist, output_siglist)):

        check_intbv_signal(
            each_input, 'input_siglist[%d]' % n, input_siglength, 
            signed=True)
        check_intbv_signal(
            each_output, 'output_siglist[%d]' % n, input_siglength, 
            signed=True)

    min_val = input_siglist[0].min
    max_val = input_siglist[0].max

    N = len(input_siglist)
    butterflies = int(log(N, 2))
    permutations = np.zeros((butterflies, N), dtype='int64')

    for n in range(butterflies):
        # A neat trick to compute the permutations
        permutations[n, :] = np.bitwise_xor(np.arange(0, N),
                                            2**(butterflies - n - 1))

    permuted_siglist = [
        Signal(intbv(0, min=min_val, max=max_val)) for _ in range(N)]

    def multiplexor(input_signals, output_signal, index):
        @always_comb
        def mux():
            output_signal.next = input_signals[index]

        return mux

    permutation_instances = []
    for n in range(N):

        input_signals = []
        # Extract the relevant subset of input signals for each permuted
        # sig
        foo = []
        for each_input_idx in permutations[:, n]:
            input_signals.append(input_siglist[each_input_idx])
            foo.append(each_input_idx)
        # Then create a multiplexor for that subset.
        permutation_instances.append(
            multiplexor(input_signals, permuted_siglist[n], butterfly_index))

    @always(clock.posedge)
    def assign_output_siglist():

        for n in range(N):
            output_siglist[n].next = permuted_siglist[n]

    return assign_output_siglist, permutation_instances

Try:

WIDTH_D = len(input_siglist[0])
for each_input_idx in permutations[:, n]:
        input_signals.append(input_siglist[each_input_idx](WIDTH_D,0)

But now MyHDL will complain about the lists in the top-level call.

Best regards,

Josy

Workaround to create a new signal for the interim lists...

#snip at line 60
    def simple_assignment(input_sig, output_sig):
        @always_comb
        def assign_sig():
            output_sig.next = input_sig

        return assign_sig

    permutation_instances = []
    assignment_instances = []
    for n in range(N):

        input_signals = []
        # Extract the relevant subset of input signals for each permuted
        # sig
        for each_input_idx in permutations[:, n]:
            this_signal = input_siglist[each_input_idx]
            copied_signal = Signal(
                intbv(0, min=this_signal.min, max=this_signal.max))
            input_signals.append(copied_signal)
            assignment_instances.append(
                simple_assignment(this_signal, copied_signal))
        # Then create a multiplexor for that subset.
        permutation_instances.append(
            multiplexor(input_signals, permuted_siglist[n], butterfly_index))

    @always(clock.posedge)
    def assign_output_siglist():

        for n in range(N):
            output_siglist[n].next = permuted_siglist[n]

    return assign_output_siglist, permutation_instances, assignment_instances

in _Signal.py, in the Signal class:

    ### use call interface for shadow signals ###
    def __call__(self, left = None, right=None):
        s = _SliceSignal(self, left, right)
        self._slicesigs.append(s)
        return s

and in _ShadowSignal:

class _SliceSignal(_ShadowSignal):

    __slots__ = ('_sig', '_left', '_right')

    def __init__(self, sig, left = None, right=None):
        ### XXX error checks
        if left is None:
            # a 'clone'
            _ShadowSignal.__init__(self, sig)
            self._sig = sig
            gen = self._genfuncClone()
            self._left = None

        else:
            if right is None:
                _ShadowSignal.__init__(self, sig[left])
            else:
                _ShadowSignal.__init__(self, sig[left:right])
            self._sig = sig
            self._left = left
            self._right = right
            if right is None:
                gen = self._genfuncIndex()
            else:
                gen = self._genfuncSlice()
        self._waiter = _SignalWaiter(gen)


    def _genfuncClone(self):
        tracejb('_ShadowSignal: _SliceSignal: _genfuncClone')
        logjbinspect(self._sig, 'self._sig', True)
        sig = self._sig
        set_next = _Signal.next.fset
        tracejbdedent()
        while 1:
            set_next(self, sig)
            yield sig

    def toVHDL(self):
        tracejb('_ShadowSignal: _SliceSignal: toVHDL')
        tracejbdedent()
        if self._left is None:
            return "%s <= %s;" % (self._name, self._sig._name)
        else:
            if self._right is None:
                return "%s <= %s(%s);" % (self._name, self._sig._name, self._left)
            else:
                return "%s <= %s(%s-1 downto %s);" % (self._name, self._sig._name, self._left, self._right)

now we can create a 'blind' ShadowSignal, e.g.:

    input_signals.append(input_siglist[each_input_idx]())

This just a test though, before creating a PR we might investigate whether a new separate class _CloneSignal wouldn't be more appropriate

@heng, If I am following the problem you are trying to solve, which is: a single module that maps the FFT butterfly (output to inputs for each stage).

The approach I would take is to calculate the indexes and have a single process (generator) that assigns the outputs to the inputs, something like this: https://gist.github.com/cfelton/eff1b0aeb84dbcdc1dde