Excess-3
| Stibitz code | |
|---|---|
| Digits | 4[1] |
| Tracks | 4[1] |
| Digit values | 8 4 −2 −1 |
| Weight(s) | 1..3[1] |
| Continuity | No[1] |
| Cyclic | No[1] |
| Minimum distance | 1[1] |
| Maximum distance | 4 |
| Redundancy | 0.7 |
| Lexicography | 1[1] |
| Complement | 9[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).
| 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 | |
|---|---|
| Digits | 6[1] |
| Tracks | 6[1] |
| Weight(s) | 3[1] |
| Continuity | No[1] |
| Cyclic | No[1] |
| Minimum distance | 2[1] |
| Maximum distance | 6 |
| Lexicography | 1[1] |
| Complement | (9)[1] |
| 4-of-8 extension | |
|---|---|
| Digits | 8[1] |
| Tracks | 8[1] |
| Weight(s) | 4[1] |
| Continuity | No[1] |
| Cyclic | No[1] |
| Minimum distance | 4[1] |
| Maximum distance | 8 |
| Lexicography | 1[1] |
| Complement | 9[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
- Offset binary, excess-N, biased representation
- Excess-128
- Excess-Gray code
- Shifted Gray code
- Gray code
- m-of-n code
- Aiken code
References
- ↑ 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.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.
- ↑ Arithmetic Operations in Digital Computers. New York, USA: van Nostrand. 1955. p. 182.
- ↑ "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)
- ↑ 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.
- ↑ 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.)
- ↑ Mathematics and Computers (1 ed.). New York, USA / Toronto, Canada / London, UK: McGraw-Hill Book Company, Inc.. 1957. p. 105. (10+228 pages)
- ↑ 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.)
- ↑ (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.)
- ↑ "Complex Computer". 1954-02-09. https://patents.google.com/patent/US2668661?oq=US2668661. [1] (102 pages)
- ↑ 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.
- ↑ The Computer Pioneers. New York, USA: Simon and Schuster. 1986. p. 35. ISBN 067152397X. https://archive.org/details/computerpioneers00ritc/page/35.
- ↑ 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.
- ↑ Hayes, John P. (1978). Computer Architecture and Organization. McGraw-Hill International Book Company. p. 156. ISBN 0-07-027363-4.
- ↑ "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.
- ↑ IBM (July 1957). 65 Data Transceiver / 66 Printing Data Receiver.
 |  |
