Cyclic Redundancy Check (CRC) generation–How to convert a polynomial into a logic circuit that calculates CRC using a parallel equations

This write-up can be supplemented by this article on Wikipedia.

Below is an example of converting CRC-8-ATM polynomial x^8 + x^2 + x + 1 into a parallel circuit for calculating CRC.  I’ll first go through the exercise of how the serial implementation works then describe how to derive a parallel circuit.

The polynomial (x^8 + x^2 + x + 1) converts into a serial implementation like so…

image

For the purposes of clarity, I’ll be calling the flops in this circuit crc. Since this circuit has 8-bits of registers, it creates an 8-bit CRC value or crc[7:0].  In order to create the CRC value, the registers are first loaded with an input message followed by trailing zeroes.  Using the example from the Wikipedia link above, if the input message was 0101_0111 (0x57), the value shifted into the circuit will be 0101_0111_0000_0000 or (0x5700).

To illustrate using more detail, the table below shows the contents of each crc register bit as we shift the input message and trailing zeroes into the serial circuit.  Please note the following:

  • Initially, the circuit’s flops are reset or defaulted to 0.
  • The next value of crc[7] is the contents of crc[6]
  • The next value of crc[6] is the contents of crc[5]
  • The next value of crc[5] is the contents of crc[4]
  • The next value of crc[4] is the contents of crc[3]
  • The next value of crc[3] is the contents of crc[2]
  • The next value of crc[2] is the contents of crc[1] Exclusive-ORed with the contents of crc[7]
  • The next value of crc[1] is the contents of crc[0] Exclusive-ORed with the contents of crc[7]
  • The next value of crc[0] is input Exclusive-ORed with the contents of crc[7]
  •  

      crc[7] crc[6] crc[5] crc[4] crc[3] crc[2] crc[1] crc[0] input
    initial value 0 0 0 0 0 0 0 0 0
    step 1 0 0 0 0 0 0 0 0 1
    step 2 0 0 0 0 0 0 0 1 0
    step 3 0 0 0 0 0 0 1 0 1
    step 4 0 0 0 0 0 1 0 1 0
    step 5 0 0 0 0 1 0 1 0 1
    step 6 0 0 0 1 0 1 0 1 1
    step 7 0 0 1 0 1 0 1 1 1
    step 8 0 1 0 1 0 1 1 1 0
    step 9 1 0 1 0 1 1 1 0 0
    step 10 0 1 0 1 1 0 1 1 0
    step 11 1 0 1 1 0 1 1 0 0
    step 12 0 1 1 0 1 0 1 1 0
    step 13 1 1 0 1 0 1 1 0 0
    step 14 1 0 1 0 1 0 1 1 0
    step 15 0 1 0 1 0 0 0 1 0
    step 16 1 0 1 0 0 0 1 0  

    The final CRC value that is taken from row step 16 is 1010_0010 or 0xA2 in hexadecimal.

    In order to convert the serial circuit to a parallel version, we need to create Exclusive-OR (XOR) equations for each flop.  The symbol for Exclusive-OR is “^”.  We can do this my following a similar method (i.e., shifting) as the previous example except that we use variables instead.  Using a table as before, we still have an 8-bit register, but this time we will call the input variable in[7:0].

      crc[7] crc[6] crc[5] crc[4] crc[3] crc[2] crc[1] crc[0] input
    initial value 0 0 0 0 0 0 0 0 in[7]
    step 1 crc[6] crc[5] crc[4] crc[3] crc[2] crc[1]
    ^ crc[7]
    crc[0] ^ crc[7] in[7] ^ crc[7] in[6]
    step 2 crc[5] crc[4] crc[3] crc[2] crc[1]
    ^ crc[7]
    crc[0] ^ crc[7] ^ crc[6] in[7] ^ crc[7] ^ crc[6] in[6] ^ crc[6] in[5]
    step 3 crc[4] crc[3] crc[2] crc[1]
    ^ crc[7]
    crc[0] ^ crc[7] ^ crc[6] in[7] ^ crc[7] ^ crc[6] ^ crc[5] in[6] ^ crc[6] ^ crc[5] in[5] ^ crc[5] in[4]
    step 4 crc[3] crc[2] crc[1]
    ^ crc[7]
    crc[0] ^ crc[7] ^ crc[6] in[7] ^ crc[7] ^ crc[6] ^ crc[5] in[6] ^ crc[6] ^ crc[5] ^ crc[4] in[5] ^ crc[5] ^ crc[4] in[4] ^ crc[4] in[3]
    step 5 crc[2] crc[1]
    ^ crc[7]
    crc[0] ^ crc[7] ^ crc[6] in[7] ^ crc[7] ^ crc[6] ^ crc[5] in[6] ^ crc[6] ^ crc[5] ^ crc[4] in[5] ^ crc[5] ^ crc[4] ^ crc[3] in[4] ^ crc[4] ^ crc[3] in[3] ^ crc[3] in[2]
    step 6 crc[1]
    ^ crc[7]
    crc[0] ^ crc[7] ^ crc[6] in[7] ^ crc[7] ^ crc[6] ^ crc[5] in[6] ^ crc[6] ^ crc[5] ^ crc[4] in[5] ^ crc[5] ^ crc[4] ^ crc[3] in[4] ^ crc[4] ^ crc[3] ^ crc[2] in[3] ^ crc[3] ^ crc[2] in[2] ^ crc[2] in[1]
    step 7 crc[0] ^ crc[7] ^ crc[6] in[7] ^ crc[7] ^ crc[6] ^ crc[5] in[6] ^ crc[6] ^ crc[5] ^ crc[4] in[5] ^ crc[5] ^ crc[4] ^ crc[3] in[4] ^ crc[4] ^ crc[3] ^ crc[2] in[3] ^ crc[3] ^ crc[2] ^ crc[1]
    ^ crc[7]
    in[2] ^ crc[2] ^ crc[1]
    ^ crc[7]
    in[1] ^ crc[1]
    ^ crc[7]
    in[0]
    step 8 in[7] ^ crc[7] ^ crc[6] ^ crc[5] in[6] ^ crc[6] ^ crc[5] ^ crc[4] in[5] ^ crc[5] ^ crc[4] ^ crc[3] in[4] ^ crc[4] ^ crc[3] ^ crc[2] in[3] ^ crc[3] ^ crc[2] ^ crc[1]
    ^ crc[7]
    in[2] ^ crc[2] ^ crc[1]
    ^ crc[7] ^ crc[0] ^ crc[7] ^ crc[6]
    in[1] ^ crc[1]
    ^ crc[7] ^ crc[0] ^ crc[7] ^ crc[6]
    in[0] ^ crc[0] ^ crc[7] ^ crc[6]  
    Removing any duplicate XOR-pairs to simplify in[7] ^ crc[7] ^ crc[6] ^ crc[5] in[6] ^ crc[6] ^ crc[5] ^ crc[4] in[5] ^ crc[5] ^ crc[4] ^ crc[3] in[4] ^ crc[4] ^ crc[3] ^ crc[2] in[3] ^ crc[3] ^ crc[2] ^ crc[1]
    ^ crc[7]
    in[2] ^ crc[2] ^ crc[1]
    ^ crc[7] ^ crc[0] ^ crc[7] ^ crc[6]
    in[1] ^ crc[1]
    ^ crc[7] ^ crc[0] ^ crc[7] ^ crc[6]
    in[0] ^ crc[0] ^ crc[7] ^ crc[6]  
    Final equations for each crc flip flop in[7] ^ crc[7] ^ crc[6] ^ crc[5] in[6] ^ crc[6] ^ crc[5] ^ crc[4] in[5] ^ crc[5] ^ crc[4] ^ crc[3] in[4] ^ crc[4] ^ crc[3] ^ crc[2] in[3] ^ crc[3] ^ crc[2] ^ crc[1]
    ^ crc[7]
    in[2] ^ crc[2] ^ crc[1]
    ^ crc[0] ^ crc[6]
    in[1] ^ crc[1]
    ^ crc[0] ^ crc[6]
    in[0] ^ crc[0] ^ crc[7] ^ crc[6]  

    The Verilog equations would look like the following:

       always_comb begin

             next_crc[0] = crc[0] ^ crc[6] ^ crc[7] ^ in[0];

             next_crc[1] = crc[0] ^ crc[1] ^ crc[6] ^ in[1];

             next_crc[2] = crc[0] ^ crc[1] ^ crc[2] ^ crc[6] ^ in[2];

             next_crc[3] = crc[1] ^ crc[2] ^ crc[3] ^ crc[7] ^ in[3];

             next_crc[4] = crc[2] ^ crc[3] ^ crc[4] ^ in[4];

             next_crc[5] = crc[3] ^ crc[4] ^ crc[5] ^ in[5];

             next_crc[6] = crc[4] ^ crc[5] ^ crc[6] ^ in[6];

             next_crc[7] = crc[5] ^ crc[6] ^ crc[7] ^ in[7];

       end

    To test that the equations are correct, we apply the input.  However, instead of applying the input serially, we apply it in parallel.  The input we drive in is 0x5700 or 0101_0111_0000_0000

    We first apply the first byte, 0101_0111 (0x57).  Note that the initial values of the crc[7:0] register is 0.

     

      crc[7] crc[6] crc[5] crc[4] crc[3] crc[2] crc[1] crc[0] input
      0 ^ 0 ^ 0 ^ 0 1 ^ 0 ^ 0 ^ 0 0 ^ 0 ^ 0 ^ 0 1 ^ 0 ^ 0 ^ 0 0 ^ 0 ^ 0 ^ 0 ^ 0 1 ^ 0 ^ 0 ^ 0 ^ 0 1 ^ 0 ^ 0 ^ 0 1 ^ 0 ^ 0 ^ 0 0x57
    contents of crc register after input of 0x57 applied 0 1 0 1 0 1 1 1  

    Next, we apply the second and final byte of trailing zeroes.

      crc[7] crc[6] crc[5] crc[4] crc[3] crc[2] crc[1] crc[0] input
      0 ^ 0 ^ 1 ^ 0 0 ^ 1 ^ 0 ^ 1 0 ^ 0 ^ 1 ^ 0 0 ^ 1 ^ 0 ^ 1 0 ^ 0 ^ 1 ^ 1 ^ 0 0 ^ 1 ^ 1 ^ 1 ^ 1 0 ^ 1 ^ 1 ^ 1 0 ^ 1 ^ 0 ^ 1 0x00
    contents of crc register after input of 0x00 applied 1 0 1 0 0 0 1 0  

    The contents of the CRC register is now 1010_0010 or 0xA2, the same value using the serial version of the circuit after we serially shifted in the last 8 bits of trailing zeroes.

    In cases where the input bus is larger than the CRC value, we can iterate through the shift register the same number of times as the input bus to create the parallel XOR equations for each crc register bit.  Using our previous example, the input bus was 8 bits wide.  If the input bus was 16 bits wide, the crc register bus still stays 8-bits wide but the equation changes.  I’ll leave it to you, the reader, to figure out how to get the result below.

       always_comb begin

             next_crc[0] = crc[0] ^ crc[4] ^ crc[6] ^ crc_in[0] ^ crc_in[14] ^ crc_in[15] ^ crc_in[8];

             next_crc[1] = crc[1] ^ crc[4] ^ crc[5] ^ crc[6] ^ crc[7] ^ crc_in[14] ^ crc_in[1] ^ crc_in[8] ^ crc_in[9];

             next_crc[2] = crc[0] ^ crc[2] ^ crc[4] ^ crc[5] ^ crc[7] ^ crc_in[10] ^ crc_in[14] ^ crc_in[2] ^ crc_in[8] ^ crc_in[9];

             next_crc[3] = crc[1] ^ crc[3] ^ crc[5] ^ crc[6] ^ crc_in[10] ^ crc_in[11] ^ crc_in[15] ^ crc_in[3] ^ crc_in[9];

             next_crc[4] = crc[0] ^ crc[2] ^ crc[4] ^ crc[6] ^ crc[7] ^ crc_in[10] ^ crc_in[11] ^ crc_in[12] ^ crc_in[4];

             next_crc[5] = crc[1] ^ crc[3] ^ crc[5] ^ crc[7] ^ crc_in[11] ^ crc_in[12] ^ crc_in[13] ^ crc_in[5];

             next_crc[6] = crc[2] ^ crc[4] ^ crc[6] ^ crc_in[12] ^ crc_in[13] ^ crc_in[14] ^ crc_in[6];

             next_crc[7] = crc[3] ^ crc[5] ^ crc[7] ^ crc_in[13] ^ crc_in[14] ^ crc_in[15] ^ crc_in[7];

       end

    Again, to test if the circuit is working properly, we apply an input of 0101_0111_0000_0000 (0x5700) in one step.  Again, the initial value of the flops are zeroes.

      crc[7] crc[6] crc[5] crc[4] crc[3] crc[2] crc[1] crc[0] input
      0 ^ 1 ^ 0 ^ 0 1 ^ 0 ^ 1 0 ^ 1 ^ 0 ^ 0 1 ^ 0 ^ 1 ^ 0 1 ^ 0 ^ 0 ^ 0 ^ 1 1 ^ 1 ^ 0 ^ 1 ^ 1 1 ^ 0 ^ 1 ^ 1 0 ^ 1 ^ 0 ^ 1 0x5700
    contents of crc register after input of 0x5700 applied 1 0 1 0 0 0 1 0

    1010_0010 or 0xA2 is the same answer as the previous examples.

    I’ve implemented CRC generators several times but I usually forget how to do it especially when I’ve been working on something else for a long period of time.  I’ve documented it here so I don’t forget and to also help my fellow logic designers.  Although this may not apply directly to the problem you are trying to solve, I hope you find the process of obtaining the crc logic helpful.

    Advertisements

    Titanfall Tips

    image

    Its been a long time since I’ve played First Person Shooters and I’ve been playing the production release of Titanfall since it came out on March 11, 2014.  The game is definitely fast-paced and the graphics are enjoyable to watch. 

    When I first started to play the game, I was averaging 0 kills most of the time especially when I played Attrition.  Talk about frustrating!  Now, I currently average between 2-4 kills per match.

    Most of the time, I play Hardpoint.  I find it more enjoyable since there is a goal I can work toward besides just killing the enemy.  I’m nowhere near being a good player yet, so I’m using NVidia’s ShadowPlay to help me improve my game.  ShadowPlay is used to record the game from beginning to end so that I can watch the replay afterwards. 

    Here are my notes after studying my replays.  I’ll continue to update this page as I play more. 

    Things to practice

      1. Jump and spin around to see who is shooting at you
      2. Use the “Q” key to camouflage as often as possible especially when entering into another room through the windows or doors.
      3. As soon as you see someone, shoot!  Don’t wait to recognize whether it’s a teammate or enemy.
      4. Reload while running.  I’ve gotten killed several times while I was standing still reloading.
      5. If you are a Pilot and a Titan sees you, just get out of there.  Don’t go head-to-head against a Titan if you are a Pilot.
      6. Don’t reload while in a firefight.  I got caught up in the heat of a battle that I run out of bullets and I’m reloading in the middle of a fight.
      7. Learn to keep moving while shooting the enemy

      Hardpoint tips

    1. Don’t reload at a Hardpoint.  Switch to Secondary weapon after using Primary weapon.  In this way, you won’t be caught off guard when the enemy pops into view
    2. Don’t be out in the open on the ground especially if there are enemy Titans nearby
    3. Although I hate campers, defending a Hardpoint could potentially increase your kill count
    4. Arcmines are great for defending a Hardpoint

    Microsoft needs to fix SkyDrive so that it works 100% of the time!

    I’m running the 64-bit version of Windows 8.1 Pro.  I noticed that there are times when SkyDrive in File Explorer won’t upload files even if SkyDrive Sync Engine Host is running.  I see this complaint everywhere on the internet.

    In my particular case, I had a PDF file that was 8,264 KB in size.  For some unknown reason, SkyDrive simply didn’t upload the file no matter how long I waited.  I ran skydrive.exe /reset many times and also ran their SkyDrive troubleshooter but to no avail.  I even ran the SkyDrive App and clicked on the Sync button.

    The only way I was able to get SkyDrive to upload the file was to go to my online account, select OneDrive and upload the file using the browser!

    For the most part, I enjoy Microsoft products but its times like these that make me really pissed off about using their products.

    My suggestion would be that they add a way to force uploading/downloading files in File Explorer.  Using the SkyDrive App just doesn’t cut it when I’m in desktop mode.

    Cisco AnyConnect Secure Mobility Client VPN slow using AT&T U-verse

    Problem:

    I was recently struggling with a slow or unusable VPN connection when using Windows 8.1, Cisco AnyConnect Secure Mobility Client VPN version 3.1.04066, and a Wireless connection to a 2Wire Gateway 3600HGV. 

    Without VPN, my speedtest.net results are:

    image

    With VPN, my speedtest.net results are:

    image

    Solution: 

    The solution that I found so far was to edit a field in a file called preferences.xml.  This file is found under

    /<Username>/AppData/Local/Cisco/Cisco AnyConnect Secure Mobility Client

    Originally, there was a line that showed this…

    <SDITokenType></SDITokenType>

    and my performance results were…

    I edited the file using Notepad to look like this instead…

    <SDITokenType>none</SDITokenType>

    Now, my performance results are…

    image

    Then I removed

    <AutoConnectOnStart>false</AutoConnectOnStart>
    <BlockUntrustedServers>true</BlockUntrustedServers>
    <LocalLanAccess>true</LocalLanAccess>

    Now, my perfomrnace results are…

    image

    When VPN doesn’t work, its frustrating to figure out what has gone wrong.  This solution worked for me so far.  I hope it works for you.

    Using the Desktop Toolbar as a pre-Windows 8 Start Menu

    When using Windows 8, I found that switching between the Desktop and the Start Screen was visually jarring.  After I updated Windows 8.1, I changed the Start Screen background to match my Desktop background.  Visually, the transition is much smoother.

    I do like the Start Screen and Live Tiles, but every now and then, I want to just stay in the Desktop.  Without using 3rd-party software, there is a way to have close to pre-Windows 8 Start Menu.  Here is how to do it.

    1. Right-click on the Toolbar followed by a left-click on Properties

    image

    A window will pop-up called Taskbar and Navigation properties.

    2. Left-click on the Toolbars tab, left-click on Desktop, and left-click on the OK button to add the Desktop to your Toolbar.

    image

    3. Adjust the position of the Desktop toolbar to the left right next to the Start button then shrink it down to allow more room for your Taskbar icons.

    4. (Optional) Lock the taskbar

    image

    The end result should look something like this..

    With taskbar unlocked

    image

    With taskbar locked

    image

    Use Task Scheduler to start then stop SkyDrive

    There are times when I don’t want SkyDrive to be running all the time for two reasons:

    1. I don’t want it to affect my boot up time
    2. I want to minimize network traffic
      But, I do want it to start at a certain time, let it do its work, then exit out.

    I found a way to do this by using a built-in Windows 8 program called Task Scheduler.  Here are the steps to do it.

    1. Type “Schedule Tasks” in the Windows 8 Start Screen

    image

    2. A window called Task Scheduler appears on the desktop.  Left-click on Create Basic Task

    image

    3. A window called Create Task appears.  Name the task you want to create.  In this example, I called it User_Created_Sync_SkyDrive.  Any tasks I create will always start with User_Created so that it is easier for me to distinguish the tasks that I created versus the tasks that Windows has created already.  Then, enter a short description of what the task does to remind you what the task is supposed to do.

    image

    4. Left-click on the Triggers tab, left-click on the New button…

    image

    … and fill in the following options – see the green boxes below.

    image

    5. Left-click on the Actions tab then left-click on the New…button

    image

    A window called New Action pops up.  Make sure the Action is Start a program.  Then, left-click the Browse…button.

    image

    Point to where the SkyDrive executable is located.  You should be able to find it under your user name/AppData/Local/Microsoft/SkyDrive.  Left-click on SkyDrive.exe to select the program you want to start and it should appear in the File name: textbox.  Afterwards, left-click on the Open button.

    image

    The result should look similar to this:

    image

    Left-click on the OK  button.

    Under the Conditions tab, ensure that you have the following settings, then left-click on the OK button.

    image

    Under the Settings tab, ensure that you have the following settings, then left-click on the OK button.

    image

    To see your newly scheduled task, left-click on Task Scheduler (Local)

    image

    then left-click on the Task Scheduler Library

    image

    Finally, left-click on File followed by a left-click on Exit to finish setting up the scheduled task.

    image

    That’s all there is to it.  Good luck.

    Fresh Paint + Surface Pro : It makes a lot of sense now

    I haven’t drawn in years.  The last time I drew anything was when I was in elementary school.

    When I first downloaded Fresh Paint it was unto my Desktop PC because it was one of the first few apps that seemed interesting.  But even then, I didn’t use it much.  The App was clearly built for touch and it was awkward to use on the desktop.

    I revisited the program but this time, I downloaded it on my Surface Pro and used it with a stylus.

    image

    Black headed seagull

    I’m going to keep practicing and learning techniques.  I have to tell you though, this is a lot of fun.  I’m really loving the technology.