# Orthogonal exponential spline pulses with application to impulse radio.

[FIGURE 1 OMITTED]1 Introduction

The M-shaped linear spline

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

plotted in Fig. 1 is not a wavelet for the multiresolutional analysis because M(t) is not orthogonal to its dilation M(t/2). But M(t) has three remarkable properties that (i) it is time-limited, (ii) its integration over the domain is zero, and (iii) its shifts by integers are orthogonal to one another [3]. Those properties are exactly what is required of pulses for the impulse radio communications [7]. They are required (i) for the sake of real-time communications, (ii) for the pulse to be feasible as a radio waveform, and (iii) for the pulse detection to be robust against noise in the sense of least-squares estimation, respectively.

We shall look for this kind of pulse functions in the broader family of exponential splines [5, 6] which have the advantage that they can be shaped through linear dynamical systems [6] . Such pulse functions will work as practical pulses which carry data in the impulse radio communications.

The problem is simple: we are to find a time-limited and zero-mean exponential spline q(t) with the knot interval 1 that is orthogonal to its integer shifts,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

for any integer k. This paper presents a procedure to find such a pulse function and its application to the impulse radio.

2 Preliminaries

2.1 Time-limited exponential splines

An exponential spline [5, 6] is the output of a certain linear dynamical system excited by a series of the Dirac delta functions input. The one having the shortest duration is called exponential B-spline [5, 6]. For a given linear dynamical system S having the irreducible transfer function with real coeffiients

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

of which pole-zero representation is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

an exponential B-spline with the knot interval 1/2 is the output

[beta](t) = S(b)(t) (5)

of S for the input being a series of delta functions

b(t) = [n.summation over l=0] [b.sub.l][delta] (t- l/2) (6)

such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

This exponential B-spline is time-limited [5, 6] as

[beta](t)=0, t[not member of] (0,n/2) (8)

Because [{[[lambda].sub.l]}.sup.n.sub.l=0] include only real numbers or pairs of complex conjugate numbers, [{[b.sub.l]}.sup.n.sub.l=0] are real numbers so that b(t) and [beta](t) are real-valued functions.

2.2 Time-limited and zero-mean exponential splines

In order to keep the splines zero-mean, instead of the original exponential B-spline [beta](t), we shall use a real-valued function

[alpha](t) = [beta](t) - [beta] (t - 1/2) (9)

which is time-limited as

[alpha](t)=0, t[not member of] (0,n+1/2) (10)

and has the zero mean

[[integral].sup.[infinity].sub.[-infinity]] [alpha](t)dt = 0. (11)

Another representation of this [alpha](t) is the output

[alpha](t) = S(a)(t) (12)

of S for the input

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

The first factor in (14) corresponds to the difference in (9).

Let the desired pulse function be represented in the form

q(t)= [n-1.summation over l=0] [c.sub.l][alpha](t - l/2) (15)

with coefficients [{[c.sub.l]}.sup.N-1.sub.l=0] for some integer N [greater than or equal to] 1. Then it automatically follows from (10) and (11) that q(t) is time-limited as

q(t) = O, t [not member of] (0, n+N/2]) (16)

and has the zero mean

[[integral].sup.[infinity].sub.[-infinity]] q(t)dt = 0, (17)

respectively.

2.3 Orthogonality with respect to shift by integers The only remaining request for the desired pulse q(t) is the orthogonality (2), i.e., its autocorrelation

r(x) = [[integral].sup.[infinity].sub.[-infinity]] q(t)q (t - x) dt (18)

should satisfy the orthogonality conditions

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (19)

with respect to shift by integer k. We shall choose the number N of [{[alpha](t-l/2)}.sup.N-1.sub.l=0] employed for composing q(t) in (15) so that the number N of the unknown coefficients [{[c.sub.l]}.sup.N-1.sub.l=0] be the same as that of the essential conditions

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (20)

reduced from (19) by

r(x)=0, x[not member of](-n+N/2,n+N/2)and r(x)= r(x), x[member of](-[infinity],[infinity]) (21)

which follow from (16) and (18). Then our choice becomes N = n, which rewrites (15), (16), (20) and (21) as follows:

q(t)= [n-1.summation over l=0] [c.sub.l][alpha](t - l/2) (22)

q(t) = 0, t [not member of] (0, n) (23)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (24)

r(x) =0, x[not member of] (-n,n) and r(x)=r(-x), x[member of] (-[infinity], [infinity]) (25)

3 Construction of Orthogonal Pulses

3.1 Procedure

Because the pulse q(t) in (22) is always time-limied and zero-mean, we have only to find the coefficients [{[c.sub.l]}.sup.n-1.sub.l=0] that make the orthogonality condition (24) hold good in order to construct the desired pulse. We shall rearrange (24) in the form of some linear equations. For that purpose, we define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (26)

and

R([[zeta].sup.1/2])=C([[zeta].sup.1/2])C([[zeta].sup.-1/2]) (27)

which can also be expressed in the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (28)

Then the autocorrelation in (18) with substitutions of x = k and (22) can be represented by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (29)

where we have set

[phi](x) = [[integral].sup.[infinity].sub.[-infinity]] [alpha](t)[alpha](t - x) dt (30)

having the properties

[phi](x)=0, x[not member of](-n+1/2,n+1/2) and [phi](x)=[phi](-x),x[member of](-[infinity],[infinity]) (31)

because of (10). By (29), we can rearrange the orthogonality condition (24) in the form of linear equations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (32)

for [{[r.sub.j]}.sup.n-1.sub.j=0] Solvability of (32) can be checked by numerical computation in practice. A simpler condition in terms of dynamical parameters of S is given by the following proposition.

Proposition 1. The linear equations (32) are uniquely solvable for [{[r.sub.j]}.sup.n-1.sub.j=0] if and only if the transfer function G(s) of S has no pairs of poles [[lambda].sub.l], and [[lambda].sub.m] such that R([[lambda].sub.l]) = R([[lambda].sub.m]) = 0 and [??]([[lambda].sub.l]) - [??]([[lambda].sub.m]) = 2[pi] (mod 4[pi]) among the poles [[lambda].sub.1], [[lambda].sub.2], ... , [[lambda].sub.n] in (4) and a virtual extra pole [[lambda].sub.0] = 0. (Proof in Appendix A)

Proposition 1 implies that the linear equations (32) are uniquely solvable unless a pair of poles are purely imaginary or zero and apart by 2[pi]i modulo 4[pi]i. Solvable cases include the polynomial spline case where G(s) = 1/[s.sup.n] has all the poles at zero, and the practical case that the system S is stable, i.e., every pole of G(s) has its real part negative.

Assume that we have solved (32) to obtain its solution [{[r.sub.j]}.sup.n-1.sub.j=0]. Then R([z.sup.1/2) determined by (28) from [{[r.sub.j]}.sup.n-1.sub.j=0] can be factorized in the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (33)

because R([z.sup.1/2]) in (28) is invariant for exchange of [zeta] and [[zeta].sup.-1]. Since there are two possibilities of labeling the same number as [[gamma].sub.l] or [[gamma].sup.-1.sub.l] for each l = 1, 2 ,.., n - 1 and because [[gamma].sub.0] is determined accordingly, we have [2.sup.n-1] variations of (33) in general. Taking half the factors in any one of them, we can find

C([z.sup.1/2])= [+ or -] [square root of [[gamma].sub.0]]([z.sup.1/2-[[gamma].sub.1])([z.sup.1/2-[[gamma].sub.2]) ... ([z.sup.1/2-[[gamma].sub.n-1]) (34)

that satisfies (27) and gives the sought coefficients [{[c.sub.l]}.sup.n-1.sub.l=0] by (26).

Exciting the system S with the input series of delta functions

v(t) = [n-1.summation over l=0][c.sub.l]a (t - l/2), (35)

we obtain the desired pulse

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (36)

Now we have learnt that the condition of Proposition 1 is necessary and sufficient for the pulse q(t) to exist. The pulse q(t) is real-valued if so are the coefficients [{[c.sub.l]}.sup.n-1.sub.l=0] because [alpha](t) is real-valued. In unfortunate cases, the coefficients and the resulting pulse may be complex-valued, which cannot be implemented by real circuitry. The following proposition is a direct consequence of the Riesz lemma (Lemma 6.1.3 of [1]) and gives a condition for the coefficients and, thus, the pulse to be real-valued.

Proposition 2. There exist real-valued coefficient [{[c.sub.l]}.sup.n-1.sub.l=0] for C(z) that satisfies (27) if and only if R([e.sup.iw/2]) [greater than or equal to] 0 for all w. (Proof in Appendix B)

After solving (32) for [{[r.sub.j]}.sup.n-1.sub.j=0] we can check this condition about R([e.sup.iw/2]) to judge if it is worthwhile to attempt factoring R([z.sup.1/2]) in the form of (33).

It would be even better if we had a condition written in terms of the dynamical parameters of S. Then we can avoid S that would result in complex-valued pulses in the first place. But that is a difficult problem. By the change of variable y = [sin.sup.2] w/4, R([e.sup.iw/2]) is equivalent to I((y) that appears in Appendix A. We first have to clarify what kind of F(y) leads to non-negative K(y) via the B@zout equation (A-12). We know that F(y) [greater than or equal to] O. But the extended Euclidean algorithm for the mathematical solution of (A-12) involves many subtractions of intermediate polynomials which are very hard to untangle. We then have to characterize such F(y) in terms of the dynamical parameters of S. Besides, we are exposed to several counter-intuitive examples. As to be mentioned soon in the next subsection, pulses are real-valued in simple cases G(S) = 1/s and 1/[s.sup.2] while they are complex-valued in other simple cases G(s) = 1/[s.sup.3] and 1/[s.sup.4]. On the other hand, there still exists a third-order case that we have a real-valued pulse. It should be left as an open problem to write a condition for the pulse to be real-valued in terms of the dynamical parameters of S.

3.2 Examples

In the case G(s) = 1/s, the problem is trivial and the resulting pulse is the Haar function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (37)

The case G(s)=1/[s.sup.2] yields the linear spline M(t) of (1) as expected. Because it happens that M(t) = [square root of 3](H x H)(t), we might speculate that the pulse associated with G(s) = 1/[s.sup.3] could be proportional to (H * H * H)(t). But that is not true because (H * H * H)(t) is not orthogonal to (H * H * H)(t - 2) although it is to (H * H * H)(t - 1). What is even worse, the quadratic spline pulses for the case G(s) = 1/[s.sup.3] are complex-valued. The cubic spline case G(s)= 1/[s.sup.4] also results in complex-valued pulses. A nice example of real-valued exponential spline pulses associated with a third-order system will appear in the next section in the context of its application to the impulse radio communications.

4 Application to Impulse Radio

4.1 Practical means of pulse shaping and detection

While the series of delta functions a(t) in (13) does not exist in the real world, its integration

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (38)

is a time-limited piecewise constant function that can be generated rather precisely by electric current switches.

The piecewise constant function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (39)

is time-limited as

u(t)=0, t[not member of] (0,n) (40)

because of (38). With this u(t) input, the system S shapes the pulse

p(t) = S(u)(t) (41)

that satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (42)

[FIGURE 2 OMITTED]

because of (9), (22) and (39). This pulse is also time-limited as

p(t)=0, t[not member of](0,n) (43)

because of (17), (23) and (42).

Besides the simple and practical means' (41) to shape p(t) from the piecewise constant seed u(t), the pulse p(t) has the remarkable property

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (44)

which follows from (18), (19), (42), (43) and the partial integration formula. This property gives the foundation to the pulse transceiver system illustrated in Fig. 2.

Given data bits {[w.sub.l]}, we transmit the waveform

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (45)

shaped in the transmitter module in Fig. 2. Since a good broadband antenna is well approximated [7] by d/dt, the transmission signal w(t) is differentiated once by the transmitter antenna to be the radio signal

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (46)

[FIGURE 3 OMITTED]

and again by the receiver antenna to arrive at the receiver as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (47)

Correlating the received signal [d.sup.2]/[dt.sup.2] w(t) with the template pulse p(t - k), which is the same as the transmission pulse, for its duration (k, k + n) at the receiver module in Fig. 2, we have the bit [w.sub.k] recovered by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (48)

because of the property (44).

It should be noted that, because of (44), the detection formula (48) virtually performs the least-squares approximation of the radio waveform d/dt w(t) by d/dt P(t - k) = q(t - k) to detect [w.sub.k]. Additive noises superimposed on d/dt w(t) will then be most suppressed in the sense of least-squares estimation.

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

4.2 Practical example pulse

An example pulse obtained from the transfer function

G(s) = 1/(s+18)(s+11 x 1i+[10.sup.-13])(s-11 x 1i+[10.sup.-13]) (49)

and its associate pulses are plotted in Fig. 3. The autocorrelation in Fig. 4 becomes 1 and 0 at the origin and at the other integers, respectively, to verify (44). The power spectral density of the radio pulse d/dt p(t) = q(t) is plotted in Fig. 5 along with the spectral mask (plotted by the boxy line) for the indoor ultra-wideband communications systems [2] imposed by the US Federal Communications Commission as the upper bound which no practical pulses are allowed to exceed. The frequency axis of the mask is scaled down by 6 GHz for the purpose of comparison, or equivalently, the pulse repetition rate is assumed to be as fast as 6 G pulses per second.

The fast transmission is possible by virtue of densely overlapping pulses. Although dense pulses are prone to mutual interference in the environment where pulses travel with various delays via multiple paths, and even though the real channel characteristics are not exactly the ideal double differentiation, the multipath effects and channel modeling errors are negligible in an extreme setting that electrically small antennas are inductively coupled at a very short distance less than one inch. In the same kind of setting, the Transfer Jet technology [41 has just started serving at the maximum transmission rate of 560 M pulses per second. A much faster communications service will hopefully be the first application of the dense pulses obtained in this paper.

5 Conclusions

Inspired by the M-shaped orthogonal linear spline, we derived a procedure to construct an exponential spline pulse with the knot interval 1/2 that is time-limited, zero-mean, and orthogonal to its shifts by integers. An example pulse was obtained that will potentially enable an impulse radio communications system as fast as 6 G pulses per second under the FCC regulation for the indoor ultra-wideband communications.

A necessary and sufficient condition for real or complex-valued pulses to exist was given in terms of the parameters of S. However, it was left as an open problem to write a condition for the pulse to be real-valued in terms of the dynamical parameters of S.

Appendix A: Proof of Proposition 1

First, we prepare an expression of the Fourier transform of [phi](x) in terms of the transfer function G(s) of S. It follows from (9) and (13) that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-l)

and it follows from (30) that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-2)

Because [alpha](t) is real-valued, which means that [??](-w) = [bar.[??](w)], those two equalities (A-l) and (A-2) imply

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-3)

Now we analyze the condition (32) in the Fourier domain. The finitely many linear equations (32) are equivalent to the infinitely many ones

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-4)

because of (25). The discrete Fourier transforms of both sides give another equivalent condition

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-5)

By the Poisson summation formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and its variant

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

the left hand side of (A-5) can be converted into

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which can be reduced to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

by (28). Then the condition (A-5) can be simplified as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-6)

The left hand side of (A-6) with the even k = 2m and odd k = 2m + 1 numbered terms separated is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which can be reduced to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-7)

By (31) and yet another version of the Poisson summation formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

the first summation of (1-7) can be rearranged in the form of an n-th degree cosine polynomial

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Denote by F(y) this polynomial in y = 1/2(1 - cos w/2) = [sin.sup.2]w/4. Then the second summation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-9)

is represented by F(1 - y) because 1/2(1-cos w+2[pi]/2)=1/2 (1 + cos w/2) = [cos.sup.2] w/4 = 1 - [sin.sup.2] w/4 = 1 - y. In the meantime, (28) implies that the other factors in (A-7) are also cosine polynomials

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-10)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-11)

which can be denoted by (n - 1)-st degree polynomials K(y) and K(1 - y), respectively. By the above rearrangements and notations, (A-6) becomes equivalent to

K(y)F(y) + K(1 - y)F(1 - y) = 1, y [member of] [0,1). (A-12)

According to the Bezout theorem (Theorem 6.1.1 of [1]), there exists a unique (n - 1)-st degree polynomial K(y) satisfying (A-12) for the n-th degree polynomial F(y) if and only if F(y) and F(1 - y) do not have a common zero. Their representations in terms of w are

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-13)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-14)

