Intereting Posts

$\omega$ – space of all sequences with Fréchet metric
Prove or disprove : Every bounded sequence converges.
Intuition for gradient descent with Nesterov momentum
General Steinitz exchange lemma
What is “multiplication by juxtaposition”?
limit as $x$ approaches infinity of $\frac{1}{x}$
General Cholesky-like decomposition
How show that $|a_{n}-1|\le c\lambda ^n,\lambda\in (0,1)$
Does the power spectral density vanish when the frequency is zero for a zero-mean process?
About fibers of an elliptic fibration.
Simplying linear recurrence sum with binomials
A function which is continuous in one variable and measurable in other is jointly measurable
A question about uniform convergent series
Covering space is a fiber bundle
Secretary problem – why is the optimal solution optimal?

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”?

- Understanding Reed-Solomon as it applies to Shamir secret sharing
- Huffman optimal code
- An easy reference for genetic algorithm
- Galois Field Fourier Transform
- The sum of a polynomial over a boolean affine subcube
- Minimum distance of the linear code $\{0,1\}$
- Construct generator matrix given generator polynomial?
- How to find all the coset leaders? (follow-up to a previous question)
- Minimum distance of a binary linear code
- What requirements should a CRC polynomial satisfy?

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.

- Basic constructions for graded algebras.
- Are there theoretical applications of trigonometry?
- What is the number of compositions of the integer n such that no part is unique?
- Differentiability of $f(x+y) = f(x)f(y)$
- Compute the limit $\sum_{n=1}^{\infty} \frac{n}{2^n}$
- Prove that $\log_a(b)=-\log_b(a)$
- Prove or disprove: if $x$ and $y$ are representable as the sum of three squares, then so is $xy$.
- Are the rings $k]$ and $k]$ Gorenstein? (Matsumura, Exercise 18.8)
- Is the Odd-4 graph a unit-distance graph without vertex overlap?
- How to show that $\sqrt{2}+\sqrt{3}$ is algebraic?
- A proof that $C$ is separable
- Cardinality of set containing true order relations from a power set
- Derivation of Gradshteyn and Ryzhik integral 3.876.1 (in question)
- When is the image of a linear operator closed?
- Multivariable Epsilon-Delta Proof?