Home Assignments Lecture Blog Resources Discussion Group

Linear Feedback Shift Register (part A)

We will be completing the linear feedback shift register assignment described at

For this portion of the assignment, you will:

  • implement the LFSR class
  • implement unit tests using the Boost test framework


Please do the following:

  • Install Boost into your development environment. From the shell:
sudo apt-get install libboost-test-dev
  • See for an introduction to using Boost.

    If you're working on Mac, take a look at the above link (because it introduces how to use Boost). Then, follow these installation instructions.
  • Per the Princeton assignment, implement the LFSR class, with the following methods:
    • constructor which accepts a C++ String of 1 and 0 characters, and a tap position;
    • int step() function of zero args which returns an int that will be a zero or a one;
    • int generate(int k) function that returns a k–bit integer;
    • instead of implementing the toString method, overload the << stream insertion operator to display its current register value in printable form (see these instructions)
The implementation must be contained in files named LFSR.cpp and LFSR.hpp.
A note to give guidance on your internal representation: Your code must work with seed strings up to 32 bits long.
  • Two additional unit tests in Boost, in a file test.cpp. Here is a starter file for your tests: Attach:test.cpp. You must have two more sets of tests in additional OST_AUTO_TEST_CASE blocks. Each block should be commented with a short discussion. Try to test some edge cases of your implementation (e.g. very long or short seed strings).
  • Create a Makefile to build your project. You must compile LFSR.cpp and test.cpp, and link them together with the boost_unit_test_framework library into an executable named ps2a.
Your Makefile should have the targets all, LFSR.o, test.o, ps2a, and clean, and make sure all prerequisites are correct (e.g., LFSR.o should have LFSR.cpp and LFSR.hpp as prerequisites).
  • Submit a ps2a-readme.txt file that includes:
    (1) your name,
    (2) an explanation of the representation you used for the register bits (how it works, and why you selected it), and
    (3) a discussion of what's being tested in your two additional Boost unit tests.
  • Make sure all your files are in a directory named ps2a

Submit instructions

Archive and submit your source code files test.cpp, LFSR.cpp, and LFSR.hpp plus your Makefile and your ps2a-readme.txt. The executable that the Makefile builds must be called ps2a. If you additionally have a main.cpp file with some printf-style tests, you may include that too. Submit via Bottlenose:

Martin section (201):
Grinberg section (202):

Grading rubric

Note: A main file is not required for this assignment.

core implementation4full & correct implementation=4 pts; nearly complete=3pts; part way=2 pts; started=1 pt
Makefile2Makefile included and works
your own test.cpp2should have at least 3 test cases for full credit
  (including starter case)
ps2a-readme.txt2included and covers material required

Just for fun

Maybe you want to test that your LFSR actually goes through 2^k - 1 steps before recycling (where k is the length of the seed)?

You can use the std::streamstring class to get your current register value into a string; e.g.:

   #include <sstream>
   LFSR l("001", 1);  
   std::stringstream buffer;
   buffer << l;

   if (buffer.str().compare("001") == 0)
     std::cout << "yeah!\n";
     std::cout << "argh!!\n";

You can use this ability to keep stepping your LFSR and count how many steps it takes for the register to recycle back to the initial seed.