Page Menu
Home
Phorge
Search
Configure Global Search
Log In
Files
F28202799
akers_synthesis.hpp
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Authored By
Unknown
Size
20 KB
Referenced Files
None
Subscribers
None
akers_synthesis.hpp
View Options
/* mockturtle: C++ logic network library
* Copyright (C) 2018-2022 EPFL
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
/*!
\file akers_synthesis.hpp
\brief Akers synthesis
\author Alessandro Tempia Calvino
\author Eleonora Testa
\author Heinz Riener
\author Marcel Walter
\author Mathias Soeken
\author Siang-Yun (Sonia) Lee
*/
#pragma once
#include
<algorithm>
#include
<bitset>
#include
<cassert>
#include
<iterator>
#include
<map>
#include
<set>
#include
<string>
#include
<unordered_map>
#include
<vector>
#include
<kitty/bit_operations.hpp>
#include
<kitty/constructors.hpp>
#include
<kitty/cube.hpp>
#include
<kitty/dynamic_truth_table.hpp>
#include
"../traits.hpp"
namespace
mockturtle
{
/* cube operators needed from Kitty :
- & (bitwise and )
- is_subset_of
- is_const0
*/
inline
kitty
::
cube
operator
&
(
kitty
::
cube
a
,
kitty
::
cube
b
)
{
assert
(
a
.
num_literals
()
==
b
.
num_literals
()
);
kitty
::
cube
c
;
for
(
auto
h
=
0
;
h
<
a
.
num_literals
();
h
++
)
{
c
.
add_literal
(
h
,
a
.
get_bit
(
h
)
&
b
.
get_bit
(
h
)
);
}
return
c
;
}
inline
bool
is_subset_of
(
kitty
::
cube
a
,
kitty
::
cube
b
)
{
assert
(
a
.
num_literals
()
==
b
.
num_literals
()
);
for
(
auto
h
=
0
;
h
<
a
.
num_literals
();
h
++
)
{
if
(
(
a
.
get_bit
(
h
)
==
1
)
&&
(
b
.
get_bit
(
h
)
==
1
)
)
continue
;
else
if
(
(
a
.
get_bit
(
h
)
==
1
)
&&
(
b
.
get_bit
(
h
)
==
0
)
)
return
false
;
}
return
true
;
}
inline
bool
all_zeros
(
kitty
::
cube
a
)
{
for
(
auto
g
=
0
;
g
<
a
.
num_literals
();
g
++
)
{
if
(
a
.
get_bit
(
g
)
==
0
)
continue
;
else
return
false
;
}
return
true
;
}
class
unitized_table
{
public
:
using
row_t
=
kitty
::
cube
;
unitized_table
(
const
std
::
string
&
columns
)
:
columns
(
columns
)
{
}
row_t
create_row
()
const
{
row_t
r
(
0
,
(
1
<<
columns
.
size
()
)
-
1
);
// for ( auto i = 0u; i < columns.size(); i++ )
// r.add_literal( i, 1 );
return
r
;
}
row_t
create_mask
()
const
{
row_t
r
(
(
1
<<
columns
.
size
()
)
-
1
,
(
1
<<
columns
.
size
()
)
-
1
);
// for ( auto i = 0u; i < columns.size(); i++ )
// r.add_literal( i, 0 );
return
r
;
}
void
add_row
(
const
row_t
&
row
)
{
rows
.
push_back
(
row
);
}
void
reduce
()
{
auto
progress
{
true
};
while
(
progress
)
{
progress
=
reduce_columns
();
progress
=
progress
||
reduce_rows
();
}
}
friend
std
::
ostream
&
operator
<<
(
std
::
ostream
&
os
,
const
unitized_table
&
table
);
inline
std
::
vector
<
row_t
>::
const_iterator
begin
()
const
{
return
rows
.
begin
();
}
inline
std
::
vector
<
row_t
>::
const_iterator
end
()
const
{
return
rows
.
end
();
}
inline
int
operator
[](
unsigned
index
)
const
{
return
(
int
)(
unsigned
char
)
columns
[
index
];
}
inline
bool
is_opposite
(
unsigned
c1
,
unsigned
c2
)
const
{
const
auto
_n1
=
columns
[
c1
];
const
auto
_n2
=
columns
[
c2
];
const
auto
n1
=
std
::
min
(
_n1
,
_n2
);
const
auto
n2
=
std
::
max
(
_n1
,
_n2
);
return
(
n1
==
0x30
&&
n2
==
0x31
)
||
(
(
n1
+
0x20
)
==
n2
);
}
inline
auto
num_columns
()
const
{
return
columns
.
size
();
}
int
add_gate
(
const
std
::
set
<
unsigned
>&
gate
)
{
assert
(
gate
.
size
()
==
3u
);
auto
it
=
gate
.
begin
();
const
auto
c1
=
*
it
++
;
const
auto
c2
=
*
it
++
;
const
auto
c3
=
*
it
;
for
(
auto
&
r
:
rows
)
{
const
auto
bi1
=
r
.
get_bit
(
c1
);
const
auto
bi2
=
r
.
get_bit
(
c2
);
const
auto
bi3
=
r
.
get_bit
(
c3
);
r
.
add_literal
(
r
.
num_literals
(),
(
bi1
&&
bi2
)
||
(
bi1
&&
bi3
)
||
(
bi2
&&
bi3
)
);
}
auto
ret
=
(
int
)
next_gate_id
;
columns
.
push_back
(
next_gate_id
++
);
return
ret
;
}
unsigned
count_essential_ones
(
bool
skip_last_column
=
true
)
const
{
auto
count
=
0u
;
auto
end
=
columns
.
size
();
if
(
skip_last_column
)
{
--
end
;
}
for
(
auto
column
=
0u
;
column
<
end
;
++
column
)
{
std
::
vector
<
row_t
>
one_rows
;
/* find rows with a 1 at column */
for
(
const
auto
&
row
:
rows
)
{
if
(
row
.
get_bit
(
column
)
)
{
auto
rt
=
row
;
rt
.
clear_bit
(
column
);
one_rows
.
push_back
(
rt
);
}
}
/* find essential rows */
for
(
auto
i
=
0u
;
i
<
one_rows
.
size
();
++
i
)
{
for
(
auto
j
=
0u
;
j
<
one_rows
.
size
();
++
j
)
{
if
(
i
==
j
)
{
continue
;
}
if
(
all_zeros
(
one_rows
[
i
]
&
one_rows
[
j
]
)
)
{
++
count
;
/* entry i is essential in column */
break
;
}
}
}
}
return
count
;
}
private
:
bool
reduce_rows
()
{
std
::
vector
<
unsigned
>
to_be_removed
;
for
(
auto
i
=
0u
;
i
<
rows
.
size
();
++
i
)
{
for
(
auto
j
=
i
+
1u
;
j
<
rows
.
size
();
++
j
)
{
if
(
rows
[
i
]
==
rows
[
j
]
)
{
to_be_removed
.
push_back
(
i
);
}
else
{
if
(
is_subset_of
(
rows
[
i
],
rows
[
j
]
)
)
{
to_be_removed
.
push_back
(
j
);
}
if
(
is_subset_of
(
rows
[
j
],
rows
[
i
]
)
)
{
to_be_removed
.
push_back
(
i
);
}
}
}
}
std
::
stable_sort
(
to_be_removed
.
begin
(),
to_be_removed
.
end
()
);
to_be_removed
.
erase
(
std
::
unique
(
to_be_removed
.
begin
(),
to_be_removed
.
end
()
),
to_be_removed
.
end
()
);
std
::
reverse
(
std
::
begin
(
to_be_removed
),
std
::
end
(
to_be_removed
)
);
for
(
auto
index
:
to_be_removed
)
{
rows
.
erase
(
rows
.
begin
()
+
index
);
}
return
!
to_be_removed
.
empty
();
}
bool
reduce_columns
()
{
std
::
vector
<
unsigned
>
to_be_removed
;
auto
mask
=
create_mask
();
for
(
auto
c
=
0u
;
c
<
columns
.
size
();
++
c
)
{
mask
.
clear_bit
(
c
);
auto
can_be_removed
=
true
;
/* pretend column c is removed */
for
(
auto
i
=
0u
;
i
<
rows
.
size
();
++
i
)
{
for
(
auto
j
=
i
+
1u
;
j
<
rows
.
size
();
++
j
)
{
const
auto
result
=
(
rows
[
i
]
&
rows
[
j
]
)
&
mask
;
if
(
all_zeros
(
result
)
)
{
can_be_removed
=
false
;
break
;
}
}
if
(
!
can_be_removed
)
{
break
;
}
}
if
(
can_be_removed
)
{
to_be_removed
.
push_back
(
c
);
}
else
{
mask
.
set_bit
(
c
);
}
}
/* remove columns */
std
::
reverse
(
to_be_removed
.
begin
(),
to_be_removed
.
end
()
);
for
(
auto
index
:
to_be_removed
)
{
columns
.
erase
(
columns
.
begin
()
+
index
);
for
(
auto
&
row
:
rows
)
{
erase_bit
(
row
,
index
);
}
}
return
!
to_be_removed
.
empty
();
}
void
erase_bit
(
row_t
&
row
,
unsigned
pos
)
const
{
for
(
auto
i
=
pos
+
1
;
i
<
unsigned
(
row
.
num_literals
()
);
++
i
)
{
if
(
row
.
get_bit
(
i
)
==
1
)
row
.
set_bit
(
i
-
1u
);
else
row
.
clear_bit
(
i
-
1u
);
}
row
.
remove_literal
(
row
.
num_literals
()
-
1u
);
}
public
:
std
::
string
columns
;
std
::
vector
<
row_t
>
rows
;
unsigned
char
next_gate_id
=
'z'
+
0x21
;
};
inline
std
::
ostream
&
operator
<<
(
std
::
ostream
&
os
,
const
unitized_table
&
table
)
{
os
<<
table
.
columns
<<
std
::
endl
;
for
(
const
auto
&
row
:
table
.
rows
)
{
std
::
string
buffer
;
std
::
bitset
<
32
>
to_print
;
for
(
auto
i
=
0
;
i
<
row
.
num_literals
();
i
++
)
to_print
[
i
]
=
row
.
get_bit
(
i
);
buffer
=
to_print
.
to_string
();
std
::
string
reversed
=
buffer
;
std
::
reverse
(
reversed
.
begin
(),
reversed
.
end
()
);
os
<<
reversed
<<
std
::
endl
;
}
return
os
;
}
inline
bool
operator
==
(
unitized_table
const
&
table
,
unitized_table
const
&
original_table
)
{
if
(
table
.
rows
.
size
()
!=
original_table
.
rows
.
size
()
)
return
false
;
for
(
auto
x
=
0u
;
x
<
table
.
rows
.
size
();
x
++
)
{
if
(
table
.
rows
[
x
]
==
original_table
.
rows
[
x
]
)
continue
;
else
return
false
;
}
return
true
;
}
namespace
detail
{
template
<
typename
Ntk
,
typename
LeavesIterator
>
class
akers_synthesis_impl
{
public
:
akers_synthesis_impl
(
Ntk
ntk
,
kitty
::
dynamic_truth_table
const
&
func
,
kitty
::
dynamic_truth_table
const
&
care
,
LeavesIterator
begin
,
LeavesIterator
end
)
:
ntk
(
ntk
),
func
(
func
),
care
(
care
),
begin
(
begin
),
end
(
end
)
{
}
public
:
signal
<
Ntk
>
run
()
{
auto
table
=
create_unitized_table
();
return
synthesize
(
table
);
}
private
:
unitized_table
create_unitized_table
()
{
const
unsigned
int
num_vars
=
func
.
num_vars
();
/* create column names */
std
::
string
columns
;
for
(
auto
i
=
0u
;
i
<
num_vars
;
++
i
)
{
columns
+=
'a'
+
i
;
}
for
(
auto
i
=
0u
;
i
<
num_vars
;
++
i
)
{
columns
+=
'A'
+
i
;
}
columns
+=
'0'
;
columns
+=
'1'
;
unitized_table
table
(
columns
);
/* add rows */
for
(
auto
pos
=
0u
;
pos
<
care
.
num_bits
();
pos
++
)
{
auto
half
=
std
::
bitset
<
16
>
(
pos
);
auto
row
=
table
.
create_row
();
/* copy the values */
for
(
auto
i
=
0u
;
i
<
num_vars
;
++
i
)
{
if
(
half
[
i
]
==
0
)
{
row
.
clear_bit
(
i
);
row
.
set_bit
(
i
+
num_vars
);
}
else
{
row
.
set_bit
(
i
);
row
.
clear_bit
(
i
+
num_vars
);
}
}
row
.
clear_bit
(
num_vars
<<
1
);
row
.
set_bit
(
(
num_vars
<<
1
)
+
1
);
if
(
!
kitty
::
get_bit
(
func
,
pos
)
)
{
for
(
auto
i
=
0
;
i
<
row
.
num_literals
();
++
i
)
{
if
(
row
.
get_bit
(
i
)
==
0
)
{
row
.
set_bit
(
i
);
}
else
{
row
.
clear_bit
(
i
);
}
}
}
table
.
add_row
(
row
);
}
table
.
reduce
();
return
table
;
}
std
::
set
<
std
::
set
<
unsigned
>>
find_gates_for_column
(
const
unitized_table
&
table
,
unsigned
column
)
const
{
std
::
vector
<
unitized_table
::
row_t
>
one_rows
;
std
::
vector
<
bool
>
matrix
;
/* find rows with a 1 at column */
for
(
const
auto
&
row
:
table
)
{
if
(
row
.
get_bit
(
column
)
)
{
auto
rt
=
row
;
rt
.
clear_bit
(
column
);
one_rows
.
push_back
(
rt
);
}
}
/* find essential rows */
for
(
auto
i
=
0u
;
i
<
one_rows
.
size
();
++
i
)
{
for
(
auto
j
=
0u
;
j
<
one_rows
.
size
();
++
j
)
{
if
(
i
==
j
)
{
continue
;
}
if
(
all_zeros
(
one_rows
[
i
]
&
one_rows
[
j
]
)
)
{
for
(
auto
k
=
0
;
k
<
one_rows
[
i
].
num_literals
();
++
k
)
matrix
.
push_back
(
one_rows
[
i
].
get_bit
(
k
)
);
break
;
}
}
}
return
clauses_to_products_enumerative
(
table
,
column
,
matrix
);
}
std
::
set
<
unsigned
>
find_gate_for_table
(
unitized_table
&
table
)
{
std
::
map
<
std
::
set
<
unsigned
>
,
unsigned
>
gates
;
std
::
vector
<
std
::
set
<
unsigned
>>
random_gates
;
auto
g_count
=
0u
;
for
(
auto
c
=
0u
;
c
<
table
.
num_columns
();
++
c
)
{
for
(
const
auto
&
g
:
find_gates_for_column
(
table
,
c
)
)
{
assert
(
g
.
size
()
==
3u
);
gates
[
g
]
++
;
g_count
++
;
}
}
if
(
gates
.
empty
()
)
{
reduce
++
;
return
find_gate_for_table_brute_force
(
table
);
}
if
(
gates
.
size
()
==
previous_size
)
{
reduce
++
;
return
find_gate_for_table_brute_force
(
table
);
}
assert
(
!
gates
.
empty
()
);
reduce
=
0
;
previous_size
=
gates
.
size
();
using
pair_t
=
decltype
(
gates
)
::
value_type
;
for
(
auto
f
=
0u
;
f
<
g_count
;
f
++
)
{
auto
pr
=
std
::
max_element
(
std
::
begin
(
gates
),
std
::
end
(
gates
),
[](
const
pair_t
&
p1
,
const
pair_t
&
p2
)
{
return
p1
.
second
<
p2
.
second
;
}
);
random_gates
.
push_back
(
pr
->
first
);
gates
.
erase
(
pr
->
first
);
if
(
gates
.
size
()
==
0
)
break
;
}
auto
this_table
=
table
;
for
(
auto
f
=
0u
;
f
<
random_gates
.
size
();
f
++
)
{
table
.
add_gate
(
random_gates
[
f
]
);
table
.
reduce
();
if
(
(
table
.
rows
.
size
()
!=
this_table
.
rows
.
size
()
)
||
(
table
.
columns
.
size
()
!=
this_table
.
columns
.
size
()
-
1
)
)
{
table
=
this_table
;
return
random_gates
[
f
];
}
table
=
this_table
;
}
reduce
++
;
return
random_gates
[
0u
];
}
std
::
set
<
unsigned
>
find_gate_for_table_brute_force
(
const
unitized_table
&
table
)
const
{
auto
best_count_iter
=
std
::
numeric_limits
<
unsigned
>::
max
();
std
::
set
<
unsigned
>
best_gate_iter
;
std
::
vector
<
unsigned
>
numbers
(
table
.
num_columns
()
);
std
::
iota
(
numbers
.
begin
(),
numbers
.
end
(),
0u
);
for
(
auto
i
=
0u
;
i
<
table
.
num_columns
();
i
++
)
{
for
(
auto
j
=
i
+
1u
;
j
<
table
.
num_columns
();
j
++
)
{
for
(
auto
k
=
j
+
1u
;
k
<
table
.
num_columns
();
k
++
)
{
std
::
set
<
unsigned
>
gate
;
gate
.
insert
(
numbers
[
i
]
);
gate
.
insert
(
numbers
[
j
]
);
gate
.
insert
(
numbers
[
k
]
);
auto
table_copy
=
table
;
table_copy
.
add_gate
(
gate
);
const
auto
new_count
=
table_copy
.
count_essential_ones
();
if
(
new_count
<
best_count_iter
)
{
best_count_iter
=
new_count
;
best_gate_iter
=
gate
;
}
}
}
}
return
best_gate_iter
;
}
signal
<
Ntk
>
synthesize
(
unitized_table
&
table
)
{
std
::
unordered_map
<
int
,
signal
<
Ntk
>>
c_to_f
;
c_to_f
[
0x30
]
=
ntk
.
get_constant
(
false
);
c_to_f
[
0x31
]
=
ntk
.
get_constant
(
true
);
for
(
auto
i
=
0u
;
i
<
func
.
num_vars
();
++
i
)
{
auto
pi
=
*
begin
++
;
// should take the leaves values
c_to_f
[
0x41
+
i
]
=
!
pi
;
c_to_f
[
0x61
+
i
]
=
pi
;
}
auto
last_gate_id
=
0
;
while
(
table
.
num_columns
()
)
{
auto
gate
=
find_gate_for_table
(
table
);
auto
it
=
gate
.
begin
();
const
auto
f1
=
*
it
++
;
const
auto
f2
=
*
it
++
;
const
auto
f3
=
*
it
;
last_gate_id
=
table
.
add_gate
(
gate
);
c_to_f
[
last_gate_id
]
=
ntk
.
create_maj
(
c_to_f
[
table
[
f1
]],
c_to_f
[
table
[
f2
]],
c_to_f
[
table
[
f3
]]
);
if
(
reduce
==
0
)
table
.
reduce
();
}
if
(
ntk
.
node_to_index
(
ntk
.
get_node
(
c_to_f
[
last_gate_id
]
)
)
==
0
)
return
ntk
.
get_constant
(
0
^
ntk
.
is_complemented
(
c_to_f
[
last_gate_id
]
)
);
return
c_to_f
[
last_gate_id
];
}
std
::
vector
<
std
::
vector
<
int
>>
create_gates
(
const
unitized_table
&
table
)
{
const
auto
num_vars
=
func
.
num_vars
();
std
::
vector
<
int
>
count
(
table
.
columns
.
size
(),
0
);
auto
best_count
=
0
;
std
::
vector
<
std
::
vector
<
int
>>
gates
;
for
(
auto
c
=
0u
;
c
<
table
.
columns
.
size
();
++
c
)
{
for
(
const
auto
&
row
:
table
)
{
best_count
++
;
if
(
row
.
get_bit
(
c
)
==
0
)
{
count
[
c
]
++
;
}
}
}
auto
best_column
=
0u
;
for
(
auto
c
=
0u
;
c
<
count
.
size
();
++
c
)
{
if
(
count
[
c
]
<
best_count
)
{
best_column
=
c
;
best_count
=
count
[
c
];
}
}
auto
icx
=
0
;
auto
name
=
table
.
columns
[
best_column
];
if
(
islower
(
name
)
)
icx
=
name
-
'a'
;
else
if
(
isupper
(
name
)
)
icx
=
name
-
'A'
+
num_vars
;
else
if
(
name
==
'0'
)
icx
=
num_vars
*
2
;
else
icx
=
num_vars
*
2
+
1
;
std
::
vector
<
int
>
best_c
;
best_c
.
push_back
(
icx
);
gates
.
push_back
(
best_c
);
for
(
const
auto
&
row
:
table
)
{
if
(
row
.
get_bit
(
best_column
)
==
0
)
{
std
::
vector
<
int
>
gate1
;
for
(
auto
c
=
0u
;
c
<
table
.
num_columns
();
++
c
)
{
if
(
c
==
best_column
)
continue
;
if
(
row
.
get_bit
(
c
)
==
1
)
{
unsigned
icx
;
auto
name
=
table
.
columns
[
c
];
if
(
islower
(
name
)
)
icx
=
name
-
'a'
;
else
if
(
isupper
(
name
)
)
icx
=
name
-
'A'
+
num_vars
;
else
if
(
name
==
'0'
)
icx
=
num_vars
*
2
;
else
icx
=
num_vars
*
2
+
1
;
gate1
.
push_back
(
icx
);
}
}
gates
.
push_back
(
gate1
);
}
}
std
::
vector
<
int
>
g
;
g
.
push_back
(
num_vars
);
gates
.
push_back
(
g
);
return
gates
;
}
std
::
set
<
std
::
set
<
unsigned
>>
clauses_to_products_enumerative
(
const
unitized_table
&
table
,
unsigned
column
,
const
std
::
vector
<
bool
>&
matrix
)
const
{
std
::
set
<
std
::
set
<
unsigned
>>
products
;
const
auto
num_columns
=
table
.
num_columns
();
const
auto
num_rows
=
matrix
.
size
()
/
num_columns
;
for
(
auto
i
=
0u
;
i
<
num_columns
;
++
i
)
{
if
(
table
.
is_opposite
(
column
,
i
)
)
{
continue
;
}
if
(
column
==
i
)
continue
;
for
(
auto
j
=
i
+
1u
;
j
<
num_columns
;
++
j
)
{
if
(
table
.
is_opposite
(
i
,
j
)
||
table
.
is_opposite
(
column
,
j
)
)
{
continue
;
}
if
(
column
==
j
)
continue
;
auto
found
=
true
;
std
::
size_t
offset
=
0u
;
for
(
auto
r
=
0u
;
r
<
num_rows
;
++
r
,
offset
+=
num_columns
)
{
if
(
!
matrix
[
offset
+
i
]
&&
!
matrix
[
offset
+
j
]
)
{
found
=
false
;
break
;
}
}
if
(
found
)
{
std
::
set
<
unsigned
>
product
;
product
.
insert
(
i
);
product
.
insert
(
j
);
product
.
insert
(
column
);
assert
(
product
.
size
()
==
3
);
products
.
insert
(
product
);
}
}
}
return
products
;
}
private
:
Ntk
ntk
;
kitty
::
dynamic_truth_table
const
&
func
;
kitty
::
dynamic_truth_table
const
&
care
;
LeavesIterator
begin
;
LeavesIterator
end
;
unsigned
reduce
{
0
};
std
::
size_t
previous_size
{
0
};
};
}
// namespace detail
/*! \brief Performs Akers majority-3 synthesis inside network.
*
* Note that the number of variables in `func` and `care` must be the same.
* Also the distance between `begin` and `end` must equal the number of
* variables in `func`.
*
* **Required network functions:**
* - `create_maj`
*
* \param ntk Network
* \param func Function as truth table
* \param care Care set of the function (as truth table)
* \param begin Begin iterator to child signals
* \param end End iterator to child signals
* \return Signal that realizes function in terms of child signals
*/
template
<
typename
Ntk
,
typename
LeavesIterator
>
signal
<
Ntk
>
akers_synthesis
(
Ntk
&
ntk
,
kitty
::
dynamic_truth_table
const
&
func
,
kitty
::
dynamic_truth_table
const
&
care
,
LeavesIterator
begin
,
LeavesIterator
end
)
{
static_assert
(
is_network_type_v
<
Ntk
>
,
"Ntk is not a network type"
);
static_assert
(
has_create_maj_v
<
Ntk
>
,
"Ntk does not implement the create_maj method"
);
assert
(
func
.
num_vars
()
==
care
.
num_vars
()
);
assert
(
std
::
distance
(
begin
,
end
)
==
func
.
num_vars
()
);
auto
pi
=
begin
;
if
(
is_const0
(
func
)
)
return
ntk
.
get_constant
(
0
);
auto
tt_1
=
unary_not
(
func
);
if
(
is_const0
(
tt_1
)
)
return
ntk
.
get_constant
(
1
);
for
(
auto
i
=
0u
;
i
<
func
.
num_vars
();
i
++
)
{
create_nth_var
(
tt_1
,
i
);
auto
it
=
*
pi
++
;
if
(
tt_1
==
func
)
{
return
it
;
}
tt_1
=
unary_not
(
tt_1
);
if
(
tt_1
==
func
)
{
return
!
it
;
}
}
detail
::
akers_synthesis_impl
<
Ntk
,
LeavesIterator
>
tt
(
ntk
,
func
,
care
,
begin
,
end
);
return
tt
.
run
();
}
/*! \brief Performs Akers majority-3 synthesis to create network.
*
* Note that the number of variables in `func` and `care` must be the same.
* The function will create a network with as many primary inputs as number of
* variables in `func` and a single output.
*
* **Required network functions:**
* - `create_pi`
* - `create_po`
* - `create_maj`
*
* \param func Function as truth table
* \param care Care set of the function (as truth table)
* \return A network that realizes the function
*/
template
<
typename
Ntk
>
Ntk
akers_synthesis
(
kitty
::
dynamic_truth_table
const
&
func
,
kitty
::
dynamic_truth_table
const
&
care
)
{
static_assert
(
is_network_type_v
<
Ntk
>
,
"Ntk is not a network type"
);
static_assert
(
has_create_pi_v
<
Ntk
>
,
"Ntk does not implement the create_pi method"
);
static_assert
(
has_create_po_v
<
Ntk
>
,
"Ntk does not implement the create_po method"
);
Ntk
ntk
;
std
::
vector
<
signal
<
Ntk
>>
pis
;
for
(
auto
i
=
0u
;
i
<
func
.
num_vars
();
++
i
)
{
pis
.
push_back
(
ntk
.
create_pi
()
);
}
const
auto
f
=
akers_synthesis
(
ntk
,
func
,
care
,
pis
.
begin
(),
pis
.
end
()
);
ntk
.
create_po
(
f
);
return
ntk
;
}
}
// namespace mockturtle
File Metadata
Details
Attached
Mime Type
text/x-c++
Expires
Fri, Nov 20, 9:37 PM (1 d, 6 h)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
413280
Default Alt Text
akers_synthesis.hpp (20 KB)
Attached To
Mode
R272 SoC_NEM_Synthesis
Attached
Detach File
Event Timeline