Logic Circuits and Basic Computer in CSE.pptx

Logic Circuits and Basic Computer

1. Logic Gates & Circuits Boolean Algebra and Logic Circuits Basic Computer Architecture

2. In this chapter you will learn about: Logic Gates Logic Circuits Boolean algebra Fundamental concepts and basic laws of Boolean algebra Boolean function and minimization Logic gates Logic circuits and Boolean expressions Combinational circuits and design Learning Objectives

3. Logic Gates Logic gates are electronic circuits that operate on one or more input signals to produce standard output signal Are the building blocks of all the circuits in a computer Some of the most basic and useful logic gates are - AND, OR, NOT, NAND and NOR gate

4. AND Gate Physical realization of logical multiplication (AND) operation Generates an output signal of 1 only if all input signals are also 1 AND Gate (Block Diagram Symbol and Truth Table)

5. OR Gate Physical realization of logical addition (OR) operation Generates an output signal of 1 if at least one of the input signals is also 1 OR Gate (Block Diagram Symbol and Truth Table)

6. NOT Gate Physical realization of complementation operation Generates an output signal, which is the reverse of the input signal

7. NAND Gate Complemented AND gate Generates an output signal of: ① 1 if any one of the inputs is a ② when all the inputs are 1

8. NOR Gate Complemented OR gate Generates an output signal of: ① 1 only when all inputs are ② if any one of inputs is a 1

9. Logic Circuits When logic gates are interconnected to form a gating / logic network , it is known as a combinational logic circuit The Boolean algebra expression for a given logic circuit can be derived by systematically progressing from input to output on the gates The three logic gates ( AND, OR, and NOT ) are logically complete because any Boolean expression can be realized as a logic circuit using only these three gates

10. Finding Boolean Expression of a Logic Circuit (Example 1)

11. Finding Boolean Expression of a Logic Circuit (Example 2)

12. Constructing a Logic Circuit from a Boolean Expression (Example 1)

13. Constructing a Logic Circuit from a Boolean Expression (Example 2)

14. Universal NAND Gate NAND gate is an universal gate , it is alone sufficient to implement any Boolean expression To understand this, consider: Basic logic gates (AND, OR, and NOT) are logically complete Sufficient to show that AND, OR, and NOT gates can be implemented with NAND gates

15. Implementation of NOT, AND and OR Gates by NAND Gates

16. Universal NOR Gate NOR gate is an universal gate , it is alone sufficient to implement any Boolean expression To understand this, consider: Basic logic gates (AND, OR, and NOT) are logically complete Sufficient to show that AND, OR, and NOT gates can be implemented with NOR gates

17. Implementation of NOT, OR and AND Gates by NOR Gates

18. Boolean Algebra An algebra that deals with binary number system George Boole (1815- 1864) , an English mathematician, developed it for: Simplifying representation Manipulation of propositional logic In 1938, Claude E. Shannon proposed using Boolean algebra in design of relay switching circuits Provides economical and straightforward approach Used extensively in designing electronic circuits used in computers

19. Boolean Algebra An algebra that deals with binary number system George Boole (1815- 1864) , an English mathematician, developed it for: Simplifying representation Manipulation of propositional logic In 1938, Claude E. Shannon proposed using Boolean algebra in design of relay switching circuits Provides economical and straightforward approach Used extensively in designing electronic circuits used in computers

20. Fundamental Concepts of Boolean Algebra Use of Binary Digit Boolean equations can have either of two possible values, and 1 Logical Addition Symbol ‘ + ’, also known as ‘ OR ’ operator, used for logical addition . Follows law of binary addition Logical Multiplication Symbol ‘ . ’, also known as ‘ AND ’ operator, used for logical multiplication. Follows law of binary multiplication Complementation Symbol ‘ - ’, also known as ‘ NOT ’ operator, used for complementation. Follows law of binary compliment

21. Operator Precedence Each operator has a precedence level Higher the operator’s precedence level , earlier it is evaluated Expression is scanned from left to right First, expressions enclosed within parentheses are evaluated Then, all complement (NOT) operations are performed Then, all ‘ ⋅ ’ (AND) operations are performed Finally, all ‘+’ (OR) operations are performed

22. Operator Precedence

23. Postulates of Boolean Algebra Postulate 1: ① A = 0, if and only if, A is not equal to 1 ② A = 1, if and only if, A is not equal to 0 Postulate 2: ① x + 0 = x ② x ⋅ 1 = x Postulate 3: Commutative Law ① x + y = y + x ② x ⋅ y = y ⋅ x Postulates - are the basic structure from which lemmas and theorems are derived. Theorem - a mathematical statement that is proved using rigorous mathematical reasoning. Lemma - a minor result whose sole purpose is to help in proving a theorem. It is a stepping stone on the path to proving a theorem.

24. Postulates of Boolean Algebra Postulate 4: Associative Law ① x + (y + z) = (x + y) + z ② x ⋅ (y ⋅ z) = (x ⋅ y) ⋅ z Postulate 5: Distributive Law ① x ⋅ (y + z) = (x ⋅ y) + (x ⋅ z) ② x + (y ⋅ z) = (x + y) ⋅ (x + z) Postulate 6: ① x + x = 1 ② x ⋅ x =

25. The Principle of Duality

26. Some Important Theorems of Boolean Algebra y

27. Methods of Proving Theorems The theorems of Boolean algebra may be proved by using one of the following methods: ① By using postulates to show that L.H.S. = R.H.S ② By Perfect Induction or Exhaustive Enumeration method where all possible combinations of variables involved in L.H.S. and R.H.S. are checked to yield identical results ③ By the Principle of Duality where the dual of an already proved theorem is derived from the proof of its corresponding pair

28. Proving a Theorem by Using Postulates (Example) Theorem: Proof: L.H.S. x + x · y = x = x + x ⋅ y = x ⋅ 1 + x ⋅ y = x ⋅ (1 + y) = x ⋅ (y + 1) = x ⋅ 1 = x = R.H.S. by postulate 2(b) by postulate 5(a) by postulate 3(a) by theorem 2(a) by postulate 2(b)

29. Proving a Theorem by Perfect Induction (Example) Theorem: x + x · y = x

30. Proving a Theorem by Perfect Induction (Example) Theorem: x + x = x

31. Proving a Theorem by Perfect Induction(Example)

32. Boolean Functions A Boolean function is an expression formed with: Binary variables Operators (OR, AND, and NOT) Parentheses, and equal sign The value of a Boolean function can be either or 1 A Boolean function may be represented as: An algebraic expression, or A truth table

33. Representation as an Algebraic Expression

34. Representation as a Truth Table The number of rows in the table is equal to 2 n , where n is the number of literals in the function

35. Minimization of Boolean Functions Minimization of Boolean functions deals with Reduction in number of literals Reduction in number of terms Minimization is achieved through manipulating expression to obtain equal and simpler expression(s) (having fewer literals and/or terms)

36. Minimization of Boolean Functions

37. Minimization of Boolean Functions Both F 1 and F 2 produce the same result x y z F 1 F 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

38. Try out some Boolean Function Minimization

39. Introduction to Basic Computer Architecture (as per P.K. Sinha, 6th Edition) Control Units, Memory, CPU vs GPU, and Quantum Computing

40. What is Computer Architecture? Definition : The conceptual design and fundamental operational structure of a computer system is called Computer Architecture . Major Components: Control Unit, Memory, Processing Components (CPU/GPU) Computer architecture refers to the design and organization of a computer's core components. The key components are: Control Unit, Memory, Processing Components (CPU/GPU)

41. Control Unit, Memory, and Processing Components A computer is an electronic device that can accept data, process it, and produce results. The basic architecture of a computer system follows the classical Von Neumann model and includes the following primary components: Input Unit – Accepts data and instructions. Central Processing Unit (CPU) – Often called the brain of the computer. Control Unit (CU) : Directs the operation of the processor. Interprets instructions from memory and initiates appropriate operations. Acts like a supervisor coordinating all components. Arithmetic Logic Unit (ALU) : Executes arithmetic and logical operations. Operates on the data fetched from memory or registers. Memory Unit : Stores instructions, data, and intermediate results. Two types: Primary Memory (RAM, ROM, Cache) Secondary Memory (Hard Disk, SSD, etc.) Acts as a bridge between the CPU and storage. These components are interconnected by a system bus (address, data, and control lines) and operate in a fetch-decode-execute cycle . “The CPU is responsible for interpreting and executing most of the commands from the computer's other hardware and software.” — P.K. Sinha

42. What is a GPU and How It Differs from a CPU CPU : Few complex cores Designed for general-purpose operations Suitable for sequential tasks GPU : Contains hundreds or thousands of simpler cores Executes many operations simultaneously Ideal for parallel tasks such as image processing, deep learning, and simulations

43. Block Diagram of CPU: Detailed Analysis of All Components

44. Block Diagram of GPU

45. Thus, a CPU is optimized for latency , while a GPU is optimized for throughput . CPU vs. GPU More details: https://www.codecademy.com/article/cpu-vs-gpu-whats-the-difference-and-which-one-should-you-use Feature CPU GPU Primary Function General-purpose computing Graphics rendering and parallel computing Core Count Few (4-16 typical) Many (hundreds to thousands) Clock Speed Higher (3-5 GHz typical) Lower (1-2 GHz typical) Task Optimization Complex sequential tasks Parallel tasks Memory Access Low latency, smaller bandwidth Higher latency, massive bandwidth Instruction Handling Complex instruction sets Simpler, more specialized instructions Power Consumption Lower per computation Higher overall, but more efficient for parallel tasks Cost per Performance Higher for parallel tasks Lower for parallel tasks Memory Type System RAM Dedicated VRAM (GDDR6, HBM) Cache Size Larger Smaller per core Instruction Pipeline Deep, complex Shallow, simple

46. Basic Architecture of GPU: Cores, Memory Bandwidth, and Parallelism Based on modern computing concepts and parallel processing ideas: Cores : A GPU may have thousands of cores. Each core is designed to run lightweight threads. Memory Bandwidth : Much higher bandwidth than CPU. Enables the GPU to transfer large volumes of data rapidly . Parallelism : Designed for SIMD (Single Instruction, Multiple Data) operations. Ideal for matrix computations and rendering millions of pixels simultaneously. While Sinha emphasizes the CPU’s control and arithmetic capability, GPUs expand on this by enabling massive concurrent computation .

47. Basic Quantum Computing Concepts: Qubits, Superposition, and Entanglement Qubits : A quantum bit or qubit is the smallest unit of information in quantum computing. Unlike classical bits (0 or 1), a qubit can be in both states at once , thanks to superposition . Superposition : A qubit can represent multiple combinations of 0 and 1 simultaneously. This allows quantum computers to evaluate many possibilities at once. Entanglement : When two qubits are entangled, the state of one automatically determines This the state of the other, no matter the distance is key to quantum speedup and teleportation concepts. In comparison to classical computers which evaluate one possibility at a time, quantum computers evaluate all possibilities simultaneously .

48. Conclusion The computer system is composed of input , CPU (with CU and ALU ), memory , and output units . The CPU handles core instruction execution while memory stores necessary data and instructions.With the rise of high-performance demands, GPUs have emerged as specialized processors for parallel tasks. Quantum computing promises to revolutionize the field through principles like superposition and entanglement , though it is still in the experimental phase.