Lecture 9: Encoders and Decoders

Dr. shama Noreen

§ Logic circuits
§ Combinational
§ Sequential

§ Combinational circuits design analysis

§ Combinational circuits design procedure

§ Decoder and Encoder Combinational circuit

§ Consist of logic gates only.
§ Outputs are determined from the present values of inputs (ideal) Plus Propagation
delays.
§ Operations can be specified by a truth table or a m set of Boolean functions.
§ Repeating a sequence will always give the same output values.

Combinational circuits consists of logic gates whose

value at any particular time are determined by the
current input values.
• No memory elements
• No feedback from output to input
§ Consist of logic gates and storage elements (FLIP FLOPS)
§ Outputs are a function of the inputs and the state of the storage elements.
§ Depend not only on present inputs, but also on past values

§ Circuit behavior must be specified by a time sequence of inputs and internal states.
§ Repeating a sequence of value may result in entirely different output values.

Sequential circuits are those which are dependent on

clock cycles and depends on present as well as past
inputs to generate any output.
A combinational
circuit consists of
• Input variables
• Logic gates
• Output variables
§ Each input and output variable is a binary signal Represent logic 1 and logic 0.
§ There are 2" possible binary input combinations for n input variable.
§ Only one possible output value for each possible input combination.

§ Can be specified with a truth table.

§ Can also be described by m Boolean functions, one for each output variable.

§ Each output function is expressed in terms of n input variables.

§ A timing specification for the device to compute specified output values from an
arbitrary set of stable valid input values.
§ Analysis: determine the function that the circuit implements
§ Input : Often given logic diagram
§ Output: Truth table, Boolean equation or Timing Diagram

§ The analysis can be performed by

§ Manually finding Boolean functions
§ Manually finding truth table
§ Using a computer simulation program

§ First step: make sure that circuit is combinational

§ No memory elements
§ No feedback path (feedback path: a connection from the output of one gate to the input of
a second gate that forms part of the input to the first gate).

§ Second step: obtain the output Boolean functions or the truth table

Final : Truth table, Boolean equation or Timing Diagram

ANALYSIS
Step 2.1:
§ Label all gate outputs that are a function of input variables.
§ Determine Boolean functions for each gate output
ANALYSIS
§ Step 2.2:
§ Label the gates that are a function of input variables and previously labeled gates.
§ Find the Boolean function for these gates
ANALYSIS

Step 2.3:
§ Obtain the output Boolean function in term of input variables.
§ By repeated substitution of previously defined functions.

§ Determine the function that the circuit implements from a logic diagram.
§ Circuit’s function can be determined by either Boolean function or truth table.
ANALYSIS

To obtain the truth table from the logic diagram:

1. Determine the number of input variables.
For n inputs:
§ 2 n possible combinations
§ List the binary numbers from 0 to 2 n-1 in a table

2. Label the outputs of selected gates.

3. Obtain the truth table for the outputs of those gates that are a function of the input
variables only.
4. Obtain the truth table for those gates that are a function of previously defined
variables at step 3.
§ Repeatedly until all outputs are determined
Digital Analog
Design procedure:
§ Input: the specification of the problem
§ Output: the logic circuit diagram (or Boolean functions)

§ The design of a combinational circuit involves the following steps:

§ Specification: How the circuit operates is clearly expressed

§ Determine the required number of inputs and outputs from the specification.

§ Formulation: Derivation of the truth table or the Boolean equations that define
the relationship between inputs and outputs
§ Optimization: Algebraic or K-map optimization of the truth table and draw the
corresponding logic diagram
§ Obtain and simplify the Boolean function (K-maps, algebraic manipulation, CAD tools, …).
Consider any design constraints (area, delay, power, available libraries, etc).
§ Draw the logic diagram.

§ Technology Mapping: Tranform the logic diagram to a new diagram using the
available implementation technology

§ Verification: Verify the correctness of the final design

§ Verify the correctness of the design
EXAMPLE 1: COMPARING 2-BIT NUMBERS -
SPECİFİCATİON
§ Let’s design a circuit that compares two 2-bit numbers, A and B. The
circuit should have three outputs:

