[OT] Byte-wise boolean optimisation

Hi all,

I'm wondering if there exist algorithms for byte-wise boolean optimisation, much like the Quine-McCluskey works for a single bit.

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.

Obviously I can write f(.) = f7(.)

Reply to
Thomas Pircher
Loading thread data ...

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 ? Sounds a fairly big ask, as you will need 'leave alone' operations many times.

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. Atmels WinCUPL has choices of optimise.

-jg

Reply to
Jim Granville

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

formatting link
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.

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.

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
Reply to
Thomas Pircher

We have looked at this in the context of compiler processing of booleans. Parallel and's and ors are quite easy. Generic boolean expressions are a lot more difficult to accomplish and there is no general solution that I know of. We do check in our compilers if boolean bits are in the same byte (or processor native word size) and generate code that take advantage of this for simple and and or operations.

w..

Thomas Pircher wrote:

Reply to
Walter Banks

The most simple way to do that is to use a table. Use your f1..8() functions to create the table either at runtime or at compiletime, whatever fits better.

Reply to
jetmarc

This is a highly interesting subject to me, so please avoid top-posting. Your answer belongs after (or intermixed with) the quoted material to which you reply, after snipping all irrelevant material. See the following links:

--
  
  
 Click to see the full signature
Reply to
CBFalconer

Oh FFS. CBF, please give this newsgroup-policing mania of yours a rest! It's getting tiresome, to the point that I'm considering plonking you, which would be a shame given the quality of the signal (despite the noise) you occasionally put out.

Steve

formatting link

Reply to
Steve at fivetrees

Well, straight-forward is a Good Thing (tm) IMHO. And there's really little you can do to improve on your code above. After all, you still have to call each function in order to get all the bits, and you have to associate each bit with the correct function.

You are potentially wasting time with the shift operators (depending on how smart your compiler is). I'd probably write a function like

unsigned char get_byte() { unsigned char result = 0;

if (f0()) result = 0x01; if (f1()) result |= 0x02; if (f2()) result |= 0x04; if (f7()) result |= 0x80;

return result; }

Not an elegant one-liner, but it should generate nearly optimal code.

If you want a statement rather than a function, you could do something like

byte = (f0()? 0x01: 0) | (f1? 0x02: 0) | (f2()? 0x04: 0) | (f7()? 0x80: 0);

But that's not much better than your original, but it at least avoids the shifts if the compiler can't figure out that f0..f7 return single- bit values.

If you want to get really crazy with the syntax, you could try

#define f_bit(n) (f ## n()? (1

Reply to
Dave Hansen

The following code will implement parallel and , or operations on a byte or word var. This is approach works for CRC's and other simple feedback polynomials.

Create a mask of the bits of interest say bits 0,1,3,7 #define b0 (1 > much like the Quine-McCluskey works for a single bit.

Reply to
Walter Banks

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.