The Mathematics Behind Your Cell Phone

Joseph Malkevitch
Mathematics Department
York College (CUNY)




Email: malkevitch@york.cuny.edu




Mathematics is:

* useful

* beautiful

Modern communications technologies:

* fax
* compact disc
* dvd
* cell phones
* ipod
* HDTV

What role has mathematics played in developing these new technologies?

Ans.

Without mathematics discovered in the 20th century these technologies would not be possible!

Essential ideas:



* error correction

(Richard Hamming (1915-1998))

* data compression

(David Huffman (1925-1999))
Representing images:



Each small square is called a pixel.


Use binary sequences to code the pixels:

000000 = white
000111 = gray
111111 = black

Thus:

Image can be represented by a sequence of 0's and 1's.

What happens if noise corrupts the binary sequence?

sent: 1100/0000/1000/etc

received: 1100/1000/0000



Possibilities:

corrupted string is not a code word! (unclear how to reconstruct image)

corrupted string is a code word! (reconstructed image is not correct)





Richard
Hamming's Work

Idea:

If code words are "far apart" and there are not too many errors then the errors can be corrected!

Hamming realized that binary sequences were far apart when they differed in many places!


Examples:

111100 Hamming
010010 Distance = 4

000100 Hamming
110110 Distance = 3

(useful idea in genome work!)




If circles of radius r do not overlap then one can correct up to r errors!


If the minimum Hamming distance between any two code words is 2r+1 then the code will correct up to r errors (per code word).


Code words are sequences of binary digits:


Block code:

All code words have the same length:


0001 1001 1000 1011

Variable length code:


1 0 11 110 1 01


Data compression Idea:


Use short code words for symbols that occur often;


Use long code words for symbols that occur rarely!
Example:

Design a code for a message where the symbols occur:

3, 7, 13, 16, 21, and 40 times.
Huffman tree:



Code words are sequences of binary digits:

Block code:

All code words have the same length:


0001 1001 1000 1011

Variable length code:


1 0 11 110 1 01