circuitdb module

Data set of optimal circuits for Boolean functions that have low arity.

class circuitdb.circuitdb.record

Bases: bytes

Wrapper class for an individual record (i.e., encoded data corresponding to a circuit).

static from_circuit(circuit: circuit.circuit.circuit) → circuitdb.circuitdb.record

Encode a circuit object and construct a record that represents it.

>>> c = circuit.circuit()
>>> g0 = c.gate(logical.id_, is_input=True)
>>> g1 = c.gate(logical.id_, is_input=True)
>>> g2 = c.gate(logical.id_, is_input=True)
>>> g3 = c.gate(logical.xor_, [g0, g2])
>>> g4 = c.gate(logical.nimp_, [g1, g3])
>>> g5 = c.gate(logical.id_, [g4], is_output=True)
>>> record.from_circuit(c).to_base64()
'CQACBAEDBgQ='

static from_base64(string: str) → circuitdb.circuitdb.record

Construct an instance from a Base64-encoded string representation of a record.

>>> record.from_base64('CQACBAEDBgQ=').hex()
'0900020401030604'

to_circuit(truthtable: Union[Tuple[int, ...], Tuple[Tuple[int, ...], ...]]) → circuit.circuit.circuit

Decode this record into a circuit object.

>>> c = record.from_base64('CQACBAEDBgQ=').to_circuit((0, 0, 1, 0, 0, 0, 0, 1))
>>> c.gates.to_legible()
(('id',), ('id',), ('id',), ('xor', 0, 2), ('nimp', 1, 3), ('id', 4))

to_base64() → str

Convert this instance into a Base64-encoded string representation.

>>> c = circuit.circuit()
>>> g0 = c.gate(logical.id_, is_input=True)
>>> g1 = c.gate(logical.not_, [g0])
>>> g2 = c.gate(logical.id_, [g1], is_output=True)
>>> record.from_circuit(c).to_base64()
'DAAGAQ=='

class circuitdb.circuitdb.records(iterable=(), /)

Bases: list

Wrapper class for a base-level operation-to-circuit map (corresponding to a fixed combination of arity, coarity, operator set, and operator set to minimize).

static from_file(resource: str) → circuitdb.circuitdb.records

Construct an instance from a binary file of circuit data (where the specified resource is either a package resource of this package or a file path).

>>> len(records.from_file('3_1_every_every'))
256

to_file(path: str)

Write the data in this instance to a binary file.

>>> rs = records.from_file('3_1_every_every')
>>> rs.to_file('test-output-records.to_file')
>>> len(records.from_file('test-output-records.to_file'))
256
>>> os.remove('test-output-records.to_file')

__getitem__(truthtable: Union[Tuple[int, ...], Tuple[Tuple[int, ...], ...]]) → circuitdb.circuitdb.record

Data retrieval wrapper that performs normalization of the truth table, but does not check that it has a correct structure. To ensure the supplied truth table representation is valid, the circuitdb.__call__ should be used to retrieve circuit data.

class circuitdb.circuitdb.circuitdb

Bases: dict

Wrapper class for a circuit data set that contains an (arbitrary but fixed) example of the smallest possible logical circuit (in terms of the number of unary and/or binary gates) for each possible logical function (from a finite set of functions). This class supports both a dictionary-like interface (inherited from the dict type) and a function-like interface (via the __call__ method).

Logical Function Representation: Logical functions are represented using tuples in an identical manner to that of the logical class defined in the logical library. For example, the logical function f (x, y, z) = x and y and z (i.e., three-argument conjunction) is represented using a tuple representation of the output column of the truth table for the function (assuming that the possible inputs are in ascending dictionary order): (0, 0, 0, 0, 0, 0, 0, 1).

>>> circuitdb((0, 0, 0, 0, 0, 0, 0, 1)).gates.to_legible()
(('id',), ('id',), ('id',), ('and', 0, 1), ('and', 2, 3), ('id', 4))

For logical functions having multiple outputs, the entries in the tuple may themselves be tuples. For example, f (x, y) = (y, x) is represented using the tuple ((0, 0), (1, 0), (0, 1), (1, 1)).

