Electronics > Projects, Designs, and Technical Stuff
Looking for an algorithm to help deciper the contents of a PAL
(1/4) > >>
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.
Navigation
Message Index
Next page
There was an error while thanking
Thanking...

Go to full version
Powered by SMFPacks Advanced Attachments Uploader Mod