Negli ultimi anni sono iniziati a comparire un po’ ovunque, in modo sempre più pervasivo, dei quadrati in bianco e nero, ormai noti a tutti come codici QR o, se vi piace di più l’originale inglese, QR-code, dove QR sta per quick response, in riferimento alla rapidità con cui lo si decifra. Inquadrando il codice con un’apposita app dello smartphone, come la diffusissima Google Lens, si ottengono link a nuovi contenuti, video, informazioni di ogni genere. Il QR-code è una versione bidimensionale del tradizionale codice a barre utilizzato per indicare, ad esempio, i prodotti che compriamo al supermercato.
L’idea originale dietro i QR-code si deve alla compagnia giapponese Denso Wave, che li utilizzò per riconoscere e tracciare le parti delle automobili Toyota, dato che i codici potevano contenere più dati del già diffuso sistema dei codici a barre. A partire dal 1999 la Denso Wave ha distribuito i codici QR sotto licenza libera e questo ha favorito la diffusione del nuovo strumento che è “esploso” con l’avvento degli smartphone.
Per qualche persona, sapere che “il QR-code è la versione migliore del codice a barre” potrebbe essere una spiegazione sufficiente, ma immaginiamo che i lettori di questa rivista siano curiosi di sapere come funzioni più nel dettaglio e cosa ci sia di così “migliore”. Dietro il puzzle di quadrati in bianco e nero c’è, ovviamente, della matematica.
Prima di parlare del codice in sé, partiamo dall’idea di base schematizzata dall’immagine sotto; affinché il meccanismo funzioni, abbiamo bisogno di:
- un encoder che trasformi il testo che si vuole trasmettere nel QR-code;
- un decoder che scansioni il codice QR e trasformi la sequenza di “misteriosi” quadratini in bianco e nero nel messaggio originale.
Il decoder è un’app, e per questo il QR-code non è comodo da leggere per un occhio umano, mentre è ottimizzato per un occhio artificiale dotato di apposito decoder.
La diffusione dei QR-code non è legata solamente alla quantità di dati che possono contenere ma alla loro natura di codici auto-correttivi. Tali codici hanno la capacità di restare decodificabili anche se scansionati sotto pessime condizioni di luminosità, rovinati dalle intemperie, con parti strappate, e questo deriva dalla modalità con cui sono salvati i dati al loro interno, legata alla teoria degli algoritmi di correzione dati.
I QR-Code sono basati su una classe di complessi algoritmi chiamati BCH (dagli ideatori Bose-Chaudhuri-Hocquenghem) che, aggiungendo del testo “ridondante” in coda al messaggio, possono fare in modo che questo sia decodificabile anche in presenza di errori alla ricezione: in base al formato di QR-code, il decoder può ricostruire il messaggio anche se ne è danneggiato il 7%, livello di correzione basso, o fino al 30%, per il livello di correzione alto. I codici di correzione errori, come il BCH, sono basati su una branca della matematica sviluppata nel 1800 da un giovane rivoluzionario francese, Evariste Galois, ben prima dell’invenzione degli smartphone, e mostra quanto alcune idee astratte siano solo in attesa di trovare un’applicazione pratica.
Per il seguito, facciamo riferimento allo schema a destra in Figura 2:
Esistono 40 versioni dei codici, in base alla loro dimensione. Si va da quelli di versione 1, di 21×21 pixel, come quello in figura, fino alla versione 40, da 177×177 pixel. La differenza è naturalmente nella quantità di informazione contenuta: ad esempio, i codici di versione 1 possono contenere solo 26 byte (un byte è una sequenza di otto 0 e 1), permettendo di immagazzinare solo piccole frasi.
I tre grandi quadrati neri sono locator patterns, o schemi di posizione, e servono per individuare la posizione corretta: il decoder riconosce che il codice è dritto quando l’unico angolo senza quadratoni è quello in basso a destra.
Per codici più grandi sono presenti altri quadrati, più piccoli, detti alignment patterns (schemi di allineamento), disposti in posizioni specifiche e con funzione simile. I moduli bianchi e neri alternati sono timing patterns (schemi di temporizzazione) e permettono al decoder di determinare la larghezza del singolo modulo. Timing, alignment e locator patterns sono fissi e non contengono informazione.
Le zone in arancione e rosso sono per il formato e indicano il tipo di maschera applicata al codice e il livello di correzione: prima di accedere all'informazione è necessario infatti smascherare il codice dato che, per evitare caratteristiche nel disegno in grado di confondere lo scanner, l’encoder applica una maschera a scelta fra le otto diverse disponibili (vd Figura 3), in modo da minimizzare gli eventuali problemi nel risultato.
Dopo aver tolto la maschera, il decoder riconosce nella zona arancione le informazioni sul livello di correzione, che delinea la quantità di byte, tra i 26, dedicati al messaggio; i restanti servono per la correzione di errori; creare un codice che si autocorregge ha un peso, e maggiore è la capacità di ripararsi, più saranno i byte utilizzati per la correzione a spese di quelli utilizzabili per il testo vero e proprio.
Tolta la maschera e scoperto il formato, ci si può interessare ai 26 byte di informazione (quelli in verde in Figura 2), scoprendo il messaggio effettivo. I bit dei dati sono letti a partire dall'angolo in basso a destra e muovendosi a zig-zag in tutta la parte verde. I byte che contengono il messaggio sono i primi, mentre quelli ridondanti per la correzione sono in fondo. Il testo originale si ottiene quindi leggendo nel giusto ordine la sequenza di 0 e 1 della parte verde; i primi indicano la modalità di codifica del testo: numerica, alfanumerica, byte o kanji, i successivi il testo.
L’idea originale dietro i QR-code si deve alla compagnia giapponese Denso Wave, che li utilizzò per riconoscere e tracciare le parti delle automobili Toyota, dato che i codici potevano contenere più dati del già diffuso sistema dei codici a barre. A partire dal 1999 la Denso Wave ha distribuito i codici QR sotto licenza libera e questo ha favorito la diffusione del nuovo strumento che è “esploso” con l’avvento degli smartphone.
Figura 1: schema del funzionamento di encoder e decoder per un QR-code
Per qualche persona, sapere che “il QR-code è la versione migliore del codice a barre” potrebbe essere una spiegazione sufficiente, ma immaginiamo che i lettori di questa rivista siano curiosi di sapere come funzioni più nel dettaglio e cosa ci sia di così “migliore”. Dietro il puzzle di quadrati in bianco e nero c’è, ovviamente, della matematica.
Prima di parlare del codice in sé, partiamo dall’idea di base schematizzata dall’immagine sotto; affinché il meccanismo funzioni, abbiamo bisogno di:
- un encoder che trasformi il testo che si vuole trasmettere nel QR-code;
- un decoder che scansioni il codice QR e trasformi la sequenza di “misteriosi” quadratini in bianco e nero nel messaggio originale.
Il decoder è un’app, e per questo il QR-code non è comodo da leggere per un occhio umano, mentre è ottimizzato per un occhio artificiale dotato di apposito decoder.
La diffusione dei QR-code non è legata solamente alla quantità di dati che possono contenere ma alla loro natura di codici auto-correttivi. Tali codici hanno la capacità di restare decodificabili anche se scansionati sotto pessime condizioni di luminosità, rovinati dalle intemperie, con parti strappate, e questo deriva dalla modalità con cui sono salvati i dati al loro interno, legata alla teoria degli algoritmi di correzione dati.
I QR-Code sono basati su una classe di complessi algoritmi chiamati BCH (dagli ideatori Bose-Chaudhuri-Hocquenghem) che, aggiungendo del testo “ridondante” in coda al messaggio, possono fare in modo che questo sia decodificabile anche in presenza di errori alla ricezione: in base al formato di QR-code, il decoder può ricostruire il messaggio anche se ne è danneggiato il 7%, livello di correzione basso, o fino al 30%, per il livello di correzione alto. I codici di correzione errori, come il BCH, sono basati su una branca della matematica sviluppata nel 1800 da un giovane rivoluzionario francese, Evariste Galois, ben prima dell’invenzione degli smartphone, e mostra quanto alcune idee astratte siano solo in attesa di trovare un’applicazione pratica.
Figura 2: sopra, un codice QR di versione 1 e sotto la sua struttura generale.
Esistono 40 versioni dei codici, in base alla loro dimensione. Si va da quelli di versione 1, di 21×21 pixel, come quello in figura, fino alla versione 40, da 177×177 pixel. La differenza è naturalmente nella quantità di informazione contenuta: ad esempio, i codici di versione 1 possono contenere solo 26 byte (un byte è una sequenza di otto 0 e 1), permettendo di immagazzinare solo piccole frasi.
I tre grandi quadrati neri sono locator patterns, o schemi di posizione, e servono per individuare la posizione corretta: il decoder riconosce che il codice è dritto quando l’unico angolo senza quadratoni è quello in basso a destra.
Per codici più grandi sono presenti altri quadrati, più piccoli, detti alignment patterns (schemi di allineamento), disposti in posizioni specifiche e con funzione simile. I moduli bianchi e neri alternati sono timing patterns (schemi di temporizzazione) e permettono al decoder di determinare la larghezza del singolo modulo. Timing, alignment e locator patterns sono fissi e non contengono informazione.
Le zone in arancione e rosso sono per il formato e indicano il tipo di maschera applicata al codice e il livello di correzione: prima di accedere all'informazione è necessario infatti smascherare il codice dato che, per evitare caratteristiche nel disegno in grado di confondere lo scanner, l’encoder applica una maschera a scelta fra le otto diverse disponibili (vd Figura 3), in modo da minimizzare gli eventuali problemi nel risultato.
Figura 3: le 8 possibili maschere applicabili a un codice QR
Dopo aver tolto la maschera, il decoder riconosce nella zona arancione le informazioni sul livello di correzione, che delinea la quantità di byte, tra i 26, dedicati al messaggio; i restanti servono per la correzione di errori; creare un codice che si autocorregge ha un peso, e maggiore è la capacità di ripararsi, più saranno i byte utilizzati per la correzione a spese di quelli utilizzabili per il testo vero e proprio.
Tolta la maschera e scoperto il formato, ci si può interessare ai 26 byte di informazione (quelli in verde in Figura 2), scoprendo il messaggio effettivo. I bit dei dati sono letti a partire dall'angolo in basso a destra e muovendosi a zig-zag in tutta la parte verde. I byte che contengono il messaggio sono i primi, mentre quelli ridondanti per la correzione sono in fondo. Il testo originale si ottiene quindi leggendo nel giusto ordine la sequenza di 0 e 1 della parte verde; i primi indicano la modalità di codifica del testo: numerica, alfanumerica, byte o kanji, i successivi il testo.
Bibliografia
- Tiwari, Sumit. 2016. “An Introduction to QR Code” Technology. 39-44. 10.1109/ICIT.2016.021.
