PRBS generator with rsds tx

A psuedo-random binary sequence is just a string of binary numbers -

8,388,607 for the 23-it case.

How you generate it is irrelevant. You could read it out of memory if necessary, though this uses up a lot more silicon than a 23-bit shift register and an exclusive-OR gate.

Win Hill's "The Art of Electronics" includes a useful discussion of the subject starting at section 9.32.

-- Bill Sloman, Nijmegen

Is there an algorithm for figuring out which bits to XOR to get the maximum length sequence for a given size of SR, or is it just by-guess-and-by-gosh?

Thanks, Rich

According to "The Art of Electronics" the criterion for maximal length is that the polynomial

1 + x^n + x^m

must be polynomial and prime over the Galois field, where m is the length of the shift register in bits, and n is the tap number.

I tried to make sense of a similar assertion when looking at error- detecting and error-correcting codes back in 1970, and didn't get anywhere at all. Mathematicians who study the algebra of finite fields seem to do better.

-- Bill Sloman, Nijmegen

So the algorithm is to try a set of feedback bits and see if it meets the requirement. There IS a maximal length sequence for all shift register lengths; in fact, there are huge numbers of them for long shift registers. It's relatively quite easy to determine the number of maximal length polynomials of a given order. Finding them for long registers--high orders--is not necessarily easy (or fast). However, once you've found one, you can generate lots of others easily. For some cases, there are not any feedback schemes using only two values xored together; for some you need to modulo-2 sum four bits, minimum. (It's relatively easy to show that you always need an even number of bits fed back, and it should be obvious that you always must include the last bit.) You can find lists of feedback that works--of maximal length polynomials. The ap notes on the Xilinx web site has one such list, up to some pretty long sequences. Finding a maximal length polynomial for some arbitrary but high order (hundreds or even thousands) would be a good task for the idle time of processors distributed around the world, connected by the internet. That's been used to find some related numbers...numbers such that 2^n-1 is prime. How those are related to maximal length shift registers is left for another day...

Cheers, Tom

Xilinx app note XAPP 052 lists the taps up to 168 bits, but maybe a Galois LFSR might be better for hardware inplementation if speed is an issue.

Best regards, Spehro Pefhany

--
"it\'s the network..."                          "The Journey is the reward"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com

Ok, Spehro, exactly what is the difference between the polynomials listed in the app note and "a Galois LFSR"? How might the latter be faster?

AFAIK, I can make a shift register whose natural response is represented by any boolean polynomial you wish, within the limits of being able to clock all the bits simultaneously, and the speed is reduced only by increased capacitive loading on the output register.

Cheers, Tom

That was the low hanging fruit, how do you apply a 7 phase PLL to an rsds transmitter? How does it interact with the prbs generator?

--
 JosephKK
 Gegen dummheit kampfen die Gotter Selbst, vergebens.  
  --Schiller

Basically you use a 7 phase PLL to fetch data from 7 parallel ports. But if the same method is used to get values from 7 random points on a

23 bit PRBS generator, we would end up with sequences repeating at random and before the end of a single cycle of the prbs generator.

@Rich, Maxim has a list of tap points for 2-32 bit PRBS here,

Thanks

How the hell would I know? I don't know what an rsds transmitter is, and I've no idea how it uses a 7-phase PLL.

This doesn't invalidate the useful point I made about generating psuedo-random binary sequences - you don't have to use a tapped shift register as the source of the bit sequence.

-- Bill Sloman, Nijmegen

Basically, you would use a serializer to fetch and serialize data from

7 parallel ports(using the 7 phases of the PLL) before the rsds or any other diff. driver. But if a built in 23 bit PRBS generator is used to check the quality of the serializer and driver, it would normally be expected to travel the same path a data would. So that would mean that somehow we have to serialize the 23 PRBS gen data such that only 7 bits are obtained per clock and yet maintain the 23 bit characteristics like 8 million + sequences.

If i just serialize any 7 consecutive ports from the PRBS gen, its not exactly a 23 bit generator. It can be achevied if i use 7 * 23 MUX, but its not practical to use that many MUXes.

Thanks

So...clock the LFSR seven times to get the seven bits you want. What? You want to do it in ONE clock? Fine, no problem. If you express what happens in the LFSR as a matrix equation, x(k+1)=A*x(k), where the matrix multiplication is performed with modulo-2 arithmetic. So then x(k+7)=A^7*x(k). Figure out what A^7 is, and implement what it implies. Depending on just what taps are fed back in your desired sequence, it's likely going to be easier than you think. With only the end and one other tap fed back, there are a lot of zeros in the A matrix. You can even trick Matlab or Scilab into doing the modulo-2 multiplication for you.

Cheers, Tom

Also...since 2^23-1 = 8388607 = 47 * 178481 which are both prime, then taking 7 bits at a time won't repeat till you've clocked 7 bits out

2^23-1 times. That is, you'll go seven times around the cycle before the bits appear in the same places again. Of course, you'll repeat 7- bit words a whole lot of times, since there are only 128 unique 7 bit words.

Cheers, Tom