Cómo generar un código QR paso a paso

 (nayuki.io)
5 puntos por GN⁺ 2024-11-19 | 1 comentarios | Compartir por WhatsApp
  • Sigue el proceso interno por el que un texto se convierte en un código QR mediante una visualización de las etapas 0 a 9, y permite ver cómo funciona la biblioteca Nayuki QR Code generator library
  • La entrada de ejemplo Hello, world! 123 se analiza como 17 puntos de código Unicode y se codifica en modo Byte, no en Numeric, Alphanumeric ni Kanji
  • Al concatenar los bits de modo, el conteo de caracteres, los datos del segmento y los bits de terminación, se generan 19 codewords de datos, que encajan en la capacidad ECC L de la Version 1
  • Un código QR Version 1 agrega 7 codewords Reed–Solomon ECC a 19 codewords de datos en 1 bloque, y luego coloca los patrones fijos y los módulos de datos
  • Compara la penalización de las 8 máscaras y elige Mask pattern 3, que tiene la puntuación total más baja; el resultado final no se decide solo por la codificación, sino también por una evaluación de calidad

Objetivo de la demo y procesamiento de la entrada

  • Esta aplicación web visualiza paso a paso el proceso por el cual una cadena de texto se codifica como código QR
  • La página desglosa el proceso de codificación para ayudar a entender el funcionamiento interno de QR Code generator library
  • Los campos de entrada del usuario consisten en una cadena de texto, nivel de corrección de errores, forzar una Version mínima y forzar un patrón de máscara

Etapa 0: análisis de caracteres Unicode

  • La cadena de ejemplo es Hello, world! 123, y el texto de entrada tiene 17 puntos de código
  • Se verifica si cada carácter puede codificarse en los modos Numeric, Alphanumeric, Byte y Kanji
  • La posibilidad de codificación de toda la cadena por modo es la siguiente
    • Numeric: no es posible
    • Alphanumeric: no es posible
    • Byte: posible
    • Kanji: no es posible
  • El modo de segmento elegido para contener todos los caracteres es Byte

Etapa 1: creación del segmento de datos

  • Cada carácter se convierte en una cadena de bits
  • En los modos Numeric y Alphanumeric, los caracteres consecutivos se agrupan para codificarse
  • En modo Byte, un carácter genera 8, 16, 24 o 32 bits
  • En el ejemplo, el valor hexadecimal de cada carácter se convierte a 8 bits
    • H: 48 → 01001000
    • e: 65 → 01100101
    • 1: 31 → 00110001
    • 2: 32 → 00110010
    • 3: 33 → 00110011
  • Para simplificar, el programa de demostración siempre crea un solo segmento
  • La estrategia de partición óptima para reducir la longitud total en bits se trata por separado en optimal text segmentation for QR codes

Etapa 2: ajuste del número de Version

  • La longitud total en bits necesaria para representar la lista de segmentos depende del rango de Version
    • Version 1~9: 148 bits, 19 codewords
    • Version 10~26: 156 bits, 20 codewords
    • Version 27~40: 156 bits, 20 codewords
  • Un codeword se define como 8 bits, es decir, 1 byte
  • La capacidad de codewords de datos de un código QR varía según la Version y el nivel de corrección de errores
  • La entrada de ejemplo encaja en Version 1 con el nivel de corrección de errores seleccionado
  • El número de Version elegido finalmente es 1

Etapa 3: concatenación de segmentos, padding y creación de codewords

  • Se concatenan varias cadenas de bits para formar la cadena de bits de datos
    • Segment 0 mode: 0100, 4 bits
    • Segment 0 count: 00010001, 8 bits
    • Segment 0 data: 136 bits
    • Terminator: 0000, 4 bits
  • El conteo acumulado de bits es de 152 bits
  • En el ejemplo, tanto el bit padding como el byte padding son de 0 bits
  • El total de bytes de codewords de datos se divide en unidades de 8 bits y se muestra en hexadecimal
    • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30

Etapa 4: división en bloques, agregado de ECC e intercalado

  • Las estadísticas de bloques del ejemplo son las siguientes
    • Número de codewords de datos: 19
    • Número de bloques: 1
    • Codewords de datos por bloque corto: 19
    • Codewords de datos por bloque largo: no corresponde
    • Codewords ECC por bloque: 7
    • Número de bloques cortos: 1
    • Número de bloques largos: 0
  • La secuencia de codewords de datos se divide en bloques cortos y largos, y al final de cada bloque se calculan y agregan codewords ECC
  • El proceso matemático para calcular el código de corrección de errores Reed–Solomon se omite por ser largo, tedioso y poco interesante
  • La secuencia final de codewords se construye intercalando los codewords de datos y 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
  • La cadena de bits final que se dibujará en el escaneo en zigzag también se genera a partir de esta secuencia de codewords

Etapas 5~6: colocación de patrones fijos y codewords

  • En la etapa de patrones fijos se dibuja el timing pattern en la fila 6 y la columna 6
  • En las tres esquinas se coloca un finder pattern de 8×8 en cada una, incluyendo el separador
  • Alrededor de los finder se colocan format bits dummy temporales
  • En la etapa de colocación de codewords se calcula el escaneo en zigzag que empieza en la esquina inferior derecha
  • El escaneo en zigzag salta los módulos de función (function module) y visita los módulos que aún no han sido rellenados
  • Los módulos de datos, ECC y remainder se dibujan según los valores de bits de los codewords finales y el orden en zigzag
  • Por ejemplo, el codeword hexadecimal C5 es el binario 11000101 y genera la secuencia de módulos [dark, dark, light, light, light, dark, light, dark]

Etapas 7~9: aplicación de máscara y cálculo de penalización

  • Cada patrón de máscara afecta únicamente a los módulos no funcionales (non-function module)
  • La máscara se aplica con XOR sobre los módulos de datos, ECC y remainder
  • Los format bits reales se dibujan alrededor de los finder
  • La búsqueda de penalización examina los siguientes elementos
    • Runs horizontales de 5 o más módulos del mismo color
    • Runs verticales de 5 o más módulos del mismo color
    • Cajas 2×2 del mismo color
    • Patrones horizontales similares a finder
    • Patrones verticales similares a finder
    • Equilibrio entre módulos oscuros y claros
  • El tamaño y la proporción de colores del código QR de ejemplo son los siguientes
    • Longitud de un lado: 21
    • Módulos totales: 441
    • Módulos claros: 221
    • Módulos oscuros: 220
    • Proporción de módulos oscuros: 49.887%
    • Desviación respecto de la mitad: −0.113%
  • La penalización total de las 8 máscaras es la siguiente
    • Mask 0: 1204
    • Mask 1: 1134
    • Mask 2: 1084
    • Mask 3: 1081
    • Mask 4: 1121
    • Mask 5: 1100
    • Mask 6: 1189
    • Mask 7: 1137
  • La máscara con la penalización total más baja es Mask pattern 3

Código fuente

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-11-19
Comentarios en Hacker News
  • Da pena que en casi cualquier explicación en línea sobre códigos QR se omita el cálculo de corrección de errores Reed-Solomon
    Aquí también el autor dijo que es “largo, aburrido y no muy interesante”, pero como todos piensan así, ahora es bastante difícil encontrar información al respecto
    • Tomé una clase de teoría de códigos en posgrado, y fue la más rigurosa que llevé y difícil para los 5 que estábamos, pero me alegra haberla tomado
      Reed-Solomon se vio un poco después de la mitad del semestre, y la idea central es que se basa en polinomios. Si tienes suficientes puntos, el polinomio queda determinado exactamente, así que si agregas puntos extra, puedes reconstruirlo aunque algunos se pierdan
      El resto consiste en cómo aplicar esto a datos binarios, o sea, la parte de usar campos finitos; es matemáticamente hermosa, pero bastante compleja
    • Estos dos tutoriales sí explican el cálculo de corrección de errores
      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 y PagedOut! Issue #2 muestran cómo crear un código QR desde cero, incluyendo el cálculo de corrección de errores con división larga
    • Es largo y aburrido, pero en realidad es la parte más interesante de todo
    • Hay un artículo de Wikipedia relacionado
  • El video reciente de Veritasium, I used to hate QR codes. But they're actually genius, también trata este tema
    https://www.youtube.com/watch?v=w5ebcowAJD8
  • La recopilación de comentarios que recibió el autor es bastante interesante: https://www.nayuki.io/page/poor-feedback-from-readers
    • Burlarse de personas que no dominan el inglés y hacer comentarios que menosprecian a todo un país como si quienes enviaron esos correos fueran una muestra representativa de esa nación dice más del dueño del blog que de los remitentes
      El tono de los comentarios se siente fuertemente elitista. Revisé por encima el blog y pide donaciones en Bitcoin sugiriendo $3, sin parecer considerar que una parte importante podría perderse en comisiones
    • Aunque recibas mensajes que no te gusten, al quejarte es mejor no mezclar racismo casual con críticas al nivel de inglés de quien escribe
    • Burlarse de un inglés deficiente siempre es señal de estupidez. La gente inteligente también puede comportarse como tonta
    • Lo siento, pero el autor del blog parece una persona bastante desagradable
      Da la impresión de: “No, no puedes usar el código de mi repositorio de GitHub para el chatbot de tu proyecto universitario. Tus estándares de programación no llegan a los míos. Y además tu inglés es pésimo”
    • Entiendo lo difícil que puede ser mantener un blog personal. Te toca lidiar con toda clase de gente
      Por suerte también comparte aparte comentarios positivos: https://www.nayuki.io/page/decent-feedback-from-readers
  • Está bastante bien. Me gustaría ver también un decodificador explicado del mismo modo
    • También podría gustarte la guía de Piko y blinry sobre cómo leer códigos QR sin computadora: https://qr.blinry.org/
    • Totalmente de acuerdo. Siempre me sorprende lo rápido que los teléfonos descifran un código QR incluso cuando está oscuro, borroso y como un cuarto fuera de la pantalla
    • Sigo buscando una guía para implementar un lector de QR desde cero
      No quiero algo del estilo que aparece en Google de “solo conecta esta biblioteca de visión por computadora, mete la imagen y sale el resultado”
      Busco una guía que asuma que ya tienes los datos de imagen sin procesar decodificados y luego vaya implementando todos los algoritmos necesarios
  • Me gustó que hubiera una explicación. En lo personal solo quería hacerlo rápido, pero al buscar me salían sitios llenos de anuncios o sitios de “tienes que registrarte para usarlo”
    También encontré algunos en GitHub, pero tenían otros problemas, así que lo hice yo mismo rápidamente con una biblioteca bien diseñada que ya había usado antes, y me tomó como 15 minutos
    https://greggman.github.io/qr-code/
    Podría agregar más opciones, pero la verdad es que la mayoría de los usuarios probablemente no las necesita
    • Me alegra que te haya sido útil. Yo también llevaba tiempo queriendo probar una implementación por mi cuenta, pero lo único que encontraba eran paquetes ya hechos para Python o Golang
      Si alguien tiene material útil para entender la parte de corrección de errores relacionada con códigos QR, me gustaría conocerlo
  • Hace tiempo hice una implementación en Rust
    https://github.com/aabiji/qr
  • Si no es un artículo del año actual, es buena práctica poner el año del texto en el título, en este caso 2018
    • De acuerdo. En el enlace original yo no veía fecha, y ahora ya no se puede editar
  • Bien. Aprender cómo funcionan los códigos QR estaba en mi lista de pendientes desde hace tiempo, y fue un buen artículo introductorio
  • Ahora que ya sabes cómo funciona, también puedes usarlo en consultas SQL: https://github.com/Florents-Tselai/pgQR