>>> circuitdb(((0, 0), (1, 0), (0, 1), (1, 1))).gates.to_legible()
(('id',), ('id',), ('id', 1), ('id', 0))

Circuit Representation: Retrieved circuits are instances of the circuit class that is defined in the circuit library. In order to make this documentation human-readible, the examples include an invocation of the to_legible method belonging to the gate list associated with the returned circuit object. This representation of a circuit consists of a list of unary and binary gates. Each gate is represented as a tuple. The first entry in each gate tuple is the name of the logical function corresponding to that gate (as defined in the names class attribute in the logical library). The remaining entries in the gate tuple are the indices of the input gates to that gate.

>>> circuitdb((0, 0, 0, 0, 0, 0, 0, 1)).gates.to_legible()
(('id',), ('id',), ('id',), ('and', 0, 1), ('and', 2, 3), ('id', 4))

In the circuit above, the entry ('and', 2, 3) represents a gate that is a conjunction of the gates at positions 2 and 3 in the overall list (i.e. , ('id',) and ('and', 0, 1)).

Set of Permitted Gates: For any given logical function, it is possible to construct a corresponding circuit using a variety of gate sets. For each logical function, the database contains an example of a smallest circuit for each of a small collection of sets of unary and binary gates. The set of gates that can be used to construct a circuit can be supplied using the operators parameter. In the remaining examples below, circuits are retrieved for the specific function (0, 0, 1, 0, 0, 0, 0, 1). The unary and binary logical operators represented by the gates in the circuit below are drawn from the set of permitted gates {logical.id_, logical.not_, logical.and_, logical.or_}.

>>> from logical import logical
>>> for g in circuitdb(
...     (0, 0, 1, 0, 0, 0, 0, 1),
...     frozenset({logical.id_, logical.not_, logical.and_, logical.or_})
... ).gates.to_legible():
...     print(g)
('id',)
('id',)
('id',)
('and', 0, 2)
('or', 0, 2)
('not', 4)
('or', 3, 5)
('and', 1, 6)
('id', 7)

All gates in the circuit below are found in the set {logical.id_, logical.not_, logical.and_, logical.xor_}.

>>> for g in circuitdb(
...     (0, 0, 1, 0, 0, 0, 0, 1),
...     frozenset({logical.id_, logical.not_, logical.and_, logical.xor_})
... ).gates.to_legible():
...     print(g)
('id',)
('id',)
('id',)
('not', 0)
('xor', 2, 3)
('and', 1, 4)
('id', 5)

By default (or if the set of all gates is supplied using the constant every that is defined in the logical), a smallest circuit that can be built using any combination of unary or binary gates is returned.

>>> circuitdb((0, 0, 1, 0, 0, 0, 0, 1)).gates.to_legible()
(('id',), ('id',), ('id',), ('xor', 0, 2), ('nimp', 1, 3), ('id', 4))
>>> circuitdb((0, 0, 1, 0, 0, 0, 0, 1), logical.every).gates.to_legible()
(('id',), ('id',), ('id',), ('xor', 0, 2), ('nimp', 1, 3), ('id', 4))

Set of Gates to Minimize: Multiple possible circuits that use gates from a given gate set can be used to implement a logical function. Some of these circuits may have more of one type of gate than other circuits. Thus, there is an option to specify using the minimize parameter which gates do contribute to the size of the circuit (i.e., the metric that is being minimized). All other gates are not counted for the purposes of comparing circuits according to their size.

>>> for g in circuitdb(
...     (0, 0, 1, 0, 0, 0, 0, 1),
...     frozenset({logical.id_, logical.not_, logical.and_, logical.xor_}), {logical.and_}
... ).gates.to_legible():
...     print(g)
('id',)
('id',)
('id',)
('not', 0)
('xor', 2, 3)
('and', 1, 4)
('id', 5)

Supported Combinations: Each logical function has a number of input values, a number of output values, a set of permitted gates/operators, and a set of gates to minimize in quantity. Entries exist in the database for only a finite set of logical functions. The table below lists the supported combinations of function input count, function output count, and gate set that are found in the database. All functions for a given combination of inputs and outputs are supported (e.g., all 2**(2**3) = 256 functions having three inputs and one output are supported). Gate sets are defined using operator constants found in the logical library).

inputs	outputs	operators	minimize
1	1	{id_, not_, and_, or_}	{id_, not_, and_, or_}
1	1	{id_, not_, and_, xor_}	{and_}
1	1	every	every
2	1	{id_, not_, and_, or_}	{id_, not_, and_, or_}
2	1	{id_, not_, and_, xor_}	{and_}
2	1	every	every
2	2	{id_, not_, and_, or_}	{id_, not_, and_, or_}
2	2	{id_, not_, and_, xor_}	{and_}
2	2	every	every
3	1	{id_, not_, and_, or_}	{id_, not_, and_, or_}
3	1	{id_, not_, and_, xor_}	{and_}
3	1	every	every

The database supports retrieval using index notation, as well.

>>> ops = logical.every
>>> circuitdb[1][1][ops][ops][(0, 0)].gates.to_legible()
(('id',), ('uf', 0), ('id', 1))
>>> circuitdb[1][1][ops][ops][((0,), (0,))].gates.to_legible()
(('id',), ('uf', 0), ('id', 1))

The top-level database instance has keys that represent to the number of inputs of the logical function. The second level down, the keys represent the number of outputs of a logical function. The third level down, keys represent the set of unary or binary gates to which circuits are restricted. Finally, the last level down, the keys represent logical functions.

>>> list(sorted(list(circuitdb.keys()))) == [0, 1, 2, 3]
True
>>> ks = list(sorted(list(circuitdb[1][1].keys())))
>>> ks[0] == frozenset({logical.and_, logical.or_, logical.not_, logical.id_})
True
>>> circuitdb[2][1][ks[0]][ks[0]][(1,1,1,1)].gates.to_legible()
(('id',), ('id',), ('not', 0), ('or', 0, 2), ('id', 3))

Note that the internal representation organizes the circuits by arity.

>>> _d = {i: _db[i][1] for i in range(1,4)}
>>> all(len(_d[1][o][m]) == 4 for o in _d[1] for m in _d[1][o])
True
>>> all(len(_d[2][o][m]) == 16 for o in _d[2] for m in _d[2][o])
True
>>> all(len(_d[3][o][m]) == 256 for o in _d[3] for m in _d[3][o])
True

__call__(truthtable: Union[Tuple[int, ...], Tuple[Tuple[int, ...], ...]], operators: Optional[AbstractSet[logical.logical.logical]] = None, minimize: Optional[AbstractSet[logical.logical.logical]] = None) → circuit.circuit.circuit

Function-like interface for the circuit database, with user-friendly defaults for retrieving circuit data.

By supplying a logical function (represented as a tuple), it is possible to retrieve a smallest circuit that implements that function. Logical functions having one output are represented using a tuple of integers (or booleans), or a tuple of one-element tuples.

>>> circuitdb((0, 0)).gates.to_legible()
(('id',), ('uf', 0), ('id', 1))
>>> circuitdb(((0,), (0,))).gates.to_legible()
(('id',), ('uf', 0), ('id', 1))
>>> circuitdb((False, False)).gates.to_legible()
(('id',), ('uf', 0), ('id', 1))

A logical function having a vector of two outputs is represented using a tuple of two-element tuples.

>>> circuitdb(((1, 0), (1, 0), (1, 0), (0, 1))).gates.to_legible()
(('id',), ('id',), ('and', 0, 1), ('not', 2), ('id', 3), ('id', 2))

It is also possible to retrieve a smallest circuit that only uses gates from a specific set of gates.

>>> circuitdb(
...     (0, 0, 0, 0, 0, 0, 0, 0),
...     {logical.id_, logical.not_, logical.and_, logical.or_}
... ).gates.to_legible()
(('id',), ('id',), ('id',), ('not', 0), ('and', 0, 3), ('id', 4))

