How Does Run Length Encoding Work?

How does run length encoding work? Imagine sending a row of pixels to a friend who can draw it one square at a time. Instead of saying “black” six times, you say “six black.” Your friend draws the same six squares. That shortcut saves space when identical pixels sit together, but it can have the opposite effect when the color changes at every pixel.
How does run length encoding work on a pixel row?
A run is an unbroken stretch of the same value. It ends when the value changes or the row ends. Run-length encoding, or RLE, replaces each run with information that tells the decoder what to repeat and how many times to repeat it. In our format, each pair puts the color first and the count second. Let B mean black and W mean white.
Original row: BBBBBBWWWWBB Encoded row: (B, 6) (W, 4) (B, 2)
Scan from left to right. The first six pixels are black, so the first white pixel tells you to write (B, 6). That white pixel is already the first pixel of the next run, so start its count at one, not zero. When the row switches back to black, write (W, 4). The final two pixels are black. There is no next color to trigger a write, so you must write (B, 2) when you reach the end.
The row contains eight black pixels in total, but (B, 8) (W, 4) would put them all at the start. RLE is not a tally of how common each color is. The order of the pairs preserves where each stretch belongs.
Decoding the row one pair at a time
Start with an empty row. Read (B, 6) and append six black pixels. Next, read (W, 4) and append four white pixels without changing the black pixels already in the row. Finally, append two black pixels for (B, 2). The result is BBBBBBWWWWBB, exactly what the encoder started with.
This makes RLE lossless: decoding the encoded data gives back the original data exactly. You can check the output length before drawing a single pixel by adding the counts: 6 + 4 + 2 = 12. But the length alone is not enough to check that decoding worked. Swapping the first and last pairs would still give 12 pixels, with the white stretch in a different place.
Try decoding (W, 1) (B, 3) (W, 2) on paper. You should get WBBBWW. The first pair is a reminder that a run can be just one pixel long. If you are implementing the encoder, a one-pixel row should produce one pair with count one. An empty row should produce no pairs.
When an alternating row gets bigger
Now keep the same row length but alternate the colors: BWBWBWBWBWBW. Every pixel starts a new run. The encoded row begins (B, 1) (W, 1) (B, 1) (W, 1) and continues that way until it has 12 pairs. In this format, you still store every color, and now you also store a count for every pixel.
To compare sizes fairly, pick storage rules rather than counting the punctuation in our examples. Suppose a raw pixel gets one bit: 0 for black and 1 for white. In the encoded form, each pair gets one color bit and four bits for an unsigned count, enough to store any run length from 1 to 12. Assume the reader knows which format it is reading, and compare just the bits for the row, without headers or padding.
| 12-pixel row | Runs | Raw bits | Encoded bits |
|---|---|---|---|
BBBBBBWWWWBB | 3 | 12 | 15 |
BWBWBWBWBWBW | 12 | 12 | 60 |
BBBBBBWWWWWW | 2 | 12 | 10 |
Even the first row grows a little under these rules. Three pairs look shorter on paper than 12 letters, but each pair costs five bits while a raw pixel costs only one. The third row saves two bits because it needs only two pairs. The alternating row costs five times as much as its raw version. Those numbers belong to this specific format, not to every kind of RLE.
What the data format can change
In a black-and-white row, once you know the first color, you can infer the color of every later run: it must be the opposite of the previous one. A different format could store the first color once and then store only the counts. With four bits per count, the first example would take 1 + 3 × 4 = 13 bits, and the alternating example would take 1 + 12 × 4 = 49 bits. Removing redundant color bits helps, but it does not make short runs cheap.
Count size also sets a limit. Four bits can represent a maximum unsigned count of 15. If you use explicit color-count pairs and allow a long run to be split, 20 black pixels could be written as (B, 15) (B, 5). That same split would not work in the format that assumes every next run changes color: the decoder would draw the last five pixels in white. The encoder and decoder have to agree on what a count means, not just how many bits it occupies.
Practice with the same pixels in a new order
Compare BBBBBBWWWWWW with BBWWBBWWBBWW. Both rows contain six black pixels and six white pixels. Before writing any pairs, mark each place where the color changes. For a nonempty row, the number of runs is one more than the number of changes. Use that rule to predict the pair count, then encode and decode both rows to check your work.
If you write an encoder, use the guide to tracing code by hand to track the current color, the count, and the pairs written so far. For other exercises in explaining and checking algorithms, see the ICSC training and practice problems.
Frequently asked questions
Do matching pixels have to be next to each other?
Yes. If a different color comes between two black pixels, those black pixels belong to separate runs.
Is run-length encoding always smaller?
No. If runs are short, storing their counts can cost more than storing the original pixels.
Does RLE change the image?
No. With matching encoding and decoding rules, every pixel returns in its original position.



