Llegeixo al Butlletí de la Societat Catalana de Matemàtiques de l’Institut d’Estudis Catalans un article sobre els Codis detectors i correctors d’errors i algunes de les seves aplicacions a la socieatat de la informació de M. Villanueva i C. Fernández-Córdoba que m’ha semblat interessant.
Segons el Resum:
En les transmissions digitals d’informació d’un emissor a un receptor a
través d’un canal, normalment es produeixen errors. En aquest article s’exposen els
conceptes i resultats més importants de la teoria de codis detectors i correctors d’errors,
que estudia mètodes eficients per garantir una transmissió exacta de la informació.
Primer es descriuen alguns exemples quotidians de codis detectors d’errors inclosos
en el DNI, l’ISBN, l’IBAN i l’EAN. A continuació, es presenta la teoria clàssica dels codis
correctors d’errors, que inclou els codis lineals i, dins d’aquests, els codis cíclics, que
resulten més eficients a l’hora de codificar. També es descriuen les dues famílies més
importants de codis cíclics, els BCH i Reed-Solomon, que permeten descodificar també
de forma eficient. Finalment, es mostren dues aplicacions històriques, en les memòries
d’ordinador i en la transmissió de fotografies a l’espai, i dues aplicacions més recents,
en els codis QR i en l’emmagatzematge distribuït.
Codi DNI
El codi del document nacional d’identitat (DNI) consisteix en un número de 8 xifres decimals seguit d’una lletra. Aquesta lletra, de fet, representa la redundància que permetrà detectar els errors més freqüents en escriure el número. La lletra s’assigna segons el valor que resulta de calcular el número del DNI a Z23, o el que és el mateix, segons el residu que s’obté en dividir-lo per 23, d’acord amb les equivalències que es mostren en la taula 1.
El càlcul es realitza a Z23. Es pren un número primer per tal de treballar en un cos finit. A més, s’exclouen les lletres I, O i U, perquè aquestes es poden confondre més fàcilment amb l’1, el 0 i la lletra V, respectivament. Podem simplificar els càlculs si tenim precalculades les potències de 10 a Z23. Així, com que 10^2 = 8, 10^3 = 11, 10^4 = 18, 10^5 = 19, 10^6 = 6 i 10^7 = 14 a Z23, calcular el número del DNI a Z23 equival a calcular x0 + 10×1 + 8×2 + 11×3 + 18×4+19×5+6×6+14×7 a Z23, on x7x6x5x4x3x2x1x0 = E^7 i=0 10ixi representa el número del DNI.
Exemple 1. La lletra del DNI corresponent al número 34149351 és D, ja que 34149351 = 9 a Z23, o equivalentment, 14 · 3 + 6 · 4 + 19 · 1 + 18 · 4 + 11 · 9 + 8 · 3 + 10 · 5 + 1 = 9 a Z23, i la lletra corresponent al valor 9 és D d’acord amb la taula 1.
Aquest codi permet detectar si hi ha hagut un error en un dels dígits del DNI, o bé si hi ha hagut una transposició entre dos dígits [6]. En canvi, si n’hi ha dos o més, no sempre es poden detectar. També permet recuperar un dels dígits si aquest no es visualitza correctament, simplement resolent una equació lineal a Z23.
Exemple 2. Continuant amb el DNI de l’exemple 1, què passa si en escriure el DNI ens equivoquem en un dígit i escrivim, per exemple, 34249351D? Com Codis detectors i correctors d’errors 57 que 34249351 = 5 a Z23 i la lletra corresponent al 5 és la M, podem detectar que hi ha hagut un error, i repassar l’escriptura d’aquest DNI.
I si ens equivoquem en dos dígits que s’han intercanviat de posició, i escrivim, per exemple, 34419351D? En aquest cas, de nou, en calcular 34419351 = 12 a Z23, podem detectar l’error ja que 12 correspon a la lletra N.
Finalment, què podem fer si un dels dígits és borrós, per exemple, si tenim 341493✷1D on el setè dígit no es reconeix? En aquest cas, podem plantejar l’equació lineal següent a Z23, 14·3+6·4+19·1+18·4+11·9+8·3+10·x1+1 = 9, o sigui 10×1 = 4 a Z23. Com que l’invers de 10 és 7, tenim que x1 = 4·7 = 28 = 5 a Z23. Per tant, el dígit de la posició setena és 5 i obtenim el DNI 34149351D.
Article sencer a : https://www.raco.cat/index.php/ButlletiSCM/article/view/359803
La catifa voladora 