pseudo-random binary sequence
timm...@my-deja.com
binary sequence means and how it works. If I have a series of such
codes, how do I decode and get back the original sequence? Thank you
very much.
Tim
Sent via Deja.com http://www.deja.com/
Before you buy.
Allan Herriman
>I would like to know how a modulo-2 addition with a pseudo-random
>binary sequence means and how it works. If I have a series of such
>codes, how do I decode and get back the original sequence? Thank you
>very much.
Tim,
The modulo 2 addition is just an XOR gate.
It has the following truth table:
A B (A xor B)
0 0 0
0 1 1
1 0 1
1 1 0
Another way of looking at this is that one of the inputs controls
whether the other one gets inverted or not.
Xoring your bit stream with a PRBS is also known as scrambling. This
is often used in modems as a means to reduce the run length of ones or
zeros sent to the modulator, which aids timing recovery. It also
improves the output spectrum.
There are two common methods for scrambling.
The first simply XORs the bitstream with a free running PRBS.
Typically the PRBS generator will be an LFSR. See Xilinx XAPP 052,
http://www.xilinx.com/xapp/xapp052.pdf
for a description of free running LFSRs.
input->(X)--> output
^
|
+--->SHIFT_REGISTER
| | |
(X)<-----+ |
^ |
| |
+-----------------+
Here, (X) is a 2 input XOR gate.
The second feeds the data *through* the LFSR as follows:
+-->output
|
input->(X)-+->SHIFT_REGISTER
^ | |
| | |
(X)<------+ |
^ |
| |
+------------------+
I know of three ways to recover the original data from the scrambled
signal.
Method 1. Self synchronising descramber.
Use the second method of scrambling, and feed the scrambed signal into
the following circuit:
input---+---->SHIFT_REGISTER
| | |
outpt<-(X) | |
^ | |
| | |
(X)<------+ |
^ |
| |
+------------------+
After a while (= number of bits in shift register), the output will be
correctly unscrambled.
One disadvantage of the self synchronising scramber is that a single
bit error in the scrambled signal will turn into (1 + number of taps)
bit errors at the output of the descrambler.
Method 2. Self synchronising scrambler with free run mode.
The above descrambler can be changed so that once the receiver has
obtained lock, the LFSR can be switched to free run mode (disconnected
from the input). This gets around the bit error multiplication effect
of method 1.
Method 3. Externally synchronised scramblers.
Here both the scrambler and the descrambler look like the circuit I
drew for the first method of scrambling, except that the LFSRs are
reset at a particular point in the frame. This synchronises them.
(I'm assuming that you have a framing signal somewhere.) It gets more
interesting when the framing signal in the receiver relies on the
output of the descrambler...
Method 1 is commonly used in just about everything.
I've used Method 3 quite successfully in radio modems I've designed.
I've heard that Method 2 is used in error rate test sets (which
generally use LFSRs to generate their test sequences, and also require
the number of errors counted to be accurate). Refer to ITU-T O.150,
etc.
I hope this wasn't a homework problem.
Does anyone know of any other ways of synchronising descramblers?
Regards,
Allan.
kapp_...@my-deja.com
timm...@my-deja.com wrote:
> I would like to know how a modulo-2 addition with a pseudo-random
> binary sequence means and how it works. If I have a series of such
> codes, how do I decode and get back the original sequence? Thank you
> very much.
>
the answer to your question has three parts.
1) A pseudo-random binary sequence is a sequence of 0s and 1s that is
generated by an algorithm - thus not truly random, but pseudo random,
since the sequence is mathematically defined and repeatable. There are
lots of algorithms around to generate said sequences, the most commonly
used (I think) in hardware being a so called
linear-feed-back-shift-register (LFSR). This can be built in different
ways. Again common is to tap some (but not all) of the shift register
cells outputs, add the taps (EXORing them) and feed the result back to
the input. Of course, care must be taken to obtain the maximum sequence
length and to avoid falling into a short cycle or static mode (like
000...000). The sequence of 0s and 1s at the output looks random to
anyone not knowing the structure of the LFSR, the longer the LFSR, the
more random.
2) The data to be coded or scrambled must first be serialized. With
every clock cycle one data bit is modulo-2-added with one bit of the
pseudo random sequence, that is EXORed (modulo-2 means just add two
numbers, divide by 2 and keep only the remainder). With the next clock
cycle both LFSR and data stream are advanced one step and the
modulo-2-addition is repeated. Thus the data stream will look
pseudo-random itself.
3) At the receiving end the scrambled data stream is again
modulo-2-added to the same pseudo-random-sequence. Since
(((data+x)mod2)+x)mod2=2 the original serial data is reconstructed
(assuming no data was disturbed during transmission). Of course, this
requires knowledge of the coding LFSR at both ends of the transmission
and some means of synchronizing both LFSRs.
Hope that helps?
For a tutorial on the topic you might have a look at the following
article:
"A tutorial on CRC computations", T.V.Ramabadran&S.S.Gaitonde, in IEEE
MICRO, August 1988, pages 62-74