'
' Hamming.Make
'
' SELF: m: Code will be linear(2^m-1, 2^m-1-m)
'          m > 1.
'
' Returns: {
'   Generator matrix:  List of bitmaps representing rows of [G|I]
'   Parity matrix:     List of bitmaps representing entire rows of H
' }
'
' AV 3.2a
' William A. Huber
' 9 January 2002
' (C) 2002 Quantitative Decisions.  All rights reserved.
'
' Examples:
'   m=3:       m=4:
'H) 100 1101   1000 10111010101
'   010 1011   0100 01110110011
'   001 0111   0010 11100001111
'              0001 00001111111
'
'G) 110        1010
'   101        0110
'   011        1110
'   111        1100
'              1001
'              0101
'              1101
'              0011
'              1011
'              0111
'              1111
'======================================================================'
m = SELF
n = 2^m-1
av.Run("MsgBox.Status",{"n,m:"++n.AsString+","++(n-m).AsString,Script.The.GetName})

'
' Compute the parity-check matrix, H.  Its columns start out as
' all the nonzero binary numbers from 1 through 2^m-1.  They are
' then systematically permuted to put the identity matrix on the
' left hand side, meaning that the first m bits are message bits
' and the remaining 2^m-1-m bits are check bits.
'
kInc = 1
lBmpH = {}
for each i in 0..(m-1)
'
' Create row i.  Represent it as a bitmap.
'
  bmpH = Bitmap.Make(n)
  lBmpH.Add(bmpH)
  '
  ' Initialize row i.
  '
  for each jBit in kInc-1..n by (2*kInc)
  '
  ' Set bits jBit, jBit+1, ..., jBit+kInc-1.
  '
    bmpH.SetRange(jBit,kInc)
  end
  kInc = kInc*2
end
'
' Put H in row-reduced echelon form.
'
j = 0
for each i in 0..(m-1)
  if (i<>j) then
    '
    ' Swap columns i and j.
    '
    for each bmpH in lBmpH
      isOn = bmpH.Get(i)
      if (bmpH.Get(j)) then
        bmpH.Set(i)
      else
        bmpH.Clear(i)
      end
      if (isOn) then
        bmpH.Set(j)
      else
        bmpH.Clear(j)
      end
    end
  end
  j = 2*j+1
end
'
' Compute the generator matrix in the form [G|I]
' where G is an n-m by m matrix.
'
lBmpG = {}
for each i in 0..(n-m-1)
  bmpG = Bitmap.Make(m)
  lBmpG.Add(bmpG)
  '
  ' Copy the m+ith column of H.
  '
  for each j in 0..(m-1)
    if (lBmpH.Get(j).Get(i+m)) then
      bmpG.Set(j)
    end
  end
end
return {lBmpG,lBmpH}
' end of script