Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!uunet!sco!gorn!deeptht!spcecdt From: spcecdt@deeptht.santa-cruz.ca.us (John DuBois) Newsgroups: sci.electronics Subject: Re: Pseudo-random numbers Keywords: PRBS,m-sequence,random Message-ID: <1991Apr5.131838.10696@deeptht.santa-cruz.ca.us> Date: 5 Apr 91 13:18:38 GMT References: <1991Mar27.101754.5326@specialix.co.uk> Distribution: sci Organization: The Armory Lines: 147 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