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 http://www.cs.princeton.edu/courses/archive/fall13/cos126/assignments/lfsr.html.
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 http://www.alittlemadness.com/2009/03/31/c-unit-testing-with-boosttest/ 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++
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
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
test.cpp, and link them together with the
boost_unit_test_framework library into an executable named
Your Makefile should have the targets
clean, and make sure all prerequisites are correct (e.g.,
LFSR.o should have
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
Archive and submit your source code files
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): https://grader.cs.uml.edu/assignments/473
Grinberg section (202): https://grader.cs.uml.edu/assignments/472
main file is not required for this assignment.
|core implementation||4||full & correct implementation=4 pts; nearly complete=3pts; part way=2 pts; started=1 pt|
|Makefile||2||Makefile included and works|
|your own |
|2||should have at least 3 test cases for full credit|
| || ||(including starter case)|
|ps2a-readme.txt||2||included 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.:
LFSR l("001", 1);
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.