HOME

TheInfoList



OR:

Excess-3, 3-excess or 10-excess-3
binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two digits (0 and 1) * Binary function, a function that takes two arguments * Binary operation, a mathematical operation that t ...
code (often abbreviated as XS-3, 3XS or X3), shifted binary or Stibitz code (after
George Stibitz George Robert Stibitz (April 30, 1904 – January 31, 1995) was a Bell Labs researcher internationally recognized as one of the fathers of the modern digital computer. He was known for his work in the 1930s and 1940s on the realization of Boolea ...
, who built a relay-based adding machine in 1937) is a self-complementary
binary-coded decimal In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each digit is represented by a fixed number of bits, usually four or eight. Sometimes, special bit patterns are used for ...
(BCD) code and
numeral system A numeral system (or system of numeration) is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using digits or other symbols in a consistent manner. The same sequence of symbo ...
. 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 code The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For example, the representat ...
s) are non-weighted codes. In excess-3 code, numbers are represented as decimal digits, and each digit is represented by four
bit The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
s 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
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s than normal non-biased BCD or binary
positional system Positional notation (or place-value notation, or positional numeral system) usually denotes the extension to any base of the Hindu–Arabic numeral system (or decimal system). More generally, a positional system is a numeral system in which the ...
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' complement The ones' complement of a binary number is the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s). The name "ones' complement" (''note this is possessive of the plural "ones", not of a si ...
ed: 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 The VHSIC Hardware Description Language (VHDL) is a hardware description language (HDL) that can model the behavior and structure of digital systems at multiple levels of abstraction, ranging from the system level down to that of logic gat ...
: 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 The ITU Telecommunication Standardization Sector (ITU-T) is one of the three sectors (divisions or units) of the International Telecommunication Union (ITU). It is responsible for coordinating standards for telecommunications and Information Commu ...
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 In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chang ...
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 Offset binary, also referred to as excess-K, excess-''N'', excess-e, excess code or biased representation, is a method for signed number representation where a signed number n is represented by the bit pattern corresponding to the unsigned numbe ...
, excess-''N'', biased representation * Excess-128 * Excess-Gray code * Shifted Gray code *
Gray code The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For example, the representat ...
*
m-of-n code In coding theory, a constant-weight code, also called an ''m''-of-''n'' code, is an error detection and correction code where all codewords share the same Hamming weight. The one-hot code and the balanced code are two widely used kinds of constant ...
*
Aiken code Aiken may refer to: Places * Aiken, Illinois * Aiken County, South Carolina * Aiken, South Carolina, Aiken County's county seat * The University of South Carolina Aiken * Aiken, Texas (disambiguation) ** Aiken, Bell County, Texas ** Aiken, Floyd ...


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 Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing. Originally founded in 1842 ...
, 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
misprint A typographical error (often shortened to typo), also called a misprint, is a mistake (such as a spelling mistake) made in the typing of printed (or electronic) material. Historically, this referred to mistakes in manual type-setting ( typography ...
s 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 Simon & Schuster () is an American publishing company and a subsidiary of Paramount Global. It was founded in New York City on January 2, 1924 by Richard L. Simon and M. Lincoln Schuster. As of 2016, Simon & Schuster was the third largest publi ...
, 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. Macmillan Publishers (occasionally known as the Macmillan Group; formally Macmillan Publishers Ltd and Macmillan Publishing Group, LLC) is a British publishing company traditionally considered to be one of the 'Big Five' English language publ ...
/ 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