1 Star2 Stars3 Stars4 Stars5 Stars (6 votes, average: 4.00 out of 5)
Loading ... Loading ...
Print Print

Hamming (7,4) code with hard decision decoding

by Krishna Sankar on September 29, 2009

In previous posts, we have discussed convolutional codes with Viterbi decoding (hard decision, soft decision and with finite traceback). Let us know discuss a block coding scheme where a group of information bits is mapped into coded bits. Such codes are referred to as codes. We will restrict the discussion to Hamming codes, where 4 information bits are mapped into 7 coded bits. The performance with and without coding is compared using BPSK modulation in AWGN only scenario.

Hamming (7,4) codes

With a Hamming code, we have 4 information bits and we need to add 3 parity bits to form the 7 coded bits. The can be seven valid combinations of the three bit parity matrix (excluding the all zero combination) i.e. .

The coding operation can be denoted in matrix algebra as follows:

where,

is the message sequence of dimension ,

is the coding matrix of dimension ,

is the coded sequence of dimension .

Using the example provided in chapter eight (example 8.1-1) of Digital Communications by John Proakis , let the coding matrix be,

.

This matrix can be thought of as,

,

where,

is a identity matrix and

is a the parity check matrix.

Since an identity matrix, the first coded bits are identical to source message bits and the remaining bits form the parity check matrix.

This type of code matrix where the raw message bits are send as is is called systematic code.

Assuming that the message sequence is , then the coded output sequence is :

, where

,

,

.

The operator denotes exclusive-OR (XOR) operator.

 

Sl No m0 m1 m2 m3 p0 p1 p2
0 0 0 0 0 0 0 0
1 0 0 0 1 0 1 1
2 0 0 1 0 1 1 0
3 0 0 1 1 1 0 1
4 0 1 0 0 1 1 1
5 0 1 0 1 1 0 0
6 0 1 1 0 0 0 1
7 0 1 1 1 0 1 0
8 1 0 0 0 1 0 1
9 1 0 0 1 1 1 0
10 1 0 1 0 0 1 1
11 1 0 1 1 0 0 0
12 1 1 0 0 0 1 0
13 1 1 0 1 0 0 1
14 1 1 1 0 1 0 0
15 1 1 1 1 1 1 1

Table: Coded output sequence for all possible input sequence

Hamming Decoding

Minimum distance

Hamming distance computes the number of differing positions when comparing two code words. For the coded output sequence listed in the table above, we can see that the minimum separation between a pair of code words is 3.

If an error of weight occurs, it is possible to transform one code word to another valid code word and the error cannot be detected. So, the number of errors which can be detected is .

To determine the error correction capability, let us visualize that we can have valid code words from possible values. If each code word is visualized as a sphere of radius , then the largest value of which does not result in overlap between the sphere is,

where,

is the the largest integer in .

Any code word that lies with in the sphere is decoded into the valid code word at the center of the sphere.

So the error correction capability of code with distance is .

In our example, as , we can correct up-to 1 error.

Parity Check Matrix

For any linear block code of dimension, there exists a dual code of dimension . Any code word is orthogonal to any row of the dual code. For the chosen coding matrix , the dual code is,

.

It can be seen that modulo-2 multiplication of the coding matrix with the transpose of the dual code matrix is all zeros i.e

.

This dual code is also known as parity check matrix.

Maximum Likelihood decoding

A simple method to perform maximum likelihood decoding is to compare the received coded sequence with all possible coded sequences, count the number of differences and choose the code word which has the minimum number of errors.

As stated in Chapter 8.1-5 of Digital Communications by John Proakis, a more efficient way (with identical performance) is to use the parity check matrix .

Let the system model be,

, where

is the received code word of dimension ,

is the raw message bits of dimension ,

is the raw message bits ,

is the error locations of dimension .

Multiplying the received code word with the parity check matrix,
.

The term is called the syndrome of the error pattern and is of dimension . As the term , the syndrome is affected only by the error sequence.

Lets assume that the message sequence

.

The code output sequence is

Let us find the error syndrome for all possible one bit error locations.

 

Sl N0 c0 c1 c2 c3 c4 c5 c6
s0 s1 s2
0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 1 0 1
2 0 1 0 0 0 0 0 1 1 1
3 0 0 1 0 0 0 0 1 1 0
4 0 0 0 1 0 0 0 0 1 1
5 0 0 0 0 1 0 0 1 0 0
6 0 0 0 0 0 1 0 0 1 0
7 0 0 0 0 0 0 1 0 0 1

Table: Syndrome for all possible one bit error locations

Observations

1. If there are no errors (first row), the syndrome takes all zero values

2. For the one bit error, the syndrome takes one among the valid 7 non-zero values.

3. If we have more than one error locations, then also the syndrome will fall into one of the 8 valid syndrome sequence and hence cannot be corrected.

Simulation Model

The Matlab/Octave script performs the following

(a) Generate random binary sequence of 0′s and 1′s.

(b) Group them into four bits, add three parity bits and convert them to 7 coded bits using Hamming (7,4) systematic code

(c) Add White Gaussian Noise

(d) Perform hard decision decoding

(e) Compute the error syndrome for groups of 7 bits, correct the single bit errors

(f) Count the number of errors

(g) Repeat for multiple values of and plot the simulation results.

Click here to download

  Matlab/Octave script for computing BER with Hamming (7,4) systematic code with hard decision decoding (2.5 KiB, 6,342 hits)

BER plot for Hamming (7,4) code with hard decision decoding in AWGN

Figure: BER plot for Hamming (7,4) code with hard decision decoding in AWGN

Observations

1. For above 6dB, the Hamming (7,4) code starts showing improved bit error rate.

Reference

Digital Communications by John Proakis


D id you like this article? Make sure that you do not miss a new article by subscribing to RSS feed OR subscribing to e-mail newsletter. Note: Subscribing via e-mail entitles you to download the free e-Book on BER of BPSK/QPSK/16QAM/16PSK in AWGN.

{ 54 comments… read them below or add one }

domain September 30, 2014 at 8:05 am

With havin so much content do you ever run into any issues
of plagorism or copyright infringement? My site has
a lot of unique content I’ve either authored myself or outsourced but it appears a lot of it is popping
it up all over the web without my permission. Do you know any methods to help stop content from being ripped off?
I’d truly appreciate it.

Reply

corporate gifts singapore September 21, 2014 at 8:00 am

They know the merchandise by the reputation of the
product. Struggle no more, Canadian company Geekware have a wide
range of irresistible gifts that geeks will give their PCs for,
and what’s more, they’re all environmentally friendly.
Corporate gift ideas are freely and widely available throughout.

Reply

Sanora July 7, 2014 at 3:44 pm

Exactly ѡhy does nott desktop efer mentfion perfect request or ϳust higgh bay led lights!

Reply

jaspreet March 21, 2013 at 9:13 pm

plz help me for logic for soft hamming codes

Reply

Krishna Sankar March 22, 2013 at 5:47 am
amir mehdi March 19, 2013 at 9:28 pm

it is exellent.

Reply

Olaolu March 11, 2013 at 5:07 pm

Hi Krishna

Nice work. Please can you reload the code again for Hamming (7,4) code with hard decision decoding. Because the matlab/octave code link is given an error message that it does not exist. Thank you

Reply

Krishna Sankar March 11, 2013 at 7:50 pm

@Olaolu: Thanks. Fixed the download error – please check now.

Reply

sakis January 20, 2013 at 4:31 am

krishna thanks for this wonderdul blog!Is it possible a post about Reed-Solomon codes…?will be a perfect add to coding issues discussed here.Again thnks!

Reply

YH December 24, 2012 at 12:13 am

I don’t know how to determine bitIdx.
I’m making a code for (23,12)Golay code, and in matlab, “??? Index exceeds matrix dimensions.” this error message coming up. Please help me.
Thanks.

Reply

Krishna Sankar December 25, 2012 at 5:54 am

@YH: The variable bitIdx stores the index of the bit to correct. i.e if syndrome is 1 –> 7th bit in error and so on

Reply

Conor November 16, 2012 at 6:33 am

Hi Krishna,

I understand how you use this line: bitIdx = [7 6 4 5 1 3 2].’; but I am trying to write similar code for a 5×10 regular parity-check matrix where each variable node is connected to 2 check nodes and I don’t know how implement the “bitIdx” vector when there are 2 or more bits in error for a certain syndrome. Do you have any ideas?

Regards,
Conor

Reply

Krishna Sankar November 18, 2012 at 7:03 am

@Conor: Well, one can make a decimal number constructed from the two bit location to be flipped. And from the decimal number, get the bit locations. Anyhow, its a matter of coding choice which one wants.

Reply

Jane September 30, 2012 at 7:50 am

Hi krishna,
Actually, I now know the answer for my second question above. But, since I want to calculate FER (the percentage of codewords in error) as well I can’t flip the parity bits. Is the anyway out to avoid indexing with zero.
Also, when I compare your simulation curve with Matlab generated BER (bercoding(0:10,’Hamming’,'hard’,7)), there is some small difference there. Matlab gives better BER?. Why? Is there a difference?
One last question, We’re treating all error patterns as if they all were of weight one. This way if an error of another weight happens then aren’t we increasing the BER by treating it like it was only one bit in error?

Thank you.

Reply

Krishna Sankar October 5, 2012 at 5:22 am

@Jane: My replies
a) Oh, i will check my numbers against bercoding(0:10,’Hamming’,’hard’,7). Am not expecting any delta (unless ofcourse, there are any hidden bugs in the simulation model) :-)
b) For every one bit error, the syndrome takes one of the 7 non-zero values. If there are more than one-bit error, this code cannot detect.

Reply

Jane September 29, 2012 at 11:26 pm

Hi Krishna,
What if I form my parity check matrix in a way so that the decimal value of syndrome be equal to the location of the bit in error? Like this:
H = [0 0 0 1 1 1 1;0 1 1 0 0 1 1 ;1 0 1 0 1 0 1]
Can I do that?
Could you explain this line as well please:
syndromeDec(find(syndromeDec==0)) = 1;
Why you’re assuming that if no error has happened then we should flip the 7th coded bit?
Also, if we want to calculate the error rate for the codewords (FER) then I think we should count in the errors in parity bits too. Right?

Thank you

Reply

Krishna Sankar October 5, 2012 at 5:27 am

@Jane: My relies
a) I think one can do that. The underlying goal is to figure out the error location.
b) Was looking at the comment, and it states something about preventing simulation crash.
syndromeDec(find(syndromeDec==0)) = 1; % to prevent simulation crash, assigning no error bits to parity
I vaguely recall about flipping the parity bit, but it does not have any impact on the BER simulation because the parity bits are anyhow removed prior to BER computation.

If you wish, you can remove that piece of code and tailor it to your needs.

Reply

Kamal September 21, 2012 at 2:15 pm

Hey bro can you please upload a Matlab simulation for (15,11) Hamming coding to a BPSK modulated signal which is transmitted in AWGN channel.

Reply

Krishna Sankar September 22, 2012 at 6:04 am

@Kamal: Will keep that in the to-do

Reply

Kamal September 22, 2012 at 10:53 am

thank you very much bro… it’s a big help because I could not find any code to do this thing :) thank you again… :)

Reply

phongk85 April 14, 2012 at 8:53 am

Dear Krishna Sankar!
In Mulation section, we use OPQSK then how we can do?
Thanks!

Reply

Krishna Sankar April 16, 2012 at 5:18 am

@phomgk85: Did you mean you want to use OQPSK with Hamming code (instead of BPSK)?

Reply

phongka85 April 19, 2012 at 9:49 pm

YEAH.
i finding how estimate ber over O-QPSK and AWGN channel using haming 7,4 or hamming 15, 11?

Reply

Krishna Sankar April 23, 2012 at 5:26 am

@phongka85: I have not discussed O-QPSK explicitly in the posts…the closest which I came to is MSK
http://www.dsplog.com/2009/06/16/msk-transmitter-receiver/

Reply

Justin March 9, 2012 at 1:17 am

Hi,
can anyone please help how to do the program for BPSK coded system (gaussian channel noise) using ML decision at the decoding part.

Reply

Krishna Sankar March 12, 2012 at 4:51 am

@Justin: By ML, I reckon you are referring to a soft decision brute force search. I am in the process of finishing up the write up for that. Will have a post on that this week

Reply

charan langton March 16, 2011 at 10:15 pm

Hi Krishna,

I like the way you have put together this website. Very nice. May I ask what program you use to create you math pages.
I want to convert my site to a blog style as well.Pperhaps you can suggest someone to convert my website?

Thanks, C. Langton

Reply

Krishna Sankar April 6, 2012 at 6:34 am

@charan:
Thanks much for the kind words. I refer to http://www.complextoreal.com a lot for my studies.

For the blogging platform, used Wordpress and purchased Thesis theme for the styling. The equations were possible thanks to Mimetex
http://www.forkosh.com/mimetex.html

Reply

waheed June 10, 2010 at 9:39 pm

Hi ,

is any boduyhas workd or ca nhelp me on Linear Block code (15 ,11) using Viterbi decoding ..i want to wrtie a matlab program for it but i am facing some problems in the long and complex trellis stucture …please email to me if somebody can help..thanks

Reply

Pawelitel June 10, 2010 at 1:24 pm

//my implementation in c (not be severely)
//Hamming(7,4) code in BAWGN channel with Hard desigion
//The result is a table of EbNo vs BER
//all worked
//Powered by Pawelitel in 2010

#include
#include
#include

//white gaussian noise
double wgn(void)
{
float PI=3.14159265358;
static int _sw = 0;
static double _t, _u, _x;
if ( _sw == 0 )
{
_sw = 1;
_x = (1.0 / (RAND_MAX + 1.0)) * rand();
while (!_x)_x = (1.0 / (RAND_MAX + 1.0)) * rand();
_t = sqrt(-2 * log(_x));
_u = 2.0 * PI * ((1.0 / (RAND_MAX + 1.0)) * rand());
return _t*cos(_u);
}
else
{
_sw = 0;
return _t*sin(_u);
}
}

int main(int argc, char **argv) {

const int Hamming74EncodeTable[16] = {0 ,14 ,21 ,27 ,35 ,45 ,54 ,56 ,71 ,73 ,82 ,92 ,100 ,106 ,113 ,127};
const int Hamming74DecodeTable[128] = {0 ,0 ,0 ,4 ,0 ,2 ,1 ,8 ,0 ,9 ,1 ,3 ,1 ,5 ,1 ,1 ,0 ,2 ,10 ,3 ,2 ,2 ,6 ,2 ,7 ,3 ,3 ,3 ,11 ,2 ,1 ,3 ,0 ,4 ,4 ,4 ,12 ,5 ,6 ,4 ,7 ,5 ,13 ,4 ,5 ,5 ,1 ,5 ,7 ,14 ,6 ,4 ,6 ,2 ,6 ,6 ,7 ,7 ,7 ,3 ,7 ,5 ,6 ,15 ,0 ,9 ,10 ,8 ,12 ,8 ,8 ,8 ,9 ,9 ,13 ,9 ,11 ,9 ,1 ,8 ,10 ,14 ,10 ,10 ,11 ,2 ,10 ,8 ,11 ,9 ,10 ,3 ,11 ,11 ,11 ,15 ,12 ,14 ,13 ,4 ,12 ,12 ,12 ,8 ,13 ,9 ,13 ,13 ,12 ,5 ,13 ,15 ,14 ,14 ,10 ,14 ,12 ,14 ,6 ,15 ,7 ,14 ,13 ,15 ,11 ,15 ,15 ,15};

float count=pow(10,6);//number of tests
float countfrom=0,countto=count, countstep=1,c=0;
float noiseRootMeanSquare;
float S=1,//signal level
SNR,//energy per signal
EbNo,//energy per bit
simBER=-11.0;
int i,j,l,nErr=0,errorBits,s;
float fin;
const int numberOfBits=4;
const int numberOfCodedBits=7;
int inUncoded,inCoded,outUncoded,outCoded;
float syndroms[numberOfCodedBits];

///compute BER
for ( c=countfrom; c<countto; c+=countstep)
{
SNR=11-c/10.;///SNR from 11dB down with step 1/10 dB
noiseRootMeanSquare=pow(10,-SNR/20.);
EbNo=simBER=nErr=0;
for ( i=0; i<count; i++ )
{
inUncoded=rand()%16;
inCoded=Hamming74EncodeTable[inUncoded];

outCoded=0;
for ( j = 0; j < numberOfCodedBits; j++ )
{
s=(inCoded&(1<0;/// 0 или 1
syndroms[j]=2*s-1+1/sqrt(2)*noiseRootMeanSquare*wgn();///BAWGN
outCoded ^=(syndroms[j]>0)<<j;//hard decision
}
outUncoded=Hamming74DecodeTable[outCoded];

errorBits= inUncoded ^ outUncoded;
if (errorBits)
for ( l=0; l<numberOfBits; l++ )
if (errorBits&(1<<l))
nErr++;
}
SNR = 20*(log10(S/noiseRootMeanSquare));
EbNo = SNR – 10*log10(numberOfBits/float(numberOfCodedBits));
printf("%f ",EbNo);
simBER=log10(nErr/float(count*numberOfBits));
printf("%f\n",simBER);

if (EbNo<0)break;
}
return 0;
}

Reply

Krishna Sankar June 14, 2010 at 6:21 am

@Pawelitel: The above code works as intended? Great. People who needs C code can take this :)

Reply

mira January 21, 2010 at 12:18 pm

Mr. Krishna ,
always thank you for very helpful posts. sorry for question not related to post. i am new in this field,especially in mathlab. so t is the best way to learn writing code in Mathlab. if you have any sugesstion? any suggestion will be appreciated.
thanks you

Reply

victor December 15, 2009 at 1:19 pm

Hi Krishna,
I would like to Hamming code (7,4) into qpsk modulation and demodulation system? what should I do? thanks.

Reply

Krishna Sankar December 22, 2009 at 5:50 am

@victor: Well, that should be simple.
You can group two coded bits into a QPSK, add awgn noise, demap into bits, then hamming decode
You can use this code as reference for qpsk mapping and demapping
http://www.dsplog.com/2007/11/06/symbol-error-rate-for-4-qam/

Reply

thilini December 10, 2009 at 6:48 pm

Plz help me
Actually I want to know the steps calculate hamming codes use hamming 7/4 mechanism

Reply

Krishna Sankar December 11, 2009 at 6:15 am

@thilini: Hopefully, this post discuss all the details which you require. Good luck.

Reply

linda December 8, 2009 at 7:28 am

I’m creating a 15 11 hamming code and I just want to know how you chose bitIdx=[7 7 4 7 1 3 2] for your 7 4 hamming code. I desperately need help. THANK YOU SO MUCH!

my
h=[1 0 0 1;1 0 1 1;1 1 1 1; 0 1 1 1;1 1 1 0;0 1 0 1; 1 0 1 0; 1 1 0 1;0 0 1 1;0 1 1 0; 1 1 0 0];
ht=[h; eye(4)];
g=[eye(11) h];
synRef = [9 11 15 7 14 5 10 13 3 6 12];

Reply

Krishna Sankar December 10, 2009 at 5:31 am

@linda: Instead of giving you the answer, may I give you the steps. I guess, it should be easy for you to figure this out.
For each coded output sequence c = mG, try multiplying with the parity check matrix H^T.
For no errors in c, the operation mGH^T = all zeros.
Introduce one bit error in c, the operation mGH^T will result in a non-zero matrix. Observe the location of the non-zero element and use it find out which bit is in error.

Good luck.

Reply

Saiful December 4, 2009 at 4:45 pm

hy sir please could you send me hard decession decoding with orthogonal signals for linear block code

Reply

Krishna Sankar December 7, 2009 at 5:13 am

@Saiful: Sorry, I do not have codes for that.

Reply

New_Student November 11, 2009 at 12:31 pm

Hi Krishna,

would you please help me in writing the same code using matlab functions?

Thanks

Reply

Krishna Sankar November 13, 2009 at 5:34 am

@New_Student: Sorry, I do not have the Matlab functions. It should be much much easier to write it that way, no? Good luck.

Reply

Richard November 5, 2009 at 12:47 am

I am wondering how can i use your code using MATLAB function for Hamming to find BER and final graph?
[ encoded_msg=encode(tmsg,7,4,'hamming/binary')
decodeed_msg=decode(rmsg,7,4,'hamming/binary') ]

I think error correction is taken care by matlab if we use this functions and so no need for g, h and synd. Am i right? Can you tell me more about any need of preshaping the binary matrix before encoding? after decoding?

Why didn’t you use MATLAB functions in the first place?
Sorry for many questions but I like your work and I know you have all the answers.

Thanks for your wonderful work and tons of help to me and all.

God bless you.

Reply

Krishna Sankar November 8, 2009 at 8:55 am

@Richard: If we use matlab functions, then there is no fun in learning … ;)
I try to use only the most basic matlab functions and then code the rest of the blocks using those basic set.

