home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / cpm / hamming / ham10-t.ark / HAM.DOC < prev    next >
Encoding:
Text File  |  1984-09-12  |  9.9 KB  |  276 lines
  1.                                HAM
  2.  
  3.                            Version 1.0
  4.                         TURBO Pascal (tm)
  5.                         October 23, 1984
  6.  
  7.                            Adam Fritz
  8.                          133 Main Street
  9.                       Afton, New York 13730
  10.  
  11.          HamE(ncode)  and HamD(ecode) may be  used  for 
  12.          non-commercial  purposes only.   No commercial 
  13.          use of this document or these programs may  be 
  14.          made  without  the  author's  express  written 
  15.          permission.
  16.  
  17.  
  18.      The  programs  HamE 1.0 and HamD 1.0 implement a version  of 
  19. Hamming  error detection and correction coding.   These  programs 
  20. are  written in TURBO Pascal 2.0 and intended for CP/M  2.2  (tm) 
  21. compatible environments.
  22.  
  23.      The  reference  explains the concept and mathematics  for  a
  24. class  of codes intended to preserve information by  using  care-
  25. fully  composed  'parity'  bits carried with the  information  to
  26. detect and correct error.  The code applied here is Hamming (8,4) 
  27. and  is used to encode 4 bit nibbles into 8 bit bytes  such  that 
  28. two bit errors are detectable and one bit errors are correctable.
  29.  
  30.      Another presentation of this topic is found on some bulletin 
  31. boards.   Files  HAMMING.DOC and FORMHAM.ASM by Rod Hart  present
  32. introduction and code.
  33.  
  34.  
  35. USAGE
  36. =====
  37.  
  38. The text in file TEXT is encoded into CODE ;
  39.  
  40.    A>hame <text >code
  41.  
  42. and decoded into CLEAR ;
  43.  
  44.    A>hamd <code >clear
  45.  
  46.  
  47. EXAMPLE
  48. =======
  49.  
  50.      The filter GREMLIN reads its input,  flips bits at intervals
  51. uniformly  distributed over a specified  interbit  distance,  and
  52. writes to the output.  The command;
  53.  
  54.  
  55. { Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
  56. { Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
  57.  
  58.  
  59.    A>gremlin -d37 <text
  60.  
  61. reads  file TEXT,  flips bits at an average interbit distance  of
  62. 18, and writes to the CON: device.  GREMLIN is intended to illus-
  63. trate corruption resistance of coded data.  
  64.  
  65. File TEXT contains;
  66.  
  67.    We the People of the United States, in order to form a more 
  68.    perfect Union, establish Justice, insure domestic Tranquility, 
  69.    provide for the common defence, promote the general Welfare, and 
  70.    secure the Blessings of Liberty to ourselves and our Posterity, 
  71.    do ordain and establish this Constitution for the United States 
  72.    of America.
  73.  
  74. Suppose that GREMLIN is used to corrupt this text;
  75.  
  76.    A>gremlin -d64 <text
  77.  
  78. so that the output might appear;
  79.  
  80.    We T`e Peophe of the Unated ^States, an orler to Fozm ! more ^I^J
  81.    perfesu Wnionl estabdisl Hustisu, iosure domestic"Tranquinity, ^]^J
  82.    provile bor uhg comMon defelce,2promnte thd general W%lfare, ant(
  83.    sgcur%!the Blessilgs of Licerty to#oursglves qnd ouz Postezity, 
  84.    do ordakn and ustajl)sh"this`Constitetion for0the!Unided stateq
  85.    of!Ame2ica.
  86.  
  87. where  the  careted characters denote ASCII  control  characters.  
  88. Suppose  instead that the text is encoded and then corrupted  and 
  89. decoded.  The commands;
  90.  
  91.    A>hame <text >code
  92.    A>gremlin -d64 <code >corrupt
  93.    A>hamd <corrupt >clear
  94.  
  95. Hamming  encode file TEXT,  corrupt the encoded file by  flipping 
  96. about  every 32nd bit,  and decode the corrupted file into CLEAR.  
  97. GREMLIN reports;
  98.  
  99.  (0) 591 (1) 169 (2) 7 (3) 1 (4) 0 (5) 0 (6) 0 (7) 0 (8) 0
  100.  
  101. which  means there are 768 bytes in the corrupted  file,  591  of 
  102. which  are  unchanged,  169 have one bit flipped,  7 have 2  bits 
  103. flipped, and 1 has 3 bits flipped.  HAMD reports;
  104.  
  105. Errors Detected: 177, Errors Corrected: 170
  106.  
  107. so  it appears that all errors were detected but that the  3  bit 
  108. error  may  have  been  treated as a single bit  error  and  some 
  109.  
  110. { Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
  111. { Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
  112.  
  113.  
  114. correction performed.  The decoded file CLEAR;
  115.  
  116.    We 4he People of the United States, in order to form a more&
  117.    perfect Union, establish Justice, insure domestic Tranquility, 
  118.    provide f-r the common defence, promotm the general Welfare, and
  119.    secure the Blessings of Libertypto ourselves and our Posterity,
  120.    do ordain and establish this Constitution for the Unitgd States
  121.    of America.
  122.  
  123. which is clearly still usable.   Similar commands,  but using  32
  124. for GREMLIN's parameter, report;
  125.  
  126.  (0) 434 (1) 300 (2) 29 (3) 4 (4) 1 (5) 0 (6) 0 (7) 0 (8) 0
  127.  
  128. and
  129.  
  130. Errors Detected: 333, Errors Corrected: 303
  131.  
  132. for GREMLIN and HAMD, respectively, and file CLEAR appears;
  133.  
  134.    We the"People of the Uniqmd^@States, In order to form a more+
  135.    perfect Umijn,0ectablish Justice, insure domestic Tranquility, ^]^J
  136.    provide fo2 the common defence$ promote thd ge~eral Welfare, and 
  137.    segure the reessingz of Libgrty to ouRselves and,our Posterity, 
  138.    d/ ovdein and establish this Constitution for the United States 
  139.    of America.
  140.  
  141. Using 16 for GREMLIN's parameter reports for GREMLIN;
  142.  
  143.  768 (0) 208 (1) 409 (2) 133 (3) 17 (4) 1 (5) 0 (6) 0 (7) 0 (8) 0
  144.  
  145. and for HAMD;
  146.  
  147. Errors Detected: 560, Errors Corrected: 430
  148.  
  149. and CLEAR appears;
  150.  
  151.    We the!P5opl` f the Wnyted [6adeS, mn orge2 to for} a mowe =^J
  152.    perfec| Unaen, esthblish JuwdicE, ijsuve d/mestIc T{enqwi^Lity, ^O^A
  153.    provi$e fob the$co}mon tafe~SE, pr/-ode'the genural S/l&arw,`and`
  154.    secur% tbeAKlessIggw f Libebti to ourselves`and Our Pkstesid{, 
  155.    dO ordain afl esta`lisH THisaGonsti~utikn"f/r thd United Stave ^L
  156.    of!Amerifan-^J
  157.  
  158.      For practical purposes,  this degree of corruption makes the 
  159. file  unusable.   Consider,  however,  what happens to TEXT  when 
  160. directly corrupted to this intensity;
  161.  
  162.    WE(phm`PmgPlm`kv#4`a W~ytdd"Svadus$$im^@opdws uo &obe #!oord ^N^X
  163.    pmzfdad ^]l)o~, usEcb-mqx Nu[xIcel()n{}bedDkMmstib00rqjp=inivy= ^I^Z
  164.  
  165. { Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
  166. { Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
  167.  
  168.  
  169.    qrn^)du corbtle$commkn!Deve~c^Gn$pVolnvM dhd!gdn$rqd Vumf`R%.^D
  170.    affr/^JS-1uve(t)e"JlmSwigg;`on H)bEB4y$|/`otsSulVas$and kws"@/rtlp+
  171.    t(, -^Jf.^@grlayN$add"es4a"l}sj`tlQ{ JLn2di|uuIoj(fgr!tme^BU~ivme$Qvi
  172.    4%s0mn$Aoevace.^I*
  173.  
  174.      Filter  BF counts the occurences of byte codes appearing  in 
  175. its  argument  files and reports the results file by file to  the 
  176. standard  output.   If no argument file appears then it uses  the 
  177. standard input.   By using BF it is possible to see what HAME  is 
  178. doing;
  179.  
  180.    A>hame <text | bf
  181.  
  182. displays the following tableau to the console;
  183.  
  184. Bytes: 768
  185.  
  186.         0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
  187.  
  188.    0    0  0  0  0  0  0  0  0  0  0  0  0  0  0 14  0
  189.    1   60  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  190.    2    0  0  0  0  0 16  0  0  0  0  0  0  0  0  0  0
  191.    3    0  0  0  0  0  0  0  0  0  0  0 59  0  0  0  0
  192.    4    0  0  0147  0  0  0  0  0  0  0  0  0  0  0  0
  193.    5    0  0  0  0  0  0  0  0  0  0  0  0  0 35  0  0
  194.    6    0  0  0  0  0  0  0  0 76  0  0  0  0  0  0  0
  195.    7    0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  196.    8    0  0  0  0  0  0  0  0  0 45  0  0  0  0  0  0
  197.    9    0  0  0  0  0  0  0 13  0  0  0  0  0  0  0  0
  198.   10    0  0 64  0  0  0  0  0  0  0  0  0  0  0  0  0
  199.   11    0  0  0  0  0  0  0  0  0  0  0  0 23  0  0  0
  200.   12    0  0  0  0 59  0  0  0  0  0  0  0  0  0  0  0
  201.   13    0  0  0  0  0  0  0  0  0  0 28  0  0  0  0  0
  202.   14    0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 52
  203.   15    0 77  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  204.  
  205. which  means that the byte $43 appears 147 times in  the  encoded 
  206. file.   Note that each row and column contains, at most, one non-
  207. zero  entry.   It is this redundancy that HAMD exploits to detect
  208. and correct errors.
  209.  
  210.  
  211. COMMENTS
  212. ========
  213.  
  214.    i. At  the  expense of doubling a file's  physical  size  and, 
  215.       therefore,  roughly doubling storage and transmission times 
  216.       some  resistance to corruption is provided with modest  CPU
  217.       times.
  218.  
  219.  
  220. { Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
  221. { Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
  222.  
  223.   ii. Any coding scheme has a fairly narrow range of utility.  If 
  224.       channel  reliability is good then errors are so  rare  that 
  225.       the code is unneeded while very poor reliability overwhelms 
  226.       the  code.  Whether  this code helps can probably  best  be 
  227.       determined  by applying it when difficulty is encountered -
  228.       somewhat  the way poor voice communications are  surmounted
  229.       by resort to spelling, e.g., papa uncle nan tare!
  230.  
  231.  iii. Note that detected errors include parity bit errors as well 
  232.       as data errors.
  233.  
  234.   iv. Note  that this code deals only with recovery from  channel 
  235.       symbol  transliteration  errors.   Missing symbols are  not 
  236.       detected.  That is, this code is probably better adapted to 
  237.       synchronous than asynchronous communication.
  238.  
  239.    v. Clearly,  GREMLIN  is not friendly and can  promptly  trash 
  240.       the  logical  contents of a  file.   The  default  interbit
  241.       distance is 64.
  242.  
  243.   vi. These routines accept I/O redirection and will pipe, e.g.;
  244.  
  245.          A>hame <text | gremlin -d100 | hamd >clear
  246.  
  247.  
  248. QUESTION
  249. ========
  250.  
  251.    i. Does  it make any difference how the parity bits are inter-
  252.       laced  with the data bits in the code word?   Suppose  that
  253.       the  bit  errors are not uniformly  distributed  over  some
  254.       interbit  distance but rather that bit errors are  serially
  255.       correlated and modeled with a 'bursty' gremlin.
  256.  
  257.   ii. Can error resistance be improved by nested encodings?   For
  258.       example;
  259.  
  260.          A>hame <text | hame | gremlin -d64 | hamd | hamd >clear
  261.  
  262.  
  263. REFERENCE
  264. =========
  265.  
  266.    Error-Correcting Codes
  267.    W. Wesley Peterson
  268.    The M.I.T. Press, 4th Printing, 1968
  269.    Chapter 5, Example 2, pg. 65 et seq
  270.  
  271. TURBO Pascal (tm) Borland International
  272. MS-DOS Microsoft
  273. CP/M (tm) Digital Research
  274.  
  275. { Copyright (C) 1984 Adam Fritz, 133 Main St., Afton, N.Y. 13730 }
  276.