Signal Paths from Analog to Digital (DACs)

The concept of a programmable system-on-chip (SoC) started in 1972 with the advent of the unassuming 4-bit TMS1000 microcomputer —the perfect fit for applications such as calculators and microwave ovens that required a device with everything needed to embed "electronic intelligence".

Microcomputers changed the way engineers approached equipment design;

1. for the first time they could reuse proven electronics hardware, needing only to create software specific to the application. 
2. The result of microcomputer-based designs has been a reduction in both system cost and time-to-market.

In 2005 many things have changed, but many things remain the same. The term microcomputer has been replaced with microcontroller unit (MCU) —a name more descriptive of a typical application.
Today’s MCU, just like yesterday’s microcomputer, remains the heart and soul of many systems.

1. But over time the MCU has placed more emphasis on providing a higher level of integration and control processing and less on sheer computing power. 
2. The race for embedded computing power has been won by the dedicated digital signal processor (DSP), a widely used invention of the ‘80s that now dominates high-volume, computing-intensive embedded applications such as the cellular telephone. But the design engineer’s most used tool, when it comes to implementing cost effective system integration, remains the MCU. The MCU allows just the right amount of intelligent control for a wide variety of applications.
3. Today there are hundreds of MCUs readily available, from low-end 4-bit devices like those found in a simple wristwatch, to high-end 64-bit devices. But the workhorses of the industry are still the versatile 8/16-bit architectures. Choices are available with 8 to 100+ pins and program memory ranging from 1 kb to 64 KB. 
4. The MCU’s adoption of mixed-signal peripherals is an area that has greatly expanded, recently enabling many new SoC solutions. It is common today to find MCUs with 12-bit analog-to-digital and digital-to-analog converters combined with amplifiers and power management, all on the same chip in the same device. This class of device offers a complete signal-chain on a chip for applications ranging from energy meters to personal medical devices.
5. Modern MCUs combine mixed-signal integration with instantly programmable Flash memory and embedded emulation. 
6. In the hands of a savvy engineer, a unique MCU solution can be developed in just days or weeks compared to what used to take months or years. 
7. You can find MCUs everywhere you look from the watch on your wrist to the cooking appliances in your home to the car you drive. An estimated 20 million MCUs ship every day(2005), with growth forecast for at least a decade to come. The march of increasing silicon integration will continue offering an even greater variety of available solutions—but it is the engineer’s creativity that will continue to set apart particular system solutions.

Analog system designers many times in the past avoided the use of electronics for their system functions because electronic circuits could not provide the dynamic range of the signal

• without severe nonlinearity, or 
• because the circuits drifted or became unstable with temperature, or 
• because the computations using analog signals were quite inaccurate.

As a result, the design shifted to other disciplines, for example, mechanical.

Today, young engineers requested by their superiors to design an analog control system, have an entirely new technique available to them to help them design the system and overcome the “old” problems.
The design technique is this:

1. sense the analog signals and convert them to electrical signals;
2. condition the signals so they are in a range of inputs to assure accurate processing; 
3. convert the analog signals to digital; make the necessary computations using the very high-speed IC digital processors available with their high accuracy;
4. convert the digital signals back to analog signals; and 
5. output the analog signals to perform the task at hand.

Here we try to explain the functions that are in the signal chain, and explain how to design electronic circuits to perform the functions. What we have to know are:

1. different types of sensors and their outputs. 
2. different techniques of conditioning the sensor signals, especially amplifiers and op amps. 
3. techniques and circuits for analog-to-digital and digital-to-analog conversions, and what a digital processor is and how it works. 
4. data transmissions and power control
5. assembly-language programming, and also 
6. hands on experience on building a working project. 
7. ability on choosing a digital processor. We choose to use TI MSP430 microcontroller because of its design, and because it is readily available, it is well supported with design and applications documentation, and it has relatively inexpensive evaluation tools.

The goal here is to provide understanding and learning of the new design technique available to analog system designers and the tools available to provide system solutions.

                                          Intro

Designers of analog electronic control systems have continually faced the following obstacles in arriving at a satisfactory design:

1. Instability and drift due to temperature variations.
2. Dynamic range of signals and non-linearity when pressing the limits of the range.
3. Inaccuracies of computation when using analog quantities.
4. Adequate signal frequency range.

Today’s designers, however, have a significant alternative offered to them by the advances in integrated circuit technology, especially low-power analog and digital circuits.
The alternative new design technique for analog systems is to

1. sense the analog signal, 
2. convert it to digital signals, 
3. use the speed and accuracy of digital circuits to do the computations, and 
4. convert the resultant digital output back to analog signals.

The new design technique requires that the electronic system designer interface between two distinct design worlds.

1. First, between analog and digital systems, and 
2. second, between the external human world and the internal electronics world. 

Various functions are required to make the interface.

1. First, from the human world to the electronics world and back again and, 
2. in a similar fashion, from the analog systems to digital systems and back again. 

Here we identify:

• the electronic functions needed, and 
• describe how electronic circuits are designed and applied to implement the functions,and 
• give examples of the use of the functions in systems.

                                          A Refresher

Since we deal with the electronic functions and circuits that interface or couple analog-to-digital circuits and systems, or vice versa, a short review is provided so it is clearly understood what analog means and what digital means.

                                                         Analog

1. Analog quantities vary continuously, and 
2. analog systems represent the analog information using electrical signals that vary smoothly and continuously over a range.

A good example of an analog system is the recording thermometer shown in Figure 1-1. The actual equipment is shown in Figure 1-1a.

 An ink pen records the temperature in degrees Fahrenheit and plots it continuously against time on a special graph paper attached to a drum as the drum rotates.
