Question: Please, anyone can help by getting the ASM chart for this code? // Code your design here //Lee algorithm // The following outputs [state, push,

Please, anyone can help by getting the ASM chart for this code?

// Code your design here //Lee algorithm // The following outputs [state, push, pop, empty, push_node, pop_node, xy] are // for verification purpose only module lee(input reset, clk, start, input [7:0] src_in, dst_in, input [255:0] mat_in, output reg done, output reg [7:0] distance, output [2:0] state, output [7:0] push, pop, output empty, output [7:0] push_node, output [15:0] pop_node, output [7:0] xy); reg [7:0] src, dst, push, pop; reg [0:255] mat, visited; reg [15:0] q [0:255]; reg [15:0] pop_node; reg [7:0] push_node; wire empty; reg [2:0] state; parameter [2:0] s0=0, s1=1, s2=2, s3=3, s4=4, s5=5, s6=6, s7=7; //temporary var to calculate 4 neighboring nodes //here I use x for row, y for column reg [4:0] x, y; reg [7:0] xy, inc_dist; //q is empty when push == pop (both pointing to the same location in the queue) assign empty = (push == pop); //coded as fsmd always@(posedge clk, posedge reset) begin if(reset) state <= s0; else case(state) s0: if(start) begin src <= src_in; dst <= dst_in; mat <= mat_in; push <= 0; pop <= 0; visited <= 0; distance <= 0; done <= 0; state <= s1; end s1: begin //push the src into q, distance=0 q[push] <= {src, 8'h00}; //as the src is in the queue, the visited flag is set visited[src] <= 1; //push pointer is pointing the next available push slot push <= push + 1; state <= s2; end s2: if (empty) begin done <= 1; state <= s0; end else begin //pop node to a register called pop_node pop_node <= q[pop]; //pop increment (chasing the push pointer) pop <= pop + 1; state <= s3; end s3: begin //if the popped node == dst, the quit, distance found. if (pop_node[15:8] == dst) begin done <= 1; distance <= pop_node[7:0]; state <= s0; end else state <= s4; end s4: begin //this checks (x,y-1) - westward x = {1'b0,pop_node[15:12]}; //this checks if y=0, going westward is invalid y = {1'b0,pop_node[11:8]}-1; //the {x,y} index xy = {x[3:0],y[3:0]}; inc_dist = pop_node[7:0] + 1; state <= s5; //if valid unsearched neighbor is found, push to queue if ((y[4] == 0) && (visited[xy]==0) && (mat[xy]==1)) begin q[push] <= {xy,inc_dist}; visited[xy] <= 1; push <= push + 1; push_node <= xy; end end s5: begin //this checks (x,y+1) - east x = {1'b0,pop_node[15:12]}; y = {1'b0,pop_node[11:8]}+1; xy = {x[3:0],y[3:0]}; inc_dist = pop_node[7:0] + 1; state <= s6; if ((y[4] == 0) && (visited[xy]==0) && (mat[xy]==1)) begin q[push] <= {xy,inc_dist}; visited[xy] <= 1; push <= push + 1; push_node <= xy; end end s6: begin //this checks (x-1,y) - north x = {1'b0,pop_node[15:12]}-1; y = {1'b0,pop_node[11:8]}; xy = {x[3:0],y[3:0]}; inc_dist = pop_node[7:0] + 1; state <= s7; if ((x[4] == 0) && (visited[xy]==0) && (mat[xy]==1)) begin q[push] <= {xy,inc_dist}; visited[xy] <= 1; push <= push + 1; push_node <= xy; end end s7: begin //this checks (x+1,y) - south x = {1'b0,pop_node[15:12]}+1; y = {1'b0,pop_node[11:8]}; xy = {x[3:0],y[3:0]}; inc_dist = pop_node[7:0] + 1; state <= s2; if ((x[4] == 0) && (visited[xy]==0) && (mat[xy]==1)) begin q[push] <= {xy,inc_dist}; visited[xy] <= 1; push <= push + 1; push_node <= xy; end end endcase end endmodule

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!