View source for Aufgaben:Exercise 2.4: GF(2 to the Power of 2) Representation Forms

{{quiz-Header|Buchseite=Channel_Coding/Extension_Field}}

[[File:EN_KC_A_2_4.png|right|frame|Three representation forms for &nbsp;${\rm GF}(2^2)$]]
Opposite you can see the addition table as well as the multiplication table for the extension field&nbsp; $\rm GF(2^2)$&nbsp; in three different variants:
* the&nbsp;  '''polynomial representation''',

* the&nbsp;  '''coefficient vector representation''',

* the&nbsp;  '''exponent representation'''.




Hints:
* The exercise refers to the chapter&nbsp; [[Channel_Coding/Extension_Field|"Extension fields"]].

* All necessary information about&nbsp; ${\rm GF}(2^2)$&nbsp; can be found on the&nbsp; [[Channel_Coding/Extension_Field#GF.2822.29_.E2.80.93_Example_of_an_extension_field|"first page"]]&nbsp; of this chapter.

* In subtask&nbsp; '''(4)'''&nbsp; the following expressions are considered:
:$$A = z_2 \cdot z_2 + z_2 \cdot z_3 + z_3 \cdot z_3,$$
:$$B = (z_0 + z_1 + z_2) \cdot (z_0 + z_1 + z_3).$$




===Questions===
<quiz display=simple>
{What characteristics can be recognized from the polynomial representation?
|type="[]"}
+ The elements&nbsp; "$\alpha$"&nbsp; and&nbsp; "$1 + \alpha$"&nbsp; are neither&nbsp; $0$&nbsp; nor&nbsp; $1$.
+ The arithmetic operations are performed modulo&nbsp; $2$.
- The arithmetic operations are performed modulo&nbsp; $4$.
- One recognizes the result &nbsp; $\alpha^2 + \alpha + 1 = 0$ &nbsp; from the addition table.
+ One recognizes the result &nbsp; $\alpha^2 + \alpha + 1 = 0$ &nbsp; from the multiplication table.

{What is the relationship between the coefficient vector and the polynomial representation? <br>Let&nbsp; $k_0 &#8712; \{0, \, 1\}$&nbsp; and&nbsp; $k_1 &#8712; \{0, \, 1\}$ hold.
|type="()"}
- "$(k_0 \ k_1)"$&nbsp; refers to the element&nbsp; "$k_1 \cdot \alpha + k_0$".
+ "$(k_1 \ k_0)$"&nbsp; refers to the element&nbsp; "$k_1 \cdot \alpha + k_0$".
- There is no relationship between the two representations.

{How are polynomial and exponent representation related?
|type="[]"}
- No connections can be seen.
+ The elements&nbsp; "$0, \ 1$"&nbsp; and&nbsp; "$\alpha$"&nbsp; are the same in both representations.
+ The element&nbsp; "$1 + \alpha$"&nbsp; is&nbsp; "$\alpha^2$"&nbsp; in the exponent representation.
- The element&nbsp; "$\alpha^2$"&nbsp; of the exponent representation stands for&nbsp; "$\alpha \cdot (1 + \alpha)$".

{Calculate the expressions&nbsp; $A$&nbsp; and&nbsp; $B$&nbsp; according to these three forms of representation.&nbsp; Which statements are true?
|type="[]"}
+ It holds&nbsp; $A = z_0$,
- It holds&nbsp; $A = z_2$,
+ It holds&nbsp; $B = z_1$,
- It holds&nbsp; $B = z_3$.
</quiz>

===Solution===
{{ML-Kopf}}
'''(1)'''&nbsp; The&nbsp; <u>proposed solutions 1, 2 and 5</u>&nbsp; are applicable.&nbsp; <u>Justification:</u>
* If&nbsp; $\alpha = 0$&nbsp; or&nbsp; $\alpha = 1$,&nbsp; the pseudo element&nbsp; $\alpha$&nbsp; would be indistinguishable from the other two&nbsp; ${\rm GF}(2)$&nbsp; elements&nbsp; $0$&nbsp; and&nbsp; $1$.

* The modulo-2 calculation can be recognized from the addition table.&nbsp; For example,&nbsp; $1 + 1 = 0, \ \alpha + \alpha = 0, \ (1 + \alpha) + (1 + \alpha) = 0$, etc.
* From the multiplication table we see that&nbsp; $\alpha^2 = \alpha \cdot \alpha = 1 + \alpha$&nbsp; holds&nbsp; $($3rd row,&nbsp; 3rd column$)$.&nbsp; Thus also 
:$$\alpha^2 + \alpha + 1 = 0.$$



'''(2)'''&nbsp; Correct is the&nbsp; <u>solution suggestion 2</u>.&nbsp; Thus 
*"$01$"&nbsp; for the element&nbsp; "$1$"&nbsp; and
 
*"$10$"&nbsp; for the element&nbsp; "$\alpha$".




'''(3)'''&nbsp; Correct are the&nbsp; <u>solutions 2 and 3</u>: 
*It is true that&nbsp; $\alpha^0 = 1$&nbsp; and&nbsp; $\alpha^1 = \alpha$.
 
*For the underlying polynomial&nbsp; $p(x) = x^2 + x + 1$,&nbsp; it follows further  from&nbsp; $p(\alpha) = 0$:
:$$\alpha^2 +\alpha + 1 = 0  \hspace{0.3cm} \Rightarrow\hspace{0.3cm} \alpha^2 =\alpha + 1 \hspace{0.05cm}.$$



'''(4)'''&nbsp; According to the tables of polynomial representation holds:
:$$A \hspace{-0.15cm} \ = \ \hspace{-0.15cm} z_2 \cdot z_2 + z_2 \cdot z_3 + z_3 \cdot z_3 =  \alpha \cdot \alpha + \alpha \cdot (1+\alpha) + (1+\alpha) \cdot (1+\alpha) = (1+\alpha) + (1) + (\alpha) = 0 = z_0
 \hspace{0.05cm},$$
:$$ B \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (z_0 +  z_1 + z_2) \cdot (z_0 +  z_1 + z_3) =  (0 + 1 + \alpha) \cdot (0 + 1 + 1+ \alpha) = (1+\alpha) \cdot \alpha = 1 = z_1
 \hspace{0.05cm}.$$

*Therefore,&nbsp; the&nbsp; <u>proposed solutions 1 and 2</u>&nbsp; are correct. 

*The same results are obtained with the coefficient vector representation:
:$$A \hspace{-0.15cm} \ = \ \hspace{-0.15cm} z_2 \cdot z_2 + z_2 \cdot z_3 + z_3 \cdot z_3 = (10) \cdot (10) + (10) \cdot (11) + (11) \cdot (11) = (11) + (01) + (10) = (00) = 0 = z_0
 \hspace{0.05cm},$$
:$$B \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (z_0 +  z_1 + z_2) \cdot (z_0 +  z_1 + z_3)  =  [(00) + (01) + (10)]  \cdot [(00) + (01) + (11)] =(11) \cdot (10) = (01) = z_1
 \hspace{0.05cm}.$$

*And finally with the exponent representation:
:$$A \hspace{-0.15cm} \ = \ \hspace{-0.15cm} z_2 \cdot z_2 + z_2 \cdot z_3 + z_3 \cdot z_3 = \alpha^1 \cdot \alpha^1 + \alpha^1 \cdot \alpha^2 + \alpha^2 \cdot \alpha^2 =
 \alpha^2 + \alpha^3 + \alpha^4 =  \alpha^2 + \alpha^0 + \alpha^1 = 0 = z_0
 \hspace{0.05cm},$$
:$$B \hspace{-0.15cm} \ = \ \hspace{-0.15cm}(z_0 +  z_1 + z_2) \cdot (z_0 +  z_1 + z_3)  =  [0 + \alpha^0 + \alpha^1]  \cdot [0 + \alpha^0 + \alpha^2] = \alpha^2 \cdot \alpha^1 = \alpha^3 = \alpha^0 = z_1
 \hspace{0.05cm}.$$
{{ML-Fuß}}



[[Category:Channel Coding: Exercises|^2.2 Extension Field^]]