Computer Lab supervisions - Digital Electronics

This is usually a fun course. As you can expect, it's very logic but it does have tricky parts (e.g. designing state machines and dealing with MOS transistors). The Harris & Harris book is quite good for the digital part.

A 5th supervision is sometimes requested by students but not needed by default.

Supervision 1:

  1. Exercises 1-5 from this sheet.
  2. The conjunctive normal form for a boolean function F on three variables consists of a product of sums, with each sum containing three literals. How would you use the truth table of F to obtain an expression for F in this form?
  3. Design a vending machine control circuit. A soft drink costs 45c, and your circuit records the nickels (5c), dimes (10c), and quarters (25c) fed to the machine. It issues a command to dispense a can when the appropriate payment has been equalled or exceeded. Assume that at least one quarter is used and that coin counters make available binary counts for each kind of coin.
  4. How would a five-variable Karnaugh map look like? (remember the adjacency property of Karnaugh maps given by the Gray code). How would you expand to six or seven variables and beyond?
  5. [OPTIONAL] How many (different) possible functions can be mapped on a two, three and four-variable Karnaugh map? For each case, what is the proportion of possible functions that cannot be simplified?

Supervision 2:

  1. Exercises 6-13 from this sheet.
  2. Solve the vending machine question from last supervision without any assumption, i.e. any number of quarters is now possible, including zero.

    1. Find a minimal sum of products form for each of the following partially specified boolean functions. Each partially specified function, g[i], is specified by a function f[i] which is true when g[i] must be true and d[i] which is true when g[i] may be true or false (that is, d[i] represents "don't cares").

      f[1] = y.x.w' + x.y.z + y'.x'.z'.w + x.w.z
      d[1] = x'.z

      f[2] = y.w'.z' + w'.x'.z' + y'.w'.z'
      d[2] = x'.w.z'

      NOTE: here x.y means "x and y", and x' means "not x". This is common notation.

    2. What is the maximum number of product terms in a minimal sum of products form of a function of n boolean variables?
    3. How do "don't cares" arise in practice? How may they be exploited? Are there any pitfalls in using them? Give examples for each of your answers.
  4. [OPTIONAL] Determine and prove whether applying DeMorgan can change (i.e. add or remove) static hazards of a logic circuit. Hint: using only boolean algebra may not get you very far.

Supervision 3:

  1. Exercises 14-19 from this sheet.
  2. Design the vending machine from last supervision using sequential logic, i.e. build a finite state machine. Derive the state diagram and the algebraic expressions for the next states and the output. Assume that the vending machine detects the coin type and asserts high one of n,d,q when a nickel,dime,quarter respectively is inserted. Hence your state machine will have 3 inputs. You are free to choose the flip-flop type.

  3. Consider the following state machine, with clock CLK, inputs A,B, and outputs X,Y.

    Reverse engineer circuit

    1. How many states does this system have?
    2. How many rows will there be in a state transition table?
    3. Provide the state transition table.
    4. Draw a state diagram of the system.
    5. Describe what the circuit does (i.e. use words).
    1. An n-bit decoder is a combinational circuit with n inputs and 2n outputs. For each possible combination at the inputs there is only one corresponding output which is set to "1". Design the circuit for a 3-bit decoder.
    2. Ignoring inverters, how many gates are required for your 3-bit input design? How many are required for an n-bit decoder?
    3. An n-bit priority encoder has 2n−1 inputs and n outputs. The inputs x[1], x[2], ..., x[2n−1] are ordered in priority with x[k] having higher priority than x[i] if k > i. The outputs y[n−1], y[n−2], ..., y[0], interpreted as an unsigned integer, denote the highest priority input asserted high. Give a design for a 3-bit priority encoder.
    4. Give two designs for a combinational circuit which has M ordered inputs and M corresponding outputs where the only output asserted (if any) is the one corresponding to the asserted input with the highest priority.
    5. Which design is better, and why?

Supervision 4:

  1. Questions 20-24 from this sheet.
  2. CST 2001 Paper 10 Question 1 parts c,d,e,f only.
  3. CST 2004 Paper 2 Question 2 parts b,c,d only.
  4. CST 2000 Paper 2 Question 3.
  5. [OPTIONAL] CST 2000 Paper 10 Question 9.
Home @ CL
Home @ Maths
Computer Science Admissions Test
Probability Questions
Teaching
Publications
Resume