see below, plz.
Dick
----- Original Message -----
From: "Tony Duell" <ard_at_p850ug1.demon.co.uk>
To: <classiccmp_at_classiccmp.org>
Sent: Saturday, April 13, 2002 5:51 PM
Subject: Re: TTL computing
> > > Well, considering core memory is radiation hard and non-volatile, I
would
> > > think it could be considered to be better than semiconductor RAM for
some
> > > applications. It's also got a much longer lifetime (when was the last
> > > time you had a core plane (not the drivers) fail?)
> > >
> > It really doesn't matter which part of the core memory subsystem fails,
does
> > it?
>
> Actually, yes it does. As core is non-volatile, a failure of the drivers
> will leave the data in the core substatially intact (a failure of the
> core plane wouldn't).
>
> > BTW, I've never had a memory failure on a PC. I've had numerous ones in
> > varous older commercial systems, but never a hard failure in a PC memory
>
> I've had semicondcutor RAM fail, albeit not DRAM in a PC. 2114s are
> particularly bad for this.
>
I don't think it's the parts, but, rather, the way in which they're used. I
have noted that 2114's seem to have a problem. I also wonder at the relative
freedom from memory problems in the PC environment. I did occasionally have
memory problems back in the CP/M days, mostly due to poorly timed DRAM
circuits.
>
> > > > A PAL can generate any combinatorial function of its inputs. A prom
can
>
viewing its inputs in terms of the fact that PALs generally have 8 or more
outputs, and in view of the fact that those separate outputs may not want to
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.
>
> > >
> > > Sorry, but absolute rubbish (well, I'll qualifiy that. Given a large
> > > enough OR matrix, it's possible, but all real PALs have a very
restricted
> > > OR matrix).
> > >
> > Nevertheless, while they have a fixed OR matrix, they have a very flexibly
> > programmable AND array, which allows you to express any logic function of
the
> > number of inputs you have in SOP form. Keep in mind that you can use
multiple
>
> No it doesn't!
>
> Any real PAL has a limited number of OR terms for each output. (typically
> around 8 or so).
>
What this suggests is that you've chosen the wrong device. You can't do the
same things with ANY device. Take a look at the spec for the 16V8 and compare
it with the 42VA12. Clearly, they have different size "fuse" arrays, and, if
you want to program the device such that it produces functions of a size that
consumes the entire "fuse" array, then you'll end up with a single output, but
you can implement that function. With the 42VA12 you have 64 product terms,
each of which can have any combination of the 42 inputs. On the 16V8 you have
less flexibility. MANY functions will fit in a small device like the 16V8.
It has a relatively small fuse array, in general, smaller than what's in a
PROM, though it's larger than 32x8.
>
> So I take my function. I write it in SOP notation. I combine terms that
> differ by one containing a particular variable and the other containing
> its inverse when all other variables are the same (like
> A.B/.C.D/.E + A.B/.C/.D/.E -> A.B/.D/.E).
>
You can let the software deal with optimizing that process, and in assigning
the polarity of your outputs so the fewest product terms are used. This one
is a single product (OR) term.
>
> I then end up with more than 8 (or however many OR terms I've got) terms
> ORed together in my equation. I can't minimise any more. And I can't put
> it into the PAL.
>
ALL that tells you is that you've picked too small a device, or one with the
wrong architecture. All PLD's don't have to be small ones, just like ROMs.
>
> I've not worked out what the maximum number of terms I might need for
> any <n> input function is, but I'll bet that when I do, you need as many
> bits to specify them as you have in an 2^n bit PROM.
>
You do have to choose the right device, but, in general, you have lots of
inputs, of which you can use any combination of AND's, and the number of OR's
that the device architecture provides. Some parts, e.g. 20X10, 20RA10, etc,
have relatively few product terms, though they can use all the inputs in
various combinations in the AND array. Part of choosing the right device, is
figuring out whether you're after a function easily expressed as SOP, or
whether you really do want a PROM. There are also devices that have both the
AND array and the OR array programmable. That allows sharing of product
terms, among other things. A lot depends on what your objective is. If you
want to produce the logic required for block 2G on that diagram I wrote about
a day or two back, you may want to approach the problem differently than if
you want to include several blocks and use a larger device. The difference
between the result that you get with a PROM versus a PAL, is that the PAL
allows you to put the registers in the device along with the logic, and to use
the resulting outputs as inputs, which lends itself nicely to generating clean
Moore and Mealy machines. If you think you want to secure your design, you
certainly can do more to that end with a PAL than with a ROM and external
registers and logic. The timing benefits from keeping the devices
self-contained, as does power and PCB routing. Layout errors are also easily
fixed with PALs, while that's not as easy on discrete logic.
>
> 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.
> >
> > > Let's consider a single-output combinatorial function of <n> inputs.
> > > There are 2^(2^n) possible functions (including ones that ignore some or
> > > all of the inputs).
> > >
> > You're running down an unimplementable path again, Tony. You can't
implement
> > all those functions in a comparable ROM either. For starters, though,
let's
>
> Of course I can!. I can implement any of the 2^(2^n) functions in a 2^n
> bit ROM (which has n address inputs). There are _exactly_ that many
> possible programming patterns of the PROM, each one corresponding to a
> different function.
>
SO you use a PAL with a fuse array of comparable size.
>
> > postulate that you've got, at most, 22 inputs. (a 24-pin device with Vcc
and
> > Gnd). Each pin you use as output, of course, has feedback, but it's not
an
> > input. Nevertheless, that means 44 signals to the AND array, since each
input
> > is in true and complement form.
> > Quite obviously, you can AND whatever combination of these that you want,
and
> > use up to 8 of these sum terms in, say, a 22V10. Since a ROM doesn't
share
> > inputs and outputs, you'd be dealing with a larger package, but, since
you've
> > only got 8, 10, or maybe even 12 outputs, there's a limit on what you can
> > derive from that number of inputs. PALs have the same technological
> > restrictions as PROMs, so whatever size of fuse array you can generate in
a
> > PAL, you can also have in a PROM, and vice-versa. Now, I won't say it's
>
> All you seem to be saying here is that both PROMs and PALs have finite
> size. Which is not something I disagree with.
>
> 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.
>
> Of course you can make a PAL (defined as a programable AND array followed
> by a fixed OR array) that can implement any cominatiorial function of the
> <n> inputs just like a PROM can. This is related to the fact that you can
> write any function in SOP or POS notation I think. But the resulting PAL
> will be as complex as the PROM.
>
Nobody said the device is simpler than the PROM. The job of concocting the
PAL is made easier by the rather well-developed tools that we have, though.
Generating the fuse map for the PROM when you have 22 inputs is a big job and
requires a big PROM, even though the functions are mostly simple. consider
what happens if you have 16 inputs, 6 outputs, of which four are inverters
with tristate outputs and the other two are strobes decoded from the
addresses, with totem pole outputs that remain enabled. That would be a
problem in a PROM in any event.
>
> The reason PALs are useful is that many functions used in the real world
> will fit into them. But not all....
>
> > > This is easy to see. Think of writing out the complete truth table of
the
> > > function. It's got 2^n lines (one for each of the possible combinations
> > > of the inputs). In each line we have to pick the output bit, either 0 or
1.
> > >
> > Truth tables are an unwieldy way to create/analyze PALs, though they were
once
>
> Oh for %detiy's sake. Have you actually read what I have written?
>
> I am not proposing that you use truth tables to actually design the data
> for a PAL.
>
> What I am saying is that every combinatorial function has a truth table.
> And that it's possible to count how many possible combinatorial functions
> there are by consdiering these truth tables.
>
It seemed that you were headed there because you have to do that to create the
equivalent PROM, and folks used to generate truth tables and reduce them.
>
> Let me give you an example.
>
> Suppose, for some reason, you want to know how many 2-input (let's call
> the inputs A and B) logic functions you could make (including things like
> 'always 0',. 'always 1', 'A', 'NOT(B)', etc).
>
> You could start by saying 'Well, there's 'A', and 'NOT(A)', and 'B', and
> 'NOT(B)', and '0'. and '1', amd 'A AND B', and 'A OR B' and 'A XOR B' and
> 'NOT(A) XOR NOT(B)' -- Ooops, we've just counted that one twice, as it's
> the same as 'A XOR B'' and so on. And you'll either count one function
> twice or you'll miss one.
>
> Or you could do it more systematically by saying ' Every 2 input
> combinatorial function has a 4 line truth table (the 4 lines
> corresponding to inputs (A=0, B=0), (A=1, B=0), (A=0, B=1), (A=1, B=1)).
> For each line in the truth table I have to pick the state of the output,
> either 0 or 1, So I have 2 choices for each line, so 2^4 choices for the
> entire table. Aha, there must be 16 ways to fill in the truth table, so
> 16 possible 2 input functions'.
>
> And that's _all_ I am saying here. I want to count the total number of <n>
> input functions (so as to see if there are enough different ways to
> program a PAL to cover all of them), so I consider a truth table. I am
> not suggesting using the truth table as a way to actually design the PAL.
>
> > the possible fuse arrays are about the same size, regardless of whether
you
>
> The 'fuse array' _is_ the programmable section. And the PALs I've used
> have needed many fewer bits to program them than PROMs with the same
> number of inputs (normlly called 'address lines' :-))
>
> > have a PROM or a PAL. How they're implemented differs somewhat, in how
> > they're applied, however. Because the OR array is fixed, fewer bits are
> > programmable, but then, if you use a PROM to generate random logic, there
are
> > lots of redundant bits. The PAL, with its fixed OR array, won't let you
>
> No there are not. There may be many redundant bits for many useful
> functions (this is _why_ PALs are actually useful -- because many
> real-world functions will fit into them), but that can't be the case in
> general.
>
> > generate a lookup table. If you need a lookup table, you'd use a PROM.
OTOH,
>
> A lookup table is just a combinatorial function.
>
> > if you need a decoder, that's straightforward enough using a single
output.
>
> Most decoders have the property that if you write the equation in SOP
> form, it's got only a few product terms (maybe only one). And that will
> fit into a PAL. sure.
>
> > >
> > > So I say again. Consider the 16C2. It has 16 inputs and 1 output (yes, 2
> > > output _pins_, but one is always the inverse of the other). Does it have
> > > 65536 programming fuses? No! It has many fewer. Therefore there are 16
> > > input functions you can't fit into a 16C2.
> > >
> > Well, you've picked a long-obsolete device type, Tony, but if you consider
> > what it was intended to do, I think you'll find it can detect and signal
any
> > unique combination of the 16 inputs. The 'C' means it's a comparator.
Have
>
> Actaully, the 'C' means Complimentary, refering to the fact that the 2
> outputs are always inverses of each other.
>
I can't find a databook old enough to have this part in it, but I do remember
seeing them once upon a time. Their purpose was to generate a programmable
decoder with a minimum of resources, apparently for cost reasons. The
true/compliment output was probably more to cover the potential requirement
for one polarity or the other, by giving you both, but that doesn't matter.
WHy not look at a more conventional sort of device that's survived, like the
16L8. It has seven product terms plus one for the output enable. That means
you can take all the inputs and create any combination of those in a single
product term. If the seven PT's aren't enough, you have to sacrifice the
output associated with one group of seven and pass it back as feedback into
the product term array via feedback, which one of the macrocells hasn't got.
That's the one, probably, to which you'd pass the feedback from another
macrocell. If you need a really complex function it can generate it, but you
have to use enough resources to do that. In this case, you have 64*32 = 2048
fuses. 1/8 of those are allocated to output enable product terms, so you have
only 1792 fuses with which to combine the 16 inputs into 8 outputs. This
gives you a flexibility you don't have with a ROM, i.e. enabling only one or
more of the outputs independently. Further, if you leave out the feedback,
which a PROM won't allow you to have unless you feed the outputs back to
address lines, which wil reduce the number of independent inputs you have, you
essentially have only 8 inputs and 8 outputs. That's 256 bytes, and that's
2048 bits, which is more or less what the 16L8 has. I'd submit that you can,
with a similarly sized PAL create pretty much the same range of combinatorial
logic that a ROM with the same number of storage bits has. Remember, if you
need ANY function of the 16 inputs, then you need a 64Kbit fuse array for each
bit of output. There are PLD's that are that large, but they're not commonly
used because the requirement for ANY combination of the 16 inputs is seldom
encountered. There are such things, however.
>
> And I am not disputing you can program a PAL to implement any function
> consisting of one product term (which is what 'any unique combination of
> the inputs' would be.
>
You seem to be ignoring the fact that you can use as many of the available
product terms as you like, however. That's why 16V8's, for example, are so
popular.
>
> > > The parts _you_ choose to design with [PALs, GALs, PLDs]
> > > The parts others choose to design with (for whatever reasons) [Just
about
> > > anything]
> > > The parts that have been used in the past [Ditto]
> > > Parts that could theoretically be created [e.g. a PAL with a large
enough OR
> > > matrix to implement any function, and which will have as many
programming
> > > bits as a PROM]
> > > Theoretical concepts [PDAs, Turing machines]
> > >
> > Yes, except that the last two are really not germane to the topic which
was
> > semantic. I don't disagree with you except in the sense that you continue
to
>
> Actually, the 4th item on the list _could_ be a real world part (there is
> nothing to stop you making a PAL-like structure with enough inputs to the
> fixed OR matrix), and it's what you're claiming exists if you believe
> that there are PALs that can implement any combinatorial function of
> their <n> inputs.
>
> Go back to that 22V10 for a moment. I don't have the data sheet in front
> of me, so I can't remember exactly how you can use the pins as inputs and
> outputs, but I think I can program it so I have 1 output, 21 inputs, and
> don't use any form of 'registers' or feedback terms. OK, I am not using
> all the PAL in that case.
>
Just to refresh your memory, the 22 is the maximum number of inputs, the V
indicates the "versatile" macrocell, and the 10 is for the number of outputs.
A 16R4 has 16 possible inputs to the AND array, which are available both true
and compliment, and there are 8 outputs, of which 4 are registered. You get
the idea.
In the case you cite, you are discarding most of the resources associated with
control, i.e. product terms for output enable, global reset, set, etc. aside
from the ones associate with the one macrocell you do use, and if you discard
the feedback terms, you have only 12 external inputs. You presumably would
choose the oututs that have 16 product terms, though. It wouldn't be
advisable to do exactly what you suggest, simply because you can leave the
outputs you don't use disabled and use their associated pins for input via the
feedback paths. If you do that, you do have 21 inputs.
>
> Now you claim I can use that to make any 21 input, one output, function.
> I believe it takes fewer than 2 megabits to program it, in which case I
> claim that your claim is plain wrong. Because there really are 2^(2^21)
> possible 21-input combinatioral functions.
>
There's a wide range of input combinations that you can implement in a 22V10,
but none with more than 16 product terms. If you need more complex functions,
there are some more complex devices you'd have to look at. Keep in mind,
however, that if you want to cover the entire range associated with 21 bits of
input, which is a 2 M word x 1 array, you'd need a pretty big PROM also. If
you get a part big enough to hold that amount of memory, you wont\'t fit it on
a 24-pin skinnydip leadframe owing to the die size. Now you're into a 44-pin
or so package. If you specify the logic equation you want to implement, I
suspect we can find a PLD large enough to implement it. What's made the PALs
popular is that most of the logic that one normally wants in a single device
is quite limited by comparison with what you've been addressing. True, it's
conceivable that one might, at least once in one's carreer, need a terribly
complex logic function that needs nearly a couple of dozen product terms. It
doesn't come up often, which is why the devices that support such functions
aren't so prominent.
Received on Sun Apr 14 2002 - 04:17:20 BST