EENG3150 Digital Technologies - Lecture 6 Combinational Logic Circuits

Combinational Logic Circuits

Course Overview – Combinational Logic

• Lecture 1: Introduction to digital signals
• Lecture 2: Logic gates and truth tables
• Lecture 3: Introduction to minimisation
• Lecture 4: Minimisation using Karnaugh Maps
• Lecture 5: Boolean algebra, De Morgan’s theorem, Duality
• Lecture 6: Combinational logic circuits

Combinational Logic Circuits

• "Off the shelf" building blocks for digital design.
• Functionality and design investigation of the following units:
  • Comparator
  • Multiplexer
  • Decoder
  • Encoder
  • Adder
• Looking at programmable implementation devices to realise designs.

Comparator Unit

• Accepts two n bit quantities as inputs and produces a ‘1’ as an output if the inputs are equal.
• Input 1: a
• Input 2: b
• Output: Output

Single Comparator Unit

• If n=8 the truth table will take 2^{16} (65536) entries.
• A better option is to work with 1-bit comparator units.
• This is an XNOR gate.
• Sum of products implementation by reading the ‘1’s from the truth table.

Truth Table:

Single Comparator Unit

• Sum of products implementation of 1-bit comparator unit
  a \cdot b

Modular Structure

• System can be designed out of identical sub-systems.
• Realise structures of any width by connecting sub-systems together.
• comparator, comparator, comparator
  a2, b2, a1, b1, a0, b0

Modular Structure – a 1-bit comparator subsystem

• comparator
  an, bn, eq{in}, eq{out}
• if (an = bn) and (eq{in} = 1) then eq{out} = 1 else eq_{out} = 0

Modular Structure - a 1-bit comparator subsystem implementation

a, b, eq{in} a \cdot b eq{out}
\overline{a} \cdot \overline{b}

• Circuit diagram

Implementation of 3-bit Comparator

• eq_{in} on the most significant block needs to be set to ‘1’ to enable the comparison.
• The eq_{out} from the least significant block (block 0) gives the result of the entire string of bits. If = ‘1’ then the numbers are equal. If = ‘0’ then a pair of bits in the chain were not equal.
• Comparator, comparator, comparator
  a2, b2, a1, b1, a0, b0
• Least significant block Need to set at logic 1 Block diagram

Multiplexers

• A multiplexer takes in several data channels and outputs a selected channel on (typically) a single communications medium – it is essentially a switch.
• A multiplexer shown in this example allows the selection one of n input channels to be output on a single output channel.
• Selection of the channel will be by m control lines.
• Multiplexer
• output
• n input channels
• m control lines

Multiplexers

• With m control lines, the maximum number of input channels that can be uniquely selected is 2^m.
• Multiplexers usually referred in terms of n-to-1 (4-to-1, 8-to-1 etc.).
• Structure of a multiplexer is based around a series of AND gates feeding an output OR gate. A logic high to a particular AND gate selects the input channel which is to be replicated on the output.

2-to-1 Channel Multiplexer Circuit Diagram

• Output
• Input a
• Input b
  output = a \cdot \overline{cs} + b \cdot cs
• Channel Select (cs)

Decoders

• Multiple input, multiple output logic circuit where input and output codes are different.
• Input word generally has fewer bits that the output word.
• One to one mapping – each input word produces a unique output word.
• Input Word Decoder Output Word

Decoders

• Common input word sizes – n bit binary code representing 2n different coded values (0 to 2n-1).
• Output is usually a “one-out-of-m” code with active high output code words of 0001, 0010, 0100 and 1000 (4 bit example) where one output bit is asserted at any one time.
• Output need not decode all inputs. A decimal decoder will only decode between 0 (0000) and 9 (1001).

2-to-4 Bit Decoder

• When enable is active then decoder translates the two bit input to a four bit output.
• 2-to-4 bit decoder
  Y0, Y1, Y2, Y3
  I0, I1
• Enable

2-to-4 Bit Decoder

• The decoder is decoding the input binary pattern (two input bits) to a 4 bits output pattern
• Don’t care state reduces rows in truth table.

| Enable | I1 | I0 | Y3 | Y2 | Y1 | Y0 |
| :----- | :-: | :-: | :-: | :-: | :-: | :-: |
| 0 | X | X | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |

2-to-4 Bit Decoder- Circuit Diagram

Encoders

• Opposite function of decoders – converts a single active signal (out of m data lines) to a binary s-bit output.
• 4-to-2 Bit Encoder
• Encoder
  p, q, r, s, A, B

| number | p | q | r | s | A | B |
| :----- | :-: | :-: | :-: | :-: | :-: | :-: |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 | 1 | 0 |
| 3 | 0 | 0 | 0 | 1 | 1 | 1 |

4-to-2 Bit Encoder

• The output functions for A and B can be defined as:
  A = \overline{p} \cdot q \cdot r \cdot s + \overline{p} \cdot \overline{q} \cdot r \cdot \overline{s}
  B = \overline{p} \cdot q \cdot r \cdot s + \overline{p} \cdot \overline{q} \cdot \overline{r} \cdot s

4-to-2 Bit Encoder

Adders

• Reminder of binary arithmetic:

| | | | |
| - | - | - | - |
| 0 | 1 | 0 | 1 |
| + 0 | + 0 | + 1 | + 1 |
| 0 | 1 | 1 | (1) 0 |
| | | | Carry Bit |

Simple Adder Function

• Does not care for Carry-Out within a calculation
• Adder Sum Output Bit
  a, b
  sum = a \bigoplus b

| a | b | sum |
| - | - | - |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

Half Adder

• Half adder provides a Carry-Out function
• Sum can now range from 0 to 2
• Two separate outputs: sum and carry_out
• Bit A Bit B Sum Output Carry Output
• Half Adder

Half Adder Truth Tables

| a | b | sum |
| - | - | - |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

| a | b | carry_out |
| - | - | - |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

sum = a \bigoplus b
carry_out = a \cdot b

Half Adder Implementation

Adder Implementation

• Using the Half-Adder we can add two bits together and produce a sum and carry output.
• However, consider the case where two 2 bit numbers are summed.
• Example: 112 + 012

Adder Implementation

• We need the ability to include a carry-out from a previous calculation within an adder design (i.e. a carry-in)

Full Adder

• 3 Inputs – bit A, bit B and a carry_in
• 2 Outputs – sum and carry_out
• Sum Output Carry Output
• Full Adder Bit A Bit B Carry In

Full Adder Truth Table

| a | b | carryin | sum | carryout |
| - | - | - | - | - |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |

Full Adder K-Maps

• sum carry_out

Full Adder K-Maps

• Sum K-Map gives the checker-board pattern of an XOR implementation.
• carryout K-Map sum of products minimization gives: sum = a \bigoplus b \bigoplus carry{in}
  carry{out} = a \cdot b +a \cdot carry{in} +b \cdot carry_{in}

Full Adder Implementation

4-Bit Ripple Adder

• Again, we can use a modular approach based on 1-bit Full Adders
• Full Adder Bit A3 Bit B3 Sum 3 Carry
• Full Adder Bit A2 Bit B2 Sum 2 Carry
• Full Adder Bit A1 Bit B1 Sum 1 Carry
• Full Adder Bit B0 Sum 0 Carry In Bit A0 Carry Out

Exercise

Minimize the following Boolean expressions using Boolean Algebra or Karnaugh Maps

1. Y = ABC + \overline{A}BC + A\overline{B}C + AB\overline{C}
2. Y = a\overline{b}c + \overline{a}bc + \overline{a}\overline{b}c