Gates

Assignment: Gates

• Assign: Thursday 23 January
• Checkpoint: aim to complete at the first 5 problems by the end of the day Tuesday 28 January
• Due: Monday 3 February
• Policy: Individual graded synthesis assignment
• Submit: Upload a PDF written on the cs240-gates-worksheet-blank-s25.pdf submission sheet
• Reference:
  • Digital Logic
  • Data as Bits
  • Boolean Laws

• Notes:

  • You can complete Problems 1–8 based on the information in the Digital Logic material
  • You can complete Problems 9–10 based on the information in the Data as Bits material

Goals

• To understand how circuits model computation with inputs, wires, and gates.
• To master converting between logical expressions, truth tables, and gate diagrams.
• To become comfortable applying Boolean algebraic laws.
• To understand universal logical gates—giving you a taste of how complex computation can be expressed with very simple building blocks.
• To understand binary and hex representations of ASCII and Unicode characters

Expected time

This is a long assignment with 10 problems. We do not have a time analysis for this version of the assignment, but we expect that t will take most students 6 to 10 hours to complete. But some students may need even more time. So start early!

Contents

• Assignment: Gates
  • Goals
  • Expected time
• Contents
• Exercises
  • 1. Circuit to Expression [4 points]
  • 2. Expression to Circuit [6 points]
  • 3. Equivalences [4 points]
  • 4. Sum-of-Products [5 points]
  • 5. Product-of-Sums [5 points] [Independent]
  • 6. Simplification [10 points]
  • 7. Fun with DeMorgan [10 points]
  • 8. XOR from Universal Gates (12 points)
  • 9. Decoding a T-shirt (8 points)
  • 10. Decoding a Unicode message (12 points)
• Submission

Exercises

Please write your answers on the cs240-gates-worksheet-blank-s25.pdf submission sheet to streamline the grading process. Submit your work by scanning a PDF of all worksheet pages (in order) and uploading it to Gradescope. Remember that this course uses your Gradescope account attached to your Wellesley email address (the variety that matches your username). You can merge accounts across multiple email addresses if helpful.

1. Circuit to Expression [4 points]

Write truth tables (2 points) and unsimplified Boolean expressions (1 point each) for each of the output signals $F_1$ and $F_2$ in the following circuit. Create the boolean expressions via a direct translation of the circuit.

2. Expression to Circuit [6 points]

Draw unsimplified circuits to implement the following Boolean expressions. We use the apostrophe$’$ notation as an alternative to the overbar to indicate logical negation of the preceding term. The apostrophe binds tightly. For example, $AB’$ means $(A)(B’)$. Use many-input AND, OR, NOR, or NAND gates where they are useful (instead of using only 2-input gates).

1. [1] $(A + B)(A + B’)$
2. [2] $ABC + A’B + ABC’$
3. [3] [Independent] $A’B’ + A’BC’ + (A + C’)’$

3. Equivalences [4 points]

In each of the following subparts, are circuits $O_1$ and $O_2$ equivalent (do they always produce the same output when given the same inputs)?

If they are not, provide an example value for $A$ and/or $B$ and what the different outputs of $O_1$ and $O_2$ become (a counterexample). If they are equivalent, provide a short explanation.

a.

b.

c. [Independent]

d. [Independent]

4. Sum-of-Products [5 points]

Recall that a sum-of-products form is a boolean expression that is a sum of minterms, where each minterm is a product of one literal for every input variable (a literal is a variable or its negation). For example, ABC and ABC' are minterms of a circuit with 3 inputs, but AB is not.

An example of a sum-of-products expression is (A'BC') + AB'C + ABC'. Using a circuit layout convention similar to that suggested from DDCA, this example can be expressed as the following circuit:

A nice feature of this layout convention is there is never more than one inverter per input.

Below is a truth table.

1. [2] Write a sum-of-products Boolean expression bexp₄ for the output $Y$ of this truth table. (Hint: See Section 2.2.2 of DDCA.)
2. [3] Draw a circuit that is a direct translation of bexp₄ without any simplification. For the circuit, try to use the same input order and layout convention as in the example shown above.

$A$	$B$	$C$		$Y$
0	0	0		1
0	0	1		0
0	1	0		1
0	1	1		0
1	0	0		1
1	0	1		1
1	1	0		0
1	1	1		1

5. Product-of-Sums [5 points] [Independent]

