Near-optimal depth-constrained codes

This note considers an n-letter alphabet in which the ith letter is accessed with probability p/sub i/. The problem is to design efficient algorithms for constructing near-optimal, depth-constrained Huffman and alphabetic codes. We recast the problem as one of determining a probability vector q/sup */=(q/sup *//sub 1/,...,q/sup *//sub n/) in an appropriate convex set, S, so as to minimize the relative entropy D(p/spl par/q) over all q/spl isin/S. Methods from convex optimization give an explicit solution for q/sup */ in terms of p. We show that the Huffman and alphabetic codes so constructed are within 1 and 2 bits of the corresponding optimal depth-constrained codes.     

Polyharmonic smoothing splines and the multidimensional Wiener filtering of fractal-like signals.

Motivated by the fractal-like behavior of natural images, we develop a smoothing technique that uses a regularization functional which is a fractional iterate of the Laplacian. This type of functional was initially introduced by Duchon for the approximation of nonuniformily sampled, multidimensional data. He proved that the general solution is a smoothing spline that is represented by a linear combination of radial basis functions (RBFs). Unfortunately, this is tedious to implement for images because of the poor conditioning of RBFs and their lack of decay. Here, we present a much more efficient method for the special case of a uniform grid. The key idea is to express Duchon's solution in a fractional polyharmonic B-spline basis that spans the same space as the RBFs. This allows us to derive an algorithm where the smoothing is performed by filtering in the Fourier domain. Next, we prove that the above smoothing spline can be optimally tuned to provide the MMSE estimation of a fractional Brownian field corrupted by white noise. This is a strong result that not only yields the best linear filter (Wiener solution), but also the optimal interpolation space, which is not bandlimited. It also suggests a way of using the noisy data to identify the optimal parameters (order of the spline and smoothing strength), which yields a fully automatic smoothing procedure. We evaluate the performance of our algorithm by comparing it against an oracle Wiener filter, which requires the knowledge of the true noiseless power spectrum of the signal. We find that our approach performs almost as well as the oracle solution over a wide range of conditions.     

A stochastic framework for recursive computation of spline functions--Part I: Interpolating splines

The method for exploiting stochastic smoothing techniques to develop dynamical recursive algorithms for the deterministic problem of d interpolation (optimal curve fitting) is shown. A reproducing kernel Hilbert space approach is used to develop an explicit correspondence between spline interpolation and linear least-squares smoothing of a particular zero-mean random process. This random process is shown to be the output of a white-noise-driven dynamical system whose parameters and initial conditions are fixed by the functional form chosen for the spline. A recursive algorithm is then derived for this (nonstandard) smoothing problem, and thus also for the original spline interpolation problem.     

Polynomial spline-approximation of Clarke's model

We investigate polynomial spline approximation of stationary random processes on a uniform grid applied to Clarke's model of time variations of path amplitudes in multipath fading channels with Doppler scattering. The integral mean square error (MSE) for optimal and interpolation splines is presented as a series of spectral moments. The optimal splines outperform the interpolation splines; however, as the sampling factor increases, the optimal and interpolation splines of even order tend to provide the same accuracy. To build such splines, the process to be approximated needs to be known for all time, which is impractical. Local splines, on the other hand, may be used where the process is known only over a finite interval. We first consider local splines with quasioptimal spline coefficients. Then, we derive optimal spline coefficients and investigate the error for different sets of samples used for calculating the spline coefficients. In practice, approximation with a low processing delay is of interest; we investigate local spline extrapolation with a zero-processing delay. The results of our investigation show that local spline approximation is attractive for implementation from viewpoints of both low processing delay and small approximation error; the error can be very close to the minimum error provided by optimal splines. Thus, local splines can be effectively used for channel estimation in multipath fast fading channels.     

Exact thresholds and optimal codes for the binary-symmetric channel and Gallager's decoding algorithm A

We show that for the case of the binary-symmetric channel and Gallager's decoding algorithm A the threshold can, in many cases, be determined analytically. More precisely, we show that the threshold is always upper-bounded by the minimum of (1-/spl lambda//sub 2//spl rho/'(1))/(/spl lambda/'(1)/spl rho/'(1)-/spl lambda//sub 2//spl rho/'(1)) and the smallest positive real root /spl tau/ of a specific polynomial p(x) and we observe that for most cases this bound is tight, i.e., it determines the threshold exactly. We also present optimal degree distributions for a large range of rates. In the case of rate one-half codes, for example, the threshold x/sub 0//sup */ of the optimal degree distribution is given by x/sup *//sub 0//spl sim/0.0513663. Finally, we outline how thresholds of more complicated decoders might be determined analytically.     

H optimal approximation for causal spline interpolation

In this paper, we give a causal solution to the problem of spline interpolation using H^∞ optimal approximation. Generally speaking, spline interpolation requires filtering the whole sampled data, the past and the future, to reconstruct the inter-sample values. This leads to non-causality of the filter, and this becomes a critical issue for real-time applications.Our objective here is to derive a causal system which approximates spline interpolation by H^∞ optimization for the filter. The advantage of H^∞ optimization is that it can address uncertainty in the input signals to be interpolated in design, and hence the optimized system has robustness property against signal uncertainty.We give a closed-form solution to the H^∞ optimization in the case of the cubic splines. For higher-order splines, the optimal filter can be effectively solved by a numerical computation. We also show that the optimal FIR (finite impulse response) filter can be designed by an LMI (linear matrix inequality), which can also be effectively solved numerically. A design example is presented to illustrate the result.     

Channel capacity and state estimation for state-dependent Gaussian channels

We formulate a problem of state information transmission over a state-dependent channel with states known at the transmitter. In particular, we solve a problem of minimizing the mean-squared channel state estimation error E/spl par/S/sup n/ - S/spl circ//sup n//spl par/ for a state-dependent additive Gaussian channel Y/sup n/ = X/sup n/ + S/sup n/ + Z/sup n/ with an independent and identically distributed (i.i.d.) Gaussian state sequence S/sup n/ = (S/sub 1/, ..., S/sub n/) known at the transmitter and an unknown i.i.d. additive Gaussian noise Z/sup n/. We show that a simple technique of direct state amplification (i.e., X/sup n/ = /spl alpha/S/sup n/), where the transmitter uses its entire power budget to amplify the channel state, yields the minimum mean-squared state estimation error. This same channel can also be used to send additional independent information at the expense of a higher channel state estimation error. We characterize the optimal tradeoff between the rate R of the independent information that can be reliably transmitted and the mean-squared state estimation error D. We show that any optimal (R, D) tradeoff pair can be achieved via a simple power-sharing technique, whereby the transmitter power is appropriately allocated between pure information transmission and state amplification.     

Algorithms for designing wavelets to match a specified signal

Algorithms for designing a mother wavelet /spl psi/(x) such that it matches a signal of interest and such that the family of wavelets {2/sup -(j/2)//spl psi/(2/sup -j/x-k)} forms an orthonormal Riesz basis of L/sup 2/(/spl Rscr/) are developed. The algorithms are based on a closed form solution for finding the scaling function spectrum from the wavelet spectrum. Many applications require wavelets that are matched to a signal of interest. Most current design techniques, however, do not design the wavelet directly. They either build a composite wavelet from a library of previously designed wavelets, modify the bases in an existing multiresolution analysis or design a scaling function that generates a multiresolution analysis with some desired properties. In this paper, two sets of equations are developed that allow us to design the wavelet directly from the signal of interest. Both sets impose bandlimitedness, resulting in closed form solutions. The first set derives expressions for continuous matched wavelet spectrum amplitudes. The second set of equations provides a direct discrete algorithm for calculating close approximations to the optimal complex wavelet spectrum. The discrete solution for the matched wavelet spectrum amplitude is identical to that of the continuous solution at the sampled frequencies. An interesting byproduct of this work is the result that Meyer's spectrum amplitude construction for an orthonormal bandlimited wavelet is not only sufficient but necessary. Specific examples are given which demonstrate the performance of the wavelet matching algorithms for both known orthonormal wavelets and arbitrary signals.     

High-quality image resizing using oblique projection operators

The standard interpolation approach to image resizing is to fit the original picture with a continuous model and resample the function at the desired rate. However, one can obtain more accurate results if one applies a filter prior to sampling, a fact well known from sampling theory. The optimal solution corresponds to an orthogonal projection onto the underlying continuous signal space. Unfortunately, the optimal projection prefilter is difficult to implement when sine or high order spline functions are used. We propose to resize the image using an oblique rather than an orthogonal projection operator in order to make use of faster, simpler, and more general algorithms. We show that we can achieve almost the same result as with the orthogonal projection provided that we use the same approximation space. The main advantage is that it becomes perfectly feasible to use higher order models (e.g. splines of degree n=/>3). We develop the theoretical background and present a simple and practical implementation procedure using B-splines. Our experiments show that the proposed algorithm consistently outperforms the standard interpolation methods and that it provides essentially the same performance as the optimal procedure (least squares solution) with considerably fewer computations. The method works for arbitrary scaling factors and is applicable to both image enlargement and reduction.     

GaN MSM UV photodetectors with titanium tungsten transparent electrodes

GaN metal-semiconductor-metal (MSM) ultraviolet photodetectors with titanium tungsten (TiW) transparent electrodes were fabricated and characterized. It was found that the 10-nm-thick TiW film deposited with a 300-W RF power can still provide a reasonably high transmittance of 75.1% at 300 nm, a low resistivity of 1.7/spl times/10/sup -3/ /spl Omega//spl middot/cm and an effective Schottky barrier height of 0.773 eV on u-GaN. We also achieved a peak responsivity of 0.192 A/W and a quantum efficiency of 66.4% from the GaN ultraviolet MSM photodetector with TiW electrodes. With a 3-V applied bias, it was found that minimum noise equivalent power and maximum D/sup */ of our detector were 1.987/spl times/10/sup -10/ W and 6.365/spl times/10/sup 9/ cmHz/sup 0.5/W/sup -1/, respectively.     

In/sub 0.5/Ga/sub 0.5/As/GaAs quantum dot infrared photodetectors grown by metal-organic chemical vapor deposition

We report the growth by low-pressure metal-organic chemical vapor deposition, fabrication, and characterization of ten-layer In/sub 0.5/Ga/sub 0.5/As/GaAs quantum dot infrared photodetectors. Normal incidence photoresponse of the detector was obtained at 5.9 /spl mu/m. The 77-K peak responsivity was 5.6 mA/W with the detectivity D/sup */ of 1.2/spl times/10/sup 9/ cm/spl middot/Hz/sup 1/2//W at the bias of 0.4 V.     

New View on an Anisotropic Medium and Its Application to Transformation from Anisotropic to Isotropic Problems

The metric factor is defined as m(epsilon*/sub x/, epsilon*/sub y/, theta/sub x/) = /spl radic/ cos/sup 2/theta/sub x/ / epsilon*/sub x/ + sin/sup 2/theta/sub x/ / epsilon*/sub y/ in the radial direction, with the angle theta/sub x/ from the x axis being one of the principal axes in an anisotropic dielectric medium filling the two-dimensional space. The normalized metric factor is defined as n(epsilon*/sub x/, epsilon*/sub y/, theta/sub x/, beta) /spl equiv/ m(epsilon*/sub x/, epsilon*/sub y/, theta/sub x/) / m(epsilon*/sub x/, epsilon*/sub y/, beta) in the form normalized by the metric factor in the direction with the angle beta from the x axis. The effective path length d'/sub P1P2/ between the points P1 and P2 is defined as d'/sup P1P2/ = n(epsilon*/sub x/, epsilon*/sub y/, theta/sub x/, beta)d/sub P1P2/ where d/sub P1P2/ is the actual path length of the straight line P1P2 with the angle theta/sub x/ from the x axis. We propose the minimun principle of the effective path length for electric flux in the region with multilayered anisotropic media. It is applied to solving the electrostatic problem with two anisotropic media whose principal axes are different. We show by using the normalized metric factor that the anisotropic problem can be transformed into the isotropic problem.     

Collision-minimizing CSMA and its applications to wireless sensor networks

Recent research in sensor networks, wireless location systems, and power-saving in ad hoc networks suggests that some applications' wireless traffic be modeled as an event-driven workload: a workload where many nodes send traffic at the time of an event, not all reports of the event are needed by higher level protocols and applications, and events occur infrequently relative to the time needed to deliver all required event reports. We identify several applications that motivate the event-driven workload and propose a protocol that is optimal for this workload. Our proposed protocol, named CSMA/p/sup */, is nonpersistent carrier sense multiple access (CSMA) with a carefully chosen nonuniform probability distribution p/sup */ that nodes use to randomly select contention slots. We show that CSMA/p/sup */ is optimal in the sense that p/sup */ is the unique probability distribution that minimizes collisions between contending stations. CSMA/p/sup */ has knowledge of N. We conclude with an exploration of how p/sup */ could be used to build a more practical medium access control protocol via a probability distribution with no knowledge of N that approximates p/sup */.     

Decoding by linear programming

This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e. Here, A is an m by n (coding) matrix and e is an arbitrary and unknown vector of errors. Is it possible to recover f exactly from the data y? We prove that under suitable conditions on the coding matrix A, the input f is the unique solution to the /spl lscr//sub 1/-minimization problem (/spl par/x/spl par//sub /spl lscr/1/:=/spl Sigma//sub i/|x/sub i/|) min(g/spl isin/R/sup n/) /spl par/y - Ag/spl par//sub /spl lscr/1/ provided that the support of the vector of errors is not too large, /spl par/e/spl par//sub /spl lscr/0/:=|{i:e/sub i/ /spl ne/ 0}|/spl les//spl rho//spl middot/m for some /spl rho/>0. In short, f can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program). In addition, numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted. This work is related to the problem of finding sparse solutions to vastly underdetermined systems of linear equations. There are also significant connections with the problem of recovering signals from highly incomplete measurements. In fact, the results introduced in this paper improve on our earlier work. Finally, underlying the success of /spl lscr//sub 1/ is a crucial property we call the uniform uncertainty principle that we shall describe in detail.     

Frequency hopping sequences with optimal partial autocorrelation properties

We classify some p/sup k/-ary (p prime, k integer) generalized m-sequences and generalized Gordon-Mills-Welch (GMW) sequences of period p/sup 2k/-1 over a residue class ring R=GF(p)[/spl xi/]/(/spl xi//sup k/) having optimal partial Hamming autocorrelation properties. In frequency hopping (FH) spread-spectrum systems, these sequences are useful for synchronizing process. Suppose, for example, that a transmitting p/sup k/-ary FH patterns of period p/sup 2k/-1 are correlated at a receiver. Usually, the length of a correlation window, denoted by L, is shorter than the pattern's overall period. In that case, the maximum value of the out-of-phase Hamming autocorrelation is lower-bounded by /spl lceil/L/p/sup k/+1/spl rceil/ but the classified sequences achieve this bound with equality for any positive integer L.     

Conjugate ESPRIT (C-SPRIT)

In this paper, we present an algorithm to estimate the direction of the arrival angles (DOAs) from noncoherent one-dimensional (1-D) signal sources such as binary phase shift keying (BPSK) and M-ary amplitude shift keying (MASK). The proposed algorithm can provide a more precise DOA estimation and can detect more signals than well-known classical subspace-methods MUSIC and ESPRIT for the 1-D signals. The complexity is the same as that of ESPRIT since the proposed algorithm uses the same array geometry and subarray processing that ESPRIT does. The main differences between the proposed algorithm and the ESPRIT algorithm are as follows: 1) the number of overlapping array elements between two subarrays is equal to M in the proposed algorithm, while in ESPRIT the maximum number of overlapping elements is M-1, where M denotes the total number of array elements, and 2) the proposed algorithm employs the conjugate of rotation matrix (CRM) /spl Phi//sup */ while ESPRIT uses /spl Phi/ with no conjugate for the second subarray geometry.     

Covering codes with improved density

We prove a general recursive inequality concerning /spl mu//sup */(R), the asymptotic (least) density of the best binary covering codes of radius R. In particular, this inequality implies that /spl mu//sup */(R)/spl les/e/spl middot/(RlogR+logR+loglogR+2), which significantly improves the best known density 2/sup R/R/sup R/(R+1)/R!. Our inequality also holds for covering codes over arbitrary alphabets.     

Broad-band distributed Bragg reflectors with photorefractive Ti : Cu : LiNbO/sub 3/ waveguide gratings

We have realized broad-band distributed Bragg reflectors with photorefractive gratings recorded at 441.6 nm in channel Ti : Cu : LiNbO/sub 3/ waveguides. Proton-assisted copper exchange is used to enable a high level of copper doping and, thereby, achieve an extremely large modulation of refractive index (/spl ges/ 5/sup */10/sup -4/) within a photorefractive grating. Experimental structures demonstrate reflectivities up to 17% with full-width at half-maximum bandwidths in excess of 1.2 nm at center wavelengths around 1.55 /spl mu/m.     

Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f/spl isin/C/sup N/ and a randomly chosen set of frequencies /spl Omega/. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set /spl Omega/? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying |T|/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ |/spl Omega/| for some constant C/sub M/>0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1-O(N/sup -M/), f can be reconstructed exactly as the solution to the /spl lscr//sub 1/ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C/sub M/ which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of |T| spikes may be recovered by convex programming from almost every set of frequencies of size O(|T|/spl middot/logN). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1-O(N/sup -M/) would in general require a number of frequency samples at least proportional to |T|/spl middot/logN. The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.     

4H-SiC UV photo detectors with large area and very high specific detectivity

Pt/4H-SiC Schottky photodiodes have been fabricated with the device areas up to 1 cm/sup 2/. The I-V characteristics and photoresponse spectra have been measured and analyzed. For a 5 mm/spl times/5 mm area device leakage current lower than 10/sup -15/ A at zero bias and 1.2/spl times/10/sup -14/ A at -1 V have been established. The quantum efficiency is over 30% from 240 to 320 nm. The specific detectivity, D/sup */, has been calculated from the directly measured leakage current and quantum efficiency are shown to be higher than 10/sup 15/ cmHz/sup 1/2//W from 210 to 350 nm with a peak D/sup */ of 3.6/spl times/10/sup 15/ cmHz/sup 1/2//W at 300 nm.