What is Interleaving?

Imagine kids in two buses.


In Bus #1, the kids are seated according to their age, with the oldest one seated last. When the bus stops, the kids are supposed to come down according to their age. As you can imagine, it is easier for the stream of kids to flow because they are already in the correct order closest to the door.

In Bus #2, kids can sit anywhere they want. When the bus stops, the kids are supposed to come down according to their age. Now, if the youngest kid is sitting somewhere in the middle, he or she will take more time coming to the door, and so on. Clearly, this system is more inefficient, in this scenario.

This second bus/system is called Interleaving, and is widely used in memory, hard drive and transmission systems today.

Come again? Why use it if it is inefficient?

Let’s do the bus example again, but this time let’s look at the whole picture. In Bus #1, the kids have to enter according to their age, and then seat themselves. We all know it takes time to arrange them in order.

In Bus #2, this isn’t a problem. The kids run up and sit, with no latency.

In sum total, which bus is more efficient overall? You’ll see that the difference isn’t so bad as it seems.

So, why is interleaving used at all if it’s the same thing? Wouldn’t things be better off in order?

Interleaving is used because that’s the nature of data writing, reading and transmission.

Humans don’t use computers or television in a systematic way. When was the last time you surfed from channel 1 to your favorite channel – every time? When was the last time you took all your photographs for the year, ordered them, then looked at all the files your created on your computer, ordered them, and wrote them on disk?

The nature of data storage and transmission is fragmented, and that’s how disks are designed to behave. The way they store data is non-contiguous (not continuous). Whatever you want to save, your computer does it under the hood, without complaining.

It is designed to embrace randomness. This is interleaving.

Tape vs Disc
Tape: Copyright 2003 by Daniel P. B. Smith. Licensed under to the terms of the Wikipedia copyright.
DVD Disc:Marcin Sochacki (Wanted), 2004

If you were born after the year 2000 you might have never seen a tape, but it still exists, especially in the form of LTO drives for backup. Tapes write data in an orderly fashion, sequentially.

But this is also its greatest disadvantage. If your data is buried deep inside, you can’t get to it without going through the rest of the tape, even at full speed. A disc, on the other hand, is designed to store data in a non-contiguous fashion, so you can get to it quickly.

In its fundamental sense, interleaving is designed to reduce latency in complex random systems where data is flying around all over the place. It is left to software and each individual human to make sense of it all.

The Challenge Interleaving faces

You see, when people send an email or save a file to computer, they don’t usually care how the computer executes it. Now that computers have become good at multitasking, you can carry on working without knowing how the computer actually does the interleaving.

On the other hand, when humans want something, they want it now! This is the biggest challenge interleaving faces, the problem of bus #2. In other words, how to reduce latency in an interleaved system?

As a side note, one such interleaved system is AVI, which stands for Audio Video Interleave (now you know where you’ve heard that word before!). The AVI standard breaks down audio and video into chunks for writing. AVI is actually designed to hold many streams of audio and video in one file – a real interleaved file format for storage, delivery and transmission.