Skip to content

Instantly share code, notes, and snippets.

@sujathakvr
Last active August 29, 2015 14:20
Show Gist options
  • Save sujathakvr/004fb52e3c1f162df020 to your computer and use it in GitHub Desktop.
Save sujathakvr/004fb52e3c1f162df020 to your computer and use it in GitHub Desktop.
Generating different combinations of polynomials for a given degree 'n'
/**
@author Sujatha
*/
import org.apache.commons.lang.StringUtils;
public class Polynomial {
public static void main(String[] args) {
// TODO Auto-generated method stub
long num = 1;
if (args.length < 0){
System.out.println("Enter a degree of the polynomial to be generated:: ");
System.exit(0);
}
long n = Long.parseLong(args[0]); //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");
temp = getPolynomial(temp, length);
System.out.println(i+": "+temp);
}
}
public static String getPolynomial(String str, int length){
String finalStr = "";
for (char c: str.toCharArray()){
finalStr += c+"x^"+length--+" + ";
}
finalStr += 1;
return finalStr;
}
}
Linear Feedback Shift Register(LFSR):
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.
While implementing the LFSR, one of the tasks involved is generating different combination of polynomials for a given degree say n.
In mathematics, a polynomial is an expression consisting of variables (or indeterminates) and coefficients, that involves only
the operations of addition, subtraction, multiplication, and non-negative integer exponents.
e.g. x^3 + x^2 + x^1 + 1. This is a polynomial of the 3rd degree.
Coming back to the combination of polynomials for 3rd degree, they are as follows:
1. x^3 + x^2 + x^1 + 1
2. x^3 + x^2 + 1
3. x^3 + 1
and so on.
This can be done using the attached java file. The input to the program is an integer.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment