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 polynomials firmly linked to it$)$.

• For multiplications,  however,  the exponential representation is more convenient.

Hints:

• This exercise belongs to the chapter  "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}.$$