Blog Post Actions
Group Actions
Engagement
  • Author Author: SGarciaV
  • Date Created: Date Created
  • Views 307 views
  • Likes 1 like
  • Comments 5 comments
Related
Recommended

Back to Karnaugh

SGarciaV

Back in school I had a few courses in digital electronics, so Karnaugh maps were not something alien to me. Unfortunately, my life experience never took me down a path where I had to simplify Boolean equations.

 

A current software development project required a screen with various UI options to allow the user to configure the application. Among the usual validations that I had to perform on the entered selections was one that was somewhat unusual.

 

The application provides logging functionality and also calls an external process that also performs logging functions. In both cases the folder location of the log file can be specified by the user. The UI elements to handle this were the following:

 

    1. A checkbox that allows the user to either enable or disable logging for the application.
    2. Another checkbox to specify that the external application should use the same log folder as the calling app.
    3. A text field where the user types in a valid folder specification where the log file will be created.

 

The validation is a success when either of these checkboxes are ticked and the folder specification is valid or when neither checkbox is ticked. Of course, I could have just put together an interesting IF statement that would accomplish the required tests, but I wondered if I could put together one Boolean formula (function) that would return the status of the validation given the rules above.

 

That’s when I remembered the Karnaugh maps. I also came to the realization that I did not remember how to use these maps. I already had the truth table:

 

a = Log enable/disable check box

b = External app uses same log folder as main app check box

c = Valid folder specification text field

 

 

a b c    Valid

0  0  0    1

0  0  1    1

0  1  0    0

0  1  1    1

1  0  0    0

1  0  1    1

1  1  0    0

1  1  1    1

 

I just needed to remember the technique for setting up the map, inserting the result values and deriving the resultant Boolean formula. After doing some research and reading I managed to perform the first two steps (left side of image):

I should note that I had completely forgotten that little rule that indicates that the rows (or columns) should be numbered such that only one bit changes. I had initially numbered the rows 00, 01, 10 and 11, but when I read that I changed it as shown above.image

 

After a bit more research I understood how to get the formula’s terms which are also shown above. The translation of this formula to code was easy from here:

 

Function fLoggingUIIsValid() as Boolean

 

    Return (Not chkboxEnLog.Checked and Not chkboxXAppLog.Checked) or

                     fFolderExists(txtboxLogFolder.Text)

End Function

 

And there it is. This worked nicely for my purposes. Regards.

  • in reply to SGarciaV

    Salvador

    In boolean algebra, the "+" operator is commonly used to denote an OR operation as a dot at mid height represents a AND operation

    never took algebra ...too keen to get away from school into work.

    Funnily enough maths has become very important in software image

     

    Thanks

    mark

  • Thanks for the remarks all.

     

    Shabaz, your function will work as well. I guess I am just in the habit of testing for valid results, not invalid. Your code reflects a conversion of my formula from sum of products (/a/b + c) to product of sums (a+b) AND /c. The production code will contain enough of an explanation to allow me and anyone else to understand what the function is doing. I have way too many projects and will most likely not remember this function within a few months.

     

    Mcb1. In boolean algebra, the "+" operator is commonly used to denote an OR operation as a dot at mid height represents a AND operation. Having the formula /a/b + c is the same as saying not a AND not b OR c. Perhaps a bit clearer would be ((not a) AND (not b)) OR c. I hope I've answered your question since I am not sure if I understood it. Salvador

  • in reply to shabaz

    Frequently there is no point in optimizing the detail of the code if you are using a high level language (especially C or if logic VHDL or Verilog).  The compiler/synthesiser will often do a better job than the coder so it's much more useful to concentrate on readability and clarity at the coding level.

    Usually there are only very small gains in performance to be had by helping the compiler and much larger gains from optimising the algorithm. I find the best rule is write code which reflects my intent, let the compiler do its bit and only contemplate tuning the details if there is a performance problem. It can be rather fun to compare a compiler's output from Shabaz' example with optimisation set to different levels.

    Karnaugh maps had their heyday in the era of boards full of logic chips but I suppose are mainly of interest to compiler or synthesiser writers now.

     

    MK

  • in reply to mcb1

    Depending on the use-case, it may not be easy to always follow. Personally I would have written it differently, so that it can be understood six months afterwards - but then my memory is not as great as some people.

     

    validation=SUCCESS;
if ((box1.checked || box2.checked) && (!folder.valid)) // if a box is checked, then we ought to have had folder information
  validation=FAILED;
return(validation);

     

    It may work out to a couple more machine instructions of course.

    But Salvador's method is efficient, if that is the main aim.

  • Never did study that, and during my training the Logic course was the worst.

     

    Looking at your truth table it seems that whenever c=1 its valid or when a,b and c = o its valid.

     

    You might want to expand on how you got from the formula to the expression ( ie how does '+ c'  translate to an OR)

     

     

    very useful thanks for sharing

    Mark