Timeline for How to map a truth table to ternary logical functions?
Current License: CC BY-SA 3.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 18, 2017 at 13:57 | vote | accept | HJLebbink | ||
| Dec 12, 2017 at 15:49 | answer | added | HJLebbink | timeline score: 2 | |
| Dec 11, 2017 at 13:48 | vote | accept | HJLebbink | ||
| Dec 18, 2017 at 13:57 | |||||
| S Dec 11, 2017 at 13:48 | history | bounty ended | HJLebbink | ||
| S Dec 11, 2017 at 13:48 | history | notice removed | HJLebbink | ||
| Dec 5, 2017 at 3:18 | answer | added | Pål-Kristian Engstad | timeline score: 4 | |
| Dec 4, 2017 at 19:15 | comment | added | Tony Stewart EE since 1975 | actually 2 sets of tables with combinations of 2 of 3 functions(or,and,xor) not counting their input/output complements and 0/1 | |
| Dec 4, 2017 at 18:53 | comment | added | stark | For 4 inputs you need a maximum of two 3-input tables selected by the 4th input to generate any possible function. The selector can be done by a third 3-input table, so the worst case for 4 inputs is 3. Not sure how to either generalize that or to reduce it, though. | |
| Dec 4, 2017 at 18:51 | comment | added | Tony Stewart EE since 1975 | Normally EE's might use a brute force programmable logic chip to reduce 256 functions and create a connection map with sets of 3 input OR,AND,XOR gates , 2 inputs and inverters for inputs or outputs to produce a 1 bit logical output from a 1 byte hex function.. I probably still dont understand | |
| Dec 4, 2017 at 16:17 | comment | added | HJLebbink | @user110971 The standard algorithms (that I'm aware of) do not reduce to arbitrary ternary logical functions (that is the question). They simplify to 3-in NANDs, and 3-in ANDs, but not all other 3-in logical functions which would allow a much more compact reduction. | |
| Dec 4, 2017 at 16:12 | comment | added | user110971 | @HJLebbink So, why not use one of the standard algorithms? How big is your table? What proportion of the entries require a high output? | |
| Dec 4, 2017 at 16:02 | comment | added | HJLebbink | @user110971 When I reorder my data structure such that the first bit of 512 integers are stored consequently in memory, same for the second bit, third, etc., I can reduce the number of memory access (gathers) considerably. My software program now contains a large truth table that that I like to simplify. I do not simulate hardware, I write HPC software. | |
| Dec 4, 2017 at 15:39 | comment | added | user110971 | I read the original question at SO and I am still not sure what you are trying to achieve exactly. Do you need faster simulation times? I have simulated very large systems, e.g. FPUs, memory controllers, and a communication stack on top, without much trouble. The limiting factor seems to be RAM access speeds, not CPU processing. | |
| Dec 4, 2017 at 15:32 | comment | added | user110971 | @EugeneSh. I think the problem reduces to Boolean minimization, which is NP hard, because otherwise you could solve the SAT problem. At least this is what I think the OP is asking. | |
| Dec 4, 2017 at 15:24 | comment | added | Eugene Sh. | @user110971 I don't think so.. I think you confuse with the SAT problem. | |
| Dec 4, 2017 at 15:20 | comment | added | user110971 | I believe this is NP hard for binary functions. | |
| Dec 4, 2017 at 15:03 | comment | added | Eugene Sh. | There is no even formal way to "map" to an arbitrary binary function. And not every binary function comprise a complete functional system. The same is true for ternary. | |
| S Dec 4, 2017 at 10:11 | history | bounty started | HJLebbink | ||
| S Dec 4, 2017 at 10:11 | history | notice added | HJLebbink | Draw attention | |
| Dec 3, 2017 at 17:03 | history | tweeted | twitter.com/StackElectronix/status/937366750227779586 | ||
| S Dec 3, 2017 at 13:03 | history | suggested | Rodrigo de Azevedo | CC BY-SA 3.0 | Minor improvements |
| Dec 3, 2017 at 10:23 | review | Suggested edits | |||
| S Dec 3, 2017 at 13:03 | |||||
| Dec 2, 2017 at 0:11 | review | First posts | |||
| Dec 2, 2017 at 1:56 | |||||
| Dec 2, 2017 at 0:10 | history | asked | HJLebbink | CC BY-SA 3.0 |