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
MemoryReadandMemoryWriteinstead ofInputandOutput. 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:
SFGSignal 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:
SFGSorting 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
MemoryReadandMemoryWriteinstead ofInputandOutput. 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:
SFGSignal 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
MemoryReadandMemoryWriteinstead ofInputandOutput. 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:
SFGSignal 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:
SFGSorting network with
size * (size - 1) / 2comparators.
See also
- 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
MemoryReadandMemoryWriteinstead ofInputandOutput. 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:
SFGSignal 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.
- name
Name, 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:
SFGSignal 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:
SFGThe 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 asf"{adaptor_names}{idx}"based on coefficient position. Defaults to"a0","a1", … based on coefficient position.
- Returns:
SFGSignal 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
MemoryReadandMemoryWriteinstead ofInputandOutput. 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:
SFGSignal 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.
- name
Name, optional The name of the SFG. If None, “Matrix-multiplication”.
- mad_propertiesdictionary, optional
Properties passed to
MAD.- membool, default: False
Use
MemoryReadandMemoryWriteinstead ofInputandOutput. Matrices use separate memories namedA,B, andC, 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:
SFGSignal 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:
SFGSorting 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:
SFGSorting 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
MemoryReadandMemoryWriteinstead ofInputandOutputoperations. Each memory address is the corresponding sample index.
- Returns:
SFGSignal 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 ofz**-1is[1, b * (a - 1), -a]and the numerator is its reverse. For one coefficienta, the denominator is[1, -a]. Each additional coefficient nests another adaptor behind the previous adaptor’s delay, increasing the order by one.- name
Name, 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 asf"{adaptor_names}{idx}"based on coefficient position. Defaults to"a0","a1", … based on coefficient position.
- Returns:
SFGSignal 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:
SFGSorting network using descending gaps of the form
2**p * 3**q. Each gap uses two stages of disjoint compare-exchanges, givingO(size * log(size)**2)comparators andO(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 aslatency,latency_offsets, andexecution_time.- add_propertiesdictionary, optional
Properties passed to every
Addition.- sub_propertiesdictionary, optional
Properties passed to every
Subtraction. If omitted, useadd_propertiesfor subtractions as well.- membool, default: False
Use
MemoryReadandMemoryWriteinstead ofInputandOutput. Matrices use separate memories namedA,B, andC, 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:
SFGInputs are the elements of A followed by B, each in row-major order, named
A[i,j]andB[i,j]with zero-based row and column indices. Outputs are the elements of \(C = AB\) in row-major order, namedC[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
MemoryReadandMemoryWriteinstead ofInputandOutput. 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:
SFGSignal 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:
SFGFlat signal flow graph of the allpass filter.
See also
richardsGenerate a single Richards structure of arbitrary order.