The record of the temperature changes is shown in Figure 1-1b.

Note that the temperature changes smoothly and continuously. There are no abrupt steps or breaks in the data.

Another example is the automobile fuel gauge system shown in Figure 1-2.

The electrical circuit consists of a potentiometer, basically a resistor connected across a car battery from the positive terminal to the negative terminal, which is grounded. The resistor has a variable tap that is rotated by a float riding on the surface of the liquid inside the gas tank.
A voltmeter reads the voltage from the variable tap to the negative side of the battery (ground) abbreviated as GND (black), 0V, usually connected to the vehicle's metal chassis and body.
The voltmeter indicates the information about the amount of fuel in the gas tank.

It represents the fuel level in the tank.The greater the fuel level in the tank the greater the voltage reading on the voltmeter.

The voltage is said to be an analog of the fuel level.

An analog of the fuel level is said to be a copy of the fuel level in another form—it is analogous to the original fuel level.

The voltage (fuel level) changes smoothly and continuously so the system is an analog system, but is also an analog system because the system output voltage is a copy of the actual output parameter (fuel level) in another form.

                                                        Digital

Digital quantities vary in discrete levels.

In most cases, the discrete levels are just two values—ON and OFF.

Digital systems carry information using combinations of ON-OFF electrical signals that are usually in the form of codes that represent the information. 

The telegraph system is an example of a digital system.
The system shown in Figure 1-3 is a simplified version of the original telegraph system, but it will demonstrate the principle and help to define a digital system.

The electrical circuit (Figure 1-3a) is a battery with a switch in the line at one end and a light bulb at the other.

1. The person at the switch position is remotely located from the person at the light bulb. 
2. The information is transmitted from the person at the switch position to the person at the light bulb by coding the information to be sent using the International Morse telegraph code.
3. Morse code uses short pulses (dots) and long pulses (dashes) of current to form the code for letters or numbers as shown in Figure 1-3b. As shown in Figure 1-3c, combining the codes of dots and dashes for the letters and numbers into words sends the information. 
4. The sender keeps the same shorter time interval between letters but a longer time interval between words. This allows the receiver to identify that the code sent is a character in a word or the end of a word itself. The T is one dash (one long current pulse). The H is four short dots (four short current pulses). The R is a dot-dash-dot. And the two Es are a dot each. 
5. The two states are ON and OFF—current or no current. The person at the light bulb position identifies the code by watching the glow of the light bulb. In the original telegraph, this person listened to a buzzer or “sounder”to identify the code.
6. Coded patterns of changes from one state to another as time passes carry the information. 
7. At any instant of time the signal is either one of two levels. The variations in the signal are always between set discrete levels, but, in addition, a very important component of digital systems is the timing of signals. In many cases, digital signals, either at discrete levels, or changing between discrete levels, must occur precisely at the proper time or the digital system will not work. 
8. Timing is maintained in digital systems by circuits called system clocks.

This is what identifies a digital signal and the information being processed in a digital system.

                                                          Binary

The two levels—ON and OFF—are most commonly identified as 1(one) and zero (0) in modern binary digital systems, and the 1 and 0 are called binary digits or bits for short.

Since the system is binary (two levels), the maximum code combinations 2^n depends on the number of bits, n, used to represent the information. 

For example, if numbers were the only quantities represented, then the codes would look like Figure 1-4, when using a 4-bit code to represent 16 quantities.

To represent larger quantities more bits are added.
For example, a 16-bit code can represent 2^16=65,536 quantities.

The first bit at the right edge of the code is called the least significant bit (LSB). The left-most bit is called the most significant bit (MSB).

                                    Binary Numerical Quantities

Our normal numbering system is a decimal system. Figure 1-5 is a summary showing the characteristics of a decimal and a binary numbering system.

Note that each system in Figure 1-5 has specific digit positions with specific assigned values to each position. Only eight digits are shown for each system in Figure 1-5.

1. Note that in each system, the LSB is either 100 in the decimal system or 20 in the binary system. 
2. Each of these has a value of one since any number to the zero power is equal to one.

The following examples will help to solidify the characteristics of the two systems and the conversion between them.

Example 1. Identifying the Weighted Digit Positions of a Decimal Number
Separate out the weighted digit positions of 6524.

Solution:
6524 = 6 × 10^3 + 5 × 10^2 + 2 × 10^1 + 4 × 10^0
6524 = 6 × 1000 + 5 × 100 + 2 X 10 + 4 × 1
6524 = 6000 + 500 + 20 + 4

Can be identified as 6524₁₀ since decimal is a
base 10 system. Normally 10 is omitted since
it is understood.

Example 2. Converting a Decimal Number to a Binary Number
Convert 103 to a binary number.

Solution:
103₁₀ / 2 = 51 with a remainder of 1
51/2 = 25 with a remainder of 1
25/2 = 12 with a remainder of 1
12/2 = 6 with a remainder of 0
6/2 = 3 with a remainder of 0
3/2 = 1 with a remainder of 1
1/2 = 0 with a remainder of 1 (MSB)
103₁₀ = 1100111

Example 3. Determining the Decimal Value of a Binary Number
What decimal value is the binary number 1010111?

Solution:
Solve this the same as Example 1, but use the binary digit weighted position values.
Since this is a 7-bit number:
And since the MSB is a 1, then MSB = 1 × 2^6 = 64
and  (next digit)                                     0 × 2^5 = 0
and  (next digit)                                     1 × 2^4 = 16
and  (next digit)                                     0 × 2^3 =   0
and  (next digit)                                     1 × 2^2 =   4
and  (next digit)                                     1 × 2^1 =   2
and  (next digit, LSB)                            1 × 2^0 =    1
                                                                               ----------
                                                                                 87

                              Binary Alphanumeric Quantities

If alphanumeric characters are to be represented, then Figure 1-6, the ASCII table defines the codes that are used.
For example, it is a 7-bit code, and capital M is represented by 1001101. Bit #1 is the LSB and bit #7 is the MSB.

As shown, upper and lower case alphabet, numbers, symbols, and communication codes are represented.

                               Accuracy vs. Speed — Analog and Digital

Quantities in nature and in the human world are typically analog. The temperature, pressure, humidity and wind velocity in our environment all change smoothly and continuously, and in many cases, slowly.

Instruments that measure analog quantities usually have slow response and less than high accuracy. 

To maintain an accuracy of 0.1% or 1 part in 1000 is difficult with an analog instrument.

Digital quantities, on the other hand, can be maintained at very high accuracy and measured and manipulated at very high speed. 

The accuracy of the digital signal is in direct relationship to the number of bits used to represent the digital quantity. 

For example, using 10 bits, an accuracy of 1 part in 1024 (2^10=1204) is assured.
Using 12 bits gives four times the accuracy (1 part in 4096, 2^12=4096), and
using 16 bits gives an accuracy of 0.0015%(2^16=65536), or
1 part in 65,536. 

And this accuracy can be maintained as digital quantities are manipulated and processed very rapidly, millions of times faster than analog signals.

The advent of the integrated circuit has propelled the use of digital systems and digital processing.

The small space required to handle a large number of bits at high speed and high accuracy, at a reasonable price, promotes their use for high-speed calculations.

As a result, if analog quantities are required to be processed and manipulated, the new design technique is to

1. first convert the analog quantities to digital quantities, 
2. process them in digital form, 
3. reconvert the result to analog signals and 
4. output them to their destination to accomplish a required task.

The complete procedure is indicated in Figure 1-7, and the need for analog circuits, digital circuits and the conversion circuits between them is immediately apparent.

                                      Interface Electronics

The system shown in Figure 1-7 shows the major functions needed to couple analog signals to digital systems that

• perform calculations, 
• manipulate, and 
• process the digital signals and 
• then return the signals to analog form.

In that article we deal with the analog-to-digital portion of Figure 1-7, and in a later article we'll deal with the digital-to-analog portion.

                  The Basic Functions for Analog-to-Digital Conversion

                                 Sensing the Input Signal

Figure 1-8 separates out the analog-to-digital portion of the Figure 1-7 chain to expand the basic functions in the chain.

Most of nature’s inputs such as temperature, pressure, humidity, wind velocity, speed, flow rate, linear motion or position are not in a form to input them directly to electronic systems.

They must be changed to an electrical quantity—a voltage or a current—in order to interface to electronic circuits.

The basic function of the first block is called sensing. The components that sense physical quantities and output electrical signals are called sensors.

The sensor illustrated in Figure 1-8 measures pressure. The output is in millivolts and is an analog of the pressure sensed. An example output plotted against time is shown.

                                Conditioning the Signal

Conditioning the signal means that some characteristic of the signal is being changed. In Figure 1-8, the block is an amplifier that increases the amplitude of the signal by 1,000 times so that the output signal is now in volts rather than millivolts.

The amplification is linear and the output is an exact reproduction of the input, just changed in amplitude. 

Other signal conditioning circuits may

• reduce the signal level, or 
• do a frequency selection (filtering), or 
• perform an impedance conversion.

Amplification is a very common signal conditioning function. Some electronic circuits handle only small-signal signals, while others are classified as power amplifiers to supply the energy for outputs that require lots of joules (watts are joules/second).

                           Analog-to-Digital Conversion

In the basic analog-to-digital conversion function, as shown in Figure 1-7, the analog signal must be changed to a digital code so it can be recognized by a digital system that processes the information.

Since the analog signal is changing continuously, a basic subfunction is required. It is called a sample-and-hold function.

1. Timing circuits (clocks) set the sample interval and the function takes a sample of the input signal and holds on to it. 
2. The sample-and-hold value is fed to the analog-to-digital converter that generates a digital code whose value is equivalent to the sample-and-hold value. This is illustrated in Figure 1-8 as the conditioned output signal is sampled at intervals 0, 1, 2, 3, and 4 and converted to the 4-bit codes shown.
3. Because the analog signal changes continually, there maybe an error between the true input voltage and the voltage recorded at the next sample.

Example 4. A to D Conversion
For the analog signal shown in the plot of voltage against time and the 4-bit codes given for the indicated analog voltages, identify the analog voltage values at the sample points and the resultant digital
codes and fill in the following table.

Obviously, one would like to increase the sampling rate to reduce this error.
However, depending on the code conversion time, if the sample rate gets to large, there is not enough time for the conversion to be completed and the conversion function fails.

Thus, there is a compromise in the analog-to-digital converter between the speed of the conversion process and the sampling rate. 

Output signal accuracy also plays a part. If the output requires more bits to be able to represent the magnitude and the accuracy required, then higher-speed conversion circuits and more of them are going to be required.

Thus, design time, cost, and all the design guidelines enter in.

As shown in Figure 1-8, the bits of the digital code are presented all at the same time (in parallel) at each sample point.
Other converters may present the codes in a serial string. It depends on the conversion design and the application.

                                 Summary

So far we reviewed

1. analog and digital signals and systems, 
2. digital codes, 
3. the decimal and binary number systems, and 
4. the basic functions required to convert analog signals to digital signals.

In a next article we'll complete the look at the basic functions required to convert digital signals to analog signals. It will be
important to have these basic functions in mind as the electronic circuits that perform these functions are the "core business" of our work.__

Resources

1. Foundations of Analog and Digital Electronic Circuits
2. Home » Courses » Electrical Engineering and Computer Science » Circuits and Electronics » Lecture Notes (MIT OpenCourseWare)
3. Home » Courses » Electrical Engineering and Computer Science » Circuits and Electronics
4. The University Program (
5. Electronics I and II
6. Analog and Digital Circuits for Electronic Control System Applications
7. Fundamentals of Digital Electronics
8. Notes on Digital Circuits  
9. Analog to Digital (ADC) and Digital to Analog (DAC) Converters
10. Digital Vs Analog control
11. Digital to Analog Converter--DAC (slides)
12. Analog-Digital Interface Integrated Circuits (slides)
13. Analog-Digital Interface Integrated Circuits
14. Digital-to-Analog Converter Interface for Computer Assisted Biologically Inspired Systems (117p.)
15. Analog Integrated Circuit Design: Why? 
16. ANALOGUE AND DIGITAL ELECTRONICS (beginner notes)
17. Introduction to analog circuits  and operational amplifiers
18. Digital Pulse-Width Modulation Control in Power Electronic Circuits: Theory and Applications
19. Analog and Digital Control of an Electronic Throttle Valve
20. Intro to Mechatronics (notes)
21. Difference between Analog and Digital circuits 
22. Ultralow-Power Electronics for Biomedical Applications
23. ANALOG ELECTRONICS LECTURE NOTES (papageorgas at http://www.electronics.teipir.gr/index.php/el/)
24. Basic Analog Electronic Circuits(slides)
25. Digital electronics (WP)
26. Analogue electronics (WP)
27. Computer-Aided Design of Analog and Mixed-Signal Integrated Circuit (paper)
28. Hardware Trojan Detection in Analog/RF Integrated Circuits (paper)
29. Analog Integrated Circuits
30. Types of ICs. Classification of Integrated Circuits and Their Limitation   

1. Simulation of Logic Circuits

EDU Resources

1. berkeley.edu
2. osu.edu
3. ufl.edu
4. utdallas.edu
5. uakron.edu
6. illinois.edu
7. ucla.edu
8. uci.edu
9. utk.edu 
10. columbia.edu
11. gatech.edu
12. tamu.edu
13. colostate.edu 
14. utsa.edu
15. k-state.edu
16. Center for Design of Analog-Digital Integrated Circuits (CDADIC)

Other Resources

•  What are the applications of integrated circuits? (Q)
•  What are digital electronics applications? (Q)
• A  forum  for  the  exchange  of  circuits,  systems,  and  software  for  real-world  signal  processing
• Hybrid Digital-Analog Circuits Can Increase Computational Power of Chaos-Based Systems
•  https://www.electronics-circuits.com/
•  Motorola Field Programmable Analog Arrays in Simulation, Control, and Circuit Design Laboratories (paper)
•  A Self-Tuning Analog Proportional-Integral-Derivative (PID) Controlle (paper)
• ANALYSIS OF SWITCHING TRANSIENTS IN A DYNAMICALLYRECONFIGURABLE ANALOG/DIGITAL HARDWARE
• OPTIMIZATION OF PERFORMANCE OF DYNAMICALLY RECONFIGURABLE MIXED-SIGNAL HARDWARE USING FIELD PROGRAMMABLE ANALOG ARRAY (FPAA) TECHNOLOGY (Diplomarbeit) 

• IEEE Control Systems Magazine FEATURE T he history of  analog computing.
•  Analog Computation by DNA Strand Displacement Circuits

Where Is the Internet?

It is quite common for the Internet to be visually represented as a cloud, which is perhaps an apt way to think about the Internet given the importance of light and magnetic pulses to its operation. To many people using it, the Internet does seem to lack a concrete physical manifestation beyond our computer and cell phone screens.
But it is important to recognize that our global network of networks does not work using magical water vapor, but is implemented via millions of miles of copper wires and fiber optic cables, as well as via hundreds of thousands or even millions of server computers and probably an equal number of routers, switches, and other networked devices, along with many thousands of air conditioning units and specially constructed server rooms and buildings.
The big picture of all the networking hardware involved in making the Internet work is far beyond our  scope here. We should,  however, try to provide at least some sense of the hardware that is involved in making the web possible.

       From the Computer to the Local Provider

Andrew Blum, in his eye-opening book, Tubes: A Journey to the Center of the Internet, tells the reader that he decided to investigate the question “Where is the Internet” when a hungry squirrel gnawing on some outdoor cable wires disrupted his home connection thereby making him aware of the real-world texture of the Internet.
While you may not have experienced a similar squirrel problem, for many of us, our main experience of the hardware component of the Internet is that which we experience in our homes. While there are many configuration possibilities, Figure 1.18 does provide an approximate simplification of a typical home to local provider setup.
The broadband  modem (also called a cable modem or DSL modem) is a bridge between the network hardware outside the house (typically controlled by a phone or cable company) and the network hardware inside the house. These devices are often supplied by the ISP.

The wireless router is perhaps the most visible manifestation of the Internet in one’s home, in that it is a device we typically need to purchase and install.
Routers are in fact one of the most important and ubiquitous hardware devices that make the Internet work. At its simplest, a router is a hardware device that forwards data packets from one network to another network. 

1. When the router receives a data packet, it examines the packet’s destination address and then forwards it to another destination by deciding the best path to send the packets.
2. A router uses a routing table to help determine where a packet should be sent. It is a table of connections between target addresses and the node (typically another router) to which the router can deliver the packet. 

In Figure 1.19, the different routing tables use next-hop routing, in which the router only knows the address of the next step of the path to the destination; it leaves it to the next step to continue routing the packet to the appropriate destination. The packet thus makes a variety of successive hops until it reaches its destination. There are a lot of details that have been left out of this particular illustration.

Routers will make use of

• submasks, 
• timestamps, 
• distance metrics, and 
• routing algorithms

to supplement or even replace routing tables; but those are all topics for a network architecture course.
Once we leave the confines of our own homes, the hardware of the Internet becomes much murkier.
In Figure 1.18, the various neighborhood broadband cables (which are typically using copper, aluminum, or other metals) are aggregated and connected to fiber optic cable via fiber connection boxes.

Fiber optic cable (or simply optical fiber) is a glass-based wire that transmits light and has significantly greater bandwidth and speed in comparison to metal wires. 

In some cities (or large buildings), you may have fiber optic cable going directly into individual buildings; in such a case the fiber junction box will reside in the building.

• These fiber optic cables eventually make their way to an ISP’s head-end, which is a facility that may contain a cable modem termination system (CMTS) or a digital subscriber line access multiplexer (DSLAM) in a DSL-based system. 
• This is a special type of very large router that connects and aggregates subscriber connections to the larger Internet. 
• These different head-ends may connect directly to the wider Internet, 
• or instead be connected to a master head-end, which provides the connection to the rest of the Internet.

         From the Local Provider to the Ocean’s Edge

Eventually your ISP has to pass on your requests for Internet packets to other networks.

1. This intermediate step typically involves one or more regional network hubs.
2. Your ISP may have a large national network with optical fiber connecting most of the main cities in the country. 
3. Some countries have multiple national or regional networks, each with their own optical network. 

Canada, for instance, has three national networks that connect the major cities in the country as well as connect to a couple of the major Internet exchange points in the United States, as well as several provincial networks that connect smaller cities within one or two provinces.
Alternatively, your smaller regional ISP may have transit arrangements with a larger national network (that is, they lease the use of part of their optical fiber network’s bandwidth).

A general principle in network design is that the fewer the router hops (and thus the more direct the path), the quicker the response.

Figure 1.20 illustrates some hypothetical connections between several different networks spread across four countries. As you can see, just like in the real world, the countries in the illustration
differ in their degree of internal and external interconnectedness.

• The networks in Country A are all interconnected, but rely on Network A1 to connect them to the networks in Country B and C. 
• Network B1 has many connections to other countries’ networks. 
• The networks within Country C and D are not interconnected, and thus rely on connections to international networks in order to transfer information between the two domestic networks. For instance, even though the actual distance between a node in Network C1 and a node in C2 might only be a few miles, those packets might have to travel many hundreds or even thousands of miles between networks A1 and/or B1.

Clearly this is an inefficient system, but is a reasonable approximation of the state of the Internet in the late 1990s (and in some regions of the world this is still the case), when almost all Internet traffic went through a few Network Access Points (NAP), most of which were in the United States.
This type of network configuration began to change in the 2000s, as more and more networks began to interconnect with each other using an Internet exchange point (IX or IXP). These IXPs allow different ISPs to peer with one another (that is, interconnect) in a shared facility, thereby improving performance for each partner in
the peer relationship(List of Internet exchange points).

Figure 1.21 illustrates how the configuration shown in Figure 1.20 changes with the use of IXPs.

1. As you can see, IXPs provide a way for networks within a country to interconnect. Now networks in Countries C and D no longer need to make hops out of their country for domestic communications. 
2. Notice as well that for each of the IXPs, there are connections not just with networks within their country, but also with other countries’ networks as well. 
3. Multiple paths between IXPs provide a powerful way to handle outages and keep packets flowing. 
4. Another key strength of IXPs is that they provide an easy way for networks to connect to many other networks at a single location.11

As you can see in Figure 1.22, different networks connect not only to other networks within an IXP, but now large websites such as Microsoft and Facebook are also connecting to multiple other networks simultaneously as a way of improving the performance of their sites.
Real IXPs, such as at Palo Alto (PAIX), Amsterdam (AMS-IX), Frankfurt (CE-CIX), and London (LINX), allow many hundreds of networks and companies to interconnect and have throughput of over 1000 gigabits per second. The scale of peering in these IXPs
is way beyond that shown in Figure 1.22 (which shows peering with only five others); companies within these IXPs use large routers from Cisco and Brocade that have hundreds of ports allowing hundreds of simultaneous peering relationships.
In recent years, major web companies have joined the network companies in making use of IXPs.

As shown in Figure 1.23, this sometimes involves mirroring (duplicating) a site’s infrastructure (i.e., web and data servers) in a data center located near the IXP.
For instance, Equinix Ashburn IX in Ashburn, Virginia, is surrounded by several gigantic data centers just across the street from the IXP.

This concrete geography to the digital world encapsulates an arrangement that benefits both the networks and the web companies. The website will have incremental speed enhancements (by reducing the travel distance for these sites) across all the networks it is peered with at the IXP, while the network will have
improved performance for its customers when they visit the most popular websites.

                   Across the Oceans

Eventually, international Internet communication will need to travel underwater.
The amount of undersea fiber optic cable is quite staggering and is growing yearly.
As can be seen in Figure 1.24, over 250 undersea fiber optic cable systems operated by a variety of different companies span the globe.

For places not serviced by under sea cable (such as Antarctica, much of the Canadian Arctic islands, and other small islands throughout the world), Internet connectivity is provided by orbiting satellites. It should be noted that satellite links (which have smaller bandwidth in comparison to fiber optic) account for an exceptionally small percentage of oversea Internet communication.

Resources

1. Fundamentals of Web Development by Randy Connolly, Ricardo Hoar
2. How Does the Internet Work? - Stanford University
3. How does the Internet work?
4. Internet Basics - What is the Internet?
5. 
   
6. Advanced Networking | Internet2
7.  

Fundamental Data Structures

                              Introduction

The modern digital computer was invented and intended as a device that should facilitate and speed up complicated and time-consuming computations. In the majority of applications its capability to store and access large amounts of information plays the dominant part and is considered to be its primary characteristic, and its ability to compute, i.e., to calculate, to perform arithmetic, has in many cases become almost irrelevant.

In all these cases, the large amount of information that is to be processed in some sense represents an abstraction of a part of reality(aka a model).

• The information that is available to the computer consists of a selected set of data about the actual problem, namely that set that is considered relevant to the problem at hand, that set from which it is believed that the desired results can be derived. 
• The data represent an abstraction of reality in the sense that certain properties and characteristics of the real objects are ignored because they are peripheral and irrelevant to the particular problem. 
• An abstraction is thereby also a simplification of facts.

We may regard a personnel file of an employer as an example. Every employee is represented (abstracted) on this file by a set of data relevant either to the employer or to his accounting procedures.

• This set may include some identification of the employee, for example, his or her name and salary. But it will most probably not include irrelevant data such as the hair color, weight, and height.
• In solving a problem with or without a computer it is necessary to choose an abstraction of reality, i.e., to define a set of data that is to represent the real situation. This choice must be guided by the problem to be solved. 
• Then follows a choice of representation of this information. This choice is guided by the tool that is to solve the problem, i.e., by the facilities offered by the computer. In most cases these two steps are not entirely separable.
• The choice of representation of data is often a fairly difficult one, and it is not uniquely determined by the facilities available. It must always be taken in the light of the operations that are to be performed on the data. 
• A good example is the representation of numbers, which are themselves abstractions of properties of objects to be characterized. If addition is the only (or at least the dominant) operation to be performed, then a good way to represent the number n is to write n strokes. The addition rule on this representation is indeed very obvious and simple. The Roman numerals are based on the same principle of simplicity, and the adding rules are similarly straightforward for small numbers. On the other hand, the representation by Arabic numerals requires rules that are far from obvious (for small numbers) and they must be memorized.
• However, the situation is reversed when we consider either addition of large numbers or multiplication and division. The decomposition of these operations into simpler ones is much easier in the case of representation by Arabic numerals because of their systematic structuring principle that is based on positional weight of the digits.
• It is generally known that computers use an internal representation based on binary digits (bits). This representation is unsuitable for human beings because of the usually large number of digits involved, but it is most suitable for electronic circuits because the two values 0 and 1 can be represented conveniently and reliably by the presence or absence of electric currents, electric charge, or magnetic fields.

From this example we can also see that the question of representation often transcends several levels of detail. Given the problem of representing, say, the position of an object,

• The first decision may lead to the choice of a pair of real numbers in, say, either Cartesian or polar coordinates. 
• The second decision may lead to a floating-point representation, where every real number x consists of a pair of integers denoting a fraction f and an exponent e to a certain base (such that x = f×2^e). 
• The third decision, based on the knowledge that the data are to be stored in a computer, may lead to a binary, positional representation of integers, and 
• the final decision could be to represent binary digits by the electric charge in a semiconductor storage device.

Evidently, the first decision in this chain is mainly influenced by the problem situation, and the later ones are progressively dependent on the tool and its technology. Thus, it can hardly be required
that a programmer decide on the number representation to be employed, or even on the storage device characteristics. These lower-level decisions can be left to the designers of computer equipment, who have the most information available on current technology with which to make a sensible choice that will be
acceptable for all (or almost all) applications where numbers play a role.

In this context, the significance of programming languages becomes apparent.

A programming language represents an abstract computer capable of interpreting the terms used in this language, which may embody a certain level of abstraction from the objects used by the actual machine. Thus, the programmer who uses such a higher-level language will be freed (and barred) from questions of number representation, if the number is an elementary object in the realm of this language.

The importance of using a language that offers a convenient set of basic abstractions common to most problems of data processing lies mainly in the area of reliability of the resulting programs. It is easier to design a program based on reasoning with familiar notions of numbers, sets, sequences, and repetitions
than on bits, storage units, and jumps.

1. Of course, an actual computer represents all data, whether numbers, sets, or sequences, as a large mass of bits. But this is irrelevant to the programmer as long as he or she does not have to worry about the details of representation of the chosen abstractions, and as long as he or she can rest assured that the corresponding representation chosen by the computer (or compiler) is reasonable for the stated purposes.
2. The closer the abstractions are to a given computer, the easier it is to make a representation choice for the engineer or implementor of the language, and the higher is the probability that a single choice will be suitable for all (or almost all) conceivable applications. 
3. This fact sets definite limits on the degree of abstraction from a given real computer. For example, it would not make sense to include geometric objects as basic data items in a general-purpose language, since their proper representation will, because of its inherent complexity, be largely dependent on the operations to be applied to these objects. The nature and
   frequency of these operations will, however, not be known to the designer of a general-purpose language and its compiler, and any choice the designer makes may be inappropriate for some potential applications.

Here these deliberations determine the choice of notation for the description of algorithms and their data. Clearly, we wish to use familiar notions of mathematics, such as numbers, sets, sequences, and so on, rather than computer-dependent entities such as bitstrings.
But equally clearly we wish to use a notation for which efficient compilers are known to exist.
It is equally unwise to use a closely machine-oriented and machine-dependent language, as it is unhelpful to describe computer programs in an abstract notation that leaves problems of representation widely open.

The programming language Pascal had been designed in an attempt to find a compromise between these extremes, and the successor languages Modula-2 and Oberon are the result of decades of experience [1-3]. Oberon retains Pascal's basic concepts and incorporates some improvements and some extensions. It has been successfully implemented on several computers, and it has been shown that the notation is sufficiently close to real machines that the chosen features and their representations can be clearly explained. The language is also sufficiently close to other languages, and hence the lessons taught here may equally well be applied in their use.


                      The Concept of Data Type

In mathematics it is customary to classify variables according to certain important characteristics. Clear distinctions are made between real, complex, and logical variables or between variables representing individual values, or sets of values, or sets of sets, or between functions, functionals, sets of functions, and so on.
This notion of classification is equally if not more important in data processing.

We will adhere to the principle that every constant, variable, expression, or function is of a certain type. This type essentially characterizes the set of values to which a constant belongs, or which can be assumed by a variable or expression, or which can be generated by a function.

In mathematical texts the type of a variable is usually deducible from the typeface without consideration of context; this is not feasible in computer programs. Usually there is one typeface available on computer equipment (i.e., Latin letters).

The rule is therefore widely accepted that the associated type is made explicit in a declaration of the constant, variable, or function, and that this declaration textually precedes the application of that constant, variable, or function. 

This rule is particularly sensible if one considers the fact that a compiler has to make a choice of representation of the object within the store of a computer.
Evidently, the amount of storage allocated to a variable will have to be chosen according to the size of the range of values that the variable may assume. If this information is known to a compiler, so-called dynamic storage allocation can be avoided. This is very often the key to an efficient realization of an algorithm.

The primary characteristics of the concept of type that is also  embodied in the programming language Oberon, are the following [1-2]:

1. A data type determines the set of values to which a constant belongs, or which may be assumed by a variable or an expression, or which may be generated by an operator or a function.
2. The type of a value denoted by a constant, variable, or expression may be derived from its form or its declaration without the necessity of executing the computational process.
3. Each operator or function expects arguments of a fixed type and yields a result of a fixed type. If an operator admits arguments of several types (e.g., + is used for addition of both integers and real numbers), then the type of the result can be determined from specific language rules.

As a consequence, a compiler may use this information on types to check the legality of various constructs.
For example, the mistaken assignment of a Boolean (logical) value to an arithmetic variable may be detected without executing the program.

This kind of redundancy in the program text is extremely useful as an aid in the development of programs, and it must be considered as the primary advantage of good high-level languages over machine code (or symbolic assembly code). 

Evidently, the data will ultimately be represented by a large number of binary digits, irrespective of whether or not the program had initially been conceived in a high-level language using the concept of type or in a typeless assembly code.

To the computer, the store is a homogeneous mass of bits without apparent structure. But it is exactly this abstract structure which alone is enabling human programmers to recognize meaning in the  monotonous landscape of a computer store.

The theory presented here and the programming language Oberon specify certain methods of defining data types.

1. In most cases new data types are defined in terms of previously defined data types. Values of such a type are usually conglomerates of component values of the previously defined constituent types, and they are said to be structured. 
2. If there is only one constituent type, that is, if all components are of the same constituent type, then it is known as the base type. 
3. The number of distinct values belonging to a type T is called its cardinality. The cardinality provides a measure for the amount of storage needed to represent a variable x of the type T, denoted by x: T.
4. Since constituent types may again be structured, entire hierarchies of structures may be built up, but, obviously, the ultimate components of a structure are atomic. Therefore, it is necessary that a notation is provided to introduce such primitive, unstructured types as well. 
5. A straightforward method is that of enumerating the values that are to constitute the type. For example in a program concerned with plane geometric figures, we may introduce a primitive type called shape, whose values may be denoted by the identifiers rectangle, square, ellipse, circle. 
6. But apart from such programmer-defined types, there will have to be some standard, predefined types. They usually include numbers and logical values. 
7. If an ordering exists among the individual values, then the type is said to be ordered or scalar. In Oberon, all unstructured types are ordered; in the case of explicit enumeration, the values are assumed to be ordered by their enumeration sequence.

With this tool in hand, it is possible to define primitive types and to build conglomerates, structured types up to an arbitrary degree of nesting. In practice, it is not sufficient to have only one general method of combining constituent types into a structure. With due regard to practical problems of representation and use, a general-purpose programming language must offer several methods of structuring.

In a mathematical sense, they are equivalent; they differ in the operators available to select components of these structures.

The basic structuring methods presented here are the

• array, 
• the record, 
• the set, and 
• the sequence.

More complicated structures are not usually defined as static types, but are instead dynamically generated during the execution of the program, when they may vary in size and shape.
Such structures include

• lists, 
• rings, 
• trees, and 
• general, finite graphs.

Variables and data types are introduced in a program in order to be used for computation. To this end, a set of operators must be available.
For each standard data type a programming language offers a certain set of primitive, standard operators, and likewise with each structuring method a distinct operation and notation
for selecting a component.

The task of composition of operations is often considered the heart of the art of programming. However, it will become evident that the appropriate composition of data is equally fundamental and essential.

The most important basic operators are

1. comparison and 
2. assignment,

i.e., the test for equality (and for order in the case of ordered types), and the command to enforce equality.
The fundamental difference between these two operations is emphasized by the clear distinction in their denotation throughout this text.

Test for equality: x=y (an expression with value TRUE or FALSE)
Assignment to x: x := y (a statement making x equal to y)

These fundamental operators are defined for most data types, but it should be noted that their execution may involve a substantial amount of computational effort, if the data are large and highly structured.

For the standard primitive data types, we postulate not only the availability of assignment and comparison, but also a set of operators to create (compute) new values.
Thus we introduce the standard operations of arithmetic for numeric types and the elementary operators of propositional logic for logical values.

                     Primitive Data Types

A new, primitive type is definable by enumerating the distinct values belonging to it. Such a type is called an enumeration type. Its definition has the form

TYPE T = (c1, c2, ... , cn)

T is the new type identifier, and the ci are the new constant identifiers.

Examples

TYPE shape = (rectangle, square, ellipse, circle)
TYPE color = (red, yellow, green)
TYPE sex = (male, female)
TYPE weekday = (Monday, Tuesday, Wednesday, Thursday, Friday,
Saturday, Sunday)
TYPE currency = (franc, mark, pound, dollar, shilling, lira, guilder,
krone, ruble, cruzeiro, yen)
TYPE destination = (hell, purgatory, heaven)
TYPE vehicle = (train, bus, automobile, boat, airplane)
TYPE rank = (private, corporal, sergeant, lieutenant, captain, major,
colonel, general)
TYPE object = (constant, type, variable, procedure, module)
TYPE structure = (array, record, set, sequence)
TYPE condition = (manual, unloaded, parity, skew)

The definition of such types introduces not only a new type identifier, but at the same time the set of identifiers denoting the values of the new type.
These identifiers may then be used as constants throughout the program, and they enhance its understandability considerably. If, as an example, we introduce variables s, d, r, and b.

VAR s: sex
VAR d: weekday
VAR r: rank

then the following assignment statements are possible:

s := male
d := Sunday
r := major
b := TRUE

Evidently, they are considerably more informative than their counterparts

s := 1 d := 7 r := 6 b := 2

which are based on the assumption that c, d, r, and b are defined as integers and that the constants are mapped onto the natural numbers in the order of their enumeration.
Furthermore, a compiler can check against the inconsistent use of operators. For example, given the declaration of s above, the statement

s := s+1 

would be meaningless.
If, however, we recall that enumerations are ordered, then it is sensible to introduce operators that generate the successor and predecessor of their argument. We therefore postulate the following standard operators, which assign to their argument its successor and predecessor respectively:

INC(x)
DEC(x)

                  Standard Primitive Types

Standard primitive types are those types that are available on most computers as built-in features.
They include

• the whole numbers, 
• the logical truth values, and 
• a set of printable characters.
• On many computers fractional numbers are also incorporated, together with the standard arithmetic operations.

We denote these types by the identifiers

INTEGER, REAL, BOOLEAN, CHAR, SET

                            Integer types

The type INTEGER comprises a subset of the whole numbers whose size may vary among individual computer systems.

1. If a computer uses n bits to represent an integer in two's complement notation, then the admissible values x must satisfy -2^n-1 <= x < 2^n-1. 
2. It is assumed that all operations on data of this type are exact and correspond to the ordinary laws of arithmetic, and that the computation will be interrupted in the case of a result lying outside the representable subset. This event is called overflow. 
3. The standard operators are the four basic arithmetic operations of addition (+), subtraction (-), multiplication (*), and division (/, DIV).
4. Whereas the slash denotes ordinary division resulting in a value of type REAL, the operator DIV denotes integer division resulting in a value of type INTEGER. If we define the quotient q = m DIV n and the remainder r = m MOD n, the following relations hold, assuming n > 0: q*n + r = m and 0 <= r

Examples:

 31 DIV 10 = 3           31 MOD 10 = 1
-31 DIV 10 = -4         -31 MOD 10 = 9

We know that dividing by 10^n can be achieved by merely shifting the decimal digits n places to the right and thereby ignoring the lost digits.
The same method applies, if numbers are represented in binary instead of decimal form.
If two's complement representation is used (as in practically all modern computers), then the shifts implement a division as defined by the above DIV operation. Moderately sophisticated compilers
will therefore represent an operation of the form m DIV 2^n or m MOD 2n by a fast shift (or mask) operation.

                                The type REAL

The type REAL denotes a subset of the real numbers.

Whereas arithmetic with operands of the types INTEGER is assumed to yield exact results, arithmetic on values of type REAL is permitted to be inaccurate within the limits of round-off errors caused by computation on a finite number of digits. This is the principal reason for the explicit distinction between the types INTEGER and REAL, as it is made in most programming languages.

The standard operators are the four basic arithmetic operations of
addition (+), subtraction (-),multiplication (*), and division (/).

It is an essence of data typing that different types are incompatible under assignment. An exception to this rule is made for assignment of integer values to real variables,because here the semanitcs are unambiguous. After all, integers form a subset of real numbers.

However, the inverse direction is not permissible: Assignment of a real value to an integer variable requires an operation such as truncation or rounding. 

The standard transfer function Entier(x) yields the integral part of
x.
Rounding of x is obtained by Entier(x + 0.5).

Many programming languages do not include an exponentiation operator. The following is an algorithm for the fast computation of y = x^n, where n is a non-negative integer.

y := 1.0;
i := n;
WHILE i > 0 DO (* x0^n = x^i * y *)
  IF ODD(i) THEN
    y := y*x
  END ;
  x := x*x;
  i := i DIV 2
END



[to be continued...]

Donald Knuth

When I was younger prof. Donald Knuth was(and is) one of my idols. An interesting article about a myth in our field. By the way that blog is dedicated to him as well