Coordinate Digits Magically Appear Mystery Cache

Code Division Multiple Access (CDMA) is a protocol for allowing multiple radios to transmit data at the same time without garbling their signals. In this area, CDMA technology is used by three local cellular phone companies: Sprint, Verizon, and Alltel.

In this cache, we will learn how to encode and decode CDMA messages.

The Basics

The first cellular telephone systems assigned a separate radio channel to each phone conversation, like a CB radio or a walkie talkie. This is called "Frequency Division Multiple Access" (FDMA). This is pretty wasteful, since there are a lot more people with cellular phones than there are radio channels. So in the 1980's, cellular companies started using a system of "time slicing" called Time Division Multiple Access (TDMA). Each phone takes turns so that no one's conversation gets interference from the others.

CDMA technology allows multple phone conversations to use the same radio frequency at the same time. The secret is in the mathematics. And the inspiration came from a beautiful actress named Hedy Lemarr.

History

In the early 1940's, Hedy Lamarr and her music composer, George Anthiel, noticed that musicians could send messages to their dancers by playing a series of notes in their songs. Even in a crowded dance studio, while several different groups were practicing, this method still worked remarkably well. Hedy and George developed this idea into a system called "frequency hopping" that could be used by the Navy to make radio-controlled torpedos harder to detect. Wow! While Hedy's invention and patents used a system of changing radio frequencies, researchers began looking into other ways to use this so-called "spread spectrum" technology. Eventually, the phone companies (namely, Qualcomm) developed a system that could be used on digital cellular phones.

Theory

Anyone who's played "name that (muzak) tune" in a restarant has noticed how easy it is to pick out a tune in spite of significant background noise. CDMA works the same way. Suppose I wanted to send a short one-letter message to someone else in a restaurant. I could go to the jukebox and pick a song that started with my letter. In fact, people are so good at picking out a tune, this would probably still work with four people in the same restaurant, playing four different songs on four different jukeboxes, all at the same time.

In our game, it takes us a long time to send a single letter on the jukebox. That's not very efficient. But what we lose in efficiency in one conversation, we make up for by allowing several conversations (tunes) in the same room at the same time.

And that's exactly how cellular phones do it. Each phone sends a lot of data that represents sounds of the speaker's voice (they send a "wideband" signal). That one phone is inefficent. But we can crowd 64 phones onto a single radio channel, and then it becomes fairly efficient, overall.

Practice - Walsh Codes

Humans are good at picking out tunes in a crowded restaurant. Computers are good at picking out patterns in digital data. So CDMA uses a set of code numbers called "Walsh codes".

Walsh Codes are specially chosen numbers that can be easily distingushed from one another using a computer. Mathematicians say that they are "orthogonal". That means that to a computer, these numbers are as easily distinguishable as Barry Manilow and Nirvana. It also means that if you compare any two Walsh Codes, half of the bits will be the same and half will be different.

The codes come from a special formula that starts with one 1-digit number. If you want larger Walsh Codes, you build them up from the smaller codes. Below is the formula, but don't worry about it. I'll compute the Walsh Codes in a minute.

Cellular phones use 64-digit Walsh Codes, which means 64 separate phones can send 64 different conversations over the same radio channel at the same time. Our puzzle only uses 4-bit Walsh Codes, because we don't have that much information to send, and because decoding such a large puzzle would take all day.

So I need four 4-digit Walsh Codes. I'll build W₂ out of four W₁'s.

And then I'll build W₄ out of four W₂'s.

This gives me the four Walsh Codes that I need to encode the messages. You will use these same Walsh Codes to decode the puzzle.

You'll notice that if you compare any of the two Walsh Codes to each other, two of the digits are the same and two of the digits are different. Orthogonal... cool.

An example - encoding

We're going to work through a simple example of encoding several messages and then combine them using CDMA.

I have chosen four messages to be sent over the air at the same time. Each message will be encoded using one of the four Walsh Codes from above.

We will work through the encoding process for message #4, "NEWS". It will be sent using the Walsh Code #4, (0 1 1 0).

