{"id":3953,"date":"2021-11-05T04:38:44","date_gmt":"2021-11-05T04:38:44","guid":{"rendered":"http:\/\/www.raymaps.com\/?p=3953"},"modified":"2022-06-03T11:06:51","modified_gmt":"2022-06-03T11:06:51","slug":"hamming-codes","status":"publish","type":"post","link":"https:\/\/www.raymaps.com\/index.php\/hamming-codes\/","title":{"rendered":"Hamming Codes"},"content":{"rendered":"\n

We have\npreviously discussed modulation and demodulation in wireless communications,\nnow we turn our attention to channel coding. We know that in a wireless channel\nthe transmitted information gets corrupted due to noise and fading and we get\nwhat are called bit errors. One way to overcome this problem is to transmit the\nsame information multiple times. In coding terminology this is called a\nrepetition code. But this is not recommended as it results in reduced data rate\nand reduced spectral efficiency.<\/p>\n\n\n\n\n\n\n\n

In this post\nwe discuss Hamming (7,4) Code which transmits 4 information bits for every 7\nbits transmitted, resulting in a code rate of 4\/7. The 3 additional bits are\ncalled parity bits and these protect against single bit errors in the channel.\nThis is called a systematic code since after performing the coding operation\nthe information bits are preserved, parity bits are only appended to the\ninformation bits. <\/p>\n\n\n\n

At the\nreceiver we implement two decoding techniques namely syndrome decoding and\nmaximum likelihood decoding and compare the bit error rate with no coding case\n(BPSK modulation is assumed). In the first case syndrome is calculated at the\nreceiver, which should be all zero if no error has occurred in the\ntransmission. If a nonzero term appears in the syndrome then it means that an\nerror has occurred and a lookup table can be used to correct the error. It must\nbe noted that only single bit errors can be corrected using this technique\n(here dmin is 3 and t=(3-1)\/2). <\/p>\n\n\n\n

The reason\nthat this technique works is that the generator matrix at the transmitter is\northogonal to parity check matrix at the receiver, which is used in the\ncalculation of syndrome. Next, we consider maximum likelihood decoding or soft\ndecision decoding. This is a brute force method in which we search for the\ncombination of symbols that have the minimum distance from the received\nsymbols. This is done before the decision stage in the receiver as some\ninformation is lost in the decision stage. <\/p>\n\n\n\n

The second method described above is based on Euclidean distance rather than Hamming distance. Euclidean distance is calculated between the possible transmitted symbols and the received symbols whereas Hamming distance is calculated between the possible transmitted bits and received bits. As expected, maximum likelihood decoding performs much better than syndrome-based decoding which can detect only one bit error at a time. In fact, at low signal to noise ratio syndrome-based method is even worse than no coding case. <\/p>\n\n\n\n

\"\"
Parity Generation Table<\/figcaption><\/figure><\/div>\n\n\n\n
\"\"
Bit Error Rate for Coded and Uncoded Case<\/figcaption><\/figure>\n\n\n\n
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n%  ENCODING AND DECODING USING HAMMING CODE \n%  k is the number of message bits\n%  n is the number of encoded bits\n%  k\/n is the code rate\n%  Copyright 2020 RAYmaps\n%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\nclear all\nclose all\n \nk=4;\nn=7;\nm=round(rand(1,k));\n\nP=[1 0 1;\n   1 1 1;\n   1 1 0;\n   0 1 1];\nI=eye(k);\nG=[I,P];\nc=mod(m*G,2);\ncx=2*c-1;\n\nEb=1.0*(n\/k);\nEbNo=10;\nsigma=sqrt(Eb\/(2*EbNo));\ny=cx+sigma*randn(1,n);\nd=y>0;\nH=[P',eye(n-k)];\ns=mod(d*H',2);\n\nif s==([1 0 1])\n  d(1)=not(d(1));\nelseif s==([1 1 1])\n  d(2)=not(d(2));\nelseif s==([1 1 0])\n  d(3)=not(d(3));\nelseif s==([0 1 1])\n  d(4)=not(d(4));\nend\nber=sum(d(1:4)~=m)\/4;\n%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n<\/pre>\n\n\n\n
Note:<\/p>\n\n\n\n
  1. We have assumed BPSK modulation in the\nsimulations but any other modulation format can be easily incorporated. In\nreality channel coding provides the leverage to go higher modulation formats, resulting\nin higher spectral efficiency.<\/li>
  2. Single bit errors only need to be corrected for\nthe four possible erroneous message sequences. Errors in parity bits can be\nignored since they do not influence the bit error rate.<\/li>
  3. Hard decision decoding does not make full use of\nthe information available e.g. if we have BPSK modulation (s=+\/-1) there is no\ndifference between a +0.1 and +0.5 after a bit decision is made. But soft\ndecision decoding gives more weightage to +0.5 than +0.1.  <\/li><\/ol>\n","protected":false},"excerpt":{"rendered":"
    In this post we discuss Hamming (7,4) Code which transmits 4 information bits for every 7 bits transmitted, resulting in a code rate of 4\/7. The 3 additional bits are called parity bits and these protect against single bit errors in the channel. This is called a systematic code since after performing the coding operation the information bits are preserved, parity bits are only appended to the information bits. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[11,10],"tags":[34,132,230],"class_list":["post-3953","post","type-post","status-publish","format-standard","hentry","category-berp","category-chancod","tag-ber","tag-channel-coding","tag-hamming"],"_links":{"self":[{"href":"https:\/\/www.raymaps.com\/index.php\/wp-json\/wp\/v2\/posts\/3953","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.raymaps.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.raymaps.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.raymaps.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.raymaps.com\/index.php\/wp-json\/wp\/v2\/comments?post=3953"}],"version-history":[{"count":2,"href":"https:\/\/www.raymaps.com\/index.php\/wp-json\/wp\/v2\/posts\/3953\/revisions"}],"predecessor-version":[{"id":4270,"href":"https:\/\/www.raymaps.com\/index.php\/wp-json\/wp\/v2\/posts\/3953\/revisions\/4270"}],"wp:attachment":[{"href":"https:\/\/www.raymaps.com\/index.php\/wp-json\/wp\/v2\/media?parent=3953"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.raymaps.com\/index.php\/wp-json\/wp\/v2\/categories?post=3953"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.raymaps.com\/index.php\/wp-json\/wp\/v2\/tags?post=3953"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}