kennethw@tekecs.UUCP (01/10/84)
The following program is the fourth of 4 programs I received to do logic reduction by the Quine-McCluskey method. I have received several requests for copies of anything I got, so I'm posting them here. (Message inbox:50) From: tektronix!decvax!allegra!psuvax!burdvax!coltoff Cc: coltoff Received: from decvax.uucp by tektronix ; 4 Jan 84 18:08:43 PST Received: by decvax.UUCP (4.12/4.13), id AA03350; Wed, 4 Jan 84 20:44:03 est Date: Wed, 4 Jan 84 20:44:03 est Message-Id: <8401050144.AA03350@decvax.UUCP> Subject: logic reduction Awhile back I asked for the same thing. Below is part of what I got. You should aske this guy if he will send you the code. If he doesn't let me know. Path from burdvax is - presby!seismo!rochester!ritcv!tropix!djl If I ever get my program done maybe we can exchange our programs. Don't be too hopeful though. Somehow real work always gets in the way of the things I really want to do. good luck, - Joel ************************************************************************ This is the documentation to the 'reduce' and 'reminte' logic reduction programs. The programs are designed to take raw logic definitions as input and provide the reduced form as output. 'reminte'... This program accepts minterms as input. These non-reduced minterms, when used in the sum of products form, may be used to define the given logic function. The minterms should be entered as positive integers with negative integers defining don't care conditions. A maximum of 1000 minterms may be entered. The following is an example of a function with four inputs and is stored under mintest. Redirect the input of reminte to mintest to run this function. given: f(a,b,c,d) = sum m(2, 3, 7, 9, 13) + sum x(-1, -10, -15) where sum m(...) are the sum of the "care" minterms sum x(...) are the sum of the don't care minterms The input FILE consists of the numbers with a space to seperate them. A line may be continued by simply typing a return. The output will consist of a list of prime implicants along with a chart signifing the minimal expression. The letter labels should not be confused with the function parameters given above. For this example, the prime implicant table is in the form of: A a,b,c,d ( associated minterms ) The small a,b,c,d refer to the function parameters. The possible parameters values are: - don't care (not included in final SOP) 0 x' or inverted x parameter 1 x or non-inverted x parameter The final minimal output expression is a table which consists of: O essensial implicant, include minterm number above it in the final SOP function + a minterm that was eliminated by an essensial implicant, don't include this in SOP expression - a minterm that was eliminated by another prime implicant, don't include this in SOP expression X user choice, pick to eliminate remaining X's and to suit your needs 'reduce'... This program accepts input of minterms in binary form followed by the desired output(s) also in binary form. The program has input parameters as follows... reduce [-outnum] [-d] [file] [-outnum] indicates the output to be used for the current level of logic reduction. "1" specifies the first output. [-d] if the -d option is used, debug information will be printed. [file] file from which input is to be taken. A typical file is shown in v67mem. The first line is explained as follows... 000000------- ------ The first group of symbols represent the 13 input parameters while the second set represents the 6 outputs. "-" are don't care conditions. To run reduce on v67mem output number 2, type: reduce -2 v67mem. The output produced is in the same general form as above. The only addition is a list of decimal representations of the original minterms. The method used to determine the minimal SOP expression is the same as before. Once a minimal expression is obtained for all the outputs, the functions may be futher reduced between all the outputs. This must be done by hand. The X's are usefull here because they provide more choices for reduction. Example of reduce program: Input file v67mem 000000------- ------ 000001------- 011000 0000100------ 000010 0000101------ 000001 000011------- ------ 000100-----0- 000100 000100-----1- 000010 000101------- ------ 000110------- ------ 000111------- ------ 0010001------ 001000 0010000------ 000100 001001------- ------ 001010------- ------ 001011------- ------ 001100------- ------ 001101------- ------ 001110------- ------ 001111------- ------ 010000------- ------ 010001------- ------ 010010------- ------ 010011------- ------ 010100--01--- 101000 010100--11--- 110000 010100--10--- 111000 010100--00--- ------ 010101------- ------ 010110------- ------ 010111------- ------ 011000-0--0-- 011000 011000-1----0 001000 011000-1----1 011000 01100000--1-- 010100 01100010----- 011000 011001------- ------ 011010------- ------ 011011------- ------ 011100------- ------ 011101------- ------ 011110------- ------ 011111------- ------ 100000------- ------ 100001------- ------ 100010------- ------ 100011------- ------ 100100-00-0-- 100100 100100-00-1-- 101000 100100-01---- 011000 100100-1----- 001000 100101------- ------ 100110------- ------ 100111------- ------ 101000----0-- 100100 101000----1-- 101000 101001------- ------ 101010------- ------ 101011------- ------ 101100------- ------ 101101------- ------ 101110------- ------ 101111------- ------ 110000----1-- 110000 110000----0-- 011000 110001------- ------ 110010------- ------ 110011------- ------ 110100-0-1--- 011000 110100-0-00-- 110100 110100-0-01-- 111000 110100-1----- 001000 110101------- ------ 110110------- ------ 110111------- ------ 111000----0-- 110100 111000----1-- 111000 111001------- ------ 111010------- ------ 111011------- ------ 111100------- ------ 111101------- ------ 111110------- ------ 111111------- ------ This is the output from reduce using the datafile v67mem. =========================================================== Input data: 000000------- ( 0) 000011------- ( 384) 000101------- ( 640) 000110------- ( 768) 000111------- ( 896) 001001------- ( 1152) 001010------- ( 1280) 001011------- ( 1408) 001100------- ( 1536) 001101------- ( 1664) 001110------- ( 1792) 001111------- ( 1920) 010000------- ( 2048) 010001------- ( 2176) 010010------- ( 2304) 010011------- ( 2432) 010100--01--- ( 2568) 010100--11--- ( 2584) 010100--10--- ( 2576) 010100--00--- ( 2560) 010101------- ( 2688) 010110------- ( 2816) 010111------- ( 2944) 011001------- ( 3200) 011010------- ( 3328) 011011------- ( 3456) 011100------- ( 3584) 011101------- ( 3712) 011110------- ( 3840) 011111------- ( 3968) 100000------- ( 4096) 100001------- ( 4224) 100010------- ( 4352) 100011------- ( 4480) 100100-00-0-- ( 4608) 100100-00-1-- ( 4612) 100101------- ( 4736) 100110------- ( 4864) 100111------- ( 4992) 101000----0-- ( 5120) 101000----1-- ( 5124) 101001------- ( 5248) 101010------- ( 5376) 101011------- ( 5504) 101100------- ( 5632) 101101------- ( 5760) 101110------- ( 5888) 101111------- ( 6016) 110000----1-- ( 6148) 110001------- ( 6272) 110010------- ( 6400) 110011------- ( 6528) 110100-0-00-- ( 6656) 110100-0-01-- ( 6660) 110101------- ( 6784) 110110------- ( 6912) 110111------- ( 7040) 111000----0-- ( 7168) 111000----1-- ( 7172) 111001------- ( 7296) 111010------- ( 7424) 111011------- ( 7552) 111100------- ( 7680) 111101------- ( 7808) 111110------- ( 7936) 111111------- ( 8064) Prime implicants: A ----11------- ( 384, 4480, 2432, 6528, 896, 2944, 4992, 7040, 1408, 3456, 1920, 3968, 5504, 7552, 6016, 8064) B ---1-1------- ( 640, 1664, 2688, 3712, 896, 2944, 1920, 3968, 4736, 6784, 5760, 7808, 4992, 7040, 6016, 8064) C ---11-------- ( 768, 4864, 1792, 5888, 2816, 6912, 3840, 7936, 896, 2944, 1920, 3968, 4992, 7040, 6016, 8064) D --1--1------- ( 1152, 1664, 5248, 5760, 1408, 5504, 1920, 6016, 3200, 7296, 3712, 7808, 3456, 3968, 7552, 8064) E --1-1-------- ( 1280, 1792, 3328, 3840, 1408, 3456, 1920, 3968, 5376, 5504, 5888, 6016, 7424, 7936, 7552, 8064) F --11--------- ( 1536, 1792, 5632, 5888, 1664, 1920, 5760, 6016, 3584, 7680, 3840, 7936, 3712, 7808, 3968, 8064) G -1---1------- ( 2176, 2688, 3200, 3712, 2432, 3456, 2944, 3968, 6272, 6528, 6784, 7040, 7296, 7552, 7808, 8064) H -1--1-------- ( 2304, 3328, 2432, 3456, 2816, 3840, 2944, 3968, 6400, 7424, 6912, 7936, 6528, 7552, 7040, 8064) I 1----1------- ( 4224, 5248, 4480, 5504, 4736, 4992, 5760, 6016, 6272, 6528, 6784, 7040, 7296, 7552, 7808, 8064) J 1---1-------- ( 4352, 4480, 4864, 4992, 6400, 6528, 6912, 7040, 5376, 5504, 5888, 6016, 7424, 7936, 7552, 8064) K 1-1---------- ( 5120, 5124, 5376, 5248, 5504, 5632, 5888, 5760, 6016, 7168, 7172, 7680, 7424, 7936, 7296, 7552, 7808, 8064) L 010---------- ( 2048, 2304, 2176, 2432, 2560, 2576, 2568, 2584, 2688, 2816, 2944) M 10-0--------- ( 4096, 4224, 5120, 5124, 5248, 4352, 5376, 4480, 5504) N 01-1--------- ( 2560, 2576, 2568, 2584, 3584, 2816, 3840, 2688, 3712, 2944, 3968) O -00000------- ( 0, 4096) P 0-0000------- ( 0, 2048) Q 11-000----1-- ( 6148, 7172) R 100100-00---- ( 4608, 4612) S 110100-0-0--- ( 6656, 6660) A B C D E F G H I J K L M N O P Q R S 2568 X X 2584 X X 2576 X X 4608 O 4612 O 5120 + - 5124 + - 6148 O 6656 O 6660 O 7168 O 7172 - +