hamming.h

Go to the documentation of this file.

#ifndef HAMMING_CLASS
#define HAMMING_CLASS

/*****************************************************************************\
*                                                                             *
*  Name   : hamming network                                                   *
*  Author : Chris Koeritz                                                     *
*                                                                             *
*******************************************************************************
* Copyright (c) 1992-$now By Author.  This program is free software; you can  *
* redistribute it and/or modify it under the terms of the GNU General Public  *
* License as published by the Free Software Foundation; either version 2 of   *
* the License or (at your option) any later version.  This is online at:      *
*     http://www.fsf.org/copyleft/gpl.html                                    *
* Please send any updates to: fred@gruntose.com                               *
\*****************************************************************************/

#include "hamming_dll.h"

#include <basis/chaos.h>

#include <stdio.h>

//hmmm: move this constant stuff to inside the cpp file.

// The names below tell the program where to locate its data files.
// defaults are necessary for it to know exemplar sizes and the number
// of exemplars, while the prefix is what every exemplar starts with.
// exemplars will be read in in the form exempl00.dat through
// exempl{m-1}.dat, where {m} is the total number of exemplars.
#define DEFAULTS_FILE_NAME "./data/defaults.dat"
#define EXEMPLAR_PREFIX    "./data/exempl"

// MBIP = largest value for N, ME = largest value for M
// the following values are obtained from the defaults file.
#define MAXIMUM_BITS_IN_PATTERN 100
#define MAXIMUM_EXEMPLARS       50

// iterations allowed before abandoning convergence.
#define MAXIMUM_ITERATION 30

// the size of the terminal's screen.
#define SCREEN_WIDTH 80

// patterns are read from files or entered by the user.
typedef int bit_pattern[MAXIMUM_BITS_IN_PATTERN];




class HAMMING_CLASS_STYLE hamming
{
public:
  // The unknown (and user specified) input pattern.
  bit_pattern x;

  // the constructor and destructor do not do anything yet.
  hamming();
  ~hamming();

  // corrupter: flips the number of bits specified by _faults_
  // in an exemplar pattern.
  void corrupter(int ex[], int faults);

  // init_lower_subnet: initialize the weight matrix for the lower network.
  // if _faults_ is positive, the specified number of weights
  // will be corrupted to some random value (see note about faults).
  void init_lower_subnet(int faults);

  // init_upper_subnet: init the weight matrix for the upper subnet, Maxnet.
  // _faults_ is the number of faulty weight lines.  (see note).
  void init_upper_subnet(int faults);

  // f_thresh: implement a threshold logic non-linearity, the function
  // each node is calculating.
  double f_thresh(double alpha);

  // init_with_unknown_pattern: apply an unknown input pattern to the
  // lower net and derive state 0 of the maxnet's outputs.
  // a number (faults) of the first output components are corrupted.
  void init_with_unknown_pattern(int faults);

  // converge: inhibits the less likely outputs to achieve one optimal
  // solution.
  void converge();

  // iterate_until_converges: repeatedly calls converge until there
  // is only one positive output of maxnet.  this is chosen as the
  // closest exemplar to the input pattern and returned.
  int iterate_until_convergence();

  // show_pattern_line: prints a particular line from the pattern ex[].
  // the second version prints the line to a file.
  void show_pattern_line(int ex[], int line);
  void show_pattern_line(int ex[], int line, FILE *print_to);
  void show_pattern_line(int exemplar_number, int line, FILE *print_to);

  // dump_pattern: prints one entire pattern.
  void dump_pattern(int ex[]);

  // copy_pattern:
  void copy_pattern(bit_pattern destination, bit_pattern source);

  // show_exemplars: display the whole set of exemplars.
  void show_exemplars();

  // get_sample: queries for patterns interactively.
  void get_sample();

  // save_sample: stores an example input.
  void save_sample();

  // read_file: reads a pattern out of the file specified
  // and stored it in the array.
  void read_file(char *filename, int pattern[]);

  // get_defaults:
  void get_defaults();

  // get_exemplars:
  void get_exemplars();

  // print_instructions_and_exit:
  void print_instructions_and_exit();

  // current_time, pattern_rows, pattern_cols: windows into the program's variables.
  int current_time();
  int pattern_rows();
  int pattern_cols();

private:

  // maxnet_output_sum: sums all maxnet outputs, except at node j,
  // using the values as they were at time t.
  double maxnet_output_sum(int j);

  // only_one_positive_output_left: if only one output (mu) at time t
  // is left standing, then that output is returned.  otherwise, a
  // negative value is returned to denote that convergence has not
  // yet happened.
  int only_one_positive_output_left();

  // weighted_sum:
  double weighted_sum(int j);

  // corrupted_sum:
  double corrupted_sum();

  // The current simulation time in "units", or simulation steps.
  int t;

  int rows;       // height of pattern
  int cols;       // width of pattern

  int M;          // number of exemplar patterns
  int N;          // number of bits per pattern (rows x cols)

  // exemplars are the patterns to be recognized.
  int exemplars [MAXIMUM_EXEMPLARS] [MAXIMUM_BITS_IN_PATTERN];

  chaos randomizer;

  // The weights of the lower subnet, set from the hamming distances
  // of the exemplars.
  double w [MAXIMUM_BITS_IN_PATTERN] [MAXIMUM_EXEMPLARS];
  // The weights of Maxnet, which inhibits the outputs whose exemplars
  // are not close in hamming distance to the unknown input pattern.
  double maxnet [MAXIMUM_EXEMPLARS] [MAXIMUM_EXEMPLARS];
  // Temporary pattern used to hold the input pattern between corruptions.
  bit_pattern y;
  // The output at time t.  It is in matrix form because each output is
  // kept as time goes along discretely.  Since the net often converges
  // by the tenth time unit, this is reasonable.
  double mu [MAXIMUM_ITERATION] [MAXIMUM_EXEMPLARS];

  // The threshold value that for maxnet's outputs.
  double THETA;
  // Maxnet inhibitory weight.
  double EPSILON;
};

// A NOTE about faults added to the net:
// Major ASSUMPTION: Faults only occur between training periods of
// the net; no faults will occur while the net is actually working
// on an unknown input pattern.  This is a reasonable assumption if
// the duration between uses of the net is long compared to the duration
// of time to recognize a pattern.  Since our net is always initialized
// before each attempt at recognition, that reasoning works here.
// ASSUMPTION: in init_lower_subnet, the weight will only be corrupted
// within the range in which it is usually valid.  If, in reality, a fault
// can cause the weight in the net to vary beyond -.5 to .5, then this
// would not represent the behavior of the net very accurately.
// ASSUMPTION: in init_upper_subnet, the faulty line could be at ANY of
// the maxnet lines, including the self connection.
// ASSUMPTION: in init_upper_subnet again, the value of the faulty line
// ranges over the entire spectrum from -1 to 1, since these are valid
// values that the net is programmed with (self con=1, all others equal
// -EPSILON).  If this is not really possible, the simulation is again not
// going to mimic real faults very accurately.
// ASSUMPTION: the corruption in init_with_unknown_pattern affects an
// entire output for some exemplar.  originally, the exemplar's output
// took on a random value over the entire range for an output (N/2 to -N/2),
// but this caused ...?
// the same warning about real life applies.  the output thus has nothing
// to do with any of the maxnet lines; the error is totally unrelated to
// the inputs that the output usually considers.

//--------------------------------------------------------------------------
// Revision History:
// 3/1992-4/1992: modified by Chris Koeritz.
// the program was made useable for the EE734 Fault Tolerance Project.
// this meant numerous revisions.  the prior program structure
// was mostly tossed in favor of mimicking lippmann's exact
// algorithm.  this led to a result much like lippman's, whereas
// the prior version of this program was _very_ different from what
// lippmann described, to the point of ignoring the value for theta.
//--------------------------------------------------------------------------
// modified for interactive input patterns - Marilyn Nelson, Feb. 1991
// c version of the hamming net, david leasure, 9/25/87
// this routine is a hamming classification network
// described in IEEE ASSP April 1987 by Richard P. Lippmann pg. 9
// correcting for a presumed bug in the presented routine
// the bug is the value set for THETA by Lippmann. When THETA is
// N / 2 it so overwhelms the outputs from the lower net that only 0
// activation values are passed up from the threshold function.
// I have chosen to set epsilon to 1 / 2M and to not have an upper
// limit on the threshold function so no saturation occurs
// the program is somewhat inefficient because of the use of
// data storage for maxnet (t[k,l] in lippman's) and for output[t,M]
// but they could be useful in a simulator of this network which allowed
// things to be fiddled with.
// the code could be improved by not encoding the size and values
// of the node matrices directly, too, reading them instead from files
// and/or a user interface.
//
// if you improve the code, please send me the diff's
// david e. leasure
// ihnp4!homxc!del or del@homxc.att.com

#endif

---