Aufgaben:Exercise 2.08Z: Addition and Multiplication in GF(2 power 3)

• Return to book

$\rm GF(2^3)$: Incomplete addition and multiplication tables

The graph shows the addition and multiplication table for the finite field  $\rm GF(2^3)$. The tables are not complete. Some fields (highlighted in color) should be completed.

The elements are given both in the exponent representation (with red lettering, left and above) and in the coefficient representation (gray lettering, right and below). From this assignment one can already recognize the underlying irreducible polynomial  $p(\alpha)$.

• Additions (and subtractions) are best done in the coefficient representation (or with the polynomials firmly linked to it).
• For multiplications, however, the exponent representation is more convenient.

Hints:

• Die Aufgabe gehört zum Kapitel  "Definition and Properties of Reed-Solomon Codes".
• However, reference is also made to the chapter  "Extension Field".

Questions

1

What element does the  $\rm A$  stand for in the addition table?

	$\rm A = 0$,
	$\rm A = 1$,
	$\rm A = \alpha^1$,

2

What element does the  $\rm B$  stand for in the addition table?

	$\rm B = 0$,
	$\rm B = 1$,
	$\rm B = \alpha^1$.

3

What element does the  $\rm C$  stand for in the addition table?

	$\rm C = \alpha^2$,
	$\rm C = \alpha^3$,
	$\rm C = \alpha^4$.

4

What element does the  $\rm D$  stand for in the addition table?

	$\rm D = \alpha^2$,
	$\rm D = \alpha^3$,
	$\rm D = \alpha^4$.

5

What assignments apply in the multiplication table?

	$\rm E = \alpha^5$,
	$\rm F = \alpha^1$,
	$\rm G = \alpha^6$.

6

What irreducible polynomial underlies these tables?

	$p(\alpha) = \alpha^2 + \alpha + 1$,
	$p(\alpha) = \alpha^3 + \alpha^2 + 1$,
	$p(\alpha) = \alpha^3 + \alpha + 1$.

Solution

Solution

(1)  Adding any element of an extension field based on $\rm GF(2)$ to itself always yields $0$, as can be easily seen from the coefficient representation, for example:

$$\alpha^3 + \alpha^3 = (011) + (011) = (000) = 0 \hspace{0.05cm}.$$

That is:   $\rm A$stands for the zero element   ⇒   Solution 1.

(2)  $\rm B$ is the result of adding $\alpha^5$ and $\alpha^6$  ⇒  Solution 3:

$$\alpha^5 + \alpha^6 = (111) + (101) = (010) = \alpha^1 \hspace{0.05cm}.$$

• One could have found this result more simply, since in each row and column each element occurs exactly once.
• After $\rm A = 0$ is fixed, exactly only the element $\alpha^1$ is missing in the last row and the last column.

(3)  $\rm C$ is the result of the sum of $\alpha^1$ and $\alpha^2$   ⇒   Solution 3:

$$\alpha^1 + \alpha^2 = (010) + (100) = (110) = \alpha^4 \hspace{0.05cm}.$$

(4)  $\rm D$ is the result of $\alpha^3$ and $\alpha^5$   ⇒   Solution 1:

$$\alpha^3 + \alpha^5 = (011) + (111) = (100) = \alpha^2 \hspace{0.05cm}.$$

(5)  All proposed solutions are correct, as can be seen from row 2 (multiplication with the identity element):

$\rm GF(2^3)$: Complete addition and multiplication tables

• The complete tables for addition and multiplication are shown opposite.
• Because of the validity of $\alpha^i \cdot \alpha^j = \alpha^{(i+j)\hspace{0.1cm} {\rm mod}\hspace{0.1cm} 7} $, multiplication yields a symmetry that could be used to solve.

(6)  Correct here is the proposed solution 3:

• All polynomials are indeed irreducible. However, one needs a degree 3 polynomial for $\rm GF(2^3)$.
• The third proposed solution results from the relation

$$\alpha^3 = \alpha + 1 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} p(\alpha) = \alpha^3 + \alpha + 1 = 0 \hspace{0.05cm}.$$