Introduction to Computer Organization: ARM Assembly Language Using the Raspberry Pi

Section 5.3 Canonical (Standard) Forms

Some terminology and definitions at this point will help our discussion. Consider two dictionary definitions of “literal” from Merriam-Websters's Online Dictionary[18]:

literal

(1) Adhering to fact or to the ordinary construction of primary meaning of a term or expression : ACTUAL

(2) Of, relating to, or expressed in letters.

In programming we use the first definition of literal. For example, in the following C code sequence

int xyz = 123;
char a = 'b';
char *greeting = "Hello";

the number 123, the character 'b', and the string "Hello" are all literals. They are interpreted by the compiler exactly as written (without the quotation marks). On the other hand, xyz, a, and greeting are all names of variables. By the way, *greeting is a pointer variable that contains the address of the first characters in the text string, "Hello".

In mathematics we use the second definition of literal. That is, in the algebraic expression

the letters \(x\text{,}\) \(y\text{,}\) and \(z\) are called literals. It is common to omit the “\(\cdot\)” operator to designate multiplication. Similarly, it is often dropped in Boolean algebra expressions when the AND operation is implied.

The meaning of “literal” in Boolean algebra is slightly more specific.

literal

The presence of a variable or its complement in an expression.

For example, the expression

contains seven literals. From the context of the discussion you should be able to tell which meaning of “literal” is intended and when the “\(\cdot\)” operator is omitted.

A Boolean expression is created from the numbers \(\binary{0}\) and \(\binary{1}\text{,}\) and literals. Literals can be combined using either the “\(\cdot\)” or the “\(+\)” operators, which are multiplicative and additive operations, respectively.

Like elementary algebra, Boolean algebra expressions are made up of groups of terms.

Product Term

A term in which all the literals are connected with AND operators. AND is multiplicative, hence the use of “product.”

Sum of Products (SoP)

One or more product terms connected with OR operators. OR is additive, hence the use of “sum.”

Minterm or Standard Product Term

A product term that contains all the variables in the problem, either in its uncomplemented or complemented form. For example, if a problem involves three variables, \(x\text{,}\) \(y\text{,}\) and \(z\text{,}\) then \((x\cdot y\cdot z)\text{,}\) \((x' \cdot y \cdot z')\text{,}\) and \((x' \cdot y' \cdot z')\) are all minterms, but \((x\cdot y)\) is not.

Canonical Sum or Sum of Minterms (SoM)

a sum of products in which each product term is a minterm. Since all the variables are present in each minterm, the canonical sum is unique for a given problem.

A function that defines the solution to a problem can be expressed as a sum of minterms (SoM) in which each of the minterms evaluates to \(1\text{.}\) When first defining a problem, starting with the canonical sum ensures that the full effect of each variable has been taken into account. This often does not lead to the best implementation. In Section 5.5 we will see some tools to simplify the canonical sum expression, and hence, the implementation.

It is common to index the minterms according to the values of the variables that would cause that minterm to evaluate to \(1\text{.}\) For example, \(x' \cdot y' \cdot z' = 1\) when \(x = 0\text{,}\) \(y = 0\text{,}\) and \(z = 0\text{,}\) so this would be \(m_{0}\text{.}\) The minterm \(x' \cdot y \cdot z'\) evaluates to \(1\) when \(x = 0\text{,}\) \(y = 1\text{,}\) and \(z = 0\text{,}\) so is labeled \(m_{2}\text{.}\) Table 5.3.1 lists all the minterms for a three-variable expression.

A convenient notation for expressing a sum of minterms is to use the \(\sum\) symbol with a numerical list of the minterm indices. For example,

As you might expect, each of the terms defined above has a dual definition.

Sum Term

A term in which all the literals are connected with OR operators. OR is additive, hence the use of “sum.”

Product of Sums (PoS)

One or more sum terms connected with AND operators. AND is multiplicative, hence the use of “product.”

Maxterm or Standard Sum Term

A sum term that contains all the variables in the problem, either in its uncomplemented or complemented form. For example, if a problem involves three variables, \(x\text{,}\) \(y\text{,}\) and \(z\text{,}\) then \((x + y + z)\text{,}\) \((x' + y + z')\text{,}\) and \((x' + y' + z')\) are all maxterms, but \((x + y)\) is not.

Canonical Product or Product of Maxterms (PoM)

A product of sums in which each sum term is a maxterm. Since all the variables are present in each maxterm, the canonical product is unique for a given problem.

It also follows that any Boolean function can be uniquely expressed as a product of maxterms (PoM) that evaluate to \(0\text{.}\) Starting with the product of maxterms ensures that the full effect of each variable has been taken into account. Again, this often does not lead to the best implementation, and in Section 5.5 we will see some tools to simplify canonical product expressions.

It is common to index the maxterms according to the values of the variables that would cause that maxterm to evaluate to \(0\text{.}\) For example, \(x + y + z = 0\) when \(x = 0\text{,}\) \(y = 0\text{,}\) and \(z = 0\text{,}\) so this would be \(M_{0}\text{.}\) The maxterm \(x' + y + z'\) evaluates to 0 when \(x = 1\text{,}\) \(y = 0\text{,}\) and \(z = 1\text{,}\) so is \(M_{2}\text{.}\) Table 5.3.2 lists all the maxterms for a three-variable expression.

A convenient notation for expressing a sum of maxterms is to use the \(\prod\) symbol with a numerical list of the maxterm indices. For example,

The names “minterm” and “maxterm” may seem somewhat arbitrary, but consider the two functions:

There are eight (\(2^{3}\)) permutations of the three variables, \(x\text{,}\) \(y\text{,}\) and \(z\text{.}\) \(F_{1}\) has one minterm and evaluates to \(1\) for only one of the permutations, \(x = y = z = 1\text{.}\) \(F_{2}\) has one maxterm and evaluates to \(1\) for all permutations except when \(x = y = z = 0\text{.}\) This is shown in the following truth table:

OR-ing more minterms to a sum of products expression expands the number of cases where it evaluates to \(1\text{,}\) and AND-ing more maxterms to a product of sums expression reduces the number of cases where it evaluates to \(1\text{.}\)