Computer Science 220

Assembly Language & Computer Architecture

Fall 2010, Siena College

Agenda

- Announcements
- Unix Tip of the day:
`banner` - Lecture assignment recap
- Digital logic basics
- representing mathematical functions

- Simplification of circuits
- Multiplexers and Demultiplexers
- Encoders and Decoders

Lecture Assignment 0c

Due at the start of class, Thursday, October 21.

Please submit answers to these questions
either as a hard copy (typeset or handwritten are OK) or by email to
*jteresco AT siena.edu* by the start of class. We will discuss these questions at
the start of class, so no late submissions are accepted.
* *

Please note that this is a larger than usual lecture assignment, so be sure to allocate some time to complete it.

- Gray code is an alternative binary representation of integers.
Interestingly, incrementing a number in gray code causes the
representation to change by exactly one bit. We have seen one context
where this representation is useful when we labeled our Karnaugh maps.
Consider the following table used to convert 3-bit binary integers
into their gray code equivalents:
binary

000 001 010 011 100 101 110 111 gray code 000 001 011 010 110 111 101 100 - Construct three combinational circuits that compute the 1's digit, the 2's digit, and 4's digit of gray code. Please use the general or-of-ands network (the "sum-of-products" we discussed in class). Do not apply any simplification techniques.
- Construct the simplest, most elegant circuit you can to convert a binary number (on three inputs) to a gray code number (on three outputs).

- In class, we saw how any boolean function can be expressed in
disjunctive form -- as a disjunction (or) of a set of terms (often
called
*min-terms*), each of which is a conjunction (and) of inputs or their negations. This is a handy if you happen to be a digital circuit designer that has a very large pile of*and*and*not*gates, and one big*or*gate. But what if instead you have large piles of*or*and*not*gates, but only a single big*and*? Show that it is possible to express any boolean function as the conjunction of a set of terms, each of which is a disjunction of inputs.- Prove that deMorgan's law for converting conjunctions to
disjunctions (with negations) holds for
*n>2*inputs. - Prove that deMorgan's law for converting disjunctions to
conjunctions (with negations) holds for
*n>2*inputs. - Use these to prove the conjecture.

- Prove that deMorgan's law for converting conjunctions to
disjunctions (with negations) holds for
- Suppose you are interested in constructing a circuit that is high
precisely when four input lines
*DCBA*represent a prime in 4-bit unsigned binary.- Use a Karnaugh map to generate a logical expression with the smallest number of terms that computes this function. Do not optimize the expression further.
- Suppose we didn't care if the function worked on the range 12..15. Use another Karnaugh map to generate a logical expression with the smallest number of terms that computes this function.