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 ...
INPUT(1)
INPUT(2)
INPUT(3)
INPUT(6)
INPUT(7)
OUTPUT(22)
OUTPUT(23)
# 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.

Regards
Niketh

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):

``````gate::calculate()
{
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.

Hello thats sound a very interesting project. You have all done fine ?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.19 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.