LFSR implementation using split-table lookup

A computer program device comprising:

• a computer program storage device readable by a digital processing apparatus;
• and
• a program means on the program storage device and including instructions executable by the digital processing apparatus for determining the output of an A linear feedback shift register (A LFSR) having a configuration and having one of a plurality of initial LFSR values, each value being defined by respective bits of the A LFSR, the method steps comprising:
• generating plural model LFSRs, each model LFSR having a respective subset of the bits of the A LFSR;
• generating respective data tables based on the model LFSRs, each data table representing model output values of a respective model LFSR after a predetermined number of shifts;
• and
• determining the output of the A linear feedback shift register by combining the model output values.

A computer including computer readable instructions executable by the computer for performing method steps for determining the output of a linear feedback shift register (LFSR) defining a configuration and having one of a plurality of initial LFSR values, each value being defined by a respective sequence of at least first bits and second bits, the method steps comprising:

• for each initial LFSR value, replacing the first bits with zeroes to establish first model values;
• determining first outputs of the LFSR for each first model value;
• storing in a first table only non-duplicative first outputs;
• for each initial LFSR value, replacing the second bits with zeroes to establish second model values;
• determining second outputs of the LFSR for each second model value;
• storing in a second table only non-duplicative second outputs;
• and
• determining the output of the LFSR by accessing the first table to retrieve a first test output, accessing the second table to retrieve a second test output, and undertaking a bitwise exclusive OR operation on the first and second test outputs.