HAM

                           Version 1.0
                        TURBO Pascal (tm)
                        October 23, 1984

                           Adam Fritz
                         133 Main Street
                      Afton, New York 13730

         HamE(ncode)  and HamD(ecode) may be  used  for 
         non-commercial  purposes only.   No commercial 
         use of this document or these programs may  be 
         made  without  the  author's  express  written 
         permission.


     The  programs  HamE 1.0 and HamD 1.0 implement a version  of 
Hamming  error detection and correction coding.   These  programs 
are  written in TURBO Pascal 2.0 and intended for CP/M  2.2  (tm) 
compatible environments.

     The  reference  explains the concept and mathematics  for  a
class  of codes intended to preserve information by  using  care-
fully  composed  'parity'  bits carried with the  information  to
detect and correct error.  The code applied here is Hamming (8,4) 
and  is used to encode 4 bit nibbles into 8 bit bytes  such  that 
two bit errors are detectable and one bit errors are correctable.

     Another presentation of this topic is found on some bulletin 
boards.   Files  HAMMING.DOC and FORMHAM.ASM by Rod Hart  present
introduction and code.


USAGE
=====

The text in file TEXT is encoded into CODE ;

   A>hame <text >code

and decoded into CLEAR ;

   A>hamd <code >clear


EXAMPLE
=======

     The filter GREMLIN reads its input,  flips bits at intervals
uniformly  distributed over a specified  interbit  distance,  and
writes to the output.  The command;


{ Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
{ Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }


   A>gremlin -d37 <text

reads  file TEXT,  flips bits at an average interbit distance  of
18, and writes to the CON: device.  GREMLIN is intended to illus-
trate corruption resistance of coded data.  

File TEXT contains;

   We the People of the United States, in order to form a more 
   perfect Union, establish Justice, insure domestic Tranquility, 
   provide for the common defence, promote the general Welfare, and 
   secure the Blessings of Liberty to ourselves and our Posterity, 
   do ordain and establish this Constitution for the United States 
   of America.

Suppose that GREMLIN is used to corrupt this text;

   A>gremlin -d64 <text

so that the output might appear;

   We T`e Peophe of the Unated ^States, an orler to Fozm ! more ^I^J
   perfesu Wnionl estabdisl Hustisu, iosure domestic"Tranquinity, ^]^J
   provile bor uhg comMon defelce,2promnte thd general W%lfare, ant(
   sgcur%!the Blessilgs of Licerty to#oursglves qnd ouz Postezity, 
   do ordakn and ustajl)sh"this`Constitetion for0the!Unided stateq
   of!Ame2ica.

where  the  careted characters denote ASCII  control  characters.  
Suppose  instead that the text is encoded and then corrupted  and 
decoded.  The commands;

   A>hame <text >code
   A>gremlin -d64 <code >corrupt
   A>hamd <corrupt >clear

Hamming  encode file TEXT,  corrupt the encoded file by  flipping 
about  every 32nd bit,  and decode the corrupted file into CLEAR.  
GREMLIN reports;

 (0) 591 (1) 169 (2) 7 (3) 1 (4) 0 (5) 0 (6) 0 (7) 0 (8) 0

which  means there are 768 bytes in the corrupted  file,  591  of 
which  are  unchanged,  169 have one bit flipped,  7 have 2  bits 
flipped, and 1 has 3 bits flipped.  HAMD reports;

Errors Detected: 177, Errors Corrected: 170

so  it appears that all errors were detected but that the  3  bit 
error  may  have  been  treated as a single bit  error  and  some 

{ Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
{ Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }


correction performed.  The decoded file CLEAR;

   We 4he People of the United States, in order to form a more&
   perfect Union, establish Justice, insure domestic Tranquility, 
   provide f-r the common defence, promotm the general Welfare, and
   secure the Blessings of Libertypto ourselves and our Posterity,
   do ordain and establish this Constitution for the Unitgd States
   of America.

which is clearly still usable.   Similar commands,  but using  32
for GREMLIN's parameter, report;

 (0) 434 (1) 300 (2) 29 (3) 4 (4) 1 (5) 0 (6) 0 (7) 0 (8) 0

and

Errors Detected: 333, Errors Corrected: 303

for GREMLIN and HAMD, respectively, and file CLEAR appears;

   We the"People of the Uniqmd^@States, In order to form a more+
   perfect Umijn,0ectablish Justice, insure domestic Tranquility, ^]^J
   provide fo2 the common defence$ promote thd ge~eral Welfare, and 
   segure the reessingz of Libgrty to ouRselves and,our Posterity, 
   d/ ovdein and establish this Constitution for the United States 
   of America.

Using 16 for GREMLIN's parameter reports for GREMLIN;

 768 (0) 208 (1) 409 (2) 133 (3) 17 (4) 1 (5) 0 (6) 0 (7) 0 (8) 0

and for HAMD;

Errors Detected: 560, Errors Corrected: 430

and CLEAR appears;

   We the!P5opl` f the Wnyted [6adeS, mn orge2 to for} a mowe =^J
   perfec| Unaen, esthblish JuwdicE, ijsuve d/mestIc T{enqwi^Lity, ^O^A
   provi$e fob the$co}mon tafe~SE, pr/-ode'the genural S/l&arw,`and`
   secur% tbeAKlessIggw f Libebti to ourselves`and Our Pkstesid{, 
   dO ordain afl esta`lisH THisaGonsti~utikn"f/r thd United Stave ^L
   of!Amerifan-^J

     For practical purposes,  this degree of corruption makes the 
file  unusable.   Consider,  however,  what happens to TEXT  when 
directly corrupted to this intensity;

   WE(phm`PmgPlm`kv#4`a W~ytdd"Svadus$$im^@opdws uo &obe #!oord ^N^X
   pmzfdad ^]l)o~, usEcb-mqx Nu[xIcel()n{}bedDkMmstib00rqjp=inivy= ^I^Z

{ Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
{ Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }


   qrn^)du corbtle$commkn!Deve~c^Gn$pVolnvM dhd!gdn$rqd Vumf`R%.^D
   affr/^JS-1uve(t)e"JlmSwigg;`on H)bEB4y$|/`otsSulVas$and kws"@/rtlp+
   t(, -^Jf.^@grlayN$add"es4a"l}sj`tlQ{ JLn2di|uuIoj(fgr!tme^BU~ivme$Qvi
   4%s0mn$Aoevace.^I*

     Filter  BF counts the occurences of byte codes appearing  in 
its  argument  files and reports the results file by file to  the 
standard  output.   If no argument file appears then it uses  the 
standard input.   By using BF it is possible to see what HAME  is 
doing;

   A>hame <text | bf

displays the following tableau to the console;

Bytes: 768

        0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

   0    0  0  0  0  0  0  0  0  0  0  0  0  0  0 14  0
   1   60  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   2    0  0  0  0  0 16  0  0  0  0  0  0  0  0  0  0
   3    0  0  0  0  0  0  0  0  0  0  0 59  0  0  0  0
   4    0  0  0147  0  0  0  0  0  0  0  0  0  0  0  0
   5    0  0  0  0  0  0  0  0  0  0  0  0  0 35  0  0
   6    0  0  0  0  0  0  0  0 76  0  0  0  0  0  0  0
   7    0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   8    0  0  0  0  0  0  0  0  0 45  0  0  0  0  0  0
   9    0  0  0  0  0  0  0 13  0  0  0  0  0  0  0  0
  10    0  0 64  0  0  0  0  0  0  0  0  0  0  0  0  0
  11    0  0  0  0  0  0  0  0  0  0  0  0 23  0  0  0
  12    0  0  0  0 59  0  0  0  0  0  0  0  0  0  0  0
  13    0  0  0  0  0  0  0  0  0  0 28  0  0  0  0  0
  14    0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 52
  15    0 77  0  0  0  0  0  0  0  0  0  0  0  0  0  0

which  means that the byte $43 appears 147 times in  the  encoded 
file.   Note that each row and column contains, at most, one non-
zero  entry.   It is this redundancy that HAMD exploits to detect
and correct errors.


COMMENTS
========

   i. At  the  expense of doubling a file's  physical  size  and, 
      therefore,  roughly doubling storage and transmission times 
      some  resistance to corruption is provided with modest  CPU
      times.


{ Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
{ Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }

  ii. Any coding scheme has a fairly narrow range of utility.  If 
      channel  reliability is good then errors are so  rare  that 
      the code is unneeded while very poor reliability overwhelms 
      the  code.  Whether  this code helps can probably  best  be 
      determined  by applying it when difficulty is encountered -
      somewhat  the way poor voice communications are  surmounted
      by resort to spelling, e.g., papa uncle nan tare!

 iii. Note that detected errors include parity bit errors as well 
      as data errors.

  iv. Note  that this code deals only with recovery from  channel 
      symbol  transliteration  errors.   Missing symbols are  not 
      detected.  That is, this code is probably better adapted to 
      synchronous than asynchronous communication.

   v. Clearly,  GREMLIN  is not friendly and can  promptly  trash 
      the  logical  contents of a  file.   The  default  interbit
      distance is 64.

  vi. These routines accept I/O redirection and will pipe, e.g.;

         A>hame <text | gremlin -d100 | hamd >clear


QUESTION
========

   i. Does  it make any difference how the parity bits are inter-
      laced  with the data bits in the code word?   Suppose  that
      the  bit  errors are not uniformly  distributed  over  some
      interbit  distance but rather that bit errors are  serially
      correlated and modeled with a 'bursty' gremlin.

  ii. Can error resistance be improved by nested encodings?   For
      example;

         A>hame <text | hame | gremlin -d64 | hamd | hamd >clear


REFERENCE
=========

   Error-Correcting Codes
   W. Wesley Peterson
   The M.I.T. Press, 4th Printing, 1968
   Chapter 5, Example 2, pg. 65 et seq

TURBO Pascal (tm) Borland International
MS-DOS Microsoft
CP/M (tm) Digital Research

{ Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }