/* Find a Hamming-type code of specified radius, size, and number of codewords */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define CORRECTS 2
#define RADIUS  2*CORRECTS+1
#define NUMWORDS 4		/* Number of codewords */
#define NUMBITS 11		/* must be at most 31 */
#define N  (1<<NUMBITS)

typedef struct { unsigned int bits; int active; } Codeword;


/* Return the Hamming distance between two integer-sized bit strings */
int
dist(unsigned int x, unsigned int y)
{
  unsigned int z;
  int d;
  z = x^y;			/* Exclusive-or leaves 1 bits at differences */
  d=0;
  while(z>0) {
    d += z & 0x1;		/* add 1 to d for each 1 bit */
    z >>= 1;
  }
  return d;
}

void
tobinary(unsigned int x)
{
  int i;
  for(i=NUMBITS-1; i>=0; i--)
    if((x>>i) & 0x1) putchar('1');
    else putchar('0');
  printf(" (base 2)");

}

int
main(void)
{
  int n, j, m[4];
  Codeword *code;

  code = (Codeword *)malloc(N*sizeof(Codeword));  assert(code);

  /* Initialize the codeword array */
  for(n=0; n<N; n++) {
    code[n].bits = (unsigned int)n;
    code[n].active = TRUE;
  }

  m[0] = 0;
  for(j=0; j<NUMWORDS-1; j++) {
    for(n=m[j]+1; n<N; n++)
      if( dist( code[m[j]].bits, code[n].bits ) <= RADIUS )
	code[n].active = FALSE;	/* throw out nearby codewords. */
    for(n=m[j]+1; n<N; n++)
      if( code[n].active ) {
	m[j+1] = n;
	break;
      }
  }

  for(j=0; j<NUMWORDS; j++) {
    printf("Codeword %3d: %10u = ", j, code[m[j]].bits);
    tobinary(code[m[j]].bits);
    putchar('\n');
  }

  free(code);
  return 0;
}