How reed solomon error correction algorithm makes a damaged QR code to work fine ?

How reed solomon error correction algorithm makes a damaged QR code to work fine ?

Amused At

Today (02/12/2023), due to fever and cold i went to Ayurvedic medicine store. During the payment , i asked him QR code for digital payment. The QR code sheet is pretty damaged.

Before scanning i thought it wouldn't work. But to my surprise it worked after straightening the torn part. How could it work ?

On Googling ...

A QR code (short for Quick Response code) is an array of black and white squares or pixels set in a grid that stores data for a machine to read. A smartphone or camera can quickly process the information contained in a QR code’s specific arrangement of pixels, making it a convenient way to store and access data.

How do QR codes work?

QR codes work by arranging a series of black and white pixels into a unique pattern that encodes a string of data. When scanned, the pattern of the qcode can be translated into human-readable information.

If you know how to scan a barcode using a laser-reader, you already know how to scan a QR code — the only real difference is the type of device used to read the code. But unlike barcodes’ linear arrangement, QR codes can store much more data, because they’re written both vertically and horizontally.

All QR codes have a standard structure that makes information readable. Let’s break it down:

  • Quiet Zone: The empty white border around the outside of a QR code.

  • Hinder pattern: The three black squares in the bottom-left, top-left, and top-right corners.

  • Alignment pattern: A small square near the bottom-right corner, which ensures the QR code can be read, even if it’s skewed or at an angle.

  • Timing pattern: An L-shaped line that helps to identify individual squares within the whole code, making it possible for a damaged QR code to be read.

  • Version information: Identifies which version of the QR code is being read.

  • Data cells: The rest of the QR code communicates the actual information — the URL, phone number, or other data.

Usually, you don’t need to use a special QR app scanner — smartphones will link to the content in the QR code when you point your camera app at it. If you’re offline or think you’ll need to access the code again, taking a picture of it will make the QR code scan again when you view it later.

How does it manage damages ?

The QR code error correction is a unique feature that allows printed QR codes to withstand damage like scratches and smudging yet still work just fine.

The error correction in QR codes comes in four levels, each capable of withstanding a different maximum amount of damage.

And since the error correction works by adding extra modules, the QR code’s dimensions will increase as its error correction level rises.

Online QR code generator platforms offer different levels of error correction, so it’s important to go for one that provides the level that suits your needs. Here are the four levels:

  1. Level L (low) - 7% error correction

  2. Level M (Medium) - 15% error correction

  3. Level Q (Quartile) - 25% error correction

  4. Level H (High) - 30% error correction

Higher the level, more dense the code looks.

The magical ingredient on top of these error correction is Reed Solomon Error Correction.

The Reed-Solomon encoder takes a block of digital data and adds extra "redundant" bits. Errors occur during transmission or storage for a number of reasons (for example noise or interference, scratches on a CD, etc). The Reed-Solomon decoder processes each block and attempts to correct errors and recover the original data. The number and type of errors that can be corrected depends on the characteristics of the Reed-Solomon code.

How it works ?

Let's try the working using python library. Install it,

pip install --upgrade reedsolo

Let's take our family name, "IAMFULLSTACKDEVELOPER"

from reedsolo import RSCodec, ReedSolomonError
rsc = RSCodec(10)
# bytearray(b'I AM FULL STACK DEVELOPERsC9_\xec\xfe\xfd2\xf41')

  1. Decode the original value,

     rsc.decode(b'I AM FULL STACK DEVELOPERsC9_\xec\xfe\xfd2\xf41')[0]
     # bytearray(b'I AM FULL STACK DEVELOPER')

  2. Let's add some error,

     rsc.decode(b'I AM FULJ STAKK DEVELOPERsC9_\xec\xfe\xfd2\xf41')[0]
     #                    |    ||       <- Error

  3. Let's change a word itself,

     rsc.decode(b'I AM BLUE STACK DEVELOPERsC9_\xec\xfe\xfd2\xf41')[0]
     #                 ||||  <- Error

    Impressive isn't.

It's very awesome computer stuff i feel. I just fell in love with Error correction codes.

Some good reads ...

  1. Read Solomon Codes

  2. CTF related to Read Solomon Codes

  3. Some great examples

  4. csfieldguide