Recall that a product-of-sums form is a boolean expression that is a product of maxterms, where each maxterm is a sum of one literal for every input variable. An example product-of-sums expression is (A+B+C)(A+B+C')(A+B'+C)(A'+B+C).

Using the same truth table from Problem 4:

1. [2] Write a product-of-sums Boolean expression bexp₅ for the output $Y$ of the truth table
2. [3] Draw a circuit that is a direct translation of bexp₅ without any simplification. For the circuit, use a layout that is analogous to the layout of the sample circuit in Problem 3 (where the and and or gates are appropriately swapped).

6. Simplification [10 points]

As seen in the Digital Logic material, Boolean simplification uses Boolean laws to rewrite one Boolean expression step by step into another Boolean expression, where each step preserves the meaning of the expressions. Below is an example of Boolean simplification used to prove A + AB = A (one form of Absorption Law 1):

	A + AB
=	1A + AB	Identity
=	A1 + AB	Commutativity
=	A(1 + B)	Distributivity
=	A1	One law
=	1A	Commutativity
=	A	Identity

Each step of a Boolean simplification applies a simplification law to a subpart of a Boolean expression known as the redex. In the above proof, the redex on each line is highlighted in a bolded color, and the law applied to that redex is named in the following line (using the same bolded color as the redex to which is is applied). The redex colors alternate between lines to avoid confusion.

It is tedious to explicitly show each application of the Commutativity and Associativity laws, so these are usually omitted. With these omissions, the above derivation can be shortened to:

	A + AB
=	A1 + AB	Identity
=	A(1 + B)	Distributivity
=	A1	One law
=	A	Identity

Below is another simplification example that illustrates more laws:

	DEFG + DEFGHI+ (E'+F')G + (EF)'G'
=	DEFG +(E'+F')G + (EF)'G'	Absorption 1
=	DEFG +(EF)'G + (EF)'G'	DeMorgan
=	DEFG + (EF)'(G + G')	Distributivity
=	DEFG +(EF)'(1)	Inverse
=	DEFG + (EF)'	Identity
=	DG +(EF)'	Absorption 2 (where A=(EF)',B=DG, and commutativity and involution are used implicitly)
=	DG + E' + F'	DeMorgan

Note that a single application of the Combining law could have been used to replace the three redex applications Distributivity, Inverse, and Identity to directly simplify the redex (EF)'G + (EF)'G' to (EF)' in one step.

In this problem, you will use the laws of Boolean algebra to simplify some Boolean expressions. Each result (including intermediate ones) should used only products, sums, and negation (i.e., no XOR). Each final result should be expressed as a sum of products of literals (but here, it’s OK for individual products to include literals for only some of the inputs, not necessarily all of them). Your goal is to have the most concise final expression (smallest number of products, where each product uses the smallest number of literals).

Show your derivation in a step-by-step way, using the conventions shown in the above examples. Notes:

• Rather than using colors for redexes, you can box them or underline them.
• As in the above examples, you must list the law(s) used to justify each step. The law names do not need to be colored, but the law(s) listed on a line should justify the redex highlighed on the previous line.
• You should not show explicit applications of the Commutativity and Associativity laws, but can implicitly rearrange parts of expressions via this laws between steps.
• To help you think about the meaning of each Boolean expression, you must show a truth table for the original expression and verify that your final expression satisfies the same truth table. If not, you made one or more mistakes in your steps that you need to correct!

1. [5] ABC + ABC’ + A’C + A’B’C + AB’C Hint: the following laws are the only ones you need (not necessarily in this order, and not necessarily all of them, depending on what approach you take), p though you are welcome to use others: Absorption 1, Absorption 2, Combining, DeMorgan, Distributivity
2. [5] [Independent] A'B' + A'BC' + (A + C')'

7. Fun with DeMorgan [10 points]

Lois Reasoner thinks that AB + A'B' simplifies to 1 by the Inverse law.

1. [1] Show that Lois is wrong by fleshing out a truth table to find all rows in which AB + A'B' evaluates to 0, not 1. Circle these rows.

2. [1] By part (a), A'B' is clearly not the inverse of AB. Using DeMorgan’s law, express the inverse of AB as a Boolean expression bexp_7b that is a sum of literals.

3. [1] Extend the truth table from part (a) to add columns for bexp_7b and AB + bexp_7b. All entries in the column for AB + bexp_7b should have the value 1, showing that bexp_7b is indeed the inverse of AB.

4. [2] Using the DeMorgan and Involution (double-negation) laws, express the inverse of A'B' as a boolean expression bexp_7d that is a sum of literals. Show the application(s) of each law.

5. [2] [Independent] Using the DeMorgan and Involution (double-negation) laws, express the inverse of (A'+B+C') as a boolean expression bexp_7e that is a product of literals. Show the application(s) of each law.

6. [3] [Independent] Using the DeMorgan and Involution (double-negation) laws, express the inverse of A'(B+(C'D)')(E'+F) as a a boolean expression bexp_7f that is a sum of products. Show the application(s) of each law.

8. XOR from Universal Gates (12 points)

NAND and NOR are universal gates: each one alone can be used to build any other logical gate. The goal of this problem is to demonstrate how this works by drawing two circuits that implement two-input XOR:

1. [6] Using only 2-input NAND gates.
2. [6] [Independent] Using only 2-input NOR gates.

Rather than using trial and error (which is very unsatisyfing) to develop these circuits, you should derive them using the laws of Boolean algebra in conjunction with the definitions of XOR, NAND, and NOR gates. I.e., start with the the sum-of-products or product-of-sums definition of A XOR B and use Boolean laws to convert the original expression to an equilvalent one that uses only NAND or NOR.

Hints:

• Recall that A NAND B = (AB)' and A NOR B = (A+B)'

• The only Boolean laws you need are DeMorgan, Involution (Double Negation), and Distributivity.

• The minimal number of NAND gates is 4, but nearly full credit will be awarded for 5 NAND gates.

• The minimal number of NOR gates is 5, but nearly full credit will be awarded for 6 NOR gates.

• XOR treats its two inputs symmetrically, so your design should reflect this.

• Full credit for a correct circuit will be awarded only if the circuit is accompanied by a correct algebraic derivation that corresponds to the circuit.

• Half credit will be awarded for a correct circuit without an algebraic derivation as long as you explain why the circuit correctly calculates XOR.

9. Decoding a T-shirt (8 points)

Margaret Ligon ‘14, a Wellesley CS student in the 2012 CS342 Computer Security class, designed a T-shirt for the Wellesley participants in the Lincoln Laboratory Capture the Flag (CTF) computer security contest. The back of the T-shirt is shown in the figure below. It has two parts: a base consisting of hex bytes and a flag consisting of bits. The hex and binary digits on the shirt stand for a message that can be decoded with the help of an ASCII table, such as the one at http://www.asciitable.com/

1. [2 points] What is the message encoded in the hex bytes at the base of the flag? Show the ASCII character that corresponds to each pair of hex digits.

2. [6 points] What is the message encoded in the binary bits of the flag? (Hint: the line breaks in the flag are irrelevant; they just make the shape of the bits look like a flag. So just consider a single sequence of all the bits.) Explain the details of your decoding strategy by writing down the sequence of bits in the flag and showing the characters that correspond to subsequences of the bits. (Hint: focus on 8-bit bytes.)

10. Decoding a Unicode message (12 points)

You have been sent a message that consists of the following seven bytes (expressed in hex):

49 E2 99 A5 CF 80 21

You have been informed that this message consists of Unicode characters that have been encoded into a byte sequence via the UTF-8 encoding. Your goal in this problem is to decode the message.

Start this problem by doing two things:

1. Read this article about what every programmer should know about Unicode. It’s an oldie, but goodie. It explains that Unicode characters are understood as code points, which are just numbers that specify Unicode characters. For example, codepoint U+03B1 is the Greek letter $\alpha$ (see https://unicode-table.com/en/03B1 or do a web search for Unicode U+03B1.)

2. The core to understanding the UTF-8 encoding is the following table, which is explained in the Encoding section of the Wikipedia article on UTF-8.

   

   The table shows how Unicode characters in the UTF-8 encoding can be represented as one to four bytes. The 0 and 1 bits are header bits that indicate how many bytes are being used for the current Unicode code point. The bits marked x in the encoding are the actual content bits bits that specify the code point.

After you’ve finished the above two steps, you can now answer the parts of this question:

1. [10 points] Show how to decode the Unicode UTF-8 message encoded in the hex bytes 49 E2 99 A5 CF 80 21 to a sequence of Unicode code points. Write the message bits corresponding to the message expressed in hex bytes, distinguish header bits from content bits, and indicate the number of bytes in each code point. Show the code points determined by the content bits. Write a code point as U+WXYZ, where each of W, X, Y, Z is a hex digit.

2. [2 points] What would this message look like when displayed in a Unicode-enabled application? (Search for your code points at https://unicode-table.com/en.)

Submission

Please write your answers on the cs240-gates-worksheet-blank-s25.pdf submission sheet to streamline the grading process. Submit your work by scanning a PDF of all worksheet pages (in order) and uploading it to Gradescope. Remember that this course uses your Gradescope account attached to your Wellesley email address (the variety that matches your username). You can merge accounts across multiple email addresses if helpful.