Recent Changes - Search:
ECG Home

GitHub

People

Publications

Calendar

Projects

Fall 2017

Older Courses

Spring 2017

Fall 2016

Spring 2016

Fall 2015

Spring 2015

Fall 2014

Spring 2014

Fall 2013

Spring 2013

Fall 2012

Spring 2012

Fall 2011

Spring 2011

Fall 2010

Spring 2010

Fall 2009

Spring 2009

Fall 2008

Spring 2008

Fall 2007

HOWTOs

edit SideBar

PS2a

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

Details

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++ 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): https://grader.cs.uml.edu/assignments/473
Grinberg section (202): https://grader.cs.uml.edu/assignments/472

Grading rubric

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

FeatureValueComment
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
Total10 

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";
   else
     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.

Edit - History - Print - Recent Changes - Search
Page last modified on February 09, 2015, at 06:39 PM