This course is about information. Although you may have a general notion of what information is, and may have dealt with both precise and imprecise information, you may not have realized that the information you deal with can be quantified. You can measure the amount of information in a variety of situations and state general principles about how information behaves in the real world.
To define something as information is subjective. In this course, we define information to be both information you don't have and information you do have. Let's take, for example, a quarter. If I flip the quarter and only allow myself to see whether it's heads or tails, I have information whereas you don't. But if I allow you to see the result of the flip, you now have information. The information is there, whether you have it or not.
Information can be communicated, stored, moved from place to place, and most importantly used. What is the unit of information? It is the bit. A bit is a selection from a set of 2 possibilites, such as True or False, Boy or Girl, Heads or Tails, 0 or 1, High or Low, On or Off. All these are representations of a bit having two states.
In computers, the bit is represented as High voltage or Low voltage. Defining which voltages represent 0 or 1 is up to the designer. We will assign the High voltage to be 1 and the Low voltage to be 0. In most integrated circuits, like the CPU of a computer, bits are processed using transistors called MOSFETs (Metal-Oxide Silicon Field Effect Transistors). Below is a cross section of a MOSFET. <Picture of cross section of MOSFET>
The MOSFET is comprised of several key parts. The top part is known as the gate. When a positive voltage is applied to the gate, electrons (which are negative in voltage) are attracted to the gate but cannot come into contact because of an oxide insulated layer. However, the source and drains on both sides of the gate now have a pathway of electrons where current can flow through. What we have here is a voltage controlled switch. From this, we can build logic gates, mathematical operations applied onto a group of bits. <Picture of schematic of a MOSFET inverter>
Above is a schematic representation of a MOSFET attached to a high voltage source on the top and a low voltage source (ground) on the bottom. When low voltage is applied to the gate, there is current flow from the high voltage to the output. When high voltage is applied to the gate, there is now a connection from the ground to the output (the resistor drops the high voltage down). What we have here is an inverter; input a high voltage and we get a low voltage, input a low voltage and a high voltage is outputted. Below is a graph of the input voltage versus the output voltage. <Picture of inverter input/output voltage graph>
If we attach another inverter to the output, we get what is known as a buffer. What we input to the whole thing, we get back. This may seem useless, but look at the voltage graph below. <Picture of buffer input/output voltage graph>
What we have here is some noise immunity. If the buffer is given an input voltage that isn't a well defined low or high voltage, the buffer will be forgiving and will choose the closest value. However, transistors are not confined to just inverters and buffers; they allow for interesting manipulations such as the following, a NAND (NOT AND) gate and a NOR (NOT OR) gate. <Picture of a NAND gate using MOSFETs followed by a schematic representation of a NAND gate>
By examining the inputs and determining the related outputs, we can construct truth tables:
| NAND | NOR | |||||
|---|---|---|---|---|---|---|
| A | B | O | A | B | O | |
| 0 | 0 | 1 | 0 | 0 | 1 | |
| 0 | 1 | 1 | 0 | 1 | 0 | |
| 1 | 0 | 1 | 1 | 0 | 0 | |
| 1 | 1 | 0 | 1 | 1 | 0 | |
These gates are functions in a field of mathematics called boolean algebra. It's similar to regular algebra except that its variables holds just true or false values. There are a total of 16 possible functions on two inputs (2^4) in boolean algebra. Take for example, the AND, and the XOR (Exclusive OR). AND XOR A B | O A B | O -------+-------- -------+-------- 0 0 | 0 0 0 | 0 0 1 | 0 0 1 | 1 1 0 | 0 1 0 | 1 1 1 | 1 1 1 | 0
Notice that the XOR can be represented as combinations of the other boolean functions. A XOR B = (A OR B) AND NOT(A AND B) _________ A XOR B = (A OR B) AND (A AND B)
You may find in many textbooks that NOT is denoted by an upperbar on top of the quantity being negated. There are also special properties in some of the 2 input boolean functions. The NAND gate is a universal boolean function where other boolean functions can be created using just NAND gates. Another is reversibility (or invertibility) where given the output and one of the inputs, the other input can be restored. The distributed and commutative properties also still apply to certain functions. A AND B = B AND A A OR (B OR C) = (A OR B) OR C
From boolean algebra also comes identities with the most famous one being DeMorgan's Theorem which can be easily proved using truth tables going through all possible inputs. ________ _ _ (A OR B) = A AND B _________ _ _ (A AND B) = A OR B
So far, we have only discussed 2 input boolean functions. From that comes 4 possible states of 2 bits: 00, 01, 10, and 11. As we will see in the future, information can be represented as the log2 of the total number of states possible.