Electronics > Projects, Designs, and Technical Stuff

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

<< < (3/4) > >>

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

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

rastro:

--- Quote from: intabits on February 02, 2020, 10:54:28 am ---...
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)
...

--- End quote ---

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.



--- Quote from: rstofer on February 02, 2020, 04:44:13 pm ---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...
--- End quote ---

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.



--- Quote from: FenTiger on February 02, 2020, 07:23:58 pm ---I've used Espresso for analysing truth tables like this before.

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

--- End quote ---


"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:-




--- Quote from: Rerouter on February 03, 2020, 03:01:15 am ---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?
--- End quote ---

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


Navigation

[0] Message Index

[#] Next page

[*] Previous page

There was an error while thanking
Thanking...
Go to full version
Powered by SMFPacks Advanced Attachments Uploader Mod