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.

Essential ideas:

*

(Richard Hamming (1915-1998))

*

(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