Synthagate’s fast Logic Synthesis of FSM and combinational circuits reduces the circuit area of very complex Finite state machines and combinational circuits by as much as 50%, compared with results obtained by the best industrial tools from Synopsys, Xilinx, Altera and Mentor Graphics. At the same time, Synthagate runs faster than other tools by a factor of 10 or more.

Finite State Machine Synthesizer. Fig. 1 presents the design flow of FSM Synthesizer.

LogicSynthesis Design Flow

Figure 1. The design flow of FSM Synthesizer

For Synthesis, FSM can be presented in one of the following forms:

  • Algorithmic state machine (ASM);
  • Transition table of FSM (T1);
  • FSM in VHDL;
  • FSM in Verilog.

As an example, we use the small FSM Chick containing only 6 states and 16 rows in its transition table. However, there are no constraints on the parameters of FSM. The biggest FSM, synthesizes by Synthagate, contains 2314 states and more than 350,000 rows in the transition table. By the way, no existing tool, except Synthagate, can synthesize such a huge FSM.

The following five figures present the example FSM Chick as ASM (as a graph – Fig. 2), as two connected list and the list of operators and microoperations (Fig. 3a, b), as a transition table of FSM (Fig. 4), as FSM in VHDL (Fig. 5) and FSM in Verilog (Fig. 6). ASM can be drawn in ASM Creator (Fig. 2) which immediately transfers it into the internal representation in Fig. 3.

ChickNumbered

Figure 2. ASM Chick

ChickInternal

Figure 3. ASM Chick as two connected list (a) and its operators (b)

Columns from left to right in the transition table of FSM (Fig. 4):

  • current state;
  • next state;
  • input signal – the conjunction of input variables;
  • output signals;
  • transition number.
a1   a2   x1*x2*x3    y1y3      1
a1   a6   x1*x2*~x3   y6y7      2
a1   a2   x1*~x2      y1y2      3
a1   a5   ~x1         y4        4
a2   a2   x4*x1       y8y9      5
a2   a4   x4*~x1      y3y4      6
a2   a5   ~x4         y4        7
a3   a2   x6          y8y9      8
a3   a1   ~x6*x7      y3y6y10   9
a3   a1   ~x6*~x7     --        10
a4   a1   x6          y6y7      11
a4   a4   ~x6         y3y4      12
a5   a3   x5          y5y6y7    13
a5   a2   ~x5*x1      y8y9      14
a5   a4   ~x5*~x1     y3y4      15
a6   a4   1           y3y4      16

Figure 4. FSM Chick as a transition table

library ieee;
use ieee.std_logic_1164.all;

entity Chick_mkb is
   port ( clk,rst,x1,x2,x3,x4,x5,x6,x7 : in std_logic;
        y1,y2,y3,y4,y5,y6,y7,y8,y9,y10 : out std_logic );
end Chick_mkb;

architecture ARC of Chick_mkb is

   type states_Chick_mkb is ( s1,s2,s3,s4,s5,s6 );
   signal current_Chick_mkb : states_Chick_mkb;

begin
   process (clk , rst)
   procedure proc_Chick_mkb is
   begin

 y1   <= '0' ; y2   <= '0' ; y3   <= '0' ; y4   <= '0' ;
 y5   <= '0' ; y6   <= '0' ; y7   <= '0' ; y8   <= '0' ;
 y9   <= '0' ; y10  <= '0' ;

   case current_Chick_mkb is
   when s1 =>
      if ( x1 and x2 and x3 ) = '1' then
         y1 <= '1' ;
         y3 <= '1' ;
         current_Chick_mkb <= s2;

      elsif ( x1 and x2 and not x3 ) = '1' then
         y6 <= '1' ;
         y7 <= '1' ;
         current_Chick_mkb <= s6;

      elsif ( x1 and not x2 ) = '1' then
         y1 <= '1' ;
         y2 <= '1' ;
         current_Chick_mkb <= s2;

      else
         y4 <= '1' ;
         current_Chick_mkb <= s5;

      end if;

   when s2 =>
      if ( x4 and x1 ) = '1' then
         y8 <= '1' ;
         y9 <= '1' ;
         current_Chick_mkb <= s2;

           .   .   .

   when s6 =>
         y3 <= '1' ;
         y4 <= '1' ;
         current_Chick_mkb <= s4;

   end case;
   end proc_Chick_mkb;

   begin
      if ( rst = '1' ) then
 y1   <= '0' ; y2   <= '0' ; y3   <= '0' ; y4   <= '0' ;
 y5   <= '0' ; y6   <= '0' ; y7   <= '0' ; y8   <= '0' ;
 y9   <= '0' ; y10  <= '0' ;
 current_Chick_mkb <= s1;
      elsif (clk'event and clk ='1') then
        proc_Chick_mkb;
      end if;
   end process;
end ARC;

Figure 5. FSM Chick in VHDL 

module Chick_mkb ( clk,rst,
    x1, x2, x3, x4, x5, x6, x7, 
    y1, y2, y3, y4, y5, y6, y7, y8, y9, y10);

input clk, rst, x1, x2, x3, x4, x5, x6, x7;
output y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;
reg y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;

parameter s1=1, s2=2, s3=3, s4=4, s5=5, s6=6;
integer pr_state;
integer nx_state;

always@ ( posedge rst or negedge clk )
begin
    if ( rst == 1'b1 )
        pr_state = s1;
    else
        pr_state = nx_state;
end

always@ ( pr_state or x1 or x2 or x3 or x4 or x5 or x6 or x7)
    begin
            y1 = 1'b0;  y2 = 1'b0;  y3 = 1'b0;  y4 = 1'b0;  
            y5 = 1'b0;  y6 = 1'b0;  y7 = 1'b0;  y8 = 1'b0;  
            y9 = 1'b0;  y10 = 1'b0; 
        case ( pr_state )
                s1 : if( x1 && x2 && x3 )
                        begin
                            y1 = 1'b1;  y3 = 1'b1;  
                            nx_state = s2;
                        end
                    else if( x1 && x2 && ~x3 )
                        begin
                            y6 = 1'b1;  y7 = 1'b1;  
                            nx_state = s6;
                        end
                    else if( x1 && ~x2 )
                        begin
                            y1 = 1'b1;  y2 = 1'b1;  
                            nx_state = s2;
                        end
                    else if( ~x1 )
                        begin
                            y4 = 1'b1;  
                            nx_state = s5;
                        end
                    else nx_state = s1;
                s2 : if( x4 && x1 )
                        begin
                            y8 = 1'b1;  y9 = 1'b1;  
                            nx_state = s2;
                        end

                        .  .  .  
                        
                s6 : if( 1'b1 )
                        begin
                            y3 = 1'b1;  y4 = 1'b1;  
                            nx_state = s4;
                        end
                    else nx_state = s6;

            default : nx_state = 0;
        endcase
    end
endmodule

Figure 6. FSM Chick in Verilog

ASIC or FPGA is a possible target of logic synthesis. Synthesizing a FSM, a designer can choose its type – Mealy, Moore or Combined (Mealy and Moore) model. For ASIC and FPGA implementations we can use one of possible FSM encoding – Binary (logarithmic), One Hot (the only ‘1’ in the code of initial state is on the left) or Reverse (the only ‘1’ in the code of initial state is on the right).

For ASIC implementation a designer can construct combinational circuits and FSM with gates from the library or with matrix structure. For FPGA implementation a designer can use area or delay optimizations.

Combinational Circuit Synthesizer. This synthesizer contains the following steps from Fig.1:

  • Logic Circuit Synthesizer;
  • FPGA Synthesizer (Area and Delay optimizations);
  • ASIC Synthesizer.