b_asic.sfg_generators

B-ASIC signal flow graph generators.

This module contains a number of functions generating SFGs for specific functions.

b_asic.sfg_generators.analytical_block_matrix_inverse(N: int, name: str | None = None, mode: Literal['top', 'bot', 'mid'] = 'mid', pe: Literal['addsub', 'mads'] | None = None, mem: bool = False) → SFG

Generate an SFG for the analytical block matrix inverse algorithm.

Parameters:
Nint

Dimension of the square input matrix.

namestr, optional

The name of the SFG. If None, “Analytical block matrix-inversion”.

modestr, default: “mid”

The mode of operation, either “top”, “bot”, or “mid”.

pestr, optional

Processing element to use. Can be “mads”, “addsub”, or None.

membool, default: False

Use MemoryRead and MemoryWrite instead of Input and Output. Input and inverse entries use packed lower-triangular row order in the default unnamed memory: entry \((i, j)\) has address \(\frac{i(i+1)}{2} + j\) for \(i \ge j\). Each matrix occupies \(\frac{N(N+1)}{2}\) locations.

Returns:
SFG

Signal Flow Graph

b_asic.sfg_generators.bitonic_sort(size: int) → SFG

Generate a Batcher bitonic sorting network with ascending outputs.

Parameters:
sizeint

Positive number of inputs and outputs. Sizes other than powers of two are supported by pruning a network for the next power of two.

Returns:
SFG

Sorting network built from Comparator.

b_asic.sfg_generators.block_cholesky_matrix_inverse(N: int, name: str | None = None, mode: Literal['eqs', 'mult'] = 'eqs', pe: Literal['addsub', 'mads'] | None = None, mem: bool = False) → SFG

Generate an SFG for the block Cholesky matrix inverse algorithm.

Parameters:
Nint

Dimension of the square input matrix.

namestr, optional

The name of the SFG. If None, “Block Cholesky matrix-inversion”.

modestr, default: “eqs”

The mode of operation, either “mult” or “eqs”.

pestr, optional

Processing element to use. Can be “mads”, “addsub”, or None.

membool, default: False

Use MemoryRead and MemoryWrite instead of Input and Output. Input and inverse entries use packed lower-triangular row order in the default unnamed memory: entry \((i, j)\) has address \(\frac{i(i+1)}{2} + j\) for \(i \ge j\). Each matrix occupies \(\frac{N(N+1)}{2}\) locations.

Returns:
SFG

Signal Flow Graph

b_asic.sfg_generators.block_ldlt_matrix_inverse(N: int, name: str | None = None, mode: Literal['eqs', 'mult'] = 'eqs', pe: Literal['addsub', 'mads'] | None = None, mem: bool = False) → SFG

Generate an SFG for the block LDLT matrix inverse algorithm.

Parameters:
Nint

Dimension of the square input matrix.

namestr, optional

The name of the SFG. If None, “Block LDLT matrix-inversion”.

modestr, default: “eqs”

The mode of operation, either “mult” or “eqs”.

pestr, optional

Processing element to use. Can be “mads”, “addsub”, or None.

membool, default: False

Use MemoryRead and MemoryWrite instead of Input and Output. Input and inverse entries use packed lower-triangular row order in the default unnamed memory: entry \((i, j)\) has address \(\frac{i(i+1)}{2} + j\) for \(i \ge j\). Each matrix occupies \(\frac{N(N+1)}{2}\) locations.

Returns:
SFG

Signal Flow Graph

b_asic.sfg_generators.bubble_sort(size: int) → SFG

Generate a bubble/insertion sorting network with ascending outputs.

Parameters:
sizeint

Positive number of inputs and outputs.

Returns:
SFG

Sorting network with size * (size - 1) / 2 comparators.

See also

insertion_sort
b_asic.sfg_generators.cholesky_matrix_inverse(N: int, name: str | None = None, mode: Literal['eqs', 'mult'] = 'eqs', pe: Literal['addsub', 'mads'] | None = None, mem: bool = False) → SFG

Generate an SFG for the Cholesky matrix inverse algorithm.

Parameters:
Nint

Dimension of the square input matrix.

namestr, optional

The name of the SFG. If None, “Cholesky matrix-inversion”.

modestr, default: “eqs”

The mode of operation, either “mult” or “eqs”.

pestr, optional

