INTELLIGENT WORK FORUMS FOR ENGINEERING PROFESSIONALS
Come Join Us!
Are you an Engineering professional? Join EngTips now!
 Talk With Other Members
 Be Notified Of Responses
To Your Posts
 Keyword Search
 OneClick Access To Your
Favorite Forums
 Automated Signatures
On Your Posts
 Best Of All, It's Free!
*EngTips's functionality depends on members receiving email. By joining you are opting in to receive email.
Posting Guidelines
Promoting, selling, recruiting, coursework and thesis posting is forbidden.

probability of an undetected error in crccode word(2)

gerczek (Mechanical) (OP) 
22 Jan 10 7:39 
I am trying to calculate the probability of an undetected error in a dataframe that is sent through an embedded wireless network (ieee 802.15.4). The length of the dataframe is 1000 bits plus 16 bits FCS(Frame Check Sequence), generated by the CRCCCITT x^16+x^15+x^5+1 polynomial. I know from a researchpaper that the CRCCCITT can detect any 1,2 and 3 biterrors and any uneven biterrors. So only the 4,6,8,.... biterrors might lead into an undetected error. To calculate the propability of an undetected error for a dataframe, i would have to calculate the probability that a 4,6,8,.. biterror even occurs (given the biterrorrate), multiply it by the probability that these specific bit errors actually lead into an undetected error and sum it all up. for example for 4 biterrors there exist 1016^4 (simplified) different possible combinations, but only a few of these lead into an undetected error. (Am I right so far?).
The problem now is, that I don't know how many 4,6,8,.. biterrors lead into undetected errors and thus I can't calculate exactly the possibility of an undetected error. So I made an assumption. In the frame there 2^1000 correct Codewords, that share 2^16 FCS. That means on average 2^1000/2^16 share 1 FCS, but for a specific frame only one is correct and the others are in incorrect, but are not detectable as such. The total amount of possible incorrect frames is of cours 2^1016 1. The average possibility of an undetected error is the amount of undetectable error devided by the total amount of errors. (2^984 1)/(2^1016 1). Finally I multiplied that by the probability that errorcorruption can even occur as mentioned above and had my results.
I hope I expressed myself coherently. If you have any questions feel free to ask. What I would like to know is. Does my assumption make sense? And is calculated probality higher than the actual probability, so that I am still on the safe side. Do you know where I can get the actual amount of undetectable errors for each biterror for my specific datalength CRCpolinomial? thanks a lot for your time 

Quote (gerzcek):And is calculated probality higher than the actual probability
Wouldn't that mean you calculated incorrectly? Dan  Owner http://www.HiTecDesigns.com


gerczek (Mechanical) (OP) 
22 Jan 10 11:40 
Yes my calculation is not 100% correct. The assumption is actually a simplification because I don't know the exact properties of the codewords that are generated by the CRC. 

gerczek (Mechanical) (OP) 
22 Jan 10 13:07 
I am sending information (dataframes) from one point to another over a wireless channel. In that channel the frames might get corrupted. Normally the receiver can detect these errors with the help of the Frame Check Sequence. But there is a slight chance that these errors cannot be detected. I want to know how big that chance is, so I can say how reliable the data is. The probability I calculated for the worst case, was around 1^7 . If I am off 50% that, would mean 5^7 or 5^8. I could still live with that as long as I am not near the thresholdprobability of 1^6. 

(2) Noway2 (Electrical) 
22 Jan 10 16:41 
There are problems in trying to compute an error rate for which the CRC will fail to detect a bad communication. First, whether or not the error gets through will be highly dependent on the message. Second, CRC was designedto catch short bursts of contiguous bit errors. If the number of error bits is greater than this, there is a chance that CRC will fail.
Here is an example: Consider these two hex strings: 1) 4B04B6F9BF002F002C002E002CD12E 2) 00260010BF002F002C002E002CD12E
This is from an actual application and uses a 16 bit CRC algorithm to calculate a check value. In both cases the check value is 0x2ED1 (byte swapped). The CRC is the standard CRC used in Modbus, CCITT believe.
Mathematically speaking, an X bit CRC will detect all consecutive bit errors less than X bits. When the error burst is bigger than X, the an X bit CRC will detect at a rate of 12^X . For example,a 16 bit CRC has a 99.99847412109375% chance of catching the error burst.
As you can see from my example above with the two strings, in reality, error bursts longer than X bits DO HAPPEN AND DO GET THROUGH! 

sreid (Electrical) 
23 Jan 10 7:23 
A Star for Noway2.
1) One must be careful in calculating probabilities that all events have an equal probability of occuring [unless you account for that].
2) There's probably [certainly] published data on the BER for the CRC you are using. 

gerczek (Mechanical) (OP) 
24 Jan 10 12:09 
I know that errors can get through. In literature they are called undetectable errors, which is the whole point of my opening post. I want to calculate the probability of an undectable error, depending on the attributes of the CRCCode and on the biterrorrate of the channel. There are quite a lot of CRCCodes out there with different attributes. For example CRCCode A can detect more 4Bit errors then CRCCode B. But B can detect all uneven Bit errors. Thus I am pretty sure, it's not possible to say there is 12^x chance to detect all errorburst bigger than X (size of the FCS), because not all CRCCodes are different. It's just a simplification and my original question was how good that simplification is. http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf I found this paper on the net. It was very helpful in understanding CRCCodes. I hope this post makes my first post more understandable. 

Noway2 (Electrical) 
24 Jan 10 15:17 
I don't think that there is a "practical" answer to your question. By "practical" I mean ones that makes sense and is usable by a real world engineer and this thread is heading dangerously towards the academic.
While I think I understand what you are asking, I don't see how to develop a reasonable answer that doesn't depend on seriously advanced concepts of probability theory regarding stochastic processes. There are simply too many variables, not the least of which is the science behind the different CRC algorithms. It is well known that the polynomial choice has a dramatic impact, I don't have a clue as to how to pick a particular one and try to quantitatively predict the results given a theoretical communication channel SNR or error rate.
Perhaps an investigation into how to analyze random events based upon probability would lead you to a better solution. This type of analysis is commonly used in DSP algorithms where noise is concerned and the nature of the noise is non deterministic. 

Assemble a Beowulf cluster from all those old computers you have, and let them beat on a simulation of the problem for a few weeks. Mike Halloran Pembroke Pines, FL, USA 

Noway, a star for you, good sir. I couldn't have said it better myself had I tried (which I failed to do with anything more than "Why?"). Dan  Owner http://www.HiTecDesigns.com




