Hi there 👋 in this article I will represent the problem related to error detection codes, focusing specifically on Cyclic Redundancy Check (CRC). In summary, for each data block of k bits, a transmitter generates an error-checking sequence (Frame Check Sequence, FCS) to create a total sequence divisible by a predetermined number. The receiver verifies the correctness of the received frame by performing a division, accepting frames with no remainder and requesting retransmission for corrupted ones.
This article details the implementation process, including the creation of data sequences, addition of error control sequences, and calculation of CRC for each message. It also describes the methods for introducing noise into the data, generating messages with noise, and calculating the error rate in received messages. The effectiveness of CRC is evaluated through methods for calculating the percentage of detected and undetected messages.
An example of program execution is provided, highlighting the reliability of CRC in recognizing altered messages under specific conditions, such as a Bit Error Rate (BER) of 1000. The text concludes by noting the program's results when reducing the BER to 100, emphasizing the impact on message corruption and CRC detection efficiency.
Representation of the problem
For each data block D of k bits, the transmitter generates an error-checking sequence F of n-k bits (Frame Check Sequence, FCS),
such that the total sequence T of n bits obtained is divisible exactly by a predetermined number P of n-k+1 bits.
When the sequence T of n bits reaches the receiver,
its correctness is verified by dividing it by the predetermined number.
If there is no remainder from this division, then the frame is accepted.
If a remainder occurs, it is assumed that the frame has been corrupted, and retransmission is requested.
It is worth noting that for the calculation of FCS, as well as for verifying the correctness of the received frame, modulo-2 arithmetic is used.
This means binary arithmetic without carries.
Reasons for using modulo-2 arithmetic:
The simplicity characterizing this arithmetic and the resulting ease of implementation.
Modulo-2 division leaves a remainder 1 bit smaller than regular division, leading to a slight reduction in the transmitted control bits that burden the communication system.
CALCULATION OF FCS AT THE TRANSMITTER
VERIFICATION AT THE RECEIVER
Implementation
Creation of k-bit data sequences for transmission (D)
To generate randomly selected binary messages of k bits for the transmitter (a block of k bits, where each bit has an equal probability of being 0 or 1), the method GenerateRandomMessage was implemented. This method takes the variable k as an argument, representing the number of bits in the binary message.
Random Message Collection Method
We gather all the messages generated by the GenerateRandomMessage method for further processing.
Error Control Sequence Addition Method F in Each Message
For each data block D of k bits, the transmitter generates an error control sequence F of n-k bits (Frame Check Sequence, FCS) in such a way that the total sequence T of n bits obtained is divisible exactly by a predetermined number P of n-k+1 bits.
To compute the error control sequence F, the following algorithm is used:
Place n-k zeros to the right of D so that the resulting 2n-k D
Calculation of CRC (FCS) for Each Message
For every message to be transmitted, after appending the F to each message, we need to compute the FCS resulting from the XOR operation between 𝑇 = 2𝑛−𝑘𝐷 + 𝐹 and P. Subsequently, these FCS values are stored in a list.
Method for Binary Division
The Divide method implements division using XOR logical operations. The method returns the remainder in binary string format, which serves as the Frame Check Sequence (FCS) for a specific message and polynomial P.
Method for Creating a Sequence from (Number of Messages * k) Bits
For the random insertion of erroneous bits, as we will see later, we will need to concatenate all the messages to be sent into one. For example, for a number of messages = 5000, where each message consists of k = 20 bits, we will end up with a sequence of 5000 * 20 = 100,000 bits.
Noise Injection in Data
Using the following methods, we simulate the random injection of noise into the data. Essentially, we alter the value of one bit every n bits according to the Bit Error Rate (BER). For instance, with a BER of 10^-3, it implies that we have one erroneous bit per 1000 bits.
Method for Generating Messages with Noise
Once the noise has been introduced into the messages as described above, we need to separate the data sequence into messages of 20 bits each.
Calculation of the error rate in received messages
By comparing the original messages (before the introduction of noise) with the messages after noise introduction, a check is performed on the messages that differ to determine the percentage of messages that were altered due to noise.
Error Message Separation
Only messages that have been altered due to noise are stored in the list.
Method for Calculating CRC-Detected Messages
The method "percentageOfDetected" takes as input the messages after the introduction of noise, the list of Frame Check Sequences (FCS), the polynomial (P), and the number of altered messages. Subsequently, it performs a check on the receiver based on the FCS list and divides the number of detected altered messages by the actual number of erroneous messages (count). The result is then returned as the efficiency percentage of the CRC.
Method for calculating the percentage of messages not detected by the CRC
The method `percentageOfUndetected` takes as input the messages (pre-noise injection), the messages (post-noise injection), the list of FCS, and P. It compares the two message lists and, upon detecting a corrupted message, performs a check with the corresponding FCS. If the remainder returns an acceptance value, it increments a counter to ultimately calculate the percentage of messages that, although corrupted, were not detected by the CRC.
An example of program execution
The following parameters were used for the execution conditions of the program:
Each data transmission sequence consists of 20 bits
The number of binary '0' bits (F) added to each sequence is n-k = 5 bits.
P is the predetermined number of n-k+1 bits by which the sequence T should be divisible, and it is '11010'.
The Bit Error Rate (BER) is 1000, meaning one erroneous bit per 1000 bits in a sequence.
The number of messages sent to the receiver is 100,000.
As indicated by the program's results, the percentage of messages altered due to noise introduction in the channel is 2%. In other words, out of the total 100,000 messages, 2000 were distorted.
CRC (Cyclic Redundancy Check) is highly reliable as it can recognize altered messages and potentially request their retransmission from the transmitter.
If, however, we reduce the Bit Error Rate (BER) to 100, we observe that 18,000 messages were corrupted, and the CRC was unable to identify 80 of them, even though they were altered due to the noise in the transmission channel.
"For percentage calculations, rounding to 2 decimal places was applied."
Until the next one, cheers! 🍺
Comments