where we have used (A-3). The first factors of (A-13) and (A-14) are always positive. The second factors are expanded by (14) as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-15)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A-16)

These two products become zero at the same time if and only if an exponent in (A-15) and another exponet in (A-16) happen to be integer multiples of 2[pi]i for a common w [member of] [0, 2[pi]). Denoting [[lambda].sub.0] = 0, we can express this condition by R([[lambda].sub.l]) = R([[lambda].sub.m]) = 0 and [??]([[lambda].sub.l]) - [??]([[lambda].sub.m]) = 2[pi] (mod 4[pi]) for some l and m, (l,m = 0, 1,2, ... ,n). If this is not the case, F(y) and F(1 -y) never get zero at the same time, which implies that there exists a unique K(y) satisfying (A-12). Then we can uniquely determine [{[r.sub.j]}.sup.n-1.sub.j=0] by equating K([sin.sup.2] w/4) with R([e.sup.iw/2]) in (A-10).

Appendix B: Proof of Proposition 2

Necessity. If C(z) in (26) satisfies (27) and [{[c.sub.l]}.sup.n-1.sub.l=0] are real numbers, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all w. Sufficiency. It follows from (28) that R([e.sup.iw/2]) = R([e.sup.-iw/2]). In addition, suppose that R([e.sup.iw/2]) [greater than or equal to] 0 for all w. Then, by the Riesz lemma (Lemma 6.1.3 of [1]), there exist real numbers [{[c.sub.l]}.sup.n-1.sub.l=0] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Such real coefficients make it hold good that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and, consequently, satisfy (27).

ACKNOWLEDGEMENT

This work was partially supported by JSPS grant-in-aid No. 22560401.

References

[1] I. Daubechies, Ten Lectures on Wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, 61, SIAM, Philadelphia, 1992.

[2] Federal Communications Commission, Revision of Part i5 the Commission's Rules Regarding Ultra-Wideband Transmission Systems, Notice of Proposed Rule Making, ET Docket No. 98-153, FCC, Washington, D.C., 2002.

[3] A. J. Jerri, Introduction to Wavelets, Exercises of Chapter 3, Sampling Publishing, Potsdam, NY, 2011.

[4] Transfer Jet Consortium, Worlds are about to Touch, Transfer Jet Overview Whitepaper, Tokyo, 2009.

[5] M. Unser and T. Blu, Cardinal exponential splines: Part I--Theory and filtering algorithms, IEEE Trans. Signal Process., 53(4), 1425-1438, 2005.

[6] M. Unser, Cardinal exponential splines: Part II--Think analog, act digital, IEEE Trans. Signal Process., 53(4), 1439-1449, 2005.

[7] M. Z. Win and R. A. Scholtz, Impulse radio: how it works, IEEE Commun. Lett., 2(2), 36-38, 1988.

Masaru Kamada

Department of Computer and Information Sciences, Ibaraki University Hitachi, Ibarald 316-8511, Japan

kamada@mx.ibaraki.ac.j p

Semih Ozlem

Department of Mathematics, Statistics, and Computer Science

University of Illinois at Chicago

322 Science and Engineering Offices (M/C 249)

851 S. Morgan Street, Chicago, IL 60607-7045, USA

sozlem2@uic.edu

Hiromasa Habuchi

Department of Computer and Information Sciences, Ibaraki University Hitachi, Ibaraki 316-8511, Japan

habuchi@mx.ibaraki.ac.jp

Printer friendly Cite/link Email Feedback | |

Author: | Kamada, Masaru; Ozlem, Semih; Habuchi, Hiromasa |
---|---|

Publication: | Sampling Theory in Signal and Image Processing |

Article Type: | Report |

Geographic Code: | 1USA |

Date: | Jan 1, 2011 |

Words: | 3827 |

Previous Article: | On sampling related properties of B-spline Riesz sequences. |

Next Article: | Non-uniform filter interpolation in the frequency domain. |

Topics: |