lunedì 17 agosto 2020

Capacità — 7. Il codice Morse

L'altra volta ho fatto un piccolo errore: avevo citato il Manuale delle Giovani Marmotte, ma in realtà volevo parlare del Manuale di Archimede. Guarda:”.



“Che meraviglia! Stavo proprio guardando il codice Morse: è un delirio”.

“Beh, è un codice reale che è nato quando c'erano certe esigenze e certe disponibilità tecniche, c'è poco da fare”.

“Almeno ho capito che non è un codice binario”.

“No, anche se in effetti usa solo due segnali: luce accesa e luce spenta, oppure corrente che passa e corrente che non passa, oppure beep e silenzio”.

“Vero, ma c'entra anche la durata di questi segnali”.

“Sì. Facciamo un riassunto di tutto quello che può succedere nel codice Morse. Possiamo distinguere quattro tipo di segnale: il punto, la linea, lo spazio tra le lettere e lo spazio tra le parole”.

“I due spazi si distinguono per la durata, vero?”.

“Sì. Prima di definire i segnali, definiamo ciò che sta alla base di tutto: l'unità di tempo. I segnali Morse sono scanditi dal passare del tempo, come se ci fosse un metronomo. La velocità di trasmissione non è predefinita: due bravi operatori possono trasmettere segnali con una velocità molto alta, due operatori che invece stanno imparando il codice andranno certamente più lenti”.

“Ok”.

“Ora, definiamo i segnali:”. 
  • Punto (P): linea chiusa per un'unità di tempo, seguita da linea aperta per un'altra unità di tempo 
  • Linea (L): linea chiusa per tre unità di tempo, seguita da linea aperta per un'unità di tempo
  • Spazio tra le lettere (S): linea aperta per tre unità di tempo
  • Spazio tra le parole (V): linea aperta per sei unità di tempo

“Uhm, qualcosa non mi torna, io ho letto cose diverse su Wikipedia”.

“Cosa?”.

“Beh, che il punto corrisponde semplicemente alla linea chiusa per un'unità di tempo, non seguita da nulla, così come la linea, mentre lo spazio tra le lettere corrisponde alla linea aperta per quattro unità di tempo, e quello tra le parole alla linea aperta per sette unità”.

“Uhm. Ai fini dei calcoli che faremo dopo, è più comodo pensare che dopo un punto o una linea ci sia sempre uno spazio vuoto della durata di un'unità di tempo, e questo corrisponde anche al fatto che io ti ho detto che lo spazio tra le parole corrisponde a uno spazio vuoto che dura sei e non sette unità: dopo un qualunque simbolo c'è una unità vuota obbligatoria che si somma alle altre sei. Questo è un sistema che usano gli informatici per decodificare in automatico una stringa di bit: si chiama codice prefix-free o comma-free. Però, però, mmh”.

“Non torna quello che dici riguardo lo spazio tra le lettere”.

“Esattamente. Secondo Shannon, che si è fatto tutto il calcolo che vorrei raccontarti, lo spazio tra le lettere sarebbe di 1+3 unità di tempo, cioè 4, mentre secondo lo standard attuale lo spazio è solo di 3 unità”.

“Mi stai dicendo che Shannon ha fatto un errore?”.

“Mah, non oso arrivare a tanto, eppure c'è una incongruenza. Secondo me l'ha fatto per poter fare un esempio, con i calcoli che fa in seguito, più completo. Nel suo articolo scrive: Thus in telegraphy suppose the symbols are: (1) A dot, consisting of line closure for a unit of time and then line open for a unit of time; (2) A dash, consisting of three time units of closure and one unit open; (3) A letter space consisting of, say, three units of line open; (4) A word space of six units of line open.”.

“Ah. Quando definisce il letter space, dice say”.

“Sì, probabilmente adatta l'esempio in modo da avere tante lunghezze diverse: il punto dura 2 unità, la linea 4, lo spazio tra le lettere 3 e quello tra le parole 6. Così facendo ha lunghezze pari a 2, 3, 4 e 6, tutte diverse. Se avesse scelto lo spazio tra le lettere lungo 2 unità, avrebbe avuto lunghezze pari a 2, 2, 4 e 6. Quelle due lunghezze uguali danno un po' fastidio.”.

“Va bene, allora prendiamo per buone le lunghezze date da Shannon. Ora che succede?”.

“Ora dobbiamo conoscere le regole di composizione. Per esempio: dopo un punto o una linea ci può essere un altro punto, un'altra linea, oppure uno dei due spazi”.

“E fin qua mi sembra facile”.

“Ma dopo uno spazio non può esserci un'altro spazio, ma solo un punto o una linea, e non si può nemmeno iniziare una trasmissione con uno spazio”.

“Ah, comincia a essere meno facile”.

“Questa figurina riassume tutte le regole di composizione:”.
 


“Vedo. Fissando la partenza, impedisci che si possa iniziare con uno dei due tipi di spazio. Interessante, anche se non avrei idea di come proseguire nello studio”.

“Lo studio è molto complicato, sì. Partiamo dal caso più semplice di tutti: può esistere una trasmissione Morse di lunghezza 1?”.

“Cosa vuol dire? Un punto?”.

“Un punto, l'abbiamo definito poco fa, è un simbolo di lunghezza 2, perché è composto da due segnali: linea chiusa per un'unità di tempo, linea aperta per un'altra unità di tempo”.

“Allora non esistono trasmissioni di lunghezza 1, no?”.

“Esatto. Se indichiamo con N(t) le trasmissioni di lunghezza t, abbiamo che N(1) = 0”.

“Bene, questa era facile. Non mi dire che ora andiamo avanti con le trasmissioni di lunghezza 2, poi 3, eccetera”.

“Esatto, faremo proprio questo. Prima, però, di complicarci la vita, facciamo un riassunto di tutti i possibili finali di trasmissione”.

“Immagino che ci siano delle regole per terminare una trasmissione Morse”.

“Sì, ma non intendevo questo. Lasciamo perdere le convenzioni utilizzate nelle trasmissioni, e rimaniamo aderenti solo allo schema che abbiamo visto. In pratica, studiamo solo quel grafo”.

“Va bene. Hai domandato quali possono essere i possibili finali: immagino di dover muovermi lungo quell'albero e vedere come si può finire”.

“Sì. Un possibile finale l'abbiamo visto, il più semplice di tutti: percorri solo un arco di quel grafo, quello che corrisponde a un punto. In quel caso, il finale è semplicemente P”.

“Ok. Allora un altro finale potrà essere L”.

“Giusto, invece di un punto trasmetti una linea, e basta”.

“Ora però le cose si complicano. Dopo aver percorso l'arco P o l'arco L, ho varie scelte”.

“Se la tua prima scelta è stata P e la seconda è stata di nuovo P, la tua trasmissione è PP, che però finisce con P”.

“Ma perché guardiamo i finali?”.

“Per ora guardiamo i finali, che sono i casi più semplici. Le trasmissioni più complicate si faranno aggiungendo finali a trasmissioni più brevi”.

“Ah. Allora, vediamo questi finali. Oltre a P e a L potrei avere PS?”.

“Esatto: un punto seguito da uno spazio tra le lettere”.

“E non potrei avere un solo spazio come finale?”.

“Eh, no. Ammettere S come finale significa che, nel caso di trasmissione più semplice possibile, tu possa trasmettere un singolo spazio, ma questo non è possibile. S è necessariamente preceduto da qualcosa, come mostra il grafico”.

“Allora di finali con lo spazio tra le lettere ce ne sono due: PS e LS”.

“Proprio così. E poi ci saranno anche i finali con la V, lo spazio tra le parole”.

“Che saranno PV e LV”.

“Giusto. Facciamo quindi un riassunto dei possibili finali:”.

  • P: lunghezza 2
  • L: lunghezza 4
  • PS: lunghezza 5
  • LS: lunghezza 7
  • PV: lunghezza 8
  • LV: lunghezza 10

“Mamma mia, e questi sono solo i finali”.

“Eh. Alleniamoci un po' sulle cose semplici: abbiamo già visto che N(1) = 0: non ci sono trasmissioni di lunghezza 1”.

“E immagino che N(2) sia uguale a 1, perché c'è una sola trasmissione di lunghezza 1, il nostro P”.

“Giusto. Quanto vale invece N(3)?”.

“Non ci sono finali di lunghezza 3”.

“Vero. Ed è possibile combinare due finali più brevi per farne uno di lunghezza 3?”.

“Non mi sembra, dato che non ci sono trasmissioni di lunghezza 1, non posso combinarne P, che è lungo 2, con un qualcosa lungo 1 che non esiste”.

“Ok. Quindi N(3) = 0”.

“Sì. Provo ad andare avanti con le trasmissioni di lunghezza 4. C'è L, la linea, che è lunga 4”.

“Ma non è l'unica trasmissione di lunghezza 4: potresti anche trasmettere PP”.

“Oh, vero, anche quella è lunga 4, cioè 2 + 2. Quindi N(4) = 2”.

“Volendo complicarci la vita, per capire le difficoltà che incontreremo andando avanti, potrei dirti che N(4) = N(2) + 1”.

“Uh. Capisco che sia vero, ma non capisco il senso”.

“Quella formula ci sta dicendo che per ottenere una trasmissione di lunghezza 4 si prendono tutte quelle di lunghezza 2 (che si possono far diventare di lunghezza 4 mettendo un P davanti) e, in più, se ne aggiunge una nuova, che è poi L”.

“Una definizione ricorsiva?”.

“Esattamente. Se ci fossero 42 trasmissioni di lunghezza 2, ne potresti ottenere altre 42 di lunghezza 4 facendole tutte precedere da un P. Poi si aggiunge una nuova trasmissione di lunghezza 4, cioè L”.

“Credo di capire. Ora provo a calcolare N(5), vediamo cosa combino”.

“Vai”.

“Allora, le trasmissioni di lunghezza 5 si possono ottenere da quelle di lunghezza 3 aggiungendo una P davanti (ma di trasmissioni di lunghezza 3 non ce ne sono), oppure da quelle di lunghezza 1 aggiungendo una L davanti (ma anche di queste non ce ne sono), e poi ce n'è una nuova, che è PS”.

“Ottimo! La formula è quindi: N(5) = N(3) + N(1) + 1”.

“Che dà come risultato un semplice 1, però”.

“Non importa: hai capito il procedimento, andando avanti non aggiungerai sempre degli zeri”.

“Ma quando mi fermo?”.

“Ti fermi quando capisci la regola generale”.

“E la regola generale quando la capisco?”.

“Quando smetti di aggiungere roba nuova”.

“Aha! Allora provo ad andare avanti”.

“Prima permettimi di complicarti ancora un po' la vita”.

“Argh”.

“Ti riscrivo la formula per N(5) in questo modo: N(5) = N(5−2) + N(5−4) + 1”.

“Ah, credo di capire: hai scritto N(5−2) invece di N(3) perché ciò che conta è quel 2: aggiungi un simbolo di lunghezza 2 davanti”.

“Perfetto. Ora prova a calcolare N(6)”.

“Ok, vado. Una trasmissione di lunghezza 6 si ottiene aggiungendo a una trasmissione più breve una P, che è lunga 2, oppure una L, che è lunga 4, oppure una PS, che è lunga 5. E non ci sono finali di lunghezza 6, quindi la formula è questa: N(6) = N(6−2) + N(6−4) + N(6−5)”.

“Ottimo: fai i conti”.

“Ecco: N(6) = N(4) + N(2) + N(1) = 2 + 1 + 0 = 3”.

“Ed ecco qua l'elenco delle trasmissioni di lunghezza 6: PPP, PL, LP”.

“E, dato che non ho aggiunto nuovi finali, ho finito, vero?”.

“Eh, no. Non hai aggiunto nuovi finali non perché non ce ne siano più, ma perché i finali che rimangono sono lunghi più di 6”.

“Ah, vero. Che peccato. Beh, allora proverò ad andare avanti, però non adesso”.

“La prossima volta”.

“Ok”.