GupShup Study
 
  
Computer Structure & Introduction to Digital Computers Lecture Notes by Guy Even
Rajan Sharma

Computer Structure & Introduction to Digital Computers Lecture Notes by Guy Even

Rajan Sharma | 29-Feb-2016 |
Digital Computers , The digital abstraction , Foundations of combinational circuits , Trees , Decoders and Encoders , Combinational modules , Addition , Fast Addition , Signed Addition , Flip-Flops , Synchronous Circuits , Digital Computers , The digital abstraction , Foundations of combinational circuits , Trees , Decoders and Encoders , Combinational modules , Addition , Fast Addition , Signed Addition , Flip-Flops , Synchronous Circuits ,

Hi friends, here Rajan Sharma uploaded notes for Computer Structure and Digital Computers with title Computer Structure & Introduction to Digital Computers Lecture Notes by Guy Even. You can download this lecture notes, ebook by clicking on the below file name or icon.

Contents
1 The digital abstraction 1
1.1 Transistors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 From analog signals to digital signals . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Transfer functions of gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 The bounded-noise model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 The digital abstraction in presence of noise . . . . . . . . . . . . . . . . . . . 7
1.5.1 Redening the digital interpretation of analog signals . . . . . . . . . 7
1.6 Stable signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Foundations of combinational circuits 11
2.1 Boolean functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Gates as implementations of Boolean functions . . . . . . . . . . . . . . . . . 11
2.3 Building blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Combinational circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Cost and propagation delay . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 Syntax and semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Trees 21
3.1 Trees of associative Boolean gates . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.1 Associative Boolean functions . . . . . . . . . . . . . . . . . . . . . . 21
3.1.2 or-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.3 Cost and delay analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Optimality of trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.2 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4 Decoders and Encoders 31
4.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Values represented by binary strings . . . . . . . . . . . . . . . . . . . . . . 33
4.3 Decoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3.1 Brute force design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3.2 An optimal decoder design . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3.3 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3.4 Cost and delay analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.4 Encoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4.2 Cost and delay analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.4.3 Yet another encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5 Combinational modules 47
5.1 Multiplexers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.1.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Cyclic Shifters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.3 Priority Encoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.3.1 Implementation of u-penc(n) . . . . . . . . . . . . . . . . . . . . . . 54
5.3.2 Implementation of b-penc . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4 Half-Decoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.4.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.4.3 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.4.4 Cost and delay analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.5 Logical Shifters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6 Addition 65
6.1 Denition of a binary adder . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.2 Ripple Carry Adder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.2.1 Correctness proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.2.2 Delay and cost analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.3 Carry bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.4 Conditional Sum Adder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.4.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.4.3 Delay and cost analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.5 Compound Adder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.5.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.5.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.5.3 Delay and cost analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7 Fast Addition 75
7.1 Reduction: sum-bits 7

    Attachment Lists

    If download doesn't start in application like IDM then press Alt + click on download button to start download
  • Computation Structures.pdf (Size: 823.47KB) Dowland
Share With Friends :  

No any Comment yet!