# Connexions

You are here: Home » Content » An Introduction to Compressive Sensing » Analog-to-information conversion

### Recently Viewed

This feature requires Javascript to be enabled.

Inside Collection (Course):

# Analog-to-information conversion

Module by: Mark A. Davenport, Jason Laska. E-mail the authors

Summary: In this module we describe the random demodulator and how it can be used in the application of the theory of compressive sensing to the problem of acquiring a high-bandwidth continuous-time signal.

We now consider the application of compressive sensing (CS) to the problem of designing a system that can acquire a continuous-time signal x(t)x(t). Specifically, we would like to build an analog-to-digital converter (ADC) that avoids having to sample x(t)x(t) at its Nyquist rate when x(t)x(t) is sparse. In this context, we will assume that x(t)x(t) has some kind of sparse structure in the Fourier domain, meaning that it is still bandlimited but that much of the spectrum is empty. We will discuss the different possible signal models for mathematically capturing this structure in greater detail below. For now, the challenge is that our measurement system must be built using analog hardware. This imposes severe restrictions on the kinds of operations we can perform.

## Analog measurement model

To be more concrete, since we are dealing with a continuous-time signal x(t)x(t), we must also consider continuous-time test functions {φj(t)}j=1M{φj(t)}j=1M. We then consider a finite window of time, say t[0,T]t[0,T], and would like to collect MM measurements of the form

y [ j ] = 0 T x ( t ) φ j ( t ) d t . y [ j ] = 0 T x ( t ) φ j ( t ) d t .
(1)

Building an analog system to collect such measurements will require three main components:

1. hardware for generating the test signals φj(t)φj(t);
2. MM correlators that multiply the signal x(t)x(t) with each respective φj(t)φj(t);
3. MM integrators with a zero-valued initial state.

We could then sample and quantize the output of each of the integrators to collect the measurements y[j]y[j]. Of course, even in this somewhat idealized setting, it should be clear that what we can build in hardware will constrain our choice of φj(t)φj(t) since we cannot reliably and accurately produce (and reproduce) arbitrarily complex φj(t)φj(t) in analog hardware. Moreover, the architecture described above requires MM correlator/integrator pairs operating in parallel, which will be potentially prohibitively expensive both in dollar cost as well as costs such as size, weight, and power (SWAP).

As a result, there have been a number of efforts to design simpler architectures, chiefly by carefully designing structured φj(t)φj(t). The simplest to describe and historically earliest idea is to choose φj(t)=δ(t-tj)φj(t)=δ(t-tj), where {tj}j=1M{tj}j=1M denotes a sequence of MM locations in time at which we would like to sample the signal x(t)x(t). Typically, if the number of measurements we are acquiring is lower than the Nyquist-rate, then these locations cannot simply be uniformly spaced in the interval [0,T][0,T], but must be carefully chosen. Note that this approach simply requires a single traditional ADC with the ability to sample on a non-uniform grid, avoiding the requirement for MM parallel correlator/integrator pairs. Such non-uniform sampling systems have been studied in other contexts outside of the CS framework. For example, there exist specialized fast algorithms for the recovery of extremely large Fourier-sparse signals. The algorithm uses samples at a non-uniform sequence of locations that are highly structured, but where the initial location is chosen using a (pseudo)random seed. This literature provides guarantees similar to those available from standard CS [6], [7]. Additionally, there exist frameworks for the sampling and recovery of multi-band signals, whose Fourier transforms are mostly zero except for a few frequency bands. These schemes again use non-uniform sampling patterns based on coset sampling [1], [3], [4], [5], [10], [14]. Unfortunately, these approaches are often highly sensitive to jitter, or error in the timing of when the samples are taken.

We will consider a rather different approach, which we call the random demodulator [8], [9], [12].1 The architecture of the random demodulator is depicted in Figure 1. The analog input x(t)x(t) is correlated with a pseudorandom square pulse of ±1±1's, called the chipping sequence pc(t)pc(t), which alternates between values at a rate of NaNaHz, where NaNaHz is at least as fast as the Nyquist rate of x(t)x(t). The mixed signal is integrated over a time period 1/Ma1/Ma and sampled by a traditional integrate-and-dump back-end ADC at MaMaHz NaNaHz. In this case our measurements are given by

y [ j ] = ( j - 1 ) / M a j / M a p c ( t ) x ( t ) d t . y [ j ] = ( j - 1 ) / M a j / M a p c ( t ) x ( t ) d t .
(2)

In practice, data is processed in time blocks of period TT, and we define N=NaTN=NaT as the number of elements in the chipping sequence, and M=MaTM=MaT as the number of measurements. We will discuss the discretization of this model below, but the key observation is that the correlator and chipping sequence operate at a fast rate, while the back-end ADC operates at a low rate. In hardware it is easier to build a high-rate modulator/chipping sequence combination than a high-rate ADC [9]. In fact, many systems already use components of this front end for binary phase shift keying demodulation, as well as for other conventional communication schemes such as CDMA.

## Discrete formulation

Although the random demodulator directly acquires compressive measurements without first sampling x(t)x(t), it is equivalent to a system which first samples x(t)x(t) at its Nyquist-rate to yield a discrete-time vector xx, and then applies a matrix ΦΦ to obtain the measurements y=Φxy=Φx. To see this we let pc[n]pc[n] denote the sequence of ±1±1 used to generate the signal pc(t)pc(t), i.e., pc(t)=pc[n]pc(t)=pc[n] for t[(n-1)/Na,n/Na]t[(n-1)/Na,n/Na]. As an example, consider the first measurement, or the case of j=1j=1. In this case, t[0,1/Ma]t[0,1/Ma], so that pc(t)pc(t) is determined by pc[n]pc[n] for n=1,2,...,Na/Man=1,2,...,Na/Ma. Thus, from Equation 2 we obtain

y [ 1 ] = 0 1 / M a p c ( t ) x ( t ) d t = n = 1 N a / M a p c [ n ] ( n - 1 ) / N a n / N a x ( t ) d t . y [ 1 ] = 0 1 / M a p c ( t ) x ( t ) d t = n = 1 N a / M a p c [ n ] ( n - 1 ) / N a n / N a x ( t ) d t .
(3)

But since NaNa is the Nyquist-rate of x(t)x(t), (n-1)/Nan/Nax(t)dt(n-1)/Nan/Nax(t)dt simply calculates the average value of x(t)x(t) on the n th n th interval, yielding a sample denoted x[n]x[n]. Thus, we obtain

y [ 1 ] = n = 1 N a / M a p c [ n ] x [ n ] . y [ 1 ] = n = 1 N a / M a p c [ n ] x [ n ] .
(4)

In general, our measurement process is equivalent to multiplying the signal xx with the random sequence of ±1±1's in pc[n]pc[n] and then summing every sequential block of Na/MaNa/Ma coefficients. We can represent this as a banded matrix ΦΦ containing Na/MaNa/Ma pseudorandom ±1±1s per row. For example, with N=12N=12, M=4M=4, and T=1T=1, such a ΦΦ is expressed as

Φ = - 1 + 1 + 1 - 1 + 1 - 1 + 1 + 1 - 1 + 1 - 1 - 1 . Φ = - 1 + 1 + 1 - 1 + 1 - 1 + 1 + 1 - 1 + 1 - 1 - 1 .
(5)

In general, ΦΦ will have MM rows and each row will contain N/MN/M nonzeros. Note that matrices satisfying this structure are extremely efficient to apply, requiring only O(N)O(N) computations compared to O(MN)O(MN) in the general case. This is extremely useful during recovery.

A detailed analysis of the random demodulator in [12] studied the properties of these matrices applied to a particular signal model. Specifically, it is shown that if ΨΨ represents the N×NN×N normalized discrete Fourier transform (DFT) matrix, then the matrix ΦΨΦΨ will satisfy the restricted isometry property (RIP) with high probability, provided that

M = O K log 2 ( N / K ) , M = O K log 2 ( N / K ) ,
(6)

where the probability is taken with respect to the random choice of pc[n]pc[n]. This means that if x(t)x(t) is a periodic (or finite-length) signal such that once it is sampled it is sparse or compressible in the basis ΨΨ, then it should be possible to recover x(t)x(t) from the measurements provided by the random demodulator. Moreover, it is empirically demonstrated that combining 11 minimization with the random demodulator can recover KK-sparse (in ΨΨ) signals with

M C K log ( N / K + 1 ) M C K log ( N / K + 1 )
(7)

measurements where C1.7C1.7 [12].

Note that the signal model considered in [12] is somewhat restrictive, since even a pure tone will not yield a sparse DFT unless the frequency happens to be equal to k/Nak/Na for some integer kk. Perhaps a more realistic signal model is the multi-band signal model of [1], [3], [4], [5], [10], [14], where the signal is assumed to be bandlimited outside of KK bands each of bandwidth BB, where KBKB is much less than the total possible bandwidth. It remains unknown whether the random demodulator can be exploited to recover such signals. Moreover, there also exist other CS-inspired architectures that we have not explored in this [2], [11], [13], and this remains an active area of research. We have simply provided an overview of one of the more promising approaches in order to illustrate the potential applicability of the ideas of this course to the problem of analog-to-digital conversion.

## Footnotes

1. A correlator is also known as a “demodulator” due to its most common application: demodulating radio signals.

## References

1. Bresler, Y. and Feng, P. (1996, Sept.). Spectrum-blind minimum-rate sampling and reconstruction of 2-D multiband signals. In Proc. IEEE Int. Conf. Image Processing (ICIP). Zurich, Switzerland
2. Bajwa, W. and Haupt, J. and Raz, G. and Wright, S. and Nowak, R. (2007, Aug.). Toeplitz-structured compressed sensing matrices. In Proc. IEEE Work. Stat. Signal Processing. Madison, WI
3. Bresler, Y. (2008, Jan.). Spectrum-blind sampling and compressive sensing for continuous-index signals. In Proc. Work. Inform. Theory and Applications (ITA). San Diego, CA
4. Feng, P. and Bresler, Y. (1996, May). Spectrum-blind minimum-rate sampling and reconstruction of multiband signals. In Proc. IEEE Int. Conf. Acoust., Speech, and Signal Processing (ICASSP). Atlanta, GA
5. Feng, P. (1997, Mar.). Universal spectrum blind minimum rate sampling and reconstruction of multiband signals. Ph. D. Thesis. University of Illinois at Urbana-Champaign.
6. Gilbert, A. and Guha, S. and Indyk, P. and Muthukrishnan, S. and Strauss, M. (2002, May). Near-Optimal Sparse Fourier Representations via Sampling. In Proc. ACM Symp. Theory of Comput. Montreal, Canada
7. Gilbert, A. and Muthukrishnan, S. and Strauss, M. (2005, Aug.). Improved time bounds for near-optimal sparse Fourier representations. In Proc. SPIE Optics Photonics: Wavelets. San Diego, CA
8. Kirolos, S. and Laska, J. and Wakin, M. and Duarte, M. and Baron, D. and Ragheb, T. and Massoud, Y. and Baraniuk, R. (2006, Oct.). Analog-to-Information Conversion via Random Demodulation. In Proc. IEEE Dallas Circuits and Systems Work. (DCAS). Dallas, TX
9. Laska, J. and Kirolos, S. and Duarte, M. and Ragheb, T. and Baraniuk, R. and Massoud, Y. (2007, May). Theory and Implementation of an Analog-to-Information Convertor Using Random Demodulation. In Proc. IEEE Int. Symposium on Circuits and Systems (ISCAS). New Orleans, LA
10. Mishali, M. and Eldar, Y. C. (2009). Blind multi-band signal reconstruction: Compressed sensing for analog signals. IEEE Trans. Signal Processing, 57(3), 993–1009.
11. Romberg, J. (2009). Compressive sensing by random convolution. SIAM J. Imag. Sci., 2(4), 1098–1128.
12. Tropp, J. and Laska, J. and Duarte, M. and Romberg, J. and Baraniuk, R. (2010). Beyond Nyquist: Efficient sampling of sparse, bandlimited signals. IEEE Trans. Inform. Theory, 56(1), 520–544.
13. Tropp, J. and Wakin, M. and Duarte, M. and Baron, D. and Baraniuk, R. (2006, May). Random filters for compressive sampling and reconstruction. In Proc. IEEE Int. Conf. Acoust., Speech, and Signal Processing (ICASSP). Toulouse, France
14. Venkataramani, R. and Bresler, Y. (1998, Oct.). Further results on spectrum blind sampling of 2-D signals. In Proc. IEEE Int. Conf. Image Processing (ICIP). Chicago, IL

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

#### Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

#### Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks