Binary Logic

Binary Logic

Integrated Circuits • A small silicon semiconductor crystal called a chip, containing electrical components such as transistor, diodes, resistors and capacitors. • Two Types of Package: Dual-in-Line Package and Flat Package • SSI (Small Scale Integration)<10 gates • MSI (Medium Scale Integration) 10 to 100

- Decoders, adders, Multiplexers • LSI (Large Scale Integration)>100 - processors, memory chips and PLD’s(programmable Logic device)

• VLSI (Very Large Scale Integration) -1000

- large memory arrays, complex microcomputer chips

Binary Logic • Two discrete values – True or false – Yes or no – 0 or 1

• Describes the mathematical way, the manipulation and processing of binary information.

Logic Gates • Basic Gates – AND – OR – NOT

• Universal Gates – NAND – NOR

• Special Gates – X-or – X-Nor

AND Gate • Symbol is dot – C=A·B

• Or no symbol – C = AB

• C is 1 only if – Both A and B are 1

OR Gate • Symbol is + – Not addition – C=A+B

• C is 1 if either 1 – Or both 1

NOT Gate • Unary • Symbol is bar – C=Ā

• Inversion

Logic Gates

Logic Gates

Positive and negative logic • Positive logic: High-level H represents logic – 1.

• Negative Logic: Low level L represents logic – 1.

Logic Gates

Special characteristics • Fan-in: Number of inputs of a logic gate • Fan-out/Loading: Number of standard loads that the output of a gate can drive without impairing its normal operation • Propagation delay: Average transition delay time for a signal to propagate from input to output when the binary signals change in value (expressed in ns) • Power dissipation: Supplied power (mW) required to operate the gate • Noise Margin: Maximum noise voltage added to the input signal of a digital circuit that does not cause an undesirable change in the circuit output.

Boolean Algebra-History • Algebraic Structure: Defined as set of elements, a set of operators and a number of unproved axioms or postulates. • Boolean Algebra- George Boole in 1854 • Switching Algebra ( Two valued Boolean Algebra) – Shanon in 1938 • Postulates formulated –Huntington in 1904

Comparison of Boolean algebra and ordinary algebra Huntington postulates

Ordinary algebra

Do not include associative law

Holds associative law

+ over • distributive law is valid

+ over • distributive law is invalid

Does not have additive and multiplicative inverses (hence no subtraction & division)

Additive and multiplicative inverse exists

Complement exists

Complement is not available

Finite set of elements

Real numbers

Boolean Operator Precedence • The order of evaluation in a Boolean expression is: – Parenthesis – NOT – AND – OR • Consequence: Parentheses appear around OR expressions • Example: F = A(B + C)(C + D)

References • M. Morris Mano – Digital Logic and Computer Design PHI – 5th Edition- 2004. pp. 18, 20, 25 – 29

Common postulates to formulate various algebraic structures • Closure – A Set S is closed, if for every pair of elements of S, the binary operator specified a rule for obtaining a unique element of S.

• Associative law – (x*y)*z = x*(y*z) for all x, y, z in S

• Commutative law – x * y = y * x for all x, y in S

• Identity element – e * x = x * e = x for every x in S [ 0 is the identity element of + and 1 is the identity element of *]

• Inverse – x * y = e => y is the inverse of x and vice versa

• Distributive law – x * (y•z) = (x * y) • (x * z)

Huntington Postulates • Boolean algebra is an algebraic structure defined on a set of elements B together with two binary operators + and • provided the following postulates are satisfied • Closure with respect to + and • • Identity element: x + 0 = 0 + x = x; x •1 = 1 •x = x • Commutative: x + y = y + x; x • y = y • x • Distributive: (• over +: x • (y + z) = (x • y) + (x • z)) (+ over •: x + (y • z) = (x + y) • (x +z)) • Complement: X + X = 1 and x • = 0X • There exists at least two elements x, y Є B such that x ≠ y

Basic Theorems

18.

x+xy =x

19.

x(x+y) = x

Absorption

• Duality – To obtain the dual of an algebraic expression, interchange OR and AND operators and replace 1’s by 0’s and 0’s by 1’s. • Unless it happens to be self-dual, the dual of an expression does not equal the expression itself. • Example: F = (A + C) · B + 0 dual F = (A · C + B) · 1 = A · C + B • Example: G = X · Y + (W + Z) dual G = (X + Y) . (W . Z) • Example: H = A · B + A · C + B · C dual H = A + B . A + C . B + C