Simple Cyclic Hamming codes

Some field algebra

A polynomial of degree \(n\) is said to be primitive (over GF) if it is an irreducible polynomial that is not a divisor of \(1+x^m\), for any \(m < 2^n - 1\). Every finite field has a primitive element. In Galois field (GF), \(GF(q)\), if \(a\) is a non-zero element, it is a primitive if its order is \(q-1\). An irreducible polynomial always divides \(1+x^m\) for \(m = 2^n - 1\) (exact). For this exercise, \(h(x)=1+x+x^4\), does not divide \((1+x^m)\) for any \(m < 2^4 -1 ( m < 15)\). It will divide \((1+x^{15})\) though (is a factor). I can use MATLAB to verify this,

>> h=[ 0 0 0 1];
>> test=[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1];
>> [qr] = deconv(test,h);
>> mod(r,2)
>> s =
 0 0 .... 0

The remainder from the division over Galois field (GF) yields zeros vector from the MATHLAB operations. Next is to construct the parity check matrix, \(H^t\) over \(GF(2^r)\). From parity check matrix, the generator matrix for the code can be found. First, let \(\beta\) represents the code word corresponding to \(x mod h(x)\) so that, \(\beta^i \equiv x^i mod h(x)\). This means that every non-zero can be represented by the power of \(\beta\), for example, \(\beta^5 \equiv x^5 mod (1+x+x^4) = x+x^2\). Verify it with MATHLAB operation,

>> beta5=[1 0 0 0 0 0];
>> [q,r] = deconv(beta5,h);
>> mod(r,2)
ans =
    0 0 0 1 1 0

I need to generate all powers of \(\beta\), from \(\beta^0\) to \(\beta^{14}\). I can use MATLAB operations to do that.

I can do it step-by-step by first generate the matrix of 16 code words follows by modulo operation. MATHLAB's dec2bin(0:2^{11}-1) - '0' is used to generate an arrary or matrix of base code words 0 to \(2^{11}\).

Note that \(\beta^{15} = \beta^0 = 1\) (Theorem 2.4 of [CIT003]). This will give me the cyclic Hamming codes of length \(n = 2^r - 1\) (15) base on the the degree of \(h(x)\) where its parity check matrix is,

If I sum row 1, 4 and 5 together (modulo 2), I get zeros. There is no two rows that forms the third row or sum to zeros so it takes three or more to do that. By definition, it takes \(d-1\) rows of \(H^t\) matrix to show linear independency; therefore, I can verify that its minimum distance is \(d-1=2 \Rightarrow d=3\).

The generator is then obtained from the parity check matrix,

Because of the orthagonality between \(G\) and \(H\), \(GH^t = 0\). The encoded codeword of \(u\) for this \((n,k,d)=(15,11,3)\) is,

where \(v\) is the 11-bit source code word to be encoded. I use MATLAB to create the matrices for the parity(11x4), parity check(15x4) and generator respectively(11x15).

>> p=[1 0 0 1;1 1 0 1;1 1 1 1;1 1 1 0;0 1 1 1;1 0 1 0;0 1 0 1;1 0 1 1;1 1 0 0 ;0 1 1 0;0 0 1 1];
>> G=[eye(11) p];
>> ht=vertcat(eye(4),p);
>> mod(G*ht,2)

ans =

     0     0     0     0
     0     0     0     0
     ..
     0     0     0     0

The error bit syndrome can then be computed for the FEC,

Obviously this is the same as \(H^t\) since \(I_{15}H^t=H^t\) where \(I_{15}\) is an identity matrix 15x15. Syndrome will point to the corresponding row of \(I_{15}\) for the correction. If the received code word, \(w\) is received withou error then \(wH^t=0\) otherwise, \(uH^t + eH^t = 0 + eH^t =s\) where \(s\) is the syndrome. The row of \(H^t\) corresponds to the row of \(I_{15}\). The most likely code word with the closest distance would then be the corresponding row of \(I_{15}\) with matching syndrome plus the received code word \(w\). In general, the t-error correcting code \((n,k)\) is capable of correctin \(2^{n-k}\) pattern. In this exercise, there will be 16 correctable patterns and they are the patterns of the identity matrix.

Using MATLAB to generate the input words to be encoded for all \(2^{11}\) possible values then encoded it with the \(G\) matrix following by 1 bit error simulation for error correction,

>> v=dec2bin(0:2^11-1)-'0';
>> u=mod(v*G,2);
>> mod(u(100,:)*ht,2)

ans =

    0     0     0     0

Simulate 1 bit error from one of the encoded words will result in syndrome of,

>> a=u(100,:);
>> a(1)=1

a =

     1     0     0     0     1     1     0     0     0     1     1     1     0     0     0

>> mod(a*Ht,2)

ans =

    1     0     0     1

This syndrome will correspond to the first row of \(I_{15}\), so the corrected code word would be,

>> mod(a(1:11) + I11(1,:),2)

ans =

     0     0     0     0     1     1     0     0     0     1     1

which is the same as the original unaltered test code word. This is also based on the fundamental assumption that bit error occurs independently and that the most likely error pattern is the one with the least weight. It is not always true in real life situation where errors can occur in burst and the level of complexity to FEC this type of error will increase. For this block code, the probability that the decoder commits the error is bounded by

where \(p\) is the transition probability of the channel, for example, if the reliability of the BSC is one bit error for every ten millions bits then \(p = 10^{-7}\).

The next step is to implement this simple FEC in verilog HDL using shift registers for the encoder and decoder following by synthesizing it into FPGA bitstream if the input data stream is the serialized bits stream. If the input data is in parallel block format, the parity bits or the redundant bits \(P_i\) can be calcuted from the 11 bit input word, \(v_{10}..v_0\) based on G,

to put the encoded data bits \(u\) is in its systematic form where its row vector,

The encoded words are the contatenation of the input word and the parity bits. The HDL implementation of this FEC exercise is Simple Cyclic Hamming FEC

There are many excellent text books and articles on this subject. Listed in the reference are only a few that I have. For EE, [CIT003] is a very well known text book on this subject.