6
\$\begingroup\$

This is part of my homework on digital logic design, so I would like to present some technical background first.

Quine–McCluskey algorithm is a method for minimizing Boolean functions. Given the truth table of a Boolean function, it tries to find the simplest sum-of-product to represent that function.

For example, the Boolean function \$ F_{xyz}=xy' + yz \$ has the following truth table:

     X   Y   Z   F
0    0   0   0   0
1    0   0   1   0
2    0   1   0   0
3    0   1   1   1
4    1   0   0   1
5    1   0   1   1
6    1   1   0   0
7    1   1   1   1

From the truth table, we can write the DNF(disjunctive normal form) of the Boolean function, which is a sum-of-product of all the rows where \$F = 1\$.

\$ F_{xyz}= x'yz + xy'z' + xy'z + xyz \$

Often, the DNF is represented by simply listing the index of the terms. For example, the previous function could be expressed as \$ \sum m(3,4,5,7) \$.

The Quine–McCluskey algorithm starts from DNF and ends with the simplied form, \$ F_{xyz}=xy' + yz \$.

Some more jargon:

  • A minterm is a product where each variables appears once, like \$xy'z\$
  • An implicant is a product that is not necessarily a minterm, like \$xy'\$. Implicants can be obtained by combining minterms or other implicants(e.g. \$xy'z + xy'z'\$)
  • A prime implicant is an implicant which, when you have a bunch of implicants at hand, cannot be combined with any others to obtain simpler implicants.

That should make it easier to understand the algorithm.


Now the code part. I implemented a reduced version of the algorithm. There're no "don't care" inputs. The implementation assumes that the "prime implicant chart" part of the problem can be solved via greedy algorithm, otherwise we just give up and throw an exception.

I'm mainly concerned about two aspect of the code, but any suggestions or improvements are welcome!

  • Frozensets. Python distinguishes between "normal" sets, which is mutable thus cannot be contained in a set, and frozensets. As I want to have sets within sets, I basically littered frozensets everywhere, sometimes mixing them with normal sets. Is this OK? Is there a better way to do this?
  • Data abstraction. I exposed the implementation of an implicant(a tuple of a string and a set), which can make it hard to change it later on. In fact, I originally designed it that it is just a string, and later changed it, which involves a lot of search/replace. What's the proper way to solve this problem?(I know a little about OOP abstractions, but I usually find them verbose and brittle and hard to design well.)

# An implicant consists of two parts in a tuple:
#   - A string consisting of 0, 1, and dash
#   - A set of numbers representing the minterms

# Construct an implicant from its index in the truth table.
# [var_cnt] number of variables in the truth table.
# [index] its index in the truth table.
def implicant_from_index(var_cnt, index):
    return (
        bin(index)[2:].rjust(var_cnt, "0"),
        frozenset({index}),
    )


# Combines two implicants.
# Returns the combined implicant, or False if they cannot be combined.
# For example, combining "10-1" and "10-0" gives us "10--".
def combine(implicant_a, implicant_b):
    str_a, nums_a = implicant_a
    str_b, nums_b = implicant_b

    def combine_str(str_a, str_b):
        assert len(str_a) == len(str_b)
        assert str_a != str_b

        if len(str_a) == 0 and len(str_b) == 0:
            return ""

        head_a, *rest_a = str_a
        head_b, *rest_b = str_b

        if head_a == head_b:
            combined = combine_str(rest_a, rest_b)
            if combined:
                return head_a + combined
            else:
                return False

        elif {head_a, head_b} == {"0", "1"} and rest_a == rest_b:
            return "-" + "".join(rest_a)

        else:
            return False

    combined_str = combine_str(str_a, str_b)
    if combined_str:
        return combined_str, nums_a.union(nums_b)
    else:
        return False


# Find a set of prime implicants from DNF(disjunctive normal form).
# [var_cnt] the number of variables.
# [minterms] a list of intergers representing the boolean function in DNF.
def find_prime_implicants(var_cnt, minterms):
    def iter(implicants):
        if len(implicants) == 0:
            return set()

        unused_implicants = implicants.copy()
        resulting_implicants = set()
        for term_a in implicants:
            for term_b in implicants:
                if term_a != term_b:
                    combined = combine(term_a, term_b)
                    if combined:
                        unused_implicants.discard(term_a)
                        unused_implicants.discard(term_b)
                        resulting_implicants.add(combined)
        return unused_implicants.union(iter(resulting_implicants))

    return iter({implicant_from_index(var_cnt, minterm) for minterm in minterms})


# Union in function form.
# It also converts normal set to frozensets.
# [sets] an iterable of sets to be unioned.
def union(*sets):
    return frozenset().union(frozenset(s) if isinstance(s, set) else s for s in sets)


