Cyclic Redundancy Check

Checks whether transmitted message has an error

Polynomial code

bit strings

polynomials with coefficients of 0 and 1 E.g.: 1, 1, 0, 0, 0, 1 x5 + x4 + x0

Polynomial arithmetic is done modulo 2 +, , *, / on modulo 2 system

0: IntMod(0, 2), 1: IntMod(1, 2)

Cyclic Redundancy Check

Sender and Receiver agree on a generator polynomial G(x) of integer modulo 2

G(x) begins with xr and ends with 1: xr + + 1

Given a G(x) a shift S(x) is xr

Sender: sending a message M(x)

Checksum C(x) = S(x) * M(x) mod G(x)

Transmit T(x) = S(x) * M(x) C(x) such that T(x) mod G(x) = 0

Receiver Check if T(x) mod G(x) = 0 M(x) = T(x) quo S(x)

public class CRC { static final IntMod I = new IntMod(1, 2); static final IntMod O = new IntMod(0, 2); public static Poly sendMessage(Poly msg, Poly gen) { checkPoly(gen); checkPoly(msg); Poly shift = /*TODO: compute x^r, when gen = x^r + ... + 1*/ Poly shiftMsg = /*TODO: compute msg * shift*/ Poly checksum = /*TODO: compute shiftMsg mod gen*/ Poly txMsg = /*TODO: compute shiftMsg - checksum*/ printPoly("msg: ", msg); printPoly("gen: ", gen); printPoly("shift: ", shift); printPoly("shiftMsg: ", shiftMsg); printPoly("checksum: ", checksum); printPoly("txMsg: ", txMsg); return txMsg; }

public static boolean checkMessage(Poly rxMsg, Poly gen) { checkPoly(gen); checkPoly(rxMsg);

Ring rem = /*TODO: compute msg mod gen*/ printPoly("rem: ", (Poly)rem);

return Comp.eq(rem, rem.addIdentity()); }

public static Poly receiveMessage(Poly rxMsg, Poly gen) { checkPoly(gen); checkPoly(rxMsg);

Poly shift = /*TODO: compute x^r, when gen = x^r + ... + 1*/ Poly msg = /*TODO: compute rxMsg quo shift*/ printPoly("shift: ", shift); printPoly("msg: ", msg); return msg; } protected static Poly shiftPoly(Poly gen) { int shiftLen = ((Field[])gen.getCoef()).length; IntMod[] shiftCoef = new IntMod[shiftLen];

/*TODO: compute x^r, when gen = x^r + ... + 1*/ } protected static void checkPoly(Poly poly) { //check whether all coefficients are integer modulo 2 Field[] coefs = poly.getCoef(); for(Field coef : coefs) if(((IntMod)coef).getMod() != 2) throw new IllegalArgumentException("Not a modulo 2 polynomial"); }

protected static void printPoly(String tag, Poly poly) { System.out.format("%s %s ", tag, poly); } public static void testCRC() { /* expected output msg: [1%2, 1%2, 0%2, 1%2, 1%2, 0%2, 1%2, 0%2, 1%2, 1%2, ] gen: [1%2, 1%2, 0%2, 0%2, 1%2, ] shift: [0%2, 0%2, 0%2, 0%2, 1%2, ] shiftMsg: [0%2, 0%2, 0%2, 0%2, 1%2, 1%2, 0%2, 1%2, 1%2, 0%2, 1%2, 0%2, 1%2, 1%2, ] checksum: [0%2, 1%2, 1%2, 1%2, ] txMsg: [0%2, 1%2, 1%2, 1%2, 1%2, 1%2, 0%2, 1%2, 1%2, 0%2, 1%2, 0%2, 1%2, 1%2, ] rem: [0%2, ] shift: [0%2, 0%2, 0%2, 0%2, 1%2, ] msg: [1%2, 1%2, 0%2, 1%2, 1%2, 0%2, 1%2, 0%2, 1%2, 1%2, ] testCRC Success! */ Poly message = new Poly(new IntMod[] {I, I, O, I, I, O, I, O, I, I}); Poly generator = new Poly(new IntMod[] {I, I, O, O, I}); Poly answer = new Poly(new IntMod[] {O, I, I, I, I, I, O, I, I, O, I, O, I, I}); Poly txMsg = sendMessage(message, generator); if(!Comp.eq(answer, txMsg)) throw new RuntimeException("Error: unexpected"); Poly rxMsg = txMsg; if(!checkMessage(rxMsg, generator)) throw new RuntimeException("Error: unexpected");

Poly msg = receiveMessage(rxMsg, generator); if(!Comp.eq(message, msg)) throw new RuntimeException("Error: unexpected"); System.out.println("testCRC Success!"); } public static void main(String[] args) { testCRC(); } }