Cyclic redundancy check

How do we know if a message is corrupted during transmission?

Imagine sending a secret letter through the mail. If the letter arrives with some pages missing or torn, you'd know something went wrong during delivery.

Think of a secret letter as a sequence of numbers. Before sending, we add extra numbers that help us check if any pages are missing or torn upon arrival. These extra numbers are calculated using a special method that looks at all the numbers in the sequence.

Example

Suppose the original message is 12345, and we add extra numbers (let's call them "check numbers") to get a new sequence: 12345 + 678 = 13073. When we check the message upon arrival, we use the same method to see if the check numbers match. If they don't, we know some pages are missing or torn.

Remember this

The extra numbers, called a cyclic redundancy check (CRC), help us detect if any pages (or bits of data) are missing or torn (corrupted) during transmission.

Text adapted from Wikipedia, licensed under CC BY-SA 4.0.

Related concepts

a parity check bit does: detects single-bit errors by making total 1s even/odd

Can you spot a single mistake in a secret code?

Error detection and correction

Reed-Solomon codes correct burst errors in data transmission and storage

Low-density parity-check code

LDPC codes revolutionized coding theory with significant performance improvements

Adam has bias correction: divides by (1-β^t) in early steps

Why do we sometimes need to fix mistakes in computer decisions?

ACID

ACID guarantees data validity in transactions

Overdrawn at the Memory Bank

Overdrawn at the Memory Bank was shot on videotape due to budget constraints

Swipe through 100 ML concepts daily

Open Pocket Polymath