Como um código QR é gerado passo a passo

 (nayuki.io)
5 pontos por GN⁺ 2024-11-19 | 1 comentários | Compartilhar no WhatsApp
  • É possível acompanhar o processo interno em que um texto vira um código QR por meio de uma visualização das etapas 0 a 9, entendendo como funciona a Nayuki QR Code generator library
  • A entrada de exemplo Hello, world! 123 é analisada como 17 code points Unicode e codificada em modo Byte, não em Numeric, Alphanumeric ou Kanji
  • Ao concatenar bits de modo, contagem de caracteres, dados do segmento e bits de término, são gerados 19 codewords de dados, que cabem na capacidade de ECC L da Version 1
  • O código QR Version 1 anexa 7 codewords de ECC Reed–Solomon a 19 codewords de dados em 1 bloco, depois posiciona padrões fixos e módulos de dados
  • Comparando as penalidades das 8 máscaras, é escolhido o Mask pattern 3, com a menor pontuação total, mostrando que o resultado final não é definido apenas por codificação, mas também por avaliação de qualidade

Objetivo da demo e processamento da entrada

  • Esta aplicação web visualiza passo a passo o processo de codificação de uma string de texto em um código QR
  • A página destrincha o processo de codificação para ajudar a entender o funcionamento interno da QR Code generator library
  • Os campos de entrada do usuário consistem em string de texto, nível de correção de erro, imposição da Version mínima e imposição do mask pattern

Etapa 0: análise de caracteres Unicode

  • A string de exemplo é Hello, world! 123, e o texto de entrada tem 17 code points
  • Cada caractere é verificado para saber se pode ser codificado nos modos Numeric, Alphanumeric, Byte e Kanji
  • A possibilidade de codificação da string inteira por modo é a seguinte
    • Numeric: impossível
    • Alphanumeric: impossível
    • Byte: possível
    • Kanji: impossível
  • O modo de segmento escolhido para conter toda a string é Byte

Etapa 1: geração do segmento de dados

  • Cada caractere é convertido em uma sequência de bits
  • Nos modos Numeric e Alphanumeric, caracteres consecutivos são agrupados para codificação
  • No modo Byte, cada caractere gera um entre 8, 16, 24 ou 32 bits
  • No exemplo, o valor hexadecimal de cada caractere é convertido em 8 bits
    • H: 48 → 01001000
    • e: 65 → 01100101
    • 1: 31 → 00110001
    • 2: 32 → 00110010
    • 3: 33 → 00110011
  • O programa de demonstração sempre cria um único segmento para simplificar
  • A forma de particionamento ideal para reduzir o comprimento total em bits é tratada separadamente em optimal text segmentation for QR codes

Etapa 2: ajuste do número da Version

  • O comprimento total em bits necessário para representar a lista de segmentos varia conforme o intervalo de Version
    • Version 1~9: 148 bits, 19 codewords
    • Version 10~26: 156 bits, 20 codewords
    • Version 27~40: 156 bits, 20 codewords
  • Um codeword é definido como 8 bits, ou seja, 1 byte
  • A capacidade de codewords de dados de um código QR varia conforme a Version e o nível de correção de erro
  • A entrada de exemplo cabe na Version 1 com o nível de correção de erro selecionado
  • O número de Version escolhido ao final é 1

Etapa 3: concatenação de segmentos, padding e geração de codewords

  • Várias strings de bits são concatenadas para formar a sequência de bits de dados
    • Segment 0 mode: 0100, 4 bits
    • Segment 0 count: 00010001, 8 bits
    • Segment 0 data: 136 bits
    • Terminator: 0000, 4 bits
  • A contagem acumulada de bits é de 152 bits
  • Neste exemplo, tanto o Bit padding quanto o Byte padding têm 0 bits
  • Os bytes totais de codewords de dados são divididos em unidades de 8 bits e mostrados em hexadecimal
    • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30