# Select a minimum set of sets that cover their union.
# This is a NP-complete problem.
# Instead of implementing a proper algorithm that runs in exponential time, we just try some greedy method and give up if a solution cannot be found.
# [sets] an iterable of sets to be covered.
# [ignore_values] a set of values that should be excluded from the union. This argument is just for easy implementation.
def minimum_cover(sets, ignore_values=frozenset()):
    # Remove "empty" sets.
    sets = frozenset(
        s for s in sets if len([x for x in s if x not in ignore_values]) > 0
    )

    if len(sets) == 0:
        return frozenset()

    # Remove sets that are completely covered("shadowed") by another set.
    sets = frozenset(s for s in sets if not any(s < t for t in sets))

    # Try find a value that is only covered by one set.
    for v in union(*sets) - ignore_values:
        for s in sets:
            if v not in union(t - s for t in sets):
                # Gotcha
                return minimum_cover(
                    sets - frozenset({s}), ignore_values=ignore_values.union(s)
                ).union({s})

    # Worst case: non of the values are only covered by one set.
    # We give up.
    raise Exception()


# Run the argorithm and print the result.
# [vars] variable names of the boolean function.
# [minterms] a list of intergers representing the boolean function in DNF(disjunctive normal form)
def qm_algorithm(vars, minterms):
    prime_implicants = find_prime_implicants(len(vars), minterms)
    sets = frozenset(implicant[1] for implicant in prime_implicants)
    cover = minimum_cover(sets)

    strs = [implicant[0] for implicant in prime_implicants if implicant[1] in cover]
    terms = [
        "".join(
            {"0": vars[i] + "'", "1": vars[i], "-": "",}[char]
            for i, char in enumerate(str)
        )
        for str in strs
    ]
    print("sigma(", end="")
    print(*minterms, sep=", ", end="")
    print(") => ", end="")
    print(*terms, sep=" + ")

Test code:

qm_algorithm("XYZ", [3, 4, 5, 7])  # YZ + XY'
qm_algorithm("XYZ", [1, 3, 5, 6, 7])  # XY + Z
qm_algorithm("ABCD", [0, 2, 4, 8, 10, 11, 15])  # ACD + B'D' + A'C'D'
qm_algorithm("WXYZ", [0, 1, 3, 5, 14, 15])  # W'X'Y' + W'Y'Z + W'X'Z + WXY
\$\endgroup\$
  • \$\begingroup\$ Welcome to CodeReview@SE! What size functions do you intend to handle? Back in the day, we ran into layout&routing nightmares long before exceeding 32 bits, not to mention fan-in and fan-out limitations and processing time. \$\endgroup\$ – greybeard Mar 18 at 16:21
  • \$\begingroup\$ (Are you aware of Duşa, Adrian: Enhancing Quine-McCluskey?) \$\endgroup\$ – greybeard Mar 18 at 16:32
  • 1
    \$\begingroup\$ (What we did use when we could lay hands on it was Espresso. Funny I should forget about "multiple-valued variables".) \$\endgroup\$ – greybeard Mar 18 at 16:48
  • \$\begingroup\$ @greybeard Could you tell me what is a "size function"? Do you mean how many variables we need to process? This is part of my homework to enhance my understanding of the algorithm and not meant to be practical. I'm mainly concerned about the implementation details of the code. Thanks for the additional pointers though. \$\endgroup\$ – Yizhe Sun Mar 19 at 2:42
  • \$\begingroup\$ Not size function, but size of the boolean function. E.g. number of variables + number of terms in the minimised function. \$\endgroup\$ – greybeard Mar 19 at 5:43
3
\$\begingroup\$

Function signatures

This:

def combine(implicant_a, implicant_b):
    str_a, nums_a = implicant_a
    str_b, nums_b = implicant_b

should go in one of two directions:

  • Unpack the arguments themselves, i.e. def combine(str_a, nums_a, str_b, nums_b); or
  • Make some kind of named tuple:
def combine(implicant_a, implicant_b):
    # Refer to implicant_a.str and implicant_a.nums

This combine function also has a problematic return type - mixed boolean-or-combined-implicant. Returning False on failure is a C-ism. In Python, the saner thing to do is raise an exception, and then catch it (or not) in the calling code.

Do not shadow built-ins

def iter(implicants):

should have a different name, because iter is already a thing.

Specific exceptions

raise Exception()

is going to make it effectively impossible to meaningfully catch this exception and distinguish it from others. You should use a narrower built-in at least (perhaps ValueError), or more likely define your own exception. This can be done in two lines and makes the job of the caller much easier.

Tests

You have tests; that's good! You should actually apply asserts to them so that they can be quickly run as a sanity check.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.