hi all,

I am working on C++ coding of fault simulation algorithm of a digital circuit . The first step involves parsing of netlist files. The sample netlist looks like -

# Only 2,3 input gates considered ...
# comment here

10 = NAND(1, 3)
11 = NAND(3, 6)
16 = NAND(2, 11)
19 = NAND(11, 7)
22 = NAND(10, 16)
23 = NAND(16, 19)

INPUT are the primary inputs, OUTPUT are the primary outputs, gates are the intermediate nodes. I hope some of you can imagine how this circuit will look like (..:)..).I have attached a sample image file of the above circuit. At this stage i have been able to extract all relevant numbers/values and gate type from the file.

My concern is what are the appropriate data structures that i can use to model the above circuit , so that i will be able to do the following :-

1) given bool values to the inputs , i can propagate it through the intermediate nodes to the output nodes.

2) To each node , i can add customary features like fan-in array, fan-out array.

I have tried out singly linked lists . Is it possible for a node to be pointed by multiple nodes(node1,2,3...) and a node to point to multiple nodes ? And also to be able to ascertain as from which node(node1,2,3...) is the current node traversed from ? Is it possible to propagate an integer value from one node to the other ?

In that case it would be slightly helpful . Any help as earlier as possible will be appreciated.

Thank you in advance

Attachments circuit.png 5.56 KB
5 Years
Discussion Span
Last Post by hactor

I don't think a linked list is a right approach. You need a dependency graph, along the lines of

struct gate {
    bool result;
    bool resolved;
    gate * dep1;
    gate * dep2;

To calculate the output, you just simply traverse the graph starting from the output gate (remember, pull is almost always better than push):

    if(!resolved) {
        bool val1 = dep1->calculate();
        bool val2 = dep2->calculate();
        result = nand(val1, val2);
        resolved = true;
    return result;

Of course, if some gates require more than one input (and/or perform functions other than nand), replace dep1 and dep2 with std::vector<gate *> dependency , and replace nand a virtual method.

This article has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.