How do we find the minimum distance of a narrow sense BCH code?

Question

I know the designed distance, $d$, is a lower bound for the minimum distance, $d(C)$.

Usually, in the examples I've seen, what we do is find the generator polynomial $g(x)$ of the code, then from $d \le d(C) \le w(g)$, where $w(g)$ is the weight of the code word $g(x)$, it always so happens that $w(g)=d$. This clearly doesn't always work. What if the last equality doesn't hold? Is there a way to find the minimum distance without finding the generator polynomial first?

For example, in our text, for the narrow sense BCH code of length 23 with $d=5$, the minimum distance is said to be $7$. How are they getting this?

Answer 1

This is a very special code $C$ known as the binary Golay code. To get $d_{min}=7$ you can do the following.

• The smallest extension field containing a 23rd root of unity is $GF(2^{11})$. We see this for example by repeatedly applying the Frobenius (i.e. squaring). If $\alpha$ is a 23rd root of unity, its conjugates are $$\alpha,\alpha^2,\alpha^4,\alpha^8,\alpha^{16},\alpha^9,\alpha^{18},\alpha^{13},\alpha^3,\alpha^6,\alpha^{12}.$$
• So you see that the minimal polynomial of $\alpha$ has as its zeros also $\alpha^2$, $\alpha^3$ and $\alpha^4$. Therefore the BCH-bound says that $d_{min}\ge5$.
• For the rest to work, you need to produce a generator matrix for $C$. If you know a generator polynomial $g(x)$, it is easy. Another way is to calculate the idempotent of $C$. By the same calculation we see that idempotents in the ring $R=GF(2)[x]/\langle x^{23}+1\rangle$ are $$e(x)=x+x^2+x^3+x^4+x^6+x^8+x^9+x^{12}+x^{13}+x^{16}+x^{18}$$ its reciprocal $\tilde{e}(x)=x^{23}e(\dfrac1x)$, and whatever you get by adding $1$ to one of them (the sum $e+\tilde{e}$ is also an idempotent, but it generates the repetition code, so is not interesting).
• IIRC $e(x)$ generates a code we want. The code is 12-dimensional, and you get a basis for $C$ by writing out the words $x^ie(x), 0\le i\le 11$.
• Extend $C$ to a code $C^+$ of length $24$ by adding an overall parity check bit.
• Then follows the key step: Check that the basis vectors generating $C^+$ all have weights divisible by four, and that they are orthogonal to each other. Prove (by induction on the number of generators appearing in the sum) that all the words of $C^+$ have weights divisible by four.
• Conclude that $d_{min}(C^+)\ge8$, and thus $d_{min}(C)\ge7$.