Excess-3

From Wikipedia, the free encyclopedia
Jump to: navigation, search
"XS-3" redirects here. For the experimental aircraft, see Douglas XS-3 Stiletto.

Excess-3 or 3-excess[1] binary code (often abbreviated as XS-3 or X3[2][3]) or Stibitz code[1] (after George Stibitz) is a self complementary binary-coded decimal code and numeral system. It is a biased representation. Excess-3 was used on some older computers as well as in cash registers and hand-held portable electronic calculators of the 1970s, among other uses.

Biased codes are a way to represent values with a balanced number of positive and negative numbers using a pre-specified number N as a biasing value. Biased codes (and Gray codes) are nonweighted codes. In XS-3, numbers are represented as decimal digits, and each digit is represented by four bits as the digit value plus 3 (the "excess" amount):

  • The smallest binary number represents the smallest value (0 − excess).
  • The greatest binary number represents the largest value (2N+1 − excess − 1).
Excess-3 / Stibitz code
Decimal Excess-3 Stibitz BCD 8-4-2-1 Binary
−3 0000 pseudo-tetrade N/A N/A
−2 0001 pseudo-tetrade N/A N/A
−1 0010 pseudo-tetrade N/A N/A
0 0011 0011 0000 0000
1 0100 0100 0001 0001
2 0101 0101 0010 0010
3 0110 0110 0011 0011
4 0111 0111 0100 0100
5 1000 1000 0101 0101
6 1001 1001 0110 0110
7 1010 1010 0111 0111
8 1011 1011 1000 1000
9 1100 1100 1001 1001
10 1101 pseudo-tetrade pseudo-tetrade 1010
11 1110 pseudo-tetrade pseudo-tetrade 1011
12 1111 pseudo-tetrade pseudo-tetrade 1100
13 N/A N/A pseudo-tetrade 1101
14 N/A N/A pseudo-tetrade 1110
15 N/A N/A pseudo-tetrade 1111

To encode a number such as 127, one simply encodes each of the decimal digits as above, giving (0100, 0101, 1010).

Excess-3 arithmetic uses different algorithms than normal non-biased BCD or binary positional system numbers. After adding two excess-3 digits, the raw sum is excess-6. For instance, after adding 1 (0100 in excess-3) and 2 (0101 in excess-3), the sum looks like 6 (1001 in excess-3) instead of 3 (0110 in excess-3). In order to correct this problem, after adding two digits, it is necessary to remove the extra bias by subtracting binary 0011 (decimal 3 in unbiased binary) if the resulting digit is less than decimal 10, or subtracting binary 1101 (decimal 13 in unbiased binary) if an overflow (carry) has occurred. (In 4-bit binary, subtracting binary 1101 is equivalent to adding 0011 and vice versa.)

Motivation[edit]

The primary advantage of XS-3 coding over non-biased coding is that a decimal number can be nines' complemented (for subtraction) as easily as a binary number can be ones' complemented; just invert all bits. Also, when the sum of two XS-3 digits is greater than 9, the carry bit of a 4-bit adder will be set high. This works because, after adding two digits, an "excess" value of 6 results in the sum. Because a 4-bit integer can only hold values 0 to 15, an excess of 6 means that any sum over 9 will overflow (carry).

Example[edit]

BCD to excess-3 converter example (VHDL code):

entity bcdxs3 is
  port (
    a   : in    std_logic;
    b   : in    std_logic;
    c   : in    std_logic;
    d   : in    std_logic;

    an  : inout std_logic;
    bn  : inout std_logic;
    cn  : inout std_logic;
    dn  : inout std_logic;

    w   : out   std_logic;
    x   : out   std_logic;
    y   : out   std_logic;
    z   : out   std_logic
  );
end entity bcdxs3;

architecture dataflow of bcdxs3 is
begin
    an  <=  not a;
    bn  <=  not b;
    cn  <=  not c;
    dn  <=  not d;

    w   <=  (an and b  and d ) or (a  and bn and cn)
         or (an and b  and c  and dn);
    x   <=  (an and bn and d ) or (an and bn and c  and dn)
         or (an and b  and cn and dn) or (a  and bn and cn and d);
    y   <=  (an and cn and dn) or (an and c  and d )
         or (a  and bn and cn and dn);
    z   <=  (an and dn) or (a  and bn and cn and dn);

end architecture dataflow; -- of bcdxs3

See also[edit]

References[edit]

  1. ^ a b Steinbuch, Karl W.; Weber, Wolfgang (1974) [1967]. Taschenbuch der Informatik - Band II - Struktur und Programmierung von EDV-Systemen. Taschenbuch der Nachrichtenverarbeitung (in German) 2 (3 ed.) (Springer Verlag Berlin). pp. 98–100. ISBN 3-540-06241-6. 
  2. ^ Schmid, Hermann (1974). Decimal Computation (1 ed.). Binghamton, New York, USA: John Wiley & Sons, Inc. p. 11. ISBN 0-471-76180-X. Retrieved 2016-01-03. 
  3. ^ Schmid, Hermann (1983) [1974]. Decimal Computation (1 (reprint) ed.). Malabar, Florida, USA: Robert E. Krieger Publishing Company. p. 11. ISBN 0-89874-318-4. Retrieved 2016-01-03.  (NB. At least some batches of this reprint edition were misprints with defective pages 115–146.)