The Principle Of Duality States Computer Science Essay

The Principle Of Duality States Computer Science Essay To simplify a SOP for a Boolean expression using a K map, first identify all the input combinations that produce an output of logic level 1 and place them in their appropriate K map cell. Consequently, all other cells must contain zero (0). Second, group the adjacent cells that contain 1 in a manner that maximizes the size of the groups but also minimizes the total number of groups. All 1s in the output must be included in a group even if the group is only one cell. Third, as each SOP term represents an AND expression, each (AND) grouping is written with only the input variables that are common to the group. Finally, the simplified expression is formed by ORing each of the (AND) groups. To illustrate let us consider the function X =ABC+ABC+ABC whose truth table and K map are illustrated below: Truth table specifications for a logic function may not to include all possible combinations of the input binary digits for the input variables, yet they may still be complete specifications of the logic function for the prescribed application. In these situations certain input combinations will not occur due to the nature of the application. When the input combinations are irrelevant or cannot occur, the output states are in the Truth table and the K map are filled with an X and are referred to as dont care states. When simplifying K maps with dont care states, the contents of the undefined cells (1 or 0) are chosen according to preference. The aim is to enlarge group sizes thereby eliminating as many input variables from the simplified expression as possible. Only those Xs that assist in simplifying the function should be included in the groupings. No additional Xs should be added that would result in additional terms in the expression. THE TABULATION METHOD The K-map method is convenient as long as the number of variables does not exceed five or six, but when the number increases it becomes difficult to use this method. The tabulation method overcomes this difficulty, besides it is suitable for computer mechanisation. It was first formulated by Quine and later improved by McCluskey. It is also known as the Quine-McCluskey method. The tabular method of simplification consits of two parts: Determination of Prime Implicants. Selection of Essential Prime Implicants. The first part is covered in the software provided, the second part is not. Each minterm and its combined cells are included in the Minterm record, and linked lists techniques are used. Linked lists are the best way to manage unknown amount of data at run time instead of using a large array which is a waste of memory. The record used is: Pminterm = ^Minterm; Minterm = Record Number : Word; {This is to hold the decimal equivalent of the minterm} NumberOfOnes : Byte; {This is to hold the no. of 1s in the field Number} Selected : Boolean; {used as a tick when this term is selected} CellStr : String; { a string to hold all minterms that form a cell with this term } DashPlaceStr : String {a string to hold the place of the dash } Next : Pminterm { a pointer to the next record to form a linked list} End; The software procedure summarise as follows: The user enters the minterms in decimal equivalent. The program sorts minterms in the number of ones included in the binary equivalent (SortMinTerms). Any two minterms that differ from each other by only one variable are combined (done in FirstTabulation procedure), two minterms fit into this category if the number in the lower group is greater than that in the upper one, and the two numbers differ by a power of 2 e.g. ( 2d = 0010b and 10d = 1010b the difference is 8d which is a power of 2). Then the two numbers are copied to the second linked list ( First, Second, Vertex : Pminterm;). This procedure is carried for all the minterms. Matching groups are copied to second linked list while first one deleted. Then a second tabulation is carried in the SecondTabulation procedure, here each cell contained in the CellStr field of the Minterm record are compared together, a matching is found if the numbers in one cell are greater than the other one and they differs by a power of 2 e.g. (0,2 and 8,10 differs by 8 which is a power of two) . This procedure is carried for all the records in the second linked list and matching cells are copied to the first linked list, and any incomparable cells are copied to the Vertex linked list. Then the second linked list is deleted. The step 4 is repeated m 1 time where m is the number of inputs, transferring cells between first and second linked lists. The last linked list and the vertex linked list prime implicants are printed in the ABC equivalent using the WMterm procedure. My program architecture can be used to simplify any number of inputs, but practical limitations are in the Number field in the Minterm record which is a word i.e. 16 bits (16 inputs). Bearing in mind as well the simplified expression is contained in a string which is only 255 characters. Some inputs and corresponding outputs to try on the program: Boolean Expression Simplified Boolean Expression F(A,B,C) = S(0,6,7) ABC + AB F(A,B,C) = S(0,4,6,7) BC + AB + AC F(A,B,C,D,E,F) = S(4,5,6,7,36,37,38,39) BCD F(A,B,C,D,E,F,G,H) = S(16,17 up to 31,144,145 up to 159) BCD VARIABLE ENTERED METHOD (VEM) The conventional logic minimization is time consuming easy only for 4-5 variables. It becomes difficult to solve using conventional K-map method when number of variables goes on increasing. In that case Variable Entered Method will be good idea to use. It represents values of functions in terms of its variables called map entered variables. A new method for obtaining a compact subsumptive general solution of a system of Boolean equations is presented. The method relies on the use of the variable-entered Karnaugh map (VEKM) to achieve successive elimination through successive map folding. It is superior in efficiency and simplicity to methods employing Marquand diagrams or Conventional Karnaugh maps; it requires the construction of significantly smaller maps and produces such maps in a minimization-ready form. Moreover, the method is applicable to general Boolean equations and is not restricted to the two-valued case. Combinational Sequential Circuits Combinational logic circuits implement Boolean functions. Boolean functions are mappings of input bitstrings to output bitstrings. These circuits are functions of input only. What does that mean? It means that if you feed in an input to a circuit, say, 000, then look at its output, and discover it is, say, 10, then the output will always be 10 for that circuit, if 000 is the input. 000 is mapped to 10. If that value were not the same every single time, then the output must not completely depend on 000. Something else must be affecting the output. Combinational logic circuits always depend on input. Another way to define something that is a function of input is to imagine that you are only allowed to use input variables xk-1,,x0, i.e. data inputs, cm-1,,c0, i.e., control inputs, to write the function. This function can not depend on global variables or other variables. Like combinational logic circuits, a sequential logic circuit has inputs (labelled with x with subscripts) and outputs (labelled with z with subscripts). Unike combinational logic circuits, a sequential logic circuit uses a clock. Also, there is a box inside the circuit called State. This box contains flip flops. Assume it has k flip flops. The flip flops basically store a k-bit number representing the current state. The output z is computed based on the inputs (x with subscripts) and the state coming out of the state box (q with subscripts). The state may be updated at each positive clock edge. When theres not a positive clock edge, the state remains unchanged. The information needed to update to the state (called the next state) comes from the current state (the current value of q) and the input, which is fed through combinational logic, and fed back into the state box, telling the state box how to update itself. A sequential circuit uses flip flops. Unlike combinational logic, sequential circuits have state, which means basically, sequential circuits have memory. The main difference between sequential circuits and combinational circuits is that sequential circuits compute their output based on input and state, and that the state is updated based on a clock. Combinational logic circuits implement Boolean functions, so they are functions only of their inputs, and are not based on clocks. The S-R Latch A bistable multivibrator has two stable states, as indicated by the prefix bi in its name. Typically, one state is referred to as set and the other as reset. The simplest bistable device, therefore, is known as a set-reset, or S-R, latch. To create an S-R latch, we can wire two NOR gates in such a way that the output of one feeds back to the input of another, and vice versa, like this: http://sub.allaboutcircuits.com/images/04173.png The Q and not-Q outputs are supposed to be in opposite states. I say supposed to because making both the S and R inputs equal to 1 results in both Q and not-Q being 0. For this reason, having both S and R equal to 1 is called an invalid or illegal state for the S-R multivibrator. Otherwise, making S=1 and R=0 sets the multivibrator so that Q=1 and not-Q=0. Conversely, making R=1 and S=0 resets the multivibrator in the opposite state. When S and R are both equal to 0, the multivibrators outputs latch in their prior states. The Clocked D-Latch Since the enable input on a gated S-R latch provides a way to latch the Q and not-Q outputs without regard to the status of S or R, we can eliminate one of those inputs to create a multivibrator latch circuit with no illegal input states. Such a circuit is called a D latch, and its internal logic looks like this: http://sub.allaboutcircuits.com/images/04181.png Note that the R input has been replaced with the complement (inversion) of the old S input, and the S input has been renamed to D. As with the gated S-R latch, the D latch will not respond to a signal input if the enable input is 0 it simply stays latched in its last state. When the enable input is 1, however, the Q output follows the D input. Since the R input of the S-R circuitry has been done away with, this latch has no invalid or illegal state. Q and not-Q are always opposite of one another. Master-Slave Flip-Flops A master-slave flip-flop is constructed from two seperate flip-flops. One circuit serves as a master and the other as a slave. The logic diagram of an SR flip-flop is shown in figure below. The master flip-flop is enabled on the positive edge of the clock pulse CP and the slave flip-flop is disabled by the inverter. The information at the external R and S inputs is transmitted to the master flip-flop. When the pulse returns to 0, the master flip-flop is disabled and the slave flip-flop is enabled. The slave flip-flop then goes to the same state as the master flip-flop. http://wearcam.org/ece385/lectureflipflops/flipflops/fig9.gif Logic diagram of a master-slave flip-flop The timing relationship is shown in Figure below and is assumed that the flip-flop is in the clear state prior to the occurrence of the clock pulse. The output state of the master-slave flip-flop occurs on the negative transition of the clock pulse. Some master-slave flip-flops change output state on the positive transition of the clock pulse by having an additional inverter between the CP terminal and the input of the master. http://wearcam.org/ece385/lectureflipflops/flipflops/fig10.gif Timing relationship in a master slave flip-flop Edge Triggered Devices Another type of flip-flop that synchronizes the state changes during a clock pulse transition is the edge-triggered flip-flop. When the clock pulse input exceeds a specific threshold level, the inputs are locked out and the flip-flop is not affected by further changes in the inputs until the clock pulse returns to 0 and another pulse occurs. Some edge-triggered flip-flops cause a transition on the positive edge of the clock pulse (positive-edge-triggered), and others on the negative edge of the pulse (negative-edge-triggered). The logic diagram of a D-type positive-edge-triggered flip-flop is shown in figure below: http://wearcam.org/ece385/lectureflipflops/flipflops/fig11.gif D-type positive-edge triggered flip-flop When using different types of flip-flops in the same circuit, one must ensure that all flip-flop outputs make their transitions at the same time, ie., during either the negative edge or the positive edge of the clock pulse.