ASSIGNMENT ON

HADAMARD CODE

FOR

SPREAD SPECTRUM TECHNIQUE AND MULTIPLE

ACCESS

SUBMITTED BY:

BIKASH RANJAN RAM (MEEC/1039/2010)

TEJASWETA KUMARI (MEEC/1037/2010)

BIRLA INSTITUTE OF TECHNOLOGY,MESRA

INTRODUCTION:

The Hadamard code, named after Jacques Hadamard, is a system used for signal error detection
and correction . It is one of the family of codes. Especially for large n it has a poor rate but it is
capable of correcting many errors. Hadamard codes can be considered as a special case of Reed–
Muller codes. In particular, first order Reed–Muller code are equivalent to Hadamard codes.

Construction

The code is based on Hadamard matrices. If H is a Hadamard matrix of order 2n the codewords
are constructed by taking the rows of H and −H as codewords, where each −1 is replaced by 0. In
this way 2n + 1 code words are constructed that each have a length of 2n. Since the rows of a
Hadamard matrix are orthogonal the minimum distance is 2n - 1. In this way a code is
constructed.

The code can also be constructed by creating the parity-check matrix which consists of all 2n − 1
vectors containing an odd number of 1s, or by using a recursive encoding process.

Decoding

The code has minimum distance 2n − 1 and hence can correct at most t = 2n − 2 − 1 errors. The
algorithm below achieves this.

When a code word is received it is first transformed to a 1/−1 vector v by changing all 0s to −1.
Compute (v HT). The entry with the maximum absolute value corresponds to the row taken as a
code word. If it is positive the code word came from H, if it is negative the code word came from
−H.

Proof: If there were no errors the product (v HT) would consist of only zero's and one entry of +/
−2n. If there are errors in v then, in absolute value, some of the zeros become larger and the
maximum becomes smaller. Each error that occurs can change a zero with 2. So the zeros can
become at most 0 + 2t = 2n − 1 − 2. The maximum can decrease at most to 2n − 2t =
2n − 2n − 1 + 2 = 2n − 1 + 2. So the maximum that points to the correct row will always be
larger in absolute value than the other values in the row.
Hadamard Codes:
Take the 4m by 4m Sylvester-Hadamard matrix H4m and -H4m and change all the -1
entries to 0's.Here is how to obtain them:

where J4m is the 4m by 4m matrix whose entries are all ones . This gives us binary words

of length 4m.The binary codes formed by using 8m rows of H^4m and H^’4m

are called Hadamard codes .Here is a Hadamard code of order 16 using H8 = H2 *H2 * H2:

A generator may be the matrix:

Now by the properties of Hadamard matrices ,a Hadamard code is a [4m,2m,2m] linear Code
and it will correct any error pattern of weight (m-1).

Note that in order to change b H^4m into H4m or H^’4m into -H4m we proceeded as follows:
Hadamard Decoding Algorithm:
By using the fact that

and Theorem1,we use a simple scheme to decode any received word W^.

• Step1. A received signal W^ ,i.e. a sequence of 4m zeros and ones ,is first changed into
its +_1 form w (by changing each 0 to -1)as follows: w =2W^-h1:

• Step2. Compute s = wH4m.

• Step3. If the received word b w is a codeword, then there are no errors and the syndrome
s = w*H4m will be either §4mek.

• Step4. In the presence of errors, s will not be +_4mek, but if the number of error is at
Most7 then according to Theorem1, the absolute value of the largest component may not
decrease below 2m+4 and the absolute value of other components May decrease up to
2m-2. Thus the position of entry in s = w * H^t4m with the largest absolute value will
tell us which row of H4m or -H4m (if it is negative)was Transmitted .

• Step5. Too many errors, Impossible to decode W^.

Remark. While this is the actual algorithm used to decode the Mariner9 signals, it is a bit slow
from the computational point of view (requiring 322 multiplications and the corresponding
additions for each codeword), so a number of computational tricks are employed to reduce the
actual computation to less than 1/3 of what the algorithm calls for.
Examples.

Consider the Hadamard code C4m = C8,then

Corrects any single error pattern.

a. Suppose W^ =11000011 is the received word, then

Step1. w =2 W^-h1 =(1; 1;-1;-1; -1;-1; 1; 1).

Step2. s = wH8 =(0; 0; 0; 0; 0; 0; 8; 0).

