# Find a message given a CRC and generating polynomial

This will give you the 31-bit input sequence that generated the CRC result. In summary, the conversation discusses a circuit that inputs a 31-bit binary string into a CCIT CRC-16 block to generate a 16-bit CRC output. The generating polynomial and method for determining the input sequence are also discussed. It is suggested to reverse the process in time to find the input sequence without knowing the quotient.
Gold Member
I am working on a circuit that inputs a 31-bit pseudo-random binary string into a CCIT CRC-16 block which generates a 16-bit CRC output.

I know that M(x)/G(x) = Q(x) + R(x) and the transmitted code will be R(x) appended to M(x).

When I simulated the circuit, I got a CRC of 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0. From the help file of the software (VisSim/Comm), I know that the generating polynomial is G(x) = 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1.

How do I determine the 31-bit input sequence that generated the CRC result?

Since M(x)/G(x) = Q(x) + R(x), we can say that M(x) = [Q(x) + R(x)]G(x). But we don't know Q(x). Assuming the 16-bit CRC is equal to R(x) and the G(x) is given, how do I go about finding M(x) without knowing Q(x)?

Because the generating polynomial is symmetrical = 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 you should be able to reverse the process in time without rewiring the generator.

First reverse the order of bits in your final CRC and load it into the generator. Then feed the data stream bits backward in time through the generator until you reach the original starting position.

## 1. What is a CRC?

A CRC (Cyclic Redundancy Check) is a type of error-detecting code used in digital communication and data storage. It is a mathematical algorithm that generates a unique checksum, or code, based on the data being transmitted. This checksum is then used to detect and correct any errors that may occur during transmission.

## 2. How does a CRC work?

A CRC works by dividing the data being transmitted into blocks and performing a series of mathematical operations on each block. This includes bitwise XOR operations and shifting of bits. The resulting checksum is then attached to the data and transmitted along with it. The receiver can use the same algorithm to calculate its own checksum and compare it to the one received. If they match, it is assumed that the data was transmitted without error.

## 3. What is a generating polynomial in relation to CRC?

A generating polynomial is a mathematical expression that defines the CRC algorithm to be used. It is also referred to as the CRC polynomial or CRC divisor. It is typically represented as a binary number and is used in the CRC calculation to generate the checksum. Different generating polynomials can be used to create different types of CRC codes with varying levels of error-detection capabilities.

## 4. How do I find a message given a CRC and generating polynomial?

To find a message given a CRC and generating polynomial, you will need to use a reverse CRC algorithm. This involves calculating all possible combinations of the message and appending the generating polynomial to each combination. The resulting checksum is then compared to the given CRC. If they match, it is assumed that the corresponding combination is the original message.

## 5. Can a CRC be used for error correction?

No, a CRC is not capable of correcting errors. It can only detect errors and signal for the data to be retransmitted. If the receiver detects errors, it will request for the data to be resent until a correct transmission is received. However, using a longer CRC code can increase the likelihood of detecting errors, making it more reliable for error detection purposes.

• Math Proof Training and Practice
Replies
10
Views
2K
• General Math
Replies
8
Views
2K
• Calculus
Replies
5
Views
895
• Differential Equations
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
13
Views
2K
• Calculus and Beyond Homework Help
Replies
24
Views
2K
• Differential Geometry
Replies
4
Views
2K
• Advanced Physics Homework Help
Replies
1
Views
986
• Electrical Engineering
Replies
3
Views
825
• Introductory Physics Homework Help
Replies
9
Views
342