Cours Logcomb - P1

Download as pdf or txt
Download as pdf or txt
You are on page 1of 60

Industrial IT

Electrical and Energy Engineering


Industrial computing

Plan du cours
 Combinational and sequential logic :
5 séances cours+TD (20 heures)
4 séances TP (16 heures)
Examen+controle (4 heures) 60 heures
 Sequential automata :
4 séances cours+TD (16 heures)
Examen+controle (4 heures)
Combinational logic

Plan
 Variables and logical functions
 Boolean algebra
 Logic diagrams
 Timing diagrams
 Combinational logic circuits
 Representations of numbers: the codes
Introduction: From analog to digital
 Since the 80s and the introduction of the CD, sound and image processing
chains have been digitized.

 Man evolves in an analog world where quantities evolve continuously over


time (voltage, current, temperature, distance, pressure, volume, etc.).

 The advantages of digital processing push us to convert analog quantities


into digital quantities as soon as possible.

 The transition from analog to digital allows for greater precision against
interference that may occur during transmission and storage.
Introduction: The digital
Definitions
 Logical state (binary or discrete)
 Null element: binary value 0 (false, no, low, open, off, empty)
 Unit element: binary value 1 (true, yes, high, closed, on, full)
 Logical variable (bit : binary digit)
 Quantity represented by a symbol (letter or sign) which can take 2
logical states.
 Logical function
 Function represented by groups of variables linked by logical
operators which can only take 2 logical states 0 (false point) or 1 (true
point).
Binary system:

logical function
I L
logical variable off, on
open, closed
Introduction: The truth table

The truth table


 Let F be a function of n variables. The truth table of F is
a table of n+1 columns and 2n rows in which all appear
the combinations of entries associated with the
corresponding value of the function.

I L
0 0 False point
I L 1 1 True point
Open
Closed On
Off
Introduction
 Convention for writing the truth table :
The variables a, b, and c a b c f(a,b,c) f(a,b,c) is a function
represent a binary word 0 0 0 0 1 logic of 3 variables

Ordre binaire naturel


(a b c)2 1 0 0 1 0
2 0 1 0 0 True points
3 0 1 1 1
4 1 0 0 1
5 1 0 1 1 False points
6 1 1 0 0
7 1 1 1 0
(N)10 is the decimal equivalent of the word (a b c)2 with :
(N)10 = 20c + 21b + 22a (binary encoding) where :
- c represents the least significant bit (LSB) or low order bit and
- a represents the most significant bit (MSB) or high order bit
- Example : (1 0 1)2 = 20  1 + 21  0 + 22  1 = 1 + 0 + 4 = (5)10
truth table
truth table
truth table
truth table
Fundamental operators
 NOT: complement function or inverse function. It is a function f of a
variable x such that:

f(x) = x

binary system :

x f(x)

Truth table: symbol :


x f(x) 1
0 1
1 0 CEI standard IEEE Standard
Fundamental operators
 AND: logical product. It is a function f of several variables equivalent
to the intersection in set theory. It takes the value 1 if all variables
are simultaneously equal to 1. Let x and y be two Boolean
variables, f(x,y) is written:
:
f(x,y) = x  y = x  y

binary system :
Switches connected
in series x y f(x,y)

Truth table : symbol :


x y f(x,y)
0 0 0 &
0 1 0
1 0 0 CEI standard IEEE Standard
1 1 1
Fundamental operators
 OR : logical sum (produel). It is a function f of several variables
equivalent to the union in set theory. It takes the value 1 if at least
one variable is equal to 1. Let x and y be two Boolean variables,
f(x,y) is written:

f(x,y) = x + y = x  y

binary system :
Switches connected x
in parallel
y f(x,y)

Truth table : symbol :


:
x y f(x,y)
0 0 0 ≥1
0 1 1
1 0 1 CEI standard IEEE Standard
1 1 1
Fundamental operators
 NAND: It takes the value 1 if at least one variable is equal to 0. It
is a complete operator because it allows for the realization of the
three basic operators of Boolean algebra. Let x and y be two Boolean
variables, f(x,y) is written as:

