Canalization

Boolean Canalization

Functions to compute the Quine-McCluskey algorithm.

cana.canalization.boolean_canalization.computes_pi_coverage(k, outputs, prime_implicants)[source]

Computes the input coverage by Prime Implicant schematas.

Parameters
  • k (int) – the number of inputs.

  • outpus (list) – the list of transition outputs.

  • prime_implicants (tuple) – a tuple containing a list negative and positive prime implicants. This is returned by find_implicants_qm.

Returns

a dictionary of coverage where keys are input states and values are lists of the Prime Implicants covering that input.

Return type

pi_coverage (dict)

Note: based on code from Alex Gates and Etienne Nzabarushimana.

cana.canalization.boolean_canalization.computes_ts_coverage(k, outputs, two_symbols)[source]

Computes the input coverage by Two Symbol schematas.

Parameters
  • k (int) – the number of inputs.

  • outpus (list) – the list of transition outputs.

  • two_symbols (list) – The final list of Two Symbol permutable schematas. This is returned by find_two_symbols.

Returns

a dictionary of coverage where keys are inputs states and values are lists of the Two Symbols covering that input.

Return type

coverage (dict)

cana.canalization.boolean_canalization.find_implicants_qmOLD(column, verbose=False)[source]

Finds the prime implicants (PI) using the Quine-McCluskey algorithm [Qui55].

Parameters

column (list) – A list-of-lists containing the counts of 1 for each input. This is given by make_transition_density_tables.

Returns

a set of prime implicants.

Return type

PI (set)

# Authors: Alex Gates and Etienne Nzabarushimana

cana.canalization.boolean_canalization.find_two_symbols_v2(k=1, prime_implicants=None, verbose=False, verbose_level=0)[source]

This function calculates the permutation, two-symbol (TS), list of schematas. This implementation considers ‘11’ and ‘00’ as a possible input permutation.

Parameters
  • k (int) – The number of inputs.

  • prime_implicants (list) – The prime implicants computed.

Returns

The list of two-symbol schematas.

Return type

final_list (list)

Note: This is a modification of the original algorithm that can be found in Marques-Pita & Rocha [2013].

cana.canalization.boolean_canalization.make_transition_density_tables(k=1, outputs=[0, 1])[source]

This method creates a tuple-of-lists that is used to calculate Prime Implicants in the first step of the Quine-McCluskey algorithm [Qui55]. In practice it separates the positive and negative transitions (tuple), then further separates it by counting the number of 1’s in each (lists).

Parameters
  • k (int) – the k number of inputs

  • outputs (list) – a list of [0,1] output for each state number.

Returns

a tuple where [0] is the negative table and [1] is the positive table.

Return type

tables (tuple)