Digital Logic + trees=getting crazy! :)

This is a discussion on Digital Logic + trees=getting crazy! :) within the C Programming forums, part of the General Programming Boards category; Hello everybody! I put a lot of effort trying to understand what was wrong in this program but still cannot ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    100

    Digital Logic + trees=getting crazy! :)

    Hello everybody!
    I put a lot of effort trying to understand what was wrong in this program but still cannot find the problem.
    The aim is to emulate a digital logic network composed by AND OR and NOT gates. The network has to be represented as a tree. I supposed that all the doors can have a maximum of 2-inputs so the node of the tree is:

    Code:
    struct gate
    {
    	void *leftPtr;
    	void *rightPtr;
    	int input1,input2,output;
    	int (*function)(int,int);
    };
    
    typedef struct gate Gate;
    typedef Gate * GatePtr;
    I suppose that an input to the gate is represented by a node with output set to 1 or 0 during the initialization, while all the gates have the input initially set to -2.

    These are the functions the pointer points to:

    Code:
    int and (int input1, int input2)
    {
    	printf("AND IN1:%d IN2:%d\n",input1,input2);
    	if (input1&input2) return 1;
    	return 0;
    }
    int or (int input1,int input2)
    {
    
    	printf("OR IN1:%d IN2:%d\n",input1,input2);
    	if (input1|input2) return 1;
    	return 0;
    }
    
    int not (int input1, int input2)
    {
    	
    	printf("NOT IN1:%d\n",input1);
    	if (input1==0)
    		return 1;
    	return 0;
    }
    In the main I initialize the network like this:

    Code:
    int main ()
    {
    	GatePtr rootPtr = NULL;
    	
    	GatePtr gate[4],input[4];
    	int i;
    	
    	for (i=0;i<4;i++)
    	{
    		gate[i]=(GatePtr) malloc (sizeof(Gate));
    		if (gate[i]==NULL)
    		{
    			printf("Out of memory\n");
    			return 1;
    		}
    		
    		input[i]=(GatePtr) malloc (sizeof(Gate));
    		if (input[i]==NULL)
    		{
    			printf("Out of memory\n");
    			return 1;
    		}
    	}
    	rootPtr=gate[0];
    	gate[0]->function=or;
    	gate[0]->leftPtr=gate[1];
    	gate[0]->rightPtr=gate[3];
    	gate[0]->output=-2;
    	printf("p0 %p\n",gate[0]);
    
    	gate[1]->function=not;
    	gate[1]->leftPtr=gate[2];
    	gate[1]->rightPtr=NULL;
    	gate[1]->output=-2;
    		printf("p1 %p\n",gate[1]);
    
    	gate[2]->function=and;
    	gate[2]->leftPtr=input[0];
    	gate[2]->rightPtr=input[1];
    	gate[2]->output=-2;
    		printf("p2 %p\n",gate[2]);
    	gate[3]->function=and;
    	gate[3]->leftPtr=input[2];
    	gate[3]->rightPtr=input[3];
    	gate[3]->output=-2;
    		printf("p3 %p\n",gate[3]);
    	input[0]->function=NULL;
    	input[0]->output=1;
    	input[0]->leftPtr=NULL;
    	input[0]->rightPtr=NULL;
    		printf("i0 %p\n",input[0]);
    	input[1]->function=NULL;
    	input[1]->output=1;
    	input[1]->leftPtr=NULL;
    	input[1]->rightPtr=NULL;
    		printf("i1 %p\n",input[1]);
    	input[2]->function=NULL;
    	input[2]->output=1;
    	input[2]->leftPtr=NULL;
    	input[2]->rightPtr=NULL;
    		printf("i2 %p\n",input[2]);
    	input[3]->function=NULL;
    	input[3]->output=1;
    	input[3]->leftPtr=NULL;
    	input[3]->rightPtr=NULL;
    		printf("i3 %p\n",input[3]);	
    		printf("PREORDER: \n");
    	preorder(rootPtr);
    	printf("\n");
    	int exit=gateExit(&rootPtr);
    	printf("***EXIT***:%d\n",exit);
    	for (i=0;i<4;i++)
    	{
    		free (input[i]);
    		free (gate[i]);
    	}
    	return 0;
    }
    In brief,
    input 0 and input 1 go into an AND gate represented by gate2, whose output goes into gate1 (a NOT gate) and on the other side the inputs 2 and 3 go into the AND gate3. The output of gates 1 and 3 is ORed in gate 0 whose output represents the output of the network.
    Finally, this is the function which should explore the tree and evaluate the exits:

    Code:
    int gateExit (GatePtr *rootPtr)
    {
    	if (*rootPtr!=NULL)
    	{
    	printf("GateExit: NODE:%p LEFT:%p RIGHT:%p\n",*rootPtr, (*rootPtr)->leftPtr,(*rootPtr)->rightPtr);
    	
    
    	if ( (*rootPtr)->output==-2) //devi calcolare l'output della gate
    	{
    		printf("Node with output to be evaluated: Root:%p Left:%p Right:%p\n",*rootPtr, (*rootPtr)->leftPtr,(*rootPtr)->rightPtr);
    
    		if ((*rootPtr)->leftPtr!=NULL)
    		{
    			printf("Invoke GateExit with root (Left) %p:\n",(*rootPtr)->leftPtr);
    			(*rootPtr)->input1=gateExit( (*rootPtr)->leftPtr );
    		}
    		
    		if ((*rootPtr)->rightPtr!=NULL)
    		{
    			
    			printf("Invoke GateExit with root (Right) %p:\n",(*rootPtr)->rightPtr);
    			(*rootPtr)->input2=gateExit((*rootPtr)->rightPtr);
    		}
    		else
    			(*rootPtr)->input2=-1;
    
    		(*rootPtr)->output=((*rootPtr)->function)((*rootPtr)->input1,(*rootPtr)->input2);
    	}
    	printf("EXIT OF GATE: %p = %d\n",*rootPtr,(*rootPtr)->output);
    	return (*rootPtr)->output;
    	}
    	return -2;
    
    }
    When I run the program I get this output:

    Code:
    p0 0x804a008
    p1 0x804a048
    p2 0x804a088
    p3 0x804a0c8
    i0 0x804a028
    i1 0x804a068
    i2 0x804a0a8
    i3 0x804a0e8
    PREORDER:
    0x804a008 ] IN1 0 IN2 0 OUT -2
    0x804a048 ] IN1 0 IN2 0 OUT -2
    0x804a088 ] IN1 0 IN2 0 OUT -2
    0x804a028 ] IN1 0 IN2 0 OUT 1
    0x804a068 ] IN1 0 IN2 0 OUT 1
    0x804a0c8 ] IN1 0 IN2 0 OUT -2
    0x804a0a8 ] IN1 0 IN2 0 OUT 1
    0x804a0e8 ] IN1 0 IN2 0 OUT 1
    
    GateExit: NODE:0x804a008 LEFT:0x804a048 RIGHT:0x804a0c8
    Node with output to be evaluated: Root:0x804a008 Left:0x804a048 Right:0x804a0c8
    Invoke GateExit with root (Left) 0x804a048:
    GateExit: NODE:0x804a088 LEFT:0x804a028 RIGHT:0x804a068
    Node with output to be evaluated: Root:0x804a088 Left:0x804a028 Right:0x804a068
    Invoke GateExit with root (Left) 0x804a028:
    Invoke GateExit with root (Right) 0x804a068:
    AND IN1:-2 IN2:-2
    EXIT OF GATE: 0x804a088 = 1
    Invoke GateExit with root (Right) 0x804a0c8:
    GateExit: NODE:0x804a0a8 LEFT:(nil) RIGHT:(nil)
    EXIT OF GATE: 0x804a0a8 = 1
    OR IN1:1 IN2:1
    EXIT OF GATE: 0x804a008 = 1
    ***EXIT***:1
    In my mind the gateExit should perform a PREorder visit to nodes, but if you read the output it's like if gate 1 is not explored:
    Code:
    ...GateExit: NODE:0x804a008 LEFT:0x804a048 RIGHT:0x804a0c8
    Node with output to be evaluated: Root:0x804a008 Left:0x804a048 Right:0x804a0c8
    Invoke GateExit with root (Left) 0x804a048:
    GateExit: NODE:0x804a088 LEFT:0x804a028 RIGHT:0x804a068...
    May you help me in understanding what is wrong with my program please?
    THANKS!

  2. #2
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    nobody can help me please?

  3. #3
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Does your tree have only one node to start from? IE:
    Code:
    	preorder(rootPtr);
    	printf("\n");
    	int exit=gateExit(&rootPtr);
    Makes it look as if you are starting from one node and recuring out via linked nodes. The way I see it is that this should not work for most sets of logic gates. For example a set of gates such as:
    Code:
    AND
       \
        OR--->
       /
    AND
    You would need to determine the o/p of both AND gates before you evaluate the OR gate. Maybe your preorder function is meant to handle this, but as I dont know the code I cant tell.

  4. #4
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    Quote Originally Posted by mike_g View Post
    Does your tree have only one node to start from? IE:
    Code:
    	preorder(rootPtr);
    	printf("\n");
    	int exit=gateExit(&rootPtr);
    Makes it look as if you are starting from one node and recuring out via linked nodes. The way I see it is that this should not work for most sets of logic gates. For example a set of gates such as:
    Code:
    AND
       \
        OR--->
       /
    AND
    You would need to determine the o/p of both AND gates before you evaluate the OR gate. Maybe your preorder function is meant to handle this, but as I dont know the code I cant tell.
    the code of preorder is very easy
    Code:
    void preorder(GatePtr sPtr)
    {
    	if (sPtr!=NULL)
    	{
    		printf("%p ] IN1 %d IN2 %d OUT %d\n",sPtr,sPtr->input1,sPtr->input2,sPtr->output);
    		preorder(sPtr->leftPtr);
    		preorder (sPtr->rightPtr);
    	}
    }
    and I just inserted it to get this output:

    Code:
    PREORDER:
    0x804a008 ] IN1 0 IN2 0 OUT -2
    0x804a048 ] IN1 0 IN2 0 OUT -2
    0x804a088 ] IN1 0 IN2 0 OUT -2
    0x804a028 ] IN1 0 IN2 0 OUT 1
    0x804a068 ] IN1 0 IN2 0 OUT 1
    0x804a0c8 ] IN1 0 IN2 0 OUT -2
    0x804a0a8 ] IN1 0 IN2 0 OUT 1
    0x804a0e8 ] IN1 0 IN2 0 OUT 1
    yes i imagined that the network has only 1 exit which is the root and is explored backward towards the inputs...
    the core of the problem is in the gateExit function...

  5. #5
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Actually your recursion should reach out to all the leaf nodes then evaluate correctly, but this is assuming that you have only one exit gate.

    You would however get more coherent output if you printed the line that starts with:
    printf("Node with output to be evaluated:
    After you call the recurring functions

    Could you maybe create a simplified compiliable prog demonstrating your problem? It would probably make it easier for other people to help you with this.

  6. #6
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Since this seemed like something fun to code I had a go at creating my own version, which as far as I can tell so far seems to work.

    The way I did it was to shove all the nodes on a list. Then repeatedly run over the list until all gates have been evaluated. Evaluation is only performed once both inputs are set.

    Code:
    void eval_gates(Gate* head)
    {
        int todo=1, inputs;
        while(todo) 
        {
            Gate* node = head;
            todo = 0;
            while(node)
            {   
                inputs =  (node->one)?(node->one->result != -1)?1:0:1;
                inputs += (node->two)?(node->two->result != -1)?1:0:1;
    
                if(inputs != 2)
                    todo++;       
                //if both inputs are set calculate output if not done so already 
                else if(node->result == -1);
                {
                    // if a or b != -1 then it is a leaf node
                    if(node->a == -1) node->a = node->one->result;
                    if(node->b == -1) node->b = node->two->result;
                    node->result = (node->func)(node->a, node->b);                
                }
                node=node->next;
            }
        }
    }
    Last edited by mike_g; 09-11-2008 at 08:07 AM.

  7. #7
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    this is my version:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int and (int input1, int input2);
    int or (int input1,int input2);
    int not (int input1, int input2);
    
    struct gate
    {
    	void *leftPtr;
    	void *rightPtr;
    	int input1,input2,output;
    	int (*function)(int,int);
    };
    
    typedef struct gate Gate;
    typedef Gate * GatePtr;
    void preorder(GatePtr sPtr)
    {
    	if (sPtr!=NULL)
    	{
    		printf("%p ] IN1 %d IN2 %d OUT %d\n",sPtr,sPtr->input1,sPtr->input2,sPtr->output);
    		preorder(sPtr->leftPtr);
    		preorder (sPtr->rightPtr);
    	}
    }
    
    int gateExit (GatePtr *rootPtr)
    {
    	if (*rootPtr!=NULL)
    	{
    	printf("GateExit: NODE:%p LEFT:%p RIGHT:%p\n",*rootPtr, (*rootPtr)->leftPtr,(*rootPtr)->rightPtr);
    	
    
    	if ( (*rootPtr)->output==-2) //devi calcolare l'output della gate
    	{
    		printf("Node with output to be evaluated: Root:%p Left:%p Right:%p\n",*rootPtr, (*rootPtr)->leftPtr,(*rootPtr)->rightPtr);
    
    		if ((*rootPtr)->leftPtr!=NULL)
    		{
    			printf("Invoke GateExit with root (Left) %p:\n",(*rootPtr)->leftPtr);
    			(*rootPtr)->input1=gateExit( (*rootPtr)->leftPtr );
    		}
    		
    		if ((*rootPtr)->rightPtr!=NULL)
    		{
    			
    			printf("Invoke GateExit with root (Right) %p:\n",(*rootPtr)->rightPtr);
    			(*rootPtr)->input2=gateExit((*rootPtr)->rightPtr);
    		}
    		else
    			(*rootPtr)->input2=-1;
    
    		(*rootPtr)->output=((*rootPtr)->function)((*rootPtr)->input1,(*rootPtr)->input2);
    	}
    	printf("EXIT OF GATE: %p = %d\n",*rootPtr,(*rootPtr)->output);
    	return (*rootPtr)->output;
    	}
    	return -2;
    
    }
    
    int and (int input1, int input2)
    {
    	printf("AND IN1:%d IN2:%d\n",input1,input2);
    	if (input1&input2) return 1;
    	return 0;
    }
    int or (int input1,int input2)
    {
    
    	printf("OR IN1:%d IN2:%d\n",input1,input2);
    	if (input1|input2) return 1;
    	return 0;
    }
    
    int not (int input1, int input2)
    {
    	
    	printf("NOT IN1:%d\n",input1);
    	if (input1==0)
    		return 1;
    	return 0;
    }
    
    int main ()
    {
    	GatePtr rootPtr = NULL;
    	
    	GatePtr gate[4],input[4];
    	int i;
    	
    	for (i=0;i<4;i++)
    	{
    		gate[i]=(GatePtr) malloc (sizeof(Gate));
    		if (gate[i]==NULL)
    		{
    			printf("Out of memory\n");
    			return 1;
    		}
    		
    		input[i]=(GatePtr) malloc (sizeof(Gate));
    		if (input[i]==NULL)
    		{
    			printf("Out of memory\n");
    			return 1;
    		}
    	}
    	rootPtr=gate[0];
    	gate[0]->function=or;
    	gate[0]->leftPtr=gate[1];
    	gate[0]->rightPtr=gate[3];
    	gate[0]->output=-2;
    	printf("p0 %p\n",gate[0]);
    
    	gate[1]->function=not;
    	gate[1]->leftPtr=gate[2];
    	gate[1]->rightPtr=NULL;
    	gate[1]->output=-2;
    		printf("p1 %p\n",gate[1]);
    
    	gate[2]->function=and;
    	gate[2]->leftPtr=input[0];
    	gate[2]->rightPtr=input[1];
    	gate[2]->output=-2;
    		printf("p2 %p\n",gate[2]);
    	gate[3]->function=and;
    	gate[3]->leftPtr=input[2];
    	gate[3]->rightPtr=input[3];
    	gate[3]->output=-2;
    		printf("p3 %p\n",gate[3]);
    	input[0]->function=NULL;
    	input[0]->output=1;
    	input[0]->leftPtr=NULL;
    	input[0]->rightPtr=NULL;
    		printf("i0 %p\n",input[0]);
    	input[1]->function=NULL;
    	input[1]->output=1;
    	input[1]->leftPtr=NULL;
    	input[1]->rightPtr=NULL;
    		printf("i1 %p\n",input[1]);
    	input[2]->function=NULL;
    	input[2]->output=1;
    	input[2]->leftPtr=NULL;
    	input[2]->rightPtr=NULL;
    		printf("i2 %p\n",input[2]);
    	input[3]->function=NULL;
    	input[3]->output=1;
    	input[3]->leftPtr=NULL;
    	input[3]->rightPtr=NULL;
    		printf("i3 %p\n",input[3]);	
    	printf("PREORDER: \n");
    	preorder(rootPtr);
    	printf("\n");
    	int exit=gateExit(&rootPtr);
    	printf("***EXIT***:%d\n",exit);
    	for (i=0;i<4;i++)
    	{
    		free (input[i]);
    		free (gate[i]);
    	}
    	return 0;
    }

  8. #8
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    Quote Originally Posted by mike_g View Post
    Since this seemed like something fun to code I had a go at creating my own version, which as far as I can tell so far seems to work.

    The way I did it was to shove all the nodes on a list. Then repeatedly run over the list until all gates have been evaluated. Evaluation is only performed once both inputs are set.

    Code:
    void eval_gates(Gate* head)
    {
        int todo=1, inputs;
        while(todo) 
        {
            Gate* node = head;
            todo = 0;
            while(node)
            {   
                inputs =  (node->one)?(node->one->result != -1)?1:0:1;
                inputs += (node->two)?(node->two->result != -1)?1:0:1;
    
                if(inputs != 2)
                    todo++;       
                //if both inputs are set calculate output if not done so already 
                else if(node->result == -1);
                {
                    // if a or b != -1 then it is a leaf node
                    if(node->a == -1) node->a = node->one->result;
                    if(node->b == -1) node->b = node->two->result;
                    node->result = (node->func)(node->a, node->b);                
                }
                node=node->next;
            }
        }
    }
    i've some problems to understand your code...

  9. #9
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Well I think the recursive approach will become very complicated when you have to deal with circuits that may look something like:
    Code:
    AND-
        \
         |
         +-NOT-->
         |
         +-AND-->
           /
         /     
    OR-
    Also, you could remove some redundant code by making a constructor-like function for you gates.

    Edit:
    i've some problems to understand your code...
    Yeah, sorry about that its probably not all that easy to follow. The basic concept is to add each gate to a linked list, or for your version you could just work with the array.

    Then you repeatedly loop over the list or array.
    If both inputs are set, then you can you are ready to evaluate the result for the gate; otherwise you ignore the gate for the time being until the inputs are set.
    Eventually all the gates will have results, so then you can break out of the loop.

    Hope that makes sense.
    Last edited by mike_g; 09-11-2008 at 08:56 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Digital Logic
    By strokebow in forum Tech Board
    Replies: 3
    Last Post: 12-09-2006, 01:05 PM
  2. logic circuit truth table
    By botakis in forum C Programming
    Replies: 3
    Last Post: 11-18-2004, 11:02 AM
  3. God
    By datainjector in forum A Brief History of Cprogramming.com
    Replies: 746
    Last Post: 12-22-2002, 12:01 PM
  4. Wav file to digital value conversion
    By RpiMatty in forum C++ Programming
    Replies: 1
    Last Post: 12-23-2001, 06:42 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21