Understanding Codes in Computing
Understanding Codes in Computing
C O D E
SECOND EDITION
CHARLESPETZOLD
MULTIMEDIA
Table of contents
PREFACE TO THE SECOND EDITION IX 15. IS THIS REAL? 183
The complementary website
Responsible people BUT WHAT ABOUT SUBTRACTION? 197
And finally
Anaya's commitment to diversity, equality, and inclusion
17. FEEDBACK AND BISTABLES 213
BEST FRIENDS 1
18. LET'S MAKE A CLOCK! 241
2. CODES AND COMBINATIONS 7
19. A MEMORY ASSEMBLY 267
3. BRAILLE AND BINARY CODES 13
20. AUTOMATE ARITHMETIC 289
4. ANATOMY OF A FLASHLIGHT 21
21. THE ARITHMETIC-LOGIC UNIT 315
5. COMMUNICATION AROUND THE CORNER 31
22. REGISTERS AND BUSES 335
6. LOGIC WITH SWITCHES 41
23. CONTROL SIGNALS OF THE CPU 355
7. TELEGRAPHS AND RELAYS 57
24. LOOPS, JUMPS, AND CALLS 379
8. RELAYS AND DOORS 65
25. PERIPHERALS 403
9. OUR TEN DIGITS 91
26. THE OPERATING SYSTEM 413
10. ALTERNATIVE TENS 99
27. CODE 425
11. BIT A BIT A BIT 117
28. THE WORLD BRAIN 447
12. BYTES AND HEXADECIMAL 139
ÍNDICE ALFABÉTICO 460
13. FROM ASCII TO UNICODE 149
T
He is 10 years old. His best friend lives across the street. In fact, their windows are facing each other.
one facing the other. Every night, when their parents have sent them to bed to one
too early, they still need to exchange thoughts, observations,
secrets, gossip, jokes, and dreams. No one can blame them. After all, the impulse to
Communicating is one of the most human traits.
While the lights in your bedrooms remain on, you and your best friend can
greet each other with a hand from the window, using wide gestures and body language
rudimentary, to convey a thought or two. But the more sophisticated exchanges seem
difficulties, once your parents have said 'turn off the light!', quieter solutions are needed.
How to communicate? If you are lucky enough to have a mobile phone at 10 years old, maybe
a secret call or a silent message works, but what if your parents have the
habit of confiscating phones at bedtime or even taking away Wi-Fi? A bedroom
Without electronic communication, it is a very isolated room.
What you and your best friend do have, however, are flashlights. Everyone knows.
that lanterns were invented to allow children to read books under the blankets; the lanterns
they also seem perfect for the task of communicating in the dark. Of course, they are the
quite silent and the light can be directed well, so it is unlikely that they are suspicious
parents see it from under the door.
Can we make flashlights talk? It's worth a try. They learned to write.
letters and words on paper in elementary school, so transferring that knowledge to the flashlight seems
razonable. Lo único que tienen que hacer es ponerse delante de la ventana y dibujar las letras con
light. For an O, they turn on the flashlight, draw a circle in the air and turn it off. For an I, they draw
a vertical line. But they soon discover that this method is a disaster. While looking at the
your friend's flashlight making turns and lines in the air, realizes that it is too difficult
Unite the multiple strokes in your head. These turns and bars of light are not precise enough.
Perhaps once he saw a movie in which a couple of sailors signaled to each other through Although Morse code has nothing to do with computers, becoming familiar with the natu-
of the sea with blinking lights. In another movie, a spy moved a mirror to reflect the light The analysis of codes is an essential preliminary step to achieve a deep understanding.
of the sun in a room where there was another captive spy. Perhaps that is the solution, so of hidden languages and the internal structures of the hardware and software of a computer.
first, they design a simple technique. Each letter of the alphabet corresponds to a series of In this book, the word 'code' usually means a system for transferring information between
flashes of the flashlight. An A is 1 flash, a B is 2 flashes, a C is 3, and so on until people, between people and computers or within the computers themselves.
the 26 blinks of the Z. The word BAD has 2 blinks, 1 blink, and 4 blinks with
A code allows us to communicate. Sometimes, the codes are secret, but most
small pauses between the letters so they don't get confused with the 7 blinks of a G. It
they are not. In fact, most of the codes should be well understood because they are the basis of
take a slightly longer pause between words.
human communication.
This looks promising. The good news is that they no longer have to wave the flashlight in the
The sounds we make with our mouths to form words constitute a code that is
air; you just have to aim and ignite. The bad thing is that one of the first messages that tries to
intelligible to anyone who can hear our voices and understand the language we speak.
Sending to see how your friend is doing ('How are you?') requires a total of 131 blinks!
We call this code 'spoken word' or 'oral speech'.
In addition, they have forgotten about the punctuation, so you don't know how many blinks correspond.
to the question mark. Within the communities of deaf people, there are several sign languages that they use.
the hands and arms to form movements and gestures that represent individual letters of
But they are close. They think that surely someone must have had to face this.
words or complete words and concepts. The two most common systems in North America
problem before, and they are completely right. With a walk to the library or a search in
is American Sign Language (ASL), which was developed in the early 19th century in America
Internet, they discover a wonderful invention known as Morse code. It is just what
School for the Deaf, and the Quebec Sign Language (LSQ), which is a variation of the language
they were looking for, even if now they have to relearn how to 'write' all the
of French signs.
letters of the alphabet.
We use another code for words on paper or other media, called 'written word'
Here is the difference: in the system invented by you, each letter of the alphabet is a
the 'text'. The text can be written or typed by hand, then printed in newspapers.
a determined number of blinks, from 1 blink for A to 26 blinks for Z.
magazines and books, or to be displayed digitally on various types of devices. In many
In Morse code, there are two types of blinks: short and long. Of course, this makes the
languages, there is a strong correspondence between oral speech and text. In English, for
Morse code is more complicated, but, in real use, it turns out to be much more efficient.
For example, the letters and groups of letters correspond (more or less) to spoken sounds.
The phrase 'How are you?' only requires 32 blinks (some short and some long) instead of 131, and
that includes a code for the question mark. For people with a visual impairment, written words can be replaced by Braille,
that uses a system of raised dots that correspond to letters, groups of letters, or
When describing how Morse code works, people don't talk about 'blinks.'
complete words (we will talk about Braille in more detail in chapter 3).
shorts and long blinks, but of dots and dashes, because it is a convenient way
to display the codes on printed pages. In Morse code, each letter of the alphabet is When spoken words need to be transcribed to text very quickly, shorthand
corresponds to a short series of dots and dashes, as you can see in the following table. stenography is useful. In courts or to generate closed captions for news or
sports broadcasts on television, stenographers use a stenotype with a keyboard
simplified that incorporates its own codes that correspond to text.
We use a variety of different codes to communicate with each other because
some codes are more convenient than others. The code of spoken word cannot
stored on paper, so the code of the written word is used. Exchange information
in silence across a certain distance in the dark is not possible with oral speech or in
paper. Therefore, Morse code is a convenient alternative. A code is useful if it serves to
a purpose that no other code can serve.
As we will see, various types of codes are also used in computers to store
and communicate text, numbers, sounds, music, photographs, and videos, in addition to the instructions
inside the computer itself. Computers cannot easily handle human codes.
2 CHAPTER 1 BESTFRIENDS 3
Once you have a working flashlight, you can connect another long-distance one to
that your friend can send you messages.
On The house
house of his friend
From now on, the circuits will be shown in a more symbolic rather than realistic way. Although On The house
I am going to show only one stack, I could actually be using two. In this and in future diagrams, house of his friend
this will be a switch off (or open):
Congratulations! They have just set up a bidirectional telegraph system. You will notice that
it is about two identical circuits that are completely independent of each other. In theory, it may be
sending a message to your friend while your friend is sending you a message, even though
it could be difficult for your brain to read and send messages at the same time.
And this will be the switch when it is on (or closed): They may also be smart enough to realize that they don't need so many.
cables that cover the distance between the two houses. They can eliminate one of the four cables if
they configure the connection this way:
The flashlight in this chapter works in the same way as the one illustrated in the chapter
front, except that the wires connecting the components are now a bit longer.
When you turn off the switch in your house, the light turns on in your friend's house.
On The house
house of your friend
In this book, the cables that connect to each other are represented by a dot.
connection. This diagram has two connections like this, one under the stack in your house and another below
the light bulb in your friend's house.
On The house
house of your friend Note that the negative terminals of the two batteries are now connected. The two
circular circuits (battery to switch to bulb to battery) still operate independently,
Now messages can be sent using Morse code. even though they are united now.
This type of connection between the two circuits is called common. In this circuit, the common
extends between the two connection points of the cables, from the point where the bulb
and the battery on the far left connects up to the point where the bulb and the battery on the
they connect to the right.
32CHAPTER 5 COMMUNICATIONAROUNDTHECORNER33
La I es un uno. Esto podía derivar de una raya vertical o de un solo dedo levantado. LaV, The complete structure of Indo-Arabic numbers is revealed in the way that the
which is possibly a symbol to represent a hand, it is a five. Two Vs form an X. We pronounce. Let’s take 4,825 as an example. We say "four thousand eight hundred twenty-five".
What does ten represent. L is fifty. The letter C comes from the word centum, which is one hundred in That means:
Latin. The D is five hundred. Finally, the M comes from the word latinamille, which is a thousand. With a thousand
four thousand
steps from left to right, it will cover approximately a mile.
eight hundred
Although we may not agree, for a long time it was considered that the
two dozens and
Roman numerals were easy to add and subtract, and that's why they survived for so long in Europe.
five
for accounting. In fact, to add two Roman numbers, you just need to combine all
the symbols of both numbers and then simplify the result using a few rules: Or we can write the components like this:
Five I make a V, two V make an X, five X make an L, etc.
4.825 = 4.000 + 800 + 20 + 5
But multiplying and dividing Roman numbers is difficult. Many other numerical systems
primitives (like those of the ancient Greeks) were also not suitable for working with numbers Oh, to break it down even further, we can write the number this way:
in a sophisticated way. The Greeks developed an extraordinary geometry that still
4.825 = 4 × 1.000 +
It is taught in current institutes with hardly any changes, but they are not known for their algebra.
8 × 100 +
The numerical system we use today is known as Indo-Arabic. It is of Indian origin. 2 × 10 +
but it was the Arab mathematicians who brought them to Europe. It is especially known 5×1
the Persian mathematician Muhammed ibn Musa al-Khwarizmi (from whose name the word derives
Oh, using powers of ten, the number can be written like this:
algorithm), who wrote a book on algebra around the year 820 AD that used the system
Hindu for counting. There is a Latin translation dating from around 1145 A.D., and that 4.825 = 4 × 103+
had a great influence to accelerate the transition throughout Europe from Roman numerals to 8 × 102+
our current Indo-Arabic system. 2 × 101+
Indo-Arabic numbers differ from previous numerical systems in three ways 5 × 100
ways:
Remember that any number raised to 0 is equal to 1.
■ It is said that the Indo-Arabic number system is positional, meaning that a Each position in a multi-digit number has a particular meaning. The seven
A concrete digit represents a different quantity depending on where it is located. The boxes shown here allow us to represent any number from 0 to 9,999,999.
in the number. Where a digit appears is actually much more significant than
the digits themselves! Both 100 and 1,000,000 have a single 1, but we all know that
A million is much greater than a hundred.
Number of units
■ Almost all primitive numerical systems have something that the Indo-Arabic system does.
Number of tens
it does not have, which is a special symbol for the number ten. In our numerical system, Number of hundreds
there is no special symbol for ten. Number of thousand units
■ On the other hand, almost all primitive numerical systems lack something that the system Number of tens of thousands
Indo-Arabic has, and which turns out to be much more important than a symbol for ten. Number of hundred thousand
We are talking about zero. Number of millions
Yes, the zero. The humble zero is undoubtedly one of the most important inventions of the Since each position corresponds to a power of ten, a symbol is not required.
history of numbers and mathematics. Supports positional notation because it allows us to special for the ten, because it is represented by placing the 1 in a different position and
See immediately the difference between 25 and 205 and 250. The zero also facilitates many operations. using 0 as a placeholder.
mathematics that become uncomfortable in non-positional systems, particularly multiplication
and the division.
Chapter 9 OURTENDIGITS95
What interests us here is that the UPC is a binary code, although it might not be.
It may seem so at first glance. It could be interesting to decode the UPC and examine how it works.
In its most common form, the UPC is a collection of 30 vertical black bars of various
widths, divided by spaces of various widths, along with some numbers. For example,
this is the UPC that appears on the 10¾ ounce Campbell's chicken noodle soup:
0 51000 01251 7
That same UPC appeared in the first edition of this book. It has not changed in more
20 years old!
We feel tempted to try to visually interpret the UPC from the point of
view of fine black and white bars, narrow and wide spaces and, of course, that is a
way of looking at it. The black bars in the UPC can have four different widths, and the bars
thicker ones can have widths two, three, or four times greater than those of the bar.
Finally. Similarly, the wider spaces between the bars are two, three, or four times.
wider than the width of the narrowest space.
But another way to see the UPC is as a series of bits. Note that the symbol
The complete barcode is not exactly what the scanner 'sees' at the checkout.
The scanner does not try to interpret the numbers printed at the bottom, for example, because
Around the outer circle there are also some coded numbers, which reveal the that would require a more sophisticated computer technique known as optical recognition
latitude and longitude of the Jet Propulsion Laboratory: 34°11'58"N 118°10'31"W. With of characters (optical character recognition, OCR). Instead, the scanner will only see a strip
the simple coding system used here, there is nothing that distinguishes letters and numbers. The narrow of this complete block. The UPC is this large to provide cashiers something
to what to aim with the scanner. The strip that the scanner sees can be represented like this:
numbers 10 and 11 that are part of the geographic coordinates could be the letters J and K.
Only the context indicates that they are numbers.
Perhaps the most common visual representation of binary digits is the ubiquitous Code
Universal Product Code (UPC), the barcode symbol that This almost looks like Morse code, right? In fact, the original invention of codes of
appears on almost any packaged item we buy. The UPC is one of the dozens scannable bars were partly inspired by Morse code.
of barcodes used for various purposes. If you have the printed version of this book,
As the computer scans this information from left to right, it assigns a
You will see on the back cover another type of barcode that encodes the ISBN (International
bit 1 to the first black bar it encounters and a bit 0 to the next white space. The spaces
Standard Book Number, international standardized code for books.
and subsequent bars are read as a series of 1, 2, 3 or 4 consecutive bits, depending
Although the UPC generated some paranoia with its introduction, in reality it is an innocent little thing, of the width of the space or the bar. The correspondence of the scanned barcode
invented to automate the collection and preparation of inventory in commerce in bits it is simply:
retailer, something that it does quite well. Before the UPC, it was not possible for cash registers
supermarkets generated a detailed purchase receipt. Now it is something common.
10100011010110001001100100011010001101000110101010111001011001101101100100111011001101000100101
126CHAPTER 11 BITABITABIT127
You can use the following two logic gates to achieve these results: This box is labeled as a 'semi-adder' for a reason. It is clear that it adds two digits.
binaries and it gives us a sum bit and a carry bit. But, for higher binary numbers
XOR 0 1
A 1 bit, the half adder is inadequate for anything other than summing the two least bits.
0 0 1 significant. It does not add a possible carry bit from a previous 1-bit sum. For example,
1 1 0 let's suppose we are adding two binary numbers like these:
1111
AND 0 1
+ 1111
0 0 0
11110
1 0 1
We can use the half adder for the sum of the rightmost column: 1 plus 1
The sum of two binary numbers is given by the output of an XOR gate and the carry bit is given by it's 0 and we take 1. For the second column from the right, actually nece-
the output of an AND gate. Thus, we can combine an AND gate and an XOR gate We need to add three binary numbers due to the carry. And that applies to all columns.
to add two binary digits called A and B: subsequent. Each subsequent sum of two binary numbers must add the carry bit
from the previous column.
Entry
A Exit To add three binary numbers, we need two half-adders and one OR gate.
Entrance Sum
B connected in this way:
Transport of A S Exit
entry Sum
Transport of Semisu-
exit mador
Entry
A S B AS
A
Semisu- Transport of
mador exit
Entry
Please note that this is more complex than it appears! The XOR gate is actually B B AS
a combination of an OR gate, a NAND gate, and an AND gate, and each of those
doors consist of two relays. But it is easier to understand if many details are hidden. This The reason this works may not be very clear. Start with the inputs.
the process is sometimes referred to as 'encapsulation': a complex assembly of something is hidden in a
A and B to the first half-adder on the left. The output is a sum and a carry. That sum
simplest package. At any time, we can unwrap that package if we want to It should be added to the carry of the previous column, called input carry. That carry of
see the details, but it's not necessary. input and the sum of the first half-adder are inputs to the second half-adder. The sum of the
Here is another encapsulation: instead of drawing and redrawing an AND gate and a gate the second half-adder is the final sum. The two output carries of the half-adders are
XOR, we can represent the entire circuit simply with a box like this, inputs to an OR gate. You might think that another half-adder is needed here, and the truth is
called 'semisumador': this could work. But if you examine all the possibilities, you will realize that
It never happens that in both output carries the two half adders are equal to 1.
Entry A S Exit The OR gate is sufficient to add them because it is the same as the XOR gate if it never happens.
A Sum
Semisu- that both entries are 1.
Entry
mador
Transport
B B AS
outgoing Instead of drawing and redrawing that diagram, we can call it a full adder:
Transport of AC Exit
The labels S and AS mean "Sum" and "Carry out". Sometimes, a box of this type entry S
Sum
Entry Adder
is called 'black box'. A particular combination of inputs results in some A
A complete
particular outputs, but the implementation is hidden. However, as we know what Entry AS Transport of
B B exit
go inside the semi-summer, the term 'transparent box' is more correct.
176CHAPTER 14 SUMWITHLOGICGATES177
For now, we are going to try to store only 1 byte of data. You can mount eight flip-flops of Towards the end of chapter 14, eight 1-bit adders have also been gathered and connected.
Type D activated by level with all Clock inputs consolidated as a single signal. Here to sum integer bytes:
Here is the resulting package:
8 8
A7...A0 B7...B0
AS 8-bit adder AE
S7...S0
In that chapter, the eight A entries and the eight B entries were connected to switches, the
Latches capable of storing a whole byte at once. The eight inputs of the part AE (incoming carry) was connected to ground and the eight outputs S (Sum) and outputs AS (carry)
superior are labeled D0a D7, and the eight exits at the bottom are labeled as Q0 a (exit) were connected to light bulbs.
Q7. The input on the right is Clock. The Clock signal is usually 0. When the Clock signal is 1, the The adders can be used as modular building blocks for assembly.
The complete 8-bit value at the D inputs is transferred to the Q outputs when the Clock signal more complex circuits. For example, it is possible to store the output of the 8-bit adder in a
returns to 0, that 8-bit value stays there until the next time the Clock signal is 1. The 8-bit latch. It is also possible to replace one of the rows of eight switches with a latch.
cadalatchse outputs are ignored. of 8 bits so that the output of the latch is an input to the adder. Here is something that
The 8-bit latch can also be drawn with the eight data inputs and eight Q outputs. combine those two concepts to create what could be called 'accumulating adder' that
grouped in a data route, as shown here: maintains a total accumulated from multiple numbers:
Eight switches
8
D7...D0 8
8
226CHAPTER 17 F E E D B A C K A N D B I S TA B L E S 2 2 7
A F2 F 1 F0 B like S). Although there are only three indicators, they are treated as 3 bits of a byte when exiting the ALU.
Then, the Carry Indicator rises back to the top to provide the entry.
Input carry indicator of the Add/Subtract module.
The next step is to hide all this complex logic in a simple box:
F1F0 A B F2 F1F0 A B
Entry
Sum/Subtraction Exit Logic F2F1F0 A B
CY CY
Exit Exit
Clock Arithmetic-logic unit (ALU) Enable
Entry
H Indicadores Exit
THREE
Exit
Indicators Exit
The two boxes labeled TRES are three-state buffers. The Logic module enables
an output only for the three combinations of F0, F1y F2which select AND operations,
OR or XOR. The three-state buffer on the output of the Add/Subtract model is only enabled if F.2
is 0, which indicates addition or subtraction.
At the bottom, both latches have their Clk inputs connected to a Clock input.
in the lower left that applies to the entire ALU. Another three-state buffer is
controlled by a signal Enable in the bottom left that is also an input
to the ALU. The three-state buffer at the bottom right is the composite output of the
Addition/Subtraction and Logic modules.
Most of the logic gates in the diagram are dedicated to the Carry Indicator
(abbreviated as CY). The Carry Indicator should be set up if the signal F2is 0 (indicating
an addition or subtraction operation) or F1y F0son 1, which indicates a Compare operation.
The three indicators are inputs that latch in the center of the bottom part. A NOR door.
For eight inputs, determine if the result of an operation is all zeros. That is the Indicator.
from zero (abbreviated as Z). The high bit of the data output is the Sign Indicator (abbreviated
332CHAPTER 21 THEARITHMETIC-LOGICUNIT333
16 bits during this time and the diode ROM matrix for the address establishes that
value in the HL registers). When the destination is a register, the second three-state buffer
controls the input Clock for the register matrix. When the destination is memory, the signal
Writing RAM stores that value in memory.
date
date
data
In the case of the instructions INX and DCX, the Execution Pulse 1 signal stores the value of the
HL records in the latch incrementer-decrementer.
The instructions INXyDCX are the only two instructions that involve address management.
during the second execution cycle. These two instructions make the incremented value or
CE1 3-state buffer PE1 3-state buffer
decremented from the HL register is on the address bus. Then, the Execution Pulse 2 signal
make the new value of HL be stored in the H and L registers.
Enable Enable Enable Enable Clock Write Clock Watch
The diode ROM matrix for the 8-bit data bus is a bit more complicated. The MR SD Latch. Acu. MR RAM ALU Acupuncture.
RAM Inst. 2
I have divided into two diagrams corresponding to the two instruction cycles. In the following
the figure is the first instruction.
For the two types of instructions MVI ('move immediate'), the contents of the latch
This circuit is the implementation of the 8-bit data column bus from the table on the page.
instruction 2 is enabled in the data bus; the value is stored in the register array or is
362. The two three-state buffers at the bottom are enabled by the Cycle signals.
save in memory.
Execution 1 and Pulse Execution 1. The first three-state buffer controls what is on the bus.
of data; the second three-state buffer controls where that value is stored. All arithmetic and logical instructions are represented in this diagram through the
instructionsADDyADI("immediate sum"). The value enabled in the data bus is the matrix
The three types of MOV instructions at the top are followed by a destination and a
de registro, Salida Datos RAM oLatchde instrucción 2, dependiendo de la instrucción. En
source. These destinations and sources can be any of the records or can be memory.
In all cases, that value clings to the arithmetic-logic unit. These instructions require
addressed by the HL registers. When the source is a register, the register matrix (abbreviated
an additional job during the second execution cycle, which we will see shortly.
as MR in the diagram) is enabled in the data bus; when the source is memory, it is
Data Output from RAM enabled. (Please note that RAM is addressed by the
374CHAPTER 23 CPUControlSignals375
C CODE
SECOND EDITION
WIDELY UPDATED
Computers are everywhere, in a more
evident in our laptops and smartphones, but
CHARLES PETZOLDit has been 35 years
also in our cars, televisions, microwaves,
writing about programming
alarm clocks, vacuum cleaners, and other appliances
smart. Have you ever wondered what there is and computers. Their books include
within these devices that make our life more than a dozen tutorials
easier, from time to time, more exasperating? of programming and The Annotated
Turing:AGuided Tour through
For more than 20 years, readers have enjoyed
Alan Turing’s Historic Paper on
of the instructive history of Charles Petzold about the
Computability and the Turing
the inner life of computers and now it has been revised
Machine (Wiley, 2008). Lives in the
for this new era of computing. Easy to understand
and illustrated in an intelligent way, this is the book that city of New York with his wife,
unravel the mystery. You will discover what the flashlights, the historian and novelist Deirdre
black cats, the rockers and the midnight stroll Sinnott, and two cats named Honey
Paul Revere can teach you about the and Heidi. Their website is
computer science and how human ingenuity and our [Link].
the compulsion to communicate has shaped us all
the electronic devices that we use.
This new expanded edition explores in greater depth
depth the construction bit by bit, door to door,
the heart of a smart device, the unit
central processing that combines operations
simplest basics to achieve the greatest accomplishments
complex. In addition to adding new chapters, Petzold
he has created a new website, CodeHiddenLanguage.
that uses animated interactive graphics to
make computers even easier to
understand.
From the simple tick-tock of the clocks to the buzzing
worldwide Internet, Code reveals the essence of
the digital revolution.
MULTIMEDIA [Link]