0:00

[music] So here, in Lecture 2.4, we're going to continue working on Computational

Boolean Algebra. And now that we've done some interesting

things with cofactors, and we've put them together in some interesting ways, let's,

let's do an interesting application. Let's actually do a realistic application.

This is a network repair application. So, suppose I, I, I gave you a

specification for a Boolean function, let's say something complicated with a lot

of logic gates in it and suppose you got, you got that wrong and, and suppose you're

pretty sure that one of those gates in your thousand or 5,000 or 10,000 gates is

incorrect and you'd like to figure out how to change it that seems to be an

incredibly complicated kind of a problem. It turns out that by using some clever

cofactor-based computational techniques, we can pose the problem, we can write an

equation like Physics, that expresses the problem when we can solve the equation

like Physics. And the solution of the problem will not

only tell us that the gate is wrong, the solution to the problem will actually tell

us what gate we should use to repair it. That's a pretty amazing amount of stuff

that you can do just by manipulating Boolean Algebra with a computational kind

of a mindset. So, let's go see how that works.

This is Lecture 2.4, . We're continuing our development of

Computational Boolean Algebra. We've just done a lot of interesting

things with cofactors. Let's actually do a, a realistic sort of

application, something called logic network repair.

So, suppose that I gave you a logic block to implement, and let's say, I specified

it as Boolean Algebra and this is how I specified it.

Now, I will admit right away that this is very silly because if you just do a little

Boolean Algebra on this what you will discover is that this is a plus B bar.

So, I'm just going to say, please ignore this.

I need this to be simple so that the example works out in a nice way.

So, I give you the specification, right, and then I ask you to implement it.

And you know, maybe you're having a bad day and it's, you know, just kind of not

working. And, you know, some of this stuff you got

right so there's an inversion, right, you got the inverter right and that's an and

gate and you got the and gate right and that is an or gate and, oh, gosh, I have

no idea what you did, you don't know what you did but you didn't do the right thing

and this function g, wow, it's just not doing the right thing.

It's, it's not implementing f. Here's what I'd like to ask as an

Engineering problem. Can I deduce precisely how to change this

gate to restore the correct function? And the answer is yes.

And what's amazing is that I'm going treat this like a Physics problem.

And in a Physics problem, you know, you get some physics.

You have a cannon, you know, you shoot a cannonball up in the air, you ask how high

it goes, and at what time it gets there and you write an equation and you solve

it. But, in order to do this network repair,

I'm going to do exactly the same thing. I'm going to write an equation in the

Boolean domain, I'm going to solve it, and the solution is going to tell me if this

gate can be repaired and if so, what gate to replace it with to repair it, which is

pretty amazing. So, we are going to use this trivial test

case so that you can see how the mechanics all work, right?

So, the first thing is that there is a trick and the trick is that we're going to

replace our suspect gate with a 4 to 1 multiplexer.

And remember that a 4 to 1 multiplexer has two select lines and it selects from one

of four values, in this case, d0 through d3 shown down here.

And by putting some constant values on the d's, we can pretend to be, or fake any

gate, right? So those two inputs right to the gates,

are now the select lines. By putting constant values on the d's, we

can make the gate anything we want. So, the big question we are trying to

figure out is what are the right values of the d so g is repaired, so that g is

actually the same thing? Now, it's just a, a little reminder, you

can do any function of two variables with one four input multiplexer, right?

So, in this particular example, I have zeros in all, on all of the inputs, except

when both s1 and s0 are one. And so this thing is actually pretending

to be an and gate. And similarly, over here the only times I

have ones are when the s1 and s0 are different.

And so, this guy here is pretending to be an exclusive or gate, that's great.

What we know is that, if I can solve for the constants that go into the

multiplexers and make that, the logic networks correct, right, if I can make the

network with the multiplexer do the same thing as the specification network, then I

can repair things. So, here's the next interesting trick.

I'm going to make this new function Z, and Z is a function of the original variables,

alright, so there's the original variables.

Z has got them, but the Z is also a function of all of these multiplexeor

inputs. And note what I'm doing here, this is

required, this is a known good version of the logic, or at least just some Boolean

equation that does the right thing, even if I don't have it implemented in

engineering practical gates. I just gotta have it written down

somewhere. And I'm comparing the, the function up

here, okay, the G function with the funny multiplexer with the known good version,

and I'm doing over here an exclusive nor gate.

And just a little, a little reminder, okay, alright?

An exclusive nor gate looks, looks like, looks like that.

People I like to write this as an exclusive or sign with a bar over it, x

exclusive nor y. And this is xy plus x bar y bar, and this

thing is equal to 1 if and only if x is the same thing as y, alright?

This is an equality gate. So, we're going to take this equality

gate, and we're going to compare G and we're going to compare f, right?

And we're going to call this whole thing Z, and Z is the thing that we're going to

try to figure out. So, what do I want?

You just think real hard about, about what I want.

This is what I want from an engineering point of view.

I want the values of these constants, d0, d1, d2, d3, that make this interesting new

function, that make this thing Z exactly equal to 1.

And look what I'm writing. I'm being very careful.

For all possible values of the original inputs a and b I know how to do that.

If you give me the Z function, what I will do is I will universally quantify away a

and b out of the Z function, that's a new function.

And that functions depends only on d0, d1, d2 and d3, it doesn't have any a's and b's

in it. And then I will ask the question, can I

make this thing a 1, can I find some values of the d's that make it a 1?

And so, just like the bullet says, hey, this is something I know how to do.

Universal quantification of Z with respect to the variables a and b will do the

trick. Any pattern of the d's that makes this new

universally quantified function of one solves my problem.

That's petty amazing. And aside, you know where the a and b

went? They went away because they got consumed

in the co-factors when we set a and b to all four possible values of the a and b,

00 01 10 11. Let's go do it, okay?

Let's convince ourselves we can do it. So, the first thing I'm doing on the top

is I'm just writing the equation for the multiplexer, alright?

So, for example, you know, when s1 is a 0 and s0 is a 0, d0 is the value you, you

send on out, right? So, that's just the mux.

Alright. So, what's the, what's the G function,

right? The G function is if we just take the, the

function shown on the top and replace it with basically this logic, alright, what I

get is I get d0 ab bar, b bar, bar, two bars, plus d1 ab bar, b with a bar, plus

d2 ab, b with two bars, plus d3 ab b bar. Well, okay, that one just goes right away.

And then if I simplify this a little bit I will get d0 a bar b plus d1 b bar plus d2

ab. So, that's the G function.

That's the thing with the multiplexer pretending to be a gate, whose function is

determined by the d's. I'm going to put that into an exclusive

nor inequality gate, okay? I'm also going to put that in, that's the,

that's the f function, and the result of that is going to be my Z.

So, Z is G exclusive nor f which is Gf plus G bar f bar and what I want is to go

calculate this thing with the star, for all abZ, right, which is going to be the

ab cofactor ended with the a bar b cofactor ended with the a, b bar cofactor

ended with the a bar b bar cofactor. Now one could take a frontal assault on

this and just go pound out all of these all of these exclusive nors and one would

be badly advised if one did that. That would, golly that would hurt.

I really don't advise you to do that. I advise you to be smart and use some of

the tricks that we just showed you a couple of lectures ago, alright?

So, here it is again, all written out nice.

Z is equal to the G exclusive nored with the f.

And I've just got a little reminder over here, if you don't play with exclusive

nors too often. If you exclusive nor something with a

zero, you complement it. And if you exclusive nor something with a

1, you return it unchanged. Let's use the nice property that we showed

a couple of lectures ago. The cofactor of an exnor is the exnor of

the cofactors. So, in other words, I don't have to do

this terrible exnor and make this, this terrible big expression and then go

