Códigos BCH e Golay em informações de formato e versão

BCH and Golay Codes in Format and Version Information

While Reed-Solomon codes protect the data payload, QR codes use different error-correcting codes for their metadata: BCH codes for format information and Golay-like codes for version information.

Format Information: BCH(15,5)

The format information is a 15-bit sequence encoding two critical pieces of metadata:

• Error correction level (2 bits): L=01, M=00, Q=11, H=10
• Mask pattern (3 bits): 000 through 111

These 5 data bits are encoded into 15 bits using a BCH(15,5) code with generator polynomial x^10 + x^8 + x^5 + x^4 + x^2 + x + 1. The 10 parity bits can detect and correct errors in the format information itself.

The 15-bit result is XORed with the mask pattern 101010000010010 to ensure the format information is never all-zero (which would be undetectable).

Format Information Placement

Format information is written twice in every QR code:

1. Along the edges of the top-left finder pattern (horizontal and vertical)
2. Split between the bottom-left and top-right finder patterns

This redundancy ensures format information can be read even if one copy is damaged.

Version Information: Golay(18,6)

For versions 7-40, an 18-bit version information block encodes the version number:

• Version number (6 bits): 7 through 40
• Error correction (12 bits): Golay-type code

The generator polynomial is x^12 + x^11 + x^10 + x^9 + x^8 + x^5 + x^2 + 1. The 12 parity bits provide strong error detection and correction for the 6-bit version number.

Version Information Placement

Version information also appears twice:

1. A 6x3 block above the bottom-left finder pattern
2. A 3x6 block to the left of the top-right finder pattern

Why Not Reed-Solomon?

Format and version information are very short (5 and 6 bits respectively). RS codes over GF(256) operate on 8-bit codewords and would be inefficient for such small payloads. BCH and Golay codes operate at the bit level, providing optimal protection for short binary sequences.

Decoding Priority

During the scanning process, the decoder reads format information first — before attempting to decode any data. This is because the format information reveals the EC level and mask pattern needed to decode everything else.

Key Takeaways

• BCH(15,5) protects the 5-bit format information (EC level + mask pattern)
• Golay(18,6) protects the 6-bit version number (versions 7-40)
• Both are placed redundantly in two locations for damage resilience
• Bit-level codes are more efficient than RS codes for very short data
• Format information is decoded first — it is needed to decode everything else