From: Randall Bart Newsgroups: alt.folklore.computers,comp.sys.unisys Subject: Single bit error detection Organization: Please reply without spam Reply-To: admin@RandallBart.spam.com Message-ID: References: <01HW.B93BD4F1004260F610E07880@news-east.usenetserver.com> <3D16682A.6050609@beagle-ears.com> <01HW.B93C94F0006F75FD10E07880@news-east.usenetserver.com> <01HW.B93D459C0098EEDA10E07880@news-east.usenetserver.com> <3D17E11A.A3053900@yahoo.com> <3D1A2C63.6050205@boutel.co.nz> X-Newsreader: Forte Agent 1.9/32.560 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit Lines: 55 Date: Thu, 27 Jun 2002 02:49:29 GMT NNTP-Posting-Host: 12.89.136.125 X-Complaints-To: abuse@worldnet.att.net X-Trace: bgtnsc05-news.ops.worldnet.att.net 1025146169 12.89.136.125 (Thu, 27 Jun 2002 02:49:29 GMT) NNTP-Posting-Date: Thu, 27 Jun 2002 02:49:29 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!wn1feed!worldnet.att.net!bgtnsc05-news.ops.worldnet.att.net.POSTED!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:110872 Lemme see if I can reconstruct this from memory. Single Bit Error Correction Via Hamming Bits (8-Bit Example) For error correction, we need a parity bit plus enough hamming bits to address the data bits, the parity bit, and the hamming bits. For eight bits, that will be one parity bit and four hamming bits. The hamming bits go in hamming locations which correspond to powers of 2. Therefore the hamming bits will be 1, 2, 4, and 8. Let's lay out the bits: Data bits: P H1 H2 D0 H4 D1 D2 D3 H8 D4 D5 D6 D7 Hamming location: 0 1 2 3 4 5 6 7 8 9 10 11 12 (It looks better monospaced.) The parity bit and the hamming bits each have a domain. The domain of each hamming bit is the data bits whose hamming location in binary contains that bit. The domain of the parity bit is all data and hamming bits. H1 - D0, D1, D3, D4, D6 H2 - D0, D2, D3, D5, D6 H4 - D1, D2, D3, D7 H8 - D4, D5, D6, D7 The value of the parity bit and the hamming bits is set so that each domain has an even number of 1 bits. (Or odd, but I'll use even parity.) Example: Take the data 01101110 0 1 1 0 1 1 1 0 Data bits: P H1 H2 D0 H4 D1 D2 D3 H8 D4 D5 D6 D7 Hamming location: 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 To validate the data, the parity and hamming bits are calculated. If any one bit is flipped, the parity bit will be wrong, indicating correctable error. Calculate the hamming bits, and their binary value points to the bit in error. If it comes out to zero, the bad bit is the parity bit itself. If it comes out to 1, 2, 4, or 8, the error is in the hamming bit. If it comes out any other value, the error in the data bit in that hamming location. If the parity bit works out right, but one of more hamming bits is wrong, that's a two bit error. It can't be corrected, but that's two bit error detection. If three bits are flipped, the parity bit will come out wrong, and error correction will flip one bit (erroneously). If you turn off one bit error correction, you will have three bit error detection. Play around with this and you'll see what I mean. -- RB |\ © Randall Bart aa |/ admin@RandallBart.spam.com Barticus@att.spam.net nr |\ Please reply without spam I LOVE YOU 1-917-715-0831 dt ||\ http://RandallBart.com/ DOT-HS-808-065 MS^7=6/28/107 a |/ "Believe nothing, no matter where you read it, or who l |\ said it, no matter if I have said it, unless it agrees l |/ with your own reason and your own common sense."--Buddha