comp_arch.org

Code: The Hidden Language of Computer Hardware and Software

Charles Petzold

Chapter 1-10 - Basics

Morse code

2 best friends can communicate using torches, via the morse code. Morse code contains 2 “signals” (or 2 states) - short blink and a long blink. It is a variable length code, with the common characters having smaller codes, eg E is just a small blink.

We can expand the above table into a parse tree so that it is easier to read and understand.

Braille Code

It is a 6bit code.

So, 2⁶ is 64 unique codes. There are many contractions as well in Braille, eg: “you and me” is written as:

There are some codes that alter the meanings of the codes that follow them - from letters to numbers and vice versa until the shift is undone. They are called shift codes In contrast, the escape codes are the ones that change the meaning of only the next following character and not beyond that.

Seeing around corners

If the houses aren’t adjacent, we can use bulbs, with this setting:

Here, we can reduce the wire length if we use a common:

This is a bidirectional telegraph system

Now, there is some more optimization to be had, the Earth! It is a good conductor due to the virtue of it’s size

Recall, “` R = ρ l ~~~ A

“` So, we can use the Earth to conduct our electrons. So, from:

You can get:

Which can be further simplified to:

The ground is 0 potential, so 0V. Hence, we get this model now:

This is not much different from a telegraph,

Or, simpler:

Note, the V represents a battery connected to the ground on the other side. So, it’s just a source of power

So, when the key is pressed, due to the voltage, the iron is magnetized and it clanks against the iron top.

To carry longer distances, you would need a relay system.

The relay has it’s own power source so it strengthens the signal and sends it onward.

UPC - Universal Product Code

It is a binary code with 30 black bars (of 4 different widths) which are divided by gaps of various widths. Eg:

The computer sees a narrow strip as a series of bits

So, the entire series is simply 95bits. The first 3 bits are always 101 - left hand guard pattern - this is for orientation

This is followed by 6groups of 7 bits each (so, 42 bits in total) - each group is a digit from 0-9 Then comes a 5bit center guard pattern - always 0101010101 Then comes another 6groups of 7bits each Finally, a right hand guard pattern - 101

So, we have 12 numeric digits in total encoded as 95 bits. Now, the left side codes use 7bits for each digit. They don’t use the traditional unsigned representation for digits, but a special encoding:

0001101	0
0011001	1

Etc. It always starts with 0 and ends with a 1. It Always has odd number of 0s - odd parity for 0 bit

“A group of bits has even parity if it has an even number of 1 bits and odd parity if it has an odd number of 1 bits”

The RHS is the exact opposite of it, and has even parity for 1 bit.

1110010	0
1100110	1

Logic and switches

Commutative

Addition and multiplication is commutative: → A + B = B + A → A ∗ B = B ∗ A

Associative

Addition and multiplication is associative: → A + (B + C) = (A + B) + C → A * (B * C) = (A * B) * C

Distributive

Addition and multiplication is distributive: → A * (B + C) = (A * B) + (A * C)

George Bool invented a new algebra that didn’t refer to numbers along, but rather classes Eg: F can be used to refer to a class of female cats.

→ + or ∪ symbol means union of 2 classes → * or ∩ means intersection of 2 classes ( FxT, or F.T or FT)

Apart from all the above rules, in Boolean Algebra, + operator is distributive over x operator so: → W + (B x F) = (W + B) x (W + F) Also, BA has: → X + X = X → X² = X

We can use BA to solve Socrates’ immortality problem

1. All persons are mortal
2. Socrates is a person
3. Hence, Socrates is mortal

Let’s see:

• P = class of all persons
• S = class of Socrates
• M = class of mortals

We have from 1 and 2

• P X M = P
• S X P = S

Thus

• S X (P X M) = S
• (S X P) X M = S
• S X M = S

hence, proved 3 is logically true.

We can use BA to model some logical equations. Say we want “I want a male cat, neutered, either white or tan; or a female cat, neutered, any color but white; or I’ll take any cat you have as long as it’s black.” So, the equation for this will be: (M x N x (W + T)) + (F x N x (1 – W)) + B

We can also look at * as an /AND/ We can also look at + as an /OR/

And we can use circuits to model the AND/OR

AND:

OR:

And so, our earlier equation can be modeled as:

We had: (M x N x (W + T)) + (F x N x (1 – W)) + B This equation has 6 variables - M, N, W, T, F, B Currently we have 8, we can reduct it to 7 with - (N x ((M x (W + T)) + (F x (1 – W)))) + B

But we should need only 4 switches (bits) to encode all the possible cases.

• 1 for F/M
• 1 for N/U
• 2 for B, T, W, O

Like switches, relays can be connected in a series and in parallel to perform simple tasks in logic. These combinations of relays are called logic gates (later transistors were used and not relays) Recall our relay:

Or simply,

So, we can connect relays like so (note, this is not any logic gate, just a normal connection)

Another way to connect the relay is:

This is called double throw relay The relay is on by default and when we pass the V via the input, the circuit is broken So, the relay’s output is the opposite of what you give it:

This can be used to model out signals:

So, we have an AND gate as - 2 normal relays connected in series:

This is the AND gate represented as:

Next is OR gate - 2 normal relays connected in parallel

Written as:

We can now model our simplified equation (N x ((M x (W + T)) + (F x (1 – W)))) + B as:

• If you connect 2 double throw relays in series, you get NOR - both have to be 0 to get 1

• If you connect 2 double throw relays in parallel, you get NAND - if both 1 you get 0

So, we have:

• AND
  • 2 normal relays in series
• OR
  • 2 normal relays in parallel
• NAND
  • 2 double throw relays in parallel
• NOR
  • 2 double throw relays in series
• NOT
  • 1 double throw relay - inverts output
• BUFFER
  • 1 normal relay - strengths same output

Demorgan’s laws

They help us to move from OR to AND and vice-versa this allowing us to simplifying Bool’s equations (and circuits)

Adding machine

Addition in bits can be represented as:

sum bit:

This is exactly an XOR - exclusive or We can model it with 1 AND, 1 NAND, 1 OR

Shorthand:

Carry bit:

This is exactly an AND

Hence, a single bit addition can be represented as:

This can be encapsulated in a package:

Hence, in this HA, we can put in 2 bits and the sum comes out the other hand

If we want to do a division that can have a carry bit to it, we need something more than a single HA

We have: A + B + carry_in We do A+B normally. We park the carry bit and add the sum bit to the carry_in From this, the sum bit is the sum bit of the total addition and the carry bit from this is added to the parked carry bit.

Thus, we get a full adder:

We can now wire up the lightbulbs on our control panel like so:

Note, 🔝 this is for the first added. Consecutively, we have an input for the carry in and the carry out will go to the CI of the next FA in the bank

It looks like so: ⬇️

This is a 8bit adder. It takes in two 8bit numbers and gives an 9bit result.

The bits A₀, B₀, S₀ are the least significant bits. A₇, B₇, S₇ are the most significant bits

We can daisy chain the 8bit HAs as well:

Here, we have the ability to add 16bit numbers. Right now, the CI bit from the last FA is needed for the next computation. This is called ripple carry. Faster adders can use look-ahead carry which makes this faster

This 8bit adder needs 144 relays. Here’s how:

• each FA needs:
  • 2 HAs and an OR gate
    • each HA needs 1 AND and 1 XOR
      • each XOR needs 1 AND, 1 NAND, 1 OR
        • each AND, NAND, OR needs 2 relays each
      • so, each HA needs 2 + 6 = 8 relays
  • each FA needs 18 relays
• 8 FAs need → 18*8 = 144 relays

We can replace the first FA with a HA and we can reduce this to: 134 relays

Subtraction

A - B is just addition of A and -B If we represent number using 2s complement, we need to convert the negative number to it’s 2s complement and do the addition.

Conversion from unsigned to 2s complement

Since we have 8 bits, we can represent 255/2 = -128 to 127. For the positive bits, it is the same as in unsigned. But for negative numbers, steps:

• write the binary representation of the number in unsigned binary
• invert the bits and add 1
• the result is the 2s complement representation of that number

why does this work 🔝 what we want to do to get -A from A is, subtract A from 0 or 0 - A when we invert bits of A, it is logically equivalent to 11111..11 - A and then when we add 1, we what we end up is same as 1000..00 - A (1 followed by “A” number of 0s, or 2ⁿ in unsigned binary) since we take the least significant |A| bits, we end up with the same computation as 0-A

So, we have: 253 - 176

• 11111101 (unsigned for 253), 10110000 (unsigned for 176)

-176 → 01001111 + 1 = 01010000 Now, 01010000 + 11111101 = 0101001101 which is 77 (ignoring overflow, we get 1001101, the 9th bit is 1 here note)

We can add subtraction to our machine: We need to invert bits and add a carry bit to one to do so (this will give us the 2s complement)

We can put this in a box - One’s complement and get this circuit:

Note here, when SUB signal is 1, we add the carry in bit to 1, invert our B input bits, so we get 2s complement of B And also, we signal the overflow/underflow. That bulb will light up if SUB is 0 and other bit is 1 - so our sum was greater than 255 Or, SUB is 1 and the other bit is 0 (WHY ?? :/)- so our result was negative - our machine can’t represent negative numbers.

The 2s complement

It is amazing because it allows us to perform seamless addition and subtraction given we do not have overflow/underflow

So, we have 2 ways to encode integers in binary numbers: 10110110 can be either 182 in unsigned or it can be -74 in 2s complement

Feedback and Flipflops

Consider our old relay wired like so:

This relay is an oscillator. I.E. The output of a NOT gate is also the input

What is the speed of this oscillator? We’ll have to find out. Consider this circuit:

Originally, the current is flowing in the red marked wire only. Pressing the lower switch has no effect because the NOR gate is 0 even if there is a single 1, and 1 only when both inputs are 0s.

However, if we press the top switch, we get this:

Now, pressing the top switch has no effect. We can get back to the original state only by pressing the 2nd switch.

