Given a syndrome $wH$, $GF(2^4)$ and $\beta$ (class of $x$), determine if $d(v,w) \leq 2$ for some $v$ in a BHC code $C$

321 Views Asked by At

I would like to know what is the best way to do that manually. Consider the following case:

$GF(2^4)$ is constructed as $K[x]$ modulo $1 + x + x^4$.

$\beta$ is the class of $x$ so $1 + \beta + \beta^4 = 0$ and $\beta$ is primitive. The table for its powers is:

0000 -
1000 1
0100 $\beta$
0010 $\beta^2$
0001 $\beta^3$
1100 $\beta^4$
0110 $\beta^5$
0011 $\beta^6$
1101 $\beta^7$
1010 $\beta^8$
0101 $\beta^9$
1110 $\beta^{10}$
0111 $\beta^{11}$
1111 $\beta^{12}$
1011 $\beta^{13}$
1001 $\beta^{14}$

$C \subseteq K^{15}$ is an 2-error correcting BHC code with parity check matrix

$H = \begin{pmatrix} 1 & 1\\ \beta & \beta^3 \\ \beta^2 & \beta^6 \\ \vdots & \vdots \\ \beta^{14} & \beta^{42} \end{pmatrix} $

and $wH = [s_1,s_3] = [\beta^7, \beta^6]$ or $wH = [s_1,s_3] = [\beta^7, 0]$

1

There are 1 best solutions below

2
On BEST ANSWER

Since the syndrome is non-zero in both cases we conclude that error(s) have occured. As the code is two-error-correcting, we wish that the number of errors is one or two.

If there is a single error at position $i$, $0\le i<15$, then let $x=\beta^i\in GF(16)$. In that case we get $wH=(s_1,s_3)=(x,x^3)=(\beta^i,\beta^{3i})$. Because $(\beta^7)^3=\beta^{21}=\beta^{15+6}=\beta^6$, your first syndrome happens to be compatible with this. Thus we conclude that in the first case the bit at position $i=7$ is in error, and decode accordingly.

In the second case we need to do more work, because obviously $s_3=0\neq s_1^3$. Anyway, we see that the syndrome is incompatible with there being just one error. Let's wishfully check out, whether it is possible that there are two errors, at positions $i$ and $j$, $0\le i<j<15$. Denote $x=\beta^i, y=\beta^j$. The syndrome equations are then $$ \left\{\begin{array}{lcl} x+y&=&\beta^7,\\ x^3+y^3&=&0. \end{array}\right. $$ There are several ways of approaching this system of equations (note that in general we are not guaranteed to have a solution, as it is possible that more than two errors occured). I could go a bit ad hoc using the unusual fact that $s_3=0$, but let's do it in a general way first. We have a factorization $$ 0=s_3=x^3+y^3=(x+y)(x^2+xy+y^2). $$ From this we can deduce that $x^2+xy+y^2=s_3/s_1=0$. Furthermore, squaring the first syndrome equation gives us $$ x^2+y^2=x^2+2xy+y^2=(x+y)^2=\beta^{14}. $$ Therefore $$ xy=(x^2+xy+y^2)+(x^2+y^2)=0+\beta^{14}=\beta^{14}. $$ At this point we know the elementary symmetric polynomials of the error locations. In other words we know the coefficients of the polynomial $$ p(T)=(T-x)(T-y)=T^2+(x+y)T+xy=T^2+\beta^7T+\beta^{14}. $$ If this polynomial has two distinct non-zero zeros in the field $GF(16)$, then they must be $x$ and $y$. In hardware often something called Chien search will check this for you. There is an algebraic method for checking solvability of a quadratic, but it needs a trace check, and the so called half-trace, and I'm not in the mood to explain that. So let's have it understood that in general this is the way to go, and do ad hoc instead. Also, it may happen that $p(T)$ has no zeros in $GF(16)$ in which case we again conclude that more than two errors occured.

A way to use the fortunate $s_3=0$ is the following. From $x^3+y^3=0$ we conclude that $x^3=y^3$, so $x/y$ must be a third root of unity. The third roots of unity in $GF(16)$ are $1=\beta^0, \beta^5$ and $\beta^{10}$. Because $x\neq y$ (you can't have two errors at the same position), we rule out the first possibility. So either $x=\beta^5 y$ or $x=\beta^{10}y$. In the latter case we have $y=\beta^5 x$, so if we interchange the roles of $x$ and $y$ (and thus lift the requirement $i<j$) we can assume that $x=\beta^5 y$. Given this, the second syndrome equation is then automatic. The first syndrome equation reads $$ \beta^7=x+y=x(1+\beta^5). $$ From your table of base $\beta$ discrete logarithms we read that $$ 1+\beta^5=1+\beta+\beta^2=\beta^{10} $$ (you need to mentally scan that table and spot the $1+\beta+\beta^2$, or use another trick). Therefore $$ \beta^7=x\beta^{10}, $$ and we can conclude that $$ x=\beta^{7-10}=\beta^{-3}=\beta^{12}. $$ Recalling that $$ y=x\beta^5=\beta^{12+5}=\beta^{15+2}=\beta^2, $$ we can then conclude that the errors occured at positions $2$ and $12$.