Intereting Posts

Irreducible Polynomials: How many elements are in E?
Proof of Goldstine's theorem
For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles
Sufficient condition for a *-homomorphism between C*-algebras being isometric
Find the set of $n\in\Bbb Z^+$ with $M=\{n,n+1,n+2,n+3,n+4,n+5\}$ partitionable into two sets
Complex differentiabilty
Why does $\sqrt{n\sqrt{n\sqrt{n \ldots}}} = n$?
Operator norm of the inverse
Are $\sigma$-algebras that aren't countably generated always sub-algebras of countably generated $\sigma$-algebras?
The difference between $\Delta x$, $\delta x$ and $dx$
A problem from Evans' PDEs book: find a Lagrangian for a given Euler-Lagrange equation
Prove sum of $\cos(\pi/11)+\cos(3\pi/11)+…+\cos(9\pi/11)=1/2$ using Euler's formula
Decomposing the sphere as a product
Irreducibility of Polynomials in $k$
Hint on a limit that involves the Hurwitz Zeta function

Wikipedia says that CRC algorithm is **based** on cyclic codes, but it doesn’t say that it **is** a cyclic code. If I understood correctly, a linear code of length $n$ called cyclic if and only if its generator polynomial divides $x^n-1$. So I think that in general CRC codes are not cyclic. Is it true? And if yes, why do they called it “**Cyclic** Redundancy Check/Code” rather than, for example, “Polynomial Redundancy Code”?

- For what $(n,k)$ there exists a polynomial $p(x) \in F_2$ s.t. $\deg(p)=k$ and $p$ divides $x^n-1$?
- Generating a binary code with maximized Hamming distance
- Understanding Reed-Solomon as it applies to Shamir secret sharing
- Deducing correct answers from multiple choice exams
- How is this possible to convert a long string to a number with less characters?
- What is the trellis diagram for a linear block code?
- The sum of a polynomial over a boolean affine subcube
- Linear Code in Cryptography
- How to find all the coset leaders? (follow-up to a previous question)
- What is the difference between the sphere and projective space?

Minus typical bells and whistles such as first 16 bits are complemented etc., a CRC-encoded transmission

($k$ data bits followed by CRC bits) *can* be viewed as a codeword

in a *systematic cyclic code*. In a practical implementation, $k$ is

restricted to be a few thousand bits at most while the cyclic code

has *much larger* block length.

For example, with CRC-16, the code is a $[2^{15}-1,2^{15}-17]= [32767, 32751]$ single-error-correcting

double-error-detecting expurgated Hamming code whose generator polynomial (the CRC-16 polynomial) is of the form $(x+1)p(x)$ where $p(x)$ is

a primitive polynomial of degree $15$. So, if $1600$ data bits

are to be transmitted, the actual transmission is $1616$ bits, and this

transmission is a codeword in the $[32767, 32751]$ systematic cyclic code. *However*, the leading

$32751-1600 = 31151$ data bits in this codeword are $0$, and

they are ignored at the transmitter as well as the receiver, that is,

they are not transmitted at all. What *is*

transmitted is just the $1600+16 = 1616$ bits which are at the low-order

end of the codeword polynomial. At the receiver, the system knows

that the high-order bits, **however many they might be**, are all $0$

and can be ignored: it simply processes the $1616$ bits it has received

as a polynomial of degree $1615$, and checks whether or not the

received polynomial is a multiple of the CRC-16 polynomial or not.

The *next* transmission might have only $256$ data bits in it. No matter:

the receiver processes only $256+16 = 272$ bits. So, how can the receiver

tell if it is supposed to process $1616$ bits or $272$ bits? It *doesn’t*

need to know! The receiver simply processes the received bit

stream until an “end-of-transmission” (EOT) or “end-of-file” (EOF)

marker is reached. At that point,

if the “division by CRC-16 polynomial” process has produced a $0$

remainder, the *received* data bits (everything in the received stream

of bits except the last $16$ bits which are the CRC bits) are

accepted as correct; if not,

a re-transmission is requested. Note that *no* attempt is made to use

the error-correcting capability of the code; it is used for error

detection only.

**TL; DR version** Yes, CRC transmissions are codewords in a

systematic cyclic code but nobody bothers to think about the

transmissions in this way, or to exploit this notion in any way.

- Show that $\int\nolimits^{\infty}_{0} x^{-1} \sin x dx = \frac\pi2$
- To show that the limit of the sequence $\sum\limits_{k=1}^n \frac{n}{n^2+k^2}$ is $\frac{\pi}{4}$
- Polyhedral symmetry in the Riemann sphere
- Is there a more efficient method of trig mastery than rote memorization?
- Let $f$ be an analytic isomorphism on the unit disc $D$, find the area of $f(D)$
- Proving the volume of a cone
- Upper/lower bound on covariance two dependent random random variables.
- Real Analysis Proofs: Additive Functions
- Examples of metric vector spaces but not normed ? Normed but not prehilbertian?
- conformally equivalent flat tori
- Why is the tensor product constructed in this way?
- Non-Euclidean Geometrical Algebra for Real times Real?
- About Math notation: the set of the $n^{th}$ natural numbers
- Why is stable equivalence necessary in topological K-theory?
- Showing $1+2+\cdots+n=\frac{n(n+1)}{2}$ by induction (stuck on inductive step)