'Hamming correcting code generating formula need'
To increase duration of 24xxx functioning inside of PIC system I think I
apply something like Hamming coding . Information block consist of 7
byte and 1 correcting code byte . I should correct 1-bit error and
error situation inside of information block.
Would someone like to tell me is any information about Hamming coding
theory , with
examples how to generate checking tail and further check information
block with it ,
( maybe CRC or else ) in Internet ?
P.S. Thank you for answer .
> To increase duration of 24xxx functioning inside of PIC system I think I
> apply something like Hamming coding . Information block consist of 7
> byte and 1 correcting code byte . I should correct 1-bit error and
> detect another
> error situation inside of information block.
Hmm... I think Hamming code is probably not your best choice, but I can
tell you about it anyhow.
> Would someone like to tell me is any information about Hamming coding
> theory , with
> examples how to generate checking tail and further check information
> block with it ,
> ( maybe CRC or else ) in Internet ?
The simplest way to understand Hamming code is to start with a number of
buckets, labeled 1 on up. Into every bucket (starting with the lowest)
whose number is NOT a power of two, you place a bit. If the bit was a 1,
you should toggle the state of all the power-of-two buckets whose numbers
go into the bucket number you used (e.g. if you place a "1" into bucket
#11, then you should toggle the bits in buckets 1, 2, and 8). The
power-of-two buckets are your check bits, the other buckets are your data.
Four data, 3 check
1 2 3 4 5 6 7
K0 K1 D0 K2 D1 D2 D3 Kn = check bit; Dn = data bit
K0 = D0 ^ D1 ^ D3
K1 = D0 ^ D2 ^ D3
K2 = D1 ^ D2 ^ D3
Eight data, 4 check
1 2 3 4 5 6 7 8 9 10 11 12
K0 K1 D0 K2 D1 D2 D3 K3 D4 D5 D6 D7
K0 = D0 ^ D1 ^ D3 ^ D4 ^ D6
K1 = D0 ^ D2 ^ D3 ^ D5 ^ D6
K2 = D1 ^ D2 ^ D3 ^ D7
K3 = D4 ^ D5 ^ D6 ^ D7
If you a number whose check bits don't match, add the numbers of the wrong
check bits to get the number of the wrong bit (e.g. if check bits K1 and
K3 don't match, you'd add their bucket numbers [2 and 8] to get the number
of the wrong bit bucket [bucket 10, D5]). If only one check bit is wrong,
then either the check bit itself is in error, or there are multiple errors
in the word.
Hamming code is nice for hardware implementations because it lends itself
to on-the-fly correction and small block sizes [allowing memory words to
be checked, corrected, and updated individually]. It's not the best
approach from a software point of view, however. A CRC tends to be better
for that [I'd suggest an 8-bit CRC would probably do just what you're
looking for]. More on those in another post.
Mik O Kim
I am interested in this as well. Any pointers or explanations is greatly
John Payson wrote:
> Hamming code is nice for hardware implementations because it lends itself
> to on-the-fly correction and small block sizes [allowing memory words to
> be checked, corrected, and updated individually]. It's not the best
> approach from a software point of view, however. A CRC tends to be better
> for that [I'd suggest an 8-bit CRC would probably do just what you're
> looking for]. More on those in another post.
Just another idea cross-parity checking. ( Not my ;)
Let we have 48 bit with useful information.
And we construct block with information like block below :
a0 a1 a2 a3 a4 a5 a6 a7 ; byte a
b0 b1 b2 b3 b4 b5 b6 b7 ; byte b
c0 c1 c2 c3 c4 c5 c6 c7 ; byte c
d0 d1 d2 d3 d4 d5 d6 d7 ; byte d
e0 e1 e2 e3 e4 e5 e6 e7 ; byte e
f0 f1 f2 f3 f4 f5 f6 f7 ; byte f
g0 g1 g2 g3 g4 g5 g6 g7 ; byte g
h0 h1 h2 h3 h4 h5 h6 h7 ; byte h
where a0,a1..a6,b0,b1..b6,...,g0,g1..g6 - information bits
1) a7 = a0^a1^a2^a3^a4^a5^a6 , b7 = b0^b1^b2^...^b6 , ... g7 =
2) h0 = a0^b0^c0^d0^e0^f0^g0 , h1 = a1^b1^c1^...^g1 , ... h6 =
3) h7 = h0^h1^h2^h3^h4^h5^h6^a7^b7^c7^d7^e7^f7^g7
" ^ " = XOR operation .
After reading total 8 bytes a,b,c..h we XOR it together. If result is
zero then OK .
Error occured in information bit result to corresponding column and
checking fault. ( In two checking bits at one time , see string 1) and
2) above) But
h7 parity check must be true .
If error occur in checking bits then h7 parity check fault.
To conclude talking above:
a) No error - byte_a ^ byte_b ^ ... ^ byte_h == 0
b) Single bit error - one bit from h0,h1..h6 parity checks fault and one
from a7,b7,c7...g7 parity checks fault too. But h7 parity check must
be true .
c) Single bit error in checking bits - one bit from
parity checks fault and h7 parity check fault too.
d) Any another results are situation with equal or more then 2 bits
Advantage of this method - easy to implement with PIC .
Misadvantage - to correct 48 bits of data need 16 reserved bits
(data efficient is 75%)
So question - is there another simple algorithm which also easy to PIC
and have much more data efficient ?
I look to CRC coding\decoding idea - I see I have to multiply\divide on
so I think CRC is hard for my purpose .
Finally I haven't much ROM space free inside of PIC to realize CRC
and division, I looking for "checking" fast algorithm solution about
words for PIC16Cxx .
>> Hamming code is nice for hardware implementations
> Just another idea cross-parity checking. ( Not my ;)
I believe this is called an LRC (longitudinal redundancy check).
It was used/is by old 9-track tape drives.
> Just another idea cross-parity checking. ( Not my ;)
> Advantage of this method - easy to implement with PIC .
> Misadvantage - to correct 48 bits of data need 16 reserved bits
> (data efficient is 75%)
> So question - is there another simple algorithm which also easy to PIC
> and have much more data efficient ?
For datagrams as described (56 bits data, 8 bits check) a CRC would be
better, and would be by recommended approach.
> I look to CRC coding\decoding idea - I see I have to multiply\divide on
> some nums,
> so I think CRC is hard for my purpose .
Many documents I've seen on CRC are confusing. Using straightforward
code, a PIC will require 16 instructions/cycles to run each byte through
the 8 bit CRC [assuming straight-line code]. Using looping code requires
more cycles but fewer instructions. My recommendation is to have one
CRC-byte routine which is called once for each byte in the message. In
this case, the routine is 17 cycles plus call/return.
The CRC byte routine itself is remarkably simple:
; DoCRC: Given a number in W, munge it into the CRC. To compute the CRC
; for a message, set CRC to the first byte of the message and then
; call this routine once every other byte of the message. Then call
; it once more with a constant value in W. The routine would have
; been a little more intuitive if I xor'ed W into CRC before doing
; the bit-munge (rather than having to do the extra call to DoCRC at
; the end) but that would have required an extra two cycles per call.
; Sorry I don't offhand know the proper values for Magic0 to
; Magic7. I'll have to write a little program to crunch them out.
; This routine should give you a pretty good idea of what's involved,
> Finally I haven't much ROM space free inside of PIC to realize CRC
> and division, I looking for "checking" fast algorithm solution about
> 70..100 program
> words for PIC16Cxx .
To checksum a 7+1 byte datagram with the above routine would be well
within your means:
movlw $A5 ; Or whatever; almost anything non-zero is good
; At this point, CRC holds the CRC value. You could either send
; the computed value or check it against a received value which
; is stored elsewhere.
The CRC method above will use 34 instruction words and take 174 cycles to
execute (total time for all 7 bytes). While it may not look like much, use
of the proper constants Magic0..Magic7 will give you:
- Full detection of all two-bit errors
- Full detection of all errors which occur within 8 consecutive bits
- Full detection of all errors involving an odd number of incorrect bits
- Ability (using more code) to correct all single-bit errors, with minimal
risk of "correcting" something into an equally-bad packet (depending
upon speed/codespace requirements, there are a number of approaches you
can use for this).
More... (looser matching)
- Last day of these posts
- In 1997
, 1998 only
- New search...