# Numb3rs 505: Scan Man

In this episode, Charlie, Don and the FBI team are trying to stop a series of truck heists. Seemingly random shipping trucks are stolen along with all of the parcels on board.

The episode begins with Charlie's arrival at FBI headquarters as Larry and Amita are trying to pinpoint the location of the next heist. The two are using error correcting codes to do this and Charlie seems skeptical that this method will work. Sure enough, Larry and Amita's attempts fail. However, Charlie soon figures out that understanding the bar codes on the packages is the key to solving the case.

After Charlie's realization, the FBI team goes to the shipping company that is the victim of the heists and finds Emmerson, an autistic young man with savant capabilities. Among other things, Emmerson has the amazing ability to reconstruct damaged bar codes just by looking at them. Learning of Emmerson's abilities and about his relation to various suspects leads the team toward solving the crime. The last piece of the puzzle falls into place when Charlie, Larry and Amita use fractal analysis to fully understand the locations of the stolen shipping trucks.

Let's take a closer look at some of the math that appears in this episode!

## Error Correction

Though error correcting codes aren't all that helpful for stopping the truck heists, error detection and correction is an interesting and important topic that arises in all sorts of places. For example, cellular phones and cd players make use of error correcting techniques.

In the episode, the technicians filling in for Emmerson use a type of error correction software to reconstruct damaged bar codes. One technique used in software like this is known as Reed-Soloman error correction.

So... what is error detection and correction?

Here's the general idea:

Suppose you have some information that you wish to transmit. In order to do this, you encode your data using a sequence of numbers. However, you know that there is a chance that this encoded data could get damaged. Damaged encoded data translates back to erroneous information. In order to avoid this problem, error detection and correction techniques are used. The original data is translated into a sequence of numbers in a special way (adding redundant information) so that any errors that arise in the sequence can be detected and then corrected based on the remaining numbers. The procedures or "algorithms" for encoding the information so that errors can be detected and corrected are known as error correcting codes.

There are many different error correcting codes and different codes rely on different mathematical ideas. The following activity introduces one of the most basic error detection techniques, parity bit error detection. This technique does not provide enough information for error correction. Instead, if an error is detected, the original data must be encoded and transmitted again.

Activity 1: Parity Bit Error Detection
Suppose you have some data that is encoded by a sequence of 0s and 1s (ex: 0100111). When this data is transmitted, it is possible that a 0 could be swapped for a 1 or vice versa. In order to check to see if this has happened, an extra digit (or bit) is appended to the beginning of the sequence in the following way:
If the number of 1s in the sequence is odd then a 0 is appended to the beginning. Otherwise, a 1 is appended.
For example, if we wish to transmit 0100111 using parity bit error detection, we should send the string 10100111.
This extra digit added on to the beginning of the sequence is known as an odd parity bit. Similarly, there is an even parity bit. (In this case, if the number of 1s in the original sequence is even then a 0 is appended to the beginning. If the number of 1s is odd then a 1 is appended.)
1. Suppose you receive the sequence 1001110 and an odd parity bit has been used. Has an error occurred in transmission? If so, is it possible to know how many? Are you able to determine any of their locations in the string of numbers?
2. Suppose that you again receive 1001110 but this time an even parity bit has been used. Can you know for sure that an error has not occurred? Explain.
3. Using your answers to the above two exercises, explain why parity bit error detection is not always reliable. In which situations can it be trusted? Finally, explain why this technique can't be used for error correction.

Before ending this very brief introduction, note that the study and development of error correction and detection techniques comes under the subject of Coding Theory. This is not to be confused with Cryptography, the study of code making and breaking.

1. http://mathworld.wolfram.com/Error-CorrectingCode.html
2. http://en.wikipedia.org/wiki/Error_correcting_codes
3. http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/ecc.html (This site is somewhat more advanced.)

## Bar Codes

Bar codes play a central role in this episode of Numb3rs. They are also ubiquitous in daily life. Though there are many different types of bar codes, let's focus our attention on UPC (universal product code) symbols and see how they work. UPC symbols are the modern bar codes that can be found on many of the products that we purchase. For the remainder of this section, "bar code" will mean UPC symbol.

