Tues, 20th Oct 2015, 02:31 Recall a discussion I had with a student during class last week

My students,

A little relaxation time after the first program, and before you sink your
teeth into program 2.  I thought I would share with you the follow-up to
an interaction that took place in class last week.  If instead, you would
rather just relax and forget about EE306 tonight, I fully understand.  This
is not essential.  But for those who can't get enough of this, you are
welcome to keep reading.

Recall I said that the way to determine if R0 (the input character) and
R3 (the character in the file we were checking) were identical was to first
take the negative of R0 and then add the result to R3.  If the result is 0,
the original R0 is identical to R3.

A student volunteered that he could do the job with one AND gate and due to
time constraints, I invited him to prove it and to send me email with the proof.

Well, he indeed sent me email, which I thought I would share with you.



> Professor Patt,
>
>      My name is ***********************, and I'm an Electrical Engineering
> student in your EE306 class. During this past Monday's lecture, you asked
> me to determine why the AND function can't be used to determine if 2 values
> are identical. This is my answer:
>
>      I initially believed that AND could be used to see if two values
> were identical. My method was to AND(NOT(A), B) and if the result
> was #0, the two values were identical.
>
>      Although the result is #0 in every case where the two values are
> identical, this method is fundamentally flawed. The flaw is that for a
> lot of cases where A is not identical to B, the result of AND(NOT(A),B)
> will give the result 0.
>
> We can actually see this with a simple example.  Suppose A=1100 and B=0100.
> Then AND(NOT(A),B) = AND(0011,0100) = 0000.
>
> The three right-most bits (100) are identical, and so when I invert A, I end up
> ANDing a 0 and a 1 for each of the three bits.  However, the left most bit
> is problematic.  It is 1 in A and 0 in B.  When I invert A, I get 0 in that
> bit, so the AND will produce a 0 regardless whether the corresponding bit of
> B is 0 or 1.  So, the method does not work.
>
> -Now that I see this, I will use the A + (-B) = 0 to check if two values
> are identical from here on out.
>
> Thank you for giving me the impetus to better understand the relationship
> between binary values and AND, I really enjoyed the process of exploring
> and discovering the flaw and the reason behind it. There's probably a few
> ideas that I didn't catch, and so please point me towards them so I can do
> more thinking.
>
> Sincerely,
> <<name withheld to protect the student who enjoys exploring and discovering>>



Actually, you were almost there!  What if you reversed A,B: AND(NOT(B),A).
In this case, it would work!  AND(NOT(0100),1100) = AND(1011,1100) = 1000.
This is not 0, and sure enough, A and B are not identical.

But you can't know ahead of time which value should be A and which should be B.
So you have to do it both ways, and OR the result.  That is,
OR(AND(NOT(A),B),AND(NOT(B),A).  This, in fact, would work!  If you make a
truth table for this function, you will find that you have the XOR.  And,
indeed, XOR(A,B) = 0 if they are identical, and not 0 if they are not identical.

Good luck with the rest of the course.



Yale Patt