Difference between revisions of "Aufgaben:Exercise 2.3Z: Polynomial Division"
From LNTwww
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{quiz-Header|Buchseite=Channel_Coding/Extension_Field}} | {{quiz-Header|Buchseite=Channel_Coding/Extension_Field}} | ||
| − | [[File:P_ID2504__KC_Z_2_3.png|right|frame|Multiplication and division of polynomials in $\rm GF(2)$]] | + | [[File:P_ID2504__KC_Z_2_3.png|right|frame|Multiplication and division of polynomials in $\rm GF(2)$ <br><u>Note.</u> remainder $r(x)$]] |
| − | In this exercise we deal with the multiplication and especially the division of polynomials in the Galois field $\rm GF(2)$. In the | + | In this exercise we deal with the multiplication and especially the division of polynomials in the Galois field $\rm GF(2)$. In the graph the procedure is indicated by a simple and (hopefully) self-explanatory example: |
| − | * Multiplying the two polynomials $x^2 + 1$ and $x +1$ yields the result $a(x) = x^3 + x^2 + x + 1$. | + | * Multiplying the two polynomials $x^2 + 1$ and $x +1$ yields the result $a(x) = x^3 + x^2 + x + 1$. |
| − | * Dividing the polynomial $b(x) = x^3$ by $p(x) = x + 1$ gives the quotient $q(x) = x^2 + x$ and the remainder $r(x) = x$. | + | |
| + | * Dividing the polynomial $b(x) = x^3$ by $p(x) = x + 1$ gives the quotient $q(x) = x^2 + x$ and the remainder $r(x) = x$. | ||
| + | |||
* One can check the latter result as follows: | * One can check the latter result as follows: | ||
:$$b(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} p(x) \cdot q(x) + r(x)\hspace{0.05cm}= \big[(x+1) \cdot (x^2+x)\big] +x =\big[x^3+ x^2+x^2+ x\big] +x = x^3\hspace{0.05cm}.$$ | :$$b(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} p(x) \cdot q(x) + r(x)\hspace{0.05cm}= \big[(x+1) \cdot (x^2+x)\big] +x =\big[x^3+ x^2+x^2+ x\big] +x = x^3\hspace{0.05cm}.$$ | ||
| − | Hint: | + | Hint: This exercise belongs to the chapter [[Channel_Coding/Extension_Field| "Extension field"]]. |
| − | |||
| Line 25: | Line 26: | ||
- $a(x) = x^6 + x^3 + x^2 + 1$- | - $a(x) = x^6 + x^3 + x^2 + 1$- | ||
| − | {Which of the polynomial divisions do not yield a remainder $r(x)$? | + | {Which of the polynomial divisions do not yield a remainder $r(x) \ne 0$? |
|type="[]"} | |type="[]"} | ||
+ $(x^5 + x^2 + x + 1)/(x^3 + x + 1)$. | + $(x^5 + x^2 + x + 1)/(x^3 + x + 1)$. | ||
| Line 32: | Line 33: | ||
- $(x^5 + x^2 + x)/(x^2 + 1)$. | - $(x^5 + x^2 + x)/(x^2 + 1)$. | ||
| − | {It is $a(x) = x^6 + x^5 + 1$ and $p(x) = x^3 + x^2 + 1$. <br>Determine $q(x)$ and $r(x)$ according to the description equation $a(x) = p(x) \cdot q(x) + r(x)$. | + | {It is $a(x) = x^6 + x^5 + 1$ and $p(x) = x^3 + x^2 + 1$. <br>Determine $q(x)$ and $r(x)$ according to the description equation $a(x) = p(x) \cdot q(x) + r(x)$. |
|type="()"} | |type="()"} | ||
- $q(x) = x^3 + x^2 + 1, \hspace{0.2cm} r(x) = 0$, | - $q(x) = x^3 + x^2 + 1, \hspace{0.2cm} r(x) = 0$, | ||
| Line 41: | Line 42: | ||
===Solution=== | ===Solution=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' The modulo 2 multiplication of the two polynomials leads to the result | + | '''(1)''' The modulo-2 multiplication of the two polynomials leads to the result |
:$$a(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (x^3+ x+1) \cdot (x^2+1)= x^5+x^3+ x^2+ x^3+x+1 = x^5+ x^2+x+1\hspace{0.05cm}.$$ | :$$a(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (x^3+ x+1) \cdot (x^2+1)= x^5+x^3+ x^2+ x^3+x+1 = x^5+ x^2+x+1\hspace{0.05cm}.$$ | ||
| − | *Thus the <u>proposed solution 2</u> is correct. | + | *Thus the <u>proposed solution 2</u> is correct. |
| − | *The last solution suggestion cannot | + | |
| + | *The last solution suggestion cannot be valid already alone, since the degree of the product polynomial would be unequal $5$. | ||
| − | [[File:P_ID2506__KC_Z_2_3b_neu.png|right|frame|Example 1 for polynomial division]] | + | [[File:P_ID2506__KC_Z_2_3b_neu.png|right|frame|'''Example 1''' for polynomial division]] |
'''(2)''' With the abbreviations | '''(2)''' With the abbreviations | ||
:$$a(x) = x^5+ x^2+x+1\hspace{0.05cm},\hspace{0.4cm}p(x) = x^3+ x+1\hspace{0.05cm},\hspace{0.4cm}q(x) = x^2+ 1$$ | :$$a(x) = x^5+ x^2+x+1\hspace{0.05cm},\hspace{0.4cm}p(x) = x^3+ x+1\hspace{0.05cm},\hspace{0.4cm}q(x) = x^2+ 1$$ | ||
| − | and the result from subtask (1) we get $a(x) = p(x) \cdot q(x)$. | + | and the result from subtask '''(1)''' we get $a(x) = p(x) \cdot q(x)$. |
| − | That is: The divisions $a(x)/p(x)$ and $a(x)/q(x)$ are free of remainders | + | That is: The divisions $a(x)/p(x)$ and $a(x)/q(x)$ are free of remainders |
| − | ⇒ Correct are the <u>solutions 1 and 2</u>. | + | ⇒ Correct are the <u>solutions 1 and 2</u>. |
| − | Even without calculation one recognizes that $a(x)/x^2$ must result in a remainder. After calculation it results explicitly: | + | Even without calculation one recognizes that $a(x)/x^2$ must result in a remainder. After calculation it results explicitly: |
| − | :$$(x^5 + x^2+x+1)/(x^2) = x^3 + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm | + | :$$(x^5 + x^2+x+1)/(x^2) = x^3 + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm remainder}\hspace{0.15cm} r(x) = x+1\hspace{0.05cm}.$$ |
| − | To the last proposed solution | + | To the last proposed solution: We use for shortcut $b(x) = x^5 + x^2 + x = a(x) + 1$. This is the given quotient: |
:$$b(x)/q(x) = a(x)/q(x) + 1/q(x) \hspace{0.05cm}.$$ | :$$b(x)/q(x) = a(x)/q(x) + 1/q(x) \hspace{0.05cm}.$$ | ||
| − | [[File:P_ID2505__KC_Z_2_3c.png|Right|frame|Example 2 for polynomial division]] | + | [[File:P_ID2505__KC_Z_2_3c.png|Right|frame|'''Example 2''' for polynomial division]] |
| − | *The first quotient $a(x)/q(x)$ gives exactly $p(x)$ without remainder, the second quotient $0$ | + | *The first quotient $a(x)/q(x)$ gives exactly $p(x)$ without remainder, the second quotient $0$, remainder $1$. |
| − | *Thus the remainder of the quotient $b(x)/q(x)$ is equal to $r(x) = 1$, as the calculation in | + | |
| + | *Thus the remainder of the quotient $b(x)/q(x)$ is equal to $r(x) = 1$, as the calculation in Example 1 shows. | ||
| − | '''(3)''' The polynomial division is explained in detail in | + | '''(3)''' The polynomial division is explained in detail in Example 2. Correct is the <u>proposed solution 3</u>. |
Latest revision as of 17:17, 29 September 2022
Multiplication and division of polynomials in $\rm GF(2)$
Note. remainder $r(x)$
Note. remainder $r(x)$
In this exercise we deal with the multiplication and especially the division of polynomials in the Galois field $\rm GF(2)$. In the graph the procedure is indicated by a simple and (hopefully) self-explanatory example:
- Multiplying the two polynomials $x^2 + 1$ and $x +1$ yields the result $a(x) = x^3 + x^2 + x + 1$.
- Dividing the polynomial $b(x) = x^3$ by $p(x) = x + 1$ gives the quotient $q(x) = x^2 + x$ and the remainder $r(x) = x$.
- One can check the latter result as follows:
- $$b(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} p(x) \cdot q(x) + r(x)\hspace{0.05cm}= \big[(x+1) \cdot (x^2+x)\big] +x =\big[x^3+ x^2+x^2+ x\big] +x = x^3\hspace{0.05cm}.$$
Hint: This exercise belongs to the chapter "Extension field".
Questions
Solution
(1) The modulo-2 multiplication of the two polynomials leads to the result
- $$a(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (x^3+ x+1) \cdot (x^2+1)= x^5+x^3+ x^2+ x^3+x+1 = x^5+ x^2+x+1\hspace{0.05cm}.$$
- Thus the proposed solution 2 is correct.
- The last solution suggestion cannot be valid already alone, since the degree of the product polynomial would be unequal $5$.
Example 1 for polynomial division
(2) With the abbreviations
- $$a(x) = x^5+ x^2+x+1\hspace{0.05cm},\hspace{0.4cm}p(x) = x^3+ x+1\hspace{0.05cm},\hspace{0.4cm}q(x) = x^2+ 1$$
and the result from subtask (1) we get $a(x) = p(x) \cdot q(x)$.
That is: The divisions $a(x)/p(x)$ and $a(x)/q(x)$ are free of remainders ⇒ Correct are the solutions 1 and 2.
Even without calculation one recognizes that $a(x)/x^2$ must result in a remainder. After calculation it results explicitly:
- $$(x^5 + x^2+x+1)/(x^2) = x^3 + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm remainder}\hspace{0.15cm} r(x) = x+1\hspace{0.05cm}.$$
To the last proposed solution: We use for shortcut $b(x) = x^5 + x^2 + x = a(x) + 1$. This is the given quotient:
- $$b(x)/q(x) = a(x)/q(x) + 1/q(x) \hspace{0.05cm}.$$
Example 2 for polynomial division
- The first quotient $a(x)/q(x)$ gives exactly $p(x)$ without remainder, the second quotient $0$, remainder $1$.
- Thus the remainder of the quotient $b(x)/q(x)$ is equal to $r(x) = 1$, as the calculation in Example 1 shows.
(3) The polynomial division is explained in detail in Example 2. Correct is the proposed solution 3.