Step3. The seventh component of s =8e7 is the largest component, which implies that there is no
error. Thus

v = h7 =(1; 1;-1;-1; -1;-1; 1; 1) and b v ´ 2h1 - v mod 3=11000011:

b. Suppose b w =10111010 is the received word, then

Step1. w =2W^ - h1 =(1;-1; 1; 1; 1;-1; 1;-1).

Step2. s = wH8 =(2; 6;-2; 2; 2;-2;-2; 2).

Step4. The second component of 6 ¸ 4m - 2=6 is the largest component, thus

v = h2 =(1;-1; 1;-1; 1;-1; 1;-1) and b v ´= 2h1 -v mod 3=10101010:

c. Suppose b w =00011010 is the received word, then

Step1. w =2 W^ - h1 =(-1;-1;-1; 1; 1; 1; 1; 1).

Step2. s = wH8 =(2; 2;-2;-2;-6; 2;-2;-2).

Step4. The ¯fth component of s is -6 is the largest component in absolute value and

j- 6j =6 ¸ 8 -2=6, thus

v = -h5 = (-1;¡1;-1;-1; 1; 1; 1; 1) and b v ´ 2h1 - v mod 3=00001111:

d. Suppose b w =11111100 is the received word, then

Step1. w =2 b w ¡ h1 =(1; 1; 1; 1; 1; 1;-1;-1).

Step2. s = wH8 =(4; 0; 0; 4; 4; 0; 0;-4).

Step5. Since 4 < 4m - 2=6, there are too many errors in order for us to decode.
Error correction using c:-
#include<stdio.h>
#include<conio.h>
#include<math.h>
void main()
{
int W[8],i,j,h[8][8],h1[8],z[8],s[8],o[8],k,d,b,m,y;
printf("enter hadamard matrix for 8m");
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
scanf("%d",&h[i][j]);
}
}
printf("hadamard code is\n");
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
printf("%d",h[i][j]);
}
printf("\n");
}
printf("\nfrom given hadamard matrix we get h1\n");
i=0;
for(j=0;j<8;j++)
{
h1[j]=h[i][j];
}
for(i=0;i<8;i++)
{
printf("%d",h1[i]);
}
printf ("\nenter the received bits"); //receiving
for(i=0;i<8;i++)
{
scanf("%d",&W[i]);
}
for(i=0;i<8;i++)
{
printf("%d",W[i]);
}
printf("\nwe get z= 2*W-h1\n");
for(i=0;i<8;i++)
{
z[i]=2*W[i]-h1[i];
}
for(i=0;i<8;i++)
{
printf(" %d",z[i]);
}
printf ("\nsyndrome\n");
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
s[i]=0;
for(k=0;k<8;k++)
{
s[i]=s[i]+(W[i]*h[k][j]);
}
}
}

for (i=0;i<8;i++)
{
printf(" %d",s[i]);
}
printf("\n"); //checking
d=0;
for(i=0;i<8;i++)
{
if(d<s[i]*s[i])
{
d=s[i]*s[i];
y=i;
}
else
{
m=sqrt(d);
goto out;
}
}

out:
printf("largest component position =%d",i);
printf(" largest component= %d",m); //checked
 printf("\n%d",y);
if(m>=8-2)
{
printf("\nerror can be correct");
printf("\noriginal word will be%d row of hadamard matrix",y);
i=y;
for(j=0;j<8;j++)
{
o[j]=h[i][j];
}
goto output;
}
else
printf("impossible");
output:
for(i=0;i<8;i++)
printf("%d",o[i]);

}
Output:

enter hadamard matrix for 8m

hadamard code is
11111111
1 -1 1 -1 1 -1 1 -1
1 1 -1 -1 1 1 -1 -1
1 -1 -1 1 1 -1 -1 1
1 1 1 1 – 1 -1 -1 -1
1 1 1 1 -1 -1 -1 -1
1 -1 1 -1 -1 1 -1 1
1 1 -1 -1 -1 -1 1 1
1 -1 -1 1 -1 1 1 -1
from given hadamard matrix we get h1
11111111
enter the received bits
10111010
we get z= 2*W-h1
1 1 -1 1 -1 1 -1 -1
Syndrome
2 6 -2 2 2 -2 -2 2
Largest component 6
Largest position 2
error can be correct
noriginal word will be 2 row of hadamard matrix
1 -1 1 -1 1 -1 1 -1
10101010