QR Codes Can Survive 30% Damage? (Reed-Solomon Codes)

QR Codes are everywhere in our daily lives, used for payments, check-ins, and information sharing.

Have you ever noticed that a smartphone can still scan a QR code even if part of it is torn or scribbled over?

This is because QR Codes have built-in Error Correction. They can recover data even if up to 30% of the code is damaged.

1. Structure of a QR Code

A QR Code is not just a random scattering of black and white dots.

• Finder Patterns: The three large squares in the corners. They help the camera detect the position and orientation of the code.
• Timing Patterns: Alternating black and white dots connecting the finder patterns. They define the coordinate system.
• Data Region: Where the actual information is stored.
• Error Correction Code Region: Where information needed to recover damaged data is stored.

2. Error Correction Levels

When generating a QR Code, you can choose one of four error correction levels.

1. Level L (Low): Recovers ~7% damage. (Highest data capacity)
2. Level M (Medium): Recovers ~15% damage. (Most commonly used)
3. Level Q (Quartile): Recovers ~25% damage.
4. Level H (High): Recovers ~30% damage.

Higher correction levels require more error correction codewords, which increases the size of the QR Code or reduces the amount of data it can hold.

Design QR Codes with logos in the center utilize Level H, treating the area covered by the logo as "damaged data" and recovering it.

3. Reed-Solomon Codes

The core of this magical recovery ability is the Reed-Solomon algorithm.

Also used in CDs, DVDs, hard drives, and space communication, this algorithm adds mathematical redundancy to the data. This allows the original values to be calculated from the remaining information even if some parts are lost.

It's similar in principle to solving a system of linear equations: if you have enough equations, you can find the unknown variables.

Conclusion

A QR Code is not just a barcode; it is a technology packed with advanced mathematical algorithms.

Next time you scan a QR code, take a moment to appreciate the mathematical robustness hidden within those little squares.