Sommaire
En bref : un QR code ne stocke pas seulement son message. Il y ajoute des octets de réserve calculés à partir de lui, la correction d’erreurs de Reed-Solomon, les mêmes maths que sur les CD audio, si bien qu’un lecteur peut reconstruire des octets manquants ou faux. Vous choisissez combien : quatre niveaux, L, M, Q et H, restaurent environ 7, 15, 25 et 30 % des mots de code, et plus d’octets de réserve font un code plus grand. Voilà pourquoi un logo au milieu peut marcher : pour le lecteur, c’est un dégât. Les trois carrés des coins, c’est autre chose : ce ne sont pas des données, ils servent au lecteur à trouver le code et à le redresser, et la plupart des lecteurs en ont besoin.
Déchiré, taché, et il se scanne
DENSO WAVE, qui a mis au point le QR code : « QR Code has error correction capability to restore data if the code is dirty or damaged. » (Le QR code sait corriger les erreurs et restaurer les données si le code est sale ou abîmé.) Et dans sa liste de caractéristiques : « Data can be restored even if the symbol is partially dirty or damaged. » (Les données peuvent être restaurées même si le symbole est en partie sale ou abîmé.)
Le code de la vidéo est réel : il contient oliverz.dev. Déchiré à un coin, taché sur un bord et couvert par un logo au milieu, 13 de ses 44 mots de code sont faux, et il se décode quand même (testé avec deux décodeurs, jsQR et ZXing).
Des octets de réserve, calculés à partir du message
DENSO WAVE : « The QR Code error correction feature is implemented by adding a Reed-Solomon Code… to the original data. » (La correction d’erreurs du QR code consiste à ajouter un code de Reed-Solomon aux données d’origine.) Le Computer Science Field Guide de l’université de Canterbury le dit plus simplement : « it adds extra bits to the data so that errors can be corrected. » (Il ajoute des bits en plus aux données pour que les erreurs puissent être corrigées.)
L’unité, c’est le mot de code. DENSO WAVE : « codeword is a unit that constructs the data area. One codeword of QR Code is equal to 8 bits. » (Le mot de code est l’unité qui compose la zone de données. Un mot de code du QR code vaut 8 bits.) Et le CS Field Guide : « Each black or white square (“dot” or “module”) corresponds to one bit of data. » (Chaque carré noir ou blanc, « point » ou « module », correspond à un bit de données.) Huit modules font donc un octet.
Ces maths ne sont pas nouvelles. DENSO WAVE : « Reed-Solomon Code is a mathematical error correction method used for music CDs etc. The technology was originally developed as a measure against communication noise for artificial satellites and planetary probes. » (Le code de Reed-Solomon est une méthode mathématique de correction d’erreurs utilisée notamment sur les CD audio. La technique a d’abord été conçue contre le bruit des communications des satellites artificiels et des sondes planétaires.)
Deux octets de réserve par octet corrigé
DENSO WAVE : « Reed-Solomon Code requires twice the amount of codewords to be corrected. » (Le code de Reed-Solomon demande deux fois plus de mots de code qu’il y en a à corriger.) Le CS Field Guide : « The maximum number of errors that a Reed-Solomon code can correct is one half of the amount of extra error correcting data added to it. » (Le nombre maximal d’erreurs qu’un code de Reed-Solomon peut corriger est la moitié des données de correction ajoutées.)
Notre code, au niveau le plus haut, a 16 mots de code pour le message et 28 de réserve, 44 en tout. La moitié de 28, c’est 14 : il peut donc réparer jusqu’à 14 mots de code faux. 14 sur 44, c’est environ 32 % (notre calcul), le « Approx. 30% » (environ 30 %) de DENSO. Dans notre test, la limite tombait exactement là : avec 14 mots de code faux, il se lisait ; avec 15, aucun résultat.
Aucun résultat, pas un résultat faux. Le CS Field Guide : « they won’t read the data incorrectly, instead they just refuse to give any data at all, rather than giving you incorrect data. » (Ils ne liront pas les données de travers : ils refusent tout simplement de donner quoi que ce soit plutôt que de vous donner des données fausses.)
Quatre niveaux : de 7 à 30 %
Extrait de la présentation de la norme (ISO/IEC 18004) par DENSO WAVE : « Level L Level M Level Q Level H Approx. 7% of codewords can be restored. Approx. 15% of codewords can be restored. Approx. 25% of codewords can be restored. Approx. 30% of codewords can be restored. » (Niveaux L, M, Q, H : environ 7 % des mots de code peuvent être restaurés ; environ 15 % ; environ 25 % ; environ 30 %.)
Le pourcentage compte des mots de code, pas la surface visible : « *Data restoration rate for total codewords » … « QR Code therefore represents its error correction rate as a ratio of the total codewords. » (*Taux de restauration rapporté à l’ensemble des mots de code… Le QR code exprime donc son taux de correction comme une part de l’ensemble des mots de code.)
Plus d’octets de réserve, ça prend de la place. DENSO WAVE : « Raising this level improves error correction capability but also increases the amount of data QR Code size. » (Monter ce niveau améliore la correction d’erreurs, mais augmente aussi la quantité de données et la taille du QR code.) Et : « as the amount of data increases, more modules are required to comprise QR Code, resulting in larger QR Code symbols. » (Quand la quantité de données augmente, il faut plus de modules pour former le QR code, et les symboles grandissent.) Nos quatre codes d’oliverz.dev, mots de code du message + de réserve :
- L : 19 + 7, 21 × 21 modules
- M : 16 + 10, 21 × 21 modules
- Q : 13 + 13, 21 × 21 modules
- H : 16 + 28, 25 × 25 modules (au niveau H, les 11 octets d’« oliverz.dev » ne tiennent plus en 21 × 21)
Un logo, c’est un dégât qu’il répare
Voilà pourquoi un logo au milieu peut marcher : le lecteur le traite comme un dégât et reconstruit ce qu’il cache. Sur notre code H, un logo de 7 × 7 modules rend faux 9 de ses 44 mots de code, sous sa limite de 14.
Mais ce n’est pas gratuit : il consomme les octets de réserve. La FAQ de DENSO WAVE, sur les codes en couleur ou avec une illustration : « If it is deformed, the QR Code's error correction function is invoked where even a tiny missing or smeared part renders the reading operation impossible, or the response of the operation may become slow. » (S’il est déformé, la correction d’erreurs du QR code entre en jeu, et la moindre petite partie manquante ou bavée peut alors rendre la lecture impossible, ou la ralentir.)
Ne couvrez pas les coins
Les trois grands carrés ne sont pas des données. DENSO WAVE : « QR Code accomplishes this task through position detection patterns located at the three corners of the symbol. » (Le QR code y parvient grâce à des motifs de détection de position placés à trois coins du symbole.) Son historique du code raconte qu’avec eux, « the orientation of their code could be determined regardless of the angle of scanning, which could be any angle out of 360° » (on pouvait déterminer l’orientation du code quel que soit l’angle de lecture, n’importe lequel sur 360°).
Le CS Field Guide : « Don’t colour in near the three large squares in the corners, as most QR scanners need these to align the image. » (Ne coloriez pas près des trois grands carrés des coins : la plupart des lecteurs QR en ont besoin pour aligner l’image.)
Dans notre test, un petit autocollant de 3 × 3 modules au centre d’un carré de coin a suffi à faire échouer les deux décodeurs, sans toucher un seul octet de données. Le logo couvre 49 modules et se scanne ; l’autocollant en couvre 9 et ne se scanne pas.
À retenir
- Un QR code stocke son message et des octets de réserve tirés de lui (Reed-Solomon) : un lecteur reconstruit donc les octets déchirés, tachés ou cachés.
- Vous choisissez combien : L, M, Q, H, environ 7 à 30 % des mots de code ; plus d’octets de réserve, un code plus grand. Un logo au milieu est un dégât que couvrent les octets de réserve.
- Les trois carrés des coins ne sont pas des données : ils servent au lecteur à trouver le code et à le redresser, et la plupart des lecteurs en ont besoin.
Sources
- DENSO WAVE : Error Correction Feature, QR Code Standardization, What is a QR Code?, Information capacity and versions of the QR Code, History of QR Code, FAQ
- Université de Canterbury (University of Canterbury), Computer Science Field Guide, QR codes
La vidéo est animée en code et le script a été écrit avec l’aide de l’IA ; chaque citation ci-dessus est vérifiée dans sa source, et le chiffre marqué « notre calcul » est le nôtre. Les codes sont réels (générés, puis décodés avec jsQR et ZXing), tout comme leurs octets et leurs nombres de mots de code. Illustratif : la déchirure, la tache et le logo (une marque générique, dessinée exactement sur les modules testés), le viseur de l’appareil photo et le code incliné, le même code dessiné en perspective. L’usure réelle est moins nette qu’un dégât dessiné le long des modules. « QR Code » est une marque déposée de DENSO WAVE INCORPORATED. La vidéo est narrée en anglais. Réalisée avec Shotloop, mon app Mac gratuite pour faire des vidéos explicatives en code, corrigées un plan à la fois.
