evsource
Joined: 21 Nov 2006
Posts: 129
|
| Hamming code example |
 Posted: Thu Jan 11, 2007 12:57 pm |
 |
|
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 |
|
FAQ 
Search
Register
Profile 
Log in to check your private messages 
Log in
