Chapter 2.3, Problem 2.29PP

Program Plan Intro

Two’s complement addition:

Consider two integer values “x” and “y” in the range ${\text{-2}}^{\text{w-1}}\le \text{x,}\text{y}\le {\text{2}}^{\text{w-1}}\text{-}\text{1}$ and their sum in the range ${\text{-2}}^{\text{w}}\le \text{x+y}\le {\text{2}}^{\text{w}}\text{-}2$. The result of given sum is represented by “w + 1” bits.

Calculate the two’s complement truncation by using below formula. That is for bit-level representation of the two’s-complement sum.

${\text{x +}}_{\text{w}}^{\text{t}}{\text{ y = U2T}}_{\text{w}}\left[\left(\text{x}\text{+}\text{y}\right)\text{mod}{\text{2}}^{\text{w}}\right]$

To easily understand the above formula, assume

$\begin{array}{l}\text{z}\text{=}\text{x}\text{+}\text{y}\\ {\text{z' = z mod 2}}^{\text{w}}\\ \text{z''}\text{=}\text{U2T}\left(\text{z'}\right)\end{array}$

There are four cases in the two’s-complement addition.

• Case 1:
  • It is the negative overflow case. The range occurs in ${\text{-2}}^{\text{w}}\le \text{z}<{\text{-2}}^{\text{w-1}}$. Then ${\text{z' = z + 2}}^{\text{w}}$, giving $\text{0}\le \text{z'}\text{<}{\text{-2}}^{\text{w-1}}\text{+}{\text{2}}^{\text{w}}\text{=}{\text{2}}^{\text{w-1}}$.
  • In this case, user has added two negative numbers “x” and “y” and their result is in nonnegative number. Therefore, $\text{z''}\text{=}\text{x+}\text{y}\text{+}{\text{2}}^{\text{w}}$
• Case 2:
  • The range of this case is ${\text{-2}}^{\text{w-1}}\le \text{z}\text{<}\text{0}$. Then it contains ${\text{z' = z + 2}}^{\text{w}}$ giving ${\text{-2}}^{\text{w-1}}\text{+}{\text{2}}^{\text{w}}\text{=}{\text{2}}^{\text{w-1}}\le \text{z'}\text{<}{\text{2}}^{\text{w}}$.
  • The range of “z’” in this case is $\text{z''}\text{=}\text{z'}\text{-}{\text{2}}^{\text{w}}$

    $\begin{array}{c}\text{z''}\text{=}\text{z'}\text{-}{\text{2}}^{\text{w}}\\ \text{=}{\text{z + 2}}^{\text{w}}\text{-}{\text{2}}^{\text{w}}\text{=>}\text{z'}\text{=}{\text{z + 2}}^{\text{w}}\\ \text{z''}\text{=}\text{z}\end{array}$

  • Therefore, the two’s-complement sum “$\text{z''}$” equals the integer sum $\text{z}\text{=}\text{x}\text{+}\text{y}$.
• Case 3:
  • The range of this case is $\text{0}\le \text{z}\text{<}{\text{2}}^{\text{w-1}}$. Then it contains $\text{z' = z}$ giving $\text{0}\le \text{z'}\text{<}{\text{2}}^{\text{w-1}}$.
  • Therefore,$\text{z''}\text{=}\text{z'}\text{=}\text{z}$ and also the two’s-complement sum “$\text{z''}$” equals the integer sum $\text{z}\text{=}\text{x}\text{+}\text{y}$.
• Case 4:
  • It is the positive overflow case. The range occurs in ${\text{2}}^{\text{w-1}}\le \text{z}<{\text{2}}^{\text{w}}$. Then $\text{z' = z}$, giving ${\text{2}}^{\text{w-1}}\le \text{z'}\text{<}{\text{2}}^{\text{w}}$. 
    • But in this case, it contains ${\text{z'' = z' - 2}}^{\text{w}}$ giving ${\text{z'' = (x + y) - 2}}^{\text{w}}$.
  • In this case, user has added two positive numbers “x” and “y” and their result is in negative number. Therefore,$\text{z''}\text{=}\text{x +}\text{y}\text{-}{\text{2}}^{\text{w}}$

“B2T” function:

• The two’s complement encoding is represented by the interpretation function of “B2T_w”.
  • The function “B2T_w” means “binary to two’s complement” of length “w”.
• The equation for “B2T_w” is

${\text{B2T}}_{\text{w}}\left(\overrightarrow{\text{x}}\right)\text{=}{\text{-x}}_{\text{w-1}}{\text{2}}^{\text{w-1}}\text{+}{\displaystyle \sum _{\text{i}\text{=}\text{0}}^{\text{w}\text{-}\text{2}}{\text{x}}_{\text{i}}{\text{2}}^{\text{i}}}$

“U2T” function:

• This function is used to convert the unsigned number to two’s-complement number.
• The equation for computing this function is

${\text{U2T}}_{\text{w}}\left(\text{u}\right)\text{=}{\text{-u}}_{\text{w-1}}{\text{2}}^{\text{w}}\text{+}\text{u}$