stevem@specialix.co.uk (Steven Murray) (03/27/91)
'Pseudo-Random Binary Sequences', sometimes known as
'm-sequences' and the basis for random number generation in some
electronic and software products, are produced by a 'shift-register'
where the input to the shift-register is an X-OR of some of the
shift-register outputs (usually called taps). At each clock of
the shift-register, a new bit of 'pseudo-random' sequence is
generated at the XOR outupt. The only danger is that the S/R
must not be allowed to power up in the 'all-zero's' condition -
because it will never change - and that the correct Taps are used.
There's the rub, has anyone got a definitive list of PRBS taps?
I saw one in a book once - a reference text - but didn't copy it.
The length of the PRBS sequence with proper taps ('maximal length')
is normally (2^n)-1, where n is the number of S/R bits - without
getting greedy, I saw taps for a 33 bit SR once - has anyone got
the taps for anything longer?
Regards,
Steven Murray
--
Steven Murray
uunet!slxsys!stevem stevem@specialix.co.uk
I am speaking, but | If these are your opinions, then we are in agreement!!
not for my employer.| Flames, spelling errors, complaints > /dev/nulljhgillespie@ucdavis.edu (03/30/91)
In article <1991Mar27.101754.5326@specialix.co.uk> stevem@specialix.co.uk (Steven Murray) writes: > > 'Pseudo-Random Binary Sequences', sometimes known as >'m-sequences' and the basis for random number generation in some >electronic and software products, are produced by a 'shift-register' >where the input to the shift-register is an X-OR of some of the >shift-register outputs (usually called taps).... >There's the rub, has anyone got a definitive list of PRBS taps? Try Arvillias, A. C. and D. G. Maritsas. 1979 IEEE Trans. Comp. C-28:89-101. or Pangratz, H. and H. Weinrichter 1919 IEEE Trans. Comp. C-28:89-101.637-642
ferguson@maitai.SRC.Honeywell.COM (Dennis Ferguson) (03/30/91)
In article mumble mumble stevem@specialix.co.uk (Steven Murray) writes: > >There's the rub, has anyone got a definitive list of PRBS taps? >I saw one in a book once - a reference text - but didn't copy it. >The length of the PRBS sequence with proper taps ('maximal length') >is normally (2^n)-1, where n is the number of S/R bits - without >getting greedy, I saw taps for a 33 bit SR once - has anyone got >the taps for anything longer? From "The Art of Electronics" by Horowitz and Hill pp 657 Taps Sequence Length 33, 20 8589934591 35, 33 34358738367 36, 25 68719476735 39, 35 549755813887 Dennis ferguson@src.honeywell.com
ressler@galileo.ifa.hawaii.edu (Mike "IR" Ressler) (03/30/91)
In article <1991Mar27.101754.5326@specialix.co.uk> stevem@specialix.co.uk (Steven Murray) writes: > >There's the rub, has anyone got a definitive list of PRBS taps? >I saw one in a book once - a reference text - but didn't copy it. >The length of the PRBS sequence with proper taps ('maximal length') >is normally (2^n)-1, where n is the number of S/R bits - without >getting greedy, I saw taps for a 33 bit SR once - has anyone got >the taps for anything longer? Try page 227 of Numerical Recipes in C by William Press et al (Cambridge University Press). They give a table of primitive polynomials (taps) out to order 100 (100 bits). They are obviously mostly concerned about software implementations, but discuss it in hardware terms enough to be useful. Besides, they give the taps for ALL orders up to and including 100. -- Mike Ressler - Infrared Photon Jockey ressler@galileo.ifa.hawaii.edu If at first you don't succeed, get a bigger sledgehammer.
tomb@hplsla.HP.COM (Tom Bruhns) (04/02/91)
>ressler@galileo.ifa.hawaii.edu (Mike "IR" Ressler) writes: >In article <1991Mar27.101754.5326@specialix.co.uk> stevem@specialix.co.uk (Steven Murray) writes: >> >>There's the rub, has anyone got a definitive list of PRBS taps? >>I saw one in a book once - a reference text - but didn't copy it. >>The length of the PRBS sequence with proper taps ('maximal length') >>is normally (2^n)-1, where n is the number of S/R bits - without >>getting greedy, I saw taps for a 33 bit SR once - has anyone got >>the taps for anything longer? > >Try page 227 of Numerical Recipes in C by William Press et al (Cambridge >University Press). They give a table of primitive polynomials (taps) out to >order 100 (100 bits). They are obviously mostly concerned about software >implementations, but discuss it in hardware terms enough to be useful. >Besides, they give the taps for ALL orders up to and including 100. >---------- Actually, I doubt you want catalog of _all_ maximal length boolean polynomials, even up to order 32, since there are somewhere around 2^25 of them. And it just gets worse as the order gets larger ;-). It's fun to test different polynomials to see which gives the best results for a particular application (if the application is critical enough to warrant it). See Knuth's 'Algorithms...' book (I don't recall the volume) for a good discussion of finding prime polynomials. I've used search techniques to find them up to order 48 or so, but it starts chewing up lots of CPU time and isn't real efficient.
Mike.McManus@FtCollins.NCR.com (Mike McManus) (04/04/91)
(Couldn't get this to go via email.)
I'll admit up front that most of what little I know about Linear Feedback Shift
Registers (LSFRs) comes from a 3-day "survey" class on testability techniques,
so it's not terribly complete, but here goes...
You are looking for what are colled "primitive polynomials", those which are
irreducible (no factors) and for which the smallest positive integer that
allows the polynomilal to divide evenly (modulo 2) into (x^r + 1) is r = 2^m -
1. It can be shown that such primitive polynomials can be used to describe
maximal length LSFRs (based on the degree of the polynomial).
Research has been done on the subject (and the table you are looking for
compiled) by W. W. Peterson and E. J. Weldon, though I don't have an exact
reference for you. One possibility might be "Error-correcting Codes", 2nd Ed.,
The Colonial Press, 1972 (at least that's the reference stated in my class
notes). Not sure if their table goes up to degree 33, though!
As far a start-up state of the circuit, you will need to set the seed yourself
to make sure it's not 0. Having a power-on circuit to set at least one element
of your LFSR to 1 should suffuce, with the rest reseting randomly. In some
sequencial circuits, however, the starting seed condition may be very important
if you are trying to produce pseudo-ramdom test patterns!
Good luck.
--
Disclaimer: All spelling and/or grammar in this document are guaranteed to be
correct; any exseptions is the is wurk uv intter-net deemuns,.
Mike McManus Mike.McManus@FtCollins.NCR.COM, or
NCR Microelectronics ncr-mpd!mikemc@ncr-sd.sandiego.ncr.com, or
2001 Danfield Ct. uunet!ncrlnk!ncr-mpd!garage!mikemc
Ft. Collins, Colorado
(303) 223-5100 Ext. 378
ee5391aa@triton.unm.edu (Duke McMullan n5gax) (04/05/91)
I may be totally off the beam here, but I think someone was asking about linear feedback shift registers (LFSRs). The classic of the field is considered to be: _Shift_Register_Sequences_ Simon W. Goulmb Holden-Day, San Francisco (1967). Hope it helps, d
spcecdt@deeptht.santa-cruz.ca.us (John DuBois) (04/05/91)
In article <1991Mar27.101754.5326@specialix.co.uk> stevem@specialix.co.uk (Steven Murray) writes: + + 'Pseudo-Random Binary Sequences', sometimes known as +'m-sequences' and the basis for random number generation in some +electronic and software products, are produced by a 'shift-register' +where the input to the shift-register is an X-OR of some of the +shift-register outputs (usually called taps). At each clock of +the shift-register, a new bit of 'pseudo-random' sequence is +generated at the XOR outupt. The only danger is that the S/R +must not be allowed to power up in the 'all-zero's' condition - +because it will never change - and that the correct Taps are used. + +There's the rub, has anyone got a definitive list of PRBS taps? +I saw one in a book once - a reference text - but didn't copy it. +The length of the PRBS sequence with proper taps ('maximal length') +is normally (2^n)-1, where n is the number of S/R bits - without +getting greedy, I saw taps for a 33 bit SR once - has anyone got +the taps for anything longer? Here's a list that someone sent me when I asked this same question a while ago. Have fun. John Shift Register Taps for Psuedorandom Sequences backward forward 2: 1 2 | 1 2 3: 1 3 | 2 3 4: 1 4 | 3 4 5: 2 5 | 3 5 | 6: 1 6 | 5 6 7: 1 7 | 6 7 8: 2 3 4 8 | 4 5 6 8 9: 4 9 | 5 9 10: 3 10 | 7 10 | 11: 2 11 | 9 11 12: 1 4 6 12 | 6 8 11 12 13: 1 3 4 13 | 9 10 12 13 14: 1 3 5 14 | 9 11 13 14 15: 1 15 | 14 15 | 16: 2 3 5 16 | 11 13 14 16 17: 3 17 | 14 17 18: 7 18 | 11 18 19: 1 2 5 19 | 14 17 18 19 20: 3 20 | 17 20 | 21: 2 21 | 19 21 22: 1 22 | 21 22 23: 5 23 | 18 23 24: 1 2 7 24 | 17 22 23 24 25: 3 25 | 22 25 | 26: 1 2 6 26 | 20 24 25 26 27: 1 2 5 27 | 22 25 26 27 28: 3 28 | 25 28 29: 2 29 | 27 29 30: 1 4 6 30 | 24 26 29 30 | 31: 3 31 | 28 31 32: 1 2 22 32 | 10 30 31 32 33: 13 33 | 20 33 34: 1 2 27 34 | 7 32 33 34 35: 2 35 | 33 35 | 36: 11 36 | 25 36 37: 1 2 3 4 5 37 | 32 33 34 35 36 37 38: 1 5 6 38 | 32 33 37 38 39: 4 39 | 35 39 40: 3 4 5 40 | 35 36 37 40 | 41: 3 41 | 38 41 42: 1 2 3 4 5 42 | 37 38 39 40 41 42 43: 3 4 6 43 | 37 39 40 43 44: 2 5 6 44 | 38 39 42 44 45: 1 3 4 45 | 41 42 44 45 | 46: 1 2 3 5 8 46 | 38 41 43 44 45 46 47: 5 47 | 42 47 48: 1 2 4 5 7 48 | 41 43 44 46 47 48 49: 4 5 6 49 | 43 44 45 49 50: 2 3 4 50 | 46 47 48 50 | 51: 1 3 6 51 | 45 48 50 51 52: 3 52 | 49 52 53: 1 2 6 53 | 47 51 52 53 54: 2 3 4 5 6 54 | 48 49 50 51 52 54 55: 1 2 6 55 | 49 53 54 55 | 56: 2 4 7 56 | 49 52 54 56 57: 2 3 5 57 | 52 54 55 57 58: 1 5 6 58 | 52 53 57 58 59: 1 3 4 5 6 59 | 53 54 55 56 58 59 60: 1 60 | 59 60 | 61: 1 2 5 61 | 56 59 60 61 62: 3 5 6 62 | 56 57 59 62 63: 1 63 | 62 63 64: 1 3 4 64 | 60 61 63 64 65: 1 3 4 65 | 61 62 64 65 | 66: 2 3 5 6 8 66 | 58 60 61 63 64 66 67: 1 2 5 67 | 62 65 66 67 68: 1 5 7 68 | 61 63 67 68 69: 2 5 6 69 | 63 64 67 69 70: 1 3 5 70 | 65 67 69 70 | 71: 1 3 5 71 | 66 68 70 71 72: 1 2 3 4 6 72 | 66 68 69 70 71 72 73: 2 3 4 73 | 69 70 71 73 74: 3 4 7 74 | 67 70 71 74 75: 1 3 6 75 | 69 72 74 75 | 76: 2 4 5 76 | 71 72 74 76 77: 2 5 6 77 | 71 72 75 77 78: 1 2 7 78 | 71 76 77 78 79: 2 3 4 79 | 75 76 77 79 80: 1 2 3 5 7 80 | 73 75 77 78 79 80 | 81: 4 81 | 77 81 82: 1 4 6 7 8 82 | 74 75 76 78 81 82 83: 2 4 7 83 | 76 79 81 83 84: 1 3 5 7 8 84 | 76 77 79 81 83 84 85: 1 2 8 85 | 77 83 84 85 | 86: 2 5 6 86 | 80 81 84 86 87: 1 5 7 87 | 80 82 86 87 88: 1 3 4 5 8 88 | 80 83 84 85 87 88 89: 3 5 6 89 | 83 84 86 89 90: 2 3 5 90 | 85 87 88 90 | 91: 2 3 5 6 7 91 | 84 85 86 88 89 91 92: 2 5 6 92 | 86 87 90 92 93: 2 93 | 91 93 94: 1 5 6 94 | 88 89 93 94 95: 1 2 4 5 6 95 | 89 90 91 93 94 95 | 96: 2 3 4 6 7 96 | 89 90 92 93 94 96 97: 6 97 | 91 97 98: 1 2 3 4 7 98 | 91 94 95 96 97 98 99: 4 5 7 99 | 92 94 95 99 100: 2 7 8 100 | 92 93 98 100 -- John DuBois spcecdt@deeptht.santa-cruz.ca.us KC6QKZ
stevem@specialix.co.uk (Steven Murray) (04/08/91)
RE: Getting a decent source of Random Noise.
Has anyone got any comments on this circuit? I've built it and checked
the output on the scope - it LOOKS like noise (I haven't got access to
anything flash like a spectrum analyser). The source of noise (with
really good power supply filtering) is mostly the reversed biased NPN
transistor. I've heard that thermal noise is pretty unpredictable (ie
it qualifies as a good source of noise) is the noise I see across a
reversed biased npn transistor B-E junction actually of thermal origin,
or something else ??
___+12v ___+5v
| |
< 1 megaohm _ > 4.7 kilo-ohm
> | \ <
< __________| \ >
> 0.1uf | | +In \____|____ TTL Noise output
|____| |____| ____| -In / (sampled by micro)
e| | | | | | / LM339
npn ,/ < < |_/
___| 1 meg > >
| b|\ < < 1 megaohm
| c\n.c. > >
| | |
--|-----------------|-----|----- Gnd
Thanks for any comments received.
--
Steven Murray
uunet!slxsys!stevem stevem@specialix.co.uk
I am speaking, but | If these are your opinions, then we are in agreement!!
not for my employer.| Flames, spelling errors, complaints > /dev/nulltgg@otter.hpl.hp.com (Tom Gardner) (04/09/91)
Re different noise sources. Don't forget that you need to specify the spectral shape you need, e.g. white, 1/f, pink, (black?).
tomb@hplsla.HP.COM (Tom Bruhns) (04/11/91)
tgg@otter.hpl.hp.com (Tom Gardner) writes: >Re different noise sources. > >Don't forget that you need to specify the spectral shape you need, >e.g. white, 1/f, pink, (black?). >---------- 'Course, you might also want to spec the amplitude distribution: Gaussian, uniform, ...