Voici à quoi ressemble un des tags qu'on utilise:
%pylab inline
Populating the interactive namespace from numpy and matplotlib
from hampy import HammingMarker
marker = HammingMarker(id=206135218)
imshow((1-marker.toimage(size=180))*255, cmap='Greys', interpolation='nearest')
<matplotlib.image.AxesImage at 0x1088cd0d0>
Ce sont des carrées de 9x9. Il y a une bordure noire (utile pour la détection vidéo) tout autour ce qui laisse un carré de 7x7 pixels.
Chacune des 7 lignes est en fait un code de Hamming. Les détails sont dispo sur la page wiki : https://en.wikipedia.org/wiki/Hamming(7,4)
Chaque ligne comprend en fait 4 bits (pixels) d'informations et 3 bits de parités (détails plus bas) permettant de vérifier qu'il n'y a pas eu d'erreur de détection ou de transmission.
Soit une ligne composée des pixels suivants:
$L = [p1, p2, p3, p4, p5, p6, p7]$
Seul, ${p3, p5, p6, p7}$ contiennent les informations de données. Les autres bits sont calculés comme suit:
$p1 = (p3 + p5 + p7) \mod 2$
$p2 = (p3 + p6 + p7) \mod 2$
$p4 = (p5 + p6 + p7) \mod 2$
Pour résumer, chaque ligne contient 4 bits d'information et 3 de vérification. On a donc pour les 7 lignes : 7 * 4 bits d'information.
Ce qui donne: $2 ^ (7 * 4) = 2^8 * 2^(10*2) \approx 256*10^6 $ Soit beaucoup :-)
Si on veut écrire notre prénom préféré:
D = 4
I = 9
D = 4
I = 9
E = 5
R = 18
DIDIER = 4949518
Note: La réprésentation n'a aucun sens le décodage serait impossible. On ne peut pas différencier 2-6 de 26 par exemple. Mais c'est juste pour donner un exemple simple, on pourra réfléchir à coder des informations plus intéressantes.
On convertit ce nombre en binaire:
from numpy import binary_repr
s = binary_repr(DIDIER, width=28)
s
'0000010010111000011000001110'
La même chose sur 7 lignes:
from numpy import array
D = array(list(s), dtype=int).reshape(7, 4)
D
array([[0, 0, 0, 0], [0, 1, 0, 0], [1, 0, 1, 1], [1, 0, 0, 0], [0, 1, 1, 0], [0, 0, 0, 0], [1, 1, 1, 0]])
Voilà nos 7 * 4 bits d'information !
On calcule les bits de parité:
P = array([[(D[i, 0] + D[i, 1] + D[i, 3]) % 2,
(D[i, 0] + D[i, 2] + D[i, 3]) % 2,
(D[i, 1] + D[i, 2] + D[i, 3]) % 2
] for i in range(7)])
P
array([[0, 0, 0], [1, 0, 1], [0, 1, 0], [1, 1, 0], [1, 1, 0], [0, 0, 0], [0, 0, 0]])
On combine tout ça en un même tableau en respectant bien les indices:
from numpy import hstack
CODE = hstack((P[:, :2],
D[:, :1],
P[:, 2:3],
D[:, 1:]))
CODE
array([[0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 1, 1, 0, 0], [0, 1, 1, 0, 0, 1, 1], [1, 1, 1, 0, 0, 0, 0], [1, 1, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 1, 0]])
Ou la même chose sous forme d'image:
%pylab inline
imshow(CODE, cmap='gray', interpolation='nearest')
Populating the interactive namespace from numpy and matplotlib
<matplotlib.image.AxesImage at 0x108b8a8d0>
On rajoute la bordure noire:
TAG = zeros((9, 9))
TAG[1:-1, 1:-1] = CODE
imshow(TAG, cmap='gray', interpolation='nearest')
<matplotlib.image.AxesImage at 0x108c19d10>
Et voilà !
Pour le décodage et la vérification, on fait exactement la même chose dans l'autre sens.
Je n'ai pas non plus abordé les questions de rotations du code de 90°, mais pour résumer on teste simplement les 4 possibilités et seul un des codes sera valide (sans erreur).
Afin de faire tout ça plus simplement (au moins d'un point de vue informatique), tout cela est fait à l'aide de matrices.
Si on reprend nos données:
D
array([[0, 0, 0, 0], [0, 1, 0, 0], [1, 0, 1, 1], [1, 0, 0, 0], [0, 1, 1, 0], [0, 0, 0, 0], [1, 1, 1, 0]])
On définit deux matrices de passage G (codage) et H (décodages):
G = array(((1, 1, 0, 1),
(1, 0, 1, 1),
(1, 0, 0, 0),
(0, 1, 1, 1),
(0, 1, 0, 0),
(0, 0, 1, 0),
(0, 0, 0, 1)))
H = array(((0, 0, 0, 1, 1, 1, 1),
(0, 1, 1, 0, 0, 1, 1),
(1, 0, 1, 0, 1, 0, 1)))
On a alors directement:
# Pour coder
CODE = numpy.dot(G, D.T).T % 2
CODE
array([[0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 1, 1, 0, 0], [0, 1, 1, 0, 0, 1, 1], [1, 1, 1, 0, 0, 0, 0], [1, 1, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 1, 0]])
# Pour vérifier un code
dot(H, CODE.T).T % 2
array([[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]])
Les 1 de la matrice ci dessus donne les indices des pixels erronés. Ici tout est bon.
Alors ça peut intéresser des lycéens ?