Binary BCH (31,16,7) linear cyclic code work out

Some more field algebra

The minimal polynomial of \(\alpha\), \(m_{\alpha}(x)\) is the smallest polynomial in \(K[x]\) of smallest degree having \(\alpha\) as a root, that is, if \(f(x)=a_0+ a_1x+a_2x^2+..+a_kx^k\), that is \(f(\alpha)=a_0+a_1\alpha+a_2\alpha^2+..+a_k\alpha^k = 0\)

The order of nonzero element \(\alpha\) in \(GF(2^r)\) is the smallest positive \(m\) such that \(\alpha^m = 1\). If \(\alpha\) is of order \(2^r-1\) then it is a primitive element. It not easy to find the primitive polynomial of higher degree. Luckily the hard part of finding them has been done and tabulated for our use and this is what I will use for my implementation.

If \(\alpha\) has order \(m\), then \(\alpha\) is a root of \(1+x^m\). Relative to my previous post, defining \(\beta\) as primitive element, \(\alpha=\beta^i\), then \(\alpha^{2r-1}=(\beta^i)^{2r-1}= (\beta^{2r-1})^i = 1^i = 1\). \(\alpha\) is therefore a root of \(1+x^{2r-1}\) and \(m_\alpha(x)\) is a factor of \(1+x^{2r-1}\). In the last post \(g(x) | (1+x^{15})\). \(g(x)\) must be the least common multiple of \(m_i(x),m_2(x),..,m_{2t}(x)\). Taking the conjugate roots into account, the t-error-correcting BCH of code length \(n=2^r-1\) has its generator \(g(x)\) reduced to,

Since the degree of of each minimal polynomial is \(m\) or less, \(g(x)\) has degree at most \(mt = (n-k)\), its parity check digits. Base on the theorem that the set of all roots of \(m_\alpha(x)\) is \(\{\alpha,\alpha^2,\alpha^4,..,\alpha^{2t-1}\}\), the single error-correcting BCH codes will have the generator polynomial, \(g(x) = m_{\alpha^1}(x)\). The two error-correcting codes will have the generator polynomial, \(g(x) = m_\alpha(x)m_{\alpha^3}(x)\).

I can generate the elements of \(GF(2^5)\) based on \(p(x)=x^5+x^2+1\) as the primitive polynomial numerically using deconv of MATHLAB/Octave,

then tabulate the result,

Note that \(\alpha^{31}=1\).

b'\nn "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">\n\n\n\n'

The elements obtained above can also be calculated by hand, for example, \(\alpha^{25}\) can be obtained by first, set \(p(\alpha) = \alpha^5+\alpha^2+1=0\) then solve for it using the table above,

The result agrees with what is obtained numerically by MATLAB/Octave. I think it is fine just to randomly verify the result for couple of elements after \(\alpha^5\).

Next is to get the generator polynomial by performing the calculation for minimal polynomials, \(m_1(x)=p(x), m_3(x)\) and \(m_5(x)\), that is the root based on \(\alpha, \alpha_3\) and \(\alpha^5\) because I need \(g(x)=m_1(x)m_3(x)m_5(x)\) for this exercise. I can avoid the tedious calculation by opting to use the tabulated generator polynomials of \((n,k,d)\) BCH code. For the \((31,16,7), t=3\), \(m_3(x)=x^5+x^4+x^3+x^2+1\), and \(m_5(x)=x^5+x^4+x^2+x+1\).

Using MATLAB/Octave's conv to multiply the polynomial,

This matches to the tabulated octal table value, \((107657)_8 = 001 000 111 110 101 111\). I can verify that \(g(x) | (x^{31} + 1)\) using Octave's deconv operation. This is to confirm that any irreducible polynomial over GF(2) of degree \(m\) divides \(X^{2^m-1}+1\).

b'\nn "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">\n\n\n\n'

b'\nn "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">\n\n\n\n'

By definition, a t-error-correcting BCH code of lengt \(2^m-1\) having a binary n-tuple \(u(X)=u_0+u_1+\cdots+u_{n-1}\) is a code word iff \(u(X)\) has \(\alpha,\alpha^2, \cdots,\alpha^{2t}\) as roots, that is,

and for this exercise,

note that the power of \(\alpha\) will wrap on this finite field, for example, \(\alpha^{35} = \alpha^{31} \alpha^4 = \alpha^{4}\). Put it in matrix form,

The equation above is in the form,

note \((\alpha^i)^0 = 1\). The transpose of the parity-check matric, \(H\) is a 31x15 matrix. It will follow that if \(U=(u_0,u_1,\cdots,u_{31})\) is a code word, then \(UH^t = 0\). \(\alpha^3 \equiv x^i mod(m_3(x))\) and so on.

Each column of power of \(\alpha\) is arranged below for \(H^t\) parity check matrix. It is not important as to whether to go for head first or bottom first as long as it stays consistent. The matrix below has the highest power of \(\alpha\) at its top row.

MATLAB/Octave is used to generate the power of \(\alpha\) above,

The parity check is not in systematic form.

Likewise the generator matrix can be obtained from the generator polynomial, \(g(x)\),

since \(G \perp H\), \(GH^t = 0\). The parity check matrix obtained this way can be easily implemented in hardware using the shift registers for error detection.

for i=1:n [a,r(i,:)]= deconv(I(i,:),gx);end
r=r(:,17:31);r=mod(r,2);
p=r(1:16,:); %partity bits
% generator matrix
G=[eye(16) p];
mod(G*h,2) %  zeros

v=dec2bin(0:2^16-1)-'0'; % input code word
u=mod(v*G,2); % BCH coded word

>> mod(u(1000,:)*h,2)

ans =

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

w=u(1000,:); % a coded word
w(14)=0; %was 1, set to 0 to simulate error

>> mod(w*h,2)
ans =
   1 0 0 1 1 0 1 1 0 0 0 1 1 1 1

w(1)=1; % was 0, set to 1 as error. Now we have bit0,14 as error bits
>> mod(w*h,2)
ans =
   0 0 0 0 1 1 1 0 1 0 1 1 0 0 0
>> mod(h(1,:)+h(14,:),2)
ans =
   0 0 0 0 1 1 1 0 1 0 1 1 0 0 0