I am trying to understand Cauchy Reed-Solomon Coding based on the paper Optimizing Cauchy Reed-Solomon Codes for Fault-Tolerant Storage Applications. I am referring to the following section:
An $m×n$ Cauchy matrix is defined as follows. Let $X = {x_1,…,x_m}$
and $Y = {y_1,…,y_n}$ be defined such that each $x_i$ and $y_i$ is a
distinct element of $GF(2^w)$, and $X ∩ Y = ∅$. Then the Cauchy matrix
defined by $X$ and $Y$ has $1 / (x_i+y_j)$ in element $i,j$.
According to the given example in figure 2 of above paper, the Cauchy matrix over $GF(2^3)$, where $X = \{1,2\}$ and $Y = \{0,3,4,5,6\}$ should be:
$
\begin{pmatrix}
1 & 5 & 2 & 7 & 4 \\
5 & 1 & 3 & 4 & 7
\end{pmatrix}
$
Now I tried to calculate the elements in the matrix by hand using the formula $1 / (x_i+y_j)$:
$
\begin{pmatrix}
1/(1+0) & 1/(1+3) & 1/(1+4) & 1/(1+5) & 1/(1+6) \\
1/(2+0) & 1/(2+3) & 1/(2+4) & 1/(2+5) & 1/(2+6)
\end{pmatrix}
$
I think my problem breaks down to the question how to calculate the term $\frac{1}{(x_i+y_j)}$ in $GF(2^3)$. For example how do I calculate $1/(2+6)$ ? I simplified it to $1/0$ because $8 \equiv 0 \pmod{2^3}$. This is where I am stuck right now. How do I divide by zero in $GF(2^3)$? Am I doing something wrong in the construction of the Cauchy matrix? Any help is appreciated!
Edit: I found the source of my confusion. I totally got addition and multiplication in $GF(2^3)$ wrong. Following the addition and multiplication tables in figure 1 of the paper everything is alright.
Multiplication and Addition table
Just for clarification: Am I right in the assumption that addition is effectively the same as subtraction in a finite field?
Best Answer
Field $GF(2^3)$ with $8$ elements is not same as the cyclic group $\mathbb{Z}_8$. $GF(2^3)$ has $8$ elements with base field $GF(2)$. For more details you need a Field theory course. For this paper, Addition and multiplication table are given in page $3$. So when you are taking addition, follow the addition table of Figure $1$. For example $2+6=4$. When you are taking inverse follow the multiplication table of Figure $1$. For example $1/4=4^{-1}=7$, since $4\times 7=1$.
Similarly $a_{12}$ position $1+3=2$ (addition table) and $1/2=5$ since $2\times 5=1$ (multiplication table).
Hope it is helpful.