DOWNLOAD - VHDL files, test .do files for testing using ModelSIM. Also find the Xilinx Project files (including the bit file) for implmentation in Nexys 2 SPARTAN 3E FPGA board.
The different modules that are used to implement parallel prefix based sequence matching
This module has already been described earlier. It is the basic block of parallel prefix method. The module is tested with the test_node.do file. The output of this simulation is shown below
Note the maximum of x_input and y_input is found and given to x_output when dup_en=0 and x_input is given to x_output when dup_en = 1, signed comparison is done between the two inputs.
- Random access memory is used to store scoring matrix
- table entries
A RAM of 8x64 bits is defined in the RAM. The inputs are clk, we, en, addr, di and output is do. A read is done when en =1 and an address is given. Read is done in the rising edge of clock. A write can be done by loading a value in the di input of the module and a address in addr input and making high both en and we inputs. Writing into the address is also done in the rising edge of the clock.
Inputs are inA, inB, add_en. Outputs are sum, overflow.Signed addition of inputs inA, inB. The inputs are added only when add_en=1 . The sum is given in sum output and an overflow output is also present. The overflow has no use in this module but might be useful later. The test file is test_adder.do
This module is used to obtain the values of z[j]s using scoring matrix and the previous table entries. The test file for this module is test_w_calc.do. The simulated results are as shown
Table_entry_prev is used to store the previous table entry. Scoring matrix value is present in the variable scoring_matrix_value.
T[i-1,j-1] + f(ai , bj) is represented by table_entry_plus_score
5. Parallel Prefix
Counter_2bit is used as a reference for pipelining. At 00 falling edge, values are loaded into the x_ram for parallel prefix operation. At 00 note the values loaded into the x_ram. As parallel prefix proceeds, the maximum values for each stage is shown by x_ram values for counter_2bit values of 01, 10. At counter_2bit = 11 we note the values in x_ram are arranged as required. The maximum value among the 8 inputs is present in x_ram(7).
Thus concludes the parallel prefix implementation of Biological Sequence Alignment using FPGA. Thank you,