Why there is no CRC-3 on Wiki?

This question is just out of my curiosity when I was led to the Wiki page on CRC table:

https://en.wikipedia.org/wiki/Cyclic_redundancy_check

There is no CRC-3 in the table. I verified that the example polynomial x^3+x+1 is a primitive polynomial. So there should be a CRC-3. But the reason it is not shown is because there is no application?

Thanks.

Verictor <stehuang@gmail.com> wrote:

> This question is just out of my curiosity when I was led to the 
> Wiki page on CRC table:
 
> https://en.wikipedia.org/wiki/Cyclic_redundancy_check
 
> There is no CRC-3 in the table. I verified that the example 
> polynomial x^3+x+1 is a primitive polynomial. So there should 
> be a CRC-3. But the reason it is not shown is because there is 
> no application?

The list shows CRC polynomials used in known systems. For example,
ethernet uses one popularly called CRC-32.

There are an infinite number of possible primitive polynomials,
so not all are in the table.

Not only does there need to be an application, but someone has to
decide to use it for that application, and publish the description
of the application. For example, ethernet is published by IEEE.

It seems that there is a CRC-4, which might be usable in some cases
where a CRC-3 might be used.

-- glen

On Friday, October 25, 2013 10:22:47 PM UTC-5, Verictor wrote:
> This question is just out of my curiosity when I was led to the Wiki page on CRC table:
> 
> 
> 
> https://en.wikipedia.org/wiki/Cyclic_redundancy_check
> 
> 
> 
> There is no CRC-3 in the table. I verified that the example polynomial x^3+x+1 is a primitive polynomial. So there should be a CRC-3. But the reason it is not shown is because there is no application?
> 
> 
> 
> Thanks.

Short CRCs are usually taken to be of the form (x+1)p(x) where
p(x) is a primitive polynomial. See, for example, CRC polynomials
of degree 12 and 16 which have an even number of nonzero coefficients
and thus have 1 as a root => they are not primitive polynomials.
The CRC-32 polynomial is a primitive polynomial.

One thing that no one talks about is that CRCs must not be
used for **arbitrarily** long packets. In particular, the total
encoded data+CRC bits should not be more than 2^deg - 1 where
deg is the degree of the primitive polynomial part of the CRC.
For CRC-16, the limitation is thus 2^15 - 1 bits, which is far
longer than the typical packet size and thus the limitation is
rarely invoked, and is usually forgotten. For a proposed CRC-3
on the other hand, the limitation is just 7 bits! 4 data bits
followed by 3 CRC bits! Thus, there is a HUGE overhead cost in
using a CRC-3 system because the data rate is reduced by a factor
of 4/7.  Thus, while you **could** use a CRC-3 polynomial if you
absolutely wanted to (and even edit the Wikipedia entry to include
your CRC-3 in their list), your system will be so unreliable (if
you ignore the 7-bit limitation) and so noncompetitive with systems
using a more-thoughtfully-chosen CRC polynomial that the only
brownie points you will earn will be those that you award to
yourself for marching to the beat of a different drummer.

Dilip Sarwate

On 10/26/2013 9:36 AM, dvsarwate wrote:

> One thing that no one talks about is that CRCs must not be
> used for **arbitrarily** long packets. In particular, the total
> encoded data+CRC bits should not be more than 2^deg - 1 where
> deg is the degree of the primitive polynomial part of the CRC.
> For CRC-16, the limitation is thus 2^15 - 1 bits, which is far
> longer than the typical packet size and thus the limitation is
> rarely invoked, and is usually forgotten. For a proposed CRC-3
> on the other hand, the limitation is just 7 bits!

However, in systems design, quite often, you have to make best use of 
whatever bits are left. IIRC in GSM they use 3- or even 2-bit CRCs.
Even if max. length condition is not satisfied, cyclic code is usually 
the best solution for integrity check.

Vladimir Vassilevsky
DSP and Mixed Signal Designs
www.abvolt.com

On Saturday, October 26, 2013 7:36:17 AM UTC-7, dvsarwate wrote:
> On Friday, October 25, 2013 10:22:47 PM UTC-5, Verictor wrote:
> 
> > This question is just out of my curiosity when I was led to the Wiki page on CRC table:
> 
> > 
> 
> > 
> 
> > 
> 
> > https://en.wikipedia.org/wiki/Cyclic_redundancy_check
> 
> > 
> 
> > 
> 
> > 
> 
> > There is no CRC-3 in the table. I verified that the example polynomial x^3+x+1 is a primitive polynomial. So there should be a CRC-3. But the reason it is not shown is because there is no application?
> 
> > 
> 
> > 
> 
> > 
> 
> > Thanks.
> 
> 
> 
> Short CRCs are usually taken to be of the form (x+1)p(x) where
> 
> p(x) is a primitive polynomial. See, for example, CRC polynomials
> 
> of degree 12 and 16 which have an even number of nonzero coefficients
> 
> and thus have 1 as a root => they are not primitive polynomials.
> 
> The CRC-32 polynomial is a primitive polynomial.
> 
> 
> 
> One thing that no one talks about is that CRCs must not be
> 
> used for **arbitrarily** long packets. In particular, the total
> 
> encoded data+CRC bits should not be more than 2^deg - 1 where
> 
> deg is the degree of the primitive polynomial part of the CRC.
> 
> For CRC-16, the limitation is thus 2^15 - 1 bits, which is far
> 
> longer than the typical packet size and thus the limitation is
> 
> rarely invoked, and is usually forgotten. For a proposed CRC-3
> 
> on the other hand, the limitation is just 7 bits! 4 data bits
> 
> followed by 3 CRC bits! Thus, there is a HUGE overhead cost in
> 
> using a CRC-3 system because the data rate is reduced by a factor
> 
> of 4/7.  Thus, while you **could** use a CRC-3 polynomial if you
> 
> absolutely wanted to (and even edit the Wikipedia entry to include
> 
> your CRC-3 in their list), your system will be so unreliable (if
> 
> you ignore the 7-bit limitation) and so noncompetitive with systems
> 
> using a more-thoughtfully-chosen CRC polynomial that the only
> 
> brownie points you will earn will be those that you award to
> 
> yourself for marching to the beat of a different drummer.
> 
> 
> 
> Dilip Sarwate

That is very good point considering effective code rate. But just a reminder, x^3+x+1 is also simply the Hamming(4,7) code gen polynomial. Also, from Glen's point, CRC-1 is in use, which results in 50% code rate. Thanks for Vladimir's reminder that CRC-3 is used in the last 50-bit in GSM. So, I think the Wiki table needs to be updated.

On Sat, 26 Oct 2013 07:36:17 -0700, dvsarwate wrote:

> On Friday, October 25, 2013 10:22:47 PM UTC-5, Verictor wrote:
>> This question is just out of my curiosity when I was led to the Wiki
>> page on CRC table:
>> 
>> 
>> 
>> https://en.wikipedia.org/wiki/Cyclic_redundancy_check
>> 
>> 
>> 
>> There is no CRC-3 in the table. I verified that the example polynomial
>> x^3+x+1 is a primitive polynomial. So there should be a CRC-3. But the
>> reason it is not shown is because there is no application?
>> 
>> 
>> 
>> Thanks.
> 
> Short CRCs are usually taken to be of the form (x+1)p(x) where p(x) is a
> primitive polynomial. See, for example, CRC polynomials of degree 12 and
> 16 which have an even number of nonzero coefficients and thus have 1 as
> a root => they are not primitive polynomials.
> The CRC-32 polynomial is a primitive polynomial.
> 
> One thing that no one talks about is that CRCs must not be used for
> **arbitrarily** long packets. In particular, the total encoded data+CRC
> bits should not be more than 2^deg - 1 where deg is the degree of the
> primitive polynomial part of the CRC.
> For CRC-16, the limitation is thus 2^15 - 1 bits, which is far longer
> than the typical packet size and thus the limitation is rarely invoked,
> and is usually forgotten. For a proposed CRC-3 on the other hand, the
> limitation is just 7 bits! 4 data bits followed by 3 CRC bits! Thus,
> there is a HUGE overhead cost in using a CRC-3 system because the data
> rate is reduced by a factor of 4/7.  Thus, while you **could** use a
> CRC-3 polynomial if you absolutely wanted to (and even edit the
> Wikipedia entry to include your CRC-3 in their list), your system will
> be so unreliable (if you ignore the 7-bit limitation) and so
> noncompetitive with systems using a more-thoughtfully-chosen CRC
> polynomial that the only brownie points you will earn will be those that
> you award to yourself for marching to the beat of a different drummer.

I'm not sure what reasoning you're going by to say the packet length 
should be limited to such a large number.

A CRC is still going to detect a few bit errors in packets longer than 
your magic length, and it is still going to fail to detect just the right 
(wrong?) combination of enough bit errors in packets that are shorter.

The limitation that I'd put on CRC length is that the shorter the CRC, 
the higher the probability of an erroneous packet getting through, and 
the longer the CRC, the more it costs in overhead.  So you need to make 
your own tradeoff between the probability that a bad packet sneaks 
through vs. the overhead cost of the CRC.

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

