58 4 Word-Length Optimization
	ˆ		(4.37)
no − βv + mv − 1 ≥ δv3(mv − βv )
Av + (k2 − k1)no − k2βv + k2(mv − 1) − k1 ≥
(1 − δv3) (k2 − k1)ˆno − k2βˆv + k2(mv − 1) − k1			(4.38)
no − βv + mv − 1 < δv4	(ˆno + mv − 2)		(4.39)
Av + k1(mv − βv − 2) ≥ (1 − δv4)k1	ˆ		(4.40)
	(mv − βv − 2)

The pre-quantization output word-length of an adder with inputs i and j and output o is given by nqo = max(ni − pi, nj − pj ) + po. We may express this as (4.41)–(4.42), since before-quantization word-lengths only appear with negative coe cient in the error so the error constraints can be relied upon to reduce nqo to achieve equality.

noq ≥ ni − pi + po	(4.41)
noq ≥ nj − pj + po	(4.42)

4.5.3 Forks

As demonstrated in Section 4.3.1, fork nodes can lead to unusual error behaviour due to the di erent possible orderings of word-length at their outputs, which are required in order to guarantee freedom from statistical correlation and hence an accurate error model. Fig. 4.17 illustrates the six di erent possible configurations of a 3-way fork with outputs n1, n2 and n3. For example, the top left figure corresponds to n1 ≥ n2 ≥ n3 and the bottom right to n3 ≥ n2 ≥ n1. Each of the ‘Q’ blocks is a truncation of least-significant bits in a signal. The z-domain transfer function from the truncation error injected, to the system output, is shown underneath the relevant ‘Q’ block.

In order for the MILP to fully model this behaviour it is necessary to consider each of the possible orderings. Let σv be a w-tuple, representing an order (a, b, . . . , f ) on a w-way fork node v VF with input signal i. Thus, for example, σv (2) is the second largest signal width. We may express the error resulting from truncation of those signals driven by node v as (4.43), with one constraint per possible σ, a total of w!. Here represents Boolean conjunction.

w−1	w−1 2	w−r
r
=1 (nσv (r) ≥ nσv (r+1))
Ev = 22pi	r=1 L2	h=1 Hσv (h)	(2−2nσv (r+1)		(4.43)
	2		q	− 2−2nw )
−2−2nσv (r) ) + L2 h=1 Hσv (h)(2−2ni
		w

Applying DeMorgan’s theorem and linearizing the resulting disjunction gives (4.44)–(4.48). Each exponential is then further linearized through the

4.5 Optimization Strategy 2: Optimum Solutions

59

Q

n 1

Q

2

n 2

Q

3

n3

Q

n 2

Q

2

n3

Q

3

n 1

1

1

H1+ H2+ H3

H2 + H3

H 3

H1+ H2+ H3

H1 + H3

H 1

n 1

n3

n 2

n3

n 1

n 2

Q

Q

2

Q

3

Q

Q

2

Q

3

1

1

H1+ H2+ H3

H2 + H3

H 2

H1+ H2+ H3

H1 + H2

H 2

n 2

n 1

n3

n3

n 2

n 1

Q

Q

2

Q

3

Q

Q

2

Q

3

1

1

H1+ H2+ H3

H1 + H3

H 3

H1+ H2+ H3

H1 + H2

H 1

(a) possible output permutations in a 3-way FORK

H1+ H2+ H3

H 1

H 2

H 3

(b) the original FORK specification

Fig. 4.17. Possible output permutations in a 3-way fork

procedure described in Section 4.5. The and η variables in (4.44)–(4.48) are additional binary decision variables and the right-hand side of each inequality consists of a trivial bound on the left-hand side, multiplied by a decision variable. At least one inequality is non-trivial, a property ensured by (4.48).

nσ(1) − nσ(2) < vσ(1),σ(2)nˆσ(1) nσ(2) − nσ(3) < vσ(2),σ(3)nˆσ(2)

							. . .
nσ(w−1) − nσ(w) < vσ(w−1),w nˆσ(w−1)
Ev − 22pi		w−1		w−r
		L22			Hσ(h) (2−2nσv(r+1)
		r=1		h=1		−2−2nσv (r) )+
L22		Hσ(h) (2−2nσv(w)
	w					− 2−2noq ) ≥
h=1
				w−1			w−r
	−ηvσ 22(pi −1)				L22		Hσ(h)
					r=0		h=1
		w−1

(4.44)

(4.45)

(4.46)

(4.47)

vσ(r),σ(r+1) + ηvσ ≤ w − 1

(4.48)

r=1

60 4 Word-Length Optimization

It is not necessary to explicitly consider quantization of the input signal to a fork node, since the above constraints use the pre-quantization word-length of the fork input nqi . It is necessary, however, to guarantee that the input signal provides enough word-length for the largest of its outputs (4.49).

ni ≥ na
ni ≥ nb	(4.49)
. . .
ni ≥ nf

4.5.4 Gains and Delays

In contrast to adders and fork nodes, gain nodes are straight-forward. The area of a gain node has already been modelled in the objective function (Section 4.5). The only remaining constraint required is to model the prequantization output word-length of a gain v VG with input signal a, output signal o and coe cient of word-length cw(v) and scaling sc(v). This constraint is already in linear form (4.50).

noq = na + cw(v) − pa − sc(v) + po

(4.50)

Delay nodes also have a simple relationship between their input wordlength and their output word-length before quantization, shown in (4.51) for the case of a delay node with input i and output o.

noq = ni

(4.51)

4.5.5 MILP Summary

A MILP model for the word-length optimization problem has been proposed. It remains to quantify the number of variables (4.52) and constraints (4.53) present in the model. Note that the number of constraints given does not include integrality constraints, the unit upper bounds on Boolean variables, or the trivial fork constraints in (4.49) which do not form part of the optimization problem.

vars = (ˆns + 1)+

s S\pred(VF )

(ˆnqs + 1)+

s S\pred(VF )\succ(VF )

|VF |+ (4.52) 6|VA|+

od(v)(od(v) − 1) {1 + (od(v) − 2)!}

v VF