Description
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a shift register whose input bit is driven by the XOR of some bits of the overall shift register value.
The initial value of the LFSR is called the seed, and because the operation of the register is deterministic, the stream of values produced by the register is completely determined by its current (or previous) state. Likewise, because the register has a finite number of possible states, it must eventually enter a repeating cycle.
Your challenge today is to implement an LFSR in software.
Example Input
You’ll be given a LFSR input on one line specifying the tap positions (0-indexed), the feedback function (XOR or XNOR), the initial value with leading 0s as needed to show you the bit width, and the number of clock steps to output. Example:
[0,2] XOR 001 7
Example Output
Your program should emit the clock step and the registers (with leading 0s) for the input LFSR. From our above example:
0 001
1 100
2 110
3 111
4 011
5 101
6 010
7 001
Challenge Input
[1,2] XOR 001 7
[0,2] XNOR 001 7
[1,2,3,7] XOR 00000001 16
[1,5,6,31] XOR 00000000000000000000000000000001 16
Challenge Output
(Only showing the first two for brevity’s sake.)
0 001
1 100
2 010
3 101
4 110
5 111
6 011
7 001
0 001
1 000
2 100
3 010
4 101
5 110
6 011
7 001
My Solution
import java.util.LinkedList;
import java.util.BitSet;
import java.lang.StringBuilder;
public class LFSR347 {
private LinkedList<BitSet> lfsr;
private int[] tapPositions;
public LFSR347(int[] initialValues, int[] tapPositions) {
this.lfsr = new LinkedList<BitSet>();
this.tapPositions = tapPositions;
for (int n: initialValues) {
this.lfsr.add(getBit(n));
}
}
public BitSet getBit(int a) {
BitSet b = new BitSet(1);
if (a == 1) b.set(1);
else if (a != 0) throw new IllegalArgumentException();
return b;
}
public String toString() {
Object[] array = this.lfsr.toArray();
StringBuilder sb = new StringBuilder();
for (Object n: array) sb.append(n);
return sb.toString();
}
public String step(String operation) {
BitSet result = this.lfsr.get(this.tapPositions[0]);
for (int i = 1; i < this.tapPositions.length; i++) {
// System.out.print(" " + result);
result.xor(this.lfsr.get(this.tapPositions[i]));
if (operation == "XNOR") result.flip(0);
else if (operation != "XOR") throw new IllegalArgumentException();
}
this.lfsr.removeLast();
this.lfsr.addFirst(result);
return toString();
}
public int xor(int a, int b) {
return a ^ b;
}
public static void main(String[] args) {
int[] initialValues = {0, 0, 1};
int[] tapPositions = {0, 2};
LFSR347 testLFSR = new LFSR347(initialValues, tapPositions);
System.out.println("0 " + testLFSR.toString() + "\n");
for (int i = 1; i < 8; i++) {
System.out.println("\n" + i + " " + testLFSR.step("XOR") + "\n");
}
}
}
Further Reading
Bonus
Write a function that detects the periodicity of the LFSR configuration.
Post-Mortem
I wrote this solution 20 months ago; a post-mortem is in order:
- I left print statements inside functions.
- I didn’t close my
java.io.BufferedReader - I couldn’t get java.util.BitSet working.