pbaumgarten.com

Unit 3: Data and logic

This unit aligns to the syllabus and textbook as follows:

Introductory activity

Build your own logic gates

What is data?

Ultimately everything in a computer is reduced to either the presence or absence of an electrical charge. This electrical charge inside transistors is scaled up to form basic circuits that can be used to remember information (ie: act as memory) and perform calculations.

At the heart of it all is the transistor which is a simple electrical switch that can be turned on or off via an electrical signal. A modern Intel CPU has about 1.75 billion transistors in a piece of silicon the size of a fingernail, or 17.185 million transistors per square millimetre. (1)

The logic gates

We mentioned before that at the most simple level, everything inside a microprocessor is reduced to transistors. But what exactly is a transistor? how does it function? How can such a simple device create the seeming complexity of modern computers?

A transistor is a switch that controls another switch. For a great introduction to how transistors can be combined to create interesting functionality, watch this brief video…

This video introduced you to logic gates. This is the level of complexity from the transistor. We use multiple transistors to build logic gates. Multiple logic gates can then be used in clever patterns to create memory and perform calculations. Once we have the ability to store values in memory, and to be able to perform calculations on those values, we then have the basic building blocks of every computer.

There are 6 logic gates we will study in this course.

These gates are effectively switches, where the state of the output (whether it is on or off) is determined by the combination of the inputs and the rule of the gate.

We will use combinations of these logic gates to create logic circuits. To enable us to do this easily each gate has a symbol by which it can be represented in a diagram, and there is also a couple of notations available to represent them in the form of written equations.

The logic gate symbols are shown below and are also in page 26 of your text (the XNOR gate is not part of your course but it should be an intuitive extension to determine what it is…?)

As you can also see, we can simplify our understanding of rules for each gate by using a table, known as a truth table, to document the circumstances in which a gate is on or off. Rather than using the “on” and “off” terminology, we use binary where 0 represents off and 1 represents on.


Exercise: NandGame

http://nandgame.com/

This website allows you to build a virtual computer beginning from just a NAND gate.

Complete the first 6 levels:


Produce truth tables

Logic gates are combined together to form logic circuits. To gain an understanding of what an individual circuit may do, we create truth tables for them as well.


Produce circuits from equations

Any logic circuit can be expressed as a diagram or as an equation. You need to be able to convert one to the other.

One small but crucial detail to ask before we go any further is order of precedence. Intuitively from maths we may understand that backets are resolved first, but what about other situations? For instance given X = NOT A AND B… is it (NOT A) AND B…. or is it NOT (A AND B)… ?

So with that in mind, you should know that the order of precedencee is 1st parenthesis, 2nd NOT, 3rd AND, 4th OR.

Let’s do some questions…

Check your answers at http://sandbox.mc.edu/~bennet/cs110/boolalg/truthtab.html

We will now look at creating the diagrams from an equation.

Check your answers at http://sandbox.mc.edu/~bennet/cs110/boolalg/gate.html

You may be presented with a written scenario from which you need to discern the equation and logic circuit.


Bits and bytes

This presence of absence of electricity needs to be simplified for computer scientists to effectively scale it to the complexity of modern computers. For this reason we think of it as True and False which is then further simplified into 1 and 0.

This most simple form of data, that is a 1 or 0 is known as a bit.

Again, dealing with thousands of bits at a time isn’t practical, so we scale again. The first level of complexity introduced is to group 8 bits together into a byte.

If a bit has two possible values, 0 and 1, and a byte consists of 8 bits, how many possible values does a byte have?

The answer, of course, is 256. But did you get there the easy way or the hard way? How long until you worked out the pattern?

Number of bits All possible values Total possiblities Also known as
1 0, 1 2 2^1
2 00, 01, 10, 11 4 2^2
3 000, 001, 010, 011, 100, 101, 110, 111 8 2^3
4 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 16 2^4

Counting in binary

Binary sizes

Memory size Number of bits Equivilent denary value
Kilobyte 2^10 1,024
Megabyte 2^20 1,048,576
Gigabyte 2^30 1,073,741,824
Terabyte 2^40 1,099,511,627,776
Petabyte 2^50 1,125,899,906,842,624

Uses of binary numbers

The integer

for n in range(256):
    b = bin(n)
    print(f" Decimal { n :3}, in binary is { b :>10}")

Floating point numbers

How are floating point numbers stored internally? By storing two integers, one representing the significant figures, the other representing the exponent for the number. In this way we can store very large and very small numbers but with a limited degree of accuracy.

In the same way that we might think of the the speed of light in decimal notation as being represented by the number 3 and 8…. to represent 3 x 10^8, floating point numbers use the same approach.

The 64 bit floating point number uses 1 bit for the sign (positive/negative), 8 bits for the exponent, and 55 bits for the significant number.

Everything is stored in binary rather than decimal. This means the first bit represents 1/2, the second bit represnts 1/4, the third will represent 1/8 and so forth. This poses some challenges for seemingly common numbers.

For instance, look at the following output from Python

>>> 0.3
0.3
>>> 0.1
0.1
>>> 0.1 + 0.1 + 0.1
0.30000000000000004
>>> 

The number 0.1 in binary is actually an infinitely recurring decimal, so when we add several together we are getting a rounding effect occurring. This is analogus to adding 0.3333333 (recurring) several times.

So it is important to remember that floating point numbers are great, but they are not designed for highlevel precision after multiple mathematical operations. They were designed for scientific applications, not financial.

Registers

16, 32, 64 bit computing


Converting between denary and binary

Binary - How to Make a Computer: Part II (7:15) https://www.youtube.com/watch?v=NRKORzi5tnM

TO

Hexadecimal numbers

Reasoning for hex notation

for n in range(256):
    b = bin(n)
    h = hex(n)
    print(f" Decimal { n :3}, in binary { b :>10}, in hex { h :>4}")

Convert hex and denary

Convert hex and binary


Common uses of hex in computing

HTML colours

MAC addresses

import uuid
print( hex(uuid.getnode()) )

Assembly languages

Debugging


References

  1. https://www.quora.com/How-many-transistors-are-in-i3-i5-and-i7-processors
  2. https://www.includehelp.com/python/binary-numbers-representation.aspx
  3. https://pythonspot.com/binary-numbers-and-logical-operators/