Excess-3

Excess-3, 3-excess or 10-excess-3 binary code (often abbreviated as XS-3, 3XS or X3), shifted binary or Stibitz code (after George Stibitz, who built a relay-based adding machine in 1937) 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 ().
* The greatest binary number represents the largest value ().

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

The primary advantage of excess-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 by inverting all bits. 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.

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 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.
* 4-of-8 code extension: As an alternative to the IBM transceiver code (which is a 4-of-8 code with a Hamming distance of 2), 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.

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

{{Reflist, refs=
{{cite book , title=Taschenbuch der Nachrichtenverarbeitung , language=de , editor-first=Karl W. , editor-last=Steinbuch , editor-link=Karl W. Steinbuch , date=1962 , edition=1 , publisher=Springer-Verlag OHG , location=Karlsruhe, Germany , publication-place=Berlin / Göttingen / New York , lccn=62-14511 , pages=71–73, 1081–1082
{{cite book , title=Taschenbuch der Informatik – Band II – Struktur und Programmierung von EDV-Systemen , language=de , editor-first1=Karl W. , editor-last1=Steinbuch , editor-link1=Karl W. Steinbuch , editor-first2=Wolfgang , editor-last2=Weber , editor-first3=Traute , editor-last3=Heinemann , date=1974 , orig-year=1967 , edition=3 , volume=2 , work=Taschenbuch der Nachrichtenverarbeitung , publisher=Springer Verlag , location=Berlin, Germany , isbn=3-540-06241-6 , lccn=73-80607 , pages=98–100
{{cite book , title=Decimal Computation , author-first=Hermann , author-last=Schmid , author-link=Hermann Schmid (computer scientist) , date=1974 , edition=1 , publisher= John Wiley & Sons, Inc. , location=Binghamton, New York, USA , isbn=0-471-76180-X , pag
11
, url=https://archive.org/details/decimalcomputati0000schm , url-access=registration , access-date=2016-01-03
{{cite book , title=Decimal Computation , author-first=Hermann , author-last=Schmid , author-link=Hermann Schmid (computer scientist) , orig-year=1974 , date=1983 , edition=1 (reprint) , publisher=Robert E. Krieger Publishing Company , location=Malabar, Florida, USA , isbn=0-89874-318-4 , page=11 , url=https://books.google.com/books?id=uEYZAQAAIAAJ , access-date=2016-01-03 (NB. At least some batches of this reprint edition were misprints with defective pages 115–146.)
{{cite book , author-first=Richard Kohler , author-last=Richards , title=Arithmetic Operations in Digital Computers , publisher= van Nostrand , location=New York, USA , date=1955 , page=182
{{cite book , author=Comité Consultatif International Téléphonique et Télégraphique (CCITT), Groupe de Travail 43 , title=Contribution No. 1 , date=1959-06-03 , id=CCITT, GT 43 No. 1
{{cite journal , author-first1=Charles J. , author-last1=Bashe , author-first2=Peter Ward , author-last2=Jackson , author-first3=Howard A. , author-last3=Mussell , author-first4=Wayne David , author-last4=Winger , title=The Design of the IBM Type 702 System , journal= Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics , volume=74 , issue=6 , date=January 1956 , pages=695–704 , doi=10.1109/TCE.1956.6372444 , s2cid=51666209 , id=Paper No. 55-719
{{cite book , author=IBM , title=65 Data Transceiver / 66 Printing Data Receiver , date=July 1957 , author-link=IBM
{{cite web , title=Binäre Codices , at=Exzeß-3-Code mit Additions- und Subtraktionsverfahren , work=Informations- und Kommunikationstechnik , language=de , author-first=Detlef , author-last=Mietke , location=Berlin, Germany , date=2017 , orig-year=2015 , url=http://elektroniktutor.de/digitaltechnik/codices.html , access-date=2017-04-25 , url-status=live , archive-url=https://web.archive.org/web/20170425181921/http://elektroniktutor.de/digitaltechnik/codices.html , archive-date=2017-04-25
{{cite book , author-last=Ritchie , author-first=David , date=1986 , title=The Computer Pioneers , pag
35
, location=New York, USA , publisher=Simon and Schuster , isbn=067152397X , url=https://archive.org/details/computerpioneers00ritc/page/35
{{cite book , title=Digital Electronics , author-first1=Folkert , author-last1=Dokter , author-first2=Jürgen , author-last2=Steinhauer , date=1973-06-18 , series=Philips Technical Library (PTL) / Macmillan Education , publisher=The Macmillan Press Ltd. / N. V. Philips' Gloeilampenfabrieken , edition=Reprint of 1st English , location=Eindhoven, Netherlands , sbn=333-13360-9 , isbn=978-1-349-01419-4 , doi=10.1007/978-1-349-01417-0 , pages=42, 44 , url=https://books.google.com/books?id=hlRdDwAAQBAJ , access-date=2018-07-01 , url-status=live (270 pages) (NB. This is based on a translation of volume I of the two-volume German edition.)
{{cite book , author-first1=Folkert , author-last1=Dokter , author-first2=Jürgen , author-last2=Steinhauer , title=Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Theoretische Grundlagen und Schaltungstechnik , language=de , series=Philips Fachbücher , publisher=Deutsche Philips GmbH , location=Hamburg, Germany , volume=I , date=1975 , orig-year=1969 , edition=improved and extended 5th , isbn=3-87145-272-6 , pages=48, 51, 53, 58, 61, 73 (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.)
{{cite journal , author-first=William H. , author-last=Kautz , author-link=William H. Kautz , title=Optimized Data Encoding for Digital Computers , date=June 1954 , journal=Convention Record of the I.R.E. 1954 National Convention, Part 4: Electronic Computers and Information Technology , publisher=The Institute of Radio Engineers, Inc. , id=Session 19: Information Theory III - Speed and Computation , volume=2 , location=Stanford Research Institute, Stanford, California, USA , pages=47–57 , url=https://www.americanradiohistory.com/Archive-IRE/50s/IRE-1954-Part-4-Electronic-Computers-&-Information%20pdf , access-date=2020-05-22 , url-status=live (11 pages)
{{cite web , title=Complex Computer , author-first=George Robert , author-last=Stibitz , author-link=George Robert Stibitz , id=Patent US2668661A , orig-year=1941-04-19 , date=1954-02-09 , url=https://patents.google.com/patent/US2668661?oq=US2668661 , access-date=2020-05-24 , url-status=live , archive-url= , archive-date=}

(102 pages)
{{cite book , title=Mathematics and Computers , author-first1=George Robert , author-last1=Stibitz , author-link1=George Robert Stibitz , author-first2=Jules A. , author-last2=Larrivee , date=1957 , edition=1 , publisher=McGraw-Hill Book Company, Inc. , publication-place=New York, USA / Toronto, Canada / London, UK , location=Underhill, Vermont, USA , lccn=56-10331 , page=105 (10+228 pages)

Binary arithmetic
Numeral systems