So, here in lecture 6.4 we're going to continue our exploration of multilevel

logic. What we know is the algebraic model

simplfies our Boolean equations and makes it possible for us to do algebraic

division by which we can divide one Boolean equation by another so we can do

some factoring. But one of the questions that we don't

have an answer for yet is where should we go look to try to find the interesting

factors of a complecated set of Boolean equations.

And it turns out that the algebraic model offers a beautiful, insightful, and simple

answer. The algebraic model actually has a deep

structure. There are some interesting foundational

parts of Boolean Equations represented in the algebraic model, and those

foundational parts are called kernels and co-kernels.

It turns out that kernels and co-kernels are where all the action is in a

multi-level Boolean logic network. So in this lecture, we're going to explore

the basic structure of and definitions of kernels and co-kernels in multi-level

logic. So, where do we look for good divisors in

a big complicated network? And surprisingly, they algebraic model has

a beautiful answer, it's one of the more reasons we, you know, we like it.

It has this surprising and elegant deep structure.

So where do you look for the divisors of a function F?

And the answer is in the kernels of F. So this is denoted K of F, this is the set

of Boolean expressions called kernels. It's pronounced like colonel in a

military, you know, like captains and generals.

It's spelled with two e's so remember that depending on your Language you may be may

be interested to try. K, e, r, n, a, l which is wrong, this is

kernel two e's. K of F, the kernels of F is another set of

2 level sum of product forms. Which are the special foundational

structure of any function f being interpreted in the algebraic model, that's

a pretty big statement. So we're going to, we're going to have to

defend that one. How do you find a kernel K, element of the

kernels of F? Well, you algebraically divide it by

something else, called a co-kernel. And I'll just say, wow, boy there's just a

lot of new math here, and a lot of new concepts.

Let's, let's go develop these ideas, because they're actually, they're actually

lovely and practical. So let's just talk about what these things

are. The kernel, or a kernel, of a Boolean

expression f is a cube-free quotient k, obtained by algebraically dividing F by a

single cube. And that single cube c has a name, it's

called the co-kernel. So, on the left-hand side of this diagram

I've just got basic algebraic division. You give me F, I divide d into it, and I

get a quotient Q. I am drawing this like long division, like

how you learn to do division when you were like, I don't know, eight years old, ten

years old. You take F, you divide it by D, you get a

quotient Q and you get a remainder R, F is D times Q plus R.

Well, what is the kernel? If you take F and you divide it by 1 cube,

write a single cube, a single product term you know, abc, or pqr, or you know, xxtz

something like that. If you divide expression F by a single

cube, when you look at the quotient if the quotient is cube free then you have found

a kernel. So we need to explain what cube free

means, because what we're saying is that F is equal to c the co-kernel, ended with k

the kernel plus R, some sort of remainder. So Cube-free is really very simple, it

means that you cannot factor a single cube, which is to say a single product

term divisor, that leaves no remainder. So technical, technically this means it

has no 1 cube product that's a factor so you just take F, you divide by the cube

and you look at result, the result if you can cross out some cube in each term than

it is not a kernel. So I've got a table here.

It's got three columns, it has expression F, F equals d and Q plus R, and the

question, cube-free? So let's just go explore this for some of

the rows of this table. Suppose I give you expression a is a

cube-free? No, of course not, a is a cube.

How can a be cube free? It can't be, and if we write F equals D

times Q plus R, you know, F is equal to a times 1 plus 0, so no, it's not cube free.

A plus b is cube free, I cannot cross out a single product term in every single

element of that Boolean expression. Conversely ab plus ac is not cube free

because I can cross out an a in both of those terms and I can pull an a out as a

factor. What about abc plus abd well no that's not

cube free either, because I could cross out an ab in each of those terms I could

pull out an ab. I get c plus d and I'd have 0 as the

remainder. What about ab plus acd plus bd?

Yes, that's actually cube for you can stare at that for a long time but your not

going to be able to pull out a single cube and simply pull it out in front and write

an equation like the top 2 like the above 2 lines.

So cube-free just means you can't cross out the same product term in every single

element of the sum of products form, it's as simple as that.

So let's look at some kernel examples. Kernels of function F are K of F suppose F

is abc plus abd plus bcd. I've got another table here.

I've got a divisor cube d. I'm going to divide d into F, right?

So F is d times Q plus R. So we're just going to write it in that

form. And then I'm going to ask is the quotient

a kernel? Okay, is Q a kernel of F?

So, what if I took F and divided it by D? Well then, I'm just going to, you know

divide it by D equals 1. Well, this is not very exciting, I'm going

to get F back again. And it turns out, in this case, F actually

is not cube-free. It's got a, an ab in every single term.

Sorry, it's gotta b in every single term. It's gotta b, gotta b, gotta b, right?

So this has cube b as a factor, so this is just not going to work.

What if we took divisor cube a and divided that into F, what would happen?

Well, it turns out that we get a for the divisor cube d and Q would be bc plus bd,

and it again has a common cube b in every term and so it's not cube-free.

So, now look. What happens if I divide F by b?

Oh, well, then it turns out I get a c plus ad plus cd.

Yes, that's a kernel, ac plus ad plus cd is a kernel, why?

Because I divided f by one cube, co-kernel b and I got something that was cube-free,

simple as that. What about if I divided by ab?

Yes, again if I divided by ab, ab is a cube, so the co-kernel is ab and the thing

I get, c plus d is cube free, I can't cross out a product term in every single

element. And you could just keep doing this as long

as you, you know, as long as you want but, but that's the basic idea.

So one of the things to take away from this immediately is that any Boolean

function F can have many different kernels.

But why are they important? And secondly, how do I compute them if it

is actually true that they are important? Well, let's start from the first reason,

you know. Why are they important?

They're important because of this very famous theorem, the Brayton and McMullen

theorem. From a paper by Bob Brayton and Curtis

McMullen way back when, expressions F and G have a common multiple cube divisor d if

and only if and this is important, there are kernels k1 which is a kernel of F and

k2 which is a kernel of G, such that when you intersect those two kernels, and

that's just a sum of products formed with common cubes in it, the resulting d is an

expression with at least two cubes in it. So that sounds very technical, it makes a

lot more sense if I draw a picture. Alright, so here's a nice little picture.

Why do I care about the Braiton-McMullen theorem?

Because it says in words that the only place to look for multiple cube divisors

is in the intersection of kernels. But that is a very powerful statement,

because it says, there is one and only one place to go look for divisors of a bunch

of complicated Boolean functions expressed in the algebraic model, and that's in the

intersections of their kernels. It's if and only if, there is no place

else. So suppose F was some Boolean function in

algebraic form and G was some Boolean function in algebraic form.

I could go extract their kernels, and so I would get a bunch of kernels in this nice

little cloud picture of F, k1, k2, k3 and then I could extract some kernels from G,

k4, k5, k6, k7 And I can say hey, do those any of those kernels intercept and what

that means is do they have some common cubes, are they're at least two cubes in

some of those intersections. So for example, you know, do we get

something that looks like this, ab plus c, that's at least 2 cubes.

If there's more, then there's more cubes. If the answer is yes, then I have

identified a multi-cube divisor. I can extract that, pull that out and

simplify both F and G. So, we had something that sounded like a

very complicated problem, you have a Boolean nation network with like thousands

of nodes, thousands of F's thousands of G's.

Your looking to extract good common divisors, and the answer is Kernel things.

Kernel F, Kernel G, ask if when you intersect them you can see something there

that has at least two cubes in it. If so, hey, you found a divisor and the

only way to find a divisor is this way. There are no other divisors.

It's a beautiful, powerful and as it turns out practical result.

So this is a little concrete example that sort of shows informally why this thing

works. Suppose F is a Boolean function and it's

got kernel1. Alright and so what we know is that

there's a cube which is a co kernel ended with kernel1 plus some remainder that,

that makes F and similarly G has a kernel called kernel2.

So, there's some cube called cube2 you end it with kernel2 and you order the

remainder and that makes G. Well, I could rewrite those things.

So let's just take you know, kernel1 and kernel2 and say alright look, kernel1 is X

plus Y plus stuff1. And X and Y I'm just arbitrarily making

this stuff up, those are some common product terms.

And G similarly cubed two times, X plus Y some, plus some different stuff, stuff2

plus a remainder. And again, x and y are just some product

terms. I could do a little Boolean algebra.

I could pull out the X plus Y, and say, oh, F is cube 1 times x plus y plus.

And then I'm just doing the Boolean algebra cube1 times stuff1 plus

remainder1. So this is just, you know, a little simple

algebra. And similarly G is cube2 times X plus Y

plus some other complicated stuff. And what I have discovered here is, oh

look, I took kernel1 from F, and kernel2 from F, and I intersected them.

And what did I find? I found two common cubes, X and Y.

And so kernal1 intersect kernal2 is X plus Y, and now I can extract d as X plus Y.

And F is now cube1 times d, F, G is cube2 times d plus some other stuff.

It got simpler, right? There's less stuff inside the F and the G

nodes because I've pulled d out. And what Brayton-McMullen says is this is

the only way this happens. The only place to look for these multiple

cube divisors is in the intersections of their kernels.

And this is just a, a more concrete example, so suppose F is ae plus be plus

cde plus ab it's got a kernel K of F of a plus b plus cd with co-kernel e.

Its got ab plus e kernel, co-kernel a. Its got an a plus e co-kernel, a plus e

kernel co-kernel b. And its got the original function with a

co-kernel of 1. And similarly on the right hand side g is

ad plus ae plus bd plus be plus bc. It's got kernels a plus b which turns out

to be something you can get with either d or e.

It's got a kernel d plus e which turns out to be something you can get either a or b

as the co-kernel. It's got a kernel d plus e plus c with

co-kernel b and again it's got its own self, which happens to be a kernel with

co-kernel 1. If you intersect the ab plus cd kernel of

F, with the a plus b kernel of G, you get a plus b, that's an intersection of

kernels. That is a workable multi-cube divisor.

We can consider using that for both of those functions.

That is an amazing result, because in a real Boolean logic network, you could have

thousands of Boolean network nodes. Okay and if you're trying to think to

yourself, wow, where do I go look for divisors that can actually have some

impact on the number of literals is this network.

It seems a big complicated problem and the answer is no, I know exactly where to go

look. Get the kernels of one of the nodes, get

the kernels of the other node. Look for, to see if the kernels overlap,

if they intersect, if they have, if they do, wow, you have found yourself good

divisors. So we now know why they're important.

You know, the next question is, how do you find the kernels?

Well, there's an algorithm. Let's go look at that next.

Multilevel Logic: Role of Kernels and Co-Kernels in Factoring

VLSI CAD Part I: Logic

Conoce a los instructores