Arquitetura do algoritmo

Como funciona a correção de erros do QR Code: a matemática Reed-Solomon explicada

Já se perguntou como um QR Code continua sendo lido perfeitamente mesmo rasgado, manchado de café, parcialmente borrado ou coberto no meio pelo logo de uma marca? O segredo está na correção de erros polinomial Reed-Solomon.

Quatro QR Codes do mesmo endereço nos níveis de correção de erros L, M, Q e H, cada um com 7, 15, 25 ou 30 por cento da área escurecida para mostrar quanto dano o nível consegue recuperar

1. O que é a correção de erros Reed-Solomon?

Inventada em 1960 pelos matemáticos Irving S. Reed e Gustave Solomon, a correção de erros Reed-Solomon (RS) é um algoritmo cíclico não binário de correção de erros amplamente usado em telecomunicações espaciais (a sonda Voyager da NASA), discos ópticos de CD/DVD, televisão por satélite e no padrão ISO/IEC 18004 para QR Codes.

Em vez de apenas detectar erros (como um simples bit de paridade ou uma soma de verificação CRC), o código Reed-Solomon gera blocos de paridade matemáticos redundantes capazes de identificar a localização exata dos módulos de bytes danificados e reconstruir os dados originais do conteúdo sem pedir que a transmissão seja repetida.

2. Os 4 níveis de correção de erros do QR Code

O padrão ISO/IEC 18004 especifica quatro níveis selecionáveis de código de correção de erros (ECC). Cada nível representa a porcentagem do total de palavras de código que pode ser destruída ou encoberta antes que o código fique ilegível:

Nível de ECC Capacidade de recuperação Densidade de módulos Uso recomendado
Nível L (baixo) ~7% dos dados Menos denso (menos quadradinhos) Telas digitais e conteúdos grandes em que o QR precisa continuar pequeno.
Nível M (médio) ~15% dos dados Padrão equilibrado Padrão para URLs em geral, embalagens, folhetos e impressos de marketing.
Nível Q (quartil) ~25% dos dados Moderadamente denso Ideal para logos personalizados, displays de mesa e ambientes sujeitos a desgaste.
Nível H (alto) ~30% dos dados Maior densidade (mais quadradinhos) Outdoors, etiquetas industriais e ambientes com muito desgaste físico.

3. Como a inserção de logos aproveita a correção de erros

Quando você coloca um logo ou ícone no centro de um QR Code, o sensor óptico do leitor interpreta o logo como dano físico na superfície ou como módulos ausentes.

Como o nível de correção de erros Q consegue recuperar até 25% dos dados corrompidos e o nível H até 30%, o decodificador matemático Reed-Solomon calcula os módulos ausentes sob o logo e reconstrói a URL original em milissegundos.

As regras de ouro para QR Codes com logo:

  • Área máxima: nunca deixe um logo ocupar mais de 20% a 25% da área total do QR Code.
  • Proteja os 3 marcadores dos cantos: nunca deixe o logo cobrir ou encostar nos três grandes olhos quadrados dos cantos superior esquerdo, superior direito e inferior esquerdo.
  • Use margens brancas: sempre desenhe uma margem de proteção branca sólida ao redor do logo para evitar que os módulos vizinhos do QR se misturem com o desenho do logo.
  • Mudança automática para o nível Q ou H: o qr-code.love aumenta automaticamente o nível de correção de erros para Q ou H sempre que você envia um logo personalizado.

4. O processo matemático no corpo de Galois GF(256)

O codificador que roda no seu navegador faz as contas em um corpo finito com 256 elementos, escrito GF(28) ou GF(256). Cada byte é um elemento desse corpo, e a multiplicação é definida módulo este polinômio primitivo:

P(x) = x8 + x4 + x3 + x2 + 1   (0x11D em hexadecimal)

Os bytes de dados são tratados como os coeficientes de um polinômio D(x). O motor o multiplica por xE, em que E é o número de palavras de código de correção de erros exigido pelo nível, e divide o resultado por um polinômio gerador fixo G(x) daquele nível. O resto dessa divisão é a paridade: E bytes que são colocados no símbolo depois dos dados.

5. As 8 máscaras da ISO e a pontuação de penalidade

Depois que as palavras de código de correção de erros são calculadas, colocar os bytes binários brutos em uma grade poderia criar sem querer grandes áreas de módulos todos pretos ou todos brancos, ou falsos formatos de "marcador de posição" que confundem os sensores ópticos das câmeras.

Para resolver isso, o padrão ISO/IEC 18004 aplica 8 máscaras matemáticas XOR candidatas sobre a grade. O motor pontua cada candidato mascarado usando uma fórmula de penalidade rigorosa:

  • Penalidade 1 (sequências de módulos adjacentes): sequências de 5 ou mais módulos seguidos da mesma cor somam 3 pontos, mais 1 para cada módulo além de cinco.
  • Penalidade 2 (blocos de 2x2 módulos): cada quadrado sólido de 2x2 soma 3 pontos de penalidade.
  • Penalidade 3 (falsos marcadores de posição): qualquer sequência de módulos na proporção 1:1:3:1:1 soma 40 pontos de penalidade.
  • Penalidade 4 (desequilíbrio entre escuro e claro): o desvio em relação ao equilíbrio de 50/50 soma pontos de penalidade proporcionais.

A máscara que produz a menor pontuação de penalidade acumulada é escolhida e codificada nos bits de informação de formato ao redor dos marcadores de posição.

6. Resistência ao desgaste no mundo real

Escolher o nível certo de correção de erros é essencial para materiais físicos expostos ao tempo ou ao desgaste:

Condição do ambiente ECC recomendado Risco típico de dano
Outdoors e placas de metal Nível H (30%) Desbotamento por UV, marcas de chuva, ferrugem e fezes de pássaros.
Displays de mesa e cardápios de restaurante Nível Q (25%) Comida derramada, marcas de dedo e álcool em gel.
Embalagens e etiquetas de produtos Nível M (15%) Pequeno atrito na superfície e arranhões de manuseio.
Telas digitais e transmissões de TV Nível L (7%) Nenhum desgaste físico; prioriza a menor quantidade de pixels.

7. Palavras de código de dados e de correção de erros por versão

Cada versão tem um número fixo de palavras de código, de oito bits cada, e o nível decide quantas levam seus dados e quantas levam dados de recuperação. As três primeiras versões ficam assim.

VersãoTotalL (dados + CE)MQH
12619 + 716 + 1013 + 139 + 17
24434 + 1028 + 1622 + 2216 + 28
37055 + 1544 + 2634 + 3626 + 44

Nem todas as palavras de código de dados são conteúdo. Os primeiros bits guardam o indicador de modo e a contagem de caracteres, que no modo byte ocupam doze bits até a versão 9 e vinte a partir da versão 10. É por isso que um símbolo da versão 1 no nível L comporta 17 bytes dos seus dados, e não 19.

No nível H, os dados de recuperação superam o conteúdo desde a versão 1. Essa é a troca que a opção de logo faz ao elevar o nível: menos bytes de espaço, em troca de um símbolo que continua legível com parte dele coberta.

Fontes e leitura complementar

Gere QR Codes com correção de erros

Escolha o nível Reed-Solomon que preferir (L, M, Q, H) e insira o logo da sua marca sem nenhum registro no servidor.

Abrir o gerador completo