Processing element to use. Can be “mads”, “addsub”, or None.

membool, default: False

Use MemoryRead and MemoryWrite instead of Input and Output. Input and inverse entries use packed lower-triangular row order in the default unnamed memory: entry \((i, j)\) has address \(\frac{i(i+1)}{2} + j\) for \(i \ge j\). Each matrix occupies \(\frac{N(N+1)}{2}\) locations.

Returns:
SFG

Signal Flow Graph

b_asic.sfg_generators.direct_form_1_iir(b: Sequence[complex], a: Sequence[complex], name: str | None = None, mult_properties: dict[str, int] | dict[str, dict[str, int]] | None = None, add_properties: dict[str, int] | dict[str, dict[str, int]] | None = None) → SFG

Generate a direct-form IIR filter of type I with coefficients a and b.

b_asic.sfg_generators.direct_form_2_iir(b: Sequence[complex], a: Sequence[complex], name: str | None = None, mult_properties: dict[str, int] | dict[str, dict[str, int]] | None = None, add_properties: dict[str, int] | dict[str, dict[str, int]] | None = None) → SFG

Generate a direct-form IIR filter of type II with coefficients a and b.

b_asic.sfg_generators.fir(coefficients: Sequence[complex], name: str | None = None, symmetric: bool = False, transposed: bool = False, mult_properties: dict[str, int] | dict[str, dict[str, int]] | None = None, add_properties: dict[str, int] | dict[str, dict[str, int]] | None = None) → SFG

Generate a signal flow graph of an FIR filter.

The coefficients parameter is a sequence of impulse response values:

coefficients = [h0, h1, h2, ..., hN]

Leading to the transfer function:

\[\sum_{i=0}^N h_iz^{-i}\]
Parameters:
coefficients1D-array

Coefficients to use for the FIR filter section.

nameName, optional

The name of the SFG. If None, “Direct-form FIR filter”.

symmetricbool, optional

Whether to generate a symmetric FIR structure.

transposedbool, optional

Whether to generate a transposed FIR structure.

mult_propertiesdictionary, optional

Properties passed to ConstantMultiplication.

add_propertiesdictionary, optional

Properties passed to Addition.

Returns:
SFG

Signal flow graph implementing the FIR filter with the given coefficients and structure options.

b_asic.sfg_generators.insertion_sort(size: int) → SFG

Generate an insertion sorting network with ascending outputs.

Parameters:
sizeint

Positive number of inputs and outputs.

Returns:
SFG

The same comparator network as bubble_sort().

b_asic.sfg_generators.lattice_wdf(coefficients: Sequence[float], name: str | None = None, only_adaptors: bool = False, adaptor_names: Sequence[str | None] | str | None = None) → SFG

Generate a signal flow graph of a lattice wave digital filter.

Parameters:
coefficients1D-array

Adaptor coefficients, interleaved between the two allpass branches.

namestr, optional

Name of the SFG. Defaults to "Lattice WDF".

only_adaptorsbool, optional

If True, use an adaptor for the final addition and scaling.

adaptor_namessequence of str or None, or str, optional

Names for each adaptor, parallel to coefficients, or a string prefix used to generate names as f"{adaptor_names}{idx}" based on coefficient position. Defaults to "a0", "a1", … based on coefficient position.

Returns:
SFG

Signal flow graph of the lattice WDF.

b_asic.sfg_generators.ldlt_matrix_inverse(N: int, name: str | None = None, mode: Literal['eqs', 'mult'] = 'eqs', pe: Literal['addsub', 'mads'] | None = None, mem: bool = False) → SFG

Generate an SFG for the LDLT matrix inverse algorithm.

Parameters:
Nint

Dimension of the square input matrix.

namestr, optional

The name of the SFG. If None, “LDLT matrix-inversion”.

modestr, default: “eqs”

The mode of operation, either “mult” or “eqs”.

pestr, optional

Processing element to use. Can be “mads”, “addsub”, or None.

membool, default: False

Use MemoryRead and MemoryWrite instead of Input and Output. Input and inverse entries use packed lower-triangular row order in the default unnamed memory: entry \((i, j)\) has address \(\frac{i(i+1)}{2} + j\) for \(i \ge j\). Each matrix occupies \(\frac{N(N+1)}{2}\) locations.

Returns:
SFG

Signal Flow Graph

