Excess-3

From HandWiki
Short description: Variation to BCD-code where three (11) is added to a binary representation
Stibitz code
Digits4[1]
Tracks4[1]
Digit values8  4 −2 −1
Weight(s)1..3[1]
ContinuityNo[1]
CyclicNo[1]
Minimum distance1[1]
Maximum distance4
Redundancy0.7
Lexicography1[1]
Complement9[1]

Excess-3, 3-excess[1][2][3] or 10-excess-3 binary code (often abbreviated as XS-3,[4] 3XS[1] or X3[5][6]), shifted binary[7] or Stibitz code[1][2][8][9] (after George Stibitz,[10] who built a relay-based adding machine in 1937[11][12]) is a self-complementary binary-coded decimal (BCD) code and numeral system. It is a biased representation. Excess-3 code was used on some older computers as well as in cash registers and hand-held portable electronic calculators of the 1970s, among other uses.

Representation

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 non-weighted codes. In excess-3 code, 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, and Stibitz code
Decimal Excess-3 Stibitz BCD 8-4-2-1 Binary 3-of-6 CCITT
extension[13][1]
4-of-8 Hamming
extension[1]
−3 0000 pseudo-tetrade N/A N/A N/A N/A
−2 0001 pseudo-tetrade
−1 0010 pseudo-tetrade
0 0011 0011 0000 0000 10 0011
1 0100 0100 0001 0001 11 1011
2 0101 0101 0010 0010 10 0101
3 0110 0110 0011 0011 10 0110
4 0111 0111 0100 0100 00 1000
5 1000 1000 0101 0101 11 0111
6 1001 1001 0110 0110 10 1001
7 1010 1010 0111 0111 10 1010
8 1011 1011 1000 1000 00 0100
9 1100 1100 1001 1001 10 1100
10 1101 pseudo-tetrade pseudo-tetrade 1010 N/A N/A
11 1110 pseudo-tetrade pseudo-tetrade 1011
12 1111 pseudo-tetrade pseudo-tetrade 1100
13 N/A N/A pseudo-tetrade 1101
14 pseudo-tetrade 1110
15 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). 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.)[14]

Motivation

The primary advantage of excess-3 coding over non-biased coding is that a decimal number can be nines' complemented[1] (for subtraction) as easily as a binary number can be ones' complemented: just by inverting all bits.[1] Also, when the sum of two excess-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 (produce a carry-out).

Another advantage is that the codes 0000 and 1111 are not used for any digit. A fault in a memory or basic transmission line may result in these codes. It is also more difficult to write the zero pattern to magnetic media.[1][15][11]

Example

BCD 8-4-2-1 to excess-3 converter example in VHDL:

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

    an  : buffer std_logic;
    bn  : buffer std_logic;
    cn  : buffer std_logic;
    dn  : buffer std_logic;

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

architecture dataflow of bcd8421xs3 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 bcd8421xs3

Extensions

3-of-6 extension
Digits6[1]
Tracks6[1]
Weight(s)3[1]
ContinuityNo[1]
CyclicNo[1]
Minimum distance2[1]
Maximum distance6
Lexicography1[1]
Complement(9)[1]
4-of-8 extension
Digits8[1]
Tracks8[1]
Weight(s)4[1]
ContinuityNo[1]
CyclicNo[1]
Minimum distance4[1]
Maximum distance8
Lexicography1[1]
Complement9[1]
  • 3-of-6 code extension: The excess-3 code is sometimes also used for data transfer, then often expanded to a 6-bit code per CCITT GT 43 No. 1, where 3 out of 6 bits are set.[13][1]
  • 4-of-8 code extension: As an alternative to the IBM transceiver code[16] (which is a 4-of-8 code with a Hamming distance of 2),[1] it is also possible to define a 4-of-8 excess-3 code extension achieving a Hamming distance of 4, if only denary digits are to be transferred.[1]

See also

