Index of all Wisdom issues.
by Christine Cabreros
It was a cold and snowy day when the executive of the Computer Science Society decided to have a cider sale with gingerbread cookies on the side.
The day began with a cold gust of snow and a chill in the air that could be felt all the way to the bone. The urns that were to heat the cider arrived at approximately 8:30 am. The sale was to begin at 10:00am but because of the bitter wind and snow, the cider decided that it wanted to take a long time to even warm up.
But even with the slow warming of the cider the overall sale was pretty good and the gingerbread cookies were definitely a success. A special thanks goes out to the executive and friends who stood out in the cold, watched the students and Proffs go by, and especially to those who bought cider and cookies and who acknowledged our presence outside of Lambton Tower.
Thanks for the Support!
by Sandy Tolentino
Hey first year computer science students. Calculus got you down? Abstract math giving you the blues? Turing assignments giving you a headache?
Well if you need a quick break to relieve that stress come out to one of our computer science society events. Just look at the up coming events section in the Wisdom and find one that you would like to come to. Heck just stop by and see what's going on, you're always welcome. So if you need a break and want some fun just come on down.
Article on the Internet
The following is a nice intro to CD technology written by Andy Poggio in 1988.
This summary describes how information is encoded on Compact Disc (CD) beginning with the physical pits and going up through higher levels of data encoding to the structured multimedia information that is possible with programs like HyperCard. This discussion is much broader than any single standards document, e.g. the CD-Audio Red Book, while omitting much of the detail needed only by drive manufacturers.
Storing data on a CD may be thought of as occurring through a data encoding hierarchy with each level built upon the previous one. At the lowest level, data is physically stored as pits on the disc. It is actually encoded by several low-level mechanisms to provide high storage density and reliable data recovery. At the next level, it organized into tracks which may be digital audio or CD-ROM. The High Sierra specification then defines a file system built on CD-ROM tracks. Finally, applications like HyperCard specify a content format for files.
The Compact Disc itself is a thin plastic disk some 12 cm. in diameter. Information is encoded in a plastic-encased spiral track contained on the top of the disk. The spiral track is read optically by a non contact head which scans approximately radially as the disk spins just above it. The spiral is scanned at a constant linear velocity thus assuring a constant data rate. This requires the disc to rotate at a decreasing rate as the spiral is scanned from its beginning near the center of the disc to its end near the disc circumference.
The spiral track contains shallow depressions, called pits, in a reflective layer. Binary information is encoded by the lengths of these pits and the lengths of the areas between them, called land. During reading, a low power laser beam from the optical head is focused on the spiral layer and is reflected back into the head. Due to the optical characteristics of the plastic disc and the wavelength of light used, the quantity of reflected light varies depending on whether the beam is on land or on a pit. The modulated, reflected light is converted to a radio frequency, raw data signal by a photodetector in the optical head.
To ensure accurate recovery, the disc data must be encoded to optimize the analog-to-digital conversion process that the radio frequency signal must undergo. Goals of the low level data encoding include:
If fourteen channel bits were concatenated with another set of fourteen channel bits, once again the above goals may not be met. To avoid this possibility, three merging bits are included between each set of fourteen channel bits. These merging bits carry no information but are chosen to limit run length, keep data signal DC content low, etc. Thus, an eight bit byte of actual data is encoded into a total of seventeen channel bits: fourteen EFM bits and three merging bits. To achieve a reliable self-clocking system, periodic synchronization is necessary. Thus, data is broken up into individual frames each beginning with a synchronization pattern. Each frame also contains twenty-four data bytes, eight error correction bytes, a control and display byte (carrying the subcoding channels), and merging bits separating them all. Each frame is arranged as follows:
Sync Pattern : 24 + 3 channel bits Control and Display byte : 14 + 3 Data bytes : 12 * (14 + 3) Error Correction bytes : 4 * (14 + 3) Data bytes : 12 * (14 + 3) Error Correction bytes : 4 * (14 + 3) TOTAL : 588 channel bits Thus, 192 actual data bits (24 bytes) are encoded as 588 channel bits.
Editorial: A CD physically has a single spiral track about 3 miles long. CDs spin at about 500 RPM when reading near the center down to about 250 RPM when reading near the circumference. Disc with a `c' or disk with a `k'? A usage has emerged for these terms: disk is used for erasable disks (e.g. magnetic disks) while disc is used for read-only (e.g. CD-ROM discs). One would presumably call a frisbee a disc.
Data errors can arise from production defects in the disk itself, defects arising from subsequent damage to the disk, or jarring during reading. A significant characteristic of these errors is that they often occur in long bursts. This could be due, for example, to a relatively wide mark on the disc that is opaque to the laser beam used to read the disc. A system with two logical components called the Cross Interleave Reed-Solomon Coding (CIRC) is employed for error correction. The cross interleave component breaks up the long error bursts into many short errors; the Reed-Solomon component provides the error correction.
As each frame is read from the disc, it is first decoded from fourteen channel bits (the three merging bits are ignored) into eight-bit data bytes. Then, the bytes from each frame (twenty-four data bytes and eight error correction bytes) are passed to the first Reed-Solomon decoder which uses four of the error correction bytes and is able to correct one byte in error out of the 32. If there are no uncorrectable errors, the data is simply passed along. If there are errors, the data is marked as being in error at this stage of decoding.
The twenty-four data bytes and four remaining error correction bytes are then passed through unequal delays before going through another Reed-Solomon decoder. These unequal delays result in an interleaving of the data that spreads long error bursts among many different passes through the second decoder. The delays are such that error bursts up to 450 bytes long can be completely corrected. The second Reed-Solomon decoder uses the last four error correction bytes to correct any remaining errors in the twenty-four data bytes. At this point, the data goes through a de-interleaving process to restore the correct byte order.
The eight-bit control and display byte in each frame carries the subcoding channels. A subcoding block consists of 98 subcoding bytes, and thus 98 of the 588-bit frames. A block then can contain 2352 bytes of data. Seventy-five blocks are read each second. With this information, it is now straightforward to calculate that the CD data rate is in fact correct for CD digital audio (CD-DA):
The eight subcoding channels are labeled P through W and are encoded one bit for each channel in a control and display byte. Channel P is used as a simple music track separator. Channel Q is used for control purposes and encodes information like track number, track type, and location (minute, second, and frame number). During the lead-in track of the disc, channel Q encodes a table of contents for the disk giving track number and starting location. Standards have been proposed that would use the remaining channels for line graphics and ASCII character strings, but these are seldom used.
Tracks can have two types as specified in the control bit field of subchannel Q. The first type is CD digital audio (CD-DA) tracks. The two-channel audio is sampled at 44.1 Khz with sixteen bit linear sampling encoded as twos complement numbers. The sixteen bit samples are separated into two eight-bit bytes; the bytes from each channel alternate on the disc. Variations for audio tracks include pre-emphasis and four track recording.
The other type of track specified by the subchannel Q control bit field is the data track. These must conform to the CD-ROM standard described below. In general, a disc can have a mix of CD digital audio tracks and a CD-ROM track, but the CD-ROM track must come first.
Editorial: This first level error correction (the only type used for CD Audio data) is extremely powerful. The CD specification allows for discs to have up to 220 raw errors per second. Every one of these errors is (almost always) perfectly corrected by the CIRC scheme for a net error rate of zero. For example, our tests using Apple's CD-ROM drive (which also plays audio) show that raw error rates are around 50-100 per second these days. Of course, these are perfectly corrected, meaning that the original data is perfectly recovered. We have tested flawed discs with raw rates up to 300 per second. Net errors on all of these discs? Zero! I would expect a typical audio CD player to perform similarly. Thus I expect this raw error rate to have no audible consequences.
So why did I say "almost always" corrected above? Because a sufficiently bad flaw may produce uncorrectable errors. These very unusual errors are "concealed" by the player rather than corrected. Note that this concealment is likely to be less noticeable than even a single scratch on an LP. Such a flaw might be a really opaque finger smudge; CDs do merit careful handling. On the two (and only two) occasions I have found these, I simply sprayed on a little Windex glass cleaner and wiped it off using radial strokes. This restored the CDs to zero net errors.
One can argue about the quality of the process of conversion of analog music to and from digital representation, but in the digital domain CDs are really very, very good.
Each CD-ROM data track is divided into individually addressable blocks of 2352 data bytes, i.e. one subcoding block or 98 frames. A header in each block contains the block address and the mode of the block. The block address is identical to the encoding of minute, second, and frame number in subcode channel Q. The modes defined in the CD-ROM specification are:
Thus, mode 1 defines separately addressable, physical 2K byte data blocks making CD-ROM look at this level very similar to other digital mass storage devices.
An uncorrected error in audio data typically results in a brief, often inaudible click during listening at worst. An uncorrected error in other kinds of data, for example program code, may render a CD unusable. For this reason, CD-ROM defines a second level of error detection and error correction (EDC/ECC) for mode 1 data. The information for the EDC/ECC occupies most of the auxiliary data field.
The error detection code is a cyclic redundancy check (CRC) on the sync, header, and user data. It occupies the first four bytes of the auxiliary data field and provides a very high probability that uncorrected errors will be detected. The error correction code is essentially the same as the first level error correction in that interleaving and Reed-Solomon coding are used. It occupies the final 276 bytes of the auxiliary data field.
Editorial: This extra level of error correction for CD-ROM blocks is one of the many reasons that CD-ROM drives are much more expensive than consumer audio players. To perform this error correction quickly requires substantial extra computing power (sometimes a dedicated microprocessor) in the drive.
This is also one reason that consumer players like the Magnavoxes which claim to be CD-ROM compatible (with their digital output jack on the back) are useless for that purpose. They have no way of dealing with the CD-ROM error correction. They also have no way for a computer to tell them where to seek.
Another reason that CD-ROM drives are more expensive is that they are built to be a computer peripheral rather than a consumer device, i.e. like a combination race car/truck rather than a family sedan. One story, probably apocryphal but not far from the truth, has it that a major Japanese manufacturer tested some consumer audio players to simulate computer use: they made them seek (move the optical head) from the inside of the CD to the outside and back again. These are called maximum seeks. The story says they managed to do this for about 24 hours before they broke down. A CD-ROM drive needs to be several orders of magnitude more robust. Fast and strong don't come cheap.
Built on top of the addressable 2K blocks that the CD-ROM specification defines, the next higher level of data encoding is a file system that permits logical organization of the data on the CD. This can be a native file system like the Macintosh Hierarchical File System (HFS). Another alternative is the High Sierra (also known as the ISO 9660) file standard, recently approved by the National Information Standards Organization (NISO) and the International Standards Organization (ISO), which defines a file system carefully tuned to CD characteristics. In particular:
For High Sierra file systems, each individual CD is a volume. Several CDs may be grouped together in a volume set and there is a mechanism for subsequent volumes in a set to update preceding ones. Volumes can contain standard file structures, coded character set file structures for character encoding other than ASCII, or boot records. Boot records can contain either data or program code that may be needed by systems or applications.
The file system is a hierarchical one in which directories may contain files or other directories. Each volume has a root directory which serves as an ancestor to all other directories or files in the volume. This dictates an overall tree structure for the volume.
A typical disadvantage in hierarchical systems is that to read a file (which must be a leaf of the hierarchy tree) given its full path name, it is necessary to begin at the root directory and search through each of its ancestral directories until the entry for the file is found. For example, given the path name "Wine Regions:America:California:Mendocino", three directories (the first three components of the path name) would need to be searched. Typically, a separate seek would be required for each directory. This would result in relatively poor performance.
To avoid this, High Sierra specifies that each volume contain a path table in addition to its directories and files. The path table describes the directory hierarchy in a compact form that may be cached in computer memory for optimum performance. The path table contains entries for the volume's directories in a breadth-first order; directories with a common parent are listed in lexicographic order. Each entry contains only the location of the directory it describes, its name, and the location in the path table of its parent. This mechanism allows any directory to be accessed with only a single CD seek.
Directories contain more detailed information than the path table. Each directory entry contains:
Interleaving may be used, for example, to meet realtime requirements for multiple files whose contents must be presented simultaneously. This would happen if a file containing graphic images were interleaved with a file containing compressed sound that describes the images.
Files themselves are recorded in contiguous (or interleaved) blocks on the disc. The read-only nature of CD permits this contiguous recording in a straightforward manner. A file may also be recorded in a series of noncontiguous extents with a directory entry for each extent.
The specification does not favor any particular computer architecture. In particular all significant, multibyte numbers are recorded twice, once with the most significant byte first and once with the least significant byte first.
Using the file system are applications that create and portray multimedia information. While it is true that a CD can store anything that a magnetic disk can store (and usually much more of it), CDs will be used more for storing information than for storing programs. It is the very large storage capacity of CDs coupled with their low cost that opens up the possibilities for interactive, multimedia information to be used in a multitude of ways.
Programs like HyperCard, with it's ease of authoring and broad extensibility, are very useful for this purpose. Hypercard stacks, with related information such as color images and sound, can be easily and inexpensively stored on CDs despite their possibly very large size.
Editorial: The High Sierra file system gets its name from the location of the first meeting on it: the High Sierra Hotel at Lake Tahoe. It is much more commonly referred to as ISO 9660, though the two specifications are slightly different.
It has gotten very easy and inexpensive to make a CD-ROM disc (or audio CD). For example, you can now take a Macintosh hard disk and send it with $1500 to one of several CD pressers. They will send you back your hard disk and 100 CDs with exactly the same content as what's on your disk. This is the easy way to make CDs with capacity up to the size of your hard disk (Apple's go up to 160 megabytes). True, this is not a full CD but CDs don't need to be full. If you have just 10 megabytes and need 100 copies, CDs may be the best way to go.
If you are buying a CD-ROM drive, there are several factors you might consider in making your choice. Two factors NOT to consider are capacity and data rate. The capacity of all CD-ROM drives is determined solely by the CD they are reading. Though you will see a range of numbers in manufacturers' specs (e.g. 540, 550, 600, and 650 Mbytes), any drive can read any disc and so they are all fundamentally the same. All CD-ROM drives read data at a net 150 Kbytes/sec for CD-ROM data. Other data rates you may see may include error correction data (not included in the net rate) or may be a mode 2 data rate (faster than mode 1). All drives will be the same in all of these specs.
by Dean Scott
I'd like to extend my introduction as the new V.P. Social Affairs. After the resignation of the former V.P. Social, I was approached for this position by the executive of the C.S.S. A short meeting and a few votes later, I was in. Since I'm fairly new at this, I'll try to live up to your expectations and the precedence set by the former V.P. Social.
In the future you can expect fresh ideas, openness to suggestions and exciting, possibly adventurous, activities. Any proposals may be e-mail'ed to scott2@server or delivered to the C.S.S. office in 5108 Lambton Tower. I appreciate the opportunity of serving your needs.
The elections for the Computer Science Society executive will be held on Monday the 5th of April and Tuesday the 6th of April. Nominations open on Monday the 22nd of March and end on Friday the 26th of March. Campaigning is from Monday the 29th of March to Friday the 2nd of April.
Every full time undergrad student in Computer Science and Computer Information Systems are eligible to run for all positions except president. The position of president is open to students who will be in 3rd and 4th year in September. The positions are:
by Christine Cabreros
It began as a simple group of people getting together to watch some movies. Things began to change, subtly at first then it became apparent that something was amiss. The rain outside was making loud pattering noises as if... there were someone or something on the roof. The winds outside howled through the trees. Branches nearby were whistling and scratching at the windows. There were pizza boxes and empty pop cans littered around the room which gave a feeling of some great feast. The silence in the room was so heavy with dread that not even the students in the room could hear themselves breathing.
Suddenly, a scream escapes from a throat torn by an elvish sword. "Elf friends!!!!! Aggghh!!!!" The room was filled with a light so bright people were squinting at the TV just to find out what would happen next. It became an all out attack as the again hungry humans took out their swords, axes and other weapons to converge upon the unsuspecting pizza bearer. Without a dollar being exchanged, the pizza bearer was beheaded and the pizzas were quickly divided and more drink was consumed by the slobbering, munching ravenous creatures of the dark night. As the fighting stopped and the blood ceased to flow, the appetites of the hoards were soon forgotten.
The first of the three movies ended and thus began `The Lord of the Rings'. The crowd was a little restless because the loud Hobbitses were singing again. Edgy hands were slowly inching towards their weapons. It was unbelievable. Hobbitses constantly singing. Soon there was a misstep and the singing hobbit disappears. Now the screams of delight became screams of horror, bringing the evil riders of Sauron. The crowd was so engrossed they didn't notice the sound of slippery feet following the escape of the last piece of pizza in the hands of the thief.
At first glance into the, now, indistinguishable room, you would see dried blood and dead bodies strewn all over. But look, in the dark recess is a group of survivors hoping that the huge battle of elves, humans and hobbits against the trolls, goblins and other evil creatures will end. The battle still rages on the video screen as the two wee Hobbitses Frodo and Sam-wise move ever onward.
This time the blinding light comes from the door as an eager but humble creature calls out,"No more pizza!". Then quickly hurries out the door before the night creatures could respond in kind. The screen then goes blank. At this time, having the distressing news of no more food, the happy and not so angered humans decide to make their exit from the now foodless room to find other pleasures in the night.
Here, we start the next movie `Return of the King' with a smaller set of people. Frodo has been captured and is being tortured by an evil goblin. There's hush in the room and a raging storm outside as the ring casts its wicked spell over the bewildered Sam-wise, giving him illusions of grandeur. The pop is slowly guzzled away into the remaining watchers. Little rats scurry here and there in the hopes to finding what remains of the devouring pizza eaters meal. There are tiny squeals as a rat ventures near a seeming sleeping hand and is caught. Another war rages on as the valiant fight evil hordes of creatures. The weather outside has seemingly died down. There were no more sounds of whistling branches or of the howling winds as the sun broke through the dark mists that hovered over the silent and not so crowded room. A bard starts to sing of the battles and middle earth is safe from the grip of evil. For Frodo has destroyed the one ring with the help of the thief with the flippers for feet.
This ends the tale of the movie night as witnessed by Christine Cabreros.
[P.S. Thanks to all the students that made it out this night. It was another successful movie night. There are a lot of Tolkien fans out there. Good Luck with the Tolkien Trivia found elsewhere in the Wisdom!!!!]
If you have any ideas for a theme drop by LT 5108 and leave a suggestion with an executive or if you have any suggestions in general for activities.
The next movie night will be in March. Hope to see you there!!!!
From the Dec. `92 tournament:
The next pool tournament is on Tuesday February 23,1993 from: 3:00 pm to: 7:00pm at "Tilt" on Wyandotte & Rankin. Pick up trophies at: LT 5108. Don't forget this is a great way to meet other people in Computer Science.
C2
by: Ron McKenzie
O.K., we got a pretty good turn out at our Tolkien Movie night, but how many of you were awake enough to pay attention. We'll start off with some very easy questions then work up to the virtually impossible. The person who submits the most correct answers, will win!
by Alain Siodlowski
Well once again another issue of the Wisdom is out. As usual we're always looking for people who would like to submit articles (you get $5.00). Anyone who would like to submit an article can do so by e-mail (wisdom@cs.uwindsor.ca) or by hard copy at the office (LT 5108).
Due to the date of printing, we weren't able to get an article on the ski trip to Alpine Valley. The weather was beautiful and everyone had fun. Look for an account of what happened and for photos in the next issue!
We hope you like the article on CD ROM technology (found on the Internet). CD ROMs have been around for a while now but not many people know much about the technologyl. Many companies (like SUN) is distributing almost all of it's new software on CDs now and other companies (such as IBM, SGI, DEC etc.) are following suite.
Well, that's it for space, so bye!
wisdom@cs.uwindsor.ca