2
$\begingroup$

I've started a logic design class where there is a chapter on binary codes and their computing (addition and subtraction). While I grasp easily the representation of negative values using sign-magnitude, one's complement, and two's complement, I'm confused about the excess-$N$ one. I've been on Wikipedia and all but I seem not to get it.

Can anyone please explain to me using examples for, let's say, excess-3 and excess-8?

There is also the value of the magic number; in my book it's $2^{(N-1)}$, while on the net I can find $2^{(N+1)}$.

$\endgroup$
3
$\begingroup$

Excess-N notation shifts all values by N. That is, in excess-N notation, the number represented by a binary code is N less than the unsigned value you would normally assign to that code.

For example, in excess-3 notation, the string '0000' (which is 0 in unsigned binary) represents 0 - 3 = -3. The string '0100' (which is 4 in unsigned binary) represents 4 - 3 = 1.

It's quite common to see excess-N notation when denoting the exponent of a floating point numbers. For example, 32-bit floating point numbers often use 8 bits in excess-127 notation to represent the exponent.

$\endgroup$
2
$\begingroup$

You may find the explanations and charts here helpful; note in particular the complete chart of $3$-bit excess-$4$ notation.

The term magic number refers to a particularly useful value of the shift. The basic idea is to shift the numbers in the representable range so that half of them are positive and half are negative. Of course that’s not actually possible. If you’re using $n$ bits, you can represent $2^n$ different integers. One of them will be $0$, leaving $2^n-1$ that are either positive or negative. But $2^n-1$ is odd, so you can’t make an even split. If you take $2^{n-1}$ as the amount of the shift, so that a string of $n$ zeroes represents the number $-2^{n-1}$, you will be able to represent the $2^{n-1}$ negative integers between $-2^{n-1}$ and $-1$ inclusive, the number $0$, and the $2^{n-1}-1$ positive integers from $1$ through $2^{n-1}-1$; this is as close to an even split as you can get. Moreover, you can tell from the first bit whether a number is negative or not: negative numbers have $0$ as their first bit, while $0$ and the positive integers have a first bit of $1$. In this respect excess-$2^{n-1}$ notation aligns $0$ with the positive integers.

You can come equally close to an even split by using a shift of $2^{n-1}-1$. If you do this, a string of $n$ zeroes represents the integer $-(2^{n-1}-1) = 1 - 2^{n-1}$. When $n=3$, for instance, $000$ now represents $1-2^2 = -3$, not $-4$ as it would in the excess-$4$ notation illustrated on that web page. Now the range of integers that can be represented runs from $-2^{n-1}+1$ through $2^{n-1}$; for $n=3$ that’s from $-3$ through $4$ instead of from $-4$ through $3$. Now the integers with first bit $1$ are positive, and those with first bit $0$ are negative or $0$, so that $0$ is aligned with the negative integers.

The first of these systems is, I think, more common, so magic number for $n$-bit notation usually refers to $2^{n-1}$, but I have seen the term applied to $2^{n-1}-1$ as well, referring to the second of these systems. $2^{n+1}$, however, is simply wrong: either it’s a typo, or it refers to something else altogether.

$\endgroup$
  • $\begingroup$ @brian-m-scott Can you check this from your link: "In fact, excess K representation maps 0^N to -K, and 1^N to -K + 2^N - 1" I have doubts about 1^N Below the second chart. $\endgroup$ – malhobayyeb Sep 24 '12 at 3:44
  • 1
    $\begingroup$ @MIH1406: It’s okay: $1^N$ means $\underbrace{1\dots 1}_n$, a string of $n$ $1$’s, which is the binary representation of $2^N-1$, so it represents $2^N-1$ more than $0^N=\underbrace{0\dots 0}_n$ does. The latter represents $-K$, so the former represents $-K+2^N-1$. $\endgroup$ – Brian M. Scott Sep 24 '12 at 3:53
  • 1
    $\begingroup$ the link provided no longer reaches a site $\endgroup$ – Jessica Tiberio Sep 30 '18 at 18:04
1
$\begingroup$

Excess Notation:

This fixed length notation (i.e., the length of the bit pattern used can not be altered once set at the beginning) makes it possible to store negative (-) and non-negative (+ including zero) values by treating the right-most digits referred to as the Most Significant Bit (MSB) as representing the sign of the number. In excess notation the MSB also known as the sign bit of 1 represents the non-negative (+) sign and a 0 indicates a negative (-) number. Note the two examples below.

Example # 1.

In the case of a 4-bit pattern, for example: 0110 the digit/column value of the most significant bit is 8, so 4 bit patterns are referred to as an “excess (8)†notation.

To convert this example find the sum value of the entire pattern as though a standard binary number: (0x8) + (1x4) + (1x2) + (0x1) = 610

Then subtract the excess value,8, from the sum, (6 – 8) The result is a signed value, -2.

Example # 2.

In the case of a 5-bit pattern example, 11110, the digit/column value of the most significant bit is 16, so 5-bit patterns are referred to as an “excess (16)†notation.

To convert this example find the sum value of the entire pattern as though a standard binary number: (1x16) + (1x8) + (1x4) + (1x2) + (0x1) = 16 + 8 + 4 + 2 + 0 = 30

Then subtract the current excess value, 16, from the sum, (30 – 16) The result is a signed value, + 14. Therefore, it is evident that in excess notation, the sign bit of 0 represents the negative sign and 1 represents the non-negative sign to denote a signed value.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.