Primtalsbaseret tæller!

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:

Bo //

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

Hej Bo

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

Indtil videre er mit svar: "øhhhh".

Vil andre med mere viden tage over her ?

BBj //

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

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

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 //

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

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

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

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

Hej Bo (og andre)

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

Mvh / Preben

skifteregister.

udvalgte

parallelle

gentager

Kig i mit tidligere svar:

se f.x:

BBj //