Forum Discussion

Altera_Forum's avatar
Altera_Forum
Icon for Honored Contributor rankHonored Contributor
12 years ago

tic tac toe

Hi to all,

A homework task I got is to implement a synchronous program

that checks a tic tac toe board, which is of n*n size.

The program detects if there is a winner ( Are all the elements in a row or column the same) and if so, who is the winner.

the information of the content of the board is given by "D_in":

00- blank cell; 01- X; 10- O; 11- end of line

The information is inserted in the shift-register method-

row by row ( left to right), and when a row ends there's 11/

end of the whole board is represented by "Rst_n" being '0'.

The output of the program is given by "Stts:

00- waiting; 01- X wins; 10- O wins; 11- draw

The way I chose to implement the exercise is as follows:

- final state machine (of D_in) for the row check.

- XOR of a last row memory with the current D_in for the column check.

The program includes a testbench which checks the following options:

- O row win; X row win; O column win; X column win; draw

for some reason which I don't manage to get hold of the

program doesn't get the output which it is supposed to.

any idea why?

Attached above is a sketch of the code and the block diagram of the program

and the FSM.

thanks in advance, Amitai

PS

I had a simulation error which pointed that there's a problem

in the main loop of the program.

I decided temporally to get rid of it by changing in

line 69 from "C < n" to "C < n-1".

(although I didn't manage to understand why is "C < n"

out of range)

9 Replies

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    12 years ago

    I have not taken the time to set up a simulation, but as for the line 69 error I have an answer.

    When the following block executes: 

      if D_in = "11" then	
    C <= 0;
  elsif C < n-1 then
    C <= C + 1;
end if;

    C can equal n.

    This is an issue since: 

    .
  signal memory_last_row : std_logic_vector (0 to 2*n-1) ;	 -- because D_in has 2 bits the memory needs to be 2*D_in
  signal changed_chk     : std_logic_vector (0 to n-1) ;
.
.
  memory_last_row(2*C)    <= D_in(1);
  memory_last_row(2*C+1)  <= D_in(0);

    Assume n = 3, so C = 3 after the execution of C < n if statement. When you calculate the declared size of the signal memory_last_row (2*3-1 = 5) and the index you are trying to select (2*3 = 6), you are out of bounds.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    12 years ago

    You have problems in the code. There is stuff missing from the sensitivity list of ROW_process_comb (ALL signals checked or used in a combinatorial process MUST be in the senstivity list or you will get simulation/synthesis missmatches). I also note you've put counters in the combinatorial process - you cannot do this. It may work in simulation as you have then missing from the sensitivity list, but in real hardware this will form a combinatorial loop - it will try and do a +1 in a feedback loop -and that wont work. All counters must be in a clocked process.

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    12 years ago

    Thanks for the quick answer,

    I understand the second issue you pot up but i'll pot it aside in the meantime.

    ( it's for the cause of the column check)

    Whats the meaning in " ALL signals checked or used in a combinatorial process MUST be in the sensitivity list" ? do you say that the output tmp_Stts and the row position

    and the column position should be in the sensitivity list ?
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    12 years ago

    Outputs dont need to be, but anything that is read should be (ie in an if statement or on the RHS of an assignment). So, as far as I can, row_position and C are missing from the sensitivity list (and watch your simulation hit an infinite loop because counters shouldnt be in this process), because you are reading them to update themselves:

    row_position <= row_position + 1;

    Obviously this only applies to signals. Variables and constants cannot go in a sensitivity list.

    In the checking process, even though its commented out (its very bad practice to leave commented code lying around - at least give a comment as to why its been commented out), you are missing D_in, memory_last_row, row_position and changed_chk from the sensitivty list.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    12 years ago

    PS. Remember this only applies to a combinatorial process. In a synchronous process, you should only have clk (and a reset if you have an async one) in there, as you would only want to update the process when the clock changes.

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    12 years ago

    If I understand correctly, what you're actually saying is that all the process of checking

    rows and columns should be out of the FSM process, but in the general clocked process ?
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    12 years ago

    basically yes. You're using a 2 process state machine format. This is ok, but like you've discovered, you need to be careful with sensitivity lists and you also have to make sure you set every signal in every branch (whcih you dont) to make sure you avoid latches. A single process state machine avoids these problems....

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    12 years ago

    I managed to implement a program which checks the rows of the array, now for the columns...

    I want to implement An array of FSM situations, so that for each column that I'm checking presently they will be a memory

    of the last row same column to compare to. that's because the information of the X/0 table is given by the input of the

    user (testbench) and I don't want to save all of it.

    ( if the board is n*n and n=999999 .....)

    so I wrote as follows:

    type C_state_type is (IDLE_C, X_chk_C, O_chk_C, tmp_draw_C);

    signal cur_st_C, nxt_st_C is array (1 to n) of C_state_type;

    any idea if this can be implemented somehow? If so, what should I

    change? because modelsim doesn't agree to this.

    Thanks, Amitai
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    12 years ago

    You missed some signals from your processes again:

    Rst_n is missing from the FSM_Process (async resets must be in the sensitivity list)

    C_pos is missing from COLUMN_process_comb.

    You also have a problem with this last process - you are going to infer latches because you do not assign all nxt_st_C entries in EVERY branch. You cannot have a "null" in an combinatorial process either (because you wont be assigning the signals). I suggest making this a synchronous process, or putting default assignments at the top (and holding state is not a valid option, because that is what a latch is - you need to assign everything in EVERY branch to an explicit value).