IEEE Circuits and Systems Magazine - Q1 2020 - 56

measurements is actually a very serious problem, since
it is in contrast with the ambition of CS to work as an efficient compression algorithm.
As an additional problem, saturation may actually be
observed at any time in the computation of y. Let us define the succession of values
j

y [ j] =

/ a k x k,

j = 0, 1, f, n - 1

(10)

k=0

These data are transmitted to the reconstruction algorithm instead of the corrupted measurement.
More specifically, it is reasonable to assume that the
expected value of each step a k x k is small with respect
to the integrator linearity range. In this way, the probability of a saturation event would be limited even for n
large. As a consequence, we have either
tj

/ a k x k . y -sat

k=0

with y = y[n - 1]. This is the sequence of all intermediate partial sums that lead to y. Considerations similar
to those mentioned above for y, hold also for each y[ j].
When analog hardware is the choice, the integrator computing (10) may saturate (i.e. compromising the correct
operation of the integrator in its linear region). Similarly,
in a digital architecture, the multiply-and-accumulate
block may overflow. In both cases, the outcome of the
computation (i.e., the final y) is unpredictable. Using
this value for reconstructing the input signal leads to an
error that will impair the signal reconstruction.
A workaround for this problem was first proposed in
[55] and adopted in [37] for the "analog discrete-time"
case, and can be easily extended to any other architecture. The authors added two analog comparators to
the multiply-and-integrate block with the aim of checking whether y[ j], 6j ! {0, 1, f, n - 1} is in a safe range of
linearity of the integrator block, defined by an upper
threshold y +sat and a lower one y -sat . As soon as this region is left, the time step tj is recorded along with the
fact that the threshold being reached is y +sat or y -sat .

True
Measurement

y [J ]

+
ysat

Erroneous
Measurement

y[0]

-
ysat

n-1

-1 -1 +1 -1 +1 +1 +1 -1 +1 -1 +1 -1 +1 -1 +1 +1 0 0 0 0

Time
Steps
.x = y +

sat

⊥

Corresponding a′

Figure 10. During the computation of a generic measurement
y, when the intermediate accumulated value y [ j ] leaves the
+
@, a non-linear phenomenon occurs
safe interval 6y -sat, y sat
(saturation, overflow, etc.). In this case, the final accumulated
value may be different from the expected one. Stopping the
integration at time step tj when the safe region is left is a
smart solution to get a non-erroneous measurement.
56

IEEE CIRCUITS AND SYSTEMS MAGAZINE

/ a k x k . y +sat

(11)

k=0

By introducing a sensing vector al ! R n defined as
al = [a 0, a 0, f, a tj, 0, f, 0]<
the two expressions in (11) can be written as al < x . y -sat
or al < x . y +sat, respectively, and can be used in the reconstruction algorithm to replace the erroneous y = a < x.
This approach is schematically represented in Figure 10.
The advantage of this solution with respect to the
simple approach where measurements characterized by
a saturation event are marked as invalid and not used
in the reconstruction algorithm [56] can be explained
by considering that the philosophy underlying CS is to
reconstruct the input signal with the minimum amount
of information. Accordingly, being able to recover even
a small quantity of information from saturated measurements is an advantage. The authors of [37] showed that,
using this approach, when a small ratio of measurements present saturation, it is still possible to recover
the input signal with the same quality one get when
no saturation events occur. Furthermore, they also
showed that when up to 60% of the measurements are
characterized by a saturation event, it is still possible to
reconstruct the input signal with an almost negligible
drop in performance.
E. Generation of Sensing Sequences
The generation of a appears as a straightforward operation in a CS-based system. Nevertheless, when dealing
with a practical CS systems implementation, this operation surprisingly requires appreciable care.
While in test prototypes it is commonly allowed to
externally generate and load the sensing sequences
[37], [47], any IoT CS-based not must have the elements
of a available on-chip. With respect to this, it is immediate to conclude that storing all the sensing sequences in
an internal memory is in general not an option. In fact,
referring for instance to [49] where n = 256, m = 64, and
each entry of the sensing matrix is a 6-bit quantized value, storing all different elements of all vectors a would
require 100-Kbit of dedicated memory, something that
should be avoided in the implementation of an analog
circuit. So the path to follow is the on-chip generation of
the sensing sequences.
FIRST QUARTER 2020

IEEE Circuits and Systems Magazine - Q1 2020

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q1 2020