Question

A bit stream 10011101 is transmitted using the standard CRC method described in the text. The generator polynomial is \(x^{3}+1\). Show the actual bit string transmitted. Suppose that the third bit from the left is inverted during transmission. Show that this error is detected at the receiver's end. Give an example of bit errors in the bit string transmitted that will not be detected by the receiver.

Short answer

The transmitted bit string is 10011101011. An error in a multiple of 1001 won't be detected.

Step-by-step solution

Append CRC Bits to Message

The original message is 10011101. Since the generator polynomial is \(x^3 + 1\), which has a degree of 3, we append three zeros to the message, giving 10011101000.

Perform CRC Division

We divide the extended message 10011101000 by the generator \(x^3 + 1\), which translates to the binary 1001. Perform binary division:1. Divide 1001 into the first four bits, 1001. Subtract to get 0000, then bring down the next bit to get 0011.2. 1001 cannot divide 0011, so bring down the next bit to get 0111.3. 1001 into 0111 is not possible, bring down another bit, getting 1110.4. 1001 goes into 1110 once, producing 0111 when subtracted.After completing the division with all bits are brought down, the remainder is 011. This is the CRC checksum.

Form Actual Bit String Transmitted

Attach the CRC checksum to the original message: 10011101 + 011 = 10011101011. This is the bit string that gets transmitted.

Simulate Transmission Error

The problem states that the third bit from the left is inverted. The transmitted bit string 10011101011 becomes 10111101011 after the error.

Verify Error Detection at Receiver

The receiver performs the CRC division on the received bit string 10111101011 using the same generator polynomial. Repeat the division process to find the remainder. If the remainder is not 000, then an error is detected. The remainder for this division is non-zero, confirming that the error is detected.

Identify Not Detected Error

An error that won't be detected is one that results in no remainder. For example, if two bits (including the most significant and least significant) are inverted, it can cause the remainder to be zero, making such errors undetectable. The simplest error not detected is when the transmitted bits are ones that are evenly divisible by the polynomial, such as a multiple of 1001.

Key concepts

Error Detection

Error detection is crucial in data communication. Its primary goal is to ensure that any data received is free of errors that may have occurred during transmission. One efficient method for error detection is the Cyclic Redundancy Check (CRC). It checks the integrity of data by using a predefined set of rules, which allows the receiver to verify if the data arrived accurately.

In CRC, a small number of redundant bits, called a checksum, is added to the data before transmission. When the data arrives, the recipient can perform the same calculation with the CRC to check for discrepancies. If the CRC remainder is zero, it suggests that the data arrived intact. Otherwise, an error is indicated.

Binary Division

Binary division plays a central role in the CRC process. This mathematical operation is applied between the divisor (a binary representation of a generator polynomial) and the data stream. Instead of performing division like in decimal operations, binary division mimics a long division strategy adapted to binary coding.

Here's how binary division works in CRC:

• Align the divisor under the initial section of the message consisting of the same number of bits as the divisor.
• Perform binary subtraction (XOR operation) on these bits, similar to how division subtracts multiples of the divisor in decimal.
• Bring down the next bit from the message and repeat until every bit has processed.

The remainder from this binary division is attached to the data stream to create a set of data complete with its CRC checksum.

Generator Polynomial

The generator polynomial is a crucial component of CRC error detection. It's essentially a polynomial equation used to calculate the CRC value. Each generator polynomial can be represented in binary form, translating to the divisor in the CRC binary division process.

For example, consider the generator polynomial \(x^3 + 1\). In binary, it is expressed as 1001. This binary format is used as the divisor in the CRC calculation. The choice of generator polynomial is significant:

• It determines how well errors can be detected.
• More bits in the polynomial typically yield better error detection.

CRC's robustness in identifying errors depends largely on the selected polynomial's properties.

Bit Stream Transmission

Bit stream transmission involves sending a series of bits over a network or between components. In digital communication, this method of transmitting data requires data to be sent in a continuous sequence of bits. The efficiency and reliability of data transmission can be impacted by errors such as bit flips, which may occur during the process.

To safeguard against errors and loss of data integrity during transmission, methods like CRC come into play. In our scenario, the original bit stream, appended with three CRC bits, was transmitted. Upon receiving the data, if any errors occurred, they can be detected by recalculating the CRC division at the destination. This ensures that the integrity of the data can be verified and the receiver can be informed promptly of any discrepancies.