import java.io.*; import java.math.*; import java.lang.Math.*; import java.lang.String.*; import byucc.jhdl.base.*; import byucc.jhdl.Xilinx.*; import byucc.jhdl.Xilinx.XC4000.*; import byucc.jhdl.Logic.*; /* This is the top level code for finding the evolutionary distance between a target string which is compiled into the hardware, and a source string which is passed through the linear systolic array of character comparitors. */ public class edistance2 extends Logic { public static CellInterface[] cell_interface = { in( "char_in", 4 ), out( "edist", "wid" ), param( "wid", INTEGER ) }; /* This single constructor takes a 4 bit wire which represents the one-hot encoded characters or the source string and the output wire of appropriate width for the distance. The Target string is passed to the constructor as well and is compiled into the hardware. */ public edistance2(Node parent, Wire char_in, Wire edist, String target) { // you must do this first super(parent); // Get the width of the target string. int width = target.length(); // use the target string width to determine the maximum # of bits needed for the counter. int count_wid = (int) (Math.log((double)2*width) / Math.log(2.0)) +1; // Wire arrays for interconnecting bit slices in the systolic path. Wire[] horizontal_dist = new Wire[width+1]; Wire[] horizontal_char = new Wire[width+1]; Wire[] reset = new Wire[width+1]; // now that we know the maximum width of edist, bind the parameter wid. // This must be done before you connect up ports. bind( "wid", count_wid); // Connect up the ports. connect("char_in", char_in); connect("edist", edist); // Construct the first wires horizontal_dist[0] = wire(1, "horizontal_dist0"); horizontal_char[0] = wire(4, "horizontal_char0"); reset[0] = wire(1, "reset0"); // The Left_edge of the processors creates the reset, and initializes the horizontal distance new left_edge2(this, char_in, horizontal_dist[0], reset[0], horizontal_char[0]); // For each character in the target string, create a bit slice // And connect the intermediate wires for (int i=1;i<=target.length();i++) { horizontal_dist[i] = wire(1, "horizontal_dist"+ i); horizontal_char[i] = wire(4, "horizontal_char"+ i); reset[i] = wire(1, "reset" + i); new char_slice2(this, reset[i-1], horizontal_char[i-1], horizontal_dist[i-1], reset[i], horizontal_char[i], horizontal_dist[i], target.charAt(i-1)); } // This is a modulo 4 counter that counts up from target_string length if horizonal_dist // is asserted and down otherwise. new mod4count2(this, width, reset[width], horizontal_dist[width], edist); } // The compute method uses a dynamic programming algorithm to find // the evolutionary distance in software. This is helpful when debugging. public static int compute(String tar, String sor) { int i,j; int width = tar.length(); int[][] results = new int[width+1][width+1]; System.out.println("comparing " + tar + " " + sor); for (i=0;i<=width;i++){ results[0][i] = i; results[i][0] = i; } for (i=1;i<=width;i++){ for (j=1;j<=width;j++){ results[j][i] = results[j-1][i-1]; if(results[j-1][i] > results[j-1][i-1]) { if(results[j][i-1] > results[j-1][i-1]) { if((tar.charAt(i-1) == sor.charAt(j-1)) || (tar.charAt(i-1) == 'n') || (sor.charAt(j-1) == 'n') || ((tar.charAt(i-1) == 'y') && ((sor.charAt(j-1) == 't') || (sor.charAt(j-1) == 'c'))) || ((sor.charAt(j-1) == 'y') && ((tar.charAt(i-1) == 't') || (tar.charAt(i-1) == 'c'))) || ((tar.charAt(i-1) == 'r') && ((sor.charAt(j-1) == 'a') || (sor.charAt(j-1) == 'g'))) || ((sor.charAt(j-1) == 'r') && ((tar.charAt(i-1) == 'a') || (tar.charAt(i-1) == 'g')))){ results[j][i] = results[j-1][i-1]; } else{ results[j][i] = results[j-1][i-1] + 2; } } } } } for (i=0;i<=width;i++){ for (j=0;j<=width;j++){ System.out.print("\t " + results[i][j]); } System.out.print("\n"); } // return the bottom right corner of the table, or the final e distance. return(results[width][width]); } }