Saturday, April 13, 2013

Playing with the Error correction.

There are several 2D bar-codes that make use of the Reed Solomon (RS) error correction. 


Each byte of a message is run through the algorithm, generating a RS code word.This code word is then added to the message.

Example:

The selected Reed Solomon code word is 9 Bytes. 
The message is a array containing = ['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd']
Converted to ASCII values = [104, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100] 
And running this through RS generator gives a total of 11 + 9 bytes:


[104, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100], [145, 124, 96, 105, 94, 31, 179, 149, 163]

With these settings up to 4 byte errors in the message and/or RS code word can be corrected.

Suppose the message was corrupted during transmission and at the receiving end would be decodes as
[104, 101, 108, 108, 111, 32, 101, 97, 114, 116, 104] ,[145, 124, 96, 105, 94, 31, 179, 149, 163]
Uncorrected the message would read as: ['h', 'e', 'l', 'l', 'o', ' ', 'e', 'a', 'r', 't', 'h']
The RS decoding algorithm returns the following information:
[[10, 12], [9, 24], [7, 14], [6, 18]]
Byte 10 needs a XOR of 12
Byte 9 needs a XOR of 24, etc

Errors in a QR Code generated by graphical enhancement are corrected in this way.

Why is this information so interesting?

In QR Codes the message part is not filled most of the time.
Suppose the message is just "hello", In a QR Code the number of reserved spaces for a message is fixed, in this example this means that there are always 11 bytes reserved for the message.
The message is a array would be = ['h', 'e', 'l', 'l', 'o', '*', '*', '*', '*', '*', '*']

The (*) parts of the message is filled by a padding pattern as described in the specification of the QR Code.

Using this information in a QR Code:

The picture illustrates a typical QR Code:
  • The gray section is to identify a QR Code.
  • The green is the used message area.
  • The black is the unused (padded) message area.
  • The red is the error correction information.
When QR is graphically enhanced in the black area, the inserted graphic will generate a modification in the part of the message that is padded. Of this new message a new RS code word can be calculated, resulting a in graphically enhanced and error free QR Code.


If you require a fast scanning, error free  graphically enhanced QR Code, don't hesitate to contact me or visit my site to see more examples of what is possible with QR Codes.

No comments:

Post a Comment