References

  1. 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 1.12 1.13 1.14 1.15 1.16 1.17 1.18 1.19 1.20 1.21 1.22 1.23 1.24 1.25 1.26 1.27 1.28 1.29 1.30 1.31 1.32 1.33 1.34 Steinbuch, Karl W., ed (1962). written at Karlsruhe, Germany (in de). Taschenbuch der Nachrichtenverarbeitung (1 ed.). Berlin / Göttingen / New York: Springer-Verlag OHG. pp. 71–73, 1081–1082. 
  2. 2.0 2.1 (in de) Taschenbuch der Informatik – Band II – Struktur und Programmierung von EDV-Systemen. 2 (3 ed.). Berlin, Germany: Springer Verlag. 1974. pp. 98–100. ISBN 3-540-06241-6. 
  3. Arithmetic Operations in Digital Computers. New York, USA: van Nostrand. 1955. p. 182. 
  4. "Optimized Data Encoding for Digital Computers". Convention Record of the I.R.E. 1954 National Convention, Part 4: Electronic Computers and Information Technology (Stanford Research Institute, Stanford, California, USA: The Institute of Radio Engineers, Inc.) 2: 47–57. June 1954. Session 19: Information Theory III - Speed and Computation. https://www.americanradiohistory.com/Archive-IRE/50s/IRE-1954-Part-4-Electronic-Computers-&-Information%20pdf. Retrieved 2020-05-22.  (11 pages)
  5. Decimal Computation (1 ed.). Binghamton, New York, USA: John Wiley & Sons, Inc.. 1974. p. 11. ISBN 0-471-76180-X. https://archive.org/details/decimalcomputati0000schm. Retrieved 2016-01-03. 
  6. Decimal Computation (1 (reprint) ed.). Malabar, Florida, USA: Robert E. Krieger Publishing Company. 1983. p. 11. ISBN 0-89874-318-4. https://books.google.com/books?id=uEYZAQAAIAAJ. Retrieved 2016-01-03.  (NB. At least some batches of this reprint edition were misprints with defective pages 115–146.)
  7. Mathematics and Computers (1 ed.). New York, USA / Toronto, Canada / London, UK: McGraw-Hill Book Company, Inc.. 1957. p. 105.  (10+228 pages)
  8. Digital Electronics. Philips Technical Library (PTL) / Macmillan Education (Reprint of 1st English ed.). Eindhoven, Netherlands: The Macmillan Press Ltd. / N. V. Philips' Gloeilampenfabrieken. 1973-06-18. pp. 42, 44. doi:10.1007/978-1-349-01417-0. ISBN 978-1-349-01419-4. https://books.google.com/books?id=hlRdDwAAQBAJ. Retrieved 2018-07-01.  (270 pages) (NB. This is based on a translation of volume I of the two-volume German edition.)
  9. (in de) Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Theoretische Grundlagen und Schaltungstechnik. Philips Fachbücher. I (improved and extended 5th ed.). Hamburg, Germany: Deutsche Philips GmbH. 1975. pp. 48, 51, 53, 58, 61, 73. ISBN 3-87145-272-6.  (xii+327+3 pages) (NB. The German edition of volume I was published in 1969, 1971, two editions in 1972, and 1975. Volume II was published in 1970, 1972, 1973, and 1975.)
  10. "Complex Computer". 1954-02-09. https://patents.google.com/patent/US2668661?oq=US2668661.  [1] (102 pages)
  11. 11.0 11.1 "Binäre Codices" (in de). Informations- und Kommunikationstechnik. Berlin, Germany. 2017. Exzeß-3-Code mit Additions- und Subtraktionsverfahren. http://elektroniktutor.de/digitaltechnik/codices.html. 
  12. The Computer Pioneers. New York, USA: Simon and Schuster. 1986. p. 35. ISBN 067152397X. https://archive.org/details/computerpioneers00ritc/page/35. 
  13. 13.0 13.1 Comité Consultatif International Téléphonique et Télégraphique (CCITT), Groupe de Travail 43 (1959-06-03). Contribution No. 1. CCITT, GT 43 No. 1. 
  14. Hayes, John P. (1978). Computer Architecture and Organization. McGraw-Hill International Book Company. p. 156. ISBN 0-07-027363-4. 
  15. "The Design of the IBM Type 702 System". Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics 74 (6): 695–704. January 1956. doi:10.1109/TCE.1956.6372444. Paper No. 55-719. 
  16. IBM (July 1957). 65 Data Transceiver / 66 Printing Data Receiver.