1. Encode the message. To send multiple messages at the same time using CDMA, the information has to be in a digital format. We could choose any digital encoding scheme here: 7-bit ASCII would be a good choice, or 16-bit Unicode would be good, too. It really does not matter, as long as the sender and the receiver use the same encoding.

   Since we don't want to labor all day over 16-bit characters, I am going to encode all of my messages using the following table of 4-bit values:

   LETTER DIGITIZED 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111

   LETTER DIGITIZED 8 1000 9 1001 N 1010 S 1011 E 1100 W 1101 . 1110 ° 1111

   Using this table, our message "N-E-W-S" becomes 1010-1100-1101-1011. Our message of 4 letters has now become 16 bits long.

2. Expand the message using Walsh Codes. Since we are using four-bit Walsh codes, we can have four phones sending four different messages at the same time on the same radio channel.

   We have chosen to use code #4 (0 1 1 0) to expand our "NEWS" message.

   Expansion is simple. Go through each BIT of the message. If the bit is a zero, then write down our Walsh code (0 1 1 0). If the bit is a one, then write down the INVERSE of our Walsh code (1 0 0 1).

   BITS	1	0	1	0	1	1	0	0	1	1	0	1	1	0	1	1
   CHIPS	1001	0110	1001	0110	1001	1001	0110	0110	1001	1001	0110	1001	1001	0110	1001	1001

   So now each letter has been turned into four bits, and each bit has been turned into four "chips". Wow, our four-letter message is now a whopping 64 chips! Computer people say that this process expands the bandwidth of the message. This is why the terms "wideband" and "spread spectrum" are often used to describe CDMA.

3. Transmit the signal over the air. A CDMA phone transmits these chips over the air at a particlar frequency. To make the math easier, we will transmit a positive value when the chip is one, and a negative value when the chip is zero.
   
   

   Phone #4 transmits his message "N-E-W-S", encoded using Walsh Code #4 (0 1 1 0): +1, -1, -1, +1, -1, +1, +1, -1, +1, -1, -1, +1, -1, +1, +1, -1, +1, -1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, -1, +1, +1, -1, +1, -1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, +1, -1, -1, +1, +1, -1, -1, +1, -1, +1, +1, -1, +1, -1, -1, +1, +1, -1, -1, +1

   
   
4. Repeat this process for the three other signals. We have four phones, sending four independent messages. Each phone does the encoding, expanding and transmitting that we outlined above.
   
   

   Phone #1 transmits his message "3-5-7-9", encoded using Walsh Code #1 (0 0 0 0): -1, -1, -1, -1, -1, -1, -1, -1, +1, +1, +1, +1, +1, +1, +1, +1, -1, -1, -1, -1, +1, +1, +1, +1, -1, -1, -1, -1, +1, +1, +1, +1, -1, -1, -1, -1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, -1, -1, -1, -1, -1, -1, -1, -1, +1, +1, +1, +1

   
   

   Phone #2 transmits his message "2-4-6-8", encoded using Walsh Code #2 (0 1 0 1): -1, +1, -1, +1, -1, +1, -1, +1, +1, -1, +1, -1, -1, +1, -1, +1, -1, +1, -1, +1, +1, -1, +1, -1, -1, +1, -1, +1, -1, +1, -1, +1, -1, +1, -1, +1, +1, -1, +1, -1, +1, -1, +1, -1, -1, +1, -1, +1, +1, -1, +1, -1, -1, +1, -1, +1, -1, +1, -1, +1, -1, +1, -1, +1

   
   

   Phone #3 transmits his message "0-0-0-0", encoded using Walsh Code #3 (0 0 1 1): -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1, -1, -1, +1, +1

   
   
5. Combine with the other signals. In the airwaves, the signals from several transmitters are all added together, simply because they are transmitted on the same radio frequency.

   In our imaginary system, there are four transmitters using four different Walsh Codes. So the four signals combine in the air to look like this:

   -2, -2, -2, +2, -4,  0,  0,  0, +2, -2, +2, +2, -2, +2, +2, +2,
   -2, -2, -2, +2, +2, -2, +2, +2, -4,  0,  0,  0, -2, +2, +2, +2,
   -2, -2, -2, +2, +2, -2, +2, +2,  0,  0, +4,  0,  0,  0,  0, +4,
   +2, -2, +2, +2, -4,  0,  0,  0, -2, -2, -2, +2,  0,  0,  0, +4
   

   In real life, we would also add in some noise that comes from everything around us. CDMA signals are surprisingly resilient to noise interference.

An example - decoding

We will now work through the decoding process for message #4, which we know was sent using the Walsh Code #4 (0 1 1 0).

1. Correlate with the target Walsh Code. The signal that we receive over the air has four separate messages encoded in it simultaneously. Suppose we wanted to decode a single message from the stream of numbers. In this example, we want to decode message #4, which uses Walsh Code #4 (0 1 1 0).

   Look at the number sequence that we received above. Using our Walsh Code (0 1 1 0), we will go through the numbers in the message, four at a time. When we have a ONE in our Walsh Code, we will invert the number from the received message. When we have a ZERO, we will leave that number alone. Since Walsh Code #4 is (0 1 1 0), we will "leave alone, invert, invert, and leave alone".

   Below, the red numbers have been inverted.

   -2, +2, +2, +2, -4,  0,  0,  0, +2, +2, -2, +2, -2, -2, -2, +2,
   -2, +2, +2, +2, +2, +2, -2, +2, -4,  0,  0,  0, -2, -2, -2, +2,
   -2, +2, +2, +2, +2, +2, -2, +2,  0,  0, -4,  0,  0,  0,  0, +4,
   +2, +2, -2, +2, -4,  0,  0,  0, -2, +2, +2, +2,  0,  0,  0, +4
   

2. Integrate. Here, we determine whether each set of four received numbers (chips) represents a bit of ONE or ZERO.

   Add the four numbers together. If the sum is positive, the result bit is ONE. If it is negative, the result bit is ZERO.

   CHIPS	-2,+2,+2,+2	-4,0,0,0	-2,+2,+2,+2	+2,+2,-2,+2	-2,+2,+2,+2	+2,+2,-2,+2	-4,0,0,0	-2,-2,-2,+2
   SUM	+4	-4	+4	-4	+4	+4	-4	-4
   BITS	1	0	1	0	1	1	0	0

   
   

   CHIPS	-2,+2,+2,+2	+2,+2,-2,+2	0,0,-4,0	0,0,0,+4	+2,+2,-2,+2	-4,0,0,0	-2,+2,+2,+2	0,0,0,+4
   SUM	+4	+4	-4	+4	+4	-4	+4	+4
   BITS	1	1	0	1	1	0	1	1

   
   
3. Decode the message. Using the same table of character encodings from above.

   "1010-1100-1101-1011" becomes "N-E-W-S"!

Decoding the other three messages

Repeating the process using the other three Walsh Codes results in the following:

This should be no surprise, since this is exactly what we sent above.

Your turn.

Now it's your turn. Decode the following received data stream to find the cache coordinates.

+3,  0,  0,  0,  0, -1, -5, -1, -1,  0, +4, -1,  0, -4, -1, -1,
-5,  0,  0,  0,  0,  0, -4, -1, +1, -2, +1, +1, +2, +2, -2, +2,
-2, -3, -3, +1, -1, +3,  0,  0, -3, +2, -2, -2, -1, +3,  0, -1, 
+4,  0,  0,  0, +3, -1,  0, -1, +4, -1, -1,  0, +4, -1, -1,  0,
-4, -1,  0,  0,  0, -1,  0, +4, -2, +2, -2, -2,  0, -4,  0,  0,
-5,  0, -1,  0, -2, +1, +2, +2, +1, -3, -3, -3, +2, -3, -2, -3,
+4,  0,  0,  0, +4,  0, -1,  0, +3,  0, -1,  0, -5, -1,  0,  0,
 0, +4, -1,  0, -3, -2, +1, -3, -5,  0,  0,  0, -3, +2, +2, +2,
-5,  0, -1,  0, -3, -2, -2, +1, -2, -2, -3, +1, -3, -2, +2, -3,
 0, -4,  0,  0,  0, +3,  0, -1, -4,  0,  0,  0, +1, +2, +2, -3 

NOTES: (1) The cache is located on corporate-owned, public-access property. (2) There is nothing to see at the published coordinates. (3) There is no need to approach the rectangle.