Difference between revisions of "Aufgaben:Exercise 2.4: GF(2 to the Power of 2) Representation Forms"
From LNTwww
Line 1: | Line 1: | ||
− | {{quiz-Header|Buchseite= | + | {{quiz-Header|Buchseite=Channel_Coding/Extension_Field}} |
− | [[File:EN_KC_A_2_4.png|right|frame| | + | [[File:EN_KC_A_2_4.png|right|frame|Three representations for ${\rm GF}(2^2)$]] |
− | + | Opposite you can see for the extension field $\rm GF(2^2)$ the addition– as well as the multiplication table in three different variants: | |
− | * | + | * the polynomial representation, |
− | * | + | * the coefficient vector representation, |
− | * | + | * the exponent representation. |
− | + | Hints: | |
− | + | * The exercise refers to the chapter [[Channel_Coding/Extension_Field|extension fields]]. | |
− | + | * All necessary information about ${\rm GF}(2^2)$ can be found on the [[Channel_Coding/Extension_Field#GF.2822.29_.E2.80.93_Example_of_an_extension_field|first page]] of this chapter. | |
− | * | + | * In the subtask '''(4)''' the following expressions are considered: |
− | * | ||
− | * In | ||
:$$A = z_2 \cdot z_2 + z_2 \cdot z_3 + z_3 \cdot z_3,$$ | :$$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).$$ | :$$B = (z_0 + z_1 + z_2) \cdot (z_0 + z_1 + z_3).$$ | ||
Line 22: | Line 20: | ||
− | === | + | ===Questions=== |
<quiz display=simple> | <quiz display=simple> | ||
− | { | + | {What characteristics can be recognized from the polynomial representation? |
|type="[]"} | |type="[]"} | ||
− | + | + | + The elements $\alpha$ and $1 + \alpha$ are neither $0$ nor $1$. |
− | + | + | + The arithmetic operations are modulo $2$. |
− | - | + | - The arithmetic operations are performed modulo $4$. |
− | - | + | - One recognizes the result $\alpha^2 + \alpha + 1 = 0$ from the addition table. |
− | + | + | + One recognizes the result $\alpha^2 + \alpha + 1 = 0$ from the multiplication table. |
{Welcher Zusammenhang besteht zwischen der Koeffizientenvektor– und der Polynomdarstellung? Es gelte $k_0 ∈ \{0, \, 1\}$ und $k_1 ∈ \{0, \, 1\}$. | {Welcher Zusammenhang besteht zwischen der Koeffizientenvektor– und der Polynomdarstellung? Es gelte $k_0 ∈ \{0, \, 1\}$ und $k_1 ∈ \{0, \, 1\}$. |
Revision as of 15:07, 31 August 2022
Opposite you can see for the extension field $\rm GF(2^2)$ the addition– as well as the multiplication table in three different variants:
- the polynomial representation,
- the coefficient vector representation,
- the exponent representation.
Hints:
- The exercise refers to the chapter extension fields.
- All necessary information about ${\rm GF}(2^2)$ can be found on the first page of this chapter.
- In the subtask (4) 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
Musterlösung
(1) Zutreffend sind die Lösungsvorschläge 1, 2 und 5.
Begründung:
- Wäre $\alpha = 0$ oder $\alpha = 1$, so wäre das Pseudoelement $\alpha$ nicht mehr unterscheidbar von den beiden anderen ${\rm GF}(2)$–Elementen $0$ und $1$.
- Die Modulo–$2$–Rechnung erkennt man aus der Additionstabelle. Beispielsweise gilt $1 + 1 = 0, \ \alpha + \alpha = 0, \ (1 + \alpha) + (1 + \alpha) = 0$, usw.
- Aus der Multiplikationstabelle geht hervor, dass $\alpha^2 = \alpha \cdot \alpha = 1 + \alpha$ gilt (3. Zeile, 3. Spalte). Damit gilt auch
- $$\alpha^2 + \alpha + 1 = 0.$$
(2) Richtig ist Lösungsvorschlag 2. So steht
- "$01$" für das Element "$1$" und
- "$10$" für das Element "$\alpha$".
(3) Richtig sind die Lösungsvorschläge 2 und 3:
- Es gilt $\alpha^0 = 1$ und $\alpha^1 = \alpha$.
- Bei dem zugrundeliegenden Polynom $p(x) = x^2 + x + 1$ folgt aus $p(\alpha) = 0$ weiterhin:
- $$\alpha^2 +\alpha + 1 = 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} \alpha^2 =\alpha + 1 \hspace{0.05cm}.$$
(4) Entsprechend den Tabellen der Polynomdarstellung gilt:
- $$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}.$$
Richtig sind demnach die Lösungsvorschläge 1 und 2.
Zu den gleichen Ergebnissen kommt man mit der Koeffizientenvektordarstellung:
- $$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}.$$
Und schließlich mit der Exponentendarstellung:
- $$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}.$$