Lab 4¶

Applications of Pseudo-Random Binary Sequences¶

PN sequences are widely used to

  • generate test, measurement and calibration signals
  • generate training signals in communication systems
  • scramble and descramble data in communication systems

Linear-feedback shift register (LFSR)¶

LFSR for PN sequence generation¶

The procedure to produce a PN sequence using the LFSR consists of three steps:

  1. Set the initial values $s[-1], s[-2], \ldots, s[-m]$ so that at least one is nonzero.

  2. Compute the addition modulo 2, equivalent to a series of exclusive or ($\oplus$) operations, of the connected taps in the shift register:

    $$ s[n] = \left( \sum_{k=1}^{m}{h_k s[n-k]} \right) \text{ mod } 2 = \bigoplus_{k=1}^{m}{h_k s[n-k]}$$

  3. Shift each value along the delay line (i.e. increment n), then repeat starting from step two.

Convolution¶

Recall that the convolution operation (denoted using $*$) for two discrete-time signals is defined as:

$$x_1[n]*x_2[n] = \sum_{k=-\infty}^{\infty}x_1[k]x_2[n-k]$$

This operation is often described as 'flip and slide', since $x_2[n-k]$ is a reversed and shifted version of $x_2[k]$.

Cross-correlation¶

The cross-correlation operation (denoted using $\star$) is nearly identical to convolution, but without the 'flip'.

$$x_1[n]\star x_2[n] = \sum_{k=-\infty}^{\infty}\overline{x_1[k]}x_2[n+k]$$

Note: $\overline{x_1[k]}$ denotes the complex conjugate of $x_1[k]$, but for real valued signals $\overline{x_1[k]}=x_1[k]$.

Auto-correlation¶

The auto-correlation $R_{xx}[k]$ of a discrete-time signal $x[n]$ is the cross-correlation with itself:

$$R_{xx}[n] = x[n]\star x[n] = \sum_{k=-\infty}^{\infty}\overline{x[k]}x[n+k]$$

For periodic signals the summation can be simplified, and the result is often normalized by the period $N$.

$$R_{xx}[n] \text{ for periodic signal} = \frac{1}{N}x[n]\star x[n] = \frac{1}{N}\sum_{k=1}^{N}\overline{x[k]}x[n+k]$$

Data scrambling¶

Suppose we have a binary data sequence $x[n]$ that we want to transmit. We can scramble the data by adding (modulo two) a scrambling sequence $s[n]$.

$$x_s[n] = ( x[n] + s[n] ) \text{ mod 2} = x[n] \oplus s[n]$$

We can 'undo' the scrambler (i.e. descramble the data) using the same process:

$$x_d[n] = ( x_s[n] + s[n] ) \text{ mod 2} = x_s[n] \oplus s[n]$$

If the same scrambling sequence $s[n]$ is used for the scrambler and descrambler, then $x_d[n]=x[n].$