f(x,y) = x  y

Truth table : symbol :


:
x y xy f(x,y)
0 0 0 1 &
0 1 0 1
1 0 0 1 CEI standard IEEE Standard
1 1 1 0
Fundamental operators
 NOR : It takes the value 1 if all the variables are simultaneously
equal to 0. It is also a complete operator. Let x and y be two Boolean
variables, f(x,y) is written as :

f(x,y) = x + y

Truth table : symbol :


:
x y x+y f(x,y)
0 0 0 1 ≥1
0 1 1 0
1 0 1 0 CEI standard IEEE Standard
1 1 1 0
Fundamental operators
 XOR : It takes the value 1 if and only if the number of variables
equal to 1 is odd. Let x and y be two Boolean variables, f(x,y) is
written as :

f(x,y) = x  y = xy + xy

binary system :
:

x y f(x,y)

Truth table : symbol :


:
x y f(x,y)
0 0 0 =1
0 1 1
1 0 1 CEI standard IEEE Standard
1 1 0
Fundamental operators
 XNOR : It takes the value 1 if and only if the number of variables
equal to 1 is even. Let x and y be two Boolean variables, f(x,y) is
written as :

f(x,y) = x  y = xy + xy

binary system :
:

x y f(x,y)

Truth table : symbol :


:
x y xy f(x,y)
0 0 0 1 =1
0 1 1 0
1 0 1 0 CEI standard IEEE Standard
1 1 0 1
Fundamental operators
 Operators of a single variable:
 Null function : f(x) = 0.  Unit function : f(x) = 1.
Truth table : Truth table :
x f(x) x f(x)
0 0 0 1
1 0 1 1

 YES: Identity function : f(x) = x.


binary system :
:
x f(x)

Truth table : symbol :


:
x f(x) 1
0 0
1 1 CEI standard IEEE Standard
Boolean algebra
Properties and theorems
 Identity (neutral element) : A 0 A+0 A 1 A1
A+0=A 0 0 0 0 1 0
A1=A 1 0 1 1 1 1

A A A
 involution : 0 1 0
A=A 1 0 1

 complementarity : A A A+A A A AA


A+A=1 0 1 1 0 1 0
AA=0 1 0 1 1 0 0
Boolean algebra
 commutativity : A B A + B
A B B + A
B A
0 0 0 0
A+B=B+A
0 1 1
0 1
0
AB=BA
1 0 1
0 1
0
1 1 1 1

 associativity : A B C B+C
BC A+(B+C)
A(BC) A+B
AB (A+B)+C
(AB)C
0 0 0 0 0 0 0
 A + (B + C) = (A + B) + C
0 0 1 01 1
0 0 1
0
 A  (B  C) = (A  B)  C
0 1 0 01 1
0 1
0 1
0
0 1 1 1 1
0 1
0 1
0
1 0 0 0 1
0 1
0 1
0
1 0 1 01 1
0 1
0 1
0
1 1 0 01 1
0 1 1
0
1 1 1 1 1 1 1
Boolean algebra
 Distributivity :
 AND on OR : A  (B + C) = (A  B) + (A  C) = AB + AC
 OR on AND : A + (BC) = (A + B)  (A + C)

A B C B+C
BC A(B+C)
A+(BC) A+B
AB A+C
AC (A+B)(A+C)
AB+AC
0 0 0 0 0 0 0 0
0 0 1 01 0 0 0
1 0
0 1 0 01 0 0
1 0 0
0 1 1 1 0
1 0
1 0
1 0
1
1 0 0 0 0
1 0
1 0
1 0
1
1 0 1 01 1 0
1 1 1
1 1 0 01 1 1 0
1 1
1 1 1 1 1 1 1 1
Boolean algebra
 Idempotence (no exponent or coefficient) :
AA=A A A AA A A A+A
A+A=A 0 0 0 0 0 0
1 1 1 1 1 1

 Absorbing element : A 0 A0 A 1 A+1


0 0 0 0 1 1
A0=0
1 0 0 1 1 1
A+1=1

 absorption : A B A+B
AB A+(AB)
A(A+B)
0 0 0 0
 A  (A + B) = A
0 1 1
0 0
 A + (A  B) = A
1 0 1
0 1
 Demonstrate algebraically 1 1 1 1
these two relations.
Boolean algebra
 De Morgan : A B A+B
AB A+B
AB A B A+B
AB
0 0 0 1 1 1 1
A+B=AB
0 1 1
0 0
1 1 0 0
1
AB=A+B
1 0 1
0 0
1 0 1 0
1
1 1 1 0 0 0 0

 Another identity to demontrate algebraically :


 AB + AB = B
 (A + B)  (A + B) = B
 A + AB = A + B
 A  (A + B) = AB

 Principle of duality
 The dual expression of any logical expression (not equation) is
obtained by swapping the AND and OR operators and the elements 0
and 1 appearing in the expression..
Boolean algebra
 Exercice :
 Using the definitions, properties, and theorems of Boolean algebra,
develop and simplify the function defined by the following equation :

F(a,b,c,d,e) = ab  bc + ce + de


Representation of logical functions
 The logical equation is given directly.
 Or by extracting it from the truth table :

a b c f(a,b,c) Points vrais : Disjunctive normal form :


0 0 0 1 F(0,0,0) = 1 = a b c It includes only the minterms for
0 0 1 0 F(0,1,1) = 1 = a b c which the particular value of the
0 1 0 0 F(1,0,0) = 1 = a b c function is equal to 1 (true points).
0 1 1 1 F(1,0,1) = 1 = a b c The number of terms in the union is
equal to the number of 1s in the
1 0 0 1
function as shown in the truth table.
1 0 1 1
1 1 0 0
1 1 1 0

f(a,b,c) = abc + abc + abc + abc


Representation of logical functions
 Extraction of a logical equation from the truth table :

a b c f(a,b,c) Points faux : Conjunctive normal form :


0 0 0 1 F(0,0,1) = 0 = a+b+c It includes only the maxterms for
0 0 1 0 F(0,1,0) = 0 = a+b+c which the particular value of the
0 1 0 0 F(1,1,0) = 0 = a+b+c function is equal to 0 (false points).
0 1 1 1 F(1,1,1) = 0 = a+b+c The number of terms in the union is
equal to the number of 0s in the
1 0 0 1
function as shown in the truth table.
1 0 1 1
1 1 0 0
1 1 1 0

f(a,b,c) = (a+b+c)(a+b+c)(a+b+c)(a+b+c)
Representation of logical functions
 Exemple : a b c f(a,b,c)
bc f(a,b,c)
0 0 0 00 0
 F(a,b) = a  bc
0 0 1 00 0
 3 variables a, b et c
0 1 0 00 0
 F(a,b) = a  bc 0 1 1 11 1
 F(a,b) = abc + abc 1 0 0 01 1
 F(a,b) = abc + a(b+c) 1 0 1 01 1
 F(a,b) = abc + ab + ac 1 1 0 01 1
1 1 1 10 0
 F(a,b) = abc + ab + ac
 F(a,b) = abc + ab(c+c) + ac(b+b)
 F(a,b) = abc + abc + abc + abc + abc
 F(a,b) = abc + abc + abc + abc
Representation of logical functions
Karnaugh maps
 Let F be a function of n variables.
 The Karnaugh map is a table of 2n cells corresponding
to the 2n input combinations in which the
corresponding values of the function are noted.

a b c f(a,b,c) bc The transition from


0 0 0 0 a 00 01 11 10 one cell to a
0 0 1 1 neighboring cell is
0 1 0 1 0 0 1 0 1 done by changing the
0 1 3 2
0 1 1 0 value of only one
1 1 0 1 0 variable at a time
1 0 0 1 4 5 7 6 (reflected binary code
1 0 1 0 tableau de Karnaugh or Gray code).
1 1 0 0
1 1 1 1
Representation of logical functions
Exercice : a
0
b
0
c
0
d
0
f
0
 Construct the Karnaugh map for the 0 0 0 1 1
function f of 4 variables a, b, c, and d 0 0 1 0 1
0 0 1 1 0
defined by the following truth table :
0 1 0 0 1
cd 0 1 0 1 0
ab 00 01 11 10 0 1 1 0 0
0 1 1 1 1
00 0 1 0 1 1 0 0 0 1
0 1 3 2
1 0 0 1 0
01 1 0 1 0 1 0 1 0 0
4 5 7 6
1 0 1 1 1
11 0 1 0 1 1 1 0 0 0
12 13 15 14
1 1 0 1 1
10 1 0 1 0 1 1 1 0 1
8 9 11 10
1 1 1 1 0
Simplification of logical functions
Algebraic method: application of the principles
of Boolean algebra
 Factoring or expansion
 idempotence...

Graphical method: using Karnaugh maps


 Two cells are adjacent if the transition from one to the
other occurs by changing the state of only one
variable.
 This principle also applies to sets of adjacent cells
consisting of 2n cells.
Simplification of logical functions
 Exemple :
cd
ab 00 01 11 10

00
0 1 3 2

01
4 5 7 6

11
12 13 15 14

10
8 9 11 10
Simplification of logical functions
 Méthode de Karnaugh :
 Depending on the desired form, group the adjacent cells of the same
value (either 0 or 1) into the largest possible sets that correspond to
powers of 2. All these groupings correspond to prime implicants (or
minterms) and form the complete prime base. The sum of these
minterms gives a simplified expression of the logical function but not
its minimal form..
 The minimal form is obtained by summing the main prime implicants
(irredundant), meaning a grouping in which there is at least one cell
that can only be grouped by itself. Sometimes, multiple possibilities
are available, and the following rules will be followed :
 All the 1 (or all the 0) must be grouped at least once.
 The largest groupings should be prioritized.
 The cells to be grouped must be grouped a minimum number of times
(starting with those that can only be grouped in one way).
Simplification of logical functions
 Exemple :
F=abcd+abcd+abcd+abcd+abcd+abcd+abcd
F=abcd+abcd+abcd+abcd+abcd+abcd+abcd+abcd+abcd
F=acd(b+b)+abc(d+d)+bd(ac+ac+ac+ac)+abcd
F=acd+abc+bd[a(c+c)+a(c+c)]+abcd cd
F=acd+abc+bd(a+a)+abcd ab 00 01 11 10
F=acd+abc+bd+abcd 00 1 0 0 0 acd
F=acd+abc(d+d)+bd+abcd
F=acd+abcd+abcd+bd+abcd 01 1 1 1 0 abc

F=acd(1+b)+bd(ac+1)+abcd
11 0 1 1 0 bd
F=acd+bd+abcd
F is the sum of the main prime 10 0 0 0 1 abcd
implicants (irredundant).
Prime
Redundant
implicants
Simplification of logical functions
 Exercice :
 Simplify under the first and second technological forms the function
defined by the following truth table using the Karnaugh map method.:

a b c f(a,b,c)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Simplification of logical functions
 Case of incompletely defined functions:
 Some combinations can never exist.
 The value of the function does not matter for certain combinations of
variables.
 The value of the function is said to be indifferent or the forbidden
combination. The value of the function is then denoted by Φ or X and
can take either the value 1 or 0, depending on whether it is used for
simplification.
cd
ab 00 01 11 10

00 1 0 0 0 acd

01 1 1 Φ 0 bd

11 0 Φ 1 0 abd
F=acd+bd+abd
10 Φ Φ 0 1
Simplification of logical functions
 Exercice :
 Simplify the following function under the first technological form using
the Karnaugh map method :

cde
ab 000 001 011 010 110 111 101 100

00 1 1 1 1 0 1 0 1

01 1 0 0 0 0 0 0 1

11 1 0 0 0 1 0 0 1

10 1 1 1 1 0 1 1 1
Simplification of logical functions
 Another approach :

c=0 c=1

de de
ab 00 01 11 10 ab 00 01 11 10

00 1 1 1 1 00 1 0 1 0

01 1 0 0 0 01 1 0 0 0

11 1 0 0 0 11 1 0 0 1

10 1 1 1 1 10 1 1 1 0
Representation of numbers: the codes
 Natural integers
 Base of a numbering system
 Base conversion
 Signed integers
 Special codes
 BCD code
 Gray code
 ASCII code
Representation of numbers: codes
-To encode integers, real numbers, or characters, bits are often grouped in
packets: a group of bits must form a code.

-Numbering systems:
A base consists of the set of different digits (or characters) used in the
numbering system. Each number can be expressed in polynomial form by
decomposing it according to the integer powers (positive or negative) of the
numbering base..

-Example :
- Base 10 or decimal, where each digit can take 10 values, and a number is a
polynomial of 10. :
Polynomial form :

8467110
base
8467110 8.10 4 + 4.103 + 6.10 2 + 7.101 + 1.100
Most significant Least rank 4 3 2 1 0
digit significant digit
Representation of numbers: codes
- Another example with a real number
Polynomial form:

48,5210 48.52 10 4.101 + 8.100 + 5.10 1 + 2.10 2


rank 1 0 -1 -2

- The rank of a digit in a number represented in a base is the exponent of the


base associated with that digit in the polynomial representation.
- In general, let b be a base containing b characters ai such that :
ai  0,1,2,...., b  1 , the polynomial representation of an integer N is :

n
N =  ai .b i where n is the rank of the most significant digit.
i =0
Representation of numbers: codes
- Several bases are possible, but two of decimal binary hexadecimal
them are of particular interest: bases 2 0 0000 0
and 16. 1 0001 1
2 0010 2
Polynomial form in binary base : 3 0011 3
4 0100 4
101012 1.24 + 0.23 + 1.22 + 0.21 + 1.20 5 0101 5
rank 4 3 2 1 0
6 0110 6
7 0111 7
8 1000 8
9 1001 9
Polynomial form in hexadecimal base :
10 1010 a
a 2b3916 a.16 4 + 2.163 + b.16 2 + 3.161 + 9.160 11 1011 b
12 1100 c
rank 4 3 2 1 0
13 1101 d
14 1110 e
15 1111 f
Representation of numbers: codes
- Base conversion
Converting from one base to another is an important question.
Conversion to base 10 remains the simplest, as it only requires calculating the
value from the polynomial representation.

By revisiting the previous examples :


101012 = 1.24 + 0.23 + 1.22 + 0.21 + 1.20 = 2110
a2b3916 = a.164 + 2.163 + b.162 + 3.161 + 9.160 = 66642510

Note :
There is a very useful grouping, the byte, which consists of 8 bits. The
value of a byte ranges from 0 to 255 in base 10. Bits are grouped in
packets of 4 and expressed in base 16,

Example :
100011012 = 8d 16
Representation of numbers: codes

- Base conversion from decimal to binary :

27 2
1 13 2

1
6 2
27 10 = 110112
3 2
0
1 1 2

1 0

- The conversion from hexadecimal to binary and from binary to hexadecimal is


simpler.
 f 8ab316 = (1111 1000 1010 1011 0011) 2
1011000101 11012 = 0010 1100 0101 11012 = 2c5d 16

- When converting from hexadecimal to decimal (or vice versa), the conversion
goes through binary to simplify the process.
Representation of numbers: codes
Signed integers :
The traditional method for encoding a signed number is called "sign-
magnitude," i.e., for a number coded on N bits, the most significant bit is used
to code the sign, and the remaining N-1 bits represent the absolute value of the
number :
 
(17)10 = 1 10001 2

This method, although simple in appearance, remains complicated to use for a


digital circuit.

The method used in these cases is the two's complement code.


Representation of numbers: codes
BCD code (Binary Coded Decimal)
It allows encoding a decimal number in binary as with the hexadecimal
base (except that we only have 10 values instead of 16).
Decimal BCD
0 0000
1 0001
2 0010
This code remains incomplete since it does
3 0011
not use all combinations, but it is useful when
4 0100 dealing with decimal numbers in digital
5 0101 electronics.
6 0110
7 0111
8 1000
9 1001
Representation of numbers: codes
Gray code:
This code (also called reflected binary code) is an adjacent code where only
one bit changes when transitioning from one value to the next. It is used in
Karnaugh maps.

Binary Gray
b2 b1 b0 gb12 bg11 g0

0 0 0 0 0 0
The construction is done graphically
0 0 1 0 0 1 by iteration or from the binary code
0 1 0 0 1 1 by creating an axis of symmetry.
0 1 1 0 1 0
1 0 0 1 1 0
1 0 1 1 1 1
1 1 0 1 0 1
1 1 1 1 0 0
Representation of numbers: codes

ASCII code: American Standard Code for Information Interchange


Combinational Logic Circuit
 Fundamental logic circuits :
 Summary:
Combinational Logic Circuit
Combinational logic circuits are circuits made up of the above gates operating
simultaneously to perform one or more logical functions.

Combinational To a combination of inputs (the input),


. logic circuit . there corresponds only one combination
. . of outputs.
. .

The output appears after the application of the input with a certain delay
called propagation time.
Combinational Logic Circuit
Combinational circuits can be used, for example :
 to convert bits into digits representing a number (or letters or a specific code).
These circuits are called encoders (or decoders for the inverse operation).
For example, a Gray encoder or BCD.
 to perform arithmetic operations on numbers. For example, an adder or a
multiplier.
 to transmit or receive information over a single transmission line (a serial
line), which requires converting a number written in parallel form into a
sequence of bits in series and vice versa. This is the role of
multiplexer/demultiplexer circuits. Here is, for example, a serial-to-parallel
transformation followed by a parallel-to-serial transformation. :

Bytes Bytes
Serial bits Serial bits
DEMUX Processing MUX
Combinational Logic Circuit
The demultiplexer:
The demultiplexer is a circuit that directs an input to an output whose address
is provided in the form of a binary-coded number.
Y0
Demux 2 Y1
G to 4 Y2
Y3

a1 a0

The diagram of a demultiplexer is : Its truth table is equal to :


Combinational Logic Circuit
The decoder:
The decoder is in the same family as the demultiplexer, but with the input G
permanently set to 1. This results in a single 1 at the output among zeros.
Y0
Décodeur Y1
2 to 4 Y2
Y3

a1 a0

Its truth table is equal to :


Combinational Logic Circuit
The multiplexer :
The multiplexer is the inverse function of the demultiplexer. It is a data selector
or converging switch. It can transform information appearing in the form of \( n
\) bits in parallel into information presented as \( n \) bits in series. The input
line, selected by its address, is connected to the output.

I0
I1 mux
I2 2 to 4 Y
I3

a1 a0 Its truth table is equal to :


The diagram of a multiplexer is :
N a1 a0 Y
0 0 0 I0
1 0 1 I1
2 1 0 I2
3 1 1 I3
Combinational Logic Circuit
The priority encoder :
The priority encoder takes an \( n \)-bit word as input and produces an \( m \)-bit
word at the output corresponding to the index of the most significant non-zero
bit. A question arises when all the input bits are 0. In this case, an indicator
signal (called GS) is added, which is set to 1 only in this situation.

I0
I1 Priority a1
I2 encoder a0
I3

Its truth table is equal to : Inputs Outputs GS


I3 I2 I1 I0 a1 a0 0
1 - - - 1 1 0
0 1 - - 1 0 0
0 0 1 - 0 1 0
0 0 0 1 0 0 0
0 0 0 0 0 0 1
Combinational Logic Circuit
 Arithmetic circuits :
Arithmetic circuits perform binary operations such as addition, multiplication,
comparison, or combine these basic operators within an ALU (Arithmetic and
Logic Unit)..
Addition : Ai Bi
A 0110 The adder processing the i-th bit :
B 0011 Ci Adder Ci 1
S 1001
Si
The input Ci 1 is the carry-in, and the output is the carry-out. The full C i adder
is constructed as follows: :

A3 B3 A2 B2 A1 B1 A0 B0
C3 Adder C2 Adder C1 Adder
C0 Adder
C1 = 0

S3 S2 S1 S0
There are other circuits such as the multiplier, divider, or comparator….
Combinational Logic Circuit
 Memory
PROMs are programmable read-only memories..
Examples (4-word by 4-bit PROM)):

The address applied to the inputs ( a1 a0 )


causes, via the address decoder, the
corresponding address line to be set to 1. If
the fuse existing between this line and the
output is intact, this output Yn will be 1. If
the fuse has been blown during
programming, the output will be 0.

Truth table: aa11 a0 Y0 Y1 Y2 Y3


0 0 0 1 0 1
0 1 0 0 1 0
1 0 0 0 1 0
1 1 1 0 1 1
Combinational Logic Circuit
 Implementation of a combinational logic function :
Example :
N a2 a1 a0 F 1. The function is written in the form of :
0 0 0 0 1 F = 1.a2 .a1.a0 + 1.a2 .a1.a0 + 0.a2 .a1.a0 + 0.a2 .a1.a0 + 0.a2 .a1.a0 + 1.a2 .a1.a0 + 1.a2 .a1.a0 + 0.a2 .a1.a0

1 0 0 1 1
2. Then:
2 0 1 0 0 F = 1.a2 .a1.a0 + 1.a2 .a1.a0 + 1.a2 .a1.a0 + 1.a2 .a1.a0

3 0 1 1 0
3. Its simplified form by the Karnaugh map :
4 1 0 0 0
F = a2 .a1 + a1.a0 + a2 .a1.a0
5 1 0 1 1
6 1 1 0 1
7 1 1 1 0
Combinational Logic Circuit
 Implementation of a combinational logic function :
Example :
With the first form, we have

F = 1.a2 .a1.a0 + 1.a2 .a1.a0 + 0.a2 .a1.a0 + 0.a2 .a1.a0 + 0.a2 .a1.a0 + 1.a2 .a1.a0 + 1.a2 .a1.a0 + 0.a2 .a1.a0
We derive
F = a1.a0 .(1.a2 + 0.a2 ) + a1.a0 .(1.a2 + 1.a2 ) + a1.a0 .(0.a2 + 1.a2 ) + a1.a0 .(0.a2 + 0.a2 )

Therefore
F = a1.a0 .a2 + a1.a0 .1 + a1.a0 .a2 + a1.a0 .0
As the output equation of a multiplexer is F = I 0 .a1.a0 + I1.a1.a0 + I 2 .a1.a0 + I 3 .a1.a0
we obtain the following diagram by identifying the two expressions. :
a1
a0

a2 I0
1 I1
F
a2 I2
0 I3
Combinational Logic Circuit
 Implementation of a combinational logic function :
Example :
With
F = 1.a2 .a1.a0 + 1.a2 .a1.a0 + 1.a2 .a1.a0 + 1.a2 .a1.a0
We implement a decoder and an OR gate.
Combinational Logic Circuit
 Implementation of a combinational logic function :
Example :
With the form simplified by the Karnaugh map. :
F = a2 .a1 + a1.a0 + a2 .a1.a0
We implement F using NAND gates. :
Combinational Logic Circuit
 The choice of the circuit or circuits depends on the logical function(s) to be
implemented. Each method has its advantages and disadvantages. It is
necessary to consider the number and cost of the packages used to calculate
the cost of the function, and to determine the number of logical layers
crossed to calculate its speed. The areas of application are as follows:
 Elementary gates are used when there are few functions and input variables.
 The decoder is used when there are few input variables (the packages have
a limited number of pins) and many outputs (an OR gate is wired for each
output).
 The multiplexer allows for the implementation of only one function (it has a
single output) with a few input variables (one more than the decoder with an
equivalent package size). It requires the simplest wiring and the smallest
package.
 The PROM is used when there are many input variables and few output
variables (a maximum of 8 or 16). For example, a 1024x8 PROM (1024
bytes) allows for the implementation of 8 functions with 10 variables each.
Combinational Logic Circuit
Temporal characteristics :
Sequential logic
Ei
Combinational Sj +
system
Sj-

Sequentiel system
Plan
 Flip-flops
 Counters
 Registers
 Memories

You might also like