Thus, the circuit is able to remember the last switch that was pressed in some sense. The circuit has 2 stable states, when both the switches are off - the bulb is on/off

A more common representation is:

• when R is on(and S is off), Qbar is 1, Q is 0
• when S is on(and R is off), Q is 1, Qbar is 0

The function table Is so:

Here, S/R 0/0 entry says Q/Qbar - this means that they remain what they were before S/R got to 0/0 S/R 1/1 is not allowed as it won’t give predictable state if both are 1/1

The R-S flip-flop is an example of a circuit that remembers which of it’s 2 inputs was a 1

We can add a little circuitry around the RS flip flop for “Hold that bit”

Here, when the HTB is 1, and S is 1, Q becomes 1 and Qbar becomes 0. Later, when HTB is 0 and S/R are anything, it makes no difference as S/R get only 0/0

When HTB is 1 and R is 1, Qbar is 1 and Q is 0 But we only want 1 input; we can get this by:

Now, when HTB is 1, the data signal’s value is saved at Q. This is called a level-triggered D type flip flop D is for data, level-triggered is means that the FF saves the value of the Data input when HTB is at a particular level (1 here)

Generally, HTB is called a Clock The circuit is also called a level triggered D type latch - it stores 1 bit of memory Logic table:

Clock	Data	Q	Qbar
1	1	1	0
1	0	0	1
0	X	Q	Qbar

We can chain these latches to store bits. If we want to add 3 bit numbers say, we can add the result of 2 numbers to a latch like this and add a third number to it

We can chain 8 latches to get 8bit memory:

When the clock signal is 1, the 8bits of D_0-7 are saved in Q_0-7 and they remain the same while Clk remains 0 Smaller representation:

We can use it in our earlier computer to get a new architecture:

This gives us the ability to add a series numbers. Note the new piece → “2-to-1 Selector” It takes in an input and select 1 of the 2 possible inputs as the one that is selected and sent forward.

2^N-to-N selector - it actually has 2^N inputs and N inputs that help us select which one to send forth

The 2-1 selector has a simple design,

Select	A	B	Out
1	X	B	B
0	A	X	A

When Select is 1, Out is whatever is B When Select is 0, Out is whatever is A

2-1 Selector has 8 of these with the same Select for all

Currently, the CO signal is left out in the next series of calculations - we will see later how to solve this problem

We can also modify our latch to add a clear signal that would just set Q to 0

This will allow us to phase out the 2-1 selector and get this:

Earlier, our flip flop was level-triggered, that is the clock input must change it’s level from 0-1 for the Data to be saved An alternative is “edge triggered flip flop” - this means the data is saved only when the clock makes a transition from 0 to 1

This means, the data is saved at the instant the clock triggers 1, and not while it is 1 like earlier. How do we accomplish this? An “edge triggered D type flip flop” looks like this ⬇️

We have 2 stages of R-S flip flops. The forward stage is exactly like earlier, and the backward stage has a NOT clock signal controlling it, so when the clock is 0, the data is saved. However, when clock is 0, the forward stage has no effect. Hence, when the clock changes from 0 to 1, the behind stage is saved in the forward stage and never otherwise. Pretty cool, eh?

The logic table:

D	Clk	Q	Qbar
0	↑	0	1
1	↑	1	0
X	o	Q	Qbar

The ↑ means clock transitions from 0 to 1 The flip flop can be represented as:

The angle bracket on Clk indicates that it is edge triggered

Consider this now:

The logic table:

• Clk is 0, Q is 0 (say to start with), Qbar is 1, D is 1
• Clk goes to 1, D is 1, so Q is 1, Qbar is 0, D is 0
• Clk goes to 0, everything still same - Q is 1
• Clk goes to 1, D is 0, so Q is 0, Qbar is 1, D is 1

Hence, we can plot this:

Note there is a change in D/Qbar/Q when Clk makes the transition from 0 to 1 The frequency of D/Qbar or even Q is half the frequency of Clk - this is know as a frequency divider

We can go ahead an repeat this process:

This will give us:

Note here, we are looking at ClkBar so, the Qs appear to change at negative transition (1 → 0), but they are still the same

Now, if we look at the bits represented by the Q (Clk, Q1, Q2, Q3) signals at any timeslice, we get the bits counting from 0000 to 1111

At each positive transition, the outputs of the counter increase by 1 We can put this in a box and we get this:

This is called a ripple counter because the output of 1 FF is the input of another.

The Qs will go from all 0s to all 1s The time it takes, say 10 secs gives means that the Clk had to move 256 cycles to get all 1s, so freq = 25.6 Hz

We can also add a Preset to the flipflop

There is a lot of rearrangement from the earlier scheme, but it’s just rearrangement. When the Preset is 1, Q becomes 1, when the clear is 1, Q becomes 0. Both Preset and Clear shouldn’t be 1 at the same time. When both are 0, the FF behaves like before This 🔝 is an “edge-triggered D-type flip flop with preset and clear”.

This FF can be packaged like so: