CCS C Software and Maintenance Offers
FAQFAQ   FAQForum Help   FAQOfficial CCS Support   SearchSearch  RegisterRegister 

ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

CCS does not monitor this forum on a regular basis.

Please do not post bug reports on this forum. Send them to support@ccsinfo.com

Hamming code example

 
Post new topic   Reply to topic    CCS Forum Index -> Code Library
View previous topic :: View next topic  
Author Message
evsource



Joined: 21 Nov 2006
Posts: 129

View user's profile Send private message

Hamming code example
PostPosted: Thu Jan 11, 2007 12:57 pm     Reply with quote

I was looking for an example yesterday on Hamming codes. I found this post:

http://ccsinfo.com/forum/viewtopic.php?t=10349&highlight=hamming&sid=345946a0a80f0abe61e57a1b46b2d028

It was really helpful. I modified the code a little, and thought I'd share the code (with formatting intact):

Code:

BYTE codeToData (BYTE code);
BYTE correctCode(BYTE code);
BYTE decode(BYTE code);
BYTE dataToCode(BYTE data);

/* struct for Hamming(8,4)
     Hamming codes from http://en.wikipedia.org/wiki/Hamming%287%2C4%29 */
struct {
     int nData; // 4-bit data (0 to 15), bytes will be handled nibble-by-nibble
     BYTE nCode; // 7-bit Hamming code with extra parity bit.
}
HammingCodes[16] = {
     {0, 0b00000000},
     {1, 0b10000111},
     {2, 0b10011001},
     {3, 0b00011110},
     {4, 0b10101010},
     {5, 0b00101101},
     {6, 0b00110011},
     {7, 0b10110100},
     {8, 0b01001011},
     {9, 0b11001100},
     {10, 0b11010010},
     {11, 0b01010101},
     {12, 0b11100001},
     {13, 0b01100110},
     {14, 0b01111000},
     {15, 0b11111111}
};
/* end of Hamming(8,4) struct */


main() {
     /* testing hamming */
     BYTE test[3];
     BYTE result;
     
     test[0]=0b01001011; // correct - should return "8" as the decoded data
     test[1]=0b00001011; // single bit error
     test[2]=0b10001011;  // double bit error

     while(TRUE) {
          printf("\fStarting...\r\n");
          for(i=0;i<3;i++) {
               result = decode(test[i]);
               if(result!=0xFF) printf("Test number %x, Original: %x, Decoded data: %x\r\n",i,test[i],result);
               else printf("More than one error in data\r\n");
          }
          delay_ms(4000); // 4000 was chosen arbitrarily
     }
     /* end of testing hamming */
}


BYTE decode(BYTE code) {
     BYTE j;
     j = codeToData(code);
     if(j!=0xFF) return j; // the corresponding code was found
     else { // code wasn't found
          j = correctCode(code); // try to correct a single bit error
          if(j==0xFF) return 0xFF; // there was more than a single bit error
          else return codeToData(j); // fixed it!  Get the data and be done!
     }
}

BYTE codeToData(BYTE code) {
     BYTE j;

     for (j = 0; j < 16; j++) {
          if (code == HammingCodes[j].nCode) {
               // Got it! Return the 4-bit data
               return j;
          }
     }
     // Not a code!
     return 0xFF;
}

BYTE correctCode(BYTE code) {
     BYTE n, j, mask;

     // Flip each bit and see if we can fix it!
     mask = 1;
     for (j=0;j<8;j++) {
          n = codeToData(code ^ mask);
          if (n != 0xFF) {
               // Corrected it!
               return code ^ mask;
          }
          mask <<= 1;
     }
     // More than single bit error - return 0xFF to signify inability to correct
     return 0xFF;
}

/* This function takes data (0-15) and converts it to a hamming code */
BYTE dataToCode(BYTE data) {
     if (data >= 0 && data < 16) {
          return HammingCodes[data].nCode;
     }
     return 0xFF; // incorrect range of data passed as parameter
}


I did pluck it out of context in another program I tested it in, so hopefully I didn't break anything or forget something. Please let me know if that's the case.

It's really cool to see the code recover completely from a single-bit error, and detect a two-bit error.

There might be a more efficient way to do this - I'd be interested in seeing it if there is a much more efficient way.

-Ryan


Last edited by evsource on Thu Jan 11, 2007 2:46 pm; edited 1 time in total
Display posts from previous:   
Post new topic   Reply to topic    CCS Forum Index -> Code Library All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group