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.
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):
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]
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]
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
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] |
{{
cite book}}
: |work=
ignored (
help)
{{
cite book}}
: CS1 maint: numeric names: authors list (
link)
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.
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):
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]
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]
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
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] |
{{
cite book}}
: |work=
ignored (
help)
{{
cite book}}
: CS1 maint: numeric names: authors list (
link)