EXTENDED GOLAY CODE

 

                            DEFINITION AND ALGORITHM

 

First we create the full cycle permutation matrix P:

 

echo on; clc

 

I1 = eye(10); Z1=zeros(1,10);P=[Z1 1; I1 Z1'];

 

Using the vector x, we define the matrices B, G, and H.

 

x = [1 1 0 1 1 1 0 0 0 1 0 ];

 

for i = 1:11, B1(i,1:11)=[x*P^(i-1)];end;

 

J1 = ones(11,1); B = [B1 J1 ; J1' 0]

 

B =  1     1     0     1     1     1     0     0     0     1     0     1

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

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

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

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

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

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

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

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

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

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

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

 

I2 = eye(12); G =[I2 B]; H =[I2; B]; J2 = ones(12,1);

 

The algorithm is explained with the help of the following examples.

 

Example a.

 

The received codeword:

 

wa1 = [1 0 1  1 1 1  1 0 1  1 1 1] ; wa2=[0 1 0  0 1 0  0 1 0  0 1 0];

 

wa = [wa1 wa2]

 

wa =  Columns 1 through 12

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

      Columns 13 through 24

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

 

STEP 1.

Compute the syndrome:

 

sa = rem(wa*H,2)

 

sa =  1     0     0     0     0     0     0     0     0     0     0     1

 

STEP 2.

Finding the weight of the syndrome:

 

wta = sa*J2

 

wta =  2

 

STEP 3.

Since the weight of sa is less than or equal to 3, the error pattern is:

 

ua = [sa zeros(1,12)]

 

ua =  Columns 1 through 12

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

      Columns 13 through 24

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

 

va = rem(wa +ua,2)

 

va = Columns 1 through 12

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

     Columns 13 through 24

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

 

The codeword sent was:

 

va0 = va(1:12)

 

va0 =  0     0     1     1     1     1     1     0     1     1     1     0

 

Example b.

 

The received codeword:

 

wb1 = [0 0 1  0 0 1  0 0 1  1 0 1] ; wb2 = [1 0 1  0 0 0  1 0 1  0 0 0];

 

wb = [wb1 wb2];

 

STEP 1.

Compute the syndrome:

 

sb = rem(wb*H,2)

 

sb = 1     1     0     0     0     1     0     0     1     0     0     1

 

STEP 2.

Finding the weight of the syndrome: 

 

nb = sb*J2

 

nb =  5

 

STEP 3.

Since the weight of sb is greater than 3, we compute the matrix Rb

 

R = J2*sb; Rb = rem(R + B)

 

STEP 4.

Find the weight of each row of Rb

 

nrb =(Rb*J2)'

 

nrb =  4     6     8     4     2     8     6     6     6     6     6     8

 

STEP 5.

The weight of the fifth row is less than or equal to 2, so the error pattern is:

 

ub = [rem(Rb(5,1:12),2) I2(5,1:12)]

 

ub = Columns 1 through 12

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

     Columns 13 through 24

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

 

vb = rem(wb +ub,2)

 

vb = Columns 1 through 12

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

     Columns 13 through 24

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

 

The message sent was:

 

vb0 = vb(1:12)

 

vb0  =  0     0     1     0     0     1     0     1     1     1     1     1

 

Note. Since the algorithm is designed for IMLD and G corrects all the error patterns of weight at most 3, only one row of Rb may have weight less than or equal to 3.

 

Example c.

 

The received codeword:

 

wc1 = [1 1 1  0 0 0  0 0 0  0 0 0] ; wc2 = [0 0 0  1 0 1  0 0 0   1 0 1];

 

wc = [wc1 wc2];

 

STEP 1.

Compute the syndrome:

 

sc = rem(wc*H,2)

 

sc = 1     1     0     0     0     0     0     1     0     1     0     1

 

STEP 2.

Find the weight of the syndrome: 

 

nc = sc*J2

 

nc = 5

 

STEP 3.

Since the weight of sc is greater than 3, we compute the matrix Rc

 

R = J2*sc; Rc = rem(R+ B)

 

STEP 4.

Find the weight of each row of Rc

 

nrc =(Rc*J2)'

 

nrc =  4     8     4     4     4     4     8     6     6     6     8     8

 

STEP 5.

All the rows of Rc have weight greater than 2. We need to find the second syndrome:

 

sc2 = rem(sc*B,2)

 

sc2 =  0     0     0     0     0     0     0     1     1     1     0     0

 

STEP 6.

Compute the weight of the second syndrome: 

 

nc2 = sc2*J2

 

nc2 = 3

 

STEP 7.

The weight of sc2 is less than or equal to 3. The error pattern is:

 

uc = [zeros(1,12) sc2]

 

uc = Columns 1 through 12

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

     Columns 13 through 24

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

 

vc = rem(wc+uc,2)

 

vc = Columns 1 through 12

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

     Columns 13 through 24

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

 

The codeword sent was:

 

vc0 = vc(1:12)

 

vc0 = 1     1     1     0     0     0     0     0     0     0     0     0

 

Example d.

 

The received codeword:

 

wd1 = [0 0 0   1 1 1  0 0 0   1 1 1]; wd2 = [0 1 1  0 1 1  0 1 0  0 0 0];

 

wd =[wd1 wd2];

 

 

 

STEP 1.

Compute the syndrome:

 

Sd = rem(wd*H,2)

 

sd = 1     0     1     1     0     1     1     0     1     0     1     0

 

STEP 2.

Finding the weight of the syndrome: 

 

nd = sd*J2

 

nd = 7

 

STEP 3.

Since the weight of sd is greater than 3, we compute the matrix Rd

 

R = J2*sd; Rd = rem(R + B)

 

STEP 4.

We find the weight of each row of Rd

 

nrd = (Rd*J2)'

 

nrd = 8     4     8     6     6     8     4     8     8     4     6     4

 

STEP 5.

All the rows of Rd have weight greater than 2. We need to find the second syndrome:

 

sd2 = rem(sd*B,2)

 

sd2 = 1     1     1     0     0     1     1     1     1     1     0     1

 

STEP 6.

Finding the weight of the second syndrome: 

 

nd2 = sd2*J2

 

nd2 = 9

 

STEP 7.

Since the weight of sd2 is greater than 3, we compute the matrix Rd2

 

R = J2*sd2; Rd2 = rem(R+ B)

 

nrd2=(Rd2*J2)'

 

nrd2 = 6     8     6     2     4     6     6     4     6     4     6     4

 

STEP 8.

Since the weight of the fourth row is less than or equal to 2, the error pattern is:

 

ud = [I2(4,1:12) rem(Rd2(4,1:12),2) ]

 

 

 

ud = Columns 1 through 12

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

     Columns 13 through 24

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

 

vd = rem(wd+ud,2)

 

vd = Columns 1 through 12

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

     Columns 13 through 24

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

 

The codeword sent was:

 

vd0 = vd(1:12)

 

vd0 = 0     0     0     0     1     1     0     0     0     1     1     1

 

Example e.

 

The received codeword:

 

we1 = [1 1 1  1 1 1  0 0 0 0 0 0] ; we2 = [1 1 1  0 0 0  1 1 1  0 0 0];

 

we =[we1 we2];

 

STEP 1.

Compute the syndrome:

 

se = rem(we*H,2)

 

se = 1     0     0     0     1     0     0     1     0     0     1     0

 

STEP 2.

Find the weight of the syndrome: 

 

ne = se*J2

 

ne = 4

 

STEP 3.

Since the weight of se is greater than 3, we compute the matrix Re

 

R = J2*sd; Re = rem(R + B)

 

STEP 4.

Find the weight of each row of Re

 

nre =(Re*J2)'

 

nre = 7     5     7     9     5     3     9     7     7     7     7     7

 

STEP 5.

All the rows of Re have weight greater than 2. We need to find the second syndrome:

 

se2 = rem(se*B,2)

 

se2 = 0     1     0     1     1     0     1     0     0     0     0     0

 

STEP 6.

Find the weight of the second syndrome: 

 

ne2 = se2*J2

 

ne2 = 4

 

STEP 7.

Since the weight of se2 is greater than 2, we compute the matrix Re2

 

R = J2*se2; Re2 = rem(R + B)

 

nre2 = (Re2*J2)'

 

nre2 = 5     7     7     7     9     7     7     9     3     7     5     7

 

STEP 8.

All the rows of Re2 have weight greater than 2. This time we request retransmission