UPC symbols were first used in grocery stores in order to help keep track of inventory as well as speed up the checkout process.

Bar codes are a way of encoding information. This is done by specifying both the width and spacing of the bars as well as the number at the bottom of the bar code. The bars correspond to a sequence of digits from 0 to 9. Each digit is represented by two bars and two spaces. On the right (respectively left) half of the bar code, each digit is represented by bars and spaces in a unique way. However, the bars and spaces encoding a given digit on the left half of the bar code look different from those encoding the same digit on the right half. The string of five numbers at the bottom of the left hand side of the bar code is the product manufacturer code. The five numbers at the bottom of the right half of the bar code is the product code. Other components of the UPC symbol include two taller, thin vertical lines on the left end, center and right end of the bar code (known as "guard patterns") as well as a single digit on either end of the bar code. The guard patterns don't encode any information. Rather, they indicate the start, center and end of the bar code. The single digit on the left end is the "number system digit" which indicates product type. The single digit on the right end is used as a way to check if the bar code has been scanned properly. The above is an example of a UPC symbol. The image is from this site.

1. http://educ.queensu.ca/~compsci/units/encoding/barcodes/barcode.html
2. http://www.howstuffworks.com/upc.htm
3. http://en.wikipedia.org/wiki/Barcode

## Fractals

Using fractals, Charlie is able to understand the locations of the stolen shipping trucks and thus help the FBI team solve the crime. Below we will discuss some of the basics of fractals and give a few examples. You are encouraged to try out the activities!

There are a number of animations on the internet which illustrate what happens when you "zoom in" on different fractals. Try typing "fractal zoom" into your favorite search engine and see what comes up.

Wolfram Mathworld defines a fractal as "an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales". An object is self-similar at different scales if it can be split up into pieces such that each piece looks approximately like a smaller copy of the whole object. Each of these smaller pieces are then self-similar as well.

In order to get a better understanding of fractals, let's look at some examples. Please note that all images below are taken from Wikipedia.

### Example 1: The Cantor Set

Start with the closed interval [0,1] (i.e. all points on the line between 0 and 1 inclusive). Remove the open middle third of this segment leaving the closed intervals [0,1/3] and [2/3,1]. Now remove the open middle third of each of [0,1/3] and [2/3,1]. This leaves four closed intervals. Continue this process of removing the open middle third from each remaining interval ad infinitum. The set of points which are never removed is known as the Cantor set.

The following is a picture of the first few stages of construction. Can you see why the Cantor set is a fractal? ### Example 2: The Mandelbrot Set ### Example 3: The Sierpinski Triangle

The construction of the Sierpinski triangle resembles that of the Cantor set. Below is a picture of the first few stages of the construction. Can you write down a rule that describes how to get from one stage to the next? Activity 2: The Koch Snowflake

To construct a Koch snowflake, begin with an equilateral triangle of total length 1. Let this triangle be stage 0 in the construction of the Koch snowflake. Define stage n to be the shape obtained by doing the following: Divide each line segment in stage n-1 into three pieces of equal length. Leave the first and third piece of each segment as is. Let the second piece become the base of an equilateral triangle pointing outwards. Erase the base of each of the new small triangles so that the new shape (i.e. stage n) has no interior lines.

Note that stage 1 looks like a six pointed "Star of David".

1. Draw the first three stages in the construction of the Koch snowflake. Explain why the Koch snowflake is a fractal.
2. What is the length at stage 1,2,3? What is the length at stage n?
3. Use your answer to 2. to deduce that the total length of the Koch snowflake is infinite.
4. What is the area in the plane that is enclosed by stage 1,2,3? Can you come up with an expression for the area enclosed at stage n?
5. (For those familiar with infinite series.) Notice that the area enclosed by the Koch snowflake is finite even though its perimeter (i.e. the total length of the Koch snowflake) is infinite.
Activity 3: Real World Fractals?
What is an example of something in the real world that has similarities to a (mathematical) fractal? How is it similar? How is it different? (Recall that a fractal must be self-similar at all scales, no matter how small the scale.)

Here are a couple of online references about fractals:

1. http://mathworld.wolfram.com/Fractal.html
2. http://en.wikipedia.org/wiki/Fractal#Examples