Signed-digit representation


Signed-digit representation

Signed-digit representation of numbers indicates that digits can be prefixed with a − (minus) sign to indicate that they are negative.

Signed-digit representation can be used in low-level software and hardware to accomplish fast high speed addition of integers because it can eliminate carries [Dhananjay Phatak, I. Koren, Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains, 1994, [http://citeseer.ist.psu.edu/phatak94hybrid.html] ] . In the binary numeral system one special case of signed-digit representation is the non-adjacent form which can offer speed benefits with minimal space overhead.

Balanced form

In balanced form, the digits are drawn from a range -k to (b-1) - k, where typically k = leftlfloorfrac{b}{2} ight floor. A notable example is balanced ternary, where the base is b=3, and the numerals have the values −1, 0 and +1 (rather than 0, 1 and 2 as in the standard ternary numeral system); another is "balanced decimal", where the digits range from −5 to +4.

Non-unique representations

Note that signed-digit representation is not necessarily unique. For instance:

:(0 1 1 1)2 = 4 + 2 + 1 = 7:(1 0 −1 1)2 = 8 − 2 + 1 = 7:(1 −1 1 1)2 = 8 − 4 + 2 + 1 = 7:(1 0 0 −1)2 = 8 − 1 = 7

The non-adjacent form does guarantee a unique representation for every integer value, as do balanced forms.

When representations are extended to fractional numbers, uniqueness is lost for non-adjacent and balanced forms; for example,:(0 . (1 0)…)NAF = fraction|2|3 = (1 . (0 −1)…)NAFand:(0 . 4 4 4 …)(10bal) = fraction|4|9 = (1 . -5 -5 -5 …)(10bal)

Such examples can be shown to exist by considering the largest and smallest possible representations with integral parts 0 and 1 respectively, and then noting that they are equal. (Indeed, this works with any integral-base system.)

ee also

* negative base (negabinary etc.)
* redundant binary representation

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Redundant binary representation — A redundant binary representation (RBR) is a numeral system that uses more bits than needed to represent a single binary digit so that most numbers have several representations. RBR is unlike usual binary numeral systems, including two s… …   Wikipedia

  • Non-standard positional numeral systems — Numeral systems by culture Hindu Arabic numerals Western Arabic (Hindu numerals) Eastern Arabic Indian family Tamil Burmese Khmer Lao Mongolian Thai East Asian numerals Chinese Japanese Suzhou Korean Vietnamese …   Wikipedia

  • Non-adjacent form — Numeral systems by culture Hindu Arabic numerals Western Arabic Eastern Arabic Indian family Tamil Burmese Khmer Lao Mongolian Thai East Asian numerals Chinese Japanese Suzhou Korean Vietnamese …   Wikipedia

  • Sign (mathematics) — The plus and minus symbols are used to show the sign of a number. Not to be confused with the sine function in trigonometry. In mathematics, the word sign refers to the property of being positive or negative. Every nonzero real number is either… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Floating point — In computing, floating point describes a method of representing real numbers in a way that can support a wide range of values. Numbers are, in general, represented approximately to a fixed number of significant digits and scaled using an exponent …   Wikipedia

  • Integer (computer science) — In computer science, an integer is a datum of integral data type, a data type which represents some finite subset of the mathematical integers. Integral data types may be of different sizes and may or may not be allowed to contain negative values …   Wikipedia

  • Year 2000 problem — Y2K redirects here. For other uses, see Y2K (disambiguation). The (French) sign reads 3 January 1900 instead of 3 January 2000 The Year 2000 problem (also known as the Y2K problem, the Millennium bug, the Y2K bug, or simply Y2K) was a problem for …   Wikipedia

  • Punched card — Overpunch redirects here. For the code, see Signed overpunch. A punched card, punch card, IBM card, or Hollerith card is a piece of stiff paper that contains digital information represented by the presence or absence of holes in predefined… …   Wikipedia

  • Negative base — Numeral systems by culture Hindu Arabic numerals Western Arabic Eastern Arabic Indian family Tamil Burmese Khmer Lao Mongolian Thai East Asian numerals Chinese Japanese Suzhou Korean Vietnamese …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.