Gently Down the Stream: The Mathematics of Streaming Information (Student)

What Is Computational Thinking?

Computational thinking is a high-level thought process that considers the world in computational terms. It begins with learning to see opportunities to compute something, and it develops to include such considerations as computational complexity; utility of approximate solutions; computational resource implications of different algorithms; selection of appropriate data structures; and ease of coding, maintaining, and using the resulting program. Computational thinking is applicable across disciplinary domains because it takes place at a level of abstraction where similarities and differences can be seen in terms of the computational strategies available. A person skilled in computational thinking is able to harness the power of computing to gain insights. At its best, computational thinking is multidisciplinary and cross-disciplinary thinking with an emphasis on the benefits of computational strategies to augment human insights. Computational thinking is a way of looking at the world in terms of how information can be generated, related, analyzed, represented, and shared.

Module Background

When Europeans first began settling in America, it would take weeks to send a letter across the ocean (and, of course, at least twice as long to get a response)! Now we can and do send information all over the world in a matter of seconds. In the digital age, it’s imperative not only that we are able to send information quickly but also that we can verify that it was correctly received. Failure to do so can have grave consequences, from the wrong amount charged to a credit card to a remote drone striking the wrong target and killing innocent civilians.

The purpose of this unit is to explore some of the issues in sending and receiving information. These issues include error detection, error correction, data compression, and sender and message authentication. The following exercise is representative of the types of problems encountered, and the successes we’ve had in solving them. After you do the activity, we’ll discuss its application to error correction. Amazingly, we can send very special messages where the recipient can not only detect that a transmission error has been made but also figure out what the intended message was!

The science of streaming information highlights a wonderful interplay between theory and application. Most of us have watched some streaming video; perhaps it’s a baseball game, a YouTube video, the latest episode of our favorite TV show, or a presidential address in a time of crisis. The purpose of this module is not to delve into all the nuts and bolts of the topic but rather to use a common experience to motivate some important mathematical results and computational perspectives.

Many complicated and interrelated issues must be understood to make streaming video practical. Obviously there are technological components, such as building the hardware capable of sending and receiving signals. The original motivation of this module is to understand how streaming video works, but other important and related problems will also be explored.

• Lesson 1: The first issue is error detection. When transmitting a large message, we need to know it was correctly received. Even small errors can have disastrous consequences because smaller sets of data can replace large amounts of data, and thus a small error can be greatly magnified. We’ll describe the general theory and see some methods to detect errors.

• Lesson 2: After learning a transmission error happened, the natural next step is to try to fix it. This leads to the subject of error correction, which is significantly harder than just detecting an error. Different solutions to this problem are investigated, and their relative strengths and weaknesses are discussed.

• Lesson 3: In many instances, such as streaming video, it is imperative that the data be transmitted and processed quickly. In this section, we discuss some issues in compression and dynamic sampling.

• Lesson 4: The topic of this lecture could easily have been the first; before we read a message, we should verify that it comes from the claimed sender. This authentication problem must be resolved before any e-commerce is possible.