Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am asked, in homework assignment, to calculate the CRC of the message and pattern that are given.

Question states:

For P = 110011 and M = 11100011, find the Cyclic Redundancy Check (CRC).

My problem here is that I must find the frame check sequence (FCS) and I'm not sure how to calculate it.

Is I believe I need FCR to add it to the original message before I start the division by XOR method.

So I know:

Message M = 11100011 (8 bits) 
Pattern P = 110011 (6 bits) 
FCS R = To Be Calculated (5 bits)

How to calculate FCS?

PS. I might get a little confused here. In the book I am being explained to first find the M, P, and state that FCS R to be calculated. Then I am being asked to find N, K, and N-K which I have done but I dont understand where the numbers coming from so I improvised and got:

n = 13
k = 8
n – k = 5

Then I am asked to "the message is multiplied by 2^5" so my message should be: 1110001100000 (????)

And here I am stuck on first 3 steps.

This is what my book have about this topic which kind of confuses me.

enter image description here enter image description here

share|improve this question
1  
I am adding a IMHO more fitting tag of coding-theory to your question. Dilip Sarwate's answer to this question gives you something to chew. –  Jyrki Lahtonen Feb 24 '12 at 20:40
    
@Jyrki Lahtonen. Thanks, this give an example of how to do the calculation but it doesn't tell me how many and what bits I should add to my original message. I guess the problem is that I must add something to my original message and I'm not sure exactly what. –  HelpNeeder Feb 24 '12 at 20:54
    
Well, I think I just must add 5 (0) bits to the message and do the long division. I hope I'm right. –  HelpNeeder Feb 24 '12 at 20:57

1 Answer 1

up vote 2 down vote accepted

Let us use $x$ as an unknown. When dealing with CRCs a common choice is to use $D$ (as in DELAY) as the unknown, but your textbook (IMHO unwisely) has denoted the message by $D$ in that example, so let's use $x$ here.

We turn your message into a polynomial (with bits as coefficients) simply by using the bits as coefficients, so your $M=11100011$ becomes $$ M(x)=1\cdot x^7+1\cdot x^6+1\cdot x^5+0\cdot x^4+0\cdot x^3+0\cdot x^2+1\cdot x+1=x^7+x^6+x^5+x+1. $$ The CRC-polynomial $P=110011$ similarly becomes $$ P(x)=x^5+x^4+x+1. $$ Notice how the exponents of $x$ simply act as place holders in the sense that the bit in position $i$ is simply the coefficient of the power $x^i$.

The degree of our CRC-polynomial is five, so we shall add five redundant bits to the message $M(x)$. These redundant (or check) bits are also a polynomial $$ R(x)=r_4x^4+r_3x^3+r_2x^2+r_1x+r_0, $$ but we don't know those bits $r_i,i=0,1,2,3,4,$ yet the task is to calculate them! One of the questions that you asked was: how do we know that there will exactly five check bits? The reason is that when we divide other polynomials by $P(x)$ the remainder of (long) division will have degree that is less than the degree of $P(x)$. So in this case it will have degree at most four (just like the polynomial $R(x)$ above), and polynomials of degree at most four are specified by five coefficients (like $r_i,i=0,1,2,3,4$). In other words, you always have $n-k=$ the length of $P$ minus $1$, here $n-k=6-1$. Given that the message is $k=8$ bits long, you get $n=k+(n-k)=8+(6-1)=13$ bits.

The idea in CRC-calculation is to first make room for those $n-k=5$ bits at the LSB-end of $M(x)$ by multiplying it with $x^5$. Then the rule for selecting the polynomial $R(x)$ is that the polynomial $$ M(x) x^{n-k}+R(x)=M(x)x^5+R(x) $$ must be divisible by the CRC-polynomial $P(x)$. So the polynomial $R(x)$ must be the negative of the remainder, when $M(x)x^5$ is divided by $P(x)$. Because modulo 2 we have that $-0=0$ and $-1=1$ we can forget about that 'negative'. Let's calculate! The product $R_0:=M(x)x^5=x^{12}+x^{11}+x^{10}+x^6+x^5$ is of degree twelve. In other words it has a total of $n=13$ coefficients. To compute the remainder of polynomial division we keep subtracting multiples of $P(x)$ from this polynomial as long as we can. Because $P(x)$ is of degree five, and the highest degree term of $R_0$ is $x^{12}$ we subtract from it (or add to it as it makes no difference!) the polynomial $x^7P(x)$. Here $7=12-5$ is chosen to make the highest degree terms both be of degree twelve. So we compute the first remainder $$ R_1:=R_0+x^7P(x)=(x^{12}+x^{11}+x^{10}+x^6+x^5)+x^7(x^5+x^4+x+1)=x^{10}+x^8+x^7+x^6+x^5. $$ Notice that we were a bit lucky in the sense that in addition to the degree twelve terms, also the degree eleven terms cancelled. This remainder is of degree ten, which is still too high. The polynomial $x^5P(x)$ is also of degree ten, so let's add that next: $$ R_2:=R_1+x^5P(x)=(x^{10}+x^8+x^7+x^6+x^5)+x^5(x^5+x^4+x+1)=x^9+x^8+x^7. $$ This is of degree $9>4$, so we continue $$ R_3:=R_2+x^4P(x)=(x^9+x^8+x^7)+x^4(x^5+x^4+x+1)=x^7+x^5+x^4. $$ Still too high degree... $$ R_4:=R_3+x^2P(x)=(x^7+x^5+x^4)+x^2(x^5+x^4+x+1)=x^6+x^5+x^4+x^3+x^2. $$ ...not there yet... $$ R_5:=R_4+x P(x)=(x^6+x^5+x^4+x^3+x^2)+x(x^5+x^4+x+1)=x^4+x^3+x. $$ Tadaa! This remainder is finally of degree less than that of $P(x)$, so we must stop. So we are done, and may set $R(x):=R_5 =x^4+x^3+x.$

As the finishig touch we first compute the sum $$ M(x)x^5+R(x)=x^{12}+x^{11}+x^{10}+x^6+x^5+x^4+x^3+x, $$ and then extract the coefficients of the terms $x^{12},x^{11},\ldots,x^2,x,x^0=1$ (in that order) to form get the final string of 13 bits $$ 11100011|11010. $$ Here the original message is the first 8 bits, and the CRC-check (or whatever you call it in your application) is the last five bits, i.e. $11010$.

share|improve this answer
    
So I ended up walking you through this one. Your textbook doesn't use polynomials for the algebra, but I can't do without! I disprove of the practice of not presenting it this way, but YMMV. –  Jyrki Lahtonen Feb 24 '12 at 21:29
    
This looks perfect by doing this by using the equation. I did the long division way and I got the same CRC as you pointed out. As of right now I have just scanned your message and now I will read it. Thanks a lot! –  HelpNeeder Feb 24 '12 at 21:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.