The Mathematics of LFSR Digital Signal Spreading

Note: The algorithm described here comes from the Spring 1998 notes for Neil Gershenfeld's ``Physics of Information Technology'' class, which are soon to be published in book form.

Given a shift register of length n, a tap vector $\ensuremath{\mathbf{C}} \in \left (G(2)\right)^n$ (a vector of bits of length n), and a data bit $\ensuremath{\mathbf{d}}^{tx}_{i} \in G(2)$,the next encoded bit $\ensuremath{\mathbf{x}}^{tx}_{i}$ is calculated by  

$$\ensuremath{\mathbf{x}}^{tx}_{i} = \sum_{j=1}^{n} \left ( \e... ...math{\mathbf{C}}_{j} \right ) + \ensuremath{\mathbf{d}}^{tx}_i,$$ (1)

where addition is define as logical XOR and multiplication as logical AND. Given a shift register of the same length, an identical tap vector, and a received bit $\ensuremath{\mathbf{x}}^{rx}_{i}$, a data bit $\ensuremath{\mathbf{d}}^{rx}_{i}$ is decoded from the encoded stream as  

$$\ensuremath{\mathbf{d}}^{rx}_{i} = \ensuremath{\mathbf{x}}^{... ...athbf{x}}^{rx}_{i-j} \cdot \ensuremath{\mathbf{C}}_{j} \right).$$ (2)

Assuming $\ensuremath{\mathbf{x}}^{tx}_{i} = \ensuremath{\mathbf{x}}^{rx}_{i}$, then

$$\ensuremath{\mathbf{d}}^{rx}_{i} = \ensuremath{\mathbf{x}}^{... ...athbf{x}}^{tx}_{i-j} \cdot \ensuremath{\mathbf{C}}_{j} \right),$$ (3)

$$\ensuremath{\mathbf{d}}^{rx}_{i} = \sum_{j=1}^{n} \left ( \e... ...thbf{x}}^{tx}_{i-j} \cdot \ensuremath{\mathbf{C}}_{j} \right),$$ (4)

but since addition and subtraction are equivalent in this basis,

$$\ensuremath{\mathbf{d}}^{rx}_{i} = \sum_{j=1}^{n} \left ( \e... ...math{\mathbf{C}}_{j} \right) + \ensuremath{\mathbf{d}}^{tx}_i,$$ (5)

$$\ensuremath{\mathbf{d}}^{rx}_{i} = \ensuremath{\mathbf{d}}^{tx}_i.$$ (6)

Thus, if transmission occurs without error, the original signal can be reconstructed perfectly. Even assuming noisy transmission, encoding schemes can be used on top of the LFSR spreading to ensure no data is lost.