Come faccio a mantenere il tempo senza errori cumulativi?
https://stackoverflow.com/questions/1654661
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Come puoi tenere traccia del tempo in un semplice sistema embedded, dato che hai bisogno di una rappresentazione a virgola fissa del tempo in secondi e che il tempo tra i tick non è esattamente esprimibile in quel formato a virgola fissa?Come evitare errori cumulativi in tali circostanze.
Questa domanda è una reazione a Questo articolo su slashdot.
0,1 secondi non possono essere espressi chiaramente come numero binario a virgola fissa, proprio come 1/3 non possono essere espressi chiaramente come numero decimale a virgola fissa.Qualsiasi rappresentazione binaria in virgola fissa presenta un piccolo errore.Ad esempio, se ci sono 8 bit binari dopo il punto (cioè utilizzando un valore intero scalato per 256), 0,1 per 256 è 25,6, che verrà arrotondato a 25 o 26, risultando in un errore dell'ordine del -2,3% o +1,6% rispettivamente.L'aggiunta di più bit binari dopo il punto riduce la portata di questo errore, ma non può eliminarlo.
Con addizioni ripetute, l'errore si accumula gradualmente.
Come si può evitare questo?
Soluzione
Un approccio non consiste nel provare a calcolare il tempo mediante l'aggiunta ripetuta di questa costante di 0,1 secondi, ma nel mantenere un semplice conteggio dei battiti dell'orologio intero.Questo conteggio dei tick può essere convertito in un tempo a virgola fissa in secondi secondo necessità, solitamente utilizzando una moltiplicazione seguita da una divisione.Dati i bit sufficienti nelle rappresentazioni intermedie, questo approccio consente qualsiasi ridimensionamento razionale e non accumula errori.
Ad esempio, se il conteggio dei tick corrente è 1024, possiamo ottenere l'ora corrente (in virgola fissa con 8 bit dopo il punto) moltiplicandola per 256, quindi dividendo per 10 - o in modo equivalente, moltiplicando per 128 e quindi dividendo per 5 .In ogni caso, c'è un errore (il resto della divisione), ma l'errore è limitato poiché il resto è sempre inferiore a 5.Non c'è errore cumulativo.
Altri suggerimenti
Un altro approccio potrebbe essere utile in contesti in cui la moltiplicazione e divisione di numeri interi è considerata troppo costosa (cosa che dovrebbe diventare piuttosto rara di questi tempi).Prende in prestito un'idea da Algoritmo di disegno al tratto di Bresenham.Mantieni l'ora corrente in un punto fisso (anziché un conteggio dei tick), ma mantieni anche un termine di errore.Quando il termine di errore diventa troppo grande, si applica una correzione al valore temporale, evitando così l'accumulo dell'errore.
Nell'esempio a 8 bit dopo il punto, la rappresentazione di 0,1 secondi è 25 (256/10) con un termine di errore (resto) di 6.Ad ogni passaggio aggiungiamo 6 al nostro accumulatore di errori.Sulla base di ciò finora, i primi due passaggi sono...
Clock Seconds Error
----- ------- -----
25 0.0977 6
50 0.1953 12
Al secondo passaggio, il valore dell'errore è andato in overflow, ovvero ha superato 10.Pertanto, incrementiamo l'orologio e sottraiamo 10 dall'errore.Ciò accade ogni volta che il valore dell'errore raggiunge 10 o superiore.
Pertanto, la sequenza effettiva è...
Clock Seconds Error Overflowed?
----- ------- ----- -----------
25 0.0977 6
51 0.1992 2 Yes
76 0.2969 8
102 0.3984 4 Yes
C'è quasi sempre un errore (l'orologio è esattamente corretto solo quando il valore dell'errore è zero), ma l'errore è limitato da una piccola costante.Non è presente alcun errore cumulativo nel valore dell'orologio.
Una soluzione solo hardware consiste nel fare in modo che i tick dell'orologio hardware funzionino leggermente velocemente, abbastanza velocemente da compensare le perdite cumulative causate dall'arrotondamento per difetto del valore della durata del tick aggiunto ripetutamente.Cioè, regolare la velocità del tick dell'orologio hardware in modo che il valore della durata del tick a virgola fissa sia esattamente corretto.
Funziona solo se per l'orologio viene utilizzato un solo formato a virgola fissa.
Perché non avere un contatore da 0,1 secondi e ogni dieci volte incrementare il contatore dei secondi e riportare il contatore da 0,1 a 0?
In questo caso particolare, avrei semplicemente mantenuto il conteggio del tempo in decimi di secondo (o millisecondi, o qualunque scala temporale sia appropriata per l'applicazione).Lo faccio continuamente in piccoli sistemi o sistemi di controllo.
Quindi un valore temporale di 100 ore verrebbe memorizzato come 3_600_000 segni di spunta: zero errori (diversi dagli errori che potrebbero essere introdotti dall'hardware).
I problemi introdotti da questa semplice tecnica sono:
- è necessario tenere conto dei numeri più grandi.Ad esempio, potrebbe essere necessario utilizzare un contatore a 64 bit anziché uno a 32 bit
- tutti i tuoi calcoli devono tenere conto delle unità utilizzate: questa è l'area che molto probabilmente causerà problemi.Cerco di risolvere questo problema utilizzando contatori del tempo con un'unità uniforme.Ad esempio, questo particolare contatore necessita solo di 10 tick al secondo, ma un altro contatore potrebbe richiedere una precisione al millisecondo.In tal caso, prenderei in considerazione la possibilità di rendere entrambi i contatori con precisione al millisecondo in modo che utilizzino le stesse unità anche se non è realmente necessaria quella precisione.
Ho anche dovuto fare altri trucchi con timer che non sono "regolari".Ad esempio, ho lavorato su un dispositivo che richiedeva l'acquisizione di dati 300 volte al secondo.Il timer hardware si attivava una volta al millisecondo.Non c'è modo di ridimensionare il timer in millisecondi per ottenere esattamente unità di 1/300 di secondo.Quindi dovevamo avere una logica che eseguisse l'acquisizione dei dati ogni 3, 3 e 4 tick per evitare che l'acquisizione andasse alla deriva.
Se è necessario gestire l'errore temporale dell'hardware, è necessaria più di una fonte temporale e utilizzarle insieme per mantenere sincronizzato il tempo complessivo.A seconda delle tue esigenze, questo può essere semplice o piuttosto complesso.
Qualcosa che ho visto implementato in passato:il valore di incremento non può essere espresso esattamente nel formato a virgola fissa, ma può essere espresso come frazione.(È simile alla soluzione "tenere traccia di un valore di errore".)
In realtà in questo caso il problema era leggermente diverso, ma concettualmente simile: il problema non era una rappresentazione a virgola fissa in quanto tale, ma derivare un timer da una sorgente di orologio che non era un multiplo perfetto.Avevamo un orologio hardware che ticchetta a 32.768 Hz (comune per un timer a basso consumo basato su cristallo).Volevamo un timer millisecondo.
Il timer in millisecondi dovrebbe incrementare ogni 32.768 tick hardware.La prima approssimazione prevede l'incremento ogni 33 tick hardware, per un errore nominale dello 0,7%.Ma, notando che 0,768 è 768/1000, o 96/125, puoi fare questo:
- Mantieni una variabile per il valore "frazionario".Inizia da 0.
- attendere che il timer hardware conti 32.
- Sebbene sia vero:
- incrementare il timer in millisecondi.
- Aggiungi 96 al valore "frazionario".
- Se il valore "frazionario" è >= 125, sottrai 125 e attendi che il timer hardware conti 33.
- Altrimenti (il valore "frazionario" è < 125), attendere che il timer hardware conteggi 32.
Ci sarà un po' di "jitter" a breve termine sul contatore dei millisecondi (32 contro 33 tick hardware), ma la media a lungo termine sarà di 32.768 tick hardware.
