Rewrite a Gray-code-to-binary converter with another structure, keeping its function.
Under one variable order, every function has exactly one ROBDD, so two outputs that compute the same function are the same node, however the circuits compute them. An equivalence check therefore compares the functions of corresponding outputs, over the same input variables, and never the gates. A rewrite with a different structure passes as long as every output computes the same function.
Design A computes y = s ? p : q with a conditional. Design B computes y = s & p | ~s & q with gates.
y = s ? p : q
y = s & p | ~s & q
Expand both on s: with s = 1, each is p; with s = 0, each is q. Their cofactors agree, so they compute the same function.
s
s = 1
p
s = 0
q
Under any one order, their outputs are therefore the same ROBDD, and the check finds them equivalent without comparing their gates.
Equivalence is a property of the functions the outputs compute, not of the circuits that compute them.
The reference, shown in the work area, converts a 4-bit Gray code g to binary b, building each bit of b from the bits of g at its position and above.
g
b
Write a module that computes the same function, building each bit of b from the bit of b above it. The site converts your module with Yosys and checks that each output is equivalent to the reference's; it does not check the structure.
A Verilog module with the ports input [3:0] g and output [3:0] b, using assign statements. In Verilog, ^ is exclusive-or and b[2] is bit 2 of b. For example, a module with other ports might read module inv(input [1:0] x, output [1:0] y); assign y = ~x; endmodule.
input [3:0] g
output [3:0] b
assign
^
b[2]
module inv(input [1:0] x, output [1:0] y); assign y = ~x; endmodule
Ports: input [3:0] g, output [3:0] b.
Every output equivalent to the reference's.
Press Build: Yosys converts your module, and the conditions show whether its ports are exactly the ones the task names.
Check one input by hand: choose a value of g, work out each bit of b from the reference, then from your module, starting at the top bit.
To check every input at once, open the Workbench's Compare two designs with the reference as design A and your module as design B, and check them for equivalence.
Kata 6.2 of Binary Decision Diagrams with CUDD on formal.org. The site checks the answer when you press Check answer; sign in to keep your progress.