Syndrome computation of BCH code

Question

I'm just trying to understand one basic property of BCH code. It was mentioned in many articles that, for binary BCH code, syndrome computation has such property: $$S_{2i+1} = (y(\alpha^{i+1}))^2=S_i^2$$, where $y(x)$ is the received codeword. However, I wonder if all the polynomial evaluation over the finite field elements under the same cyclotomic cosets can be done in a similar way. For example, for $GF(2^3)$, $\{\alpha^3,\alpha^5,\alpha^6\}$ is the coset, where $\alpha^6 = \alpha^{3*2} \ \text{and} \ \alpha^5 = \alpha^{3*2^2 mod \ 7}$. As shown above, $S_5 = S_2^2$. However, isn't that $S_4 = S_2^{2^2}$? The prove is shown as follows $$S_2^{2^2} = (y(\alpha^3))^{2^2} \\ = y(\alpha^{12 \ mod \ 7}) \\ = y(\alpha^{5}) \\ =S_4$$. Can someone helps me verify if this is true? Note: For binary BCH code, $(y(\alpha^3))^{2^2} = y(\alpha^{12})$ is valid. For the reference, this property is mentioned in this article: "Generalized Integrated Interleaved Codes" by Yingquan Wu.

Edited version: Since this question is not clear, I would like to simplify it into one short question. For $GF(2^8)$, is $$y(α^{49})=(y(α^{19}))^{2^4}$$ right or wrong? If it is wrong, can someone prove it to me?

So the conclusion by @rcgldr: The above equality is correct. And, $S_{48}=S_{18}^{2^4}$

Answer 1

The question uses non-standard naming convention for the syndromes: $$S_i = y(\alpha^{i+1})$$

Using the questions naming convention, the odd syndromes $S_1, S_3, S_5, ... $ are powers of other syndromes, therefore redundant and optionally skipped when using Berlekamp Massey decoder: $$S_1 = (y(\alpha^1))^2 = S_0^2$$ $$S_3 = (y(\alpha^2))^2 = S_1^2 = S_0^4$$ $$S_5 = (y(\alpha^3))^2 = S_2^2$$ $$S_7 = (y(\alpha^4))^2 = S_3^2 = S_0^8$$ $$S_9 = (y(\alpha^5))^2 = S_4^2$$ $$S_{11} = (y(\alpha^6))^2 = S_5^2 = S_2^4$$

In GF(2^3), does $S_4 = S_2^4$ ?

Yes. In a larger field, $S_2^4 = S_{11}$. In GF(2^3), $S_{11} = S_{11\%7} = S_4$.

In GF(2^8), does $S_{48} = S_{18}^{16}$?

Yes. In a larger field, $S_{18}^{16}$ = $S_{303}$. In GF(2^8), $S_{303} = S_{303\%255} = S_{48}$.

---

Using standard naming convention for syndromes common to BCH code and Reed Solomon code:

$$S_i = y(\alpha^i)$$ $$S_{2i} = S_i^2$$

If using Berlekamp Massey decoder, then even syndromes (S₂, S₄, S₆, ...) are redundant and can be skipped (see next section), while odd syndromes (S₁, S₃, S₅, ...) are required in order to decode.

For smaller fields of $GF(2^n)$, an even syndrome of higher order $a$ greater than $2^{n-1}$ and less than $2^{2n-2}$ will map to an odd syndrome of lower order $b$: $S_a = S_{a\%(2^{n-1})} = S_b$ This allows $S_b$ to be calculated by using the formula $S_b = S_a = S_{a/2}^2 = S_{a/4}^4 = $ ... .

Note - unlike BCH code, for Reed Solomon code, all syndromes are required.

---

To explain why the formula works for even syndromes but not odd, in GF(2^n): $$(a+b)^2 = a^2 + b^2$$ $$(a+b)^3 = a^3 + a^2 b + a b^2 + b^3$$ $$(a+b)^4 = a^4 + b^4$$ $$(a+b)^5 = a^5 + a^4 b + a b^4 + b^5$$ $$...$$ $$(a+b+c\ +...)^2 = a^2 + b^2 + c^2 + ... $$

Consider a 2 error case in GF(2^8) with reducing polynomial hex 11d, 6 syndromes, with errors at x^4 and x^8. Using hex: $$S_1 = (2^1)^4 + (2^1)^8 = 0d $$ $$S_2 = (2^2)^4 + (2^2)^8 = 51 $$ $$S_3 = (2^3)^4 + (2^3)^8 = 42 $$ $$S_4 = (2^4)^4 + (2^4)^8 = d1 $$ $$S_5 = (2^5)^4 + (2^5)^8 = de $$ $$S_6 = (2^6)^4 + (2^6)^8 = c9 $$ For the even syndromes: $$S_1^2 = ((2^1)^4 + (2^1)^8)^2 = ((2^1)^4)^2 + ((2^1)^8)^2 = (2^2)^4 + (2^2)^8 = S_2$$ $$S_2^2 = ((2^2)^4 + (2^2)^8)^2 = ((2^2)^4)^2 + ((2^2)^8)^2 = (2^4)^4 + (2^4)^8 = S_4$$ $$S_3^2 = ((2^3)^4 + (2^3)^8)^2 = ((2^3)^4)^2 + ((2^3)^8)^2 = (2^6)^4 + (2^6)^8 = S_6$$ But this strategy doesn't work for the odd syndromes.

Answer 2

This question uses nonstandard notation.

From the equation fragment $(y(\alpha^{i+1}))^2=S_i^2$ used by the OP, it seems that in the OP's world, the following definition is believed to apply:

$$S_i \stackrel{\Delta}{=} y(\alpha^{i+1}) \tag{1}$$ in contrast to the more usual $S_i = y(\alpha^i)$. Now, noting that $0^2=0$ and $1^2=1$, we have that if $f(x)$ denotes a polynomial with coefficients in $GF(2)$, then $$[f(x)]^2 = \left(\sum_k f_k x^k\right)^2 = \sum_k (f_k)^2 x^{2k} = \sum_k f_k x^{2k} = f(x^2)$$ so that $$(y(\alpha^{i+1}))^2 = y(\alpha^{2i+2}) \tag{2}$$ to which we apply the OP's convention $(1)$, viz. that the subscript on $S$ is $1$ less than the superscript on $\alpha$, to arrive at the result that $$S_{2i+1} = y(\alpha^{2i+2}) = [y(\alpha^{i+1})]^2 = S_i^2$$ as claimed by the OP. The OP then asks with respect to $GF(2^3)$ where $$\left\{\alpha^3, (\alpha^3)^2, (\alpha^3)^{2^2}\right\} = \left\{\alpha^3, \alpha^6, \alpha^{12}\right\} = \left\{\alpha^3, \alpha^6, \alpha^{5}\right\}$$ that while in his world, $$S_2 = y(\alpha^3) \implies S_2^2 = (y(\alpha^3))^2 = y(\alpha^6) = y(\alpha^{5+1}) = S_5 ~\text{vide}~ (1),$$ he is not absolutely sure whether $S_2^4$ equals $S_4$ or not. Well, $$S_2^4 = y(\alpha^{12}) = y(\alpha^{7+5}) = y(\alpha^5) = y(\alpha^{4+1}= S_4 ~\text{vide}~ (1)$$ sure enough.

---

And yes, the OP's claim that in $GF(2^8)$, $\alpha^{49} = (\alpha^{19})^{2^4}$ is perfectly correct. Those used to working with finite fields would simply use the law of exponents to write $$19 \times 16 = 304 = 255+49$$ to verify the claim.