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 complementary BCD code and numeral system. It also constitutes 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. It is a way to represent values with a balanced number of positive and negative numbers using a pre-specified number N as a biasing value. It is a nonweighted code. 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. (i.e. 0 − Excess Value)
  • The greatest binary number represents the largest value. (i.e. 2 N+1 − Excess Value − 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, then, one simply encodes each of the decimal digits as above, giving (0100, 0101, 1010).

Adding Excess-3 works on a different algorithm than non-biased decimal coding or regular binary positional system numbers. When you add two XS-3 numbers together, the result is not an XS-3 number. For instance, when you add 1 and 0 in XS-3 the answer seems to be 4 instead of 1. In order to correct this problem, when you are finished adding each digit, you have to remove the extra bias by subtracting binary 0011 (decimal 3 in unbiased binary) if the resulting digit is less than decimal 10 and subtracting binary 1101 (decimal 13 in unbiased binary), if an overflow has occurred. Note that, 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. In addition, when the sum of two XS-3 digits is greater than 9, the carry bit of a four bit adder will be set high. This works because, when adding two numbers that are greater than or equal to zero, an "excess" value of six results in the sum. Since a four bit integer can only hold values 0 to 15, an excess of six means that any sum over nine will overflow.

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.)