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.

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.

Figure 2. ASM Chick

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.