Japanese Computer Pioneers

Muroga SaburoMuroga Saburo
1925〜2009

Muroga Saburo was born on March 15, 1925 in Numazu, Japan. In 1947 Muroga graduated from the University of Tokyo with Gakushi-degree (this corresponds to a US Bachelor plus one additional year schooling) in electrical engineering. Muroga immediately joined the laboratory of the National Railway of the Japanese government. The laboratory was devoted to develop the bullet train technology and Muroga engaged in theoretical research of multiplex communication systems. At that time, researchers at Bell Labs had published a book titled "Visible Speech", on the analysis of speech by electrical signals. Stimulated by the book, Muroga and Seki Hideo applied for a patent for a speech typewriter and presented a paper on it at the general assembly of CCIR at Geneva. In 1950, Muroga joined a radio regulatory agency of the Japanese government, which was similar to the FCC in the U.S., and prepared technical data for making laws. In 1951, Muroga joined the Nippon Telegraph & Telephone Public Corp. (usually known as NTT), working in its research lab. Muroga initiated his research work in information theory. C. E. Shannon introduced "Channel Capacity", the core concept of Shannon's information theory but concluded it was difficult, if not impossible, to calculate this capacity. Muroga solved the problem, immediately garnering international fame.

In 1953, Muroga participated in a summer program at the Massachusetts Institute of Technology, supported by a Fulbright grant. From that fall, as a research assistant, Muroga began research on error-correcting codes. In 1954 Muroga spent a half year as a research assistant at the University of Illinois. At that time, there were only a half dozen large digital computers in the U.S., and only the ILLIAC was available for education. When he arrived back in Japan, Muroga was a computer celebrity -the first Japanese scientist who ever used a big computer, the ILLIAC. Muroga immediately started to promote the basic concepts of computer technology, by teaching at major communication equipment manufacturers and electronics manufacturers, writing many books and magazine articles and participating in many industrywide committees. Thus, Muroga had contributed to the buildup of the computer industry in Japan. Muroga also designed, constructed and operated a large parametron computer with Takashima Kensuke, where the Parametron is a new type of logic gate invented by Goto Eiichi and Takahashi Hidetoshi of the University of Tokyo in 1954.

The Parametron works on the principle of majority decision logic where the output of a logic gate is 1 or 0, according to which of 1's and 0's constitute the majority of the (1,0) inputs. Parametron, as the hardware realization of the majority decision logic at that time, did not have a promising future. Paying attention to the theoretical potential of the majority decision logic, Muroga devised a new type of logic design theory called "Threshold Logic" and published it in 1958. The threshold logic expresses majority decision logic operation in inequalities, a departure from traditional logic design theory, i.e., switching theory. As a result, in threshold logic, different types of gates, such as NAND and NOR gates, which cannot be easily handled by Boolean Algebra, are treated as unified by inequalities, in addition to traditional Boolean-algebraic gates, AND, OR and NOT gates. Traditional logic design theory is based on Boolean Algebra, but now we have an entirely new logic design theory based on inequalities with discovery of several unique properties of logic circuits. In 1960, Muroga left Japan, and joined IBM Research in Yorktown Heights, N.Y..

In 1964 Muroga embarked on a teaching career in the University of Illinois. Muroga published a book on threshold logic in 1971 by John Wiley, which has been popular among neuro network researchers. With Ibaraki Toshihide, Taguchi Tomoyasu and students, Muroga devised a way to minimize the number of logic gates, the number of levels in a logic circuit, or others, by extending a threshold logic to integer programming logic design. In the case of traditional logic design theory based on Boolean Algebra, a minimal sum or a minimal product is first derived and then it is converted into a transistor circuit. Thus, it is very difficult to minimize the number of logic gates, or the number of levels in a logic circuit. In contrast to this, threshold logic can be easily extended into integer programming because it is formulated in inequalities. This introduced for the first time the concept of an absolute minimization of the number of gates or interconnections in a logic circuit into logic design theory.

Extending this notion, with his students, Hung-Chi Lai and Sakurai Akito, parallel adders and logic circuits for the parity function were designed with a minimum number of NOR gates, regardless of how many input variables the adders or the parity circuits have. This solved a problem known to be difficult, because designers can try to design logic circuits for a small number of input variables, but there has been no way to confirm the minimality of their designs. The parallel adders are completely different from traditional carry-ripple adders, which is a cascade of full adders. These parallel adders have unique properties, such as the minimality of the number of interconnections among NOR gates.

The process of logic design based on integer programming is too time consuming, when a logic circuit is to be designed consisting of many logic gates. With a visiting scholar, Kambayashi Yahiko, and students, Muroga developed another logic design method that can design large circuits in a short time without necessarily minimizing the number of logic gates, observing the nature of many minimized logic circuits derived by the logic design based on integer programming. This method is called the "Transduction method". In the case of traditional logic design, designers end design efforts once logic circuits are obtained for the logic functions. In contrast to this, the transduction method is a simplification of any logic circuit designed by any design means. Thus the outcome cannot be worse than the original logic circuit. The simplification of a logic circuit is done by transformations of a logic circuit without changing any of its output functions and also a reduction of unnecessary interconnections based on a new concept called permissible functions. The transduction method has been adopted as the de facto industry standard for designing the best logic circuits by major CAD companies. The method has been taught at some universities.
In addition to many papers on his research, Muroga has contributed articles to Encyclopaedia Britannica and many other handbooks. Muroga plans to revise his VLSI system design book, which was published by John Wiley in 1982 and translated into Russian and other languages.

Muroga had taught at the University of Illinois for 38 years until 2002. Among his graduate students, many have highly successful careers in industry, such as vice presidents of Dell Computer, Sun Microsystems, Silicon Graphics and also C.E.O. of United Microelectronics. ÝHis name will live on in the Department of Computer Science in the form of two endowed positions named in his honor. Former Dell Computer executive Douglas MacGregor established the Faiman and Muroga Professorship, now held by Professor Marc Snir, and former Toshiba executive, Matsushita Shigenori, with others established the Muroga Fellowship.

Muroga died on December 9, 2009.


(As of Aug 22, 2003)