Welcome to Mathematics of Information

What is the course about?

This course focuses on the mathematical foundations needed to understand the principles governing the storage, processing, and transmission of information (on any device). It covers several branches of mathematics and their applications in data storage, communications, signal processing and security. It will allow us, for example, to better understand

• How does a cellphone, which has mostly digital components, interact with an analog world?
• How does it store different types of data (music, video, apps) reliably, when the storage device itself (flash memory) is unreliable?
• What makes it possible to stream music over noisy wireless channels that sound so good (well, most of the time)?

Topics include:

• Mathematical representation of information
• Probability, uncertainty, and information
• Linear/abstract algebra and error correction
• Spectral analysis and communication
• Number theory and encryption
• Boolean algebra and computation

Mathematics vs Engineering:

The course aims to make abstract and/or advanced mathematics, e.g., complex numbers and finite fields, tangible through applications in information science and technology. We will learn the basics of several branches of mathematics, e.g., probability, linear algebra, Fourier analysis. Based on each, we will develop a theory related to information, e.g., communication, privacy.

Given the history of the course, I need to explain how it balances mathematics with engineering applications. We will study both the mathematical foundations and the engineering solutions enabled by these foundations, but our focus will be on the former. Hence, while the topics are motivated by application, we will also discuss material without direct applications, with the goal of providing solid foundations for the topics we study.

Credit: XKCD

Although we are at the right end of the spectrum, what we study has many applications in electrical and computer engineering and computer science.

What is information?

Mathematically, we can consider a set \(\mathcal{X}\) of all possibilities and a variable \(X\) that indicates a realization (i.e., an actual occurrence). For example, for weather we may let

and then “\(X=\) ☁️” indicates cloudy weather on a given day.

Information is closely related to uncertainty, and by extension probability.

For the following cases, describe the set of all possibilities. (optional): Try to come up with rough estimates of the number of possibilities. Show Solution

1. a person’s DNA sequence
2. outside temperature measured by a thermometer
3. loudness of someone's voice at a given time instant
4. color of a pixel in an image
5. the contents of a page of a novel

1. Human DNA is a sequence of approximately 3.2 billion bases long, where each base is one of the following \(A,C,G,T\), each representing a certain chemical structure. So the set of possibilities is a sequence of length \(3.2\times 10^9\) with symbols from the set \(\{A,C,G,T\}\).
   The number of such sequences is approximately 1 followed by 2 billion 0s! (We will later discuss how this and similar counting problems are solved.)
2. Assuming the thermometer displays 1 decimal place, the set of possibilities consists of numbers of the form \(\pm xxx.x\). (The true temperature is a real value that can't be written down.) Assuming temperatures from -30 to 140, there are around 1700 possibilities.
3. Loudness is air pressure, so theoretically it can be any positive real number. The number of possibilities is infinite.
4. Color is our perception of the wavelength of light. In an image it is represented in different ways, for example, as three values for red, blue, and green, each with 256 levels. The number of possibilities is in the millions.
5. A typical page contains around 3000 characters of English alphabet. Assuming there are 100 symbols (capital and small letters, punctuation, new line, etc.), there are \(10^{6000}\) possibilities.

As we see above, the number of possibilities can be very large. For comparison, less than \(10^{18}\) seconds have passed since the big bang.

We will study information in multiple ways:

• As numbers representing signals, audio, images, or video
• Through probability
• As related to noise and errors
• Privacy and protecting information
• Via processing using a computer

Some applications of what we will study

The mathematical concepts have many applications in how any device that senses, transmits, or stores information works. Some of the applications are:

• Sensing, for example in a camera: sampling, quantization, compression, …
• Streaming music: digitization and reconstruction, spectrum, communication, …
• Data storage in flash and hard drives: data compression, encoding and decoding, error correction, …
• Computation in a processor: logic gates, computation via physics, …
• Privacy and security: encryption, …

Course overview

Now let’s see an overview of what we’ll see in the course. In each case, we’ll start with a question related to the applications of the mathematical topic.

Part 1: Numbers and signals

Q: The real world is, for practical purposes, analog and continuous. How is it represented on a computer, which is digital?

Topics:

• Set theory
• Sets of numbers and operations
• Countable and uncountable sets
• Digital and analog signals
• Number representations
• Quantization
• Analog-to-digital conversion

Part 2: Probability theory & Information

Q: The human genome is a sequence of 3 Billion bases of {A,C,G,T}. How much storage do we need to store someone’s DNA (standalone)?

Topics:

• Probability, likelihood, uncertainty, and information
• Counting
• Probability distributions
• Expected value
• Independence and conditional distributions
• Repeated (e.g., Bernoulli) trials
• Entropy, mutual information, and capacity
• Data Compression
• Mathematics of communication

Part 3: Linear algebra

Q: Hard drives, flash drives, WiFi, and cellphone signals all suffer from noise. How is it then possible to store and transmit information without errors?

Topics:

• Vectors and matrices
• Matrix operations
• Matrix equations
• Finite fields
• Error detection and error correction
• Parity checking and Hamming codes

Part 4: The frequency domain

Q: If we all start talking at the same time, no one will be able to understand anything. How is it possible for a large number of cell phones to communicate simultaneously?

Topics:

• Frequency and spectrum
• Complex numbers
• The Fourier transform
• Filtering signals and images
• Sampling and reconstructing signals
• Multiple-access communication and orthogonal coding
• Amplitude, frequency, and phase modulation

Part 5: Number theory

Q: Can we talk privately in public?

Topics:

• Number systems and binary arithmetic
• Number theory and encryption
• Divisibility, prime numbers, congruences
• Public key cryptography and Chinese remainder theorem

Part 6: Boolean algebra

Q: How to compute with physics?

Topics:

• Logic
• Boolean algebra
• Digital Computation

Some other comments:

• Read all course policies on the course info document on Collab/Overview.
• Review the material often. Don’t wait for exams.
• Due to the broad, yet particular, nature of this class, we will not be following a specific textbook. However, occasionally links to external resources will be provided.

Conventions

To improve clarity, you’ll see the following environments in the notes:

These are examples and exercises. Optional exercises are indicated by (optional) or . Sometimes a solution is available but initially, hidden. You can view it by clicking the button on the right. Show Solution

2 + 2 = 4. 2+3 = 5.