On 10/26/2013 10:24 AM, Tim Wescott wrote:
> On Sat, 26 Oct 2013 07:36:17 -0700, dvsarwate wrote:
>
>> On Friday, October 25, 2013 10:22:47 PM UTC-5, Verictor wrote:
>>> This question is just out of my curiosity when I was led to the Wiki
>>> page on CRC table:
>>>
>>>
>>>
>>> https://en.wikipedia.org/wiki/Cyclic_redundancy_check
>>>
>>>
>>>
>>> There is no CRC-3 in the table. I verified that the example polynomial
>>> x^3+x+1 is a primitive polynomial. So there should be a CRC-3. But the
>>> reason it is not shown is because there is no application?
>>>
>>>
>>>
>>> Thanks.
>>
>> Short CRCs are usually taken to be of the form (x+1)p(x) where p(x) is a
>> primitive polynomial. See, for example, CRC polynomials of degree 12 and
>> 16 which have an even number of nonzero coefficients and thus have 1 as
>> a root => they are not primitive polynomials.
>> The CRC-32 polynomial is a primitive polynomial.
>>
>> One thing that no one talks about is that CRCs must not be used for
>> **arbitrarily** long packets. In particular, the total encoded data+CRC
>> bits should not be more than 2^deg - 1 where deg is the degree of the
>> primitive polynomial part of the CRC.
>> For CRC-16, the limitation is thus 2^15 - 1 bits, which is far longer
>> than the typical packet size and thus the limitation is rarely invoked,
>> and is usually forgotten. For a proposed CRC-3 on the other hand, the
>> limitation is just 7 bits! 4 data bits followed by 3 CRC bits! Thus,
>> there is a HUGE overhead cost in using a CRC-3 system because the data
>> rate is reduced by a factor of 4/7.  Thus, while you **could** use a
>> CRC-3 polynomial if you absolutely wanted to (and even edit the
>> Wikipedia entry to include your CRC-3 in their list), your system will
>> be so unreliable (if you ignore the 7-bit limitation) and so
>> noncompetitive with systems using a more-thoughtfully-chosen CRC
>> polynomial that the only brownie points you will earn will be those that
>> you award to yourself for marching to the beat of a different drummer.
>
> I'm not sure what reasoning you're going by to say the packet length
> should be limited to such a large number.
>
> A CRC is still going to detect a few bit errors in packets longer than
> your magic length, and it is still going to fail to detect just the right
> (wrong?) combination of enough bit errors in packets that are shorter.
>
> The limitation that I'd put on CRC length is that the shorter the CRC,
> the higher the probability of an erroneous packet getting through, and
> the longer the CRC, the more it costs in overhead.  So you need to make
> your own tradeoff between the probability that a bad packet sneaks
> through vs. the overhead cost of the CRC.

I've found the following reference interesting:

http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

There are a lot of suboptimal CRCs in common use.

Rob.

On Saturday, October 26, 2013 12:24:14 PM UTC-5, Tim Wescott wrote:

> 
> I'm not sure what reasoning you're going by to say the packet length 
> 
> should be limited to such a large number.
> 
> 
> 
> A CRC is still going to detect a few bit errors in packets longer than 
> 
> your magic length, and it is still going to fail to detect just the right 
> 
> (wrong?) combination of enough bit errors in packets that are shorter.
> 


With CRC-16, say, and a packet length less than 2^15 - 1,
the **smallest** number of bit errors that could possibly
give an undetected transmission error is 4 bits. Readers
please note carefully, I am not saying that **every**
possible 4-bit error pattern will cause an undetected
transmission error (packet is received with bit errors
but CRC says packet is OK), but that there are **some**
4-bit error patterns that will cause an undetected error.
This is in contrast to the fact that **all* 1, 2, and 3
bit error patterns will cause a CRC failure and thus are
detected.

If the packet length exceeds 2^15 - 1, then there are
2-bit error patterns that are **not** detected by CRC-16.
For example, x^{2^15-1} + 1 is divisible by the CRC-16
polynomial (as well as by the CRC-CCITT polynomial for
that matter), and x^{2^32-1} + 1 is divisible by CRC-32
should you really want to push your luck and have a
data payload of approximately 2^32 bits protected by a
measly 32 bits of CRC.

Dilip Sarwate

On Saturday, October 26, 2013 10:49:59 AM UTC-5, Verictor wrote:

>Also, from Glen's point, CRC-1 is in use, which results in 50% code rate.

CRC-1, also known as an overall parity bit, was in use even in
the very first computers, long before anyone had dreamt of
data transmission between computers and CRCs. It does not
result in a 50% code rate: the overall parity bit is usually
confined to use with one (8-bit) byte of data, except for those
who read Matthew 5:37 literally and insist on following each
data bit by one (even) parity bit. One translation gives this
verse as

"But let your communication be, Yea, yea; Nay, nay:
for whatsoever is more than these cometh of evil." 

On Saturday, October 26, 2013 11:28:14 AM UTC-7, dvsarwate wrote:
> On Saturday, October 26, 2013 10:49:59 AM UTC-5, Verictor wrote:
> 
> 
> 
> >Also, from Glen's point, CRC-1 is in use, which results in 50% code rate.
> 
> 
> 
> CRC-1, also known as an overall parity bit, was in use even in
> 
> the very first computers, long before anyone had dreamt of
> 
> data transmission between computers and CRCs. It does not
> 
> result in a 50% code rate: the overall parity bit is usually
> 
> confined to use with one (8-bit) byte of data, except for those
> 
> who read Matthew 5:37 literally and insist on following each
> 
> data bit by one (even) parity bit. One translation gives this
> 
> verse as
> 
> 
> 
> "But let your communication be, Yea, yea; Nay, nay:
> 
> for whatsoever is more than these cometh of evil."

Yes, CRC-1 is usually referred to the parity bit, for 7-bit data plus 1-bit parity as you describe and the Wiki page says. I was just applying the packet length you pointed out to CRC-1's p(x)=x+1. Of course, it is not used in this way in practice.