Investigating error detection using CRC

This example examines how Cyclic Redundancy Check (CRC) detects errors when transmitting packets over a noisy binary channel. The Engee model transmits random packets, adds CRC verification bits to them, distorts them in a binary symmetric channel, checks the syndrome on reception, and counts correct, detected, and undetected erroneous packets. The model is assembled from Engee library blocks, including the General CRC Generator and General CRC Syndrome Detector. The script manages the model programmatically and compares the simulation results with an accurate theory calculated from the weight spectrum of the code. Experiments can also be set up in a web application based on the Genie Framework, which runs the same model. The example is useful for engineers and students studying noise-tolerant coding and statistical modeling of communication channels.

In any communication channel, some of the bits are distorted by interference. In order for the receiver to know about the error, the transmitter adds redundant verification bits to the data. CRC is one of the most common methods of such verification: it is used in Ethernet, USB, industrial network protocols, in file archives and in data storage.

CRC only detects errors, but does not correct them. The receiver discards the error packet or requests it again. Therefore, the main indicator of CRC quality is the probability that an error will go unnoticed.

In this example, we:

1. Let's briefly analyze the CRC theory and deduce the exact probabilities of three packet reception outcomes.
2. Let's study the model and test it on experiments with a pre-known answer.
3. Let's compare the simulation results with the theory in a wide range of error probability.
4. Let's launch a web application in which experiments can be performed without programming.

CRC Theory

The bits of the packet are considered as coefficients of a polynomial over the field GF(2), where addition is the exclusive OR. Information Bits form a polynomial degrees less . The generating polynomial degrees set by a list of degrees: [5, 3, 0] means .

The CRC encoder assigns the remainder of the division to the data:

Full package length , at the initial settings , , . Any code word divided into without a trace.

The receiver calculates the syndrome, which is the remainder of dividing the received word by . If the channel has added an error vector , the syndrome is equal to . The error is not detected only if it is itself a non-zero codeword.

A binary symmetric channel independently inverts each bit with probability . Each package falls into exactly one of the three classes:

where — the number of weight code words (the weight range of the code). By all the error vectors are equally likely, and the proportion of undetected errors is : from for vectors with zero syndrome, it is necessary to exclude the only case without errors. For and It's almost .

Description of the model

Model crc_error_detection.engee It is compiled only from Engee library blocks and works in a fixed step. . One step is one packet, so simulation time means the packet number, not the physical time.

The error handling node generates a packet event vector at each step.:

where — a sign of a non-zero syndrome, — a sign that at least one information bit has changed. The vector elements mean: a packet has been transmitted, an error has been detected, an error has been missed, the packet is correct, and the number of inverted bits. Adder Packet Statistics together with the delay unit Previous Totals accumulates an event vector of five counters.

Pay attention to the "package is correct" class: it requires that the information bits have not changed and the syndrome is zero. An error in only the verification bits gives a non—zero syndrome and is counted as detected - the receiver cannot distinguish it from an error in the data.

Block parameters are variables of the workspace crc_n, crc_k, crc_p, crc_seed, crc_packet_limit and crc_error_limit. They are set by the script code before each launch. The model can be reproducibly recreated using a script. resources/julia/build_model.jl.

Block Parameters

Let's connect the model management functions from resources/julia/crc_runtime.jl and the directory of polynomials, open the model and output the main parameters of the key blocks with the command engee.get_param. All paths are built from the script folder via @__DIR__.

The parameters are set by workspace variables. The step of the sources is equal to and by one bit, therefore, per model step, each source outputs a frame from or bit. The CRC parameters correspond to the classical scheme: zero initial state, without direct method, bit reflection and final XOR. The stop threshold for the second, fourth, and fifth counters is in other words, they do not affect the stop.

The Handbook of Polynomials

File polynomials.jl It contains a table of generating polynomials of cyclic Bose—Chowdhury—Hockingham codes (BCH). For each row, a list of degrees in the model format and the supported feature are calculated: whether the CRC Engee blocks support the polynomial. Let's print the table.

Column — the number of errors that the corresponding BCH code would correct. The model only detects errors, so provided as a reference. All length codes are available , and and five length codes . Six length codes with polynomials of degree from before CRC library blocks are not supported: their degree is greater .

Checking the model

File crc_runtime.jl It contains six functions:

• crc_validate checks the parameters of the experience: block length, probability, list of degrees of the polynomial, limits and seed;
• crc_poly_literal writes the vector of degrees of a polynomial as a literal for CRC blocks;
• crc_open_model loads the model if it is not open yet.;
• crc_signal finds the recorded block signal in the simulation results;
• crc_run_json accepts parameters as a JSON string, writes them to workspace variables and CRC block parameters, and runs the model with the command engee.run and returns the total counters as JSON;
• crc_reference_encode — independent CRC encoder: dividing polynomials "into columns" to check the General CRC Generator block.

The JSON format was chosen because the web application uses the same function. Let's launch a control experiment: , , a polynomial [5, 3, 0], packages.

Behind packages at correct accepted packages, erroneous packages were detected and skipped. This is the number of packets, not the bits: the channel has been inverted. bit from That is , under expected conditions . The percentage of correct packages coincides with the theoretical . The sum of the three classes is equal to the number of transmitted packets. This check is performed by @assert.

