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.