Free The data link layer lessonsThe data link layer · Stage 0 · Detecting and fixing errors · Step 2

Cyclic redundancy check

Divide the frame by a generator polynomial, append the remainder, and see which errors slip through. About 14 minutes.

Quick check

A sender computes a CRC with a 5-bit generator. How many bits does the CRC remainder have?

Show the answer

4. The remainder of division by an (r+1)-bit generator has r bits: here 4.

Your problem

CRC

The sender appends len(generator) − 1 zeros to the data and divides using modulo 2 arithmetic (exclusive-or, no borrows), as in long division: for each position from the left, if the bit there is 1, exclusive-or the generator into the bits starting at that position. Return the remainder, the last len(generator) − 1 bits, as a string of that length.

Example

data = "1101011011", generator = "10011" → "1110"

1 ≤ length of data ≤ 24 · 2 ≤ length of generator ≤ 9 · the generator starts and ends with 1

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.