cofactor it. I can go cofactor it first.

If I cofactor it first, life is ever so much easier.

Then, all I have to do is in the, the G function, and in the f function, I have to

set the a's and the b's to all four possible constant values.

So, if I set the a to 0, and the b to 0, right okay it turns out that what I will

get is just d1, right? The first term goes away because b is a 0

and the third term goes away because b is a 0, right, but the second term stays

because b is a 0, alright? And then that's going to be exclusive

nored with a 1, and that's going to give me d1, right?

And if I take a as a 0 and b as a 1, it turns out I get a d0, and it turns out I

am exclusive noring it with a 0, so that turns out to be d0 bar.

If I take a as a 1, and b as a 0, it turns out I get d1 exclusive nored with a 1.

I get d1 back again and in this last one, I get d2 exclusive nored with a 1, a 1, I

get d2. And the thing to remember is that the

thing I'm trying to calculate, the universal quantification of Z, right,

which is a function of d0, d1, d2, d3, right?

It's just the end of all of these cofactors and so that's just d0 bar, d1,

d2. And that's not so horrible, alright?

Trust me. If you had exclusive nored those things

out and made this really horrible big Boolean expression, and then cofactored

it, and then tried to and them all together, it would be very painful.

This is a much smarter way of doing it. Sorry, draw it in the right place there.

So what did we get? What we got was that the, the

quantification that got rid of the a's and the b's in the matter that we needed is

just d0 bar, d1, d2. And we know that our goal is to solve

this, aright and make it a 1. So you know, what do you have to do to

make this thing a 1? And the answer is you have to make d0 a 0,

you have to make d1 a 1, you have to make d2 a 1 and d3 is I don't really care,

don't care. Anything you want, it doesn't matter,

which is interesting. And it's going to be surprising, it's

going to be actually of relevance. Those values will repair this network,

alright? So remember what I said.

If you take d0 is a 0, d1 is a 1, d2 is a 1, and d3 is a don't care, it repairs this

network, alright? Well, look, one of these values makes

eminently good sense, right? If you do this as 0110, that's an or gate,

right? That makes a 1, I'm sorry 0111, okay?

That is an or gate, right? And look, that's what we expected,

alright? We expected that if this Boolean thing

worked, it would produce an or gate, because we knew that produced the right

answer. But what's interesting is that if you take

the other value, 0110, it specifies an exclusive or gate, and that will also

repair it. That's very cool, alright?

Because in the real world, you don't have a tiny example like this one is, you have

a big network. It has a hundred inputs, it has 50,000

gates. It's big and complicated, and you can

localize the problem to some blob of gates, right?

And you can point at the gate and say, gosh, I wonder what that gate is supposed

to be? And perhaps you have a specification that

you can actually work with for what is, what the golden correct version of the

logic is. But it alone is quite complicated.

The fact that you can do this as a Boolean equation, that you can do this like

physics, you can write an equation and solve the equation.

And if you solve the equation, the Boolean expression equals 1, it repairs the

network. That's a completely amazing kind of a

result. That's why we're focusing on this

Computational Boolean Algebra business. You've never really done Boolean Algebra

like Physics, where you write equations and expect solutions.

So, what have I just done? I've given you a mechanical procedure to

answer, can I change one gate and repair it?

Now, what you really haven't seen yet are a lot of computational strategies.

In this particular case, what I needed was to find inputs, okay, that make this

particular value of this function a one. That is the most famous computational

problem in all of Boolean Algebra. That's called Boolean satisfiability.

Give me a Boolean expression, tell me if there is a way to make it a 1, or tell me

that there is no possible way to make it a 1.

That's called the SAT problem. And the ability to do Boolean SAT

efficiently is a big goal for this. We're going to, we're going to see how to

do this in some, in some later lectures, but for now, what we're going to do next,

is give you some more computational infrastructure for Boolean Algebra.

[music]