return to main page## The IBM 1401, its internal use of "qui-binary"

from Carl Claunch

and unusual approach to addition/subtractionThe IBM 1401, its internal use of "qui-binary" and unusual approach to addition/subtraction

The use of what IBM insists on calling qui-binary for arithmetic in the 1401 is an interesting oddity that is partly driven by ease and cost of implementation and partly it is a persistence of historical choices and experiences which today are almost completely ignored or unknown. Because I wanted to understand why the designers took this approach, I undertook some detailed research. Nothing I could find directly answers the question of why the 1401 has a hidden conversion to qui-binary for arithmetic, but there was enough information to come to a very reasonable conclusion.

The 1401 was developed at a time when we were much closer to the mechanical and relay based calculator era that was supplanted by digital computers. Understanding the context of those times really illuminates these design decisions - as the most mature and complete theory, engineering art and industry practices of the times came from that era.

Most of the work on encoding numbers electrically came from the communications field and to a large degree the most advanced efforts of the time were the domain of the US telephone industry (e.g. Bell Laboratories) and the corresponding institutions globally (e.g. the Dollis Hill research institution of the UK). Mechanisms like Teletype and Telex were widely used. Calculator companies such as Burroughs and Marchant developed products to assist people doing calculations (the people having the title of computer, not the hardware that assisted them which were calculators or similar names).

Most of the calculators and communications devices handled numbers digit by digit, usually in decimal at least as far as the user interface. Internally, they were stored and manipulated in a variety of schemes, mostly not in decimal. However, they were not encoding the value of an entire number, they encoded the value of each decimal digit independently.

Reliability of the relay based calculators was a challenge, which didn't ease when machines shifted to vacuum tube electronics. Each relay or vacuum tube was relatively large, power hungry and costly, in addition to contributing another part which could fail, thus designers sought to minimize their numbers through clever engineering. Error checking was simplified if a set of wires would always have one and only one "on" or at logical 1 in a binary sense. Any other case, zero turned on or more than one turned on, indicated an error had occured.

You could imagine converting each digit to a set of ten wires, representing each of the ten values 0 through 9 of that digit, with error checking to ensure that only 1 of 10 was active. However, that might drive the use of ten relays for each digit. Other encoding schemes reduced the parts count but still had the property of checking for one and only one active wire.

Bell Labs used schemes for relay based systems such as this bi-quinary coding for digits which they also termed a 2 out of 5 code. There are five wires and relays used to represent any digit, the wires representing 0, 1, 2, 4 and 7. The reader can convince themselves that with these weightings, you can have exactly ten 5 bit long values that have only two of the bits at 1. 11000, 101000, 01100, 10010, 01010, 00110, 10001, 01001, 00101, and 00011 stand for 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10 although the last is actually a sum of 11 (4 + 7) which is taken to encode zero. Any single relay intermittent error would be detected because their would be more or less than two of the five bits turned on.

Later work at Bell Labs led to bi-quinary as an encoding where the wires were placed in two sections, each of which could have only one wire active. The error checking was easier (e.g. less hardware) than verifying two were active as in the prior paragraph. There was a tradeoff between error checking hardware and the digit storage hardware. This is much like an abacus, where one section has two wires - one means there the digit is five or higher, the other wire means the digit is less than five. The other section (lower section of an abacus) has five wires, representing 0, 1, 2, 3 or 4. Thus, a digit of 7 has the 'five' bit of the upper section plus the 'two' bit of the lower section. Here the analogy to an abacus breaks down because they can have up to four beads 'on' in the lower section.

Coding a decimal value with ten unique wires allows checking that only one wire is active, but bi-quinary requires only seven unique wires and can still use a circuit that verifies one-and-only-one active. Most of these implementations use the section with two wires (the 'binary' side) so that one wire is 'no five' and the other wire is 'five'. The five wire section is a quinary section where each wire is binary and only one of the five can be on at any time.

Arithmetic involves not only magnitudes but also positive and negative signs. To implement this with an adder, whether in relays or electronically, generally involves taking the complement of a number, and allows for both addition and subtraction with a single adding circuit. http://en.wikipedia.org/wiki/Method_of_complements Engineers have to design circuits to complement a number if needed to perform subtraction or to represent the value as a negative number.

