// BCH (15,5)  in GF(2^4) over 1+a+a^4  and t=3 

import java.awt.*;
import java.awt.event.*;
import java.applet.*;

public class BCH extends Applet
{

   // BCH coding constants
   final int N = 15;      // length of codeword
   final int K = 5;      // length of information 
   final int T = 3;      // number of correctable errors
          // degree of gx == N-K
   final BinaryPoly gx = new BinaryPoly(10, new Integer[] {new Integer(1),new Integer(1),new Integer(1),new Integer(0),new Integer(1),new Integer(1),new Integer(0),new Integer(0),new Integer(1),new Integer(0),new Integer(1) });  
   final BinaryPoly hx = new BinaryPoly(5, new Integer[] {new Integer(1),new Integer(1),new Integer(0),new Integer(1),new Integer(0),new Integer(1) });    

   Button send = new Button("Send Data");
   TextField field = new TextField(20); 
   TextField errfield = new TextField(20);
   TextArea text = new TextArea("BCH("+N+","+K+
				") Encoder/Decoder\n==================\n",
				22, 40,TextArea.SCROLLBARS_VERTICAL_ONLY);
   Label descrip = new Label("Enter a "+K+"-bit Binary String:    Enter a "+
			     N+"-bit error pattern:"); 


   String encode;
   char[] encodechars = new char[K]; 
   char[] errorchars = new char[N];
   BinaryPoly ix=new BinaryPoly(K-1);      // information polynomial
   BinaryPoly cx=new BinaryPoly(N-1);      // codeword polynomial
   BinaryPoly ex=new BinaryPoly(N-1);      // actual error polynomial
   BinaryPoly rx=new BinaryPoly(N-1);      // recieved polynomial
   BinaryPoly dx=new BinaryPoly(N+K-1);    // decoded polynomial
   AlphaPoly sigmax=new AlphaPoly(T);      // error-locator polynomial
   Alpha [] syn=new Alpha[2*T];    	   // syndrome

    public void init()
    {       
        setBackground(Color.lightGray);
	setLayout(new BorderLayout());
	field.setBackground(Color.pink);
	errfield.setBackground(Color.cyan);
	text.setBackground(Color.white);
        add(descrip,"North");
	add(field,"West");
	add(errfield,"Center");
	add(send,"East");
	add(text,"South");

	field.setText(ix.getString());
	errfield.setText(ex.getString());

	send.addActionListener( new ActionListener() {
      public void actionPerformed(ActionEvent e)
	{
	 text.append("Sending Information Polynomial...\n");
	 
	 field.getText().getChars(0,K,encodechars,0);	 
	 errfield.getText().getChars(0,N,errorchars,0);
	 for (int j = 0; j < K; j++)
	   {
	     if ((encodechars[j] == '0') || (encodechars[j] == '1'))
	       ix.set( new Integer(Character.digit(encodechars[j],2)), j); 
	     else
	       {  text.append("Error Parsing Information\n");  
	          break; 
	       }
	   }
	 
	 for (int j = 0; j < N; j++)
	   {
	     if ((errorchars[j] == '0') || (errorchars[j] == '1'))
	       ex.set( new Integer(Character.digit(errorchars[j],2)), j); 
	     else
	       {  text.append("Error Parsing Error Pattern\n");  
	          break; 
	       }
	   }

	 text.append("Information Poly: ");
	 ix.printPoly(text);
	 //text.append("Generator Poly: ");
	 //gx.printPoly(text);

	 // endode ix
	 text.append("Encoding Information: c(x) = i(x)*g(x)\n");
	 cx = multPoly(ix, gx);  
	 
	 text.append("Codeword Poly: ");
	 cx.printPoly(text);
	 
	 text.append("<---\nTransmitting Code:  r(x) = c(x) + e(x)\n");
	 text.append("Error in Transmission: ");
	 ex.printPoly(text);
	 text.append("--->\nReceivied Code: ");
	 rx = addPoly(cx, ex);
	 rx.printPoly(text);

	 // decode
	 //text.append("Decoding Information:  r(x)*h(x)\n");
	 //text.append("Decoding Result: ");
	 //dx = multPoly(rx, hx);
	 //dx.printPoly(text);
	 //text.append("Data: " + dx.getString()+"\n");
	 
	 text.append("Syndrome Calculation: [");
	 for (int j=0; j < 2*T; j++)
	   {
	   syn[j] = evaluate(rx, new Alpha(j+1));
	   syn[j].print(text);
	   if (j != 2*T-1)
	      text.append(", ");
	   } 
	 text.append("]\n~~~~~~~~~~~~~~~~\n Begin the Berlekamp-Massey Algorithm  \n");
	 
	   // Berlekamp-Massey algorithm
	 //setup initial conditions
	 AlphaPoly sig[] = new AlphaPoly[2*T+2];
	 int [] l = new int[2*T+2];
	 int [] k = new int[2*T+2];
	 Alpha [] d = new Alpha[2*T+1];
	 sig[0] = new AlphaPoly(new Alpha(0), 0);  // sig0 = 1
	 sig[1] = new AlphaPoly(new Alpha(0), 0);  // sig1 = 1
	 l[0] = 0;  
	 l[1] = 0;
	 d[0] = new Alpha(0);
	 try { d[1] = (Alpha)syn[0].clone(); } catch (Exception excepetion) { }
	 // k[0] is never accessed
	 k[1] = -1;
	 
	 for (int n=1; n < (2*T+1); n++)
	   {
	   if ( d[n].isZero() )
	   	{
	   	sig[n+1] = sig[n];	   
	   	l[n+1] = l[n];
	   	k[n+1] = k[n];
	   	}
	   else
	   	{
	   	AlphaPoly temp = new AlphaPoly(multAlpha(d[n],(d[(k[n]+1)]).inverse()),(n-1-k[n])); 
	   	AlphaPoly ttt = multAlphaPoly(temp, sig[(k[n]+1)]);
	   	sig[n+1] = addAlphaPoly(sig[n], ttt);
	   	
	   	l[n+1] = (l[n] >= (n - 1 - (k[n] - l[(k[n])+1]))) 
	   		? l[n] : (n - 1 - (k[n] - l[(k[n])+1]));
	   	if (l[n+1] == l[n])
	   	   k[n+1] = k[n];
	   	else
	   	   k[n+1] = n - 1;
	   	}
	   
	   if (n == 2*T)  break;
	   
	   d[n+1] = syn[n];
	   for (int i=1; i <= n; i++)
	      {
	      Alpha t3 = (Alpha)(sig[n+1].get(i));
	      Alpha temp2 = multAlpha((Alpha)(sig[n+1].get(i)),syn[n-i]);
	      d[n+1] = addAlpha(temp2 , d[n+1]);
	      }
	   text.append(" Iteration number "+n+"\nsigma["+n+"](x) = ");		   
	   sig[n+1].printPoly(text);
	   text.append(" l["+(n+1)+"] is "+l[n+1]+"  and k["+(n+1)+"] is "+k[n+1]+"\n d_n is ");
	   d[n+1].print(text);
	   text.append("     and d_kn is ");   
	   d[(k[n+1]+1)].print(text);
	   text.append("\n~~~~~~~~~~~~~\n");	   
	   }
	 sigmax = sig[2*T];
	 text.append("Error Locator Polynomial sigma(x) = ");	   
	 sigmax.printPoly(text);

	 text.append("\nFinding roots of sigma(x) \n");
	 BinaryPoly calcex=new BinaryPoly(N-1);  // calculated error polynomial
	 
	 for (int i = 0; i < sigmax.getDegree();i++)
	    for (int j=0; j < 15; j++)
	      if ( (evaluateAlphaPoly( sigmax, new Alpha(j) ) ).isZero() )
	           {
	           Alpha temp = new Alpha(j);
	           temp = temp.inverse();
	           calcex.set(new Integer(1), temp.getPower());
	           }
	           
	 text.append("Calculated Error Location Polynomial: ");
	 calcex.printPoly(text);
	 text.append("Correcting Errors in r(x) : r(x) + e(x) \n");
	 BinaryPoly correctedrx = addPoly(calcex, rx);
	 correctedrx.printPoly(text);
	 text.append("Decoding Information:  corrected_r(x)*h(x)\n");
	 text.append("Decoding Result: ");
	 dx = multPoly(correctedrx, hx);
	 dx.printPoly(text);
	 
	 text.append("Data Poly: ");
	 text.append(dx.getString() + "\n");
	 text.append("Transimitted Info Bits: "+dx.getString().substring(0, 5) );

	 text.append("\n----------------------------------------\n");
	}
	});
     
   }

//---------------------------------------------------

private Alpha evaluateAlphaPoly(AlphaPoly p, Alpha a)
  {
    EvaluatedPoly total = new EvaluatedPoly();
    Alpha tempa;

    for (int j=0; j <= p.getDegree();j++)
      {
	try {  tempa = (Alpha)a.clone(); }  
	catch (Exception e) {  tempa = a;  }
	
	if (!(((Alpha)p.get(j)).isZero()))
	  {
	    tempa.toThe(j);
	    tempa = multAlpha(tempa, (Alpha)p.get(j));
	    total = addEvaluatedPoly(total, tempa.lookup()); 
	  }
      }
    return total.lookup();
  }


private Alpha evaluate(BinaryPoly p, Alpha a)
  {
    EvaluatedPoly total = new EvaluatedPoly();
    Alpha tempa;

    for (int j=0; j <= p.getDegree();j++)
      {
	try {  tempa = (Alpha)a.clone(); }  
	catch (Exception e) {  tempa = a;  }
	
	if (((Integer)p.get(j)).intValue() != 0)
	  {
	    tempa.toThe(j);
	    total = addEvaluatedPoly(total, tempa.lookup()); 
	  }
      }
    return total.lookup();
  }

private EvaluatedPoly addEvaluatedPoly(EvaluatedPoly p1, EvaluatedPoly p2)
  {
  EvaluatedPoly ans = new EvaluatedPoly();  

  for (int j=0; j <= ans.getDegree(); j++)
      ans.set(new Integer((((Integer)p1.get(j)).intValue() + ((Integer)p2.get(j)).intValue()) % 2), j);

  return ans;
  }

private BinaryPoly addPoly(BinaryPoly p1, BinaryPoly p2)
  {
    // degree of answer is max of degrees of each poly
  int degans = (p1.getDegree() > p2.getDegree()) 
                      ? p1.getDegree() : p2.getDegree();
  BinaryPoly ans = new BinaryPoly(degans);  

  for (int j=0; j <= degans; j++)
      ans.set(new Integer((((Integer)p1.get(j)).intValue() + ((Integer)p2.get(j)).intValue()) % 2), j);

  return ans;
  }

private BinaryPoly multPoly(BinaryPoly p1, BinaryPoly p2)
  {
  int degans = p1.getDegree()+p2.getDegree();
  BinaryPoly ans = new BinaryPoly(degans);
  BinaryPoly plargest, psmallest;

  if (p1.getDegree() > p2.getDegree())
    { plargest = p1;
      psmallest = p2; }
  else
    { plargest = p2;
      psmallest = p1; }

  for (int j=0; j <= psmallest.getDegree(); j++)
    {
    if (((Integer)psmallest.get(j)).intValue() !=0)
      {
      BinaryPoly temp = (BinaryPoly)plargest.shiftRight(j);
      ans = addPoly(temp, ans);
      }
    }

  return ans;
  }
  
private AlphaPoly addAlphaPoly(AlphaPoly p1, AlphaPoly p2)
  {
    // degree of answer is max of degrees of each poly
  int degans = (p1.getDegree() > p2.getDegree()) 
                      ? p1.getDegree() : p2.getDegree();
  AlphaPoly ans = new AlphaPoly(degans);  

  for (int j=0; j <= degans; j++)
      ans.set(addAlpha((Alpha)p1.get(j), (Alpha)p2.get(j)), j);

  return ans;
  }
  
private AlphaPoly multAlphaPoly(AlphaPoly p1, AlphaPoly p2)
  {
  int degans = p1.getDegree()+p2.getDegree();
  AlphaPoly ans = new AlphaPoly(degans);
  AlphaPoly plargest, psmallest;

  if (p1.getDegree() > p2.getDegree())
    { plargest = p1;
      psmallest = p2; }
  else
    { plargest = p2;
      psmallest = p1; }
      
  for (int j=0; j <= psmallest.getDegree(); j++)
    {
    if (!(((Alpha)psmallest.get(j)).isZero()))
      {
      AlphaPoly temp = (AlphaPoly)plargest.shiftRight(j);
      for (int i=0; i <= temp.getDegree(); i++)
      	  temp.set( multAlpha((Alpha)(temp.get(i)), (Alpha)(psmallest.get(j)) ), i); 
         
      ans = addAlphaPoly(temp, ans);
      }
    }
  return ans;
  }

private Alpha addAlpha(Alpha a1, Alpha a2)
  {
  EvaluatedPoly p;
  p = addEvaluatedPoly(a1.lookup(), a2.lookup());
  return p.lookup();
  }

private Alpha multAlpha(Alpha a1, Alpha a2)
  {
  if ((a1.isZero()) || (a2.isZero()))
	return new Alpha(Integer.MIN_VALUE);
  else
	return new Alpha(a1.getPower() + a2.getPower());      
  }

}