Originally published on Computer Jagat in 1994
A.T.M. Shafiqul Khalid (Tuhin)
This article presents a new technique to simplify Boolean Expressions. The technique is simplier, more generalized and efficient than conventional K-map method and applicable for any number of variables.
Karnough map method of simplification of switching function becomes very difficult as the numbers of variables increase. For each combination of n variables or bits there exist exactly n different binary codes with Hamming distance 1. i.e., each binary combination has n adjacent combinations. Representation of such adjacency relation by Karnaugh map is very difficult for large values of n. The proposed KH-map method, however, will be able to overcome such difficulties.
METHODOLOGY & REPRESENTATION OF FUNCTIONS
A KH-map is a modified form of a truth table in which the arrangement of the combinations is particularly convenient. The new maps for functions of three and four variables are shown in fig. 1 and fig. 2 respectively. Proposed map for n variables containing 2″ cells equally spaced within a circle represents all possible combinations of n variables. Line(s) passing through the center that have been used for dividing cells, are MSB line(s). If v is the ith MSB variable then ith MSB lines or simply v-lines will be max( 1, 2*-2) in number. Those v-lines divide all the cells equally as formed previously by other MSB variables
of v. The combination contained in a cell can be calculated using following simple KH-algorithm:
1. LetCi,C2, …,C2n represent all cells.
2. Set Ci = 0, m = 1 for i = 1 to n do
for k = 1 to m do
Cm+k = Cm-k+l +m
end – for
m =2*m end – for
Alternative approach is to add 2k with each cell formed by mirror image of previous 2k cells, where 0 <= k < n and initialize first cell with 0. The process is quite similar to the process of gray code generation.
End points of the ith MSB line or v-lines is in such way that if one moves anti-clockwise direction from a cell then he will get at first v provided value of v in that cell is 1, otherwise he will get v’. The mid point of an arc of a cell is marked by • (small circle), x, or – sign depending on function values TRUE, FALSE or DONT CARE for the combination in that cell. The points marked by • are identified as TRUE or 1 vertices and points marked by x are FALSE or 0 vertices. Two vertices’ vl and v2 will be adjacent if line vl-v2, joining vl and v2 intercept even number of Mk MSB-line(s) while a single Mi MSB-line is perpendicular bisector of vl-v2 line where j<k and vl & v2 differ by jth MSB bit. Mi indicates 1st MSB and Mn indicates last MSB bit.
SIMPLIFICATION AND MINIMIZATION OF FUNCTIONS
A polygon consists of a collection of 2m vertices each adjacent to m vertices of the collection, is called a KH-polygon, and the KH-polygon is said to cover these vertices, where, 0 <= m <= n. Two consecutive vertices of the KH-polygon must be adjacent. Each KH-plygon of 2m vertices can be expressed by a product containing (n – m) literal, where n is the number of variables in the expression. Function f can be expressed as a sum of those product terms that correspond to the KH-polygon(s) necessary to cover all-of it’s 1 vertices. The number of product terms in the expression for f is equal to the number of KH-polygon. In order to obtain a minimal expression, all 1 vertices must be covered with the smallest possible number of KH-polygons, such that each KH-polygon is as large as possible. A KH-polygon contained in another larger KH-polygon must never be selected. If there is more than one way of covering the map with the minimal number of KH-polygons, then the covering that consists of larger KH-polygon must be selected.
From the foregoing discussions the following steps for obtaining simplified expression for f can be suggested:
1. Draw proposed KH-map for the function f of n variables. Start by covering with KH-polygons those 1 vertices that cannot be combined with any other 1 vertices.
2. Continue step 1 to those vertices that have only a single adjacent vertex for making KH-polygon of two vertices.
3. Next cover these TRUE vertices that yield KH-polygon of 2**- vertices and not part of any larger KH-polygon of 2k+i vertices, where i > 0 and k =
4. A minimal expression is one that corresponds to a collection of KH-polygon that are as large and as few in number as possible covering all TRUE vertices in the map of the fuction. A minterm for a KH-polygon of 2k vertices, where 0<=k<=n, will contain n-k literal. Minterm for the KH-polygon will not contain those ith MSB, where ith MSB line bisects any arm of the KH-polygon.
Example l.Fig. 3 represents KH-map for the expression f(w,x,y,z) = 1(0,1,2,5,7,8,9,10,13,15)
For abed polygon, ab and ad arm are bisected by w-line and z-line and minterm for the KH-polygon
abed will be x’ y’ that contain only x and y variables. If one start from any vertices and move anti-clockwise then he will get for the first time negative y-line and x-line and hence y’ and x’ points. Minterm x’ y’ can also be found from any vertex of KH-polygon eliminathing appropriate variable(s). In similar way expression for KH-polygon abef is x’ z’ and for ghij xz.
Hence, f(w,x,y,z) = x’y’ + xz + x’z’.
Example 2. Fig 4 represents the expression f(u, w, x, y, z) = (1, 2, 3, 5, 7, 10, 11, 12, 13, 14, 15, 18, 19, 21,23,25, 26,27)
Arms ab, be, and cd of KH-polygon abedefgh have been bisected by u-line, z-line and w-line respectively and minterm is x’ y may come from vertex u’w'x’yx’ (vertex 2) or tracing end point of MSB line. Combining
expressions for all polygon the expression can be evaluated as f(u,v,x,y,z)= x’y (abedefgh) + u’w'z (alkr) + w’xz(ijkl) u’wx (mnop) + uwx’z (eq). Content within parentheses represents corresponding polygon.
This KH-map provides a regular geometric structure that is more intuitive than other methods having non-geometric pattern. Concatenation of two KH-map is possible by placing one inside the other. By software implementation it can be extended to solve for a huge
number of variables. X-OR realization through this method will also be convenient. The author hopes that this technique will replace Karnaugh map and Quine McCluskey procedure by its inherent simplicity.
Author acknowledges encouragements and co-operation of Dr. M. Shahjahan, Vice-Chancellor, Dr. M. A. Choudhury, Associate Professor and Dr. M. Kaykobad, Asst. Professor of Bangladesh Unversity of Engineering and Technology (BUET).
A.T.M. Shqfiqul Khalid (Tuhin)
is a final year undergraduate student of the Department of Computer Science and Engineering, Bangladesh University of Engineering & Technology, Dhaka.