Searching \ for 'Hamming correcting code generating formula need' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: techref.massmind.org/techref/method/errors.htm?key=hamming
Search entire site for: 'Hamming correcting code generating formula need'.

Truncated match.
PICList Thread
'Hamming correcting code generating formula need'
1997\05\14@113210 by Dmitry Kiryashov

flavicon
face
Hi all.

To increase duration of 24xxx functioning inside of PIC system I think I
should
apply something like Hamming coding . Information block consist of 7
information
byte and 1 correcting code byte . I should correct 1-bit error and
detect another
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 ?

WBR Dmitry.

P.S. Thank you for answer .

1997\05\14@205137 by John Payson

flavicon
face
> To increase duration of 24xxx functioning inside of PIC system I think I
> should
> apply something like Hamming coding . Information block consist of 7
> information
> 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.
Typical arrangements:

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.

1997\05\15@015520 by Mik O Kim

flavicon
face
I am interested in this as well. Any pointers or explanations is greatly
appreciated.

1997\05\15@122440 by Dmitry Kiryashov

flavicon
face
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 =
g0^g1^...^g6
2) h0 = a0^b0^c0^d0^e0^f0^g0 , h1 = a1^b1^c1^...^g1 , ... h6 =
a6^b6^...^g6
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
string parity
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
bit
  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
h0,h1,h2...h6,a7,b7,c7,d7..g7
  parity checks fault and h7 parity check fault too.
d) Any another results are situation with equal or more then 2 bits
error.


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
programming
and have much more data efficient ?
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 .
Finally I haven't much ROM space free inside of PIC to realize CRC
multiplication
and division, I looking for "checking" fast algorithm solution about
70..100 program
words for PIC16Cxx .

WBR Dmitry.

1997\05\15@171834 by Lee Jones

flavicon
face
>> 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.
                                               Lee Jones

1997\05\15@204929 by John Payson

flavicon
face
> 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
> programming
> 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,
;        though.

DoCRC:
       btfsc   CRC,0
        xorlw  Magic0
       btfsc   CRC,1
        xorlw  Magic1
       btfsc   CRC,2
        xorlw  Magic2
       btfsc   CRC,3
        xorlw  Magic3
       btfsc   CRC,4
        xorlw  Magic4
       btfsc   CRC,5
        xorlw  Magic5
       btfsc   CRC,6
        xorlw  Magic6
       btfsc   CRC,7
        xorlw  Magic7
       xorwf   CRC
       return

> Finally I haven't much ROM space free inside of PIC to realize CRC
> multiplication
> 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:

       movf    Data0,w
       movwf   CRC
       movf    Data1,w
       call    DoCRC
       movf    Data2,w
       call    DoCRC
       movf    Data3,w
       call    DoCRC
       movf    Data4,w
       call    DoCRC
       movf    Data5,w
       call    DoCRC
       movf    Data6,w
       call    DoCRC
       movlw   $A5     ; Or whatever; almost anything non-zero is good
       call    DoCRC

       ; 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
- Today
- New search...