Solutions Manual for Sensors, Circuits, and Systems for
Scientific Instruments: Back-Ends and Applications
Soumyajit Mandal
1 Chapter 1
1. Solution to Exercise 1.1
(a) Full-adder equations for conventional binary digits. Let xi , yi , ci ∈ {0, 1} denote,
respectively, the ith bits of the addends and the incoming carry (with c0 = 0). The
integer sum at position i is
xi + yi + ci ∈ {0, 1, 2, 3}.
The sum bit is the parity of the three inputs:
si ≡ (xi + yi + ci ) mod 2 = xi ⊕ yi ⊕ ci ,
because XOR computes parity. The carry-out bit equals 1 exactly when at least two of
the three inputs are 1 (the “majority” of {xi , yi , ci }):
ci+1 = (xi yi ) + (xi ci ) + (yi ci ),
where juxtaposition denotes Boolean AND and + denotes Boolean OR. One way to
see this is to expand the canonical sum-of-products form for the cases that produce an
integer sum ≥ 2:
xi + yi + ci = 2 ⇐⇒ xi yi ci + xi y i ci + xi yi ci ,
xi + yi + ci = 3 ⇐⇒ xi yi ci ,
and then absorb terms using ab + abc = ab to obtain xi yi + xi ci + yi ci .
(b) Implication for parallelism. The equations for computing si and ci+1 can be written
in propagate/generate form as follows:
Pi ≜ x i ⊕ y i , G i ≜ x i yi , ci+1 = Gi + Pi ci , s i = Pi ⊕ c i .
While Pi and Gi depend only on xi , yi and can be computed fully in parallel, ci+1
and si still depend on ci . Hence, a naive bitwise implementation (“ripple carry”) cannot
compute all si simultaneously. Carry-lookahead / prefix adders can combine the {Pk , Gk }
for k ≤ i to form ci+1 with O(log n) depth, but there is no purely per-bit constant-time
computation of ci+1 using only (xi , yi ).
(c) Redundancy of signed-digit systems when 2a > (r − 1). Digits take values in
{−a, −a + 1, . . . , a} for a radix-r signed-digit representation. If 2a > (r − 1), the allowed
digit set spans at least r + 1 consecutive integers. Therefore there exist two allowed
digits d, d′ with d′ = d ± r. For any two adjacent positions,
d · ri + e · ri+1 = (d ∓ r) ri + (e ± 1) ri+1 ,
1
, and both new digits remain in-range because d ∓ r ∈ [−a, a] by construction. Hence the
same number admits multiple digit sequences (redundancy).
Concrete example. Take r = 10, a = 5 (digits in {−5, . . . , 5}). The number 5 has two
valid signed-digit representations:
(0, 5)10 and (1, −5)10 ,
since 1 · 10 + (−5) = 5 and both 1, −5 lie in [−5, 5].
(d) Correctness of the two-pass signed-digit addition (transfer-digit) algorithm.
Given a ≤ r − 1 and 2a ≥ r + 1, define for i = 0, 1, . . . , n − 1:
+1, xi + yi ≥ a,
ti+1 = 0, −a + 1 ≤ xi + yi ≤ a − 1, wi = xi + yi − r ti+1 ,
−1, xi + yi ≤ −a,
with t0 = 0 and wn = 0. Finally set si = wi + ti for i = 0, 1, . . . , n.
Why it works. By construction ti+1 ∈ {−1, 0, 1}. Consider the three cases for xi + yi :
• If −a + 1 ≤ xi + yi ≤ a − 1, then ti+1 = 0 and wi = xi + yi ∈ [−a + 1, a − 1].
• If xi + yi ≥ a, note xi + yi ≤ 2a, so
wi = (xi + yi ) − r ∈ [ a − r, 2a − r ].
Using 2a ≥ r + 1 gives a − r ≥ 1 − a = −a + 1 and 2a − r ≤ a − 1, hence
wi ∈ [−a + 1, a − 1].
• If xi + yi ≤ −a, note xi + yi ≥ −2a, so
wi = (xi + yi ) + r ∈ [ r − 2a, r − a ].
Because r ≥ a + 1 and 2a ≥ r + 1, we have r − 2a ≥ −a + 1 and r − a ≤ a − 1, hence
again wi ∈ [−a + 1, a − 1].
Thus in all cases wi ∈ [−a + 1, a − 1]. Since ti ∈ {−1, 0, 1}, the final digit si = wi + ti
always lies in [−a, a], so the output is a valid signed-digit number. Moreover,
X
n−1 X
n−1
X
n−1 X
n X
n X
n
i i i i i
(xi + yi ) r = wi + r ti+1 r = wi r + ti r = (wi + ti )r = si r i ,
i=0 i=0 i=0 i=1 i=0 i=0
using t0 = 0 and wn = 0. Hence the algorithm returns the correct sum.
Worked example (base r = 7, a = 4) with digits in {−4, . . . , 4}:
x = (x1 , x0 ) = (3, 4), y = (y1 , y0 ) = (2, 3).
Stage 1:
i = 0 : x0 + y0 = 7 ≥ a ⇒ t1 = +1, w0 = 7 − 7 = 0,
i = 1 : x1 + y1 = 5 ≥ a ⇒ t2 = +1, w1 = 5 − 7 = −2.
Stage 2 (t0 = 0, w2 = 0):
s0 = w0 + t0 = 0, s1 = w1 + t1 = −2 + 1 = −1, s2 = w2 + t2 = 1.
Thus s = (1, −1, 0)7 which equals 1·72 −1·7+0 = 49−7 = 42, matching (3, 4)7 +(2, 3)7 =
25 + 17 = 42.
2
, Galileo's 1610 observations of Callisto
20
Observed (irregular)
15 Linear interpolation (daily grid)
Apparent position (arcmin)
10
5
0
-5
-10
-15
Jan 15 Jan 22 Jan 29 Feb 05 Feb 12 Feb 19 Feb 26 Mar 05
Date (1610)
Figure 1: Galileo’s data of Callisto from 1610.
(e) Parallelism and a signal-flow view. The algorithm naturally decomposes into two
fully parallelizable passes:
i. Local transfer and centering: For each i, compute ti+1 by comparing xi + yi to
{−a, −a + 1, a − 1, a} and compute wi = xi + yi − r ti+1 . Each (ti+1 , wi ) depends
only on (xi , yi ).
ii. Final digit formation: For each i, add the previous transfer ti to wi to obtain
si = wi + ti (with t0 = 0). This is a bank of independent adders fed by a one-step
delay of the transfer path.
An equivalent signal-flow graph therefore has, for each digit slice, a local compare-and-
correct block producing (ti+1 , wi ) from (xi , yi ), a unit-delay on the t path (so ti feeds
the next slice), and a final adder computing si = wi + ti . All slices execute concurrently;
the global ripple of binary carries is avoided because {ti } are computed from local pairs
(xi−1 , yi−1 ) in the first pass, then routed (delayed) by one position in the second pass.
2. Solution to Exercise 1.2
(a) Exploratory plot and qualitative periodicity. Convert each calendar date to “days
since Jan. 15” to obtain the time vector
t = {0, 2, 3, 7, 8, 9, 10, 11, 12, 17, 18, 19, 20, 24, 25, 26, 27, 28, 29, 31, 32, 33, 35, 37, 41, 42, 43, 44, 45}
in (days), with positions (arcmin) given in the table. A stem/line plot of position versus
date (Fig. 1) shows approximately sinusoidal motion with extrema near Jan. 17, Feb. 3,
and Feb. 19 on the positive side and Jan. 24–26 and Feb. 10–12 on the negative side.
Successive positive maxima occur about 16–17 days apart (e.g., Jan. 17 → Feb. 3 is
17 days; Feb. 3 → Feb. 19 is 16 days), so the data clearly contain a strong periodic
component with period ≈ 16.5–17 days.
(b) Why Bartlett/Welch periodograms cannot be used. Classical periodogram-based
PSD estimators (Bartlett, Welch) assume a uniformly sampled signal x[n] = x(nTs ) with
a fixed sampling interval Ts . Their FFT frequency axis and window/segment definitions
rely on this constant grid. Galileo’s record has irregular gaps (missing days), so there
3
, is no single Ts that maps the samples to integer indices n. Using a standard FFT on
such data would (i) mislabel the frequency axis, (ii) invalidate the window and overlap
structure, and (iii) introduce bias and extra leakage because the effective sampling kernel
is no longer the convolution implied by a regular grid. Hence Welch/Bartlett cannot be
applied “as is” to the raw, nonuniform samples.
(c) Linear interpolation to a uniform grid and Welch PSD. Form a daily grid from
day 0 to day 45 (inclusive), and fill the missing days by linear interpolation. Denote
the interpolated, mean-removed sequence by x[n], n = 0, . . . , 45, with sampling interval
Ts = 1 day. Estimate the PSD with Welch’s method:
1 X 1 X
K
Sbxx (f ) =
2
F{w[m] xk [m]}(f ) , U= w2 [m],
K U m
k=1
using, e.g., a Hann window w[m], 50% overlap, and a large zero-padded FFT (for repro-
ducibility we used NF F T = 4096). The most prominent spectral peak occurs at
1
fmax ≈ 0.0608 cycles/day ⇒ Tblin = ≈ 16.45 days.
fmax
(Refining the peak by a 3-point quadratic fit around the maximum gives Tblin ≈ 16.447 days.)
(d) Comparison with the accepted value. The currently accepted orbital period of
Callisto is T⋆ = 16.6890184 days. For the linear–interpolation Welch estimate,
|Tblin − T⋆ |
percent error = × 100% ≈ 1.45% .
T⋆
(e) Cubic/spline interpolation and error comparison. Repeat part (c) but fill the
missing days with a cubic (natural) spline instead of linear interpolation, then apply the
same Welch PSD procedure. The dominant peak yields
Tbcubic ≈ 16.47 days ⇒ percent error ≈ 1.32% .
On this dataset the cubic interpolation produces a slightly smaller absolute period er-
ror than linear interpolation (1.32% vs. 1.45%), because the spline better preserves the
smooth curvature between observations and reduces high-frequency interpolation arti-
facts. However, the improvement is not significant.
(f) Lomb–Scargle on the nonuniform samples. The Lomb–Scargle periodogram di-
rectly accommodates irregular sampling. For angular frequency ω = 2πf , define τ via
P
sin(2ωti )
tan 2ωτ = P i ,
i cos(2ωti )
and compute
" P 2 P 2 #
1 i yi cos ω(ti − τ ) i yi sin ω(ti − τ )
PLS (ω) = P + P .
i cos ω(ti − τ ) i sin ω(ti − τ )
2 2 2
Scanning f over a dense grid (e.g., 1/40 to 1/8 cycles/day) and taking the strongest
peak gives
TbLS ≈ 16.44 days ⇒ percent error ≈ 1.51% .
4
Scientific Instruments: Back-Ends and Applications
Soumyajit Mandal
1 Chapter 1
1. Solution to Exercise 1.1
(a) Full-adder equations for conventional binary digits. Let xi , yi , ci ∈ {0, 1} denote,
respectively, the ith bits of the addends and the incoming carry (with c0 = 0). The
integer sum at position i is
xi + yi + ci ∈ {0, 1, 2, 3}.
The sum bit is the parity of the three inputs:
si ≡ (xi + yi + ci ) mod 2 = xi ⊕ yi ⊕ ci ,
because XOR computes parity. The carry-out bit equals 1 exactly when at least two of
the three inputs are 1 (the “majority” of {xi , yi , ci }):
ci+1 = (xi yi ) + (xi ci ) + (yi ci ),
where juxtaposition denotes Boolean AND and + denotes Boolean OR. One way to
see this is to expand the canonical sum-of-products form for the cases that produce an
integer sum ≥ 2:
xi + yi + ci = 2 ⇐⇒ xi yi ci + xi y i ci + xi yi ci ,
xi + yi + ci = 3 ⇐⇒ xi yi ci ,
and then absorb terms using ab + abc = ab to obtain xi yi + xi ci + yi ci .
(b) Implication for parallelism. The equations for computing si and ci+1 can be written
in propagate/generate form as follows:
Pi ≜ x i ⊕ y i , G i ≜ x i yi , ci+1 = Gi + Pi ci , s i = Pi ⊕ c i .
While Pi and Gi depend only on xi , yi and can be computed fully in parallel, ci+1
and si still depend on ci . Hence, a naive bitwise implementation (“ripple carry”) cannot
compute all si simultaneously. Carry-lookahead / prefix adders can combine the {Pk , Gk }
for k ≤ i to form ci+1 with O(log n) depth, but there is no purely per-bit constant-time
computation of ci+1 using only (xi , yi ).
(c) Redundancy of signed-digit systems when 2a > (r − 1). Digits take values in
{−a, −a + 1, . . . , a} for a radix-r signed-digit representation. If 2a > (r − 1), the allowed
digit set spans at least r + 1 consecutive integers. Therefore there exist two allowed
digits d, d′ with d′ = d ± r. For any two adjacent positions,
d · ri + e · ri+1 = (d ∓ r) ri + (e ± 1) ri+1 ,
1
, and both new digits remain in-range because d ∓ r ∈ [−a, a] by construction. Hence the
same number admits multiple digit sequences (redundancy).
Concrete example. Take r = 10, a = 5 (digits in {−5, . . . , 5}). The number 5 has two
valid signed-digit representations:
(0, 5)10 and (1, −5)10 ,
since 1 · 10 + (−5) = 5 and both 1, −5 lie in [−5, 5].
(d) Correctness of the two-pass signed-digit addition (transfer-digit) algorithm.
Given a ≤ r − 1 and 2a ≥ r + 1, define for i = 0, 1, . . . , n − 1:
+1, xi + yi ≥ a,
ti+1 = 0, −a + 1 ≤ xi + yi ≤ a − 1, wi = xi + yi − r ti+1 ,
−1, xi + yi ≤ −a,
with t0 = 0 and wn = 0. Finally set si = wi + ti for i = 0, 1, . . . , n.
Why it works. By construction ti+1 ∈ {−1, 0, 1}. Consider the three cases for xi + yi :
• If −a + 1 ≤ xi + yi ≤ a − 1, then ti+1 = 0 and wi = xi + yi ∈ [−a + 1, a − 1].
• If xi + yi ≥ a, note xi + yi ≤ 2a, so
wi = (xi + yi ) − r ∈ [ a − r, 2a − r ].
Using 2a ≥ r + 1 gives a − r ≥ 1 − a = −a + 1 and 2a − r ≤ a − 1, hence
wi ∈ [−a + 1, a − 1].
• If xi + yi ≤ −a, note xi + yi ≥ −2a, so
wi = (xi + yi ) + r ∈ [ r − 2a, r − a ].
Because r ≥ a + 1 and 2a ≥ r + 1, we have r − 2a ≥ −a + 1 and r − a ≤ a − 1, hence
again wi ∈ [−a + 1, a − 1].
Thus in all cases wi ∈ [−a + 1, a − 1]. Since ti ∈ {−1, 0, 1}, the final digit si = wi + ti
always lies in [−a, a], so the output is a valid signed-digit number. Moreover,
X
n−1 X
n−1
X
n−1 X
n X
n X
n
i i i i i
(xi + yi ) r = wi + r ti+1 r = wi r + ti r = (wi + ti )r = si r i ,
i=0 i=0 i=0 i=1 i=0 i=0
using t0 = 0 and wn = 0. Hence the algorithm returns the correct sum.
Worked example (base r = 7, a = 4) with digits in {−4, . . . , 4}:
x = (x1 , x0 ) = (3, 4), y = (y1 , y0 ) = (2, 3).
Stage 1:
i = 0 : x0 + y0 = 7 ≥ a ⇒ t1 = +1, w0 = 7 − 7 = 0,
i = 1 : x1 + y1 = 5 ≥ a ⇒ t2 = +1, w1 = 5 − 7 = −2.
Stage 2 (t0 = 0, w2 = 0):
s0 = w0 + t0 = 0, s1 = w1 + t1 = −2 + 1 = −1, s2 = w2 + t2 = 1.
Thus s = (1, −1, 0)7 which equals 1·72 −1·7+0 = 49−7 = 42, matching (3, 4)7 +(2, 3)7 =
25 + 17 = 42.
2
, Galileo's 1610 observations of Callisto
20
Observed (irregular)
15 Linear interpolation (daily grid)
Apparent position (arcmin)
10
5
0
-5
-10
-15
Jan 15 Jan 22 Jan 29 Feb 05 Feb 12 Feb 19 Feb 26 Mar 05
Date (1610)
Figure 1: Galileo’s data of Callisto from 1610.
(e) Parallelism and a signal-flow view. The algorithm naturally decomposes into two
fully parallelizable passes:
i. Local transfer and centering: For each i, compute ti+1 by comparing xi + yi to
{−a, −a + 1, a − 1, a} and compute wi = xi + yi − r ti+1 . Each (ti+1 , wi ) depends
only on (xi , yi ).
ii. Final digit formation: For each i, add the previous transfer ti to wi to obtain
si = wi + ti (with t0 = 0). This is a bank of independent adders fed by a one-step
delay of the transfer path.
An equivalent signal-flow graph therefore has, for each digit slice, a local compare-and-
correct block producing (ti+1 , wi ) from (xi , yi ), a unit-delay on the t path (so ti feeds
the next slice), and a final adder computing si = wi + ti . All slices execute concurrently;
the global ripple of binary carries is avoided because {ti } are computed from local pairs
(xi−1 , yi−1 ) in the first pass, then routed (delayed) by one position in the second pass.
2. Solution to Exercise 1.2
(a) Exploratory plot and qualitative periodicity. Convert each calendar date to “days
since Jan. 15” to obtain the time vector
t = {0, 2, 3, 7, 8, 9, 10, 11, 12, 17, 18, 19, 20, 24, 25, 26, 27, 28, 29, 31, 32, 33, 35, 37, 41, 42, 43, 44, 45}
in (days), with positions (arcmin) given in the table. A stem/line plot of position versus
date (Fig. 1) shows approximately sinusoidal motion with extrema near Jan. 17, Feb. 3,
and Feb. 19 on the positive side and Jan. 24–26 and Feb. 10–12 on the negative side.
Successive positive maxima occur about 16–17 days apart (e.g., Jan. 17 → Feb. 3 is
17 days; Feb. 3 → Feb. 19 is 16 days), so the data clearly contain a strong periodic
component with period ≈ 16.5–17 days.
(b) Why Bartlett/Welch periodograms cannot be used. Classical periodogram-based
PSD estimators (Bartlett, Welch) assume a uniformly sampled signal x[n] = x(nTs ) with
a fixed sampling interval Ts . Their FFT frequency axis and window/segment definitions
rely on this constant grid. Galileo’s record has irregular gaps (missing days), so there
3
, is no single Ts that maps the samples to integer indices n. Using a standard FFT on
such data would (i) mislabel the frequency axis, (ii) invalidate the window and overlap
structure, and (iii) introduce bias and extra leakage because the effective sampling kernel
is no longer the convolution implied by a regular grid. Hence Welch/Bartlett cannot be
applied “as is” to the raw, nonuniform samples.
(c) Linear interpolation to a uniform grid and Welch PSD. Form a daily grid from
day 0 to day 45 (inclusive), and fill the missing days by linear interpolation. Denote
the interpolated, mean-removed sequence by x[n], n = 0, . . . , 45, with sampling interval
Ts = 1 day. Estimate the PSD with Welch’s method:
1 X 1 X
K
Sbxx (f ) =
2
F{w[m] xk [m]}(f ) , U= w2 [m],
K U m
k=1
using, e.g., a Hann window w[m], 50% overlap, and a large zero-padded FFT (for repro-
ducibility we used NF F T = 4096). The most prominent spectral peak occurs at
1
fmax ≈ 0.0608 cycles/day ⇒ Tblin = ≈ 16.45 days.
fmax
(Refining the peak by a 3-point quadratic fit around the maximum gives Tblin ≈ 16.447 days.)
(d) Comparison with the accepted value. The currently accepted orbital period of
Callisto is T⋆ = 16.6890184 days. For the linear–interpolation Welch estimate,
|Tblin − T⋆ |
percent error = × 100% ≈ 1.45% .
T⋆
(e) Cubic/spline interpolation and error comparison. Repeat part (c) but fill the
missing days with a cubic (natural) spline instead of linear interpolation, then apply the
same Welch PSD procedure. The dominant peak yields
Tbcubic ≈ 16.47 days ⇒ percent error ≈ 1.32% .
On this dataset the cubic interpolation produces a slightly smaller absolute period er-
ror than linear interpolation (1.32% vs. 1.45%), because the spline better preserves the
smooth curvature between observations and reduces high-frequency interpolation arti-
facts. However, the improvement is not significant.
(f) Lomb–Scargle on the nonuniform samples. The Lomb–Scargle periodogram di-
rectly accommodates irregular sampling. For angular frequency ω = 2πf , define τ via
P
sin(2ωti )
tan 2ωτ = P i ,
i cos(2ωti )
and compute
" P 2 P 2 #
1 i yi cos ω(ti − τ ) i yi sin ω(ti − τ )
PLS (ω) = P + P .
i cos ω(ti − τ ) i sin ω(ti − τ )
2 2 2
Scanning f over a dense grid (e.g., 1/40 to 1/8 cycles/day) and taking the strongest
peak gives
TbLS ≈ 16.44 days ⇒ percent error ≈ 1.51% .
4
