Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!paperboy!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!mcsun!ukc!edcastle!cs.ed.ac.uk!cs.edinburgh.ac.uk!ddr
From: ddr@cs.edinburgh.ac.uk (Doug Rogers)
Newsgroups: comp.theory
Subject: Re: Hamming codes 101
Message-ID: <8380@skye.cs.ed.ac.uk>
Date: 28 Mar 91 19:33:45 GMT
References: <25MAR91.01330289@uc780.umd.edu> <1991Mar25.123457.24645@mailer.cc.fsu.edu> <26MAR91.00093317@uc780.umd.edu> <1991Mar26.100044.16609@mailer.cc.fsu.edu>
Sender: nnews@cs.ed.ac.uk
Reply-To: ddr@cs.edinburgh.ac.uk (Doug Rogers)
Organization: Department of Computer Science, University of Edinburgh
Lines: 40

The first posting on this was flawed in that it did not take acount of the check bits themselves being faulty.

I've always thought of hamming codes in terms of the binary value of the bit

Example for 16 bits of which 

        Bit address	Purpose
	0  0000		overall parity check for 2 bit error detection		
	1  0001		check bit 
	2  0010		check bit
	3  0011		data
	4  0100		check bit
	5  0101		data
	6  0110		data
	7  0111		data
	8  1000		check bit
	9  1001		data
	A  1010		data
	B  1011		data
	C  1100		data
	D  1101		data
	E  1110		data
	F  1111		data



By making the check sum for all bits with one of their address bits set at 1 be 
even, then the offending error is found by anding the addresses of the check bits that fail on receipt. 

For actual implementation the addresses may be shuffled to combine the check bits at one end of the message. This though illustrates that :
   s':=lg2(s')+s+1

where s' is the total number of bits needed and s is the number of bits available for
data.
which is not soluable to give an easy equation for the number of check bits needed.
-- 
Douglas Rogers                     JANET: ddr@uk.ac.ed.lfcs
Department of Computer Science     UUCP:  ..!mcvax!ukc!lfcs!ddr
University of Edinburgh            ARPA:  ddr%lfcs.ed.ac.uk@nsfnet-relay.ac.uk
Edinburgh EH9 3JZ, UK.             Tel:   031-650 5172 (direct line)