next up previous contents
Next: Binary Operations Up: Logical Operations Previous: Logical Operations   Contents

Complementation

We have a simple arithmetic definition of the logical complement.

Definition 3.1.1   (lnot) For all $ x \in \mathbb{N}$ and $ n \in \mathbb{N}$ ,

$\displaystyle lnot(x,n) = 2^n - x[n$-$\displaystyle 1:0] - 1.$

Before introducing our notation for this operation, we offer two relevant observations.

  (lnot-bits-1) For all $ x \in \mathbb{N}$ and $ n \in \mathbb{N}$ ,

$\displaystyle lnot(x[n$-$\displaystyle 1:0],n) = lnot(x,n).$

PROOF: By Lemma 2.2.20, $ x[n$-$ 1:0][n$-$ 1:0] = x[n$-$ 1:0]$ . 

  (lnot-bvecp) For all $ x \in \mathbb{N}$ and $ n \in \mathbb{N}$ , $ lnot(x,n)$ is an $ n$ -bit vector.

PROOF: Since $ 0 \leq x[n$-$ 1:0] < 2^n$ , $ 0 \leq 2^n - x[n$-$ 1:0] - 1 < 2^n$ . 

Corollary 3.1.3   (lnot-x-0) For all $ x \in \mathbb{N}$ , $ lnot(x,0) = 0$ .

Notation: For any expressions $ \phi $ and $ \lambda$ , the size the expression ` $ lnot(\phi,\lambda,)$ ' is defined to be $ \lambda$ (cf. Figure 2.4).

If $ \phi $ is an expression of size $ \lambda$ , then ` $ \verb! !\phi$ ' is an abbreviation for ` $ lnot(\phi,\lambda)$ ' (cf. Figure 2.4).

For example, ` $ \verb! !x[n$-$ 1:0]$ ' is an abbreviation for

$\displaystyle lnot(x[n$-$\displaystyle 1:0],n)$

and according to Lemma 3.2.2, may also be used as an abbreviation for `$ lnot(x,n)$ '.

For the purpose of resolving ambiguous expressions, this construction has higher precedence than the basic arithmetic operators but lower than the bit slice operator, e.g.,

$\displaystyle 3 \cdot \verb! !x[i:j][k:\ell] = 3 (\verb! !((x[i:j])[k:\ell])).$

Our next two results pertain to left- and right-shifted arguments.

  (lnot-shift) For all $ x \in \mathbb{N}$ , $ n \in \mathbb{N}$ , and $ k \in \mathbb{N}$ ,

$\displaystyle \verb! !(2^kx)[n$-$\displaystyle 1:0] = \left\{\begin{array}{ll} 2^k (\verb! !x[n\mbox{-}k\mbox{-... ...+1) -1 & \mbox{if $k \leq n$}\\ 2^n-1 & \mbox{if $k > n$}. \end{array} \right.$

PROOF: First note that

$\displaystyle \verb! !(2^kx)[n$-$\displaystyle 1:0]$ $\displaystyle =$ $\displaystyle 2^n - (2^kx)[n$-$\displaystyle 1:0] - 1$  
  $\displaystyle =$ $\displaystyle 2^n - 2^kx[n$-$\displaystyle k$-$\displaystyle 1:0] - 1$  

by Lemma 2.2.16. If $ k>n$ , then $ x[n$-$ k$-$ 1:0] = 0$ by Lemma 2.2.8, and the result follows. On the other hand, if $ k \leq n$ , then
$\displaystyle 2^n - 2^kx[n$-$\displaystyle k$-$\displaystyle 1:0] - 1$ $\displaystyle =$ $\displaystyle 2^k(2^{n-k} - x[n$-$\displaystyle k$-$\displaystyle 1:0] - 1) + 2^k-1$  
  $\displaystyle =$ $\displaystyle 2^k (\verb! !x[n$-$\displaystyle k$-$\displaystyle 1:0]+1) -1.$  

  (lnot-fl) For all $ x \in \mathbb{N}$ , $ n \in \mathbb{N}$ , and $ k \in \mathbb{N}$ ,

$\displaystyle \verb! !\lfloor x/2^k \rfloor[n$-$\displaystyle 1:0] = \lfloor \verb! !x[n+k$-$\displaystyle 1:0]/2^k \rfloor.$

PROOF:

$\displaystyle \verb! !\lfloor x/2^k \rfloor[n$-$\displaystyle 1:0]$ $\displaystyle =$ $\displaystyle 2^n - \lfloor x/2^k \rfloor[n$-$\displaystyle 1:0] - 1$  
  $\displaystyle =$ $\displaystyle 2^n - x[n$+$\displaystyle k$-$\displaystyle 1:0] - 1$                   (by Lemma 2.2.13)  
  $\displaystyle =$ $\displaystyle 2^n - \lfloor x[n$+$\displaystyle k$-$\displaystyle 1:k]/2^k \rfloor - 1$            (by Lemma 2.2.11)  
  $\displaystyle =$ $\displaystyle 2^n + \lfloor -(x[n$+$\displaystyle k$-$\displaystyle 1:k]-1)/2^k\rfloor$       (by Lemma 1.1.3)  
  $\displaystyle =$ $\displaystyle \lfloor (2^{n+k} - x[n$+$\displaystyle k$-$\displaystyle 1:k]-1)/2^k\rfloor$      (by Lemma 1.1.6)  
  $\displaystyle =$ $\displaystyle \lfloor \verb! !x[n$+$\displaystyle k$-$\displaystyle 1:0]/2^k \rfloor.$  

The remaining lemmas of this section deal with commutativity properties between lnot and various other operators.

  (mod-lnot) For all $ x \in \mathbb{N}$ , $ n \in \mathbb{N}$ , and $ k \in \mathbb{N}$ , if $ k \leq n$ , then

$\displaystyle mod(\verb! !x[n$-$\displaystyle 1:0],2^k) = \verb! !x[k$-$\displaystyle 1:0].$

PROOF: By Lemma 2.2.19,

$\displaystyle x[n$-$\displaystyle 1:0] = 2^kx[n$-$\displaystyle 1:k] + x[k$-$\displaystyle 1:0],$

and hence, applying Lemma 1.2.16, we have
$\displaystyle mod(\verb! !x[n$-$\displaystyle 1:0],2^k)$ $\displaystyle =$ $\displaystyle mod(2^n - x[n$-$\displaystyle 1:0] - 1,2^k)$  
  $\displaystyle =$ $\displaystyle mod(2^k(2^{n-k}$-$\displaystyle x[n$-$\displaystyle 1:k]$-$\displaystyle 1) + 2^k$-$\displaystyle x[k$-$\displaystyle 1:0]$-$\displaystyle 1,2^k)$  
  $\displaystyle =$ $\displaystyle mod(2^k - x[k$-$\displaystyle 1:0] - 1,2^k)$  
  $\displaystyle =$ $\displaystyle mod(\verb! !x[k$-$\displaystyle 1:0],2^k),$  

which reduces, by Lemmas 3.1.2 and 1.2.7, to $ \verb! !x[k$-$ 1:0]$ . 

  (bits-lnot) For all $ x \in \mathbb{N}$ , $ n \in \mathbb{N}$ , $ i \in \mathbb{N}$ , and $ j \in \mathbb{N}$ ,

$\displaystyle (\verb! !x[n$-$\displaystyle 1:0])[i:j] = \left\{\begin{array}{ll} \verb! !x[i:j] & \mbox{if $i<n$}\\ \verb! !x[n\mbox{-}1:j] & \mbox{if $i \geq n$.} \end{array} \right.$

PROOF: By Definition 2.2.1,

$\displaystyle (\verb! !x[n$-$\displaystyle 1:0])[i:j] = \lfloor mod(\verb! !x[n$-$\displaystyle 1:0],2^{i+1})/2^j \rfloor.$

If $ i<n$ , then this reduces to

$\displaystyle \lfloor \verb! !x[i:0]/2^j\rfloor$

by Lemma 3.1.6, whereas if $ i \geq n$ , then Lemma 1.2.7 yields

$\displaystyle \lfloor \verb! !x[n-1:0]/2^j\rfloor$

instead. Let $ k = min(i,n-1).$ Then in either case, by Lemmas 3.1.5 and 2.2.13,
$\displaystyle (\verb! !x[n$-$\displaystyle 1:0])[i:j]$ $\displaystyle =$ $\displaystyle \lfloor \verb! !x[k:0]/2^j\rfloor$  
  $\displaystyle =$ $\displaystyle \verb! !\lfloor x/2^j \rfloor [k-j:0]$  
  $\displaystyle =$ $\displaystyle \verb! !x[k:j].$  

It is the following result that allows us to refer to this operation as bit-wise complementation.

  (bitn-lnot) For all $ x \in \mathbb{N}$ , $ n \in \mathbb{N}$ , and $ k \in \mathbb{N}$ ,

$\displaystyle (\verb! !x[n$-$\displaystyle 1:0])[k] = \left\{\begin{array}{ll} \verb! !x[k] & \mbox{if $k<n$}\\ 0 & \mbox{if $k \geq n$.} \end{array} \right.$

PROOF: This is the case of Lemma 3.1.7 with $ i=j=k$ . 

  (lnot-cat) For all $ x \in \mathbb{N}$ , $ y \in \mathbb{N}$ , $ m \in \mathbb{N}$ , and $ n \in \mathbb{N}$ ,

$\displaystyle \verb! !\{x[m$-$\displaystyle 1:0],y[n$-$\displaystyle 1:0]\} = \{\verb! !x[m$-$\displaystyle 1:0],\verb! !y[n$-$\displaystyle 1:0]\}.$

PROOF: This is an immediate consequence of the definitions. Since

$\displaystyle \verb! !\{x[m$-$\displaystyle 1:0],y[n$-$\displaystyle 1:0]\}$

is an expression of size $ m+n$ ,
$\displaystyle \verb! !\{x[m$-$\displaystyle 1:0],y[n$-$\displaystyle 1:0]\}$ $\displaystyle =$ $\displaystyle 2^{m+n} - \{x[m$-$\displaystyle 1:0],y[n$-$\displaystyle 1:0]\} - 1$  
  $\displaystyle =$ $\displaystyle 2^{m+n} - 2^nx[m$-$\displaystyle 1:0] - y[n$-$\displaystyle 1:0] - 1$  
  $\displaystyle =$ $\displaystyle 2^n(2^m - x[m$-$\displaystyle 1:0] - 1) + 2^n - y[n$-$\displaystyle 1:0] - 1$  
  $\displaystyle =$ $\displaystyle 2^n(\verb! !x[m$-$\displaystyle 1:0]) + \verb! !y[n$-$\displaystyle 1:0]$  
  $\displaystyle =$ $\displaystyle \{\verb! !x[m$-$\displaystyle 1:0],\verb! !y[n$-$\displaystyle 1:0]\}.$  

next up previous contents
Next: Binary Operations Up: Logical Operations Previous: Logical Operations   Contents
David Russinoff 2007-01-02