Gate and Circuit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
## In the beginning ...

- `computer` = `the one who computes`

### Origin of modern computing architectures

- Jacquard Loom

<iframe width="560" height="315" src="https://www.youtube.com/embed/MQzpLLhN0fY" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

- Charles Babbage's Analytical Machine

<iframe width="560" height="315" src="https://www.youtube.com/embed/XSkGY6LchJs" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

- Hollerith Census Machine (eventually becomes IBM)

<iframe width="560" height="315" src="https://www.youtube.com/embed/9HXjLW7v-II" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

- ENIAC: First computer

<iframe width="560" height="315" src="https://www.youtube.com/embed/k4oGI_dNaPc" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

### Modern computer architecture

- von Neuman architecture
  - General purpose
  - A binary computer instead of a decimal computer
  - Stored-program

## Logic Gates

- Building blocks of the digital circuitry that implements arithmetic, 
control, and storage functionality in a digital computer.
- Logic gates are created from transistors that are etched into a 
semiconductor material (e.g. silicon chips). 
- Transistors act as switches that control electrical flow through the chip. 
A transistor can switch its state between on or off (between a high or low 
voltage output). Its output state depends on its current state plus its input 
state (high or low voltage).

### 2.1 Basic Logic Gates

- AND, OR, and NOT form a set of basic logic gates from which 
any circuit can be constructed. 



| A | B | A AND B  | A OR B  | NOT A | NOT B |
| - | - | -------- | ------- | ----- | ----- | 
| 0 | 0 | 0        | 0       | 1     | 1     |
| 0 | 1 | 0        | 1       | 1     | 0     |
| 1 | 0 | 0        | 1       | 0     | 1     |
| 1 | 1 | 1        | 1       | 0     | 0     |  

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
## Circuits

- Core functionality of the architecture
  - Instruction Set Architecture (ISA)
- Categories
  - Arithmetic/logic
  - Control
  - Storage
- All three are contained in a standard processor

### 3.1. Arithmetic: Addition



- Mathematical operations:
  - Bit-wise with carry
  - $0 + 0 = 0$
  - $0 + 1 = 1$
  - $1 + 0 = 1$
  - $1 + 1 = 0$ and carry $1$ to the next bit operation (or add 1 to left of the most significant bit position)
- This works for both unsigned and 2's complement notation
- Example 1: 4-bit unsigned $2+6=8$

$$
\ 0010 \\
+\ 0110 \\
\hline
\ 1000
$$  

- Example 2: 4-bit unsigned $11+12=23$

$$
\ 1011 \\
+\ 1100 \\
\hline
\ 10111
$$

- Example 3: 4-bit signed $5-7=5+(-7)=(-2)$
  - Positive to negative conversion in 2's complement: flipped bit and add 1. 
  - $7$: $0111$
  - $-7$: $1000 + 1=1001$

$$
\ 0101 \\
+\ 1001 \\
\hline
\ 1110
$$

$1110=(-1)*(1)*(8)+(1)*(4)+(1)*(2)+(0)*1=(-8)+4+2=(-2)$


- Given `w` bits operands
 - True sum can have `w + 1` bits (carry bit). 
 - Carry bit is discarded. 
- Implementation:
 - s = (u + v) mod 2<sup>w</sup>



- Create a file named `unsigned_addition.c` with the following contents:

<script src="https://gist.github.com/linhbngo/d1e9336a82632c528ea797210ed0f553.js?file=unsigned_addition.c"></script>

- Compile and run `unsigned_addition.c`.
- Confirm that calculated values are correct. 



- Almost similar bit-level behavior as unsigned addition
  - True sum of `w`-bit operands will have `w+1`-bit, but
  - Carry bit is discarded. 
  - Remainding bits are treated as 2's complement integers. 
-  Overflow behavior is different
  - $TAdd_{w}(u, v) = u + v + 2^{w}$ if $u + v < TMin_{w}$ (**Negative Overflow**)
  - $TAdd_{w}(u, v) = u + v$ if $TMin_{w} \leq u + v \leq TMax_{w}$
  - $TAdd_{w}(u, v) = u + v - 2^{w}$ if $u + v TMax_{w}$ (**Positive Overflow**)



- Create a file named `signed_addition.c` with the following contents:

<script src="https://gist.github.com/linhbngo/d1e9336a82632c528ea797210ed0f553.js?file=signed_addition.c"></script>

- Compile and run `signed_addition.c`.
- Confirm that calculated values are correct. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
### 3.3. Negation


- Negate through complement and increment:
  - `~x + 1 == -x`



- Implement a C program called `negation.c` that implements and validates
the equation in slide 24. The program should take in a command line argument
that takes in a number of type `short` to be negated. 
- What happens if you try to negate `-32768`?

:::{dropdown} Solution
<script src="https://gist.github.com/linhbngo/d1e9336a82632c528ea797210ed0f553.js?file=negation.c"></script>
:::