Now let's perform a set of control experiments. File verify_model.jl runs the model in six experiments with a pre-known answer and verifies that invalid parameters are rejected. Among the checks is a comparison of the output of the General CRC Generator block with an independent encoder crc_reference_encode on real packages of the model and checking that any single error gives a non-zero syndrome. The result is written in resources/data/verification.json.

All checks have been completed:

• everything is quiet The packages were accepted correctly;
• for the code inversion of all the bits turns a code word into another code word: a word of seven units is divided into . CRC does not see such an error, and the Stop Simulation block stops the model exactly after undetected errors;
• for the length the same inversion is always found;
• the same seed reproduces all counters;
• the output of the General CRC Generator block coincided with the independent encoder on all packages, that's all single errors give a non-zero syndrome. This means that the library unit calculates the CRC exactly according to the formula from the theoretical part.;
• the polynomial of the largest supported degree from the table, it works without errors, and the polynomial of degree rejected before the model is launched.

Comparison with theory

Calculate the exact weight range of the code with a polynomial . To do this, we will encode everything with a reference encoder. Let's find the information words and calculate the weights of the code words. Function theory Based on the spectrum, it calculates the probabilities of three classes of packages.

Minimum weight of a non-zero codeword Therefore, CRC is guaranteed to detect any single and double errors. There are many words of odd weight: a polynomial does not contain a multiplier therefore, unlike many standard CRCs, such as CRC-16, it does not detect all errors of odd multiplicity. Any error packet up to in length the bit is detected: such an error vector is not divisible by .

Let's run a model for the probabilities of bit inversion from before , by packages at each point, and compare the shares of the three classes of packages with the theory.

The proportions of correct and detected packets match the theory up to the second or third digit in the entire range. Undetected errors are a rare event, and with small the model has not registered any. To understand whether this is consistent with theory, we need to estimate the statistical error.

Let's build two panels: the proportion of correct and detected packages on a regular scale, then the proportion of undetected errors on a logarithmic scale. For each non-zero estimate, we will show a 95% Wilson confidence interval. For a share its boundaries

If the model has not registered the event, instead of the zero invisible on the logarithmic scale, we will show the upper 95% probability limit with a triangle. Such a triangle is not a measured fraction. A horizontal line Don't draw: value applies only to , rather than the entire range .

The model is consistent with the exact theory within the statistical margin of error. The upper panel shows the matching of the correct and detected packets. In the lower panel, the intervals around the non-zero estimates contain a theoretical curve, and the table confirms this for all eight points.

By , and the exact theory expects accordingly about , and an undetected packet from . The probability of getting zero events at compose . Therefore, zero counters do not contradict the theory: for such a lot more packages are needed.

By the model gave against theoretical ones (about expected events). The uncertainty interval includes the theoretical value. By the exact value , the model gave about .

Web application based on Genie Framework

Genie Framework — a set of packages for creating web applications:

• Genie.jl — a web server with query routing, HTML and JSON output;
• Stipple.jl — a reactive interface that binds script variables to page elements;
• GenieFramework.jl — a common package that connects everything at once and gives a macro @genietools.

Engee launches Genie applications in the cloud: team engee.genie.start(папка) lifts the server from the file app.jl in the specified folder and returns the page address. The application code is executed in a separate process. To execute the command in the main Engee session where the model is loaded, use the function engee.genie.eval(строка_кода).

The application of this example is in the folder resources/CRCApp:

1. index.html — a page with experience parameter fields: block size, error probability, polynomial, stop limits, and seed. The buttons launch the experience, clear the history, and upload the CSV. The history is stored in sessionStorage browser tabs.
2. The route / in app.jl gives this page as it is. The interface is written in pure JavaScript, so the Stipple reactive model is not needed here.
3. The route POST /api/run accepts parameters in JSON and checks each field with a function validate_request. Then he calls engee.genie.eval("crc_run_json(...)"): the model is launched in the main session, and the counters are returned to the page.
4. Blocking ReentrantLock it does not allow you to start the second experience while the first one is running.
5. User input is never executed as code: only the verified JSON string is passed to the main session as a string literal.

Each row of the table in the application is the result of a real model launch. crc_error_detection.engee, not an analytical calculation. Let's launch the app. File start.jl connects control functions, opens the model, and calls engee.genie.start.

The cell displays the address of the application in the form https://engee.com/prod/user/<имя_пользователя>/genie/CRCApp/. Open it in a browser. This is what the shape of the experience parameters looks like.:

After starting the model, the result appears in the table. The picture below shows the experience with the initial parameters.: packages at . The percentage of correct packages coincides with the theoretical . After launch, the model remains open for further experiments in the script and in the application.

The last cell returns a summary for the point .

Conclusion

We investigated error detection using CRC on the Engee model from library blocks and compared the simulation results with the exact theory. The code with a polynomial and the length of the package the bit is guaranteed to detect single and double errors, since its minimum weight is , as well as error packets up to in length bit. The proportions of correct, detected, and undetected packets coincided with the theory calculated from the weight spectrum of the code, over the entire range from before . By CRC skips about packets, and in a completely noisy channel — . The probability of missing an error is determined by the degree of the polynomial and its weight spectrum, therefore, higher degree polynomials are used in reliable systems.

This approach — a model, software checks, comparison with theory, and an interactive application — is useful for laboratory work and for the engineering evaluation of error-detecting systems.