Truncated match.
PICList
Thread
'Hamming correcting code generating formula need'
1997\05\14@113210
by
Dmitry Kiryashov
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 1bit 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

> 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 1bit 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 poweroftwo 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
poweroftwo 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 onthefly 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 8bit CRC would probably do just what you're
looking for]. More on those in another post.
1997\05\15@015520
by
Mik O Kim
I am interested in this as well. Any pointers or explanations is greatly
appreciated.
1997\05\15@122440
by
Dmitry Kiryashov

John Payson wrote:
>
> Hamming code is nice for hardware implementations because it lends itself
> to onthefly 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 8bit CRC would probably do just what you're
> looking for]. More on those in another post.
Just another idea crossparity 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
>> Hamming code is nice for hardware implementations
> Just another idea crossparity checking. ( Not my ;)
I believe this is called an LRC (longitudinal redundancy check).
It was used/is by old 9track tape drives.
Lee Jones
1997\05\15@204929
by
John Payson

> Just another idea crossparity 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 straightline code]. Using looping code requires
more cycles but fewer instructions. My recommendation is to have one
CRCbyte 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 bitmunge (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 nonzero 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 twobit 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 singlebit errors, with minimal
risk of "correcting" something into an equallybad 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...