Bug in akers_synthesis (known)

[lee30sonia]

Describe the bug There has been a known bug that mockturtle/algorithms/akers_synthesis.hpp produces incorrect results for some functions.

To Reproduce Failing test case:

TEST_CASE( "Akers regressions", "[akers_synthesis]" )
{
  for ( std::string const& function : std::vector<std::string>{ "0000", "3333", "5555", "aaaa", "cccc", "f0f0", "0f0f", "ffff" } )
  {
    kitty::dynamic_truth_table f( 4 ), care( 4 );
    create_from_hex_string( f, function );
    for ( auto i = 0u; i < unsigned( f.num_bits() ); i++ )
    {
      set_bit( care, i );
    }

    std::vector<kitty::dynamic_truth_table> xs{6, kitty::dynamic_truth_table( 4 )};
    xs[0] = f;
    xs[1] = care;
    kitty::create_nth_var( xs[2], 0 );
    kitty::create_nth_var( xs[3], 1 );
    kitty::create_nth_var( xs[4], 2 );
    kitty::create_nth_var( xs[5], 3 );

    mig_network mig = akers_synthesis<mig_network>( f, care );
    if ( mig.size() > 4 )
    {
      mig.foreach_gate( [&]( auto n ) {
        std::vector<kitty::dynamic_truth_table> fanin{3, kitty::dynamic_truth_table( 4 )};
        mig.foreach_fanin( n, [&]( auto s, auto j ) {
          if ( mig.node_to_index( mig.get_node( s ) ) == 0 )
          {
            fanin[j] = ~xs[1];
          }
          else
          {
            fanin[j] = xs[mig.node_to_index( mig.get_node( s ) ) + 1];
          }
        } );
        xs.push_back( mig.compute( n, fanin.begin(), fanin.end() ) );
      } );

      mig.foreach_po( [&]( auto s ){
        if ( mig.is_complemented( s ) )
        {
          CHECK( ~xs[xs.size() - 1] == f );
        }
        else
        {
          CHECK( xs[xs.size() - 1] == f );
        }
      });
    }
  }
}

Additional context This implementation of the Akers majority synthesis algorithm has been modified from the original paper [1]. An exact re-implementation of the Akers algorithm can be found in mockturtle/algorithms/resyn_engines/mig_resyn.hpp. However, it is advised to use mig_resyn_topdown instead, as this is more efficient. [2]

This issue will not be worked on and is only for documentation purpose.

[1] Akers, S. B. (1962, October). Synthesis of combinational logic using three-input majority gates. In 3rd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1962) (pp. 149-158). IEEE. [2] S.-Y. Lee, H. Riener and G. D. Micheli, "Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition," 2021 24th International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS), 2021