CM12002 Boolean Logic

What are combinational logic circuits? [2]

Inputs are static (don’t change over time)

And deterministic (single output for each combination of inputs)

What are sequential logic circuits? [3]

Incorporate feedback from their outputs

Dynamic (changing over time)

Can be non-deterministic (several possible outputs for a given input)

What are the properties of AND? [5]

Associativity - (A.B).C = A.(B.C)

Commutativity - A.B = B.A

Identity - A.1 = A

Absorption - A.A = A

Annihilator - A.0 = 0

What are the properties of OR? [5]

Associativity - (A+B)+C = A+(B+C)

Commutativity - A+B = B+A

Identity - A+0 = A

Absorption - A+A = A

Annihilator - A+1 = 1

What is distributivity? [1]

A.(B+C) = A.B + A.C

What are the properties of NOT? [1]

Involutivity - A’’ = A

What are de Morgan’s Laws? [2]

(A.B)’ = A’+B’

(A+B)’ = A’.B’

What are the 2 basic techniques to determine if two formulas are equivalent? [2]

Equational reasoning

Semantic reasoning

What is equational reasoning? [1]

Using a series of known laws or axioms to go from one formula to the other by algebraic manipulation

What is semantic reasoning? [1]

Verifying that two formulas have the same output for each possible input combination (tabulated in a truth table)

What is the standard sum of products? [3]

Every Boolean expression is equivalent to a standard sum of products

A series of terms joined by OR operations

Each term contains a combination of ALL variables joined by AND operations

What are the 2 stages of simplification? [2]

Convert to standard sum of products

Find simplest form of formula (one with fewest logic gates)

What are Karnaugh maps? [2]

Method to simplify Boolean algebra expressions

Works well for up to 4 variables

Uses Gray codes (adjacent cells differ by only one variable)

What does the Karnaugh map for 2 variables look like? [1]

What does the Karnaugh map for 4 variables look like? [1]

How are Karnaugh maps used for simplification? [2]

Adjacent squares grouped in even numbers

How do you simplify Boolean expressions? [4]

Standard sum of products

Plot on to Karnaugh maps

Find smallest number of biggest valid groupings

Read off the resulting function

What is Binary Coded Decimal (BCD)? [1]

Uses 4 bits to represent one decimal digit

What are ‘don’t cares’? [2]

Inputs which cannot arise

Or we don’t need the outputs corresponding to them

e.g. 1010, 1111

What are ‘don’t cares’ represented by? [1]

x

What would the truth table for BCD on a seven segment display look like? [2]

What would the Karnaugh map for the segment ‘a’ look like? [2]

How do we use ‘don’t cares’ in simplification? [1]

Can be included in areas

What is the truth table for a 1-bit half-adder? [2]

What is the circuit for a 1-bit half-adder? [2]

What is the truth table for a full-adder? [2]

How are full-adders combined? [2]

C_out becomes C_in of the next adder

Joined in series

What is a guard bit? [2]

Hidden bit added to most significant end of integer

Detects overflow

What is the value of the guard bit set to initially? [2]

The value of the most significant bit

What is arithmetic overflow? [1]

When the guard bit is different from the most significant bit in the result

How is a subtractor created? [3]

1’s complement using inverters

The 1 to be added becomes the first carry

How do you multiply in binary? [1]

Use long multiplication then add

Multiplying shifts bits to the left

What is a logical shift? [2]

Bits moved out are lost

0s fill vacated positions

What does an n-place logical left shift represent? [2]

Multiplication by 2ⁿ on unsigned binary

Subject to overflow

What does an n-place logical right shift represent? [2]

Division by 2ⁿ on unsigned binary

With rounding (down)

What is an arithmetic right shift? [2]

Shift bits to the right

Copies of sign bit are copied into vacated positions

What does an n-place arithmetic right shift represent? [1]

Division by 2ⁿ on signed 2’s complement value

What is a circular shift? [1]

Bits moved out one end and moved in the other end

What is a SR latch? [2]

Set-reset latch

What is the simplified characteristic table for an SR latch? [1]

Why are SR latches asynchronous? [2]

There is delay before logic gate responds to input

Two separate gates cannot switch simultaneously

What is an inverted SR latch? [2]

Sets when S=0, resets when R=0

Can’t have S=R=0

What is a solution to asynchronous transition? [2]

Use a clock input to enable / disable transitions

e.g. gated latch or flip-flop

What is a solution to non-deterministic transitions (e.g. S=R=1 on SR latch)? [1]

Avoid states by adding gates to control inputs

What is a SR flip-flop? [2]

Simple latch which responds only when clock signal is present

What is the truth table for a SR flip-flop? [1]

What is a D-type flip-flop? [2]

Ensures inputs are always different by using one input and an inverter

What does a D-type flip-flop act like? [1]

Storage of a bit

What is the truth table for a D-type flip-flop? [1]

What is a J-K flip-flop? [1]

Makes use of the combination S=R=1

Used as a toggle (changes output state of flip-flop)

What is the truth table for a J-K flip-flop? [1]

What is a parallel register? [3]

Lots of D-type flip-flops

Can be read or written from simultaneously using clock

Load is control signal

What is a shift register? [3]

Shifts bits

Transfers information serially

Output of one D-type flip-flop is input of another

What is a ripple counter? [3]

Asynchronous

JK kept at constant high