Verificare una... tastiera
In un processo industriale deve essere verificato il corretto funzionamento di una tastiera con sei tasti. La tastiera dispone di connessioni elettriche in grado di stabilire se e quale tasto viene premuto. Scopo della verifica è stabilire che ogni tasto attivi l’uscita dovuta e non attivi nessuna delle altre. Tutto semplice, direte voi: si premono i sei tasti in sequenza e si verifica che a ogni pressione corrisponda il (solo) tasto corretto. Certo, ma c’è anche un metodo più furbo: premendo i tasti a gruppi, è possibile fare questa verifica in soli quattro passi, invece di sei. Infatti, la sequenza
(dove sopra la riga di separazione sono indicati i tasti, e sotto la riga di separazione i quattro gruppi)
è sufficiente a verificare che tutti i tasti funzionino e che nessun tasto attivi due uscite anziché una sola.
Con deduzioni logiche ed empiriche, sono giunto ad un insieme di due regole che determinano i gruppi:
1) Ogni tasto deve essere premuto almeno una volta
2) Nell’insieme dei passi, ogni tasto deve essere premuto, almeno una volta, separatamente da ognuno degli altri.
Nel caso esposto, se consideriamo le quindici coppie di tasti, le regole qui sopra possono essere messe in evidenza dall’operazione di EXOR sulla tabella precedente
(dove sopra la riga di separazione sono indicate le coppie di tasti per colonna, e sotto la riga di separazione l’operazione di EXOR descritta)
Il rispetto della regola è garantito dalla presenza di almeno uno zero e di almeno un uno su ogni colonna.
Questo però è solo un algoritmo di verifica (oltretutto non dimostrato…), ma sarebbe molto più interessante trovare una funzione (o una successione, o un algoritmo) che, dato il numero di tasti, determinasse il numero minimo di vettori necessari ad un test esaustivo, ed un altro che magari trovasse anche quali sono…
Secondo voi è possibile?
123456 ------ 001100 010010 100001 101010
(dove sopra la riga di separazione sono indicati i tasti, e sotto la riga di separazione i quattro gruppi)
è sufficiente a verificare che tutti i tasti funzionino e che nessun tasto attivi due uscite anziché una sola.
Con deduzioni logiche ed empiriche, sono giunto ad un insieme di due regole che determinano i gruppi:
1) Ogni tasto deve essere premuto almeno una volta
2) Nell’insieme dei passi, ogni tasto deve essere premuto, almeno una volta, separatamente da ognuno degli altri.
Nel caso esposto, se consideriamo le quindici coppie di tasti, le regole qui sopra possono essere messe in evidenza dall’operazione di EXOR sulla tabella precedente
111112222333445 234563456456566 --------------- 011001100011110 100101101010101 111100001001011 101011010101101
(dove sopra la riga di separazione sono indicate le coppie di tasti per colonna, e sotto la riga di separazione l’operazione di EXOR descritta)
Il rispetto della regola è garantito dalla presenza di almeno uno zero e di almeno un uno su ogni colonna.
Questo però è solo un algoritmo di verifica (oltretutto non dimostrato…), ma sarebbe molto più interessante trovare una funzione (o una successione, o un algoritmo) che, dato il numero di tasti, determinasse il numero minimo di vettori necessari ad un test esaustivo, ed un altro che magari trovasse anche quali sono…
Secondo voi è possibile?
Risposte
Ti metto qui di seguito una soluzione sistematica, indipendendente dal numero di tasti.
Innanzitutto prendiamo un numero di tasti $n$ pari a una potenza del 2.
Si tratta di costruire una tabella nelle cui celle vanno scritte delle cifre binarie, quindi 0 o 1.
La tabella ha $n$ righe e $\log_2 n$ colonne.
Nelle righe della tabella, numerate a partire da 0, si scrivono i numeri binari pari al numero della riga.
Quindi nella riga 0 si scrive 000..0, nella riga 1 si scrive 000...1, nella riga 2 si scrive 000...10 e cosi' via.
L'ultima riga sara' 111...1.
Il test si effettua in questo modo:
- si prendono le cifre binarie di una colonna della tabella (in tutto $n$ valori) e le si applicano ai tasti: banalmente sara' 1: tasto premuto e 0: tasto non premuto.
- si controllano gli stati delle le uscite che devono corrispondere allo stato dei tasti.
- si ripete il controllo per tutte le $\log_2 n$ colonne della tabella.
Quindi si prende la tabella, si invertono le cifre delle singole celle e si ripete il test di prima.
Gli step da effettuare sono quindi in tutto $2 \log_2n$.
Se il numero dei tasti non e' pari ad una potenza del 2, l'unica soluzione e' di fare un "padding", ovvero di considerare un numero di tasti "immaginari" fino a raggiungere la potenza del 2. Le corrispondenti uscite "immaginarie" si ottengono copiando i valori dei tasti.
Ad es: per 8 tasti le 2 tabelle sono come segue:
Per comodita' e chiarezza ho messo le due tabelle una di fianco all'altra.
Ci sono quindi $n=8$ righe e $2\log_2 8 = 6 $ colonne.
In tutto si faranno 6 test.
Ad es. il primo test consiste nel prendere i valori della prima colonna, 11110000, e applicarli agli 8 tasti.
Le 8 uscite devono avere lo stesso valore dei tasti.
Innanzitutto prendiamo un numero di tasti $n$ pari a una potenza del 2.
Si tratta di costruire una tabella nelle cui celle vanno scritte delle cifre binarie, quindi 0 o 1.
La tabella ha $n$ righe e $\log_2 n$ colonne.
Nelle righe della tabella, numerate a partire da 0, si scrivono i numeri binari pari al numero della riga.
Quindi nella riga 0 si scrive 000..0, nella riga 1 si scrive 000...1, nella riga 2 si scrive 000...10 e cosi' via.
L'ultima riga sara' 111...1.
Il test si effettua in questo modo:
- si prendono le cifre binarie di una colonna della tabella (in tutto $n$ valori) e le si applicano ai tasti: banalmente sara' 1: tasto premuto e 0: tasto non premuto.
- si controllano gli stati delle le uscite che devono corrispondere allo stato dei tasti.
- si ripete il controllo per tutte le $\log_2 n$ colonne della tabella.
Quindi si prende la tabella, si invertono le cifre delle singole celle e si ripete il test di prima.
Gli step da effettuare sono quindi in tutto $2 \log_2n$.
Se il numero dei tasti non e' pari ad una potenza del 2, l'unica soluzione e' di fare un "padding", ovvero di considerare un numero di tasti "immaginari" fino a raggiungere la potenza del 2. Le corrispondenti uscite "immaginarie" si ottengono copiando i valori dei tasti.
Ad es: per 8 tasti le 2 tabelle sono come segue:
000 111 001 110 010 101 011 100 100 011 101 010 110 001 111 000
Per comodita' e chiarezza ho messo le due tabelle una di fianco all'altra.
Ci sono quindi $n=8$ righe e $2\log_2 8 = 6 $ colonne.
In tutto si faranno 6 test.
Ad es. il primo test consiste nel prendere i valori della prima colonna, 11110000, e applicarli agli 8 tasti.
Le 8 uscite devono avere lo stesso valore dei tasti.
Ma che bella risposta, grazie!
In pratica si tratta di provare tutte le combinazioni binarie, sia vere che negate, cosa che (ora) appare anche logica.
In pratica si tratta di provare tutte le combinazioni binarie, sia vere che negate, cosa che (ora) appare anche logica.
"LucianoD":
Ma che bella risposta, grazie!
In pratica si tratta di provare tutte le combinazioni binarie, sia vere che negate, cosa che (ora) appare anche logica.
Prego.
Comunque non si tratta di provare tutte le combinazioni ma solo $2 \log_2 n$.
Se uno avesse 1024 tasti, dovrebbe provare solo le 20 combinazioni descritte per essere sicuro che la tastiera "funzioni bene".
E' chiaro che con 6 o 8 tasti non c'e' molta convenienza ad inventarsi degli algoritmi sofisticati.
Non ho una dimostrazione che provi che sia il numero minore di prove che garantiscono il funzionamento della tastiera.
Ma quando si tratta di valori binari, di solito il $\log_2$ e' una soglia sotto la quale e' difficile andare.
Sì, certo, con "tutte le combinazioni" intendevo tutte quelle che vengono fuori guardando la tabella "dall'altra parte".
Nel tentativo di trovare l'equazione, il logaritmo in base due era venuto fuori, ma mi mancava quel 2 che cambia tutto (e anche la logica di come arrivarci).
Mentre sul fatto che per 6 o otto tasti non valga la pena... devo darti torto: sto lavorando su una macchina che verifica tastiere da sei tasti, ma ne deve provare tre milioni all'anno. A 750 millisecondi per test, risparmiare due prove fa qualcosa come 1250 ore di lavoro in meno!
Nel tentativo di trovare l'equazione, il logaritmo in base due era venuto fuori, ma mi mancava quel 2 che cambia tutto (e anche la logica di come arrivarci).
Mentre sul fatto che per 6 o otto tasti non valga la pena... devo darti torto: sto lavorando su una macchina che verifica tastiere da sei tasti, ma ne deve provare tre milioni all'anno. A 750 millisecondi per test, risparmiare due prove fa qualcosa come 1250 ore di lavoro in meno!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo