More on this book
Community
Kindle Notes & Highlights
Read between
May 1 - May 5, 2018
combinatorics or combinatorial analysis.
What we’ve constructed here is a simple electrical circuit, and the first thing to notice is that a circuit is a circle. The lightbulb will be lit only if the path from the batteries to the wire to the bulb to the switch and back to the batteries is continuous. Any break in this circuit will cause the bulb to go out. The purpose of the switch is to control this process.
The meaning of a particular bit or collection of bits is always understood contextually. The meaning of a yellow ribbon around a particular oak tree is probably known only to the person who put it there and the person who’s supposed to see it. Change the color, the tree, or the date, and it’s just a meaningless scrap of cloth. Similarly, to get some useful information out of Siskel and Ebert’s hand gestures, at the very least we need to know what movie is under discussion.
The magazine Entertainment Weekly gives grades, not only for movies but for television shows, CDs, books, CD-ROMs, Web sites, and much else. The grades range from A+ straight down to F (although it seems that only Pauly Shore movies are worthy of that honor). If you count them, you see 13 possible grades. We would need 4 bits to represent these grades: 0000 = F 0001 = D– 0010 = D 0011 = D+ 0100 = C– 0101 = C 0110 = C+ 0111 = B– 1000 = B 1001 = B+ 1010 = A– 1011 = A 1100 = A+ We have three unused codes: 1101, 1110, and 1111, for a grand total of 16.
The left-hand guard pattern is followed by six groups of 7 bits each. Each of these is a code for a numeric digit 0 through 9, as I’ll demonstrate shortly. A 5-bit center guard pattern follows. The presence of this fixed pattern (always 01010) is a form of built-in error checking. If the computer scanner doesn’t find the center guard pattern where it’s supposed to be, it won’t acknowledge that it has interpreted the UPC. This center guard pattern is one of several precautions against a code that has been tampered with or badly printed.
The final digit (a 7 in this case) is called the modulo check character. This character enables yet another form of error checking. To examine how this works, let’s assign each of the first 11 digits (0 51000 01251 in our example) a letter:
Interesting breakdown of the UPC
That’s called the modulo check character. In the case of Campbell’s Chicken Noodle Soup, we have
Aristotle thought that logic had something to do with it. The collection of his teachings known as the Organon (which dates from the fourth century B.C.E.) is the earliest extensive writing on the subject of logic.
An Investigation of the Laws of Thought on Which Are Founded the Mathematical Theories of Logic and Probabilities (1854),
The Laws of Thought. Boole died in 1864 at the age of 49 after hurrying to class in the rain and contracting pneumonia.
The first rule is that addition and multiplication are commutative. That means we can switch around the symbols on each side of the operations:
By contrast, subtraction and division are not commutative. Addition and multiplication are also associative, that is
And finally, multiplication is said to be distributive over addition: A x (B + C) = (A x B) + (A x C)
In Boolean algebra (as Boole’s algebra was eventually called), the operands refer not to numbers but instead to classes. A class is simply a group of things, what in later times came to be known as a set.
The + symbol in Boolean algebra means a union of two classes. A union of two classes is everything in the first class combined with everything in the second class. For example, B + W represents the class of all cats that are either black or white.
The x symbol in Boolean algebra means an intersection of two classes. An intersection of two classes is everything that is in both the first class and the second class. For example, F x T represents the class of all cats that are both female and tan. As in conventional algebra, we can write F x T as F·T or simply FT (which is what Boole preferred). You can think of the two letters as two adjectives strung together: “female tan” cats.
W + (B x F) = (W + B) x (W + F)
This doesn’t make much sense in conventional algebra. Because F is the class of all female cats, and (1 – F) is the class of all cats that aren’t female, the union of these two classes is 1: F + (1 – F) = 1 and the intersection of the two classes is 0: F x (1 – F) = 0 Historically, this formulation represents an important concept in logic: It’s called the Law of Contradiction and indicates that something can’t be both itself and the opposite of itself. Where Boolean algebra really looks different from conventional algebra is in a statement like this:
Boole considered X2 = X
Another Boolean statement that looks funny in terms of conventional algebra is this: F + F = F The union of female cats and female cats is still the class of female cats.
Perhaps one day you walk into a pet shop and say to the salesperson, “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.” And the salesperson says to you, “So you want a cat from the class of cats represented by the following expression: (M x N x (W + T)) + (F x N x (1 – W)) + B Right?” And you say, “Yes! Exactly!”
You’re about to perform some experiments that will unite the algebra of George Boole with electrical circuitry and thus make possible the design and construction of computers that work with binary numbers. But don’t let that intimidate you.
Switches connected in this way—one right after the other—are said to be wired in series.
This circuit is performing a little exercise in logic. In effect, the lightbulb is answering the question “Are both switches closed?” We can summarize the workings of this circuit in the following table:
These switches are said to be connected in parallel. The difference between this and the preceding connection is that this lightbulb will light if you close the top switch:
up eight switches like so: Each switch in this circuit is labeled with a letter—the same letters as in the Boolean expression. ( means NOT W and is an alternative way to write 1 – W). Indeed, if you go through the wiring diagram from left to right starting at the top and moving from top to bottom, you’ll encounter the letters in the same order that they appear in the expression. Each x sign in the expression corresponds to a point in the circuit where two switches (or groups of switches) are connected in series. Each + sign in the expression corresponds to a place in the circuit where two
...more
computers. What might have helped Babbage, we know now, was the realization that perhaps instead of gears and levers to perform calculations, a computer might better be built out of
telegraph relays. Yes, telegraph relays.
logic gates
Logic gates perform simple tasks in logic by blocking or letting through the flow of electrical current.
Claude Elwood Shannon (born 1916), whose famous 1938 M.I.T. master’s thesis was entitled “A Symbolic Analysis of Relay and Switching Circuits.” (Ten years later, Shannon’s article “The Mathematical Theory of Communication” was the first publication that used the word bit to mean binary digit.)
In computer terminology, the switches are an input device. Input is information that controls how a circuit behaves.
These combinations of relays are called logic gates.
Relays have an advantage over switches in that relays can be switched on and off by other relays rather than by fingers.
In effect, the relay amplified a weak signal to create a strong signal.
In this case, the grounds simply represent a common connection; they don’t need to be connected to the physical earth:
Connecting relays is the key to building logic gates.
This circuit of four AND gates and two inverters is called a 2-Line-to-4-Line Decoder.
These two pairs of equivalent circuits represent an electrical implementation of De Morgan’s Laws.
De Morgan’s Laws are an important tool for simplifying Boolean expressions and hence, for simplifying circuits.
When you come right down to it, addition is just about the only thing that computers do.
the result of adding a pair of binary numbers is 2 bits, which are called the sum bit and the carry bit (as in “1 plus 1 equals 0, carry the 1”).
It’s convenient to look at binary addition in this way because our adding machine will do sums and carries separately.
The rest of the adding machine will consist of logic gates wired together in various ways.
It’s called the Exclusive OR gate or, more briefly, the XOR gate. It’s called the Exclusive OR gate because the output is 1 if the A input is 1 or the B input is 1, but not both.
That’s the trouble with bits: They’re just zeros and ones and don’t tell you anything about themselves.
Well, the output quickly alternates between providing a voltage and not providing a voltage. Or, we can say, the output quickly alternates between 0 and 1. This circuit is called an oscillator.
All computers have some kind of oscillator that makes everything else move in synchronicity. The output of the oscillator alternates between 0 and 1. A common way to symbolize that fact is with a diagram that looks like this:
the output of the oscillator alternates between 0 and 1 on a regular basis. For that reason, an oscillator is sometimes often referred to as a clock because by counting the number of oscillations you can tell time
A cycle of an oscillator is defined as the interval during which the output of the oscillator changes and then comes back again to where it started:
