ECEN 1200 - Telecommunications 1

Peter Mathys, Fall 2006, 9/22/06


Homework/Computer Lab 4: Algorithms, Digital, Binary, and the "Stuff" From Which Computers are Made


How to Submit Solutions for this Homework/Computer Lab
Due Date: Friday 9-29-06
E-mail To: no-spam e-mail
Subject Line: HWCL 04
1'st Line: Your name and student number

This computer lab is written for Windows 9x/2000/NT/XT based PCs, with a Mozilla/Firefox Browser or an Internet Explorer. Those portions of the lab that are not platform-specific can also be run on a Mac.

Quick Links


Goals of this Lab

The goals of this computer lab are:


Computer Hardware

Everything in a computer that is tangible is hardware. The most important hardware items that make up a modern digital computer system are:

The term "hardware" is also used to distinguish the fixed parts of a system from the more changeable software or data components.


Computer Software

Computer systems are very flexible and can be used for many different tasks because their hardware is controlled by programs which are called software. As opposed to hardware, software is not tangible (even though it often comes on a tangible medium, like a floppy disk, a CD, or a DVD) and can be changed or updated quite easily. Making an analogy with music, hardware is the musical instrument, e.g., a piano or a guitar, and software is the score that specifies a tune to be played on the instrument. There are two major categories of software, operating system (OS) software (or firmware) and application software.

Operating system software controls the allocation and usage of the computer hardware, e.g., for sharing resources such as memory, CPU time and disk space among several users and/or processes. It also performs certain housekeeping functions like maintaining the time and the date. Popular operating systems include:

Application software are programs which are designed to assist in the performance of a specific task on a computer system. Examples are:


Information Flow Model

The block diagram of a general purpose digital computer looks as follows:

Block Diagram of a General Purpose Computer

The information flow model associated with this block diagram distinguishes between four types of activities, each of which usually requires a specific type of hardware. Before any information can be processed, it needs to be input into the computer system, e.g., via a keyboard, a microphone, a network connection, etc. The next step is to store the information, either in RAM for short term storage, or on a hard drive or similar medium for long term storage. After that the information can be processed, usually by the CPU. To complete the information flow, the processed data needs to be output, e.g., to a monitor, a printer, a network connection, sound card and speakers, etc. In addition, hardware support in the form of a power supply, a case, etc, is needed to run the circuitry associated with the above information flow operations.


Algorithms

One of the main features of a modern digital computer is that it can follow a given sequence of instructions precisely, quickly, and in the right order to accomplish some task. An algorithm is a well-defined finite sequence of operations for solving a logical or mathematical problem. A well-behaved algorithm contains rules not only for the "normal" sequence of operations, but also for the handling of special events. It should have no infinite loops or deadlocks and should terminate within a finite amount of time. An example of a deadlock and an example of an infinite loop are shown in the following "Get Up" procedure.

Algorithms: Get Up

Algorithms: Deadlock

Algorithms: Infinite Loop

Digital Versus Analog

Early computers, mechanical and electromechanical in the 1930's, and electronic (using vacuum tubes) starting in the 1940's, were actually analog, i.e., they operated on continuous-time (CT) signals with continuous amplitudes. They were used extensively to simulate and analyze structural vibration problems for the design of airplanes and missiles (e.g., during WWII 1939-1945). But starting in the early 1950's the digital computer began to take over, with a brief culminating overlap between analog and digital during the 1960's when hybrid computers flourished. A modern successor to analog computers is the neural network, a type of artificial intelligence system modeled after the neurons (nerve cells) in biological systems which process analog signals. The following graph shows an example of an analog signal.

Analog signal with continuous time and amplitude

The word digital means "Of, relating to, or resembling a digit, especially a finger". You probably learnt counting initially by counting the fingers ("digits") on your hand and/or feet. And that captures the essence of digital, namely the fact that a digital quantity is countable. For instance, the letters in the English alphabet are countable. A digital clock counts time in fixed increments, e.g., in minutes or in seconds. But time itself is not a countable quantity. How is one hour, for instance, defined? Originally as one 24-th of a day (e.g., measured from noon to noon determined by the position of the sun). But for many purposes an increment of one hour is too coarse. Thus, an hour is subdivided into 3600 seconds. But that is still not good enough to measure the times of competing runners, for example. So time is further divided into tenths and hundreths of a second, etc. It is this ability to further subdivide a quantity infinitely many times that identifies it as an analog quantity. Other measures that have this property and are thus inherently analog are distance, weight, speed, and volume. The English alphabet, on the other hand, doesn't have this infinite subdivsion property, and thus letters are digital quantities. So are the integers ...,-1,0,1,2,3,..., even though there are infinitely many of them. But they can be counted, and the interval between 0 and 1 cannot be further subdivided into integers because 1/2, for instance, is a rational number and not an integer. But be careful, 1 pound of flour, for instance, is not a digital quantity despite the fact that the integer 1 is a digital quantity. The reason for this is that weight is an analog quantity that can be subdivided infinitely many times. An example of a digital signal, obtained from an analog signal (shown dotted in blue) by subdividing time and amplitude into discrete intervals, is shown in the following graph.

Digital signal with discrete time and amplitude

Binary Data and Number Representation

Almost all modern digital computers use binary numbers such as 101110100010110 to represent and store data and instructions. Each binary digit, called bit, can only take on one of two values, either 0 or 1. This has advantages when building hardware for storage, processing and communications, since only two states need to be distinguished for each variable, e.g., as low and high voltage, or as negative and positive voltage. In contrast, an analog computer would use a continuum of values for each variable, and even small amounts of noise would lead to errors, whereas a fair amount of noise can be tolerated by binary signals.

The binary outcomes of 0 and 1 can be interpreted either numerically as the integers 0 and 1, or logically as false/no (0) or true/yes (1). The latter interpretation leads to a method by which any object can be uniquely identified and represented by a string of bits. The methods works (similar to the game of 20 questions) by asking a structured series of questions that are answered as either true (yes) or false (no). For each 'true' a 1 is added to the string that represents the object, and for each 'false' a zero is added.

Example: It is desired to represent each of the following basic 16 colors by a binary string (this is independent of and different from the '#xxxxxx' hex values of the colors).

By Color Name By Hex Value
  black #000000  
  silver #C0C0C0  
  gray #808080  
  white #FFFFFF  
  maroon #800000  
  red #FF0000  
  purple #800080  
  magenta #FF00FF  
  green #008000  
  lime #00FF00  
  olive #808000  
  yellow #FFFF00  
  navy #000080  
  blue #0000FF  
  teal #008080  
  cyan #00FFFF  

One way to identify the colors is as dark or light, with white at the extreme end of 'light' and black at the extreme end of 'dark'. Another way to describe colors is to identify them as either warm colors or cool colors. Red, brown, orange and yellow would be considered 'warm' colors, whereas cyan, blue, green and teal are 'cool' colors. Each color can be classified as either 'dark' or 'light' and, independently, as either 'warm' or 'cool'. This leads to a subdivision of all colors into 4 sets as shown in the following figure.

Arrangement for easy query of 16 basic colors

According to the figure cyan, for example, is a 'light' and 'cool' color and maroon, as another example, is a 'dark' and 'warm' color. The 'dark' and 'warm' colors can be further subdivided into 'reddish' and 'non-reddish' colors and the 'dark' and 'cool' colors can be subdivided into 'bluish' and 'non-bluish' colors. Similar subdivisions can be made for the 'light' colors. This is shown in the following color query tree figure.

Color query tree and binary representation for 16 basic colors

This works as follows. Another person picks one of the 16 colors at random. You first ask the question "Is the color light?" Suppose the answer is true(1). Then you ask "Is the color cool?". Suppose you get the answer false(0). Now you ask "Is the color reddish?". Suppose the answer is true(1). You ask "Is the color red?". Suppose the answer is false(0). Thus, the color which the other person picked has binary representation 1010 which corresponds to the color magenta. Note that in the case of the color queries the first two questions are always the same, but the last two questions depend on the answers received previously.


Where to Find More Information

Whenever you deal with computers, whether you are a beginner or an expert, you are likely to come across acronyms and terminology that you haven't seen before. Thus, it is important to know sources where this information can be looked up. The following lists should give you a good starting point to either see more explanations, or show you available products, or help you select between similar products.

Explanations about Computers and Computer Terms:

Computer Shops and Mail Order Businesses:

Price and Product Comparisons:


Manufacturer's Support Sites:

Hard Drives
CMS http://www.cmsproducts.com/product_harddrive_desktop.htm Desktop Hard Disks, and http://www.cmsproducts.com/guide/index.cfm Notebook Hard Drive Upgrades.
Fujitsu http://www.fcpa.fujitsu.com/support/hard-drives Support and Downloads for Hard Drives.
Hitachi, IBM http://www.hitachigst.com/portal/site/hgst Hitachi Global Storage Technologies.
Maxtor, Quantum http://www.maxtor.com
Seagate http://www.seagate.com/support/disc/index.html Seagate Disc Technical Support Index.
Toshiba http://sdd.toshiba.com Hard Drives and Optical Drives.
Western Digital http://support.wdc.com Western Digital Service and Support.


Motherboards and CPU Support
AMD http://www.amd.com/us-en AMD Worldwide.
AnandTech http://http://www.anandtech.com/mb Motherboard Articles.
Intel http://www.intel.com/sites/support/index.htm Support and Downloads
Motherboards.com http://www.motherboards.com
Tyan http://www.tyan.com/products/html/systemboards.html Tyan System Boards


Video Cards
3DLabs http://www.3dlabs.com
ATI http://www.ati.com/products Innovative Visual Technology Products.
Matrox http://http://www.matrox.com/mga/support/home.cfm Graphics Card Support System.
Mirage http://http://www.mirage-mmc.com/ftp/Video_Card.html Mirage Video Card Support.
NVidia http://http://www.nvidia.com/content/drivers/drivers.asp NVidia Software Download Page.
S3 Graphics http://www.s3graphics.com
SiS http://www.sis.com/support/index.htm Support Links for SiS Chipsets.



Selecting the Parts for a Tailored System

To gain some knowledge about the parts of a computer system, assume that you are going to build a Writer's PC from parts that can be bought in computer stores or via mail order. The detailed assumptions about this tailored desktop computer system are as follows.

Assumptions for Writer's PC

You intend to write a book of prose, without the need for images or figures. You want to be able to research certain topics on the Internet and you need e-mail to keep in touch with your publisher and other fellow writers. You are not connected to a local area network. To access the Internet you use a regular telephone line and an Internet service provider.

If your hard drive crashes, you don't want to loose everything you wrote, so you have to make a backup of your writings and a printout every once in a while. Of course, for the writing itself, you need a word processor. You like to listen to some music while you work, so you you want to have an audio output and speakers.

Here is a list of parts that can be used to put together a computer system for these needs. But there are also extra items in the list that you do not need. And just to make things a little more interesting, at least two items that you do need are not included in the list.


Your Task

To obtain credit for this homework/computer lab you need to answer the questions stated below. Send your solution to no-spam e-mail.

Rules for the Submission of Homework/Computerlab Solutions

Format: E-mail your solution as a plain text (ASCII) file. Do not use word processor files like Microsoft Word or "rich-text" HTML files.

Corrections: If you need to make corrections after you submitted your solution, resubmit all your answers (not only the ones that changed) since only your last submission of each homework/computer lab will be graded.

Teamwork: Teamwork is fine for the homework/computer labs, but the solutions must be turned in individually. In particular, copy and paste of entire solutions from other students is not acceptable.

Questions:

  1. Note: Make use of the resources listed above to answer the following questions.
    1. How wide (in bits) are the (externally accessible) address and data bus of a modern CPU (e.g., Pentium)?
    2. What rotates inside a hard drive, and what are typical rotating speeds for it?
    3. If you buy RAM (DDR, SDRAM, etc), what is the approximate cost per Gigabyte? How does that compare with the approximate cost per Gigabyte of storage on a Hard Drive?
  2. The two slides below show the "Go to Work" procedure and the "Replace x" procedure which is invoked whenever something breaks and needs fixing. Identify at least one potential deadlock and one potential infinite loop.

    Go to Work Procedure

    Replace x Procedure

  3. Classify the follwing quantities as either digital or analog:
    1. Position of the small hand on a (mechanical) clock.
    2. The letters of the English alphabet.
    3. One gallon of milk.
    4. The price you pay for one gallon of milk.
    5. The distance between the earth and the sun.
  4. Consider the following set of 16 objects: The answers (true(1) or false(0)) to the following 4 questions (in the given order) are used to assign a unique 4-bit representation to each of the above objects:
    1. Is the object alive?
    2. Is the object big?
    3. Is the object wet?
    4. Is the object soft?
    1. Question: What is the binary representation of the object 'Goldfish'? Hint: A goldfish has no shell like a mussel and thus is not hard.
    2. Question: What is the name of the object with the binary representation 0101?
  5. For each of the items in the list given earlier, determine whether it is software or hardware. For each hardware item determine also whether it is used for input, output, processing, storage/memory, or support in terms of the information flow model.
  6. Take only those items in the list above that are needed for a "Writer's PC" as described in the section Selecting the Parts for a Tailored System and find out how much each costs. Add the two items that are missing in the list. Compute the total system cost and make a Web page with an unordered list where you display all this information. Make a second list with links to the three (or more) best places where you found computer hardware and software and/or explanations of how things work in a computer. You can either use your existing homepage and add this information, or make a new HTML file, e.g., called writersPC.html, where you place this list (use the HTML skeleton in HWCL 2 as a starting point). Either way, your Web page must be accessible on the WWW (e.g., on webfiles.colorado.edu) and the URL where the Web page can be accessed must be clearly stated in your solution. Make sure that the permissions are set for public access.