§ G (“Greater”) should be 1 only when A > B

§ E (“Equal”) should be 1 only when A = B
§ L (“Lesser”) should be 1 only when A < B

§ Make sure you understand the problem

§ Inputs A and B will be 00, 01, 10, or 11 (0, 1, 2 or 3 in decimal)

§ For any inputs A and B, exactly one of the three outputs will be 1
COMPARING 2-BIT NUMBERS - SPECİFİCATİON
§ Two 2-bit numbers means a total of four inputs

§ We should name each of them

§ Let’s say the first number consists of digits A1 and A0 from left to
right, and the second number is B1 and B0

§ The problem specifies three outputs: G, E and L

COMPARING 2-BIT NUMBERS - FORMULATİON
A1 A0 B1 B0 G E L
§ For this problem, it’s probably easiest to start 0 0 0 0
with a truth table. This way, we can explicitly 0 0 0 1
show the relationship (>, =, <) between inputs 0 0 1 0
0 0 1 1
§ A four-input function has a sixteen-row truth 0 1 0 0
table 0 1 0 1
0 1 1 0 0 0 1
0 1 1 1
§ It’s usually clearest to put the truth table rows 1 0 0 0
in binary numeric order; in this case, from 1 0 0 1
0000 to 1111 for A1, A0, B1 and B0 1 0 1 0
1 0 1 1
§ Example: 01 < 10, so the sixth row of the truth 1 1 0 0
table (corresponding to inputs A=01 and 1 1 0 1
B=10) shows that output L=1, while G and E 1 1 1 0
are both 0. 1 1 1 1
COMPARING 2-BIT NUMBERS - FORMULATİON
A1 A0 B1 B0 G E L
0 0 0 0 0 1 0
0 0 0 1 0 0 1
0 0 1 0 0 0 1
0 0 1 1 0 0 1
0 1 0 0 1 0 0
0 1 0 1 0 1 0
0 1 1 0 0 0 1
0 1 1 1 0 0 1
1 0 0 0 1 0 0
1 0 0 1 1 0 0
1 0 1 0 0 1 0
1 0 1 1 0 0 1
1 1 0 0 1 0 0
1 1 0 1 1 0 0
1 1 1 0 1 0 0
1 1 1 1 0 1 0
COMPARING 2-BIT NUMBERS - OPTİMİZATİON
§ Let’s use K-maps. There are three functions (each with the same inputs
A1 A0 B1 B0), so we need three K-maps B1
B1 B1
0 1 1 1
0 0 0 0 1 0 0 0
0 0 1 1
1 0 0 0 0 1 0 0 A0
A0 A0 0 0 0 0
1 1 0 1 0 0 1 0 A1
A1 A1 0 0 1 0
1 1 0 0 0 0 0 1
B0
B0 B0

G(A1,A0,B1,B0) = E(A1,A0,B1,B0) = L(A1,A0,B1,B0) =

A1 A0 B0’ + A1’ A0’ B1’ B0’ + A1’ A0’ B0 +
A0 B1’ B0’ + A1’ A0 B1’ B0 + A0’ B1 B0 +
A1 B1’ A1 A0 B1 B0 + A1’ B1
A1 A0’ B1 B0’
COMPARING 2-BIT NUMBERS - OPTİMİZATİON
G = A1 A0 B0’ + A0 B1’ B0’ + A1 B1’
E = A1’ A0’ B1’ B0’ + A1’ A0 B1’ B0 + A1 A0 B1 B0 + A1 A0’ B1 B0’
L = A1’ A0’ B0 + A0’ B1 B0 + A1’ B1
EXAMPLE 2: BCD-TO-EXCESS-3 CODE
CONVERTER SPECİFİCATİON
§ Design a circuit that converts binary coded decimal (BCD) to the excess-3 code
for the decimal digits.
§ Inputs :
§ BCD (4 bits).
§ 4 inputs.
§ Symbols: A, B, C, D

