Excess-3

Last updated

Stibitz code
Digits4 [1]
Tracks4 [1]
Digit values 8  4 −2 −1
Weight(s) 1..3 [1]
ContinuityNo [1]
Cyclic No [1]
Minimum distance 1 [1]
Maximum distance4
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.

Contents

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

Excess-3, and Stibitz code
DecimalExcess-3Stibitz BCD 8-4-2-1 Binary3-of-6 CCITT
extension [13] [1] 		4-of-8 Hamming
extension [1]
−30000 pseudo-tetrade N/AN/AN/AN/A
−20001pseudo-tetrade
−10010pseudo-tetrade
00011001100000000…10…0011
10100010000010001…11…1011
20101010100100010…10…0101
30110011000110011…10…0110
40111011101000100…00…1000
51000100001010101…11…0111
61001100101100110…10…1001
71010101001110111…10…1010
81011101110001000…00…0100
91100110010011001…10…1100
101101pseudo-tetradepseudo-tetrade1010N/AN/A
111110pseudo-tetradepseudo-tetrade1011
121111pseudo-tetradepseudo-tetrade1100
13N/AN/Apseudo-tetrade1101
14pseudo-tetrade1110
15pseudo-tetrade1111

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:

entitybcd8421xs3isport(a:instd_logic;b:instd_logic;c:instd_logic;d:instd_logic;an:bufferstd_logic;bn:bufferstd_logic;cn:bufferstd_logic;dn:bufferstd_logic;w:outstd_logic;x:outstd_logic;y:outstd_logic;z:outstd_logic);endentitybcd8421xs3;architecturedataflowofbcd8421xs3isbeginan<=nota;bn<=notb;cn<=notc;dn<=notd;w<=(anandbandd)or(aandbnandcn)or(anandbandcanddn);x<=(anandbnandd)or(anandbnandcanddn)or(anandbandcnanddn)or(aandbnandcnandd);y<=(anandcnanddn)or(anandcandd)or(aandbnandcnanddn);z<=(ananddn)or(aandbnandcnanddn);endarchitecturedataflow;-- of bcd8421xs3

Extensions

3-of-6 extension
Digits6 [1]
Tracks6 [1]
Weight(s) 3 [1]
ContinuityNo [1]
Cyclic No [1]
Minimum distance 2 [1]
Maximum distance6
Lexicography 1 [1]
Complement (9) [1]
4-of-8 extension
Digits8 [1]
Tracks8 [1]
Weight(s) 4 [1]
ContinuityNo [1]
Cyclic No [1]
Minimum distance 4 [1]
Maximum distance8
Lexicography 1 [1]
Complement 9 [1]

See also

Related Research Articles

<span class="mw-page-title-main">Binary-coded decimal</span> System of digitally encoding numbers

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 a sign or other indications.

In computer science, an integer is a datum of integral data type, a data type that represents some range of mathematical integers. Integral data types may be of different sizes and may or may not be allowed to contain negative values. Integers are commonly represented in a computer as a group of binary digits (bits). The size of the grouping varies so the set of integer sizes available varies between different types of computers. Computer hardware nearly always provides a way to represent a processor register or memory address as an integer.

<span class="mw-page-title-main">Nibble</span> Four-bit unit of digital information

In computing, a nibble (occasionally nybble, nyble, or nybl to match the spelling of byte) is a four-bit aggregation, or half an octet. It is also known as half-byte or tetrade. In a networking or telecommunication context, the nibble is often called a semi-octet, quadbit, or quartet. A nibble has sixteen (24) possible values. A nibble can be represented by a single hexadecimal digit (0–F) and called a hex digit.

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.

A ternary numeral system has three as its base. Analogous to a bit, a ternary digit is a trit. One trit is equivalent to log2 3 bits of information.

A binary code represents text, computer processor instructions, or any other data using a two-symbol system. The two-symbol system used is often "0" and "1" from the binary number system. The binary code assigns a pattern of binary digits, also known as bits, to each character, instruction, etc. For example, a binary string of eight bits can represent any of 256 possible values and can, therefore, represent a wide variety of different items.

A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one).

In digital electronics, a binary decoder is a combinational logic circuit that converts binary information from the n coded inputs to a maximum of 2n unique outputs. They are used in a wide variety of applications, including instruction decoding, data multiplexing and data demultiplexing, seven segment displays, and as address decoders for memory and port-mapped I/O.

Bi-quinary coded decimal is a numeral encoding scheme used in many abacuses and in some early computers, including the Colossus. The term bi-quinary indicates that the code comprises both a two-state (bi) and a five-state (quinary) component. The encoding resembles that used by many abacuses, with four beads indicating the five values either from 0 through 4 or from 5 through 9 and another bead indicating which of those ranges.

4-bit computing is the use of computer architectures in which integers and other data units are 4 bits wide. 4-bit central processing unit (CPU) and arithmetic logic unit (ALU) architectures are those that are based on registers or data buses of that size. A group of four bits is also called a nibble and has 24 = 16 possible values.

In computing, signed number representations are required to encode negative numbers in binary number systems.

The Intel BCD opcodes are a set of six x86 instructions that operate with binary-coded decimal numbers. The radix used for the representation of numbers in the x86 processors is 2. This is called a binary numeral system. However, the x86 processors do have limited support for the decimal numeral system.

Chen–Ho encoding is a memory-efficient alternate system of binary encoding for decimal digits.

Densely packed decimal (DPD) is an efficient method for binary encoding decimal digits.

Decimal floating-point (DFP) arithmetic refers to both a representation and operations on decimal floating-point numbers. Working directly with decimal (base-10) fractions can avoid the rounding errors that otherwise typically occur when converting between decimal fractions and binary (base-2) fractions.

<span class="mw-page-title-main">Decimal computer</span> Computer operating on base-10 numbers

Decimal computers are computers which can represent numbers and addresses in decimal as well as providing instructions to operate on those numbers and addresses directly in decimal, without conversion to a pure binary representation. Some also had a variable wordlength, which enabled operations on numbers with a large number of digits.

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 number n+K, K being the biasing value or offset. There is no standard for offset binary, but most often the K for an n-bit binary word is K = 2n−1 (for example, the offset for a four-digit binary number would be 23=8). This has the consequence that the minimal negative value is represented by all-zeros, the "zero" value is represented by a 1 in the most significant bit and zero in all other bits, and the maximal positive value is represented by all-ones (conveniently, this is the same as using two's complement but with the most significant bit inverted). It also has the consequence that in a logical comparison operation, one gets the same result as with a true form numerical comparison operation, whereas, in two's complement notation a logical comparison will agree with true form numerical comparison operation if and only if the numbers being compared have the same sign. Otherwise the sense of the comparison will be inverted, with all negative values being taken as being larger than all positive values.

BCD, also called alphanumeric BCD, alphameric BCD, BCD Interchange Code, or BCDIC, is a family of representations of numerals, uppercase Latin letters, and some special and control characters as six-bit character codes.

A half-carry flag is a condition flag bit in the status register of many CPU families, such as the Intel 8080, Zilog Z80, the x86, and the Atmel AVR series, among others. It indicates when a carry or borrow has been generated out of the least significant four bits of the accumulator register following the execution of an arithmetic instruction. It is primarily used in decimal (BCD) arithmetic instructions.

<span class="mw-page-title-main">Aiken code</span>

The Aiken code is a complementary binary-coded decimal (BCD) code. A group of four bits is assigned to the decimal digits from 0 to 9 according to the following table. The code was developed by Howard Hathaway Aiken and is still used today in digital clocks, pocket calculators and similar devices.

References

  1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 Steinbuch, Karl W., ed. (1962). Written at Karlsruhe, Germany. Taschenbuch der Nachrichtenverarbeitung (in German) (1 ed.). Berlin / Göttingen / New York: Springer-Verlag OHG. pp. 71–73, 1081–1082. LCCN   62-14511.
  2. 1 2 Steinbuch, Karl W.; Weber, Wolfgang; Heinemann, Traute, eds. (1974) [1967]. Taschenbuch der Informatik – Band II – Struktur und Programmierung von EDV-Systemen. pp. 98–100. ISBN   3-540-06241-6. LCCN   73-80607.{{cite book}}: |work= ignored (help)
  3. ↑ Richards, Richard Kohler (1955). Arithmetic Operations in Digital Computers. New York, USA: van Nostrand. p. 182.
  4. ↑ Kautz, William H. (June 1954). "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. Session 19: Information Theory III - Speed and Computation. Retrieved 2020-05-22. (11 pages)
  5. ↑ 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.
  6. ↑ 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.)
  7. ↑ Stibitz, George Robert; Larrivee, Jules A. (1957). Written at Underhill, Vermont, USA. Mathematics and Computers (1 ed.). New York, USA / Toronto, Canada / London, UK: McGraw-Hill Book Company, Inc. p. 105. LCCN   56-10331. (10+228 pages)
  8. ↑ Dokter, Folkert; Steinhauer, Jürgen (1973-06-18). Digital Electronics. Philips Technical Library (PTL) / Macmillan Education (Reprint of 1st English ed.). Eindhoven, Netherlands: The Macmillan Press Ltd. / N. V. Philips' Gloeilampenfabrieken. pp. 42, 44. doi:10.1007/978-1-349-01417-0. ISBN   978-1-349-01419-4. SBN   333-13360-9 . Retrieved 2018-07-01. (270 pages) (NB. This is based on a translation of volume I of the two-volume German edition.)
  9. ↑ Dokter, Folkert; Steinhauer, Jürgen (1975) [1969]. Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Theoretische Grundlagen und Schaltungstechnik. Philips Fachbücher (in German). Vol. I (improved and extended 5th ed.). Hamburg, Germany: Deutsche Philips GmbH. 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. ↑ Stibitz, George Robert (1954-02-09) [1941-04-19]. "Complex Computer". Patent US2668661A. Retrieved 2020-05-24. (102 pages)
  11. 1 2 Mietke, Detlef (2017) [2015]. "Binäre Codices". Informations- und Kommunikationstechnik (in German). Berlin, Germany. Exzeß-3-Code mit Additions- und Subtraktionsverfahren. Archived from the original on 2017-04-25. Retrieved 2017-04-25.
  12. ↑ Ritchie, David (1986). The Computer Pioneers. New York, USA: Simon and Schuster. p.  35. ISBN   067152397X.
  13. 1 2 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. ↑ Bashe, Charles J.; Jackson, Peter Ward; Mussell, Howard A.; Winger, Wayne David (January 1956). "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. doi:10.1109/TCE.1956.6372444. S2CID   51666209. Paper No. 55-719.
  16. ↑ IBM (July 1957). 65 Data Transceiver / 66 Printing Data Receiver.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.