Reply

Tahmid October 14, 2009 at 11:21 am

Thanks for the clarification Krishna,

Have you done the block coding simulation using RS codes in matlab? Can you point me to example code?

Reply

Krishna Sankar October 15, 2009 at 5:31 am

@Tahmid: Sorry, not done RS codes till date.

Reply

Wig October 13, 2009 at 2:06 pm

sorry I can’t understand a row of your program code:
bitIdx = [ 7 7 4 7 1 3 2].’; 7 7 4 7 1 2 3 ???
↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
Could u tell me why do that,please~? my brain can’t figure out it~
thanks!!!

Reply

Krishna Sankar October 15, 2009 at 5:30 am

@Wig: Its related to the syndrome and the location of the bit which is in error. For eg, with
synRef = [ 5 7 6 3 ];
bitIdx = [ 7 7 4 7 1 3 2].’;

With syndrome of 5, the 1st bit is in error
With syndrome of 7, the 2nd bit is in error
With syndrome of 6, the 3rd bit is in error
With syndrome of 3, the 4th bit is in error

The rest of the incides we can ignore, as we do not count the errors in parity bits for our raw BER computation. Helps?

Reply

Linda December 7, 2009 at 3:12 am

I understand
synRef = [ 5 7 6 3 ];

With syndrome of 5, the 1st bit is in error
With syndrome of 7, the 2nd bit is in error
With syndrome of 6, the 3rd bit is in error
With syndrome of 3, the 4th bit is in error

but I do not understand how you got this from synRef
bitIdx = [ 7 7 4 7 1 3 2].’;
Could you please explain that? Thanks

Reply

Krishna Sankar December 7, 2009 at 5:38 am

@Linda: The variable bitIdx stores the index of the bit to correct. i.e if syndrome is 1 –> 7th bit in error and so on
Am not using synRef in the simulation (maybe I forgot to remove it while doing the code cleanup)

Reply

sophia March 27, 2012 at 12:47 am

Hi Krishna,
Could you explain more about the variable bitIdx?
Why if syndrome is 1 –> 7th bit in error ?
Could you give more examples like if syndrome is 6, what the bitIdx will be?
Thanks.

Tahmid October 12, 2009 at 1:41 pm

Hi Krishna,

If you were to do this over Rayleigh channel you would the following?

1. multiply message with
h = 1/sqrt(2)*[randn(size(cip)) + j*randn(size(cip))];
2. then divide the faded signal by h
3. demodulate

Reply

Krishna Sankar October 13, 2009 at 5:01 am

@Tahmid: In general yes. To be more precise:
1/ Generate random bits
2/ Code as per (7,4) Hamming code
3/ Convert to constellation symbols
4/ Multiply with channel h and add noise (awgn)
5/ Equalize at the receiver by dividing by h
6/ Do hard decision decode and find received coded bits
7/ Do Hamming decode and find received raw bits.

Good luck.

Reply

Krishna Sankar March 29, 2012 at 5:36 am

@sophia: The bitIdx is used to identify the bit to correct based on the syndrome value. If syndrome is 6, the bit in error is 3. The full list is given in “Table: Syndrome for all possible one bit error locations”

Reply

Leave a Comment

{ 1 trackback }

Previous post:

Next post: