James Newtons Massmind wrote:

  and quoted Andy:

>>Correct, James.  With my simple Hamming code, it's impossible 
>>to differentiate between a correctable one-bit error and a 
>>non- correctable two-bit error (or, for that matter, between 
>>zero errors and three errors).  
> 
> 
> Still and all, when bit 7 is set, you know there was an error and the data
> may, or may not be corrected. A single bit error will always be detected
> (and corrected) and the percentage chance that a multibit error could get
> through undetected is next to nothing.

I'm not exactly sure how you're wanting to use bit 7, James, but perhaps 
a slight improvement over the Hamming (4,7) algorithm is a "Hamming 
(4,8)" algorithm, which AFAIK does not exist. In the (4,7) algorithm, 
the 4 data bits are assigned the hamming indices of 3,5,6, and 7. It'd 
be instructive (read: I think it'd work but am too lazy to verify) to 
experiment with hamming indices of 3, 5, 10 and 12. These indices 
require 4 bits - hence the data plus hamming code take a total of 8 bits 
(and you get to use/waste bit 7!). What's interesting about the indices 
I've suggested is that they all have two binary 1's. All encodings are 
at least 3-hamming bits apart. I *think* this implies that you can 
distinguish between a correctable 1-bit error and an (uncorrectable) 
2-bit error. Many 3-bit errors are detectable.

BTW, the 16 possible encodings are:

00 31 52 63 A4 95 F6 C7 C8 F9 9A AB 6C 5D 3E 0F

This is analogous to Andy's encode[] array. Generating the analogous 
fixbits requires more effort than I'm willing to expend at the moment. I 
can say that the lower nibble of indices 0,3,5,10 and 12 should be 
0,1,2,4 and 8 respectively. The other indices of fixbits need to deal 
with multi-bit errors. All 2-bit errors are detectable, but I'm pretty 
sure they're not all correctable. For example, a 31 transmitted as a 38 
can be detected as an error and possibly be corrected by xoring the 38 
with a '9'. This would occupy the last index in the fixbit array (since 
(encode[8]^0x39)>>4 is 0x0f. However, something like a 52 transmitted as 
a 54 requires the same position in the fixbit array, but the correction 
of a '9' applied to 54 would be wrong...

Anyway, my conclusion based on this very meager analysis is that a 
Hamming (4,8) encoding doesn't buy anything more than the Hamming (4,7) 
encoding. Perhaps there are fewer 3-bit errors that are misinterpreted 
as valid data with the (4,8), but I don't know. Or perhaps there are a 
better choice of hamming indices, but I don't know that either.

Scott
-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist