I would like to create a 16 bit CRC. Actually I am entirely ready whit that, so a couple of hours ago I tested it, but did not work properly. But what I discovered is that the examples on the internet might be wrong when its about binary division. I link just two of them (from a lot!): http://www.ross.net/crc/download/crc_v3.txt , http://en.wikipedia.org/wiki/Cyclic_redundancy_check
So what I am doing with the binary division is that I use BigIntegers. Just like this:
BigInteger divisor = new BigInteger("10011", 2);
BigInteger dividend = new BigInteger("11010110110000", 2);
BigInteger[] result = dividend.divideAndRemainder(divisor);
These values can be seen in the first link (6. fully worked example). Lets see the results, the reference gives me 1110 for the remainder, my upper code gives me 111. Might be code wrong? I dont think so.. Lets count it in decinal: 13744/19 = 723 and remainder is 7.. So the code gives me 111 which is actually 7 in decimal, but the example gives me 1110, which is 14. It is wrong isn'it?
If you see the wikipedia example, it gives wrong again, both for the 1st and both for the 2nd calculation. When I count them with the upper code, it gives me a good result in decimal. And almost all the examples I checked, I got the same results. So actually, what the hell am i missing?
Hey kiddos, as I promised I provide a fully-wroking binary divison which uses CRC arithmetic! If you want to use polynomial arithetmic the upper code is completely OK!! Just use the getRemainder() method and add two Strings, it counts the remainder. Remember: if your bits arrived correctly, the remainder will be 0! In this example, it gives you a string with 0 length! Use it with fun!
public class BinaryDivision {
String substracted;
public BinaryDivision(){
}
public String getRemainder(String dividend, String divisor){
int dividendLength = dividend.length();
int divisorLength = divisor.length();
String quotient="";
String examinedP="";
String divisorP="";
substracted="";
int indexNumber;
int substractZeros=0;
for (int i=0;i<divisorLength;i++){
examinedP = examinedP + dividend.charAt(i);
}
indexNumber = divisorLength;
for (int j=0;j<(dividendLength-divisorLength);j++){
//START
if ( Integer.parseInt(String.valueOf(examinedP.charAt(0)))==1){
quotient=quotient + "1";
int a = divisor.length();
//substracting
for (int i = 0;i<a;i++){
// System.out.println(examinedP.charAt(i) + " " + divisor.charAt(i));
substracted = substracted +
CRC_substract(Integer.parseInt(String.valueOf(examinedP.charAt(i))),
Integer.parseInt(String.valueOf(divisor.charAt(i))));
}
substracted = substracted.substring(1);
//----------------------------------------------
substracted = substracted + dividend.charAt(indexNumber);
}
else {
quotient=quotient + "0";
int a = divisor.length();
//substracting
for (int i = 0;i<a;i++){
//System.out.println(examinedP.charAt(i) + " " + 0);
substracted = substracted +
CRC_substract(Integer.parseInt(String.valueOf(examinedP.charAt(i))),
0);
}
substracted = substracted.substring(1);
substracted = substracted + dividend.charAt(indexNumber);
}
examinedP = substracted;
//System.out.print(examinedP);
substracted="";
//System.out.println(" "); System.out.println(" ");
indexNumber++;
}
//counting remainder - if it starts with 0 - bye bye 0s..
for (int i = 0;i<examinedP.length();i++){
if (Integer.parseInt(String.valueOf(examinedP.charAt(i)))==0){
substractZeros++;
}
else {
break;
}
}
examinedP = examinedP.substring(substractZeros);
// System.out.println(" "); System.out.println(" ");
// System.out.print(examinedP);
return examinedP;
}
//XOR - Exclusive OR
public int CRC_substract(int a, int b){
if (a==0 && b==0){
return 0;
}
else if (a==0 && b==1){
return 1;
}
else if (a==1 && b==0){
return 1;
}
else if (a==1 && b==1){
return 0;
}
return -1;
}
}
See chapter five from your first link: They are using "CRC arithmetic". The main difference to "normal" arithmetic is that they do not use carries. The addition sample shown in chapter five is easier to understand than the division and shows the difference:
10011011
+11001010
--------
01010001
In normal arithmethic using carries, this would be
10011011
+11001010
--------
101100101
Since BigDecimal uses "normal" arithmetic, you get a different result than shown in your references.