An error-detection method that treats the data bits as a polynomial, appends the remainder of dividing it by a generator polynomial, and lets the receiver repeat the calculation to detect errors. It is widely used in Ethernet, PCI Express, USB and file formats.
Japanese name: CRC(巡回冗長検査)
CRC (cyclic redundancy check) appears in 4 practice questions across 2 topics, including Logic circuits, I/O Interfaces & Buses.
Field: I/O Interfaces & Buses
A CRC treats the data bits as the coefficients of a polynomial in modulo-2 arithmetic and computes the remainder after dividing by a generator polynomial. In modulo-2 arithmetic both addition and subtraction are XOR, so the division is repeated "if the leading bit is 1, XOR the generator and shift by one". For a w-bit CRC, the w-bit remainder after appending w zeros is sent with the data, and the receiver repeats the calculation to check that it matches. Real standards add conventions such as an initial value, bit reflection of each byte and a final XOR.
A w-bit CRC detects every burst error of length w or less, and the chance of missing other random errors is roughly 2⁻ʷ. It only detects errors, however; it cannot correct them, so systems recover by retransmission. CRCs are used in the Ethernet FCS (CRC-32), PCI Express packets, USB, CAN, storage commands and file formats such as ZIP and PNG, and in hardware they can be computed with a linear feedback shift register of flip-flops and XOR gates.
Answer: B. When the two inputs are different
XOR outputs 1 when its two inputs differ and 0 when they match: A⊕B = A·¬B + ¬A·B. It can also be seen as "invert the other input if one input is 1, pass it unchanged if 0," making it a controlled inverter. It computes the sum in a half adder and is used in comparators (equality detection with XNOR), parity generation, stream ciphers and CRC calculation.
Answer: A. Generating pseudo-random patterns, such as test patterns, and computing CRCs
With properly chosen taps, an n-bit LFSR cycles through all 2ⁿ − 1 nonzero states, producing a seemingly random maximal-length sequence (m-sequence). Built only from XORs and flip-flops, it is used for built-in self-test (BIST) pattern generation and response compaction, CRC calculation in protocols such as Ethernet, and scramblers that randomize data to reduce electromagnetic noise. Its output is predictable, so it is unsuitable for cryptographic randomness.
A checksum uses a simple operation such as adding bytes and easily misses reordered data or errors that cancel out, whereas a CRC is based on polynomial division, distinguishes bit positions and reliably catches burst errors.
In general, no. A CRC detects whether an error occurred but not which bit is wrong, so memories that need correction use an ECC such as a Hamming code.
It computes the sum in a half adder and is used in comparators (equality detection with XNOR), parity generation, stream ciphers and CRC calculation.
When is the output of a two-input XOR (exclusive OR) gate 1?Built only from XORs and flip-flops, it is used for built-in self-test (BIST) pattern generation and response compaction, CRC calculation in protocols such as Ethernet, and scramblers that randomize data to reduce electromagnetic noise.
What is a typical use of a linear feedback shift register (…The data link layer sends each packet with a sequence number and a CRC (cyclic redundancy check) code.
What does the PCI Express data link layer do about bit erro…Besides data, a PCI Express packet carries a header with address and type, a data-link sequence number and CRC, physical-layer framing and so on, about 20 to 30 bytes in total.
In PCI Express, sending many packets that each write 64 byt…As an Amazon Associate I earn from qualifying purchases.
PCI Express Shift register BIST (built-in self-test) 128b/130b encoding 8b/10b encoding AXI Bit error rate (BER) Characteristic impedance Clock and data recovery (CDR) Compute Express Link (CXL)