b_asic.sfg_generators.matrix_multiplication(m: int, n: int | None = None, p: int | None = None, *, name: str | None = None, mad_properties: dict[str, int] | dict[str, dict[str, int]] | None = None, mem: bool = False) → SFG

Generate a structure for the multiplication of matrices A and B. Where A is of size \(m \times n\) and B \(n \times p\).

Parameters:
mint

Number of rows in A.

nint, optional

Number of columns in A (and rows in B). If None, use m.

pint, optional

Number of columns in B. If None, use m.

nameName, optional

The name of the SFG. If None, “Matrix-multiplication”.

mad_propertiesdictionary, optional

Properties passed to MAD.

membool, default: False

Use MemoryRead and MemoryWrite instead of Input and Output. Matrices use separate memories named A, B, and C, in row-major order starting at address zero. Entry \(A_{i,j}\) has address \(in + j\); entries \(B_{i,j}\) and \(C_{i,j}\) have address \(ip + j\). Memory sizes are \(mn\), \(np\), and \(mp\), respectively.

Returns:
SFG

Signal Flow Graph

b_asic.sfg_generators.odd_even_merge_sort(size: int) → SFG

Generate a Batcher odd-even merge sorting network with ascending outputs.

Parameters:
sizeint

Positive number of inputs and outputs. Sizes other than powers of two are supported by pruning a network for the next power of two.

Returns:
SFG

Sorting network built from Comparator. This uses recursive odd-even merging, rather than odd-even transposition.

b_asic.sfg_generators.pairwise_sort(size: int) → SFG

Generate a Parberry pairwise sorting network with ascending outputs.

Parameters:
sizeint

Positive number of inputs and outputs. Sizes other than powers of two are supported by pruning a network for the next power of two.

Returns:
SFG

Sorting network built from Comparator.

References

[1]

Ian Parberry, “The Pairwise Sorting Network”, Parallel Processing Letters, 2(2,3), 205-211, 1992. https://ianparberry.com/pubs/pairwise.pdf

b_asic.sfg_generators.radix_2_dif_fft(points: int, mem: bool = False) → SFG

Generate a radix-2 decimation-in-frequency FFT structure.

Parameters:
pointsint

Number of points for the FFT, needs to be a positive power of 2.

membool, default: False

Use MemoryRead and MemoryWrite instead of Input and Output operations. Each memory address is the corresponding sample index.

Returns:
SFG

Signal Flow Graph

b_asic.sfg_generators.richards(coefficients: float | Sequence[float], name: str | None = None, latency: int | None = None, latency_offsets: dict[str, int] | None = None, execution_time: int | None = None, adaptor_names: Sequence[str | None] | str | None = None) → SFG

Generate a Richards structure using symmetric two-port adaptors.

Zero-valued adaptors are simplified using constant propagation.

Parameters:
coefficientsfloat or 1D-array

Adaptor coefficients, from the outermost to the innermost adaptor. A scalar generates a first-order section. For two coefficients [a, b], the denominator in powers of z**-1 is [1, b * (a - 1), -a] and the numerator is its reverse. For one coefficient a, the denominator is [1, -a]. Each additional coefficient nests another adaptor behind the previous adaptor’s delay, increasing the order by one.

nameName, optional

The name of the SFG. If None, “Richards structure”.

latencyint, optional

Latency of the symmetric two-port adaptors.

latency_offsetsoptional

Latency offsets of the symmetric two-port adaptors.

execution_timeint, optional

Execution time of the symmetric two-port adaptors.

adaptor_namessequence of str or None, or str, optional

Names for each adaptor, parallel to coefficients, or a string prefix used to generate names as f"{adaptor_names}{idx}" based on coefficient position. Defaults to "a0", "a1", … based on coefficient position.

Returns:
SFG

Signal Flow Graph

b_asic.sfg_generators.shell_sort(size: int) → SFG

Generate a Shell sorting network using Pratt’s gaps, with ascending outputs.

Parameters:
sizeint

Positive number of inputs and outputs.

Returns:
SFG

Sorting network using descending gaps of the form 2**p * 3**q. Each gap uses two stages of disjoint compare-exchanges, giving O(size * log(size)**2) comparators and O(log(size)**2) depth.

References

[1]

Vaughan R. Pratt, “Shellsort and Sorting Networks”, Stanford University Computer Science Department, report STAN-CS-72-260, 1972.

b_asic.sfg_generators.strassen_matrix_multiplication(m: int, n: int | None = None, p: int | None = None, *, name: str | None = None, mult_properties: dict[str, int] | dict[str, dict[str, int]] | None = None, add_properties: dict[str, int] | dict[str, dict[str, int]] | None = None, sub_properties: dict[str, int] | dict[str, dict[str, int]] | None = None, mem: bool = False) → SFG

Generate a Strassen matrix multiplication SFG for A of size \(m \times n\) and B of size \(n \times p\).

Parameters:
mint

Positive number of rows in A.

nint, optional

Positive number of columns in A and rows in B. If None, use m.

pint, optional

Positive number of columns in B. If None, use m.

namestr, optional

SFG name. Defaults to “Strassen matrix-multiplication”.

mult_propertiesdictionary, optional

Properties passed to every Multiplication, such as latency, latency_offsets, and execution_time.

add_propertiesdictionary, optional

Properties passed to every Addition.

sub_propertiesdictionary, optional

Properties passed to every Subtraction. If omitted, use add_properties for subtractions as well.

membool, default: False

Use MemoryRead and MemoryWrite instead of Input and Output. Matrices use separate memories named A, B, and C, in row-major order starting at address zero. Entry \(A_{i,j}\) has address \(in + j\); entries \(B_{i,j}\) and \(C_{i,j}\) have address \(ip + j\). Memory sizes are \(mn\), \(np\), and \(mp\), respectively. Padding is internal and occupies no memory locations.

Returns:
SFG

Inputs are the elements of A followed by B, each in row-major order, named A[i,j] and B[i,j] with zero-based row and column indices. Outputs are the elements of \(C = AB\) in row-major order, named C[i,j].

Notes

Each dimension is independently zero-padded to the next power of two. Padding uses internal constants and adds no external inputs or outputs. Recursion uses seven block products until a block dimension is one, when conventional multiplication is used. Padding may add arithmetic operations; the graph is not guaranteed to be smaller than conventional multiplication.

References

[1]

V. Strassen, “Gaussian elimination is not optimal”, Numerische Mathematik, 13, 354-356, 1969. https://doi.org/10.1007/BF02165411

b_asic.sfg_generators.tile_ldlt_matrix_inverse(N: int, name: str | None = None, mode: Literal['eqs', 'mult'] = 'eqs', pe: Literal['addsub', 'mads'] | None = None, mem: bool = False) → SFG

Generate an SFG for the tile LDLT matrix inverse algorithm.

Parameters:
Nint

Dimension of the square input matrix.

namestr, optional

The name of the SFG. If None, “Tile LDLT matrix-inversion”.

modestr, default: “eqs”

The mode of operation, either “mult” or “eqs”.

pestr, optional

Processing element to use. Can be “mads”, “addsub”, or None.

membool, default: False

Use MemoryRead and MemoryWrite instead of Input and Output. Input and inverse entries use packed lower-triangular row order in the default unnamed memory: entry \((i, j)\) has address \(\frac{i(i+1)}{2} + j\) for \(i \ge j\). Each matrix occupies \(\frac{N(N+1)}{2}\) locations.

Returns:
SFG

Signal Flow Graph

b_asic.sfg_generators.wdf_allpass(coefficients: float | Sequence[float], name: str | None = None, latency: int | None = None, latency_offsets: dict[str, int] | None = None, execution_time: int | None = None, adaptor_names: Sequence[str | None] | str | None = None) → SFG

Generate a WDF allpass filter as a cascade of Richards structures.

An odd-order filter starts with a first-order section, followed by second-order sections. Adaptors with zero coefficients are simplified.

Parameters:
coefficientsfloat or 1D-array

Adaptor coefficients, grouped into consecutive sections.

namestr, optional

Name of the SFG. Defaults to "WDF allpass section".

latencyint, optional

Latency of the symmetric two-port adaptors.

latency_offsetsdict, optional

Latency offsets of the symmetric two-port adaptors.

execution_timeint, optional

Execution time of the symmetric two-port adaptors.

adaptor_namessequence of str or None, or str, optional

Names parallel to coefficients, or a prefix used to generate names based on coefficient position. Defaults to "a0", "a1", …

Returns:
SFG

Flat signal flow graph of the allpass filter.

See also

richards

Generate a single Richards structure of arbitrary order.