CS132 - Boolean and Digital Logic

What is combinational logic?

Logic with no memory; outputs depend only on current inputs.

What is sequential logic?

Logic with memory; outputs can depend on current inputs and previous state.

Give examples of combinational logic.

Logic gates, adders, decoders, encoders, multiplexers and demultiplexers.

Give examples of sequential logic.

Latches, flip-flops, registers, shift registers and counters.

What is a truth table?

A table showing every possible input combination and the output for each one.

For n inputs, how many truth-table rows are there?

2^n rows.

What is Sum of Products (SOP)?

A Boolean expression formed by OR-ing product terms from rows where the output is 1.

How do you form SOP from a truth table?

Use rows where output is 1; write variables normally for 1 and complemented for 0; AND them in each row; OR the terms.

What is Product of Sums (POS)?

A Boolean expression formed by AND-ing sum terms from rows where the output is 0.

What is De Morgan's law for NOT(A AND B)?

NOT(A AND B) = NOT A OR NOT B.

What is De Morgan's law for NOT(A OR B)?

NOT(A OR B) = NOT A AND NOT B.

What is a Karnaugh map?

A 2D arrangement of truth-table outputs used to simplify Boolean expressions.

Why do K-maps use Gray code ordering?

Adjacent cells differ by only one input bit, making valid grouping possible.

What order should 2-bit K-map labels use?

00, 01, 11, 10.

How do you simplify using a K-map?

Fill outputs, group 1s in largest power-of-2 rectangles, allow wraparound/overlap, keep variables that do not change, OR group terms.

What sizes can K-map groups have?

Powers of 2: 1, 2, 4, 8, etc.

Can K-map groups wrap around edges?

Yes. Edge cells can be adjacent because the map wraps.

What is a don't-care condition on a K-map?

An input combination where the output does not matter; it can be treated as 0 or 1 to simplify the expression.

Give a K-map limitation.

XOR-style checkerboard patterns may not simplify well with normal grouping.

What is a universal gate?

A gate type that can be used to build any other logic gate.

Which gates are universal?

NAND and NOR.

Why use only one type of universal gate?

Simpler manufacturing, standardised design and easier power-characteristic management.

Why might using only NOR/NAND be bad?

It may require more gates, increasing delay, area, power use and diagram complexity.

How do you make NOT A using NOR?

A NOR A.

How do you make A OR B using NOR only?

(A NOR B) NOR (A NOR B).

How do you make A AND B using NOR only?

(A NOR A) NOR (B NOR B).

What does XOR output?

1 when the two inputs are different; 0 when they are the same.

What is a half adder?

A circuit that adds two bits and produces Sum and Carry, but has no carry-in.

Half adder equations?

Sum = A XOR B. Carry = A AND B.

What is a full adder?

A circuit that adds A, B and carry-in, producing Sum and carry-out.

Full adder Sum equation?

Sum = A XOR B XOR Cin.

Full adder carry-out equation?

Cout = AB + A.Cin + B.Cin.

How do you make an N-bit full adder?

Chain N one-bit full adders; carry-out from each stage goes to carry-in of the next.

Draw/describe an N-bit full adder-subtractor.

Use N full adders. XOR each B bit with control Z. Use Z as carry-in to the first full adder. Z=0 adds; Z=1 subtracts using two's complement.

What technique does the adder-subtractor use?

Two's complement subtraction.

What is a decoder?

A combinational circuit that converts an n-bit binary input into one selected output line among 2^n outputs.

What is an encoder?

The opposite of a decoder: it converts one selected input line into an n-bit binary output.

What is a multiplexer?

A circuit that selects one of many inputs and connects it to one output.

What is a demultiplexer?

A circuit that routes one input to one of several outputs using select lines.

Decoder vs demultiplexer?

A decoder converts binary code to a selected line; a demux routes an input signal to a selected output.

Multiplexer vs demultiplexer?

A mux routes many inputs to one output; a demux routes one input to one selected output.

What is 3-state logic?

Logic with outputs 0, 1 or high impedance/disconnected.

Why is 3-state logic useful on buses?

Many components can connect to one bus, but disabled components are disconnected so only one drives the bus at a time.

What happens if two devices drive a bus at once?

Incorrect behaviour or a short circuit can occur if one drives 1 and another drives 0.

How can an active-high 1-to-4 demux use 3-state logic?

Use a 2-to-4 decoder on select lines. Use decoder outputs to enable four 3-state buffers. Feed input X to all buffers; only the selected output is driven.

What is an SR latch?

A sequential circuit that stores one bit using Set and Reset inputs with Q and NOT Q outputs.

For an active-low NAND SR latch, what input sets Q=1?

Sbar=0 and Rbar=1.

For an active-low NAND SR latch, what input resets Q=0?

Sbar=1 and Rbar=0.

For an active-low NAND SR latch, what input holds the previous value?

Sbar=1 and Rbar=1.

For an active-low NAND SR latch, what input is invalid?

Sbar=0 and Rbar=0.

What is a D latch?

A level-sensitive one-bit storage circuit where Q follows D while Enable is active and holds when Enable is inactive.

Why is a D latch useful compared with an SR latch?

It avoids the invalid SR input combination.

What does transparent mean for a latch?

While Enable is active, changes at D pass through to Q.

What is a rising clock edge?

The clock transition from 0 to 1.

What is a falling clock edge?

The clock transition from 1 to 0.

Latch vs flip-flop?

A latch is level-sensitive; a flip-flop is edge-triggered.

What is a D flip-flop?

An edge-triggered one-bit storage element that copies D to Q only on the active clock edge.

What is an N-bit register?

N D flip-flops in parallel storing N bits on the same active clock edge.

What is a shift register?

A chain of flip-flops that shifts serial input data along one bit per clock edge.

Why use a shift register instead of a normal register for serial data?

It can receive one bit at a time and build up a parallel stored value.

What is a counter?

A sequential circuit that counts clock pulses, often using flip-flops.

How many bits are needed to count 8 states?

3 bits, because 3 bits represent 0 to 7.

Design a serial byte receiver using shift register and counter.

Use an 8-bit shift register for incoming bits and a 3-bit counter for clock pulses. After 8 pulses, output byte_complete=1 and expose the 8 register outputs.

What is a PAL?

Programmable Array Logic; an early programmable logic device, usually programmable once.

What is a PLA?

Programmable Logic Array with programmable AND and OR arrays to implement Boolean expressions.

What is an FPGA?

Field Programmable Gate Array; many configurable logic blocks and programmable connections, enough to implement complex circuits.

What two transistor types are used in CMOS?

pMOS and nMOS.

What is the basic idea of CMOS logic?

One transistor network pulls the output high and the other pulls the output low.

Why is CMOS widely used?

It has low static power consumption because ideally there is not a continuous path from supply voltage to ground when stable.

When does an nMOS transistor turn on?

When its gate input is high.

What is an nMOS transistor good at?

Pulling an output down to 0.

When does a pMOS transistor turn on?

When its gate input is low.

What is a pMOS transistor good at?

Pulling an output up to 1.

What happens in a CMOS inverter when input A = 0?

pMOS turns on, nMOS turns off, and output Y is pulled high to 1.

What happens in a CMOS inverter when input A = 1?

pMOS turns off, nMOS turns on, and output Y is pulled low to 0.

What does XNOR mean?

NOT XOR.

Why is XNOR useful?

It can be used for equality checking because it outputs 1 when two bits match.

For unsigned addition, when does overflow occur?

When there is a carry out beyond the available number of bits.

For two's complement addition, when does overflow occur?

When positive + positive gives a negative result, or negative + negative gives a positive result.

How else can signed overflow be detected?

Overflow occurs if the carry into the sign bit differs from the carry out of the sign bit.

What are cross-coupled inverters?

Two inverters connected in a loop so each inverter output feeds the other inverter input.

Why can cross-coupled inverters store one bit?

They have two stable states, corresponding to Q = 0 or Q = 1.

Why are cross-coupled inverters alone not enough for practical memory?

They do not provide an easy controlled way to set or reset the stored value.

What does bistable mean?

A circuit has two stable states and can remember it's state indefinitely.

What does metastable mean?

The circuit is temporarily in an unstable or undefined state rather than a clear 0 or 1.

Why is metastability a problem?

The final output and the time taken to settle can be unpredictable.

What is a finite state machine?

A model of a system with a finite number of states, inputs, outputs, and rules for moving between states.