Newsgroup: it.hobby.elettronica.digitale
Titolo: LFSR

Buongiorno,
ho scoperto da poco questo gruppo e volevo chiedere un aiuto.
Devo realizzare un divisore in modulo 2 per calcolare il resto della
divisione tra due polinomi (uno fuisso e l'altro passato attraverso un
ingresso seriale bit per bit).
Ho visto che tale operazione puo' essere eseguita tramite un LFSR
(Linear Feedback Shift Register)  e volevo chiedere se qualcuno di voi
poteva darmi un'aiuto per una realizzazione in VHDL di tale
componente.
Vi ringrazio molto.

 in VHDL di tale componente.
Devi per caso calcolare/verificare un CRC?
Dai un'occhiata quě: 
http://www.easics.com/webtools/crctool
Ciao,
A.D.

 componente.
Non so se puň esserti utile, ma a suo tempo su una Virtex 2 ho usato un LFSR 
con core IP direttamente di Xilinx. Insomma, se usi Xilinx dovresti poterlo 
inserire senza problemi.
Inoltre su 
http://www.opencores.org/
 puoi trovare diversi core scritti in 
Verilog e/o in VHDL, che sono completamente gratuiti e liberi da licenza. 
Non so se lě puoi trovare quello che cerchi, ma darei comunque un'occhiata.
Ciao 


Effettivamente devo fare un'operazione tipo quella di verifica di un
CRC in quanto devo effettuare al divisione tra un polinomio di 1024
bit e uno di 77.
Avevo gia' visto quel sito solo che in quel caso e' possibile solo
arrivare a polinomi di grado 33 mentre il mio polinomio divisore e' a
77 bit.
Inoltre sarebbe ancopra meglio se esistesse un modo per effettuare
tale operazione in parallelo.

 effettuare tale operazione in parallelo.
Cioè?!? I dati che hai a disposizione non sono seriali?
Credo che l'unico modo per fare la divisione "parallela" sia
fare una divisione vera e propria sul campo di galois, ed
implementarla con una struttura a pipeline (cosa non sempre
semplice e/o conveniente).
A.D.


Dai coefficienti del polinomio divisore ti ricavi le posizioni
dei "tap" dello shift register su cui fare lo XOR. Sinceramente non
mi ricordo come si fa questo passaggio, ma sicuramente trovi esempi
a bizzeffe.
Poi scrivere la descrizione in VHDL e` una cosa elementare, a meno che
tu non abbia esigenze particolari che non immagino.
E` abbastanza strana la dimensione di questo LFSR. Che cosa e`?
Generatore pseudorandom? Crittografia?
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

 Generatore pseudorandom? Crittografia?
Mi serve per una verifica di crittografia. Se il resto e' zero la
sequenza inviata e' valida.

 sequenza inviata e' valida.
Ma la sequenza inviata non penso che sia in parallelo.
Io penso che esista una soluzione alternativa a quello che vuoi fare,
ma dovresti spiegarti meglio.


 ma dovresti spiegarti meglio.
Ho un sistema che invia in maniera seriale un bit per volta (facendo
ogni volta uno shift sulla sequenza di 1023 di partenza). Ogni volta
devo controllare se una sequenza di 1023 bit e' divisibile per una di
77.
Se lo e' vado avanti, altrimenti aspetto il nuovo bit e rifaccio la
divisione con 1022 bit della sequenza precednete piu' il nuovo bit
(scartando quindi il piu' vecchio).
Ho visto la possibilita' di usare degli lfsr ma io ricevo in ingresso
continuamente un bit per cui non so come interrompere il calcolo del
polinomio dividendo a solo gli ultimi 1022 ricevuti (se usassi un lfsr
normale dopo, ad esempio 2000 bit ricevuti mi avrebbe calcolato il
resto della divisione di un polinomio di 2000 bit con uno di 77,
mentre a me serve solo il calcolo degli ultimi 1023 ricevuti come se
fosse un nuovo polinomio).
Inoltre non posso effettuare ogni volta un lfsr sulla nuova sequenza
in maniera seriale altrimenti mi servirebbero circa 1023 cicli interni
per calcolarmi il resto mentre io dovrei riuscire a farlo al massimo
in un centinaio di cicli (altrimenti ho un nuovo bit nella sequenza di
ingresso)
Non so se e' piu' chiaro cosi'.
Grazie.


Devo pensarci un po'. Come informazione aggiuntiva, a che
velocita` arrivano i bit dei dati?


 velocita` arrivano i bit dei dati?
Piu' o meno la frequenza e' di 500 KHz


Quindi relativamente bassa.
Mi sa che la soluzione che avevi ipotizzato, cioe` lavorare sui 1023
bit in parallelo, e` la piu` immediata. Di sicuro non e` semplice
realizzarla.
Devi avere uno shift regiter da 1023 bit e, con una rete combinatoria
MOLTO grossa, calcolare il CRC di tutti i 1023 bit contemporaneamente.
Con molta pazienza devi scrivere la funzione. Sinceramente non riesco
a stimare le risorse necessarie a questa rete combinatoria di 1023
ingressi e 77 uscite che va molto al di la` di ogni mia esperienza! Di
certo pero` sara` piuttosto lenta, nel migliore dei casi immagino
dell'ordine
dei uS, dovendo attraversare decine di gates.
Volendo invece calcolare il CRC in modo consueto sui 1023 bit, bit per bit,
penso che si potrebbe arrivare a frequenze di clock dell'ordine del
centinaio
di MHz, quindi in un tempo di calcolo complessivo dell'ordine dei 10uS.
Calcolando il CRC su blocchi di n bit invece che su un bit alla volta,
la frequenza massima si abbasserebbe ma probabilmente si
raggiungerebbero prestazioni complessive migliori. Bisognerebbe trovare
il valore di n che fornisce i risultati migliori in funzione anche della
tecnologia
costruttiva e questo lo si trova per tentativi tramite simulazione. Quindi
questa
potrebbe essere una soluzione, affrontando il problema nel modo che abbiamo
detto.
Pero` mi rimane la netta sensazione che tutto il problema sia risolubile in
qualche altra maniera piu` furba. Se trovi qualche altra soluzione mi
piacerebbe
conoscerla per mia curiosita`.