Etapa 4: divisão em blocos, adição de ECC e interleaving

  • As estatísticas de bloco do exemplo são as seguintes
    • Número de codewords de dados: 19
    • Número de blocos: 1
    • Codewords de dados por bloco curto: 19
    • Codewords de dados por bloco longo: não se aplica
    • Codewords de ECC por bloco: 7
    • Número de blocos curtos: 1
    • Número de blocos longos: 0
  • A sequência de codewords de dados é dividida em blocos curtos e longos, e codewords de ECC são calculados e anexados ao fim de cada bloco
  • O processo matemático do cálculo do código de correção de erros Reed–Solomon é omitido por ser longo, tedioso e pouco interessante
  • A sequência final de codewords é formada intercalando os codewords de dados e de ECC
    • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30 85 A9 5E 07 0A 36 C9
  • A sequência final de bits a ser desenhada no escaneamento em zigue-zague também é gerada a partir dessa sequência de codewords

Etapas 5~6: posicionamento de padrões fixos e codewords

  • Na etapa de padrões fixos, o timing pattern é desenhado na linha 6 e na coluna 6
  • Nos três cantos, é posicionado um finder pattern de 8×8 incluindo o separator
  • Ao redor dos finder patterns são inseridos temporary dummy format bits
  • Na etapa de posicionamento dos codewords, é calculado o escaneamento em zigue-zague começando pelo canto inferior direito
  • O escaneamento em zigue-zague ignora function modules e visita módulos ainda não preenchidos
  • Os módulos de dados, ECC e remainder são desenhados de acordo com os valores de bits dos codewords finais e com a ordem do zigue-zague
  • Como exemplo, o codeword hexadecimal C5 é o binário 11000101 e gera a sequência de módulos [dark, dark, light, light, light, dark, light, dark]

Etapas 7~9: aplicação de máscara e cálculo de penalidade

  • Cada mask pattern afeta apenas os non-function modules
  • A máscara é aplicada com XOR aos módulos de dados, ECC e remainder
  • Os format bits reais são desenhados ao redor dos finder patterns
  • A busca por penalidade verifica os seguintes elementos
    • runs horizontais de 5 ou mais módulos da mesma cor
    • runs verticais de 5 ou mais módulos da mesma cor
    • boxes 2×2 da mesma cor
    • finder-like pattern horizontal
    • finder-like pattern vertical
    • equilíbrio entre módulos escuros e claros
  • O tamanho e a proporção de cores do código QR de exemplo são os seguintes
    • Comprimento do lado: 21
    • Total de módulos: 441
    • Módulos claros: 221
    • Módulos escuros: 220
    • Proporção de módulos escuros: 49.887%
    • Desvio em relação à metade: −0.113%
  • A penalidade total das 8 máscaras é a seguinte
    • Mask 0: 1204
    • Mask 1: 1134
    • Mask 2: 1084
    • Mask 3: 1081
    • Mask 4: 1121
    • Mask 5: 1100
    • Mask 6: 1189
    • Mask 7: 1137
  • A máscara com a menor penalidade total é o Mask pattern 3

Código-fonte

Leituras relacionadas

1 comentários

 
GN⁺ 2024-11-19
Comentários do Hacker News
  • É uma pena que explicações sobre QR code na internet quase sempre deixem de fora o cálculo de correção de erros Reed-Solomon
    Aqui também o autor disse que é “longo, tedioso e não muito interessante”, mas como todo mundo pensa assim, agora ficou bem difícil achar esse conteúdo
    • Fiz uma disciplina de teoria dos códigos na pós-graduação; foi a mais rigorosa que cursei e difícil para todos os 5 alunos, mas ainda assim valeu muito a pena
      Reed-Solomon apareceu um pouco depois da metade do semestre, e a ideia central é que ele se baseia em polinômios. Se você tiver pontos suficientes, o polinômio fica exatamente determinado; então, se adicionar pontos extras, dá para reconstruí-lo mesmo que alguns se percam
      O resto é como aplicar isso a dados binários, ou seja, a parte que usa corpos finitos, o que é matematicamente bonito, mas bem complexo
    • Estes dois tutoriais explicam o cálculo de correção de erros
      https://www.thonky.com/qr-code-tutorial/error-correction-cod...
      https://dev.to/maxart2501/let-s-develop-a-qr-code-generator-...
    • https://www.quaxio.com/an_artisanal_qr_code.html e PagedOut! Issue #2 mostram como criar um QR code do zero, incluindo o cálculo de correção de erros com divisão longa
    • É longo e tedioso, mas na verdade é a parte mais interessante de tudo
    • Existe um artigo relacionado na Wikipedia
  • O vídeo recente do Veritasium, I used to hate QR codes. But they're actually genius, também trata desse tema
    https://www.youtube.com/watch?v=w5ebcowAJD8
  • A coletânea de feedback que o autor recebeu é bem interessante: https://www.nayuki.io/page/poor-feedback-from-readers
    • Zombar de pessoas com inglês fraco e fazer comentários depreciativos sobre um país inteiro como se quem mandou os e-mails fosse uma amostra representativa daquele país diz mais sobre o dono do blog do que sobre os remetentes
      Há um tom fortemente elitista nos comentários. Dando uma olhada rápida no blog, ele pede doações em Bitcoin sugerindo US$ 3, sem aparentemente considerar que uma parte relevante pode sumir nas taxas
    • Mesmo que você receba mensagens de que não goste, é melhor não misturar a reclamação com racismo leve e críticas ao nível de inglês do autor
    • Zombar de inglês ruim é sempre sinal de estupidez. Gente inteligente também pode agir como idiota
    • Desculpe, mas o autor do blog parece ser uma pessoa bem desagradável
      Passa uma vibe de “não, você não pode usar o código do meu repositório no GitHub no chatbot do seu projeto da faculdade. Seu padrão de código está abaixo do meu. E seu inglês também é péssimo”
    • Entendo como manter um blog pessoal pode ser difícil. Você tem que lidar com todo tipo de gente
      Felizmente ele também compartilha feedbacks bons separadamente: https://www.nayuki.io/page/decent-feedback-from-readers
  • Muito bom. Eu gostaria de ver também um decoder no mesmo estilo
    • Você também pode gostar do guia do Piko e do blinry sobre como ler QR codes sem computador: https://qr.blinry.org/
    • Concordo. Sempre me impressiona como os celulares decodificam tão rápido até QR codes escuros, borrados e com um quarto da imagem fora da tela
    • Continuo procurando um guia para implementar um leitor de QR do zero
      Não quero aquela abordagem que aparece no Google do tipo “é só plugar esta biblioteca de visão computacional e passar a imagem que sai o resultado”
      Estou procurando um guia que parta do pressuposto de que você já tem os dados brutos da imagem decodificada e implemente todos os algoritmos necessários a partir daí
  • Gostei que há uma explicação. Pessoalmente, eu só queria gerar isso rapidamente, mas ao pesquisar só apareciam sites cheios de anúncios ou sites do tipo “você precisa se cadastrar para usar”
    Também encontrei alguns no GitHub, mas tinham outros problemas, então acabei gerando rapidamente com uma biblioteca bem projetada que já tinha usado antes, e levei uns 15 minutos
    https://greggman.github.io/qr-code/
    Dá para adicionar mais opções, mas na prática acho que a maioria dos usuários não precisa disso
    • Fico feliz que tenha sido útil. Eu também queria experimentar uma implementação na prática havia algum tempo, mas tudo que consegui encontrar eram pacotes prontos para Python ou Golang
      Se alguém tiver material útil sobre a parte de correção de erros em QR codes, eu gostaria de conhecer
  • Eu fiz uma implementação em Rust há algum tempo
    https://github.com/aabiji/qr
  • Se não for um texto do ano atual, é uma boa prática colocar o ano no título, aqui 2018
    • Concordo. Pelo que vi, o link original não tinha data, e agora já não dá mais para editar
  • Muito bom. Aprender como QR codes funcionam estava na minha lista há muito tempo, e este foi um bom texto introdutório
  • Agora que você sabe como funciona, também pode usar em consultas SQL: https://github.com/Florents-Tselai/pgQR