Looking for an algorithm to help deciper the contents of a PAL

[intabits]

Possibly I'm going senile, but after much consideration, no solution to this has jumped out at me.
I just hope that I haven't embarrassingly missed an obvious answer.

I have a Programmable Logic Array (PAL) with 10 inputs and 8 outputs.
(But it could be any stateless black box containing digital logic elements where the output bit values depend solely on the current input bits)

Suppose that all 1024 combinations of the input bits have been applied to the device, and the resultant output bit values recorded.
(eg: into a 1024 byte array)

What I want to do is:-
For each output bit, determine which of the input bits affect it.
(Possibly also generating a truth table for the output)

To help visualize the problem, a simple example with 3 inputs and 2 outputs:-
If you want to first try nutting this out in your head, avoid viewing the answer at the end of this post.

inp out
ABC XY

000 01
001 11
010 00
011 10
100 11
101 01
110 10
111 00

Problem: Which of the inputs A,B,C determine the value of output X and which determine the value of output Y?

Obviously a clean, elegant solution is best, but I would be happy with even the most brute force approach that works.

Thanks in advance for any help with this...












Answer:-
X depends on A and C    (X=A Xor C)
Y depends on B      (Y=Not B)

[iMo]

Call Bletchley Park
You have only three basic functions AND, OR, NOT.
Brute force would mean to check all possible wiring combination of those 3 functions (also chained in any depth) inside the black box (10 inputs and 8 outputs). The number of combinations could be limited by the number of functions which physically fit the box. If you knew the internal structure it would help. And you know the PAL type, do you?

[magic]

To elaborate on the predecessor, isn't PAL basically a physical realization of the CNF/DNF (don't remember which one)?

CNF/DNF = conjunctive/disjunctive normal form, look up what that is. I suppose there are known algorithms for extracting them from a truth table. I don't remember details.

[SiliconWizard]

The starting point would probably be that: https://en.wikipedia.org/wiki/Karnaugh_map

[rstofer]

Right away, you can drop C from the Y term based on just the first two decoded lines.  I can't even imagine using a Karnaugh Map for 1024 inputs.

Elegant, you say?  How about stuffing the entire input/output relationship into a VHDL 'case' statement and then using the schematic view after synthesis.

Obviously, you would want to write a bit of code to generate the VHDL from a simple input file.  I did a lot of this kind of coding for code translation tables for my IBM1130 project.  ASCII -> Hollerith for the card reader, Printer Code -> ASCII for the printer output and so on.

https://reference.digilentinc.com/_media/textbooks/realdigital_module_4.pdf

Or, you could write the grand-daddy of all FOR loops, twiddling input bits and tracking which affect  what outputs using your input vs output table.  You would be trying to drop input bits from consideration like I did with the first two lines.  I wouldn't expect each output to be a function of all possible inputs unless the device is used as some kind of decoder.  I guess I would, for each output, keep a list of which input bits had an effect on the output bit.  Python?  It does lists pretty well.  Still, I might use Fortran with a large array.  After the DO loop, I would expect only a very few inputs to affect an output.

[SiliconWizard]

Right away, you can drop C from the Y term based on just the first two decoded lines.  I can't even imagine using a Karnaugh Map for 1024 inputs.

Of course you'll have to implement something programmatically, not do that by hand. Still useful to know the basics for that.

[rstofer]

If you have to write code, why not use an Arduino?  The idea is to avoid having to write or rewrite a gigantic logic table by having the PLA tied to the Arduino through an IO expander.

Finally, we need to deal with 5V vs 3.3V.  Let's just keep everything 5V by using an IO Expander rated for 5V

https://www.sparkfun.com/products/15099

Since the expander is only 8 bits wide, we need to deal with the other 2 address bits.  A second expander is the easy way but they have to have different I2C addresses and the code needs to change the upper address bits after cycling through the lower 256 addresses.  This will get awkward.

You will just have to write a function that converts the 10 bit address to two 8 bit values for the expanders.  Once this is known to work, how awkward it is kind of goes out the window.

The PLA outputs connect directly to some Arduino input pins.

The serial terminal will output the equation for each output.  I haven't thought this through.  If we just print the numeric addresses that produce a '1', we just recreate the logic table that may already be known.  More accurately, of course.  We will be getting a sum of products for each output.  But, as yet, we haven't eliminated any bits.

Do we capture all of the sum of products and then use another bit of code to eliminate address bits?  Probably.  Maybe it can be done in the Arduino but it is seriously short of memory for large arrays

Or maybe the answer is to take each 10 bit address that produces a '1' output and wiggle each bit to see if it is part of the equation and just send the bits that matter.  Perhaps each of the 10 bits is stored momentarily in an array with 3 values:  0 -> active inverted bit (like NOT A13), 1 -> active true bit, 2 -> inactive bit.  After dropping the inactive bits we have one equation. There are going to be a lot of duplicates as we iterate through all the addresses so we need to hold the array until we have tried them all and then send the equation to the terminal.  We know there will be a duplicate at every address where we have an inactive bit.

Should work...

It would be an interesting bit of coding.




 

[rstofer]

If we let the Arduino just output the truth table with no attempt at minimization, the output would be exactly what is needed for this bit of C++ code

https://www.codeproject.com/Articles/649849/A-Cplusplus-Karnaugh-Map-Minimizer-Infinite-Variab

Note that we would need to iterate over each output but that is to be expected.

Just having a machine created truth table (Arduino) is worth the effort.

[up8051]

PLD circuit diagram reproduction can be simple in the case of combination systems, e.g. PAL16L8 and more difficult in the case od registered PLDs e.g. PAL16R8
It should be remembered that even in a combination system, flip-flops can be created with feedback.

[rstofer]

I stuffed that Karnaugh code I linked above into Visual Studio 2019 and created a C++ Console Application.  I had to change a few instances of getch() to _getch() but other than that, it runs well.  There are a boatload of warnings but I ignored them.

The console inputs as shown on the web page have been changed and I haven't tried stuffing data from a file.  To do that I would probably have to actually run from the console.

I put in a 4x4 map with the center 4 squares = 1 and the perimeter 12 squares = 0.  The result came back BD which is correct.

This whole thing becomes moot if there are any RS flops created from gates.  Or any other type of storage...

ETA:

I stuffed the equations from the OP into the map program and it came up with the correct answers.  However, XOR isn't a fundamental operation so it came up with A'C + AC' - same thing.  Well, XOR may be a common logic gate but it isn't used in 'sum of products' notation.

[FenTiger]

I've used Espresso for analysing truth tables like this before.

https://en.m.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer

[rastro]

...
Suppose that all 1024 combinations of the input bits have been applied to the device, and the resultant output bit values recorded.
(eg: into a 1024 byte array)
...

This is my understanding.  There seem to be 2 general types of PAL's. 

Simpler PAL's will give consistent outputs based on the inputs regardless of the sequence they are entered - your method would work. 

More advanced PAL depend on states of prior inputs (implying memory) and in this case sequentially addressing the PAL may not fully reveal the underlying logic.  Simple brute forcing in this case would require running all permutations of sequences.  Probably something like 1024! (factorial)  or approximately 5.418 × 10^2639.  A large number indeed.  I'm sure there's probably clever ways to reduce some of the work in this case but it still seems formidable. 

If you have the PAL running in it's original system/circuit you may be able to determine if all the inputs are used and the sequences they arrive.  Again you would need to make sure the system it's embedded in is getting fully exercised to produce/present as many if not all inputs that the PAL should expect to see.

[intabits]

Thanks for the replies above. I'm glad the problem sparked some interest.

To the points raised:-

Bletchley Park, according to their very dated looking website, state that they can only entertain decipher requests made in German, and all submitted data must be in either Morse or Baudot 5-code.

The device is a PAL10L8, and there is also a PAL12L6.
I have used an Arduino to read both of these, and have all the data on a PC.

The 12L6 is not a problem, as it is used as an address decoder. It's inputs are the address bus, and it's outputs are various chip select signals. Thus, all outputs are dependant on all inputs, and from the results, it is very clear that the data is correct and matches the published memory map for the system it is used in: The "Compacta Uniboard" described in another thread:- http://www.vcfed.org/forum/showthread.php?72532-Compacta-Uniboard-A-6809-SBC-cicrca-1982

The 10L8 is used in more of a "glue" role, where there may be two or more distinct and independant input-output groups. The whole reason for this thread is so that I might verify that it's contents are correct by seeing that it's outputs as used in the circuit would reasonably depend on various of the inputs. And to gain a better understanding of the circuit operation.

I don't think I'd ever heard of CNF/DNF, but yes, these devices are DNF - an "OR of ANDs", or "a sum of products"

I knew a little of Karnaugh Maps, but not much. And from the reading I've done, they are not well suited to truth tables of the size involved here. Though related links uncover other techniques that may be more appropriate.(except that what I've found is so theoretical and hard to grasp)

I was afraid that the problem was not so simple that avoiding these very technical areas would be impossible. A lot of mostly unfamiliar mathematical notation is involved, along with a lot of totally unfamiliar terminology (defined in terms of yet more terminology...).

Delving very deeply into these areas may require more effort than is justified for my mere wish to better understand the circuit I'm working on. I was hoping for a quick and simple solution that I might have missed.

Right away, you can drop C from the Y term based on just the first two decoded lines.  I can't even imagine using a Karnaugh Map for 1024 inputs.

...  How about stuffing the entire input/output relationship into a VHDL 'case' statement ...

''' you would want to write a bit of code to generate the VHDL from a simple input file ...

Or, you could write the grand-daddy of all FOR loops...

That's the sort of algorithm I was thinking of, with nested for loops for inputs|outputs|table entries to detect inputs that are irrelevant to an output, but got a brainache before a result.
The "wiggle each bit to see if it is part of the equation" method is also along the lines I was thinking of. I'll look further into that...
I can't even spell VHDL, so going there is not desirable to me.

The Arduino was used to extract the truth table, this has been done already.
Further programming to analyze it will happen on a PC (using Delphi, as I do for everything)

The "Karnaugh map minimizer" link is of interest. Other paths explored turned up "Logic Friday", which I've downloaded and will have a play with:-  https://web.archive.org/web/20131022021257/http://www.sontrak.com/

The PALs are not registered, so the stateless black box described above applies.

I've used Espresso for analysing truth tables like this before.

https://en.m.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer

"Logic Friday", mentioned above seems to be a user friendly implementation of Expresso.
I about to try it out...


Thanks to all for your interest and input.

[Rerouter]

As you have the entire mapping of inputs to outputs. Care to post it in this thread. Either quoted text or some text / csv file?

Look for the easy input vs output connections then use the gaps to work out the internal connections.

[intabits]

Logic Friday seems pretty nifty. I dumped my truth table in the format it requires and it could generate a gate diagram from it. The diagram can be edited easily to modify it or format it for readability.

There's more to explore with it, but I think it suits my basic needs, as it shows that all outputs depend on at least some of the inputs. And I can use it to answer my questions about which inputs affect a particular output, and how.

For now, I think I have what I wanted.
Thanks for all the suggestions.


Logic Friday screen captures:-

After import:-


Initial gate diagram generated:-


After allowing all gate types to be used:-

As you have the entire mapping of inputs to outputs. Care to post it in this thread. Either quoted text or some text / csv file?

Sure. Here's the truth table in Logic Friday import format:-
https://pastebin.com/pTfFtfyQ

If not suitable, I can change it to suit. But If you install Logic Friday (simple), and import this format, it can be exported as a CSV.

Note that on the Uniboard, the PAL (U40) input pin 4 is tied high, so it's not in the LF file above, and all TT entries where it is low have been left out. (which I think should be OK?)

The Uniboard schematic:-


Logic Friday download:-
https://web.archive.org/web/20131022051518/http://www.sontrak.com/downloads.html

[NivagSwerdna]

I've used Espresso for analysing truth tables like this before.

https://en.m.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer

Thanks for that reference. I haven't come across this before; also Logic Friday. 

[rstofer]

Great tools!  Way better than rolling your own.
I may download LogicFriday just to see if it will produce a NAND  only (or NOR only) solution.

[intabits]

Great tools!  Way better than rolling your own.
I may download LogicFriday just to see if it will produce a NAND  only (or NOR only) solution.

Yes, it can:-

[iMo]

Mind propagation delays 

[up8051]

After some reverse engineering, based on the posted file:

/FDCWR =  PIN8 * /EF3X * /E * /RW
              + /PIN8 *                     RW


/FDCRD =  PIN8 * /EF3X * /E *  RW
            + /PIN8 *                     /RW


/BENQ =  A0 * MemEna * DGrnt * /E

/BENE = /A0 * MemEna * DGrnt * /E


/CAS0 = /A0 * /A15 * MemEna * DGrnt * Q4 * /E


/CAS1 =  A0 * /A15 * MemEna * DGrnt * Q4 * /E


/CAS2 = /A0 *  A15 * MemEna * DGrnt * Q4 * /E
      +                                                        Q4 *  E


/CAS3 =  A0 *  A15 * MemEna * DGrnt * Q4  * /E
      +                                                        Q4  *  E


This would still need to be tested.

Regards,
up8051 aka JarekC.DIY