ULTRA-WIDEBAND SIGNAL DETECTION AND PULSE POSITION MODULATION

Field

The present technology relates to a signal detection approach with noise and/or interference suppression for ultra wide band (UWB) systems. More specifically, it relates to an overcomplete dictionary signal representation and a sparsity-driven optimization algorithm. The technology also relates to a method of pulse shaping for pulse position modulation (PPM) for Ultra-Wideband (UWB) systems. More specifically, it is for use with sparsity-driven signal detection using a computer algorithm.

Background

In wireless communications, electromagnetic waves with an instantaneous bandwidth greater than 25% of the center operating frequency or an absolute bandwidth of 1.5 GHz or more are referred to as Ultra-Wideband (UWB) signals [1][2][3]. The basic concept of UWB communication is to transmit extremely short duration bursts of radio frequency (RF) energy or utilize multi-carrier modulation such as orthogonal frequency-division multiplexing (OFDM) to implement high data rate transmission. Therefore reliable and efficient detection of UWB signals is important for good performance. Currently, most detection methods are derived from matched filter based correlation detection theory [4]. These techniques were originally designed for the optimum detection of single-carrier based narrow band modulated signals, so better performance can be expected if the detector is designed considering UWB signal characteristics.

Recently, overcomplete dictionary based sparse representation of signals has been widely studied because of its potential to efficiently describe a linear mixture of multiple signals with diverse characteristics [5] [6] [7]. The overcomplete dictionary is composed of more than one basis so that different components of the received signal can be represented in an appropriate basis to achieve overall description sparsity [8]. Even though the sparsest description, i.e. the solution with the fewest nonzero elements, is generally hard to obtain, it is relatively easy to locate a sparse enough representation by solving sparsity-driven optimization problems [9]. Numerous applications of sparse signal representation in data compression, image denoising and blind signal separation (BSS) have been proposed [1O][I l]. However, UWB signal detection based on sparse representation of signals has yet to be examined.

Traditional detection of wireless signals cannot employ the sparse representation method because of the time continuous, relatively slow changing characteristics of most of modulated signals such as phase shift keying (PSK). Conversely for impulse radio, the transmitted signal is generally carrier-free and with low duty cycle, i.e., its time-domain representation is sparse. Noise presents another difficulty.

US 6,834,073 discloses a system, method, and computer program product for baseband removal of narrowband interference contained within UWB signals in a UWB receiver. The RFI is extracted from the UWB signal by employing a filter that is matched approximately with the RFI in the baseband signal, extracting RFI, and passing the desired data signal unscathed. The invention does not provide for signal detection.

US 6,611 ,223 discloses a method and apparatus for detecting ultra wide-band (UWB) signals using multiple detectors having dynamic transfer characteristics. A receiver circuit is

implemented using devices such as op-amps to provide the required dynamic characteristics. The detectors used in the UWB communication systems utilize direct sequence spread spectrum (DSSS) technology for multiple access reception. A method for noise reduction is not provided.

US 6,122,334 discloses apparatus for a wireless communication device, which provides fast detection and validation of pilot signals while minimizing the probability of false detection. In the apparatus a searcher subsystem generates a pilot energy sample corresponding to a pilot signal, which is provided to a pilot signal detection filter, comprising two parallel branches. The first branch calculates a weighted historical average of a signal strength of the pilot signal in response to the pilot energy sample, the second branch verifies the pilot energy sample in a state machine, wherein transitions of the state machine are proportional to a magnitude of the pilot energy sample. A pilot detection signal is generated if either the weighted historical average exceeds selected threshold, or a state of the state machine exceeds a maximum value of the states. This invention cannot be applied to signals other than pilot signals.

US 6,456,221 discloses methods and apparatus for detecting ultra wide-band signals using circuitry having nonlinear dynamics characteristics. The receiver circuit can be implemented using a simple tunnel diode or using an op-amp to provide dynamic characteristics. The detector can be used in a variety of modulation schemes, including but not limited to an ON-OFF keying scheme, an M-ary pulse position modulation scheme, and a pulse width modulation scheme. The approach requires only a single frame to detect the signal. The goal of the invention is to amplify signals, and therefore, it does not include detection and denoising.

Recent efforts on pulse shaping are mainly focused on generating UWB pulses that are able to achieve maximum spectral utilization, or equivalently, possess the largest power under the constraints imposed by the federal communication commission (FCC) emission mask[10] [1 1]. Moreover, it is required that the power spectrum of the designed pulse is in compliance with the strict FCC emission mask.

It is an object of the present invention to overcome the deficiencies in the prior art.

Summary

The present technology provides a signal detection method with noise suppression based on sparse signal representation. The optimal pulse shape for the sparsity-driven detection is quite different from most of the current work, because of the inherent difference in the principles of the detectors. For PPM UWB systems employing the sparsity-driven detection method, the desired pulse shapes would be most dissimilar to the received interference and/or noise (such as additive white Gaussian noise (AWGN)), so that the information-carrying signal can be better extracted out of the received signal by the sparse signal representation algorithm. General guidelines to generate the necessary overcomplete dictionaries for different information carrying signal constructions and noise are also provided.

In one embodiment, a method, comprising:

selecting a dictionary of words representing a communication signal degradation; and

representing a pulse waveform as a combination of words of the dictionary; and

selecting a preferred pulse waveform as the combination of words having a vector norm that is substantially a maximum is provided.

In one aspect, the method further comprises selecting the preferred pulse waveform so that a

power spectral density associated with the preferred pulse waveform does not exceed predetermined values associated with a mask.

In another aspect, the mask is an FCC mask.

In another aspect of any of the foregoing aspects of the method, the communication signal degradation is noise.

In another aspect of any of the foregoing aspects of the method, the communication signal degradation is additive white Gaussian noise.

In another aspect of any of the foregoing aspects of the method, the words of the dictionary correspond to columns of a Hadamard- Walsh matrix.

In another embodiment, a method of selecting a pulse waveform for a communication system is provided, comprising:

representing noise in a received signal as a linear combination of columns of a Hadamard-Walsh matrix;

substantially maximizing | | y I h , wherein y is a vector corresponding to a pulse

representation based on the columns of the Hadamard-Walsh matrix; and

selecting a pulse waveform based on the maximization.

In one aspect of the method, the selected pulse waveform has a power spectral density that is less than a predetermined mask.

In another aspect of any of the foregoing aspects of the method, the method further comprises selecting a size of the pulse representation.

In another aspect of any of the foregoing aspects of the method, substantially maximizing

M- I

H y Hi corresponds to maximizing a ^ _/ ^χ tanh(α xy,-) , wherein ^ represent pulse coefficients

/=o corresponding to columns of the Hadamard-Walsh matrix, i is an integer, M is a number of

columns of the Hadamard- Walsh matrix, and a is a real number greater than about 100.

In another aspect of the method, the predetermined mask is an FCC mask.

In another aspect of the invention, a computer readable medium is provided, comprising computer-executable instructions for performing the method of any of the aspects of the method of the invention.

In another embodiment, a transmitter is provided comprising:

a memory configured to store a representation of channel noise and a representation of an associated preferred pulse;

a signal processor configured to receive data for transmission, and encode the data based on the representation of the preferred pulse.

In one aspect of the transmitter, the memory is configured to store a plurality of representations of channel noise and a corresponding plurality of representations of an associated preferred pulse.

In another aspect, the transmitter further comprises a noise processor configured to establish a representation of channel noise based on detected noise, and a pulse selector configured to identify a pulse representation associated with the channel noise representation established by the noise processor.

In another aspect of any of the foregoing aspects of the transmitter, the transmitter further comprises an output configured to communicate an identification of the pulse representation used by the signal processor for data encoding to a receiver.

In another aspect of any of the foregoing aspects of the transmitter, the transmitter further comprises an input configured to receive an identification of a pulse representation.

In another aspect of any of the foregoing aspects of the transmitter the memory is configured to store a frequency mask associated with a transmitted pulse.

In another embodiment a receiver is provided, comprising:

a memory configured to store a representation of channel noise and a representation of an associated preferred pulse;

an input configured to receive an identification of a pulse representation and a noise representation; and

a signal processor configured to extract data from a received signal based on the representations.

Another aspect of the technology is a method of pulse shaping for pulse position modulation (PPM) Ultra-Wideband (UWB) systems. With the help of the recent development of sparse signal representation based on overcomplete dictionaries [6][7][9], a new sparsity-driven detection method has been proposed in [1] as an efficient way for detecting pulse position modulation (PPM) UWB signals. In particular, through properly constructing the overcomplete dictionary, the novel detection algorithm is capable of achieving excellent PPM UWB signal detection performance.

In one embodiment, an ultra- wideband (UWB) communication receiver is provided, comprising: a sampler configured to receive an incoming communication signal and produce a sampled signal; a signal processor configured to obtain a preferred representation of the sampled signal based on an overcomplete dictionary. In one aspect, the overcomplete dictionary comprises a plurality of words, and further comprising a memory configured to store the plurality of words.

In another aspect of either of the foregoing aspects of the method of pulse shaping, the overcomplete dictionary comprises a plurality of words, and the signal processor is configured to generate the plurality of words.

In another aspect of any of the foregoing aspects of the method of pulse shaping, the overcomplete dictionary comprises a plurality of words associated with noise.

In another aspect of any of the foregoing aspects of the method of pulse shaping, the overcomplete dictionary comprises a plurality of words further associated with additive Gaussian white noise.

In another aspect of any of the foregoing aspects of the method of pulse shaping, the overcomplete dictionary comprises a signal sub-dictionary and a noise sub-dictionary.

In another aspect of any of the foregoing aspects of the method of pulse shaping the overcomplete dictionary further comprises an interference sub-dictionary.

In another aspect of any of the foregoing aspects of the method of pulse shaping the receiver further comprises a channel characterization unit configured to produce a channel characterization and select at least some words of the overcomplete dictionary based on the characterization.

In another aspect of any of the foregoing aspects of the method of pulse shaping, the signal processor is configured to produce the preferred representation based on a vector norm of at least one estimated representation.

In another aspect of any of the foregoing aspects of the method of pulse shaping, the preferred representation is selected based on a minimization of the vector norm of at least one estimated representation.

In another embodiment a communication method is provided, comprising: evaluating a received communication signal, comprising an information signal and a

noise signal, based on an overcomplete dictionary; selecting at least one word of the overcomplete dictionary as a representation of the received communication signal; and extracting data from the received communication signal based on the selection of at least one word.

In one aspect of the communication method, the overcomplete dictionary comprises a sub-dictionary associated with noise.

In another aspect of either of the foregoing communication methods, the overcomplete dictionary is defined as a plurality of words, wherein the words are associated with columns of an identity matrix and columns of a Hadamard matrix.

In one aspect of any of the foregoing aspects of the communication method, the overcomplete dictionary includes sub-dictionaries that include words associated with information signals and words associated with noise-like signals, respectively. In one aspect of any of the foregoing aspects of the communication method, the method further comprises establishing a representation of the received signal based on the words associated with information signals and words associated with noise-like signals, further comprising selecting a clipping threshold, and clipping the representation of the received signal based on the clipping threshold, wherein the extracted data is based on the clipped representation of the received signal. In another aspect of any of the foregoing aspects of the communication method, the information signal is a pulse-like signal.

In one aspect of any of the foregoing aspects of the communication method the step of selecting the at least one word of the overcomplete dictionary as a representation of the received communication signal is based on a minimization of a vector norm of a representation of the received communication signal in the overcomplete dictionary.

In another embodiment, a method of extracting data from a sampled pulse-position modulation communication signal is provided, comprising: selecting an overcomplete dictionary including a plurality of words associated with pulse positions; minimizing a vector norm of a representation of the sampled communication signal in an overcomplete dictionary to obtain a preferred representation of the sampled signal in the overcomplete dictionary; and extracting data from the sampled communication signal based on a word associated with a pulse position having a largest contribution to the preferred representation of the sampled signal.

In one aspect, the method of extracting data further comprises representing the overcomplete dictionary as a dictionary matrix so that words of the overcomplete dictionary are associated with columns of the dictionary matrix.

In another aspect of the method, a plurality of words are associated with noise or interference, or both.

In another embodiment, a computer readable medium is provided, containing computer-executable instructions for performing the foregoing methods.

Brief Description of the Drawings

Fig. 1. A prior art figure of a UWB pulse with and without additive white Gaussian noise

(AWGN).

Fig. 2. A UWB signal with AWGN noise before and after denoising and clipping in accordance with the invention.

Fig. 3. UWB 2-ary pulse position modulation( PPM) sequence dictionary in accordance with the invention.

Fig. 4. UWB signal detection with single pulse and pulse sequence UWB dictionaries in accordance with the invention.

Fig. 5. Yi, Yn and γ _G for a PPM UWB signal with AWGN noise in accordance with the

invention. Fig. 6. UWB signal detection with AWGN noise included in the dictionary in accordance with the invention.

Fig. 7. UWB signal detection with AWGN noise included in the dictionary in accordance with the invention.

Fig. 8 illustrates a representative data extraction method based on signal representations in an overcomplete dictionary.

Fig. 9 is a schematic diagram of a representative UWB receiver that processes received signals based on an overcomplete dictionary.

Fig. 10. Approximation of the signum function with time-scaled hyperbolic tangent function in accordance with the invention. Fig.l 1. The pulse shape of the optimal UWB pulse in accordance with the invention.

Fig. 12. The power spectrum density of the optimal UWB pulse and the modified FCC indoor emission mask.

Fig. 13 is a schematic diagram of a transmitter based on the disclosed methods.

Detailed Description of PPM UWB Systems

Sparse Representation of UWB Signals

In this section we describe PPM UWB systems with impulse radio transmission, and show that the transmitted signals can be represented by sparse vectors.

A PPM LJWB signal over an AWGN channel can be expressed as [12]

¥ /V ₁ - I

-V(O = a a A _P {t - JT ₁ - b,d) + _W {t), (l )

/= - ¥ / = 0 where A is the signal amplitude, p(t) represents the transmitted impulse waveform that

nominally begins at time zero, and Tf is the frame time. The sequence b, is the information

stream generated by the data source, dis an additional time shift utilized by the pulse position modulation, and w(V) is AWGN noise with power spectral density N ₀ / 2 . If N _s > 1 a

repetition code is introduced, i.e. N^ pulses are used for the transmission of the same

information symbol. For simplicity, we ignore the spreading factor, as it will not affect the proposed denoising and detection approach.

In the absence of multipath fading and assuming that there is only one active user, the sampled received signal with sampling intervalT, , denoted byr[« ], can be modeled as

r[n ] = s[n ] + λv[ti ]

¥ JV ₄ - I ₍₂ )

= a a ^A P( ^nT _s - i ^τ _f - b,d) + w[ni ι= - ¥ / = 0

where s[n ] is the discrete-time UWB pulse sequence, and w[n ] is AWGN with power spectral

density N ₀ / 2.

In practical UWB systems, Tf is typically a hundred to a thousand times the impulse width

[4], thus the transmitted UWB pulse sequence s[n ] has a low duty cycle and is highly sparse in

the time-domain, i.e. a large portion of the s[n ] are zeros. As an example, assuming that /?(/)

is the second derivative of the Gaussian pulse function with pulse width 0.5 ns, A = 1 , Tf = 2.5 ns, d = 0.2 ns and T _s = 0.1 ns, the sampled transmitted signal frame for a T bit

is plotted in Fig. 1 (a). The time-domain sparsity of the transmitted signal for other UWB pulses can easily be shown.

Conversely, the received signal r[n] is not sparse in either the time domain or frequency

domain because of the AWGN noise, which motivates using sparsity-driven algorithms for UWB pulse denoising and detection. As an example, for the PPM UWB system described in the last paragraph, suppose that the signal to noise ratio is 0 dB. Then the sampled received signal frame for the T bit is plotted in Fig. l(b). Comparing Fig. l (a) with Fig. l(b), it is obvious that the existence of the continuously time varying AWGN destroys the time-domain sparsity of the received PPM UWB pulse signal. In the following, the overcomplete dictionary design guidelines are based on PPM UWB for clarity. However, this method is also applicable to multi-carrier modulation such as OFDM, as will be illustrated by an example.

Signal Representation Using Overcomplete Dictionaries

In the field of signal representation, a dictionary is defined as a matrix D a R" ^k , in which the columns are prototype signal-atoms d^ , where 0 £ k £ K - 1 , and k is commonly

referred to as the size of the dictionary. The signal y(t) can be represented by a finite-length

discrete-time sample sequence^[n], where 0 £ n < N

where N is the dimension of y and T denotes matrix transpose. For convenience, atoms of an

overcomplete dictionary are also referred to herein as words.

If y is decomposed exactly we have

K y = Dx = & a.d,, (4) k= \ and if y is decomposed approximately we have

y ; Dx = a M*, (5) l

where| | y - Dx | | ₂ £ 6, ό is the approximation error tolerance [13], a _k is the k th element of x,

and I l . || ₂ is the I ₂ norm. If the dictionary used to represent the signal contains at least one

signal basis, it is called an overcomplete dictionary [14]. Depending on the characteristics of the d^ , i.e. the dictionary, a signal can be represented as a linear combination of spikes,

sinusoids, chirps, etc.

As opposed to traditional orthonormal signal representations, such as the sinusoidal function dictionary based on the Fourier transform, where the decomposition is unique, the overcomplete dictionary contains more than enough atoms so that a number of different signal decompositions are possible. More importantly, for a signal that is a superposition of multiple phenomena with different characteristics, an overcomplete dictionary makes it possible to

represent the signal with high efficiency, i.e. with x having few nonzero elements. Conversely, it is hard, if not impossible, to achieve the same goal with a complete dictionary [8]. This can be explained intuitively by the fact that with overcomplete dictionaries, we can represent different phenomena by atoms that may not exist or coexist in a single complete basis dictionary, and hence the solution x will be more sparse. Considering PPM UWB systems, we can expect that a sparse signal representation using an overcomplete dictionary is able to separate the spike-like UWB pulses from the AWGN, i.e. the time-domain sparsity of the UWB pulses can be reconstructed. Mathematically, the sparsest signal representation is the solution of the problem given by

min | | x | | ₀ subject to y = Dx (6)

or min I l x || ₀ subject to | | y - Dx | | ₂ < ό (7)

.V where | | . | | ₀ is the / ₀ norm, counting the nonzero entries of a vector.

Generally speaking, searching for a sparse representation with a given overcomplete

dictionary is a combinatorial programming problem with complexity that grows exponentially with the size of the dictionary K [5]. However, it has been shown that if there exists a sparse enough representation of a signal, it can be located via solving the / _/; norm minimization

problem, where 0 < p £ 1 [15]. In other words, / _/; minimization is inherently sparsity-driven.

Among all available algorithms, the h norm minimization is of particular interest because it can be solved by convex linear or quadratic programming algorithms with low complexity. Mathematically, we approximate the solutions of (6) and (7) by solving

min I l x \ \ _\ subject to y = Dx (8) r or min I l x I !, subject to | | y - Dx | | ₂ < ό, (9)

T respectively. Equations (8) and (9) are also known as the basis pursuit algorithm [13]. The quantity min 11 x 11| can be referred to as a vector norm of x.

Since the satisfactory performance of (9) relies on accurate information about the power spectral density N ₀ 1 2 , which is not easy to obtain in practice [16], in this paper we consider

solving (8). Note that previously proposed denoising methods [17] have considered (9). For the proposed approach, the overcomplete dictionaries for PPM UWB system are constructed to include atoms for a pulse-like signals and noise-like signals, where AWGN is considered as a distinct portion of the signal that must be extracted. The elements of the signal and dictionary are real and as such, Iy norm minimization becomes a linear programming problem, which can

be solved with low complexity via the Simplex method or Interior Point method [18].

Example 1. PPM UWB Signal Denoising

We consider the received PPM UWB signals as the superposition of a series of spike-like UWB pulses and AWGN. To denoise the received signal by a sparse signal representation

method, the overcomplete dictionary should be composed of atoms with the characteristics of the signals. Considering that PPM UWB signals are impulse-like and AWGN has many zero-crossings, we propose the following dictionary

D^ = I Hjj (10)

where I is the N ' N identity matrix, and H is an N ' N Hadamard-Walsh (HW) matrix which can be generated recursively as

p- H _{N / 2} + H _{N I 2} o

^{HN =} ϊ I+ ⁺ 'H ¹ N / 2 " " HN / 2 i(3 ^{(1 1)}

with H i = 1 . N is the length of the received signal vector, which should be large enough so

that y contains at least one pulse.

Examining O _N , we see that the columns of I serve as a basis for the components of the

signal, while the columns of H are used to extract the non-impulsive components of the AWGN noise from the received signal. If we solve (8) with dictionary D^ and y as the

sampled received PPM UWB signal, we obtain the solution

x = L v (12)

where y = D^x = Iy ₁ + Hy ₁₁ , (13)

γ, will contain the information-carrying PPM UWB pulses together with residual noise (the

spike-like components of the noise).

We can use clipping to further suppress the noise inγ _r . Specifically, we compare the value

of each signal sample with a fixed amplitude threshold^, _/ , . Those samples with an amplitude

smaller than A _th are set to zero while the others are left unchanged. The threshold can be

determined by comparing the average pulse power (amplitude) and the residual noise power.

In Fig. 2, we show the performance of the proposed approach. We assume that y contains five pulses, with the other parameters the same as those used in generating Fig. 1. Fig. 2(a) depicts the PPM UWB signal corrupted by AWGN noise. Fig. 2(b) shows the denoised signal contained in Y ₁ . It can be seen that the PPM UWB pulses in the received signal are extracted

while the noise is significantly reduced. Fig. 2(c) is the output after clipping with.4 _//; = 0.25 ,

which shows that with denoising and clipping, most of the noise can be eliminated.

Note that the above approach cannot detect the signal directly so that correlation is still required to detect the denoised PPM UWB. In the next section, we propose a novel approach to overcomplete dictionary construction, where the UWB pulses are directly included as dictionary atoms so that the denoising and detection of PPM UWB signals can be completed in a single step.

Example 2. Joint Denoising and Detection of PPM UWB Signals

In the last section, γι described the pulse waveforms, instead of the values associated with

the information bits, i.e. the position information of the pulses. Moreover, using spikes to represent the UWB pulses is not the most effective choice, because more than one spike is required to represent each pulse. Therefore, we need atoms that better match the PPM UWB pulse sequence with pulse position information.

To achieve this goal, we construct an overcomplete dictionary which includes the transmitted PPM UWB pulses, O _ND , and is given by

This dictionary consists of three parts, the identity matrix I to describe the spikes in the noise, the Hadamard Walsh matrix H to represent the non-impulsive portion of the noise, and

G to extract the UWB pulses for signal detection. In this case, we denote the solution of (8) as

where y = D _ND x = Iy ₁ + Hy ₁ , + Gγ _G . (16)

There are two approaches to design G , namely, single pulse signal design and multiple pulse or pulse sequence design. Assume that there are M pulses iny . i.e., N = MTf I T _s .

Because each pulse can only take two possible positions, with perfect synchronization, the

sampled / th PPM UWB pulse contained in y must be one of the N ^' 1 vectors P ₍ , _>0) and P ₍ , _n ,

in which the k th entry is given by p{kT _s - iTf) and p(kT _s - iT _f - d) , 0 £ k < N ,

respectively. With single pulse signal design, G is defined as an N ' 2M matrix given by

G = [P(CO)' P(O.!) _' P( 1, 0) _' K , P(A/- 1,1) ]- (1 7)

We observe that G contains the two locations of each pulse iny . The detection of each

information bit can be achieved by comparing the two corresponding coefficients inγ _(; . With

pulse sequence design, G is an N ' 2 ^λ/ matrix in which the / th column G _j , 0 £ / < 2 ^M is

given by

M - 1

subject to /?(/, /) a OJ and / = a ^2'biiJ) .

Note that G includes all possible M -pulse sequences. Clearly, the index of each atom in G is directly associated with theM information bits embedded iny . The detection can be

performed by searching for the largest coefficient in γ _G . Fig. 3 shows a design example for a

2-ary pulse sequence, where M = 2 and the other parameters are the same as those used to obtain Fig. 1.

Using O _Nn and /, norm minimization, the PPM UWB pulses will be represented by the

atoms in G instead of those in I , if the sampling interval is small enough so that there are at least two samples for each pulse. This is made clear by the fact that no matter which design approach is used to construct G , the selection of an atom in G is equivalent to choosing at least two atoms of I . Therefore, the sparsity-driven Jy norm minimization tends to select the

atoms in G in order to reduce the number of nonzero coefficients in the solution x .

One may think that with the introduction of G , I can be eliminated to reduce the computational load. However, without I , the spike-like residual noise (similar to the PPM UWB pulses), as seen in Fig. l (b), can cause undesirable nonzero elements in γ _(; leading to

detection errors. Therefore, the inclusion of I will improve performance.

In Fig. 4, we plot the performance with joint denoising and detection of UWB signals. Fig. 4(a) is the received PPM UWB signal over an AWGN channel, Fig. 4(b) is the output after pulse sequence detection, and Fig. 4(c) is the output after detection of just single pulses. The performance with pulse sequence detection is better than with single pulse detection, since the pulse sequence detection can only chose from a certain set of signal patterns. This rules out the possibility that an interfering spike falls into an impossible time location and be detected as an UWB pulse. Fig. 5 shows the corresponding elements of x . In this figure we can see the decomposition of the noise into spike-like components (corresponding to γ ₍ ), and

non-impulsive components (corresponding to γ _H ). The largest component corresponding to

γ _f; denotes the detected signal sequence. Note the smaller amplitude spikes correspond to an

incorrect symbol sequence.

Example 3. Joint Denoising and Detection of Multi-band OFDM UWB Signals

The present method can also be applied to multi-band orthogonal frequency-division multiplexing (OFDM) UWB systems such as that proposed in [19] for the UWB wireless personal area networks (WPAN). Only moderate modification of the overcomplete dictionary is required, as we will briefly illustrate here. The proposed OFDM UWB system has multiple sub-bands, each of which employs a normal OFDM signal with QPSK modulation. As pointed out in [20], in a normal OFDM system, with careful selection of the cyclic prefix (CP) for each OFDM symbol, the received baseband signal y after removing the CP is given by

y = HF ^' 'b + n (19)

where H is the circulant channel matrix determined by the impulse response of the wireless

channel, the receiver filter and the pulse-shaping filter at the transmitter, F ¹ is the IFFT matrix,

b = [b _o ,b _l ,...,h _N _ _] ]' is the transmitted symbol block, and « is band-pass Gaussian noise. The

receiver then performs an FFT on y to obtain

z = FHF 'b + Fn = Db + n (20)

where F denotes the FFT matrix. It is obvious that D is a diagonal matrix, since FF ^"1 = I . As we can see from (20), the FFT output is simply a scaled and additive-noise-corrupted version of the transmitted symbols. Therefore, the detection of the transmitted symbols from z , as well as denoising the FFT output z , can be achieved jointly by using the following over-complete dictionary

D = [H,G _QPSK ] (21)

where H is the Hadamard Walsh matrix for representing the noise, and G _OI , _KK is a dictionary

that contains all possible combinations of QPSK symbols for the sub-carriers under

consideration. Note that the number of symbols N can be large so that processing z in sub-groups and denoi sing/detecting each sub-group separately may be necessary, depending on the specific system configurations.

Dictionary Construction for Noise or Interference

The denoising and detection approach for AWGN corrupted PPM UWB signals studied in section V can be adapted to fit other sets of noise and interference. In this case, the overcomplete dictionary D for sparse representation of the signal and noise should be designed with a signal-like sub-dictionary and a noise-like sub-dictionary. However, not all noise can be easily expressed in a simple way, i.e., with a simple set of dictionary atoms. In this case, we can use noise samples as dictionary atoms. As long as the number of samples is sufficiently large, good performance can be obtained. Depending on the type of noise and/or interference, and the detection requirements, the dictionary can take the forms

or

or

D = «H W G j (24)

where W , Wj and W ₂ are the sub-dictionaries constructed from different noise samples. In

the different dictionary structures listed above, (19) is for the case when there is one or more sources of interference, (20) is for the case when there are spike-like components in both the interference and signals, and (21) can be used when both the signal and interference have non-impulsive components.

In Fig. 6 we give an example of signal-noise dictionary based detection. The noise is

AWGN. The dictionary employed is of the form [I W G] , and SNR = OdB. The

performance is comparable to that using O _ND , and the computational complexity is the same.

In Fig. 7 we present an example with a dictionary of the form[W| W ₂ K G]. The

noise is AWGN with SNR = -3dB, and we there are two single frequency sinusoidal interference signals at 800 MHz and 1800 MHz, with signal to interference ratios of SIR = OdB. The UWB data rate is 10 GHz. For detection, we use the dictionary

where P, ₎₍₇ is a Discrete Cosine Transform (DCT) matrix to decompose the interference. In

Fig. 7(a), the UWB signal is embedded in noise and interference, but pulse sequence dictionary detection is able to recover the signal, as shown in Fig. 7(b). In Fig. 7(c) we show the decomposition of the received signals, specifically, in γ _G the large spike denotes the correct

sequence, and the two smaller spikes denote incorrect sequences.

A representative method is illustrated in Fig. 8. In a step 802, an overcomplete dictionary is specified based on, for example, communication channel noise (such as AWGN or other noise) or interference signals. Typically, the dictionary includes contributions such as I, G, W, P _DCT as described above. In a step 804, a communication signal is received and sampled and in a step 806, the sampled signal is preprocessed by for example, clipping or filtering. In a step 808. the sampled signal is processed based on the specified overcomplete dictionary. Typically, the sampled signal is processed to determine a selected approximation of the sampled signal based on the words of the overcomplete dictionary. In some examples, this processing produces an estimate of contributions of information carrying words of the overcomplete dictionary to the sampled signal. For example, the processing can produce an estimate of the parameter γ _(; ,

wherein the subscript G refers to words associated with UWB pulses as in Example 2 above, or

7ι , wherein the subscript I refers to words associated with impulse-like signal (and noise)

contributions as in Example 1 above. In a step 810, a preferred word of the dictionary is selected, typically the word associated with a largest component of the parameter γ that is

associated with information carrying words. In some examples, the preferred word corresponds directly to the detected signal sequence while in other examples subsequent processing such as, for example, correlation, is needed to extract a signal sequence. As shown in Fig. 8, data is extracted in a step 812 based on the preferred word.

A portion of a representative UWB communication system is illustrated in Fig. 9. A sampler 902 is coupled to receive an input signal, and produce a sampled signal that is delivered to a signal processor 904. The signal processor 904 can be configured to clip, filter, or otherwise enhance or conform the sampled signal. The signal processor 904 is coupled to a dictionary generator 906 that is configured to generate or store an overcomplete dictionary, or otherwise obtain an overcomplete dictionary. As shown in Fig. 9, the dictionary generator 906 is coupled to a channel characterization unit 908 that is configured to determine, for example, noise or interference contributions. Based on such characterizations, the dictionary generator 906 can obtain one or more additional overcomplete dictionaries for use by the signal processor 904, or can select which of one or more dictionaries stored in memory 910 is to be used. The signal processor 904 can be configured to provide an identification of a preferred word that is associated with the received signal, and based on the received word, the signal data can be extracted.

Overview

We first quantify the dissimilarity between a UWB pulse and AWGN. Then, taking the FCC emission mask into consideration, we formulate an optimization problem for optimally shaping

the discrete-time UWB waveform. We relax the objective function of the original pulse shaping problem to make it mathematically more tractable through incorporation of the hyperbolic tangent function. The relaxed version can be solved with classic nonlinear programming algorithms, such as sequential quadratic programming (SQP). Design examples are provided to illustrate the pulse shape, its dissimilarity to the AWGN and its power spectrum.

Signal Model

A. PPM UWB Signals

A general expression of the sampled PPM UWB signal received over an AWGN channel with sampling interval T _s is given by

¥ λ\ - 1

φ l = a a Ap(nT _s - JTf - c _(lj φ _c - b,d) + w[n l (26)

(= - ¥ /= 0

where w[n ] is the AWGN with power spectral density (PSD)N ₀ / 2 , A is the pulse amplitude,

and p(l) represents the transmitted impulse waveform. The sequence b, is the information

data stream, Jis an additional time shift utilized by the pulse position modulation, and N _s

denotes the length of the repetition code. Tf is the frame time, which is typically a hundred to

a thousand times the impulse width resulting in a signal with very low duty cycle [4]. Therefore, the noiseless UWB pulse sequence is highly sparse in the time domain, i.e. a large portion of the transmitted signal are zeros. However, this time-domain sparsity is not possessed in the received signal r[n] , due to the appearance of the 'continuously' varying AWGN, which

motivates the development of the sparsity-recovery oriented signal detection method described in the next subsection.

Ii. Sparsity-driven Signal Detection

In the area of signal representation, an overcomplete dictionary is defined as a

matrix D a R ^{λ k} , K > N , which contains at least one signal basis [25]. The columns of D , denoted byd^ , 0 £ k £ K - 1 are usually prototype signal-atoms. Given an overcomplete

dictionary, we can exactly decompose an N -sample vector of the received PPM UWB signal

r = [F[0JO ^; [1 ], ---,y[N - I]J into a linear combination of the dictionary atoms, which is given

by

K r = Dx = a ^fl *d*, (26) k= I

where x = [a _ϋ ,a _h ...,a _κ _ _\ f and T denotes the matrix transpose. Notice that N should be

large enough so that r contains at least one UWB pulse.

Since the overcomplete dictionary contains more than enough atoms, there exists a number of different signal decompositions for the same r , as opposed to traditional orthonormal signal representations. For the received PPM UWB signal, which is a superposition of spike-like pulses and continuously varying AWGN, an overcomplete dictionary makes it possible to

represent the received signal vector ^r with high efficiency. That is, the vector x will have only a small number of nonzero elements when signal components with different characteristics are efficiently represented using atoms with similar properties.

This can be achieved by constructing the dictionary through combining pulse-like atoms and noise-like atoms and searching for the sparsest representation vector x . In this way, the spike-like UWB pulses are separated from the AWGN in the sense that different atoms are used to describe them and the time-domain sparsity of the UWB pulses can be reconstructed [2I]. Moreover, if the pulse-like atoms contains PPM UWB pulses with all possible pulse positions for a given received signal vector r , PPM UWB signal detection can be accomplished by

searching for the largest coefficient among those corresponding to the pulse-like atoms in x

[21].

Mathematically, the sparsest signal representation is the solution of the problem given by

(P ₀ ) min I l x | | ₀ subject to r = Dx (27)

where || . || ₀ is the / ₀ norm, counting the nonzero entries of x . Generally, searching for the

sparsest representation given an overcomplete dictionary is a combinatorial optimization problem and its complexity grows exponentially with the size of the dictionary K [5]. However, it has been shown that if there exists a sparse enough representation of a signal, it can be located via solving the l _p norm minimization problem, where 0 < p £ 1 [8]. In other

words, /^ minimization is inherently sparsity-driven. Among all available algorithms, the /,

norm minimization is of particular interest because it can be solved by convex linear or quadratic programming algorithms with low complexity. Mathematically, we detect the PPM UWB signals through solving

(/ ^> ,) min Il x | !, subject to r = Dx (28)

Equation (28) is also known as basis pursuit [24].

Problem Statement and Relaxation

A. Quantization of the Dissimilarity

It is not hard to observe that the dissimilarity between the UWB pulses and the noise such as AWGN is essential for the sparsity-driven algorithm. If the UWB pulse shape is very similar to the noise, the sparsity-driven signal detection will fail since the separation of the UWB pulses from noise through representing them using atoms with different characteristics is not possible.

In [21 ], Gaussian monocycle is selected in generating the numerical examples. And it is shown that with Gaussian monocycle, the sparsity-driven signal detection can function correctly with the AWGN mainly represented as the linear combination of the columns of the

Hadamard Walsh matrix H _M , and the UWB pulses described by atoms in the pulse

constellation matrix G . In particular, the Hadamard-Walsh (HW) matrix is generated recursively as

γ H _{M j l} + H _{M / 2} Q_ I ⁺ H _M I 2 " H _M i ₂ g

with H i = 1 . This phenomena of the sparsity-driven optimization problem can be explained

by noting that the columns of a Hadamard-Walsh matrix better match the 'continuously' varying AWGN. In other words, representing the Gaussian monocycles with the atoms from H _A/ would result in a larger value of the objective function || x ||) .

However, Gaussian monocycle is definitely not the best choice. One important reason is that it fits the FCC emission mask poorly [26]. This motivates us to search for optimal pulse shaping in the sense that it possesses the largest dissimilarity to the 'continuously' varying noise while satisfying the FCC emission mask.

Let us denote the UWB pulse as a finite-length column vector P with M samples. Notice that the pulse vector can include a number of zeros before the pulse starts and after the pulse ends. Since the Hadamard-Walsh matrix is full-rank, P can be uniquely decomposed as the linear combination of the columns of H _w . Mathematically, we have P = H _M xy , where y is

the signal representation vector. The optimal pulse shape generates a y with the largest 1 -norm, because a lower 1 -norm value for y denotes that the pulse can be more closely described with

atoms from H _λ/ , or equivalently, the pulse is more similar to the AWGN. Taking the FCC

emission mask into consideration, we can formulate the following optimal pulse shaping

problem for sparsity-driven detection, which is given by

(P ₂ ) max H y H,

(30) subject to P = H _M *y and | F{P }(f) | ² £ M(f)

where / ⁷ M(Z) denotes the discrete-time Fourier transform and M(f) represents the FCC

emission mask over the frequency range in consideration. It should be pointed out that in practice, the PSD of the transmitted PPM UWB signal is a complex function of the PSD of the pulse and the probability distribution of the information stream [24, equ. 30]. However, since

the PSD of the PPM UWB signal is shaped by | F{P }(f) | ² , we may simply approximate the

PSD of the radiated signal with| F{P }(f) \ ² . Therefore, the constraint | F(H(Z) | ² £ M(f)

should be interpreted as the simplification of the real restriction of the FCC emission mask on the PSD of the UWB pulse, as in [23] and [24].

B. Objective Function Relaxation

Based on the definition of the 1-norm, the objective function of problem (P) can be written

^as ll y llι ⁼ a fl ^" | ' I y, I , where b/l denotes the absolute value of y, . Since we need to

maximize|| y |h , the widely adopted linearization method which bounds | y, | by introducing

a new variable d, , where | y, | ³ d, , d, ³ 0 cannot be applied. This is because this

transformation results in two mutually exclusive cases, y, ³ d, and y, £ - a] .

An alternative way is to represent the objective function as|| y |||= a (I ^' _I V, * ^s gn(y,) ,

where sgn(-) is the signum function defined as

I - 1, x < 0 sgn(x) = j , _{χ ) 0} (31)

However, the signum function is discontinuous atx = 0 , which prohibits us from using many well-developed nonlinear optimization methods. We approximate the signum function

with the time-scaled hyperbolic tangent function, which is given by

ax _ - ax tanh(«x) = _{eax + e} . _ax (32)

where a is a positive real number.

In Fig. 10, we plot the signum function and the hyperbolic tangent function with varying a to illustrate the accuracy of the approximation. It can be observed that the approximation error is decreased, as a becomes larger. It is also worthwhile to note that even with largeα , for very small value ofy, , we still have| y, |> y, ^χ tanh(αy,) . However, this difference will not cause

significant degradation in the quality of the approximation since the error mainly comes from very small | y, | , which contributes little to 11 y 11, .

Now, we obtain a relaxed version of problem in (P), which is given by

Ki- I

(P ₃ ) max a y, ^χ tanh(α xy,) ^p ,= o (33) subject to P = H _M xy and | F{P }(f) | ² £ M if)

Note that the objective function of this problem is a continuous but nonlinear function of the variables, and the constraints are indeed linear since discrete-time Fourier transform is linear. With those observations in mind, we can apply many well-studied nonlinear algorithms to solve this problem, e.g., sequential quadratic programming (SQP)[13].

Design Examples

In this section, a pulse design example is provided. We set the sampling frequency to be

64 GHz, the pulse width to be 1 ns and the size of the pulse vector to be 128. In particular, we add 32 zeros before the beginning and after the end of the pulse, respectively. The emission mask is selected as the FCC indoor spectral mask. Additionally, we slightly modify the indoor

mask by setting M(f) = - 35 dB for / £ 1 GHz. The time-scaling factor a for the

hyperbolic tangent function is set to be 10 ³ . The algorithm used to solve the problem in (1 1) is the SQP algorithm.

Fig. 1 1 and Fig. 12 plot the obtained pulse shape and its compliance with the modified FCC indoor emission mask, respectively. We can observe that the optimization problem can generate a UWB pulse with a PSD closely matching the emission mask. This can be explained by noting that the maximization of | | y H ₁ will drive the optimal pulse shape to possess as

much energy as possible. The | | y | || of the optimal pulse is around 7.5, compared with a value

of 3.6 for the Gaussian monocycle with the same power. That is, the optimal UWB pulse is less similar to the AWGN than the Gaussian monocycle.

The above examples are representative only, and should not be taken as limiting the scope of this disclosure. In additional examples, pulse design can be based on communication channel limitations other than AWGN. For example, other types of noise can be used, or channel interference, or other signal contributions associated with signal distortion or degradation. In the above examples, a linear combination of the columns of a Hadamard- Walsh matrices is used to represent AWGN, and pulse shaping is based on an approximate maximization of a vector norm || y | | _| subject to compliance with an FCC mask. In other examples, different

representations of channel noise or other imperfections can be used, and different compliance masks can be used. For convenience, a particular approximation of the signum function was used, but other approximations can be used instead, and the hyperbolic tangent is only an example. In some examples, computer-executable instructions for performing the disclosed methods are stored in RAM, ROM, hard disks, CD ROMS, or other computer-readable media.

A portion of a representative communication system is illustrated in Fig. 13. A signal processor 404 is configured to receive data and process the data to provide an output signal. The signal processor is in communication with a pulse selector 406 that can access memory 410 in which various noise sets (noise representations) and corresponding optimized or substantially optimized pulse parameters or representations are stored. Based a selected pulse, the signal processor 404 encodes data for transmission so that data and noise are more readily distinguishable at a receiver. The receiver can be similarly equipped with a noise set and pulse parameter data for use in data extraction. As shown in Fig. 13, a pulse parameter processor 408 and a noise processor 412 are provided so that communication channel properties can be estimated, and noise sets and/or pulse parameters updated, generated, or deleted in order to permit more accurate data estimation.

The foregoing is a description of representative embodiments of the disclosed technology. As would be known to one skilled in the art, variations are contemplated. Instructions for performing the disclosed methods can be stored in computer readable media such as RAM, ROM, disk drives, CD ROMs, or other media for execution on a general purpose computer or a dedicated signal processor. The method can easily be applied to other UWB systems by substituting the corresponding signal or noise atoms in the overcomplete dictionary.

References

The following references are cited in this disclosure and are incorporated herein by reference. In addition. Wei Li and Aaron Gulliver, U. S Provisional Patent Application No. 60/757,786 and US Provisional Patent Application No. 60/757,787 entitled "Overcomplete Dictionary Based Ultra- Wideband Signal Detector," and "Pulse Shaping for Pulse Position Modulation UWB Systems," both filed January 9, 2005, are also incorporated herein by reference. [1] OSD/DARPA Ultra- Wideband Radar Review Panel, "Assessment of Ultra- Wideband

Technology," Defense Advanced Research Projects Agency, July 1990.

[2] I. Oppermann, M. Hamalainen and J. linatti, UWB Theory and Applications, John Wiley and Sons, England, Oct. 2004.

[3] J. D. Taylor. Introduction to Ultra-Wideband Radar Systems, CRC Press, 1995.

[4| W. Zhuang, X. (S.) Shen and Q. Bi, "Ultra- wideband wireless communications," Wireless

Commun. and Mobile Comput., pp. 663—685, 2003.

[5] D. L. Donoho and M. Elad, "Optimally sparse representation in general (non-orthogonal) dictionaries via /| minimization," Proc. National Academy of Science, vol. 100, no. 5, pp.

2197-2202, Mar. 2003.

[6] M. Elad and A.M. Bruckstein, "A generalized uncertainty principle and sparse representations in pairs of bases," IEEE Trans. Inform. Theory, vol. 49, pp. 2558—2567,

Apr. 2002.

[7] A.R. Varkonyi-Koczy and M. Fek, "Recursive overcomplete signal representations,"

IEEE Trans. Instrumentation and Measurement, vol. 50, no. 6, pp. 1698—1703, Dec.

2001.

[8] D. L. Donoho and X. Huo, "Uncertainty principles and ideal atomic decomposition," IEEE Trans. Inform. Theory, vol. 47. no. 7, pp. 2845-2862, Nov. 2001.

[9] D. L. Donoho, "For most large underdetermined systems of linear equations, the minimal /ι -norm near-solution approximates the sparsest near-solution," Technical Report 2004-1 1 , Department of Statistics, Stanford University, 2004.

[ 10J H. Krim, D. Tucker, S. Mallat and D. Donoho, "On denoising and best signal representation," IEEE Trans. Inform. Theory, vol. 45, no. 7, pp. 2225—2238 Nov. 1999.

[1 1] D. L. Donoho, and Y. Tsaig, "Recent advances in sparsity-driven signal recovery," Proc.

IEEE Int. Coηf. Acoustics, Speech, and Signal Process., pp. 713—716, Mar. 2005.

[12] F. Ramirez-Mireles, "Performance of ultrawideband SSMA using time hopping and

M-ary PPM," IEEEJ. Select. Areas Commun., vol. 19. no. 6, pp. 1 186-1 196, June 2001.

[13] S. S. Chen, D. L. Donoho and M.A. Saunders, "Atomic decomposition by basis pursuit,"

SIAMJ. Scientific Comput., vol. 20. no. 1 , pp. 33-61 , 1999.

[14] D. L. Donoho, S. S. Chen and M.A. Saunders, "Atomic decomposition by basis pursuit,"

SlAM Review, vol. 43, no. 1. pp. 129-159, 2001.

[ 15] I. F. Gorodnitsky and B. D. Rao, "Sparse signal reconstruction from limited data using FOClJSS: A re-weighted norm minimization algorithm" IEEE Trans. Signal Processing, vol. 45. no. 3, pp. 600-616, Nov. 1997.

1 16] D. L. Donoho, "Denoising by soft thresholding," IEEE Trans. Inform. Theory, vol. 41. no.

3. pp. 613-627, May 1995.

[17] D. M. Malioutov, M. Cetin and A.S. Willsky, "A Sparse signal reconsruction perspective for source localization with sensor arrays," IEEE Trans. Signal Processing, vol. 58, no. 8, pp. 3010-3022, 2004.

[18] A. Antoniou and W. -S. Lu, Optimization: Methods, Algorithms, and Applications, Kluwer Academic Publishers, 2005.

[19] A. Batra et. al, "Multi-band OFDM Physical layer proposal," merged proposal for IEEE

802.15.3a, http://ieee802.org/15/pub/Download.htmK July 2003.

[20] Z. Wang and G.B. Giannakis, "Wireless multi-carrier communications," IEEE Signal

Processing Mag., vol. 17, no. 3, pp. 29-48, May 2000.

[21 ] Wei Li and T. Aaron Gulliver, "Overcomplete dictionary based ultra- wideband signal detection", Proc. IEEE Wireless Commun. and Networking Coηf., pp. 878-883, Apr. 2006.

[22] M. Z. Win and R. A. Scholtz, "Impulse Radio: How it works", IEEE Communications Letters, Vol. 2, No. 1. Jan. 1998.

123] Xianren Wu. Zhi Tian, T. N. Davidson and G. B. Giannakis, "Optimal Waveform Design for UWB Radios", IEEE International Conference on Acoustics, Speech, and Signal

Processing, 2004. Proceedings. (ICASSP '04)., Montreal, Canada, pp. 512-514, 2004.

[24] M.G. DiBenedetto and L. DeNardis, "Tuning UWB Signals by Pulse Shaping: Towards Context-Aware Wireless Networks", Signal Processing, vol. 89, no. 9, pp. 2172-2182, Sept. 2006.

[25] D. L. Donoho, S. S. Chen and M. A. Saunders, "Atomic decomposition by basis pursuit," SIAM Review, vol. 43, no. 1, pp. 129-159, 2001.

[26] N. C. Beaulieu and Bo Hu, "A Novel Pulse Design Algorithm for Ultra- Wideband Communications", IEEE Global Telecommunications Conference 2004 (GLOBECOM'04), Vol. 5, pp:3220 - 3224, 2004.