Transformation-based synthesis (TBS)¶

Header: tweedledum/algorithms/synthesis/tbs.hpp

Transformation-based synthesis algorithms modify the input permutation by adding gates to the input or output side of a circuit in a way that the permutation becomes the identity. The gates collected in this process construct a reversible circuit realizing the permutation.

Parameters¶

struct tbs_params¶

Parameters for tbs.

Public Types

enum behavior¶

Variants of transformation-based synthesis.

Values:

unidirectional¶: Only adds gates from the output side. (default)

bidirectional¶: adds gates from input or output side at each step.

multidirectional¶

adds gates from input and output side at each step

(for more information see [SDRM16])

Public Members

behavior behavior = behavior::unidirectional: Algorithm behavior.

cost_fn_type cost_fn = [](auto& permutation, auto x, auto z) { return __builtin_popcount(z ^ x) + __builtin_popcount(x ^ permutation[z]); }¶

Cost function in multi-directional synthesis.

By default the number of reversible gates is used as cost function.

bool verbose = false¶: Be verbose.

Algorithm¶

template<typename Network> Network tweedledum::tbs(std::vector<uint32_t> permutation, tbs_params params = {})

Transformation-based reversible logic synthesis.

This algorithm implements various variants of the transformation-based synthesis algorithm originally proposed in [MMD03]. A permutation is specified as a vector of \(2^n\) different integers ranging from \(0\) to \(2^n-1\).

std::vector<uint32_t> permutation{{0, 2, 3, 5, 7, 1, 4, 6}};
auto network = tbs<netlist<io3_gate>>(permutation);

Parameters

permutation: A vector of different integers
params: Parameters (see tbs_params)

Warning

doxygenfunction: Unable to resolve multiple matches for function “tweedledum::tbs” with arguments (Network&, std::vector<io_id> const&, std::vector<uint32_t>, tbs_params) in doxygen xml output for project “tweedledum” from directory: doxyxml/xml. Potential matches:

- template<typename Network>
  Network tweedledum::tbs(std::vector<uint32_t>, tbs_params)
- template<typename Network>
  void tweedledum::tbs(Network&, std::vector<wire::id> const&, std::vector<uint32_t>, tbs_params)