Any attempt to access the data with a malformed key raises an exception.

>>> circuitdb([0, 0, 0, 0])
Traceback (most recent call last):
  ...
TypeError: truth table must be a tuple
>>> circuitdb((0, 0, 0))
Traceback (most recent call last):
  ...
ValueError: truth table must have a length that is a power of two
>>> circuitdb(('abc', 'xyz'))
Traceback (most recent call last):
  ...
TypeError: truth table must contain boolean values, integers in the range ... of such
>>> circuitdb((('abc', 'xyz')))
Traceback (most recent call last):
  ...
TypeError: truth table must contain boolean values, integers in the range ... of such
>>> circuitdb(((1, 'abc'), (1, 0), (1, 0), (0, 1)))
Traceback (most recent call last):
  ...
TypeError: truth table must contain boolean values, integers in the range ... of such
>>> circuitdb(((), ()))
Traceback (most recent call last):
  ...
ValueError: truth table entries must each represent at least one value
>>> circuitdb(((), (1, 0)))
Traceback (most recent call last):
  ...
ValueError: truth table entries must all have the same length
>>> circuitdb((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0))
Traceback (most recent call last):
  ...
ValueError: no entries for functions of arity 4
>>> circuitdb(((0,0,0), (1,1,1)))
Traceback (most recent call last):
  ...
ValueError: no entries for functions of arity 1 having output vectors of length 1
>>> circuitdb((0, 0, 0, 0, 0, 0, 0, 0), 132)
Traceback (most recent call last):
  ...
TypeError: collection of operators must be a set or frozenset
>>> circuitdb((0, 0, 0, 0, 0, 0, 0, 0), 132)
Traceback (most recent call last):
  ...
TypeError: collection of operators must be a set or frozenset
>>> circuitdb((0, 0, 0, 0, 0, 0, 0, 0), {(0, 1, 0)})
Traceback (most recent call last):
  ...
ValueError: collection of operators must only contain valid operators
>>> circuitdb((0, 0, 0, 0, 0, 0, 0, 0), {(0, 1)})
Traceback (most recent call last):
  ...
ValueError: no entries for functions of arity 3 that have only the specified operators
>>> id_not_and_or = {logical.id_, logical.not_, logical.and_, logical.or_}
>>> circuitdb((0, 0, 0, 0, 0, 0, 0, 0), id_not_and_or, 123)
Traceback (most recent call last):
  ...
TypeError: collection of operators the number of which to minimize must be a ... frozenset
>>> circuitdb((0, 0, 0, 0, 0, 0, 0, 0), id_not_and_or, {(0, 1, 0)})
Traceback (most recent call last):
  ...
ValueError: collection of operators the number of which to minimize must ... operators
>>> circuitdb((0, 0, 0, 0, 0, 0, 0, 0), id_not_and_or, {(0, 1)})
Traceback (most recent call last):
  ...
ValueError: no entries for functions of arity 3 for specified operators ... criteria

Additional exhaustive tests are presented below.

>>> from itertools import product
>>> evals = lambda c, a: tuple([c.evaluate(v)[0] for v in product(*[[0, 1]]*a)])
>>> _d = {i: _db[i][1] for i in range(1,4)}
>>> aoms = [(a, o, m) for a in _d for o in _d[a] for m in _d[a][o]]
>>> all(
...     all(t == evals(circuitdb(t, o, m), a) for t in product(*[[0, 1]]*(2**a)))
...     for (a, o, m) in aoms
... )
True
>>> evals = lambda c, a: tuple([tuple(c.evaluate(v)) for v in product(*[[0, 1]]*a)])
>>> aoms = [(a, o, m) for a in [2] for o in _db[a][2] for m in _db[a][2][o]]
>>> pairs = [(0, 0), (0, 1), (1, 0), (0, 1)]
>>> all(
...     all(t == evals(circuitdb(t, o, m), a) for t in product(*[pairs]*(2**a)))
...     for (a, o, m) in aoms
... )
True