/*********************************************************** VeriLab 5 FINITE AUTOMATA: THE COMPLEX COMMAND OR CONTROL AUTOMATA ************************************************************/ /* The complex automata have the loop closed through a random combinational circuit. Their description have the dimension in the same magnitude order as the dimension of the random circuits that drive their autonomous behaviors. If an automaton behaves in a complex way then its structural complexity follows the behavioral complexity. They are colled 'finite' because have a finite description even the received input strings are infinite. In the same time the state space is finite because it can't grow as for the simple automata where the dimension of the definition were constant and independent by the state space dimension. */ /*************** PROBLEM NO.1: Automaton for semaphors In the crosing point of two streets, a and b, there is a semaphor. The trafic on the street a is indicated by the value 1 of variable tr_a and for the trafic on the street b we have the variable tr_b. If green = 1, then the cross is accessible for the trafic from the street a. If green = 0, then the cross is accessible for the trafic from the street b. The clock of the automaton that triggers the semaphor has a peroid of 4 second. (let be 4 time units in our simulator). The semaphor stayes 20 seconds on red/green and only 4 seconds on yelow. How behave the automaton? - if no trafic on both directions the light will changes - if trafic on both directions the light also will change - if trafic only on the not allowed directions the ligth will change - if trafic only on the allowed direction the light will not change. */ ///* module trafic_light_aut(green, yellow, red, tr_a, tr_b, reset, clock); input tr_a, // trafic on the direction a tr_b, // trafic on the direction b reset, clock; output green, yellow, red; // each output activates one collor reg green, yellow, red; // variable used to compute the outputs reg[3:0] state_reg, // the state register; will be synthetized as an actual register next_state; // the variable used to compute the next state always @(state_reg or tr_a or tr_b) case (state_reg) 4'b0000: {next_state, green, yellow, red} = {4'b0001, 1'b0, 1'b1, 1'b0}; // the cross must be evacuated 4'b0001: {next_state, green, yellow, red} = {4'b0010, 1'b0, 1'b0, 1'b1}; // free for cars from the street b 4'b0010: {next_state, green, yellow, red} = {4'b0011, 1'b0, 1'b0, 1'b1}; 4'b0011: {next_state, green, yellow, red} = {4'b0100, 1'b0, 1'b0, 1'b1}; 4'b0100: {next_state, green, yellow, red} = {4'b0101, 1'b0, 1'b0, 1'b1}; 4'b0101: if (~tr_a && tr_b) // no trafic on a and trafic on b: light must not change {next_state, green, yellow, red} = {4'b0001, 1'b0, 1'b0, 1'b1}; // the light remains red else {next_state, green, yellow, red} = {4'b1010, 1'b0, 1'b0, 1'b1}; // trafic will change 4'b1010: {next_state, green, yellow, red} = {4'b1011, 1'b0, 1'b1, 1'b0}; 4'b1011: {next_state, green, yellow, red} = {4'b1100, 1'b1, 1'b0, 1'b0}; // free for cars from the street a 4'b1100: {next_state, green, yellow, red} = {4'b1101, 1'b1, 1'b0, 1'b0}; 4'b1101: {next_state, green, yellow, red} = {4'b1110, 1'b1, 1'b0, 1'b0}; 4'b1110: {next_state, green, yellow, red} = {4'b1111, 1'b1, 1'b0, 1'b0}; 4'b1111: if (tr_a && ~tr_b) // no trafic on b and trafic on a: light must not change {next_state, green, yellow, red} = {4'b1011, 1'b1, 1'b0, 1'b0}; // the light remains green else {next_state, green, yellow, red} = {4'b0000, 1'b1, 1'b0, 1'b0}; // trafic will change endcase always @(posedge clock) if (reset) state_reg = 0; else state_reg = next_state; endmodule module trafic_aut_test; reg tr_a, tr_b, reset, clock; wire green, yellow, red; initial begin clock = 0; forever #2 clock = ~clock; end initial begin reset = 1; {tr_a, tr_b} = 2'b00; #4 reset = 0; #30 {tr_a, tr_b} = 2'b01; #50 {tr_a, tr_b} = 2'b10; #90 {tr_a, tr_b} = 2'b11; #90 $stop; end trafic_light_aut dut(green, yellow, red, tr_a, tr_b, reset, clock); initial $monitor("time=%0d clock=%b trafic=%b state=%b color=%b", $time, clock, {tr_a, tr_b}, dut.state_reg, {green, yellow, red}); endmodule //*/ /*************** PROBLEM NO.2: Automaton of recognizing a regular sequences having the following form: 'aa...acbb...b' (a number of a's folowed by a c and a number of b's). The null symbol is e. Any sequence is preceded by at least one e and is followed by at least one e. After reset, automaton wait a sequence to start and 'clasifies' each sequence that follows by 'good_sequence' or 'bad_sequence'. */ /* module rec_aut(out, in, reset, clock); input reset, clock; input[1:0] in; output[2:0] out; reg[2:0] state_reg, next_state, out; // Input codes parameter a = 2'b00, b = 2'b01, c = 2'b10, e = 2'b11; // State codes parameter q0 = 3'b000, q1 = 3'b001, q2 = 3'b010, q3 = 3'b011, q4 = 3'b100; // Output codes parameter waiting_end = 3'b000, waiting_start = 3'b001, working = 3'b111, found_bad = 3'b010, found_good = 3'b100; always @(state_reg or in) case (state_reg) q0: if (in == e) {next_state, out} = {q1, waiting_start}; else {next_state, out} = {q0, waiting_end}; q1: case (in) a: {next_state, out} = {q2, working}; // arrived the first a b: {next_state, out} = {q0, found_bad}; c: {next_state, out} = {q0, found_bad}; e: {next_state, out} = {q1, waiting_start}; endcase q2: case (in) a: {next_state, out} = {q2, working}; // follows many a's b: {next_state, out} = {q0, found_bad}; c: {next_state, out} = {q3, working}; // arrived the c e: {next_state, out} = {q1, found_bad}; endcase q3: case (in) a: {next_state, out} = {q0, found_bad}; b: {next_state, out} = {q4, working}; // arrived the first b c: {next_state, out} = {q0, found_bad}; e: {next_state, out} = {q1, found_bad}; endcase q4: case (in) a: {next_state, out} = {q0, found_bad}; b: {next_state, out} = {q4, working}; // follows many b's c: {next_state, out} = {q0, found_bad}; e: {next_state, out} = {q1, found_good}; // hitt endcase endcase always @(posedge clock) if (reset) state_reg = 0; else state_reg = next_state; endmodule module test_rec_aut; reg reset, clock; reg[31:0] right_shift_reg; wire[2:0] out; parameter a = 2'b00, b = 2'b01, c = 2'b10, e = 2'b11; initial begin reset = 1; #2 reset = 0; #40 $stop; end initial begin clock = 0; forever #1 clock = ~clock; end always @(posedge clock) begin if (reset) right_shift_reg = {e,e,a,a,a,a,c,b,b,b,b,b,b,b,e,e}; //if (reset) right_shift_reg = {b,c,e,e,a,a,c,b,b,b,b,b,b,b,e,e}; //if (reset) right_shift_reg = {e,e,a,a,a,a,b,b,b,b,b,b,b,e,e,e}; //if (reset) right_shift_reg = {e,e,a,a,a,a,c,b,b,a,b,b,b,e,e,e}; else right_shift_reg = {right_shift_reg[29:0], right_shift_reg[31:30]}; case (out) 3'b000: $display("waiting_end"); 3'b001: $display("waiting_start"); 3'b111: $display("working"); 3'b010: $display("found_bad"); 3'b100: $display("found_good"); endcase end rec_aut dut(out, right_shift_reg[31:30], reset, clock); endmodule */ /*************** PROBLEM NO.3: Electronic key There is a keyboard with 11 contacts: init, s0, s1, ... s9. The correct sequence, that allows the access, is: 'init s1 s7 s2 s4' If the 'init' is tuched it is triggered a signal wich remanis active 5 seconds. The next 4 signals must be strictly included in this time interval without any overlaps and without another input activated in the same interval. If the code is introduced correctly, then the signal 'go' is generated. After one unsuccesful trials the automaton remains in a particular state generating 'alarm'. From this state the automaton must be restarted. The restart signal is accesible only for the 'administrator' of the system. All the inputs are synchronized with the clock. */ /* module el_key(go, alarm, clock, restart, init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9); input clock, restart, init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9; output go, alarm; reg[1:0] out; reg[3:0] state_reg, next_state; reg go, alarm; wire[10:0] signals; // States coding parameter q0 = 4'b0000, q1 = 4'b0001, q2 = 4'b0010, q3 = 4'b0011, q4 = 4'b0100, q5 = 4'b0101, q6 = 4'b0110, q7 = 4'b0111, q8 = 4'b1000, q9 = 4'b1001, q10 = 4'b1010, q11 = 4'b1011; // Outputs coding parameter ok = 1'b1, n_ok = 1'b1, n = 1'b0; assign signals = {init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9}; // the combinational circuit that computes 'next_state' and the outputs 'out' always @(state_reg or signals) case (state_reg) q0 : if (init) {next_state, out} = {q1, n, n}; else {next_state, out} = {q0, n, n}; q1 : if (signals == 11'b10000000000) {next_state, out} = {q1, n, n}; else if (signals == 11'b10100000000) {next_state, out} = {q5, n, n}; else {next_state, out} = {q11, n, n}; q2 : if (signals == 11'b10000000000) {next_state, out} = {q2, n, n}; else if (signals == 11'b10000000100) {next_state, out} = {q6, n, n}; else {next_state, out} = {q11, n, n}; q3 : if (signals == 11'b10000000000) {next_state, out} = {q3, n, n}; else if (signals == 11'b10010000000) {next_state, out} = {q7, n, n}; else {next_state, out} = {q11, n, n}; q4 : if (signals == 11'b10000000000) {next_state, out} = {q4, n, n}; else if (signals == 11'b10000100000) {next_state, out} = {q8, n, n}; else {next_state, out} = {q11, n, n}; q5 : if (signals == 11'b10100000000) {next_state, out} = {q5, n, n}; else if (signals == 11'b10000000000) {next_state, out} = {q2, n, n}; else {next_state, out} = {q11, n, n}; q6 : if (signals == 11'b10000000100) {next_state, out} = {q6, n, n}; else if (signals == 11'b10000000000) {next_state, out} = {q3, n, n}; else {next_state, out} = {q11, n, n}; q7 : if (signals == 11'b10010000000) {next_state, out} = {q7, n, n}; else if (signals == 11'b10000000000) {next_state, out} = {q4, n, n}; else {next_state, out} = {q11, n, n}; q8 : if (signals == 11'b10000100000) {next_state, out} = {q8, n, n}; else if (signals == 11'b10000000000) {next_state, out} = {q9, n, n}; else {next_state, out} = {q11, n, n}; q9 : if (signals == 11'b10000000000) {next_state, out} = {q9, n, n}; else if (signals == 11'b0){next_state, out} = {q10, n, n}; else {next_state, out} = {q11, n, n}; q10: {next_state, out} = {q0, ok, n}; q11: {next_state, out} = {q11, n, n_ok}; endcase // results a Moore automaton, because 'out' depends only by the state always @(posedge clock) begin if (restart) state_reg = q0; else state_reg = next_state; {go, alarm} = out; end // we addopted a delayed variant in order to avoid output hazards endmodule module test_key_aut; reg clock, restart, init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9; wire go, alarm; initial begin clock = 0; forever #1 clock = ~clock; end // Simulating the user initial begin restart = 1; {init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9} = 11'b0; #50 restart = 0; init = 1; #50 s1 = 1; #50 s1 = 0; #50 s7 = 1; #50 s7 = 0; #50 s2 = 1; #50 s2 = 0; //#50 s5 = 1; // simulates an erroneous tasting //#50 s5 = 0; #50 s4 = 1; #50 s4 = 0; #50 init = 0; //#100 restart = 1; // restarts after a wrong tasting //#20 restart = 0; #50 $stop; end el_key dut(go, alarm, clock, restart, init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9); initial $monitor("time=%0d input=%b state=%b go=%b alarm=%b", $time, {init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9}, dut.state_reg, go, alarm,); endmodule */ /*************** PROBLEM NO.4: More patient electronic key Remake the same automaton with one change: the automaton switches in 'alarm' state only after two wrong trials. */ /* module el_key(go, alarm, clock, restart, init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9); input clock, restart, init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9; output go, alarm; reg[1:0] out; reg[4:0] state_reg, next_state; reg go, alarm; wire[10:0] signals; // States coding parameter q0 = 5'b00000, q1 = 5'b00001, q2 = 5'b00010, q3 = 5'b00011, q4 = 5'b00100, q5 = 5'b00101, q6 = 5'b00110, q7 = 5'b00111, q8 = 5'b01000, q9 = 5'b01001, q10 = 5'b01010, q11 = 5'b01011, q12 = 5'b01100, q13 = 5'b01101, q14 = 5'b01110, q15 = 5'b01111, q16 = 5'b10000, q17 = 5'b10001, q18 = 5'b10010, q19 = 5'b10011, q20 = 5'b10100, q21 = 5'b10101, q22 = 5'b10110, q23 = 5'b10111; // Outputs coding parameter ok = 1'b1, n_ok = 1'b1, n = 1'b0; assign signals = {init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9}; // the combinational circuit that computes 'next_state' and the outputs 'out' always @(state_reg or signals) case (state_reg) q0 : if (init) {next_state, out} = {q1, n, n}; else {next_state, out} = {q0, n, n}; q1 : if (signals == 11'b10000000000) {next_state, out} = {q1, n, n}; else if (signals == 11'b10100000000) {next_state, out} = {q5, n, n}; else {next_state, out} = {q11, n, n}; q2 : if (signals == 11'b10000000000) {next_state, out} = {q2, n, n}; else if (signals == 11'b10000000100) {next_state, out} = {q6, n, n}; else {next_state, out} = {q11, n, n}; q3 : if (signals == 11'b10000000000) {next_state, out} = {q3, n, n}; else if (signals == 11'b10010000000) {next_state, out} = {q7, n, n}; else {next_state, out} = {q11, n, n}; q4 : if (signals == 11'b10000000000) {next_state, out} = {q4, n, n}; else if (signals == 11'b10000100000) {next_state, out} = {q8, n, n}; else {next_state, out} = {q11, n, n}; q5 : if (signals == 11'b10100000000) {next_state, out} = {q5, n, n}; else if (signals == 11'b10000000000) {next_state, out} = {q2, n, n}; else {next_state, out} = {q11, n, n}; q6 : if (signals == 11'b10000000100) {next_state, out} = {q6, n, n}; else if (signals == 11'b10000000000) {next_state, out} = {q3, n, n}; else {next_state, out} = {q11, n, n}; q7 : if (signals == 11'b10010000000) {next_state, out} = {q7, n, n}; else if (signals == 11'b10000000000) {next_state, out} = {q4, n, n}; else {next_state, out} = {q11, n, n}; q8 : if (signals == 11'b10000100000) {next_state, out} = {q8, n, n}; else if (signals == 11'b10000000000) {next_state, out} = {q9, n, n}; else {next_state, out} = {q11, n, n}; q9 : if (signals == 11'b10000000000) {next_state, out} = {q9, n, n}; else if (signals == 11'b0){next_state, out} = {q10, n, n}; else {next_state, out} = {q11, n, n}; q10: {next_state, out} = {q0, ok, n}; q11: if (init) {next_state, out} = {q11, n, n}; else {next_state, out} = {q12, n, n}; q12: if (init) {next_state, out} = {q13, n, n}; else {next_state, out} = {q12, n, n}; q13: if (signals == 11'b10000000000) {next_state, out} = {q13, n, n}; else if (signals == 11'b10100000000) {next_state, out} = {q17, n, n}; else {next_state, out} = {q13, n, n}; q14: if (signals == 11'b10000000000) {next_state, out} = {q14, n, n}; else if (signals == 11'b10000000100) {next_state, out} = {q18, n, n}; else {next_state, out} = {q23, n, n}; q15: if (signals == 11'b10000000000) {next_state, out} = {q15, n, n}; else if (signals == 11'b10010000000) {next_state, out} = {q19, n, n}; else {next_state, out} = {q23, n, n}; q16: if (signals == 11'b10000000000) {next_state, out} = {q16, n, n}; else if (signals == 11'b10000100000) {next_state, out} = {q20, n, n}; else {next_state, out} = {q23, n, n}; q17: if (signals == 11'b10100000000) {next_state, out} = {q17, n, n}; else if (signals == 11'b10000000000) {next_state, out} = {q14, n, n}; else {next_state, out} = {q23, n, n}; q18: if (signals == 11'b10000000100) {next_state, out} = {q18, n, n}; else if (signals == 11'b10000000000) {next_state, out} = {q15, n, n}; else {next_state, out} = {q23, n, n}; q19: if (signals == 11'b10010000000) {next_state, out} = {q19, n, n}; else if (signals == 11'b10000000000) {next_state, out} = {q16, n, n}; else {next_state, out} = {q23, n, n}; q20: if (signals == 11'b10000100000) {next_state, out} = {q20, n, n}; else if (signals == 11'b10000000000) {next_state, out} = {q21, n, n}; else {next_state, out} = {q23, n, n}; q21: if (signals == 11'b10000000000) {next_state, out} = {q21, n, n}; else if (signals == 11'b0) {next_state, out} = {q22, n, n}; else {next_state, out} = {q23, n, n}; q22: {next_state, out} = {q0, ok, n}; q23: {next_state, out} = {q23, n, n_ok}; endcase // results a Moore automaton, because 'out' depends only by the state always @(posedge clock) begin if (restart) state_reg = q0; else state_reg = next_state; {go, alarm} = out; end // we addopted a delayed variant in order to avoid output hazards endmodule module test_key_aut; reg clock, restart, init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9; wire go, alarm; initial begin clock = 0; forever #1 clock = ~clock; end initial begin restart = 1; {init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9} = 11'b0; #50 restart = 0; init = 1; #50 s1 = 1; #50 s1 = 0; #50 s7 = 1; #50 s7 = 0; #50 s2 = 1; #50 s2 = 0; #50 s5 = 1; // simulates an erroneous tasting #50 s5 = 0; #50 s4 = 1; #50 s4 = 0; #50 init = 0; #50 init = 1; #50 s1 = 1; #50 s1 = 0; #50 s7 = 1; #50 s7 = 0; #50 s2 = 1; #50 s2 = 0; //#50 s5 = 1; // simulates an erroneous tasting //#50 s5 = 0; #50 s4 = 1; #50 s4 = 0; #50 init = 0; //#100 restart = 1; //#20 restart = 0; #50 $stop; end el_key dut(go, alarm, clock, restart, init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9); initial $monitor("time=%0d input=%b state=%b go=%b alarm=%b", $time, {init, s0, s1, s2, s3, s4, s5, s6, s7, s8, s9}, dut.state_reg, go, alarm,); endmodule */ /* If we want to be more patient and to trigger the alarm only after three errors, then we must add again around 12 states to the state set of the automaton. I advise you to wait the next VerLab to addopt anoter less complex solution. */