Re: [OT] Byte-wise boolean optimisation

Jim Granville wrote:
Thomas Pircher wrote:
Basically I have 8 truth-functions f7(.) ... f0(.) representing the bits
7..0 of the result byte, and I would like to find an optimised function
f(.) which gives the same result as the single-bit-functions together and
uses 8-bit parallel boolean operators.

I'm unclear - do you want a one byte answer, from an 8 byte variable
set, and you want to use common byte-wide operators, to get to the answer?

Hi Jim,

fortunately my case is slightly simpler. I have one input byte and one
output byte and a given algorithm to transform the former into the latter,
but I want to simplify the algorithm to use just logic operators (instead
of loops).

To be more precise, I'm working on a source code generator for CRC checks
(http://sourceforge.net/projects/pycrc) and I would like to overcome the
shortcomings of the bit-by-bit algorithms and the table-driven
implementation: I don't want to loop over 8 input bits to update the CRC
for one byte and I don't want to keep table in ROM as the table-driven
implementation requires.

Sounds a fairly big ask, as you will need 'leave alone' operations many
times.

With commonly used Polys (which happen to not contain too many ones) it does
not look so bad. But for other Polys, I get terribly long expressions.

You could easily feed the eqns into any CPLD/FPGA tool flow,
and inspect the output eqns for each bit, which will of course be
optimised, but using bit operators. Then, you could work backwards, to
see if any can be merged into multi-bit operations.

This will lead to the following approach: Quine-McCluskey (and Petrick's
algorithm) for all 8 output bits and then finding some common patterns in
the resulting sums of products, based on heuristics (e.g. the 'sum of
product' for one bit is often similar to the sum of products of an adjacent
bit, just shifted by one).

Ok, I admit it, I was asking for the silver bullet, but I see I have to go
down the hard way. :-)
Any suggestions are more than welcome!

Cheers,
Thomas


--
Posted via a free Usenet account from http://www.teranews.com

.

Relevant Pages

  • Re: Is there a polynomial algorithm for that problem?
    ... The sum over all n numbers is negative. ... Unfortunately that algorithm does not scale. ... An instance of 3-Partition consists of a list of 3m positive integers ... list can be partitioned into m lists of size 3, ...
    (sci.math)
  • Re: Choose k random lines from file
    ... > What, for the algorithm shown above, or for any algorithm? ... Yes, that is an unbiased generator, but I had thought ... >>give less of a bias using an extra float or double ... >>distribution for the sum. ...
    (comp.programming)
  • Re: standard deviation, but without the mean
    ... Suppose Xsum is the sum of the the first n numbes and that X2 is ... Just keep track if X2 and Xsum as you go. ... Actually this is not a correct algorithm, ... the error in the least 9 digits.. ...
    (sci.stat.math)
  • Re: C# generic containers from a "C++ perspective"
    ... If you implement the floating-point and integer algorithms ... Maintain the sum of all the items in an accumulator. ... That is the fundamentally-broken algorithm that I was expecting you to ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Disjoint circle merge NP complete for L^n error?
    ... The key point is that we need to be sure there is no optimal algorithm ... We only need to erase MAX and replace with SUM in the proof ... minimum error partition) algorithm in P. ... MAX. I'm pretty sure that if both these are in NP then all L^n metrics ...
    (comp.theory)