### How does CRC work?

###### Chapter 3 Logical Functions

###### Chapter 3.1 Introduction

I have already mentioned that **CRC** is treated as a kind of “**remainder**” of division. The “**division**” is the message being sent, the “**divisor**” is a certain **constant** known to the **Transmitter** and the **Receiver,** and the “**rest**” is the **CRC**. Wait, what’s most important, the result of division – “**quotient**“? This doesn’t interest us at all! Stop-more on this topic in **Chapter. 4 CRC** arithmetic. For now, I will only say that instead of **division** we will use something that is only similar to** division**. In fact, for “**dividend**” and “**divisor**” there is also a “**remainder**” which requires fewer bytes than “**dividend**“. And the most important. Instead of successive **subtractions**, we perform a very simple logical operation, **xor**-ing. In addition, there is no “nothing in memory” as in written **decimal division**. These operations are so simple and **fast** that they are **ideal** for calculating **CRC**. They are performed while sending the next **bit** and do not **slow down** the transmission. That’s why you need to be very good at** xoring** in later chapters.

But first you will learn the **basic logic** functions:**– NEGATION**, i.e. denial**– AND**, i.e. logical product**– OR**, i.e. logical sum

and of course**– XOR** means either

**Chapter 3.2 Logical NEGATION function, also known as Denial**

Fig. 3-1**Negator** function in our way **“NO”** **ANIMATION**

The output **y** is the negation of the input** x**, which we write as in the figure (y=x with a **“caret”**). Enter the **animation** and write the **truth** tablet.

If you don’t know what I mean, take a look at **Fig. 3-5a** in **Chapter 3.6**

**Chapter 3.3 Logical OR Function, also known as Logical Sum**

**Fig. 3-2****OR** function in our own words **“OR”** **ANIMATION**

The function can be written as** y=x1** **or x2** or as a simple sum **y=x1+x2****y=1** only if **x1=1** or** x2=1**

Enter the animation, check the above sentence and write the truth tablet.

**Ch. 3.4 Logical AND Function, also known as Logical Product**

Fig. 3-3

Fig. 3-3

**AND**function in our own words

**“AND”**

**ANIMATION**

**The**function can be written as

**y=x1 and x2**or as a simple product

**y=x1*x2**

**Y=1**only if

**x1=1**and

**x2=1**simultaneously

**Enter**the animation, check the above sentence and write the

**truth**tablet.

**Chapter 3.5 XOR Logic Function**

Fig. 3-4**XOR** function in our own words “EITHER” **ANIMATION****Y=1** only if** x1=1** or **x2=1**

Enter the **animation**, check the above sentence and write the **truth** tablet.

By the way. Some people do not distinguish the conjunction “OR” from “EITHER”.

Our law allows marriage “to Jola **either** to Mariola” but not “to Jola **or** to Mariola”. The latter would allow **bigamy**!

**Chapter 3.6 Logical Functions in the form of truth tables (Karnaugh tables)**

Fig. 3-5

Truth tables

It is very convenient to present a given **logical function** in the form of the so-called **truth tables**. Especially when we are examining a **device** and we do not yet know its **logical function**. **Fig. 3-5a…3-5d** are the results of testing the **logic** circuits from **Chap. 3.2…3.5**. Each cell of the **truth table** corresponds to one tested input **combination**. For example, in **Fig. 3-5b** regarding the **OR** function, **circled 1** means that for the combination of inputs **x1=1** and **x2=0**, output **y=1**. This function has **2** inputs **x**1 and **x2** for which there are **4** different combinations of inputs **x1** and **x2**. Therefore, its **truth** table is a **2×2** square. This note applies to** all** tested systems with **2** inputs. The **OR** symbol can be replaced with **“+”**, and the **AND** symbol with the** multiplication** symbol **“*”**. They are probably even more popular.**Fig. 3-5a**

Negator

For input **x=0** output **y=1** and for input **x=1** output **y=0**. This is the result of testing the negator in **Figure 3-1**.**Fig. 3-5b**

OR**Fig. 3-5c**

AND**Fig. 3-5d**

i.e. the **XOR** function well illustrates the fact that each **1** is a separate logical product of **x1** and **x2**. Here, some **x1*x2** in the product are “covered”, i.e. **negated**.

Now a question may arise. While this is obvious for the **AND** and **XOR** functions, the **OR** function should consist of **3** appropriately overlapped products! And here it is just simple **y=x1+x2**! It turns out that any** logical** function given in the form of a **table** can be simplified! In the **1950s**, a man named **Karnaugh** showed how to do this in one limited case. Namely, for functions with a maximum of** 5** inputs **x1, x2, x3, x4, x5**, he used the so-called **gluing**. And this is nothing more than a logical **law** that we use every day. I will say no more about its details than the following.

You can say “Tomorrow the **sun** will shine **and** it will **rain**, **or** tomorrow the sun will **shine and** it **won’t rain**.” I hope you see the sum of **2** logical products here! The same thing can be said much more simply, “The sun will **shine** tomorrow.” It’s absolutely the same content! That’s why future **parrots **(advocates) in law schools learn **mathematical logic**. Then, when defending the** client** in court, they **express** themselves** briefly** and **concisely**.**Fig. 3-5e**

This is an example of a function with **3** inputs **x1 x2 x3**. Each cell is a** different** combination of these inputs corresponding to a **different** product. Try to work out the product with a** circle** yourself, especially the carets-negations with the appropriate zeros **x2 x3**, as well as combinations for the remaining **4** cells of the table with **1**. For this function with** 3** inputs, we have a table of dimensions** 2×4**. Similarly, for **4**-input functions there is a 4×4 table and for **5**-input functions there is a **4×8** table. Returning to **Fig. 3-5e**, the same function can be presented in a “raw” form, so to speak. In other words, **canonical**, i.e. in the form of **5** products with **3** components each. Thanks to **Mr. Karnaugh**, using the so-called** gluing**, it can also be presented as just** two products**. Moreover, they are shorter, because the first one has only **2** components and the second one** 1**. Therefore, the **computer program** performing this function, will be simpler, cheaper and more reliable.

You can find more about the **Karnaugh** method **online**.