Generating an M-Sequence or Maximum Length Sequence(MLS) as part of the Linear Feedback Shift Register(LFSR) Implementation output in java

MSequence.java

/**
	@author Sujatha
*/
import java.util.ArrayList;

import org.apache.commons.lang.StringUtils;

public class MSequence {

	public static void generatePolynomial(String degree) {
		long num = 1;

		long n = Long.parseLong(degree); // this is the n value which is of the
											// highest order

		num = num << (n);
		int length = Long.toBinaryString(num).length() - 1;
		String temp = null;

		System.out.println("Number of Combinations of expressions:: "
				+ (num - 1));
		for (long i = 1; i < num; i++) {
			temp = StringUtils.leftPad(Long.toBinaryString(i), length, "0");
			System.out.println(i + ": " + getPolynomial(temp, length));
			if (temp.charAt(0) == '1') {
				System.out.println("Generating M-Sequence......");
				generateMSequence(temp + "1", degree);
			}

		}
	}

	public static String getPolynomial(String str, int length) {
		String finalStr = "";
		for (char c : str.toCharArray()) {
			finalStr += c + "x^" + length-- + " + ";
		}
		finalStr += 1;
		return finalStr;
	}

	public static void generateMSequence(String p, String degree) {
		// String poly1 = "1011"; // "101"
		// TODO Auto-generated method stub
		System.out
				.println("Polynomial Coefficients passed along with constant :: "
						+ p);
		String polynomial = p.substring(1); // x^2 + x^1 + 1 coefficients are
											// represented in this string in x^3
		System.out
				.println("Polynomial Coefficients passed along without constant :: "
						+ polynomial);
		// String initialState = "1000"; //degree 3 polynomial
		// String initialState = "1001";
		// String initialState = "001";
		String initialState = StringUtils.rightPad("1", polynomial.length(),
				"0");
		System.out.println("Initial State :: " + initialState);

		int n = initialState.length();
		boolean[] bitsArray = new boolean[n];
		for (int i = 0; i < n; i++) {
			if (initialState.charAt(i) == '1') {
				bitsArray[i] = true;
			} else
				bitsArray[i] = false;
		}

		// msequence bit
		StringBuilder output = new StringBuilder();
		output.append(bitsArray[n - 1] ? "1" : "0");

		// find the xor bits
		int[] tapArray = new int[n];
		// create tap array
		for (int i = 0; i < n; i++)
			tapArray[i] = (polynomial.charAt(i) == '1') ? i : -1;

		boolean k = bitsArray[tapArray[n - 1]];
		// xor the bits which are in the tap
		for (int i = n - 2; i > 0; i--) {
			if (tapArray[i] > 0)
				k ^= bitsArray[tapArray[i]];
		}

		long count = 1 << polynomial.length();
		int j = 0;
		while (j < count - 2) {
			StringBuilder temp = new StringBuilder();

			// shift bits by 1 position
			for (int i = n - 1; i > 0; i--)
				bitsArray[i] = bitsArray[i - 1];

			bitsArray[0] = k;

			for (int i = 0; i < n; i++)
				temp.append(bitsArray[i] ? "1" : "0");

			output.append(bitsArray[n - 1] ? "1" : "0");

			if (temp.toString().equals(initialState)) {
				System.out.println("This is not an m sequence");
				break;
			}

			// this is for the first time xor for the first initial state
			k = bitsArray[tapArray[n - 1]]; // b0

			// xor the bits which are in the tap
			for (int i = n - 2; i > 0; i--) {
				if (tapArray[i] > 0)
					k ^= bitsArray[tapArray[i]];
			}

			j++;
		}
		System.out.println(output);
	}

	public static ArrayList<String> generateInitialState(String degree) {
		long num = 1;
		long n = Long.parseLong(degree); // this is the n value which is of the
											// highest order
		num = num << (n);
		int length = Long.toBinaryString(num).length() - 1;
		ArrayList<String> initialStateList = new ArrayList<String>();
		for (long i = 1; i < num; i++) {
			String temp = StringUtils.leftPad(Long.toBinaryString(i), length,
					"0");
			initialStateList.add(temp);
		}

		return initialStateList;
	}

	public static void main(String[] args) {
		if (args.length < 0) {
			System.out.println("Enter a n value ");
			System.exit(0);
		}
		generatePolynomial(args[0]);
	}

}

MSequence.txt

This involves generating an MSequence for the nth degree polynomial for the LFSR implementation.
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.

A maximum length sequence (MLS) is a type of pseudorandom binary sequence.

They are bit sequences generated using maximal linear feedback shift registers and are so called because they are periodic and reproduce every binary sequence (except the zero vector) that can be represented by the shift registers (i.e., for length-m registers they produce a sequence of length 2m − 1). An MLS is also sometimes called an n-sequence or an m-sequence. MLSs are spectrally flat, with the exception of a near-zero DC term.

Generating the MLS given the degree of the polynomial can be achieved through the following code.