This item is getting to be rather large...
see below, plz.
Dick
----- Original Message -----
From: "Tony Duell" <ard_at_p850ug1.demon.co.uk>
To: <classiccmp_at_classiccmp.org>
Sent: Monday, April 15, 2002 7:39 PM
Subject: Re: TTL computing
> >
> > This argument is still over the same things about which we always end up
> > arguing, namely how things SHOULD or COULD be, vs. how they are. What's
> > possible clearly isn't as important in the world in which I live as what's
> > REAL.
>
> And I think that's the big difference between us. You're happy to carry
> on with the 'standard stuff' (OK, it pays the bills). I am not. I want to
> try things out. If I think of something that 'should be', then I at least
> want to investigate it.
>
> I've got dozens of bits of stripboard containing experimental circuits I
> made just for the hell of it. Things like a base -2 full adder. A circuit
> that cyclically permutes 3 voltage levels :
>
> Input Output
> 0 V/2
> V/2 V
> V 0
>
> with suitable thresholds. 3 of those in a ring make a stable 3-state
> circuit (aka a flip-flap-flop), just as 2 NOT gates in a ring
> make a stable 2 state circuit. And so on...
>
I'm curious in what way doing this sort of thing in discrete logic has over
doing it in programmable hardware. (Take a look at the field-programmable
analog hardware offered at Lattice, for example.) As for the technique
itself, I remember reading that Siemens had some hardware that did this sort
of thing about 20 years ago, so there's plenty been written about it.
>
> >
> > I live and die on what's real. Engineers don't get paid for coming up
with
> > things that SHOULD be. The things that exist only in the subjunctive
don't
>
> Which implies, I guess, that you don't believe there will ever be any new
> ideas.
>
It doesn't imply that at all. It does suggest, however, that if you're trying
to exploit new thinking, you shouldn't be weighed down with archaic
implementation techniques.
If you have a concept you want to explore, you ought to be able to convince
yourself of its validity by thinking it through, the verify that validity with
extensive simulation (which you clearly don't believe useful, in spite of the
fact the rest of the world has accepted it, then implement it in a
programmable hardware testbed because that doesn't require you to buy an
specific hardware, and then stress it in various ways to determine its
sensitivities. Building just one example of a circuit would not really prove
that the design is sound. It only proves that you can make it work ... once.
>
> > pay my bills.
>
> > > For combinatorial circuits, having <m> outputs just means having <m>
> > > times the complexity. So for the purposes of discussion it's reasonable
> > > just to consider one output (this applies to both PROMs and PALs).
> > >
> > > > share product terms, there are limitations on the common small PALs.
> > However,
> > > > if you choose a device comparable to the PROM, they'll do it.
> > >
> > > You were the one who started off claiming a PAL was simpler than a PROM.
> > > Now you're claiming that 'if yuu pick a comparable device it'll do it'.
> > > I'll agree with that. If the device is sufficiently complex, it doesn't
> > > matter which matrix (AND or OR) is programmable. But the complexity of
> > > the device (and the number of bits taken to program it) will be
> > > comparable for a complete PROM with 2^n locations and a PAL capable of
> > > generating _any_ combinatorial function of n inputs.
> > >
> > It is MUCH simpler in its application. Most of the time, though a PAL
has,
> > say, 16 inputs, you use three or four of them for a given output, and you
use
> > a couple of the outputs in feedback. You use the internal registers
because
> > that way you don't have to wire the feedback externally, nor do you have
to
> > surrender PROM address inputs in order to use them, since they're already
> > connected. The reason they "get by" with a relatively small fuse array,
is
> > because you generally want a couple or three inputs in various
combinations,
>
> Or as I've been saying for the last <n> messages, the PAL is useful
> because althought it's restricted in what functions it can generate, the
> ones it can generate are actually useful for many real-world
> applications. No arguement about that.
>
> > which become your product terms, and you want the feedback applied to
those
> > inputs as well, so you may end up with as many as 5 or 6 product terms per
> > sum, but seldom the entire 8 or more that are avaialble. If you do need
> > more, there are devices that provide them, and you use one of those
devices.
> >
> > In a PROM, regardless of how many imputs you want, you have to program
them
> > all, and there's no software that does it for you. That in itself is
already
>
> Of course there's software to do that. In fact it's simpler than logic
> minisation for a PAL. Here's the algorigthm (inputs I(N), I(N-1), ..
> I(1), I(0) )
>
> For I(N) = 0 to 1 do
> For I(N-1)=0 to 1 do
> ...
> For I(1) = 0 to 1 do
> For I(0) = 0 to 1 do
> address = I(N)*2^N + I(N-1)*2^(N-1) + ... + I(1) * 2^1 + I(0) * 2^0
> bit = desired_boolean_function(I(N),I(N-1),...,I(1),I(0))
> program_PROM (address,bit)
>
... and just exactly WHAT does this do? (BTW, it's a mite confusing keeping
the I's straight, and figuring out what, exactly, your ellispsis represents,
but, overall, it still looks like a single product term will do it. That's
not the sort of function that you said you'd need a PROM to implement.
Simpler, is a pretty nebulous concept, but I'm here to say that simpler means
you use the tools that are freely available to do the "dirty-work" including
translation from source, reduction, and production of the JEDEC file and/or
fuse map. You can also use the same tool to do the functional simulation,
just to verify that you've kept the poliarity straight in all cases. (saves
on fusible-link devices) It means you don't have to write your own tools, and
it means that you can, for the most part, rely on the resulting output. The
machine on which you accomplish these things is just a tool, like a wrench.
It's not a deity, and doesn't need special consideration. Like a hammer, when
it fails to meet my needs, I repair/replace the offending component, or chuck
the whole thing and replace it, just as I would with a screwdriver that no
long works well. If I can't afford a new tool I need, I consider a 2nd hand
one, even if I can't afford one that doesn't have a broken handle or the like.
>
> > less simple, since you now have to come up with a bitmap for the prom size
> > you're using. It's not difficult with a small prom, but with a bigger one
it
> > quickly becomes a burden, so you write an application to do the bitmap
>
> Yes, which takes a few minutes at most...
>
I'm not so sure of that. Further, I'd be interested to know how long it takes
under RT-11, to which you frequently refer.
>
> > generation. Once you've done that for every size of memory that you
intend to
> > use, you're done. I don't know where you'll get a PROM with 16 address
lines
> > and address-access times on the order of what a PAL delivers, but that's
> > another issue.
>
> You possibly can't. But alas, as I said at the start, the PAL doesn't
> necessarily solve the problem either (if you're unlucky enough to have a
> function that won't fit into the PAL).
>
I'd just recommend a bit more focus on what you CAN do in the real world
rather than focusing on what you can't in the theoretical world and using that
as an excuse not to take advantage of the technology.
You're a free person and are allowed to do pretty much whatever you want, but,
IF you consider your mental processes to be of any value at all, aside from
your own amusement, and IF you think you can come up with something that's of
use, WHY would you encumber yourself with 1970's tools?
It's fun to play with those old-timers, and they do, after all, still compute
just as they always did, but, since you've mentioned that your resources are
limited, why don't you consider that those old-timers consume kilowatts of
power and leave you technologically isolated from the
convenient-if-not-perfect technology available today, that consumes much less
power and runs so much faster, aside from being able to utilize the
no-cost/low-cost resources the lack of which seems to stand in your way? You
could recover the cost of a 2nd-hand Pentium-based PC-type in just a few
months in power savings. When you buy one 2nd hand, it normally has an OS
installed, and most people put a copy of the installation files on the HDD, it
it doesn't happen automatically when the system's installed I assume, of
course, that power isn't free in the U.K.
My own average power bill has gone down by some $22 per month (though the
overall rates have increased) since I quit using those old full-sized 5-1/4"
disk drives and leaving them spun up all the time. A 3-1/2" 18GB drive only
cost me $82 including freight and a spare (ain't eBay great?!). It does't
make nearly the noise, heat, and power bills of the dozen or so "old" drives.
>
> > > > What this suggests is that you've chosen the wrong device. You can't
do
> > the
> > >
> > > Oh, for %deity's sake, this has got totally ridiculous...
> > >
> > > If you are claiming that _in principle_ a device with only a
programmable
> > > AND matrix can genearate any combinatorial function then I'll agree with
> > > you -- provided the number of product terms is large enough. But most
> > > (all?) real PALs have a limited number of product terms. For many
> > > real-world applications there are enough product terms. But there are
> > > still functions you can't generate if you wanted to.
> > >
> > NO, what I'm saying is that there's a device to fit whatever your
application.
> > If a PROM will do it, perhaps that's the right choice, but it's going to
be a
> > bigger prom and it may require extra devices to finish the job. The PAL
makes
> > it simpler because you can design your PCB knowing that your logic can be
>
> The PAL only makes it simpler if the logic will fit into the PAL...
>
> To turn it round. If I design the PCB for PROM + latch then I know that
> no matter what logic function I end up needing, it'll fit because the
> PROM can generate any n-input logic function. But if I chose the PAL,
> there's a chance the function I want won't fit into the PAL.
>
What? Are you suggesting that you'd design a PCB without knowing what logic
functions you need? You've already said that it's not a given that such a
ROM even exists. I'm still curious what sort of a logic function you think
you might encounter that you couldn't implement, including latches, etc, in a
42VA12 or something on that order. Remember, it has both arrays programmable,
and it has 64 product terms per sum term. (look in the "Signetics
Programmable Logic Devices" Data Handbook, from Philips, 1990)
>
> And for more complex PLDs (certainly the FPGAs I used), it did matter
> which pin you used sometimes. It could be that the chip could be routed
> fully if you put the signals one way round on the pins but that there
> were not enough routing resources to put the signals on other pins. It
> could be a very bad idea to design the PCB before you designed the FPGA map.
>
I recognize that problem. I've seen boards full of FPGA's that still had
wires on them once the FPGA's were changed simply because the redesign had to
change either the timing or the pinout and timing changes weren't tolerable.
That sort of thing doesn't happen as readily with current devices, but you're
certainly right.
>
> > > OK, you have 42 inputs, and let's just consider having one output. Tell
> > > me, does it take 4 terabits (=2^42 bits) to specify the programming fuse
map
> > > for that one output? Because if it takes less, it's clear to me there
> > > must be some functions you can't implement. If you don't understand
this,
> > > then _please_ read some books on electronics and/or mathematics before
> > > going off on some other tangent.
> > >
> > You can program both the AND and OR arrays, Tony, so the functions you
would
> > want to create are quite a bit more flexible. If you need all
combinations of
>
> OK, but that's still not enough to generate _all_ possible functions.
>
I'm getting really curious what sort of function one could NEED that requires
a set of more than 64 products of those 42 inputs, though you can certainly
use more than that by combining sums if you do need. Generally one doesn't
have to decode the entire real and virtual address bus. Generally, one can
use fewer than ALL the inputs in combinations of 42 taken 64 at a time, but
there's certainly more than that available to you in the little 24-pin
skinnydip that's the 42VA12. Even if you consider only one output, that's
available to you in that part. There are, of course, more sizeable parts, but
I didn't have the sense that you needed more size. Further, if it's a
state-machine, how many states do you think you might need? How many do you
think you can manage to design with inside a realistic time? What sorts of
resources would that require?
>
> Again, let me point out that if there are 2^(2^42) possible functions (a
> rediculously big number!), then there's no way to uniquely specify one of
> them with frewe than 4 terrabits. So any device that takes fewer than
> that many bits to program it must not be able to generate all possible
> functions.
>
> > the 42 inputs, you do, indeed need a PROM. If, however, you consider REAL
> > WORLD problems and their solution I've got some difficulty conceiving of a
> > logic function that would consume the entire resources of a 42VA12, in
real
> > terms. I know, you could want to detect an access to a particular
location
>
> I've not looked at the device, but how about an arbitrary set of 12 bits
> (to be decided at program-time) from the product of a 15*15 parallel
> multiplier? (I'm assuming that if I want 12 outputs,then I have 30 pins
> left for inputs -- if I have more, then just increase the input word size,
> please :-)) Large adder arrays are notoriously difficult to fit into PALs
> (there were even some PALs with XOR terms -- the 16X4, etc) to help with
> this). A parallel divider (produces the quotient and remainder in one
> clock cycle) is likely to be even worse.
>
How many ROMs of what size would it take to do what you're suggesting? The
fixed XOR's weren't popular for long, once larger numbers of product terms
became available. How about looking at the real device in a real application?
If you want something really large in scale, you'd probably want to put the
multiplier inside the device. Just for drill, take a look at the biggest of
the XILINX devices. You'll have no trouble fitting whatever you want in
there, and the performance is pretty good too.
>
> > > > > Otherwise, I'll propose the following lossless compression system :
> > > > >
> > > > > 1) Read <2^n> bits from a file.
> > > > >
> > > > > 2) Regard them as the 'truth table' for an arbitrary <n> input, one
> > output,
> > > > > logic function (this step is OK)
> > > > >
> > > > > 3) Turn that function into the equivalent 'PAL fuse map' (which you
> > claim is
> > > > > always possible, moreover, it takes fewer (than 2^n) bits to specify
> > this).
> > > > >
> > > > > 4) I now write out this smaller number of bits to the output file.
> > > > >
> > > > > If step (3) is always possible, then we have a compression system
that
> > > > > reduces the size of all possible input files. Which is clearly
> > impossible!
> > > > >
> > > > > > > > that too, but the PAL does it with fewer fuses.
> > > > >
> > > > > > > And that should tell you something is 'wrong'.
> > > > >
> > > > Not exactly, since the PROM requires you to represent all the states
of
> > the
> > > > inputs, while the PAL allows you to use only the ones that are
relevant.
> > >
> > > Do you seriously believe that the compression scheme I've proposed can
> > > always work? Because if you do, I've got a bridge for sale!
> > >
> > You can implement functions that don't do what you want. I'd be surprised
if
> > you haven't done that.
>
> Eh? Would you mind explaining what the heck you mean here?
>
I'm saying that if you design a function that doesn't work, that doesn't mean
you can't implement that function. You shouldn't expect a compression scheme
that doesn't work to work in programmable logic.
>
> > >
> > Actually, I haven't given this example a moment's thought.
>
> Ah, right. Probably becuase it proves there are functions you can put
> into a PROM that you can't put into a PAL of smaller size (same number of
> ins and outs, but fewer 'fuses').
>
No... only because you're looking for things that fit PROMs with external
registers, while you're not considering what sorts of functions it is that you
can't implement in a PAL. All you've said is that it is conceivable that one
might invent a function that doesn't work in a PAL. You've not come up with
one yet. It's true, though, that if you want a function that requires more
product terms than you can combine in a given device,
>
> Let me go through it again. Suppose, to keep things simple, we just have
> a 20 input, one output PAL (say a 20V8, but only using one output. This
> takes a lot less than 1 megabit to progam it, right?
>
> So I propose the following.
>
> 1) Read it one megabit of data
>
> 2) Regard those 2^20 bits as the outputs for a 20 input boolean function.
> If you like, think of burning those 2^20 bits into a 1 megabit PROM, and
> figuring out just what boolean function it now generates.
>
Have you got a part number for a 1 Mbit x1 PROM?
>
> 3) Generate the PAL fuse map that generates the same function in a 20V8.
> By the above assumptions, this is less than 1 megabit in size.
>
I'm not sure where this is supposed to lead. Normally one starts with a
required logic function and then decides what sort of hardware is required to
implement that. Keep in mind that the 20L8 is a 24-pin part, so a more
complex PLD on a 24-pin footprint isn't ruled out if you only use one output.
>
> This process is reversable (in that given a PAL fuse map we can generate
> the boolean function from it (this is what a PAL does in hardware :-)),
> and thus can generate the PROM bitmap to do the same thing. And thus can
> recover the original 2^20 bits.
>
You're putting too much emphasis on the fuse map, which nobody sees, and not
on the relationship between the inputs and output, though one certainly
exists.
>
> However, it's also clear that there are many more PROM bitmaps than PAL
> fuse maps. How can we then have a 1-1 mapping between 2 finite sets of
> different sizes? Obviously we can't.
>
And what, exactly does that prove?
>
> It's actually true that _no_ lossless compression algorithm can compress
> all possible input files (the above argument doesn't depend on PROMs and
> PALs, only on having 2 things that are claimed to be equivalent, but
> which take differnent numbers of bits to specify them).
>
>
> > > > > What I am saying is that (say) a 16 input _PROM_ takes 65536 bits to
> > > > > program it. A 16 input PAL (like a 16C2) takes many fewer bits. So
there
> > > > > have to be logic functions you can fit into the PROM that you can't
fit
> > > > > into the PAL.
> > > > >
> > > > Not all PALs are alike. The 16C2 is a decoder. It tells you when the
> > desired
> > > > address appears at the inputs. A 26CV12 is quite a different device.
> > >
> > > Actually, a 16C2 is not a decoder necessarily. It's just the simplest of
> > > the original classic PALs.
> > >
> > I remember it being described as a programmable decoder. ...
>
> That may well have been it's main (or intended) use, but it's not
> restricted to that.
>
> > > [1] Considering that the FPGAs I used about 5 years ago used 32 bit RAMs
> > > to implement all the combinatorial logic, there must be tools that turn
> > > logic equations into the 'bitmap' for such RAMs. And I have no reason to
> > > believe that such tools can only exist for 32 bit RAMs.
> > >
> > Yep! Sounds like the 3000-series Xilinx devices. They had more than a
>
> Exactly!
>
> > 32-bit RAM, but that's what you saw. Believe me, their software won't
support
> > your 32-bit RAM. It only supports their unique architecture.
>
> Of course. However, there is no problem in principle for writing similar
> software for any 32 bit RAM (or any size RAM/PROM for that matter).
>
> > > True. But why do you insist of overcomplicating things. We are
> > > considering only the combinatorial part of the circuit at the moment.
> > >
> > Why? One of the benefits of PALs is that they allow you to build two or
three
> > functions into a single device. You don't always want a PROM. If you do,
you
> > should use one.
>
> No arguements there. If the PAL is the right solution, use it. But if the
> PROM is the right solution, don't ignore it.
>
> >
> > > [16C2]
> > > > > Actaully, the 'C' means Complimentary, refering to the fact that the
2
> > > > > outputs are always inverses of each other.
> > >
> > I found an old-enough databook to have that device ... it's actually a
16C1,
> > unless there was also a 16C2, which certainly isn't in this book. It
appears
> > that it has 512 bits in its fuse array.
>
> OK, sorry. Looks as though they only counted the single output from the
> OR array, even though it actually appeared on 2 pins (one the inverse of
> the other). Makes sense.
>
> > > The reason I picked the 16C2 was to avoid having any features that are
> > > irrelevant to the argument. OK, you want to pick the 16L8. It makes no
> > > difference. You might as well ignore the output control lines _because
> > > they make no difference to the combinatorial functions you can
> > > implement). And the feedback terms are almost irrelevant -- just add 6
> > > more pins to the package (IIRC only 6 of the outputs have feedback) and
> > > seperatate the feedback signal from the output. You can wire them back
> > > together if you want to.
> > >
> > OK, but Why? What's relevant is the question of what's realistically
> > implementable. I know of no PROM with performance comparable with PALs,
and I
>
> Because at the time I believed we were arguing over what combinatorial
> functiosn could be fitted into a PAL compared to a PROM. So I wanted to
> not bother about other features of the PAL for the moment.
>
> Obviously if you need these extra features _and have a combinatorial
> function that will fit into the PAL_, then you probably should at least
> consider the PAL :-)
>
> > > The result is an imaginary device that would be more versatile than
> > > the real 16L8. So if we can show this has restrictions (which we clearly
> > > can), then the real 16L8 must have at least as many restrictions.
> > >
> > Yes, but the reason such a device doesn't exist is because there's too
little
> > market for it. The PAL is extremely simple to use for the purpose for
which
>
> Do you really never consider non-existant but possible devices for the
> purposes of discussion/arguement?
>
That's the reason programmable logic exists. Devices are needed, but don't
exist, so we look at how to make 'em. If there's a very limited market, like,
I'm the only one who wants such a thing, then a programmable devices is more
likely find its way into my application than a mass-produced one.
>
> Nobody is suggesting the device should be made. Only that for the
> purposes of this argument it's easier to consider such a device.
>
I think that's why this argument has persisted for so long. With programmable
devices, I can build what I want. With TTL SSI/MSI/LSI you can build what you
want. We could switch roles, but the fact remains, each approach has
advantages. I just believe that the advantages of the SSI/MSI/LSI approach
are diminshing, while the programmable logic approach continues to expand.
As far as the theoretical capabilities of PROMs versus PAL-architecture
devices, I've never suggested you were wrong in your assertion that it was
POSSIBLE to conjure up a function that could be implemented in a PROM that
couldn't be implemented in a particular PLD. I've emphasised, I hope, that
there's a link missing between your argument and the practical realities of
(a) needing such a function and defining it, and (b) implementing such a
function in REAL hardware, whether programmable logic or PROM, for several
reasons, ranging from the size of the task to the size of the device.
With one output, you could generate only one state of a state machine, so I
imagine it would take several of the hypothetical devices to which you refer
to do anything useful. I find it difficult to imagine working with a finite
state machine with as many inputs as you suggest. That suggests a pretty wide
state register, and separate outputs, perhaps, and quite a few additional
inputs. With more than 8 product terms you'd have to share product terms
between adjacent macrocells until you have enoug of them. When you're done,
you could end up with all but 8 of the sum terms involved in some way, since 8
are used for the output enable at each input.
If you were ever to want to investigate, thoroughly, at least as thoroughly as
you could by building such a thing, a system that required such a complicated
logic function, with as many as 56 ORs of products with 1..20 ANDed inputs,
you would likely start with a simulator and not with hardware. You'd then
write a top-level functinoal simulation program and then test it with a sample
program. After that, you'd descend, step-by-step in to the bowels of each
module, simulating it as you think you'd implement it, substituting thousands,
or tens of thousands of ANDs and ORs, etc, for what was a bunch of registers
or adders, or whatever, refining your work as you progress to ever lower
levels until you've arrived at a simulation, at the gate-level, of what you
eventually plan to build. At every step of the way, you can test the
simulation. If you've written your simulator well, when you're done, you can
construct the device at the gate-level or at the SSI/MSI/LSI level. Your
result should quite well match the simulation. In my estimation, all this is
much simpler, because the tools already exist, and easier because there's help
available, if it's done with the modern hardware and accompanying tools. With
the free tools from Xilinx, for example, you have Verilog an VHDL, schematic
entry, graphical FSM entry, and lower-level PAL-style (ABEL) tools, all of
which can be used together. You can design in the large or at the SPLD level.
You can design a system and verify its logic without ever soldering a wire,
and get representative simulations of your work via the simulator that they
provide. Further, you can specify your design at behavioral, structural, and
register-transfer level and migrate from one to the other as needed in order
to specify more precisely what you want. You can even specify the design
using your own TTL library with timing and all as specified for the type of
logic you intend to use rather than using XILINX programmable logic, though I
don't know that for certain. You might have to do this last step in someone
else's freeware HDL.
Doesn't this seem less spainful than (a) finding a set of bare wire-wrap
boards, (b) installing sockets, (c) working out a large schematic design, (d)
acquiring the long list of parts, only some of which you'll already have,(e)
integrating the various modules you fabricate and test separately, (f) finding
the problems and going on only when there don't appear to be any more (else go
to (C)...) (g) and then, finally, going to the step at which you'd have
arrived without ever fiddling with any hardware with the former approach? You
don't really EVER have to implement anything in programmable logic unless you
want to, but you can use all the tools to support a development in
SSI/MSI/LSI.
Received on Tue Apr 16 2002 - 13:42:59 BST