A scheme invented at Bell Labs made the circuitry for complementing digits easier if each digit is in a four-bit binary encoding as its decimal value plus three. In other words, the digit values are 3, 4, 5, 6, 7, 8, 9, 10, 11 and 12 to encode 0 through 9. They called this 'excess three' coding. It allows the complement to take place with less hardware. Just invert all the bits and you have the nines-complement of the digit.

The Univac I employed the excess three method to represen decimal numbers. Unfortunately, the programmer and operator had to recognize that a 6 displayed on the panel was a decimal 3, not a six. This confusion was an infamous lesson of history that led most computers designers to hide internal details of encodings such as this from the operator and programmer, allowing them to see a 3 when the value was intended to be a 3.

IBMs early steps into computing included some relay based systems such as the Harvard Mark I http://en.wikipedia.org/wiki/Harvard_Mark_I and SSEC http://en.wikipedia.org/wiki/IBM_SSEC and then extensions of their electromechanical accounting machines. That led to all electronic machines such as the 650, 701 and others.

The IBM 650, an all electronic machine, implemented bi-quinary representation for decimal digits which were visible on the operator panel. This was the classic approach where the first two values indicate presence or absence of a five, the next five values are 0 through 4. Forming the nines-complement with this bi-quinary encoding meant flipping the binary section values and symmetrically flipping the quinary section - the four wire value becomes the zero wire value, the three wire value becomes the one wire value and the two wire value stays as it is. To illustrate, the decimal value 2 is encoded as 01 00010 in bi-quinary. Its nines-complement is 7, which is encoded as 10 01000 so that we flipped the binary value 01 to 10 and routed the value of the quinary bits to form 01000. Anything where the quinary section has the two value, e.g. where the quinary is 00100, does not change at all in complementing. 10000 becomes 00001, 01000 becomes 00010, 00010 becomes 01000 and 00001 becomes 10000. You can visualize this as the mirror image of the quinary pattern if that makes it easier to grasp.

Now on to the 1401, a magical blend of these historical experiences and technology antecedents. The 1401 is a character oriented machine, much like the calculators and then electromechanical accounting machines of its ancestry. The BCD encoding for each character represents decimal as a value comprised of the valid combinations of the four low order bits, 0 through 9, and makes use of the A and B zone bits for signing and other purposes. The adder, however, operates using 'qui-binary', IBM's term for an encoding which differs from what they used with the 650 machine and what everyone else in the industry calls such coding mechanisms.

Qui-binary has a two wire section, but that binary section encodes where the digit is odd or even. One wire means odd, the other means even, but they are labeled B0 and B1 in all the hardware documentation. They obey the exclusive OR property where they both cant be 0 and both cant be 1. The quinary section that has five wires uses these to represent 0, 2, 4, 6 and 8. One and only one of the quinary wires can be active at any time or we have a validity error. These are the Q# signals. One can only assume that, since the binary section is not the larger weight, as it is in the 650, but instead contributes the smallest weight of 1 or 0, they flipped the terminology to qui-binary.

The programmer and the operator using the control panel of the 1401 sees only BCD coded digits. The arithmetic logic shows the resulting sum as a BCD digit. While executing, the machine does a translation from BCD to qui-binary for both of the input digits that are being added or subtracted. As appropriate to the arithmetic operation and the signs of the two fields, it may translate to the nines-complement qui-binary for one of the fields. The machine has two separate adders - one adds the binary section and one adds the quinary section, dealing appropriately with carries, borrows and overflows across those two units and with the digits that will be added after this pair of digits has been completed. The resultant qui-binary value is complemented back if needed then translated to BCD before it is sent to storage or made visible on the operator panel.

Perhaps they hid the use of qui-binary from the operator and programmer because of the recent industry experiences with 'excess three' on the Univac I, or more likely it was to provide simplicity for the potential customers who were almost universally familiar with electromechanical accounting systems and had no prior experience with computers. This also hides the details of complementing numbers when they are negative. All numbers are represented by their absolute value in decimal, with a sign associated with the low order digit that indicates if the number is positive or negative.