§ Outputs:
§ Ex-3 (4 bits).
§ 4 outputs.
§ Symbols: w, x, y, z
BCD-TO-EXCESS-3 CODE CONVERTER - SPECİFİCAİTON
§ The excess-3 code for a decimal digit is the binary combination corresponding
to the decimal digit plus 3. For example, the excess-3 code for decimal digit 5
is the binary combination for 5 + 3 = 8, which is 1000.

§ Each BCD digit is four bits with the bits, from most significant to least
significant, labeled A, B, C, D. Each excess-3 digit is four bits, with the bits, from
most significant to least significant, labeled W, X,Y, Z.

A W
BCD B BCD-to X Excess-3
digit C Excess-3 Y digit
D Z
28
BCD-TO-EXCESS-3 CODE
CONVERTER - FORMULATİON
§ Excess-3 code is easily formed by adding a binary 3 to the binary or BCD for the
digit.
§ There are 16 possible inputs for both BCD and Excess-3.

§ It can be assumed that only valid BCD inputs will appear so the six combinations
not used can be treated as don’t cares.
BCD-TO-EXCESS-3 CODE CONVERTER - FORMULATİON

30
BCD-TO-EXCESS-3 CODE CONVERTER - OPTİMİZATİON

31
BCD-TO-EXCESS-3 CODE CONVERTER - OPTİMİZATİON

32
§ Have equations
§ W = A + BC + BD = A + B(C+D)
§ X = B’C + B’D + BC’D’ = B’(C+D) + BC’D’
§ Y = CD + C’D’
§ Z = D’
§ Factoring out (C+D) and call it T
§ Then T’ = (C+D)’ = C’D’
§ W = A + BT
§ X = B’T + BT’
§ Y = CD + T’
§ Z = D’

33
§ Implementing the second set of
equations where T=C+D results in a
lower gate count.

34
EXAMPLE 3: BCD-TO-SEVEN-SEGMENT DECODER -
SPECİFİCATİON
Digital readouts found in many consumer electronic products often use
Light Emitting Diodes (LEDs). Each digit of the readout is formed from
seven LED segments. Each segment can be illuminated by a digital
signal. A BCD-to-seven-segment decoder is a combinational circuit that
accepts a decimal digit in BCD and generates the appropriate outputs for
the segments of the displayfor the decimal digit. The seven outputs of the
decoder (a,b,c,d,e,f,g)select the corresponding segments in the display.
BCD-to-seven-segment decoder has four inputs, A, B, C, and D for the
BCD digit and seven outputs,a through g, for controlling the segments.

35
BCD-TO-SEVEN-SEGMENT DECODER - FORMULATİON

36
BCD-TO-SEVEN-SEGMENT DECODER - OPTİMİZATİON

§ Create a K-map for each output and get

§ A = A’C+A’BD+B’C’D’+AB’C’
§ B = A’B’+A’C’D’+A’CD+AB’C’
§ C = A’B+A’D+B’C’D’+AB’C’
§ D = A’CD’+A’B’C+B’C’D’+AB’C’+A’BC’D
§ E = A’CD’+B’C’D’
§ F = A’BC’+A’C’D’+A’BD’+AB’C’
§ G = A’CD’+A’B’C+A’BC’+AB’C’

37
BINARY ADDER-SUBTRACTOR
§ A combinational circuit that performs the addition of two bits is
called a half adder.
§ The truth table for the half adder is listed below:

S: Sum
C: Carry

S = x’y + xy’
C = xy
38
IMPLEMENTATION OF HALF-ADDER

39
 FULL-ADDER
§ One that performs the addition of three bits(two significant bits and a previous
carry) is a full adder.

40
SIMPLIFIED EXPRESSIONS

S = x’y’z + x’yz’ + xy’z’ + xyz

C = xy + xz + yz
41
FULL ADDER IMPLEMENTED IN SOP

42
ANOTHER IMPLEMENTATION
§ Full-adder can also implemented with two half adders and one OR
gate.
S = z ⊕ (x ⊕ y)
= z’(xy’ + x’y) + z(xy’ + x’y)’
= xy’z’ + x’yz’ + xyz + x’y’z
C = z(xy’ + x’y) + xy = xy’z + x’yz + xy

43
BINARY ADDER
§ This is also called Ripple
Carry Adder ,because of
the construction with full
adders are connected in
cascade.

44
CARRY PROPAGATION
§ Fig.4-9 causes a unstable factor on carry bit, and produces a
longest propagation delay.

§ The signal from Ci to the output carry Ci+1, propagates through an

AND and OR gates, so, for an n-bit RCA, there are 2n gate levels for
the carry to propagate from input to output.

45
CARRY PROPAGATION
§ Because the propagation delay will affect the output signals on
different time, so the signals are given enough time to get the
precise and stable outputs.

§ The most widely used technique employs the principle of carry

look-ahead to improve the speed of the algorithm.

46
BOOLEAN FUNCTIONS
Pi = Ai ⊕ Bi
Gi = AiBi
Output sum and carry
Si = P i ⊕ C i
Ci+1 = Gi + PiCi
Gi : carry generate Pi : carry propagate
C0 = input carry
C1 = G0 + P0C0
C2 = G1 + P1C1 = G1 + P1G0 + P1P0C0
C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0

C3 does not have to wait for C2 and C1 to propagate.

47
 LOGIC DIAGRAM OF
CARRY LOOK-AHEAD GENERATOR
C3 is propagated at the same time as C2 and C1.

48
4-BIT ADDER WITH CARRY LOOKAHEAD
Delay time of n-bit CLAA = XOR + (AND + OR) + XOR

49
BINARY SUBTRACTOR
M = 1àsubtractor ; M = 0àadder

50
§ Itis worth noting Fig.4-13 that binary numbers in the
signed-complement system are added and subtracted by
the same basic addition and subtraction rules as unsigned
numbers.

§ Overflow is a problem in digital computers because the

number of bits that hold the number is finite and a result
that contains n+1 bits cannot be accommodated.

51
§ When two unsigned numbers are added, an overflow is
detected from the end carry out of the MSB position.

§ When two signed numbers are added, the sign bit is

treated as part of the number and the end carry does not
indicate an overflow.

§ Anoverflow cann’t occur after an addition if one number is

positive and the other is negative.

§ Anoverflow may occur if the two numbers added are both

positive or both negative.
52
BCD adder can’t exceed 9 on each input digit. K is the carry.

53
§ Fundamental circuits that are the base building blocks of most larger digital
circuits
§ They are reusable and are common to many systems.

§ Examples of functional logic circuits

§ Decoders
§ Encoders
§ Code converters
§ Multiplexers
§ Multiplexers
§ Selectors for routing data to the processor, memory, I/O
§ Multiplexers route the data to the correct bus or port.

§ Decoders
§ are used for selecting things like a bank of memory and then the address within the bank.
This is also the function needed to ‘decode’ the instruction to determine the operation to
perform.
§ Encoders
§ are used in various components such as keyboards
§ When the binary sum isgreater than 1001, we obtain a non-
valid BCD representation.

§ The addition of binary 6(0110) to the binary sum converts it

to the correct BCD representation and also produces an
output carry as required.

§ To distinguish them from binary 1000 and 1001, which also

have a 1 in position Z8, we specify further that either Z4 or Z2
must have a 1.

C = K + Z8Z4 + Z8Z2
56
§ A decimal parallel
adder that adds n
decimal digits needs
n BCD adder stages.

§ The outputcarry
from one stage must
If =1
be connected to the
input carry of the
0110
next higher-order
stage.
57
BINARY MULTIPLIER
§ Usually there are more bits in the partial products and it is necessary
to use full adders to produce the sum of the partial products.

And

58
§ For J multiplier bits
and K
multiplicand bits we need (J X K) AND
gates and (J − 1) K-bit adders to
produce a product of J+K bits.

§ K=4 andJ=3, we need 12 AND gates

and two 4-bit adders.

59