Next: Project Summary
Up: LFSR Signal Spreading
Previous: LFSR 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
(a
vector of bits of length n), and a data bit
,the next encoded bit
is calculated by
|  |
(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
, a data bit
is decoded from the encoded stream as
|  |
(2) |
Assuming
, then
|  |
(3) |
|  |
(4) |
but since addition and subtraction are equivalent in this basis,
|  |
(5) |
|  |
(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.
Next: Project Summary
Up: LFSR Signal Spreading
Previous: LFSR Signal Spreading
root
5/22/1998