Note
This is not a solution for modern applications. It is just presented for historic interest and to demonstrate the algebraic method of prime implicant production.
This was my final year BSc project at Bristol Polytechnic, now UWE Bristol (University of the West of England). My course was Electrical Engineering but they let me do a 100% software project because it related to electronics – minimising logic circuitry.
This is a variant of the Quine–McCluskey algorithm incorporating algebraic methods proposed by Nagle et al. for improved efficiency (ref. An Introduction to Computer Logic; H.T.Nagle, B.D.Carroll & J.D.Irwin; Prentice-Hall, 1975).
The program was coded in PL/I Subset G (General Purpose), initially developed by IBM. It ran on a 1979 PRIME 550 System minicomputer by Prime Computer, Inc. running the PRIMOS operating system and accessed from dumb terminals. The photo shows a similar system at Chilton Atlas Computer Laboratory.
I chose PL/I because it can perform bitwise logical operations on arbitrary length bit strings which even today is quite rare – few modern languages natively support packed bit arrays with bitwise and shift operators. And in its time PL/I was the language of choice for scientific, engineering and system programming – I hoped the novel approach would impress the examiners!
The 1986 source code derives from the original line printer listing via scanning, optical character recognition and extensive correction (OCR does not handle old dot-matrix print well). The test runs were also scanned from 14.5" x 11" yellowing fan-fold printouts.
Recently (2024) I managed to get the program running again using the excellent Iron Spring PL/I compiler introduced in 2007, on Ubuntu Linux under VirtualBox on a Mac Pro. I also tried the Digital Research PL/I Compiler under DOSBox but it lacked some builtins and failed to parse certain bit expressions.
After fixing minor compatibility issues it works like a charm. It is programmed to handle a function order of 96 but only tested for 8 (see test-9) which took 8½ minutes on the PRIME but just a second or two on the Mac.
The amended source code is bool_min.pli, and the src/ directory also contains everything needed to build it on Linux. The test/ directory replicates the original test runs.
I shall scan and upload the accompanying dissertation sometime but it is quite brief – mastering PL/I and coding the program occupied most of my time.