Primtalsbaseret tæller!

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From Danish to

Threaded View
Hej

Nogen der kan poste til info om primtalsbaserede tællere og hvorfor man
kan udnytte dem til hurtig dataopsamling? (set i fpga-sammenhænge)

Har fået denne kommentar, men jeg kan ikke finde noget info om de
tællere: "Har du overvejet at anvende primtals baserede tællere, så kan
du få meget hurtig dataopsampling (også med Spartan-II)?"



Takker
Preben Holm


Re: Primtalsbaseret tæller!

Quoted text here. Click to load it

Hej Preben,

jeg tror der er tale om det der hedder et linear feed back skifteregister.
Den består  at et (langt) skifteregister med xnor feedback fra to udvalgte
udgange. Hvis man vælger de "rigtige" udgange, vil det samlede parallelle
output fra registeret gennemløbe samtlige kombinationer inden den gentager
sig selv. Jeg bruger det random noise i bestemmelse af sampling af data i et
støjfyldt miljø. Det giver en jitter på dataopsamlingen, som jeg selv
kender. Denne kendte jitter bruges til at udjævne spektret for visse typer
af støjkilder.

se f.x:
http://www.xilinx.com/bvdocs/appnotes/xapp052.pdf

Bo //
-jeg vil gerne høre om det var det du søgte...



Re: Primtalsbaseret tæller!
Hej Bo

Quoted text here. Click to load it

Ok, det lader til min basis digital elektronik ikke lige rækker her
endnu i hvert fald, men hvis du har tålmodighed lærer man jo nyt hver dag.

For det første.. Det skal anvendes til datasampling i en FPGA, så der
lader du til at være helt korrekt på den (mit scop-projekt som der
sikkert huskes lidt om herinde), men desværre forstår jeg ikke rigtig
hvordan ov. virker! Det lyder smart alt sammen.

Jeg skal sample data gerne så hurtigt som muligt. Og hvordan jeg kommer
så højt op i frekvens er mit nuværende problem.

Jeg fik i dag et lille ekstra tip til hvordan tællerne virker, men
forstår det stadig ikke helt:
"Primtalstællere virker ved, at du har flere tællere, der kører
samtidigt og uafhængigt. Hver af tællerne er indbyrdes primiske (f.eks.
tallene 15,13,31 og 7 giver en fin 16 bit tæller). Da tællerne er
indbyrdes primiske, vil perioden for tælleren være 15*13*31*7 (knap 16
bit). Herved kan du få Xilinx til at tælle ca. 3 gange hurtigere, da der
er kort gate-delay i hver tæller."

Men jeg tror der er tale om det samme, men jeg er ikke klog nok til at
vurdere det helt endnu.


Mvh / Preben


Re: Primtalsbaseret tæller!



Quoted text here. Click to load it

Indtil videre er mit svar: "øhhhh".

Vil andre med mere viden tage over her ?

BBj //



Re: Primtalsbaseret tæller!
Quoted text here. Click to load it

Jeg ved ikke med andre men 3 * 5 får jeg til 15, så hvordan kan 15
være et primtal ???

Re: Primtalsbaseret tæller!
Quoted text here. Click to load it

Sådan som jeg læser det er de indbyrdes primisk - ikke nødvendigvis
primtal, men derimod har tallene ingen fælles divisor udover 1.


Mvh / Preben Holm


Re: Primtalsbaseret tæller!

Quoted text here. Click to load it


Jeg mindes den gamle historie om en matematiker og en eksperimental fysiker,
der begge undersøgte primtal.

Påstanden var at alle ulige tal var primtal.

Matematikeren: "1, 3, 5, 7  det passer. Man kan fortsætte beviset ved
induktion..."

Fysikeren: ""1, 3, 5, 7, 9, 11, 13, 15, 17, 19...   9 og 15 havde dårlige
forsøgsbetingelser, men statistisk passer det fint"

Bo //



Re: Primtalsbaseret tæller!
Quoted text here. Click to load it

Hehe, nej, ikke lige just - det at tallene er indbyrdes primiske vil
sige at de netop ikke har en fælles divisor.

Jeg har faktisk fundet ud af noget mere. Der gælder nemlig at hvis man
har tællere som hver især tæller til bestemte tal der er indbyrdes
primiske, så kan man ved sammensætning af de fire tal faktisk udtrykke
værdier som ikke forekommer. Alle tællere starter f.eks. med nul, men
efter næste gang vil alle tællere være talt op med ´en. Dvs. så står der
(f.eks. i tilfældet med 7,13,15,31) stå:

     111   1101   1111   1111 1110 - dvs. et stort tal.

Der tælles altså ikke i rækkefølge, men vha. lidt tal-teori (spørg mig
ikke om teorien) er det altså givet at man ikke vil ramme det samme tal
igen, før man rammer nul igen. Dette er utrolig smart, da man på den
måde kan lave flere små tællere der pga. sin mere simple logik vil kunne
køre hurtigere. Dette kan så anvendes i kredsen (FPGA) til at give
hurtigere responstider og tillade højere clock-frekvenser.

Det er åbenbart noget af det samme som LFSR - bare på en helt anden
måde, men altså med samme formål - netop at øge performance. Givet vis
skulle det altså ikke være et særlig kendt trick at anvende, men jeg fik
tippet fra en ASIC designer, så jeg tror på det virker. Det kræver meget
tal-teori, og vil jo give "huller" i hukommelsen da alle bit ikke vil
anvendes. Det tætteste jeg er kommet er med tallene 8,13,17,37 - dette
giver kombinationsmuligheder på 65.416 hvilket er pænt tæt på de 65.536
mulige på et 32bit tal.
Desværre bliver 37 så til et 6bit tal og så forsvinder ideen jo lidt,
hvis man kunne højes med 5bit tal og alligevel komme op i nærheden af
tallet.

Mere relevant vil nok være at anvende måske 13,15,17,19 hvilket giver
62.985 - men hvad er så bedst. At anvende disse to 4-bit tællere sammen
med to 5bit tællere.


Hvis nogen kan give et bevis for at de enkelte tal ikke forekommer flere
gange er de yderst velkommen :) (Jeg kan ikke lige på stående fod, men
som sagt så skulle det altså virke)


Med venlig hilsen
Preben Holm


Re: Primtalsbaseret tæller!
Quoted text here. Click to load it
 >
 >     111   1101   1111   1111 1110 - dvs. et stort tal.
 >

Sludder, der vil stå
       001   0001   0001   0 0001

og for max på alle tællere vil der stå:
       111   11 1   1111   1 1110



Mvh / Preben Holm


Re: Primtalsbaseret tæller!
Quoted text here. Click to load it
Men her har du en "18 bit" tæller hvor du kun bruger 62985 ud af 262144
mulige tilstande. Kan din anvendelse leve med det?
/hjj

Re: Primtalsbaseret tæller!
Quoted text here. Click to load it

Det er selvfølgelig rigtigt.. Ikke smart tænkt af mig alligevel - det
kræver jo større hukommelsesblok (da jeg skal tilgå hukommelses-adresser)...

Tak for observationen.


Mvh / Preben



Re: Primtalsbaseret tæller!
Hej Bo (og andre)

Quoted text here. Click to load it

Hvordan vælger man "de rigtige" udgange? Tror jeg vil se nærmere på
denne løsning, selvom primtallene også virker "sjove".


Mvh / Preben


Re: Primtalsbaseret tæller!

Quoted text here. Click to load it
skifteregister.
udvalgte
parallelle
gentager

Kig i mit tidligere svar:


se f.x:
http://www.xilinx.com/bvdocs/appnotes/xapp052.pdf

BBj //



Site Timeline