CMIS 310 Notes

Relevant Musings:

Some standard CRC polynomials:

Instructions:

1. Enter the message, as a string of 0's and 1's, in the message field.
   
   
2. Enter the CRC polynomial in the polynomial field, also as 0's and 1's. Make sure that the first and last digits are 1's. The program will accept as many digits are you want (up to the memory of the computer), but the display can get rather messy.
   
   
3. You may enter the CRC code in the indicated field.
   
1. If there is an entry here of the right length, the program will append that code to the message, otherwise the program will append the right number of 0's when the "Reset" button is pressed.
   
2. For example, after a CRC calculation, you can select and copy the register value in the field above the "Reset" button and copy it into the CRC field, then reset and step through the simulation again to check that the receiver would actually get an all 0's result, indicating that the message was received correctly.
   
3. NOTE: If the length of the CRC code in this field is not the right size, which is the order of the polynomial, then the data in the field will be ignored and the polynomial will be padded with 0's.
   
   
4. Press the "Reset" button to initialize the simulation. This will automatically append the right number of 0's or the CRC code to the end of the message.
   
   
5. Press the "Step" button to step through the shift register calculations.
   
   
6. When the message is processed, the field above the "Step" button will say "Done". The final CRC code is shown in the registers and in the field above the "Reset" button.

See Stallings, 6th edition, pages 206-207 for a more detailed explanation of shift registers and calculating CRC's.

• Cyclic redundancy check - Wikipedia 
• Shift register - Wikipedia

Code - Application example:

// example of a shift register, for appletviewer or over net
//   as applet
// History:
//   10/23/1999 - created
//   10/27/1999 - added graphics
//   06/28/2019 - moved to swing + JFrame and JDK 8 features

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Dimension;
import java.awt.BorderLayout;
import java.awt.GridLayout;

import javax.swing.JPanel;
import javax.swing.JFrame;
import javax.swing.JTextField;
import javax.swing.JButton;
import javax.swing.JLabel;

import java.awt.event.*;

class ShiftRegisterSurface
extends JPanel
{
   public static final long serialVersionUID = 123; // ND: junk
   boolean [] poly, reg, msg;
   int ind;
   int regStart;
   int width, height;
   final int XSTEP = 8;
   final int CIRCLERADIUS = 3;
   final int YLINE=20, YREG=50;

   public ShiftRegisterSurface (boolean [] p, boolean [] r, boolean [] m, int i) {
      poly = p;
      reg  = r;
      msg  = m;
      ind  = i;
      setPreferredSize (new Dimension (10, 150));
   } // end normal constructor

   public void paint (Graphics g) {
      super.paint (g);
      Dimension dim = new Dimension (getSize());
      int x=2, y=YLINE;
      String st;
      setBackground (Color.yellow);
  
      width = dim.width;
      height = dim.height;
  
      if (poly == null || reg == null) {
         g.drawString ("Unitialized", x, y);
         return;
      } // end uninited
  
      for (int i = poly.length - 1; i >= 0; i--) {
         st = "0";
         if (poly[i]) st = "1";
         g.drawString (st, x, y);
         x = x + XSTEP;
      } // end for poly elements
  
      x = width - 30 - msg.length * XSTEP;
      regStart = x;
      for (int i = 0; i < msg.length; i++) {
         st = "0";
         if (msg[i]) st = "1";
         g.drawString (st, x, y);
         x = x + XSTEP;
      } // end for poly elements
  
      drawRegisters (g);
   } // end paint

   public void markMessage (Graphics g) {
      int x, y=YLINE;
      g.setColor (Color.red);
      g.drawRect (regStart + ind * XSTEP-1, y-15, XSTEP, 17);
      g.setColor (Color.black);
   } // end method markMessage

   public void drawRegisters (Graphics g) {
      int number = reg.length;
      int x, xs, xs2, xcb, xd, xe, y, yl, ycb;
      int cr=CIRCLERADIUS;
      float step = (float) width / (float) (2 * number + 1);
      String st1 = "1", st0 = "0";
      xs = Math.round(step);
      xs2 = Math.round (step/2.0f);
      y = YREG;
      x = Math.round (step * 0.5f);
      xe = x + Math.round (step * (number * 2 - 0.5f));
      xd = 3;
      yl = y + 80;
      g.drawLine (x+xs2, yl, xe, yl);
      ycb = y - cr + 10;
      g.drawLine (x+xs2, yl, x+xs2, y+20);
  
      if (ind < msg.length) {
         if (msg[ind]) g.drawString (st1, xe, y);
         else g.drawString (st0, xe, y);
      } // end if ind OK
  
      markMessage (g);
  
      for (int i = 0; i < number; i++) {
         x = Math.round (step * (2*i + 0.5f) );
         xcb = x+xs+xs2;
         g.drawRect (x, y, xs, 20);
         if (reg[number-i-1]) {
            g.drawString (st1, x + xs2, y+15);
         } // end if 1 in polynomial
         else g.drawString (st0, x + xs2, y+15);
         g.drawOval (xcb-cr,
                      ycb,
                      2*cr+1,
                      2*cr+1);
         if (poly[number-i-1]) {
            g.drawLine (xcb, yl, xcb, ycb+2*cr+1);
            if (reg[number-1]) g.drawString (st1, xcb+xd, y+25);
            else g.drawString (st0, xcb+xd, y+25);
         } // end if poly = 1
         g.drawLine (x+xs  , ycb+cr, xcb-cr , ycb+cr);
         if (i != number-1) g.drawLine (xcb+cr+1, ycb+cr, x+xs+xs, ycb+cr);
      } // end for each element in register
   } // end methoed drawRegisters
} // end class ShiftRegisterSurface

public class ShiftRegister
extends JFrame
{
   public static final long serialVersionUID  = 123; // ND: junk

   ShiftRegisterSurface srs;
   JPanel pan;
   JTextField input;
   JTextField polynomialStringInput;
   JTextField crcStringInput;
   JLabel inputLabel, polyLabel, crcLabel;
   JTextField regField, infoField;
   JButton stepButton, resetButton;

   boolean[] register, message, poly, result;
   int index;
  
   // main:
   public static void main (String [] args) {
      new ShiftRegister ();
   } // end main
  
   // Methods

   public boolean [] stringToBooleanArray (String st) {
      return stringToBooleanArray (st, 0);
   } // end method stringToBooleanArray (String)

   public boolean [] stringToBooleanArray (String st, int len) {
      boolean [] boolA = new boolean [st.length() + len];
      for (int i = 0; i < st.length(); i++) {
         if (st.charAt(i) == '0') boolA[i] = false;
         else boolA[i] = true;
      } // end for every character of string
      for (int i = st.length(); i < st.length()+len; i++) {
         boolA[i] = false; // append 0's
      } // end for rest of string
      return boolA;    
   } // end method stringToBooleanArray (String, int)

   public ShiftRegister () {
      pan = new JPanel(new GridLayout(5,2));
  
      srs = new ShiftRegisterSurface(poly, register, message, 0);
      srs.setSize (150,150);
      srs.setBackground (Color.yellow);
      srs.setVisible  (true);
       add (srs, BorderLayout.NORTH);
  
      inputLabel = new JLabel ("Message:   ");
      inputLabel.setHorizontalAlignment (JLabel.RIGHT);
      pan.add (inputLabel);
  
      input = new JTextField (10);
      pan.add (input);
  
      polyLabel = new JLabel ("Polynomial:   ");
      polyLabel.setHorizontalAlignment (JLabel.RIGHT);
      pan.add (polyLabel);
  
      polynomialStringInput = new JTextField (10);
      pan.add (polynomialStringInput);
  
      crcLabel = new JLabel ("CRC String (Optional):   ");
      crcLabel.setHorizontalAlignment (JLabel.RIGHT);
      pan.add (crcLabel);
  
      crcStringInput = new JTextField (10);
      pan.add (crcStringInput);
  
      regField = new JTextField(20);
      pan.add (regField);
  
      infoField = new JTextField(20);
      pan.add (infoField);
  
      resetButton = new JButton ("Reset");
      pan.add (resetButton);
  
      stepButton = new JButton ("Step");
      pan.add (stepButton);
  
      add (pan, BorderLayout.SOUTH);
     
      input.addActionListener                 (e -> reset());
      polynomialStringInput.addActionListener (e -> reset());
      crcStringInput.addActionListener        (e -> reset());
      resetButton.addActionListener           (e -> reset());
     
      stepButton.addActionListener            (e -> stepRegister());

      pack ();
      setLocationRelativeTo (null);
      setDefaultCloseOperation (JFrame.EXIT_ON_CLOSE);
      setVisible (true);
   } // end constructor

   public void reset () {
      int padding;
     
      String strPSI = polynomialStringInput.getText().trim();
      String strCSI = crcStringInput.getText().trim();
      String strMSI = input.getText().trim();
      strPSI = strPSI.replaceAll (" ", "");
      strCSI = strCSI.replaceAll (" ", "");
      strMSI = strMSI.replaceAll (" ", "");
     
      if (strMSI.length() == 0) return;
      if (strPSI.length() == 0) return;
     
      StringBuffer sb = new StringBuffer (strPSI);
      sb.reverse();
      poly = stringToBooleanArray (new String (sb));
     
      padding = poly.length - 1;
      if (strCSI.length() == padding) {
         strMSI = strMSI + strCSI;
         padding = 0;
      } // end if crc right length
      message = stringToBooleanArray (strMSI, padding);
      index = 0;
      srs.ind = index;
      register = new boolean [poly.length - 1];
      for (int i = 0; i < register.length; i++)
         register [i] = false;
      infoField.setText ("Reset");
      regField.setText ("");
     
      srs.poly = poly;
      srs.reg  = register;
      srs.msg  = message;
      srs.repaint();
   } // end method reset

   public void stepRegister () {
      boolean carry = register [register.length - 1];
      if (index >= message.length) {
         infoField.setText ("Carry: " + carry + " Index: " + index + " Done");
         return;
      } // end if message done
      for (int i = register.length - 1; i > 0; i--) {
         register [i] = register [i-1] ^ (carry & poly [i]);
      } // end for 1 to n-1 register locations
      register [0] = message [index] ^ carry;
      index++;
      srs.ind = index;
      regField.setText ("Register: " + baToString (register));
      infoField.setText ("Carry: " + carry + " Index: " + index);
      srs.repaint();
   } // end method stepRegister

   public void printBooleanArray (boolean [] b) {
      System.out.println (baToString (b));
   } // end method printBooleanArray

   public String baToString (boolean [] b) {
      char [] sb = new char [b.length];
      char trueChar = '1';
      char falseChar = '0';
      for (int i = 0; i < b.length; i++) {
         if (b[i] == true) sb[b.length - i - 1] = trueChar;
         else sb[b.length - i - 1] = falseChar;
      } // end for every element in array
      return new String (sb);
   } // end method baToString
} // end class shiftRegister