Simplification of Logic Expressions:Prime Implicates, Irredundant Conjunctive Forms, and Minimal Products.

By -
Prime Implicates, Irredundant Conjunctive Forms, and Minimal Products
 The “implicates,” “irredundant conjunctive forms,” and “minimal products,” which can be defined all based on the concept of conjunctive form, will be useful for deriving a minimal network that has OR gates in the first level and one AND gate in the second level.

First, let us represent the maxterm expansion of a given function f on a Karnaugh map. Unlike the map representation of the minterm expansion of f, where each minterm contained in the expansion is represented by a 1-cell on a Karnaugh map, each maxterm is represented by a 0-cell. Suppose that a function f is given as shown by the 1-cells in Figure 28.9(a). This function can be expressed in the maxterm expansion:

Simplification of Logic Expressions-0355

The first maxterm, (x1 ∨ x2 ∨ x3 ∨ x4), for example, is represented by the 0-cell that has components (x1, x2, x3, x4) = (1 0 0 0) in the Karnaugh map in Figure 28.9(a) (i.e., (x1 ∨ x2 ∨ x3 ∨ x4) becomes 0 for x1 = 1,x2 = x3 = x4 = 0). Notice that each literal in the maxterm is complemented or noncomplemented, corresponding to 1 or 0 in the corresponding component, respectively, instead of corresponding to 0 or 1 in the case of minterm. All other maxterms are similarly represented by 0-cells. It may look somewhat strange that these 0-cells represent the f expressed by 1-cell on the Karnaugh map in Figure 28.9(a). But the first maxterm, (x1 ∨ x2 ∨ x3 ∨ x4), for example, assumes the value 0 only for (x1, x2, x3, x4) = (1 0 0 0) and assumes the value 1 for all other combinations of the components. The situation is similar with other maxterms. Therefore, the conjunction of these maxterms becomes 0 only when any of the maxterms becomes 0. Thus, these 0-cells represent f through its maxterms. This is what we discussed earlier about the maxterm expansion or the Π-decimal specification of f, based on the false vectors of f.

Like the representation of a product on a Karnaugh map, any alterm can be represented by a rectangular loop of 2i 0-cells by repeatedly combining a pair of 0-cell loops that are horizontally or vertically adjacent in the same rows or columns, where i is a non-negative integer. For example, the two adjacent 0-calls in the same column representing maxterms (x1 ∨ x2 ∨ x 3 ∨ x4) and (x1 ∨ x2 ∨ x 3 ∨ x4) can be combined to form alterm x1 ∨ x2 ∨ x3, by deleting literals x4 and x4, as shown in a solid-line loop in Figure 28.9(b).

Simplification of Logic Expressions-0356

Simplification of Logic Expressions-0357Simplification of Logic Expressions-0358

All prime implicates of a function f can be algebraically obtained from a conjunctive form for f by modifying the Tison method discussed in Procedure 27.1; that is, by using dual operations in the method. We can define the following concepts, which are dual to irredundant disjunctive forms, minimal sums,

absolute minimal sums, essential prime implicants, complete sums, and others.

Definition 28.8: An irredundant conjunctive form for a function f is a conjunction of prime implicates such that removal of any of them makes the remainder not express f. The minimal products are irredundant conjunctive forms for f with a minimum number of prime implicates. The absolute minimal products are minimal products with a minimum number of literals. Prime implicates that appear in every irredundant conjunctive form for f are called essential prime implicates of f. Conditionally eliminable prime implicates are prime implicates that appear in some irredundant conjunctive forms for f, but not in others. Absolutely eliminable prime implicates are prime implicates that do not appear in any irredundant conjunctive form for f. The complete product for a function f is the product of all prime implicates of f.

Comments

Post a Comment

Popular posts from this blog

SRAM:Decoder and Word-Line Decoding Circuit [10–13].

By -
Image
Decoder and Word-Line Decoding Circuit [10–13] Two kinds of decoders are used in SRAM: the row decoder and the column decoder. Row decoders are needed to select one row of word-lines out of a set of rows in the array. A fast decoder can be implemented by using AND/NAND and OR/NOR gates. Figure 52.7 shows the schematic diagrams of static and dynamic AND gate decoders. The static NAND-type structure is chosen due to its low power consumption, that is, only the decoded row transitions. The dynamic structure is chosen due to its speed and power improvement over conventional static NAND gates. From a low-voltage operation standpoint, a dynamic NOR-base decoding would provide lower delay times through the decoder due to the limited amount of stacking of devices. Figure 52.8 shows circuit diagrams of dynamic NOR gates. The dynamic CMOS gate as shown in Figure 52.8(a) consists of input- NMOSs whose drain nodes are precharged to a high level by a PMOS when a clock signal Φ is at a low lev...
Read more

ASIC and Custom IC Cell Information Representation:GDS2

By -
Image
GDS2 The Graphical Design System (GDS) format is a binary format developed by Calma Company in 1971 to convey IC layout information between IC designers and fabricators. Calma presented GDS2 format, the improved version of GDS, in 1978. Finally in 1991, when Cadence acquired Calma, GDS2 rights were transferred to it. In the design process, after the completion of routing and placement, design rule check (DRC) and layout versus schematic (LVS) are performed to verify the final layout. Then the verified layout, dumped in a GDS2 file, is transferred to IC foundries for fabrication. GDS2 File Format GDS2 is a standard mask layout intermediate format containing a single cell or a library of cells each of which includes a number of geometrical objects such as boundaries, paths, boxes, etc. These objects correspond to different layers of a cell where each layer is specified by a layer number and data type [3]. The file format of GDS2 is in binary. A GDS2 file contains a number of variable...
Read more

Timing Description Languages:SDF

By -
Image
SDF Standard Delay Format (SDF) is an ASCII format used to convey timing information between EDA tools. SDF was first developed by Cadence in 1990. Open Verilog International (OVI) approved SDF version 2 in 1993 and SDF version 2.1 and 3 in the following years. Improving SDF version 3 features, resulted in IEEE Standard 1497 [1]. Role of SDF in Design Process SDF can be used in different levels of a design process to annotate timing specifications, including timing data and constraints. Timing constraints are used during the forward-annotation process while timing data are applied during the back-annotation process. Forward-annotation process deals with porting timing constraints to synthesis, floorplanner, layout, and routing tools to meet the required constraints. During the design process, timing data can be back-annotated to analysis tools (including simulators, static timing analysis tools, etc.) to provide more accurate timing representations. SDF Structure An SDF f...
Read more