15 d’octubre del 2015

Descobrir l'error i corregir-lo

Swiffy Output Quan un lector de codi de barres llegeix els nombres que codifiquen un producte sap si la lectura que ha fet és correcta o no perquè realitza uns càlculs determinats amb les primeres dotze xifres per obtenir-ne la tretzena. Si coincideixen la lectura està ben feta. Per altra banda, les targetes de crèdit o el números de compte corrent tenen també uns dígits de control que s'obtenen a partir de les altres xifres del nombre. Serveixen per autentificar-los i eliminar possibles errors o falsificacions. Podeu llegir més sobre els càlculs que es fan en cada cas al web del Calaix +ie. Una cosa és clara: aquests codis detecten un error, però no el corregeixen.

En una transmissió "digital", com la TDT o la telefonia mòbil, és molt possible que les interferències modifiquin les seqüències de uns i zeros de la transmissió. No en parlem de la connexió telefònica d'internet. Ens interessa "netejar" aquestes interferències i reconstruir el codi original si ha estat alterat: hem de detectar l'error i corregir-lo. Si, per exemple, enviem duplicada una seqüència, comparem les dues versions i són diferents, no sabrem ni quina és la bona ni si les dues són incorrectes. Ens pot passar el mateix si tripliquem una seqüència. Dues poden haver "patit" la mateixa interferència i ser correcta la diferent. O poden ser les tres incorrectes. Per tant, cal fer un altre "invent" i que sigui més econòmic en termes de transmissió. I l'invent ja està fet. Es coneixen com a codis de detecció i correcció d'errors. Bàsicament consisteixen en afegir una cadena de bites a la seqüència origen que, amb un algoritme concret, comprovi el missatge i el modifiqui si no s'ajusta al que "tocaria".

El 22 de setembre de 2015, en una conferència realitzada al MMACA, el professor Jin Akiyama va presentar un petit joc matemàtic que il·lustra perfectament un d'aquests codis correctors. També l'explica Clara Grima a una de les seves "mateaventures" (Adivinando en 55 segundos). L'únic que afegiré de nou serà un model interactiu ampliat del joc perquè podeu jugar i algunes explicacions lleugerament diferents.

Jin Akiyama
El joc matemàtic és una modificació del força conegut conjunt de targetes binàries per endevinar un nombre. Bàsicament la versió clàssica del joc es basa en que qualsevol nombre es pot descompondre en potències de 2. Així si vull endevinar nombres entre 1 i 31 faré el següent:
  • Fabricaré 5 targetes amb 16 caselles.
  • Encapçalaré les targetes amb els nombres 1, 2, 4, 8 i 16
  • Descompondré els nombres de l'1 al 31 en sumes de potències de 2 (1, 2, 4, 8 i 16). Per exemple el 6=2+4,13=1+2+8, 23=1+2+4+16...
  • Col·locaré els nombres de l'1 al 31 a les targetes encapçalades pels nombres que intervenen en la seva descomposició. El 6 estarà a les targetes de 2 i el 4, el 13 a la de l'1, el 2 i el 8, etc.
  • Amb les meves 5 targetes li demanaré a alguna persona que pensi un número de l'1 al 31 i que m'indiqui a quines targetes està el nombre pensat. Si, per exemple, m'indica les targetes encapçalades pel 2, el 8 i el 16, per endevinar el nombre pensat només haig de sumar mentalment aquests tres nombres 2+8+16=26.
Podeu veure un exemple interactiu d'aquestes targetes a la pàgina Càlculus, així com descobrir, amb més detall, com es construeixen.

Però...

... què passa si ens diuen una mentida?
Podem fabricar un joc nou de targetes, tot afegint unes quantes targetes de control, que ens permetin admetre una mentida i, tot i així, endevinar el nombre pensat. És el magnífic exemple de codi detector-corrector d'errors que se'ns va presentar a la conferència.

Però primer juguem.

  • Pensa un nombre de l'1 al 31
  • Després, clicant sobre elles, assenyala les targetes en les que estigui el número que has pensat.
  • Pots mentir, si vols, una vegada. Però una sola. Pots assenyalar una targeta de més o deixar d'assenyalar-ne una de les que contingui el teu número.
  • Després clica el botó "Endevinar" i, a més d'endevinar el número, t'assenyalarem la targeta en que has mentit.


I com ho descobrim?

Ho explicarem amb uns exemples.

  • Exemple 1
Imaginem que algú, després de pensar el nombre, ens dóna aquesta tria de targetes.

El quefarem és comptar quantes targetes tenim amb la lletra A, quantes amb la B, amb la C i amb la D. Les lletres que ens surtin amb una quantitat senar ens indiquen la "mentida". Si tots els nombres sortissin parells significaria que no ens han mentit.

Targetes triades A B C D
ACD   ABD   ABCD   B 3 3 2 3

Ara sabem que l'engany ha estat a la targeta ABD i no l'hem de tenir en compte. La targeta B, que és de control, tampoc l'hem de mirar per endevinar el nombre. Així ens queden les targetes ACD i ABCD que, amb els números que l'encapçalen, ens indiquen el número pensat:

1 + 16 = 17
  • Exemple 2
Mirem aquesta segona tria.


Targetes triades A B C D
ACD   ABC   C 2 1 3 1

L'engany ha estat a la targeta BCD i no ens l'han dita. La targeta C no la tindrem en compte perquè és de control. Les targetes vàlides per endevinar el nombre seran ACD, ABC i BCD (l'amagada):

1 + 8 + 2 = 11
  • Exemple 3

Targetes triades A B C D
ACD   ABD   ABCD   D 3 2 2 4

L'engany és la targeta A. Ja que les targetes de control no afecten per endevinar el nombre la ignorem i sumem els valors de les altres tres targetes.

1 + 4+ 16 = 21

Com es construeixen les targetes i per què descobrim la targeta "engany"?

La millor manera de veure-ho és confeccionant un joc de targetes. Farem un joc més petit, per endevinar nombres de l'1 al 7. Així amb sis targetes en tindrem prou.

Primer de tot fem les tres targetes binàries "normals", les que serveixen per endevinar el nombre. Les anomenarem AB, BC i CD (les combinacions de les tres lletres agafades de dos en dos)

Ara construirem les targetes de control. Començarem per la targeta de control A. Fixem-nos en com decidirem quins nombres hi van. Per començar només hem de mirar les columnes que tenen la lletra A: la 1a (AB) i la 3a (AC). I ara anem nombre a nombre.
  • El nombre 1 apareix una sola vegada (a la targeta AC). Com que és un nombre senar posarem una creueta.
  • El nombre 2 no apareix cap vegada a les columnes que hem de mirar. Considerant el 0 com a parell no hem de marcar la casella.
  • El nombre 3 apareix una vegada (a la columna AC). En ser senar el marquem.
  • El nombre 4 també apareix una sola vegada (columna AB). Senar: el marquem.
  • I així continuem amb els altres nombres: marcant si és senar i deixant en blanc si és parell.

  • Si ens hi fixem (i aquesta és la clau) ara tenim sempre una quantitat parell de lletres A (l'1 → 2 vegades, el 2 → 0 vegades, el 3 → 2, el 4 → 2, el 5 → 2, el 6 → 2, el 7 → 2). Només ens cal fer la targeta A amb els nombres que tenen la creu.

Ara, per fer la targeta de control B, hem de fer el mateix. Ens fixarem en la 1a i 2a columnes perquè són les que contenen la B (AB i BC), marcarem els nombres que apareixen una quantitat senar de vegades i els escriurem a les targeta B.
Per construir la targeta de control C repetim el procés, però fixant-nos en les columnes que tenen una C, la 2a i la 3a (BC i AC).


Ja ho tenim:

Tots els nombres "tenen" un nombre parell de lletres. Si ens enganyen trenquen aquesta paritat. Per això les lletres senars ens indiquen en quina targeta ens han mentit. Descobrim l'engany (l'error) i, com que sabem on està, el podem corregir.

  • I a l'aula?
Jugar amb les targetes i explicar el funcionament ja és suficient per ajudar a conèixer aquesta mena d'algoritmes de detecció i correcció d'errors. Però encara és millor fer construir un joc, per exemple amb els nombres de l'1 al 15. I encara millor si expliquem com fer les targetes però intentem que ells donin l'explicació de per què funcionen.

Les targetes binàries simples, sense enganys ni control, són una magnífica activitat per a primària i ens poden servir per començar a parlar dels sistema binari.

Cap comentari:

Publica un comentari a l'entrada