Algorithmic fairness is receiving significant attention in the academic and broader literature due to the increasing use of predictive algorithms. One benefit of this trend is that algorithm designers and users have a growing set of fairness measures to choose from. However, this choice comes with the challenge of identifying how the different fairness measures relate to one another, as well as the extent to which they are compatible or mutually exclusive. We describe some of the most widely used fairness metrics using a common mathematical framework and present new results on the relationships among them. The results presented herein can help place both specialists and non-specialists in a better position to identify the metric best suited for their application and goals.

Safety-critical system domains such as critical infrastructures, aerospace, automotive, and industrial manufacturing and control are becoming increasingly dependent on the use of distributed systems to achieve their functionality. These distributed systems can contain many complex interactions among their constituent components. Despite extensive testing and verification of individual components, security vulnerabilities resulting from unintended and unforeseen component interactions (so-called implicit interactions) often remain undetected and can have an impact on the safety, security, and reliability of a system. This paper presents an approach for identifying and analyzing the existence and severity of implicit interactions in distributed systems. The approach is based on the modeling framework known as communicating concurrent Kleene algebra (C2KA). Experimental results confirm that this approach can successfully identify and analyze dependencies in system designs that would otherwise be very hard to find. More broadly, the methods presented in this paper can help address the growing need for rigorous and practical methods and techniques for assuring the safe, secure, and reliable operation of distributed systems in critical domains.

We describe an automated pipelining approach for optimally balanced pipeline implementation that achieves low area cost as well as meeting timing requirements. Most previous automatic pipelining methods have focused on Instruction Set Architecture (ISA)-based designs and the main goal of such methods generally has been maximizing performance as measured in terms of instructions per clock (IPC). By contrast, we focus on datapath-oriented designs (e.g., DSP filters for image or communication processing applications) in ASIC design flows. The goal of the proposed pipelining approach is to find the optimally pipelined design that not only meets the user-specified target clock frequency, but also seeks to minimize area cost of a given design. Unlike most previous approaches, the proposed methods incorporate the use of accurate area and timing information (iteratively achieved by synthesizing every interim pipelined design) to achieve higher accuracy during design exploration. When compared with exhaustive design exploration that considers all possible pipeline patterns, the two heuristic pipelining methods presented here involve only a small area penalty (typically under 5%) while offering dramatically reduced computational complexity. Experimental validation is performed with commercial ASIC design tools and described for applications including polynomial function evaluation, FIR filters, matrix multiplication, and discrete wavelet transform filter designs with a 90nm standard cell library.

As chip designs become increasingly complex, there is a corresponding increased vulnerability to malicious circuitry that could be inserted in the design process. Such hardware Trojans can be designed to avoid pre-deployment detection, and thus to potentially launch attacks that could impede the function of the system or compromise the integrity of the data it contains. Given the near impossibility of exhaustive detection of malicious hardware during pre-deployment verification, techniques that enable post-deployment hardware integrity verification can play a vital role in system security. In this paper, we propose a system architecture for performing online verification in a manner that does not impede normal system hardware function. The proposed approach provides a comprehensive architectural design method aimed at system on chip (SoC) based hardware systems that performs run-time testing, detects run-time attacks by Trojans, mitigates them, quarantines the detected malicious hardware modules, and regenerates the lost system functions with modest cost.

It is important to acknowledge and address the legitimate challenges that will accompany the growth of domestic unmanned aviation, including privacy and airspace safety. But it is also important not to let those challenges mask the many benefits that unmanned aviation will provide. In the coming years, unmanned aircraft will help save lives after natural disasters. They will help search-and-rescue teams find lost hikers and allow police forces that cannot afford manned helicopters to obtain vital, potentially lifesaving overhead imagery during hostage standoffs. When used safely and in a manner respecting privacy, domestic UAS can become important tools for private citizens, firefighters, scientists, news reporters, filmmakers, and others to more effectively observe the world around them. More broadly, the 21st century will, in many ways, be the century of robotics, and unmanned aircraft will be an important part of that story. A strong robotics industry-and thus a strong unmanned aircraft industry- will be an essential ingredient to economic competitiveness.

We describe a set of design methodologies and experiments related to enabling hardware systems to utilize on-the-fly configuration of reconfigurable logic to recover system operation from unexpected loss of system function. Methods we explore include programming using locally stored configuration bitstream as well as using configuration bitstream transmitted from a remote site. We examine specific ways of utilizing reconfigurable logic to regenerate system function, as well as the effectiveness of this approach as a function of the type of attack, and various architectural attributes of the system. Based on this analysis, we propose architectural features of System-on-Chip (SoC) that can minimize performance degradation and maximize the likelihood of seamless system operation despite the function replacement. This approach is highly feasible in that it is not required to specially manage system software and other normal system hardware functions for the replacement.

We present an analytical framework for modeling a priority-based load balancing scheme in cellular networks based on a new algorithm called direct retry with truncated offloading channel resource pool (DRK). The model, developed for a baseline case of two cell network, differs in many respects from previous works on load balancing. Foremost, it incorporates the call admission process, through random access. In specific, the proposed model implements the Physical Random Access Channel used in 3GPP network standards. Furthermore, the proposed model allows the differentiation of users based on their priorities. The quantitative results illustrate that, for example, cellular network operators can control the manner in which traffic is offloaded between neighboring cells by simply adjusting the length of the random access phase. Our analysis also allows for the quantitative determination of the blocking probability individual users will experience given a specific length of random access phase. Furthermore, we observe that the improvement in blocking probability per shared channel for load balanced users using (DRK) is maximized at an intermediate number of shared channels, as opposed to the maximum number of these shared resources. This occurs because a balance is achieved between the number of users requesting connections and those that are already admitted to the network. We also present an extension of our analytical model to a multicell network (by means of an approximation) and an application of the proposed load balancing scheme in the context of opportunistic spectrum access.

In this paper we propose an analytical framework which allows the investigation of the average channel throughput at the medium access control (MAC) layer for opportunistic spectrum access (OSA) networks with channel bonding enabled. We show that channel bonding is beneficial in certain cases only (e.g. low primary user traffic), though the extent of the benefit depend on the features of the OSA network including secondary network size and the total number of channels available for bonding.

We discuss image or video enlargement methods aimed at computationally constrained environments. Traditional enlargement algorithms such as linear or cubic interpolation have been applied in many applications. However the performance of these approaches is limited by artifacts such as blurring and jagged edges. More sophisticated iterative and learning-based algorithms have been proposed to address these issues, but they typically involve very high computational complexity. We present an adaptive covariance-based edge diffusion (ACED) image enlargement method that offers both good performance and low complexity. Different from other edge-directed interpolation algorithms, the proposed method uses combination of a novel edge-directed judgment which can choose different spread templates adaptively to estimate local covariance coefficients and edge diffusion to reduce artifacts. Experimental results show that the proposed method gives performs well both in terms of subjective quality as well as objective measures.

We describe a highly scalable parallel arithmetic coder for Markov inputs suitable for implementation on modern multi-core processors. The algorithm divides the input into interleaved sub-sequences which can be then processed independently on different processing units using LDPC-based Slepian-Wolf coding. Experimental simulations show good scalability of the proposed algorithm while also maintaining good compression performance. Notably, when compared with traditional parallel arithmetic coding, the proposed method maintains a much higher efficiency both respect to the entropy limit as well as in terms of the ability to distribute computations across multiple cores without performance loss.

The benefits of utilizing the spatial-frequency sensitivity of the human visual system in video coding have been known for decades and are incorporated into video standards, such as MPEG2, MPEG4, and H.264/AVC, as well as into still image-coding standards, such as JPEG and JPEG-2000. However, all of these standards utilize frequency weighting that is adaptive only at the picture level. In contrast with such picture-level adaptive frequency-weighting algorithms, we describe a coding approach in which a macroblock-level adaptive frequency-weighting (MBAFW) algorithm is used. We show that for the bitrate, quality levels, and resolutions typically associated with high-definition video, MBAFW can lead to overall bitrate reductions typically in the 5%–9% range over the methods used in state-of-the-art video-coding standards.

This paper presents designs for both bit-parallel (BP) and digit-serial (DS) precision-optimized implementations of the discrete wavelet transform (DWT), with specific consideration given to the impact of depth (the number of levels of DWT) on the overall computational accuracy. These methods thus allow customizing the precision of a multilevel DWT to a given error tolerance requirement and ensuring an energy-minimal implementation, which increases the applicability of DWT-based algorithms such as JPEG 2000 to energy-constrained platforms and environments. Additionally, quantization of DWT coefficients to a specific target step size is performed as an inherent part of the DWT computation, thereby eliminating the need to have a separate downstream quantization step in applications such as JPEG 2000. Experimental measurements of design performance in terms of area, speed, and power for 90-nm complementary metal-oxide-semiconductor implementation are presented. Results indicate that while BP designs exhibit inherent speed advantages, DS designs require significantly fewer hardware resources with increasing precision and DWT level. A four-level DWT with medium precision, for example, while the BP design is four times faster than the digital-serial design, occupies twice the area. In addition to the BP and DS designs, a novel flexible DWT processor is presented, which supports run-time configurable DWT parameters.

We show that for high bit rates, a video coding algorithm using a suitable combination of the QM coder and on other methods first published over 20 years ago can deliver video quality rivaling that of H.264 at lower complexity. This has implications both technically, since encoders built using these methods can be more power efficient, and commercially, given the complex licensing and intellectual property issues that accompany newer coding methods such as H.264 and MPEG-4. The methods described in this paper are the basis for the recent decision of the MPEG standards group to begin work on what is referred to as the “Type-1 Video Coding” standard, which, in addition to aiming for high coding efficiency, is intended to minimize royalty issues.

Transmission over multiple frequency bands combined into one logical channel speeds up data transfer for wireless networks. On the other hand, the allocation of multiple channels to a single user decreases the probability of finding a free logical channel for new connections, which may result in a network-wide throughput loss. While this relationship has been studied experimentally, especially in the WLAN configuration, little is known on how to analytically model such phenomena. With the advent of Opportunistic Spectrum Access (OSA) networks, it is even more important to understand the circumstances in which it is beneficial to bond channels occupied by primary users with dynamic duty cycle patterns. In this paper we propose an analytical framework which allows the investigation of the average channel throughput at the medium access control layer for OSA networks with channel bonding enabled. We show that channel bonding is generally beneficial, though the extent of the benefits depend on the features of the OSA network, including OSA network size and the total number of channels available for bonding. In addition, we show that performance benefits can be realized by adaptively changing the number of bonded channels depending on network conditions. Finally, we evaluate channel bonding considering physical layer constraints, i.e. throughput reduction compared to the theoretical throughput of a single virtual channel due to a transmission power limit for any bonding size.

In this paper, we first analyze impact of the distribution of sparse signals on reconstruction quality in compressive sensing through experimental results and heuristic analysis. We suggest that trinary/binary sparse signals are one of the most difficult signals to reconstruct in terms of error bounds. We then show that by incorporating linear or non-linear mapping prior to sensing, significant improvement in the recovery performance can be achieved.

While the issue of Trojan ICs has been receiving increasing amounts of attention, the overwhelming majority of anti-Trojan measures aim to address the problem during verification. While such methods are an important part of an overall anti-Trojan strategy, it is statistically inevitable that some Trojans will escape verification-stage detection, in particular in light of the increasing size and complexity of system-on-chip (SoC) solutions and the increasing use of third-party designs. In contrast with much of the previous work in this area, we specifically focus on run-time methods to identify the attacks of a Trojan and to adapt the system and respond accordingly. We describe a solution including a bus architecture in which the arbitration, address decoding, multiplexing, wrapping, and other components protect against malicious use of the bus.

We present two probabilistic estimation techniques for identifying the most likely number of frequency-hopping transmitters for a range of different scenarios and compare their performances. In the first technique, cumulative estimation, a Gaussian approximation methodology is developed based on a single integrated measurement over the observation time window. In the second technique, time-distributed estimation, a maximum-likelihood formulation is adopted, and time-specific observation data is used. We give specific analytical consideration to the potential that not all transmitters that are present will be always detected, and explore the effects of the probability of misdetection on the overall estimation process. Simulation results confirm that the approaches presented here can lead with high probability to a correct decision regarding the number of transmitters.

We describe an image coding algorithm combining the DCT and noiselet information. The algorithm first transmits DCT information sufficient to reproduce a "low-quality" version of the image at the decoder. This image is then used both at the decoder and encoder to create a mutually known list of locations of likely significant noiselet coefficients. The coefficient values themselves are then transmitted to the decoder differentially, by subtracting, at the encoder, the low-quality image from the original image, obtaining the noiselet values and subjecting them to quantization and entropy coding. There remain significant opportunities for further work combining CS-inspired information theoretic techniques with the rate-distortion considerations that are critical in practical image communications.

Summary form only given. This paper has described an improved algorithm for reconstructing sparse binary signals using compressive sensing. The algorithm is based on the reweighted lqnorm optimization algorithm, but with the important additional operation of bounding in each round of the interior-point method iteration, and progressive reduction of q. Experimental results confirm that the algorithm performs well both in terms of the ability to recover an input signal as well as in terms of speed. We also found that both the progressive reduction and the bounding are integral to the improvement in performance. Future work includes extending this approach to Gaussian distributed, as opposed to binary inputs.

We present an analytical framework for modeling a priority-based load balancing scheme in cellular networks. The model differs in many respects from previous work on load balancing, in particular by incorporating the call admission process, through random access; allowing differentiation of users based on their priorities; and by incorporating the received signal properties. The analysis illustrates that, for example, ignoring channel quality has a non- negligible impact on the performance of load balancing. Moreover, the system model allows for the scenario-based determination of whether blocking probability or collision probability (during call admission) is the more dominant factor in the degradation of the performance of UEs affected by load balancing.

Inspired by recent theoretical advances in compressive sensing (CS), we propose a new framework that combines the classical local discrete cosine transform used in image compression algorithms such as JPEG with a global noiselet measure which is solved using second order cone programming (SOCP).

We present an analytical framework for identifying the most likely number of frequency-hopping transmitters in the presence of potential misdetection. The problem is formulated for the case where there is a single, global misdetection probability characterizing all transmitter/sensor links, and for the case where the misdetection probabilities are permitted to be different across the different pairwise transmitter/sensor links. Simulation results confirm that the approach can lead with high probability to a correct decision regarding the number of interferers.

The spectral hash algorithm is one of the round 1 candidates for the SHA-3 family, and is based on spectral arithmetic over a finite field, involving multidimensional discrete Fourier transformations over a finite field, data dependent permutations, rubic-type rotations, and affine and nonlinear functions. The underlying mathematical structures and operations pose interesting and challenging tasks for computer architects and hardware designers to create fast, efficient, and compact ASIC and FPGA realizations. In this paper, we present an efficient hardware architecture for the full 512-bit hash computation using the spectral hash algorithm. We have created a pipelined implementation on a Xilinx Virtex-4 XC4VLX200-11 FPGA which yields 100 MHz and occupies 38,328 slices, generating a throughput of 51.2 Gbps. Our fully parallel synthesized implementation shows that the spectral hash algorithm is about 100 times faster than the fastest SHA-1 implementation, while requiring only about 13 times as many logic slices.

Characterizing the number and type of transmitters occupying a given frequency band is a critical aspect of spectrum sensing specifically and cognitive radio generally. We present an analytical framework based on probability to identify the number of frequency hopping transmitters of one specific type in a band of interest, and show that the probability mass functions associated with the different potential number of transmitters quickly becomes Gaussian as the number of channel observations increases. Simulation results confirm that the approach can lead with high probability to a correct decision regarding the number of interferers. Thus, the methods here can serve as a valuable complement to other spectrum sensing approaches.

Fixed-point processors are utilized in an enormous variety of applications, often for tasks that require the evaluation of mathematical functions. We present an automated method for mapping functions to such processors via polynomials that explicitly targets the native word-length of the processor, thereby significantly reducing the execution time relative to commonly used floating-point emulation approaches based on traditional mathematical libraries. The methods presented here also contrast with hand-tuned processor-specific code, which has the potential to deliver efficient implementations but at the cost of significant design time. We describe an automated design flow utilizing multi-word arithmetic to provide overflow protection and precision accurate to one unit in the last place (ulp). Analytical approaches are used to minimize the number of fixed-width operands required for each operation and to ensure that precision requirements are met. This allows automated generation of processor-optimized code and characterization of a design space representing a rich range of tradeoffs among precision, latency, and memory cost.

One of the most important goals of current and future sensor networks is energy-efficient communication of images. This paper presents a quantitative comparison between the energy costs associated with 1) direct transmission of uncompressed images and 2) sensor platform-based JPEG compression followed by transmission of the compressed image data. JPEG compression computations are mapped onto various resource-constrained platforms using a design environment that allows computation using the minimum integer and fractional bit-widths needed in view of other approximations inherent in the compression process and choice of image quality parameters. Advanced applications of JPEG, such as region of interest coding and successive/progressive transmission, are also examined. Detailed experimental results examining the tradeoffs in processor resources, processing/transmission time, bandwidth utilization, image quality, and overall energy consumption are presented.

This paper presents a method for evaluating functions based on piecewise polynomial approximations (splines) with a hierarchical segmentation scheme targeting hardware implementation. The methodology provides significant reduction in table size compared to traditional uniform segmentation approaches. The use of hierarchies involving uniform splines and splines with size varying by powers of two is particularly well suited for the coverage of nonlinear regions. The segmentation step is automated and supports user-supplied precision requirements and approximation method. Bit-widths of the coefficients and arithmetic operators are optimized to minimize circuit area and enable a guarantee of 1 unit in the last place (ulp) accuracy at the output. A coefficient transformation technique is also described, which significantly reduces the dynamic ranges of the fixed-point polynomial coefficients. The hierarchical segmentation method is illustrated using a set of functions including -(x/2) log2x, cos-1(x), radic(-ln(x)) , a high-degree rational function, ln(1+x), and 1/(1+x). Various degree-1 and degree-2 approximation results for precisions between 8 to 24 bits are given. Hardware realizations are demonstrated on a Xilinx Virtex-4 field-programmable gate array (FPGA).

Femtocells are low-power, very small-service-area (e.g. home or office environment) cellular base stations that will significantly impact the cellular landscape in the next several years. One of the most important open technical issues related to femtocells concerns the impact on system performance of different policies regarding who is allowed to connect to a femtocell. In the present paper, interaction between mobile stations (MS) that are near to, but not necessarily communicating with, femtocells is explored. It is shown that an adaptive femtocell access policy that takes specific account of the instantaneous loads on the network can lead to improved performance over a completely open, or completely closed approach.

We explore the performance and hardware complexity tradeoffs associated with performing iterative multiple- input multiple-output (MIMO) detection using a sphere decoder and a low-density parity-check (LDPC) decoder. Iterations are performed both within the LDPC decoder as well as via an outer iteration loop through which refined soft information is fed back from the LDPC decoder to a MIMO detector. A hardware architecture and associated implementation results on Xilinx Virtex-5 field programmable gate array for a 4 x 4 QPSK MIMO system are presented. The system offers a performance improvement of approximately 1 dB over systems without the outer iteration loop, and provides an information bit throughput that ranges from 60 to 300 megabits per second when a length 1944 rate 1/2 LDPC code is used.

This paper examines the hardware implementation tradeoffs when evaluating functions via piecewise polynomial approximations and interpolations for precisions up to 24 bits. In polynomial approximations, polynomials are evaluated using stored coefficients. Polynomial interpolations, however, require the coefficients to be computed on-the-fly using stored function values. Although it is known that interpolations require less memory than approximations at the expense of additional computation, the tradeoffs in memory, area, delay, and power consumption between the two approaches have not been examined in detail. This work quantitatively analyzes these tradeoffs for optimized approximations and interpolations across different functions and target precisions. Hardware architectures for degree-1 and degree-2 approximations and interpolations are described. The results show that the extent of memory savings realized by using interpolation is significantly lower than what is commonly believed. Furthermore, experimental results on a field-programmable gate array (FPGA) show that for high output precision, degree-1 interpolations offer considerable area and power savings over degree-1 approximations, but similar savings are not realized when degree-2 interpolations and approximations are compared. The availability of both interpolation-based and approximation-based designs offers a richer set of design tradeoffs than is available using either interpolation or approximation alone.

A new set of programmable elements (PEs) using a new non-volatile device for use with routing switches and logical elements within a field-programmable gate array (FPGA) is described. The PEs have small area, can be combined with components that use low operational voltage on the same CMOS logic process, are non-volatile, enable the use of fast thin-oxide pass transistors, and are reprogrammable. A novel non-volatile flip-flop for use within the logical elements is presented as well. In combination, these methods enable programmable logic devices with improved area efficiency, the speed advantages of SRAM-based FPGAs, and a wide range of opportunities for power down strategies.

Energy-efficient image communication is one of the most important goals for a large class of current and future sensor network applications. This paper presents a quantitative comparison between the energy costs associated with 1) direct transmission of uncompressed images and 2) sensor platform-based JPEG compression followed by transmission of the compressed image data. JPEG compression computations are mapped onto various resource-constrained sensor platforms using a design environment that allows computation using the minimum integer and fractional bit-widths needed in view of other approximations inherent in the compression process and choice of image quality parameters. Detailed experimental results examining the tradeoffs in processor resources, processing/transmission time, bandwidth utilization, image quality, and overall energy consumption are presented.

An uncompressed Digital Cinema Distribution Master (DCDM) image typically has dimensions of up to 4096x2160 (4K) or 2048x1080 (2K) with 12-bit pixel data for each of the X'Y'Z' color planes. At a frame rate of 24 frames per second, this gives uncompressed data rates of 7.6 and 1.9 Gbps for 4K and 2K respectively. Even after compression, average data rates in the hundreds of Mbits/sec. are encountered. Recently, the Society of Motion Picture and Television Engineers' (SMPTE) has chosen JPEG2000 as the standard to be used for digital cinema compression. Thus, methods to appropriately trade off rate and quality for JPEG2000-compressed movies will have high importance in the next several years as systems are designed and deployed. In this paper we describe a new distortion-based framework for rate control that enables a JPEG2000 encoder to achieve a user-specified quality, and therefore makes it possible to produce constant quality from frame-to-frame in an image sequence. The new method makes direct use of the same JPEG2000 coding pass data as the traditional approaches, and thus can easily be adopted at the back end of JPEG2000 encoding engines. We compare the new method with two other common rate control techniques for JPEG2000.

We present an automated bit-width optimization methodology for polynomial-based hardware function evaluation. Due to the analytical nature of the approach, overflow protection and precision accurate to one unit in the last place (ulp) can be guaranteed. A range analysis technique based on computing the root of the derivative of a signal is utilized to determine the minimal number of integer bits. Fractional bit requirements are established using an analytical error expression derived from the functions that occur along the data path. Global fractional bit optimization across multiple computation stages is performed using simulated annealing and circuit area estimation functions

Root and Varaiya proved the existence of a code that can communicate reliably over any linear Gaussian channel for which the channel mutual information level exceeds the transmitted rate. This paper provides several examples of scalar (single-input single-output) fading channels and shows that on these channels the performance of low-density parity-check (LDPC) codes lies in close proximity to the performance limits identified by Root and Varaiya. Specifically, we consider periodic fading channels and partial-band jamming (PBJ) channels. A special case of periodic fading is the variation of signal-to-noise ratio across orthogonal frequency division modulation subchannels. The robustness of LDPC codes to periodic fading and PBJ across parameterizations of these different channels is demonstrated through the consistency of the required mutual information to provide a specified bit error rate. For the periodic fading case, the Gaussian approximation to density evolution has been adapted such that asymptotic threshold measures can be compared to simulated code performance in various periodic fading scenarios

We present an automated methodology for producing hardware-based random number generator (RNG) designs for arbitrary distributions using the inverse cumulative distribution function (ICDF). The ICDF is evaluated via piecewise polynomial approximation with a hierarchical segmentation scheme that involves uniform segments and segments with size varying by powers of two which can adapt to local function nonlinearities. Analytical error analysis is used to guarantee accuracy to one unit in the last place (ulp). Compact and efficient RNGs that can reach arbitrary multiples of the standard deviation sigma can be generated. For instance, a Gaussian RNG based on our approach for a Xilinx Virtex-4 XC4VLX100-12 field-programmable gate array produces 16-bit random samples up to 8.2 sigma. It occupies 487 slices, 2 block-RAMs, and 2 DSP-blocks. The design is capable of running at 371 MHz and generates one sample every clock cycle.

We present a flexible hardware architecture for precise gamma correction via piece-wise linear polynomial approximations. Arbitrary gamma values, input bit widths, and output bit widths are supported. The gamma correction curve is segmented via a combination of uniform segments and segments whose sizes vary by powers of two. This segmentation method minimizes the number of segments required, while providing an efficient way for indexing the polynomial coefficients. The outputs are guaranteed to be accurate to one unit in the last place through an analytical bit-width analysis methodology. Hardware realizations of various gamma correction designs are demonstrated on a Xilinx Virtex-4 field-programmable gate array (FPGA). A pipelined 12-bit input/8-bit output design on an XC4VLX100-12 FPGA occupies 146 slices and one digital signal processing slice. It is capable of performing 378 million gamma correction operations per second.

We present the design and implementation of a Gaussian random number generator (GRNG) via hierarchical segmentation. Gaussian samples are generated using the inversion method, which involves the evaluation of the inverse Gaussian cumulative distribution function (IGCDF). The IGCDF is highly nonlinear and is evaluated via piecewise polynomial approximations (splines) with a hierarchical segmentation scheme that involves uniform splines and splines with size varying by powers of two. This segmentation approach adapts the spline sizes according to the non-linearity of the function, allowing efficient evaluation of the IGCDF. Bit-widths of the fixed-point polynomial coefficients and arithmetic operators are optimized in an analytical manner to guarantee a precision accurate to one unit in the last place. Our architecture generates 16-bit Gaussian samples accurate to 8.2cr (standard deviations). A pipelined implementation on a Xilinx Virtex-4 XC4LX100-12 FPGA yields 371 MHz and occupies 543 slices, 2 block RAMs, and 2 DSP slices, generating one sample every clock cycle

We present a new approach to variable bit rate (VBR) video traffic modeling designed to capture the multi- scale characteristics that are critical in determining buffering requirements. Much of the previous work in video traffic modeling has focused on real-time multimedia systems that of necessity involve queuing models with small buffers. Today there is growing interest in understanding systems in which high quality video is downloaded in non-real-time from a source such as the Internet, and then distributed at a later time in a local environment to a very low-cost and thus resource-constrained device. Smooth playback and avoidance of data loss are of paramount importance. The work here analyzes the tradeoffs between buffering resources and the video quality in such environments, and provides a framework that is directly relevant to a large class of emerging applications and systems.

Binary arithmetic coding involves recursive partitioning the range [0,1) in accordance with the relative probabilities of occurrence of the two input symbols. We describe a modification of this approach in which the overall length within the range [0,1) allocated to each symbol is preserved, but the traditional assumption that a single contiguous interval is used for each symbol is removed. A key known to both the encoder and decoder is used to describe where the intervals are "split" prior to encoding each new symbol. The repeated splitting has the effect of both scrambling the intervals and altering their lengths, thereby allowing both encryption and compression to be obtained simultaneously.

We present a hardware Gaussian noise generator based on the Box-Muller method that provides highly accurate noise samples. The noise generator can be used as a key component in a hardware-based simulation system, such as for exploring channel code behavior at very low bit error rates, as low as 10-12to 10-13. The main novelties of this work are accurate analytical error analysis and bit-width optimization for the elementary functions involved in the Box-Muller method. Two 16-bit noise samples are generated every clock cycle and, due to the accurate error analysis, every sample is analytically guaranteed to be accurate to one unit in the last place. An implementation on a Xilinx Virtex-4 XC4VLX100-12 FPGA occupies 1,452 slices, three block RAMs, and 12 DSP slices, and is capable of generating 750 million samples per second at a clock speed of 375 MHz. The performance can be improved by exploiting concurrent execution: 37 parallel instances of the noise generator at 95 MHz on a Xilinx Virtex-II Pro XC2VP100-7 FPGA generate seven billion samples per second and can run over 200 times faster than the output produced by software running on an Intel Pentium-4 3 GHz PC. The noise generator is currently being used at the Jet Propulsion Laboratory, NASA to evaluate the performance of low-density parity-check codes for deep-space communications

An architecture and implementation of a high performance Gaussian random number generator (GRNG) is described. The GRNG uses the Ziggurat algorithm which divides the area under the probability density function into three regions (rectangular, wedge and tail). The rejection method is then used and this amounts to determining whether a random point falls into one of the three regions. The vast majority of points lie in the rectangular region and are accepted to directly produce a random variate. For the nonrectangular regions, which occur 1.5% of the time, the exponential or logarithm functions must be computed and an iterative fixed point operation unit is used. Computation of the rectangular region is heavily pipelined and a buffering scheme is used to allow the processing of rectangular regions to continue to operate in parallel with evaluation of the wedge and tail computation. The resulting system can generate 169 million normally distributed random numbers per second on a Xilinx XC2VP3O-6 device.

Array codes are error-correcting codes of very low complexity that were initially used for burst and erasure correction in redundant arrays of inexpensive disks (RAID) architectures and other storage applications. The structure of these codes allows a very simple encoding and decoding mechanism. Although they are very high-rate codes, they do not achieve the maximum possible rate given their design constraints. In fact Hamming codes maximize the possible rate given these design constraints. This paper compares the rate and complexity of array codes when compared to Hamming codes.

We describe a hardware Gaussian noise generator based on the Wallace method used for a hardware simulation system. Our noise generator accurately models a true Gaussian probability density function even at high /spl sigma/ values. We evaluate its properties using: 1) several different statistical tests, including the chi-square test and the Anderson-Darling test and 2) an application for decoding of low-density parity-check (LDPC) codes. Our design is implemented on a Xilinx Virtex-II XC2V4000-6 field-programmable gate array (FPGA) at 155 MHz; it takes up 3% of the device and produces 155 million samples per second, which is three times faster than a 2.6-GHz Pentium-IV PC. Another implementation on a Xilinx Spartan-III XC3S200E-5 FPGA at 106 MHz is two times faster than the software version. Further improvement in performance can be obtained by concurrent execution: 20 parallel instances of the noise generator on an XC2V4000-6 FPGA at 115 MHz can run 51 times faster than software on a 2.6-GHz Pentium-IV PC.

We describe a flexible hardware encoder for regular and irregular low-density parity-check (LDPC) codes. Although LDPC codes achieve better performance and lower decoding complexity than turbo codes, a major drawback of LDPC codes is their apparently high encoding complexity. Using an efficient encoding method proposed by Richardson and Urbanke, we present a hardware LDPC encoder with linear encoding complexity. The encoder is flexible, supporting arbitrary H matrices, rates and block lengths. An implementation for a rate 1/2 irregular length 2000 LDPC code encoder on a Xilinx Virtex-II XC2V4000-6 FPGA takes up 4% of the device. It runs at 143 MHz and has a throughput of 45 million codeword bits per second (or 22 million information bits per second) with a latency of 0.18 ms. The performance can be improved by exploiting parallelism: several instances of the encoder can be mapped onto the same chip to encode multiple message blocks concurrently. An implementation of 16 instances of the encoder on the same device at 82 MHz is capable of 410 million codeword bits per second, 80 times faster than an Intel Pentium-lV 2.4 GHz PC.

Rate-compatible coding is appropriate for communication systems that experience a range of operating SNRs but seek to adhere to a single underlying codec structure. This paper constructs rate-compatible low-density parity-check (LDPC) codes by carefully selecting degree distributions, followed by a combination of information nulling and parity puncturing. Techniques that suppress error floors are included as part of the construction methodology.

Hardware simulation offers the potential of improving code evaluation speed by orders of magnitude over workstation or PC-based simulation. We describe a hardware-based Gaussian noise generator used as a key component in a hardware simulation system, for exploring channel code behavior at very low bit error rates (BERs) in the range of 10/sup -9/ to 10/sup -10/. The main novelty is the design and use of nonuniform piecewise linear approximations in computing trigonometric and logarithmic functions. The parameters of the approximation are chosen carefully to enable rapid computation of coefficients from the inputs while still retaining high fidelity to the modeled functions. The output of the noise generator accurately models a true Gaussian Probability Density Function (PDF) even at very high /spl sigma/ values. Its properties are explored using: 1) several different statistical tests, including the chi-square test and the Anderson-Darling test, and 2) an application for decoding of low-density parity-check (LDPC) codes. An implementation at 133 MHz on a Xilinx Virtex-II XC2V4000-6 FPGA produces 133 million samples per second, which is seven times faster than a 2.6 GHz Pentium-IV PC; another implementation on a Xilinx Spartan-IIE XC2S300E-7 FPGA at 62 MHz is capable of a three times speedup. The performance can be improved by exploiting parallelism: an XC2V4000-6 FPGA with nine parallel instances of the noise generator at 105 MHz can run 50 times faster than a 2.6 GHz Pentium-IV PC. We illustrate the deterioration of clock speed with the increase in the number of instances.

This letter explains the effect of graph connectivity on error-floor performance of low-density parity-check (LDPC) codes under message-passing decoding. A new metric, called extrinsic message degree (EMD), measures cycle connectivity in bipartite graphs of LDPC codes. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids small cycle clusters that are isolated from the rest of the graph. This algorithm is different from conventional girth conditioning by emphasizing the connectivity as well as the length of cycles. The algorithm yields codes with error floors that are orders of magnitude below those of random codes with very small degradation in capacity-approaching capability.

Hardware simulation of channel codes offers the potential of improving code evaluation speed by orders of magnitude over workstation of PC-based simulation. We describe a hardware-based Gaussian noise generator used as a key component in a hardware simulation system, for exploring channel code behavior at very low bit error rates (BERs) in the range of 10/sup -9/ to 10/sup -10/. The main novelty is the design and use of nonuniform piecewise linear approximations in computing trigonometric and logarithmic functions. The parameters of the approximation are chosen carefully to enable rapid computation of coefficients from the inputs, while still retaining extremely high fidelity to the modeled functions. The output of the noise generator accurately models a true Gaussian PDF even at very high /spl sigma/ values. Its properties are explored using: (a) several different statistical tests, including the chi-square test and the Kolmogorov-Smirnov test, and (b) an application for decoding of low density parity check (LDPC) codes. An implementation at 133MHz on a Xilinx Virtex-II XC2V4000-6 FPGA produces 133 million samples per second, which is 40 times faster than a 2.13GHz PC; another implementation on a Xilinx Spartan-IIE XC2S300E-7 FPGA at 62MHz is capable of a 20 times speedup. The performance can be improved by exploiting parallelism: an XC2V4000-6 FPGA with three parallel instances of the noise generator at 126 MHz can run 100 times faster than a 2.13GHz PC. We illustrate the deterioration of clock speed with the increase in the number of instances.

This paper presents a method for evaluating functions based on piecewise polynomial approximation with a novel hierarchical segmentation scheme. The use of a novel hierarchy scheme of uniform segments and segments with size varying by powers of two enables us to approximate non-linear regions of a function particularly well. This partitioning is automated: efficient look-up tables and their coefficients are generated for a given function, input range, order of the polynomials, desired accuracy and finite precision constraints. We describe an algorithm to find the optimum number of segments and the placement of their boundaries, which is used to analyze the properties of a function and to benchmark out approach. Our method is illustrated using three non-linear compound functions, /spl radic/-log(x), x log(x) and a high order rational function. We present results for various operand sizes between 8 and 24 bits for first and second order polynomial approximations.

This work explains the relationship between cycles, stopping sets, and dependent columns of the parity check matrix of low-density parity-check (LDPC) codes. Furthermore, it discusses how these structures limit LDPC code performance under belief propagation decoding. A new metric called extrinsic message degree (EMD) measures cycle connectivity in bipartite graph. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids cycles and increases stopping set size. This algorithm yields codes with error floors that are orders of magnitude below those of girth-conditional codes.

We present two decoding structures which combine turbo detection and decoding, allowing communication in the presence of intersymbol interference (ISI). The first one treats the ISI as another constituent decoder which participates in the exchange of extrinsic information, and performs slightly worse than the second structure, which combines the trellis representing each one of the constituent encoders with the ISI trellis. We show that for both methods, it is possible to obtain good performance, even when no a priori information about the ISI channel is available to the decoder.

Root and Variya (1968) proved the existence of codes that can communicate reliably over any member of a set of linear Gaussian channels where each member exceeds a given amount of mutual information. In this paper we show that LDPC codes are such codes and that their performance lies within 0.1 bits of the Root and Variya capacity for a large family of periodic Gaussian channels. specifically, the robustness of LDPC codes to periodic fading is demonstrated through the consistency of their mutual information performance across period-2 and period-256 fading profiles. The latter case implies that these codes are ideal candidates for coding in OFDM.

We propose a joint source-channel coding system which utilizes turbo codes and reversible variable length codes (RVLCs). Particular attention is given to the construction of RVLCs with good error-correcting properties, in order to assure good performance in the error floor region. Furthermore, we design an iterative joint source-channel decoder, which exhibits decoding convergence at a low signal-to-noise ratio (SNR). The proposed system exhibits superior performance at all SNR levels, relative to a standard system that involves turbo codes and Huffman codes.

We describe parallel concatenated codes for communication over finite-state binary Markov channels. We present encoder design techniques and decoder processing modifications that utilize the a priori statistics of the channel and show that the resulting codes allow reliable communication at rates which are above the capacity of a memoryless channel with the same stationary bit error probability as the Markov channel. These codes outperform systems based on the traditional approach of using a channel interleaver to create a channel which is assumed to be memoryless. In addition, we introduce a joint estimation/decoding method that allows the estimation of the parameters of the hidden Markov model when they are not known a priori.

We present a method for utilizing soft information in decoding of variable length codes (VLCs). When compared with traditional VLC decoding, which is performed using "hard" input bits and a state machine, the soft-input VLC decoding offers improved performance in terms of packet and symbol error rates. Soft-input VLC decoding is free from the risk, encountered in hard decision VLC decoders in noisy environments, of terminating the decoding in an unsynchronized state, and it offers the possibility to exploit a priori knowledge, if available, of the number of symbols contained in the packet.

To achieve more efficient usage of channel bandwidth and provide better protection for the media payload transmitted over lossy packet-switched networks, we introduce a new scheme of generic uneven level protection (ULP) forward error correction. The scheme provides different protection levels for data of different significance within a packet. The ULP scheme is designed to be independent from the nature of the media that it protects, and it is very flexible for any protection configuration the user might need without using any out-of-band signaling. Simulation using a video stream transmitted over a lossy packet-switched network shows that the ULP algorithm achieves significant gain for the quality of the transmission over a wide range of network conditions.

We describe a joint source-channel scheme for modifying a turbo decoder in order to exploit the statistical characteristics of hidden Markov sources. The basic idea is to treat the trellis describing the hidden Markov source as another constituent decoder which exchanges information with the other constituent decoder blocks. The source block uses as extrinsic information the probability of the input bits that is provided by the constituent decoder blocks. On the other hand, it produces a new estimation of such a probability which will be used as extrinsic information by the constituent turbo decoders. The proposed joint source-channel decoding technique leads to significantly improved performance relative to systems in which source statistics are not exploited and avoids the need to perform any explicit source coding prior to transmission. Lack of a priori knowledge of the source parameters does not degrade the performance of the system, since these parameters can be jointly estimated with turbo decoding.

Low bit-rate multimedia communication over wireless channels has received much attention recently. A key challenge in low bit-rate wireless communication is the very high error rate during transmission. This demands error resilient services that exhibit graceful performance degradation while operating in a highly noisy channel. Among video, audio and other multimedia communication modalities, we focus on the error-resilient transmission of video signals over wireless channels in this paper. Specifically, efforts in developing H.263++ Annex V error resilient data partitioning with reversible variable length code (RVLC) are described in detail. The performance over error-prone channels is analyzed and the effectiveness of the syntax is demonstrated with extensive simulations.

We describe a trellis-based algorithm which enables R-D optimum quantization decisions in the H.263+ video coding standard. The use of the trellis allows the quantization decisions for all coefficients in a block to be made jointly, and contrasts with more commonly used R-D optimizations which operate on one coefficient at a time. Experiments conducted using H.263+ for video coding rates of 40-50 kbps show an average improvement of 3.5% in bit rate, or equivalently 0.17 dB in PSNR, relative to implementations which follow the International Telecommunications Union (ITU) Test Model specifications in making quantization decisions.

By constructing a model which takes into account the frame dependence of multimedia streams, we analyze the performance of different packet dropping mechanisms and find that scalable video combined with the priority dropping mechanism can bring higher throughput, lower delay and lower delay jitter. We also find the optimum system parameters for multimedia transmission. This study is important for achieving better performance for video transmission over IP networks.

An adaptive block based intra refresh algorithm for increasing error robustness in an interframe coding system is described. The goal of this algorithm is to allow the intra update rates for different image regions to vary according to various channel conditions and image characteristics. The update scheme is based on an "error-sensitivity metric," accumulated at the encoder, representing the vulnerability of each coded block to channel errors. As each new frame is encoded, the accumulated metric for each block is examined, and those blocks deemed to have an unacceptably high metric are sent using intra coding as opposed to inter coding. This approach requires no feedback channel and is fully compatible with H.263. It involves a negligible increase in encoder complexity and no change in the decoder complexity. Simulations performed using an H.263 bitstream corrupted by channel errors demonstrate a significant improvement in terms of error recovery time over nonadaptive intra update strategies.

We describe a trellis-based algorithm which enables R-D optimum quantization decisions in the H.263+ video coding standard. The algorithm allows the quantization decisions for all coefficients in a block to be made jointly, and experiments conducted using H.263+ for video coding rates of 40-50 kbps show an average improvement of 3.5% in bitrate relative to implementations which follow the International Telecommunications Union (ITU) Test Model specifications in making quantization decisions.

We present a method for utilizing soft information in decoding of variable length codes (VLCs). When compared with traditional VLC decoding, which is performed using "hard" input bits and a state machine, soft-input VLC decoding offers improved performance in terms of packet and symbol error rates. Soft-input VLC decoding is free from the risk, encountered in hard decision VLC decoders in noisy environments, of terminating the decoding in an unsynchronized state, and it offers the possibility to exploit a priori knowledge, if available, of the number of symbols contained in the packet.

This paper presents a method, called multiple constant multiplier trees (MCMTs), for producing optimized reconfigurable hardware implementations of vector products. An algorithm for generating MCMTs has been developed and implemented, which is based on a novel representation of common subexpressions in constant data patterns. Our optimization framework covers a wider solution space than previous approaches; it also supports exploitation of full and partial run-time reconfiguration as well as technology-specific constraints, such as fanout limits and routing. We demonstrate that while distributed arithmetic techniques require storage size exponential in the number of coefficients, the resource utilization of MCMTs usually grows linearly with problem size. MCMTs have been implemented in Xilinx 4000 and Virtex FPGAs, and their size and speed efficiency are confirmed in comparisons with Xilinx LogiCore and ASIC implementations of FIR filter designs. Preliminary results show that the size of MCMT circuits is less than half of that of comparable distributed arithmetic cores.

This paper presents on-line arithmetic structures tailored for use in the FFT and DCT. Due to their small size, several of these modules can be connected together to form larger, more powerful blocks. The digit-serial nature of on-line arithmetic allows valuable pin resources to feed a larger number of arithmetic units than in the conventional case. Additionally, the resolution of the most significant digit first a property of on-line arithmetic allows subsequent calculations to occur at a much earlier stage. As such, performance of the FFT and DCT benefit over conventional and traditional digit-serial FPGA implementations.

Wireless video communication is particularly challenging because it combines the already difficult problem of efficient compression with the additional and usually contradictory need to make the compressed bit stream robust to channel errors. We describe design and implementation strategies for error-robust video communications with an emphasis on techniques compatible with the coding approaches used in the ISO (MPEG-4) and ITU standards organizations. These techniques include modifications to the video coding algorithms as well as to the system layers that perform packetization and multiplexing.

The highly peaked wide-tailed pdf's that are encountered in many image coding algorithms are often modeled using the family of generalized Gaussian (GG) pdf's. We study entropy coding of quantized GG sources using prefix codes that are highly structured, and which therefore involve low computational complexity. We provide bounds for the redundancy associated with applying these codes to quantized GG sources. We also explore code efficiency and code choice for a wide range of GG source and quantizer parameters.

We describe techniques for joint source-channel coding of hidden Markov sources using a modified turbo decoding algorithm. This avoids the need to perform any explicit source coding prior to transmission, and instead allows the decoder to utilize the a priori structure due to the hidden Markov source. In addition, we present methods that allow the decoder to estimate the parameters of the Markov model. In combination, these techniques allow the decoder to identify, estimate, and exploit the source structure. The estimation does not degrade the performance of the system, i.e. the joint estimation/decoding allows convergence at the same noise levels as a system in which the decoder has perfect a priori knowledge of the source parameters.

The International Telecommunications Union (ITU) has adopted reversible variable length codes (RVLCs) for use in the emerging H.263+ video compression standard. As the name suggests, these codes can be decoded in two directions and can therefore be used by a decoder to enhance robustness in the presence of transmission bit errors. In addition, these RVLCs involve little or no efficiency loss relative to the corresponding non-reversible variable length codes. We present the ideas behind two general classes of RVLCs and discuss the results of applying these codes in the framework of the H.263+ and MPEG-4 video coding standards.

We describe parallel concatenated codes for communication over binary-input, binary-output hidden Markov channels. We present encoder design techniques and decoder processing modifications that utilize the a priori statistics of the channel and show that the resulting codes allow reliable communication at rates which are above the capacity of a memoryless channel with the same stationary bit error probability as the Markov channel. These codes outperform systems based on the traditional approach of using a channel interleaver to create a channel which is assumed to be memoryless. In addition, we introduce a joint estimation/decoding method that allows the estimation of the parameters of the Markov model when they are not known a priori.

We use the framework of Bayesian networks to introduce generalizations of the traditional turbo decoding algorithm. We show that traditional turbo decoding represents one of many ways in which the framework of Pearl's belief propagation algorithm (1988) can be applied for decoding of turbo codes. Simulation results show that a noisy received block which does not converge using traditional turbo decoding can converge to the correct value with one or more of the generalizations introduced here. Though we consider only the case of turbo codes with two constituent decoders here, these methods can be extended in a straightforward manner to codes with larger numbers of constituent decoders.

We present an analytical framework for describing the distortion in an image communication system that includes wavelet transformation, uniform scalar quantization, run length coding, entropy coding, forward error control, and transmission over a binary symmetric channel. Simulations performed using ideal source models as well as real image subbands confirm the accuracy of the distortion description. The resulting equations can be used to choose channel code rates in an unequal error protection scheme in which subbands are protected according to their importance.

We describe the methodology and results of parameter optimizations performed with the aid of analytical expressions for the channel-induced distortion in a wavelet-based image communication system. R(D) curves are calculated independently for each subband, with each point on each curve representing (in addition to rate and distortion) an optimal choice of quantizer step size and channel code rate. A global optimization procedure is then performed to identify the best operating point on the R(D) curve for each subband.

We describe a class of parameterized reversible variable length codes that have length distributions identical to Golomb-Rice codes and exp-Golomb codes. The pdfs to which these codes correspond are well matched to statistics of image and video data, thus enabling an increase in robustness to channel errors with no penalty in coding efficiency. These codes are applicable to MPEG-4 and other algorithms that aim to use variable length codes in error-prone environments.

We present here design techniques for trellis-coded vector quantizers with symmetric codebooks that facilitate low-complexity quantization as well as partitioning into equiprobable sets for trellis coding. The quantization performance of this coder on the independently identically distributed (i.i.d.) Laplacian source matches the performance of trellis-based scalar-vector quantization (TB-SVQ), but requires less computational complexity.

Convolutional codes based on Hadamard sequences can achieve both orthogonality and variable rate. In contrast with other convolutional coding techniques, these codes incur no processing gain penalty in direct-sequence code-division multiple-access (DS-CDMA) systems. We describe a class of such codes called "telescopic protection codes". These codes enable variable-rate error protection in the manner of rate-compatible punctured-convolutional (RCPC) codes, but preserve the Hadamard orthogonality properties necessary to maintain processing gain that RCPC codes lack.

The discrete wavelet transform (DWT) decomposes an image into bands that vary in spatial frequency and orientation. It is widely used for image compression. Measures of the visibility of DWT quantization errors are required to achieve optimal compression. Uniform quantization of a single band of coefficients results in an artifact that we call DWT uniform quantization noise; it is the sum of a lattice of random amplitude basis functions of the corresponding DWT synthesis filter. We measured visual detection thresholds for samples of DWT uniform quantization noise in Y, Cb, and Cr color channels. The spatial frequency of a wavelet is r 2-lambda, where r is display visual resolution in pixels/degree, and lambda is the wavelet level. Thresholds increase rapidly with wavelet spatial frequency. Thresholds also increase from Y to Cr to Cb, and with orientation from lowpass to horizontal/vertical to diagonal. We construct a mathematical model for DWT noise detection thresholds that is a function of level, orientation, and display visual resolution. This allows calculation of a "perceptually lossless" quantization matrix for which all errors are in theory below the visual threshold. The model may also be used as the basis for adaptive quantization schemes.

Many important sources of data including sub-band image and speech coefficients are highly peaked and can be well-modeled by the family of generalized Gaussian (GG) PDFs parameterized by a shape parameter /spl nu/. We present here algorithms for defining and quantizing to a Z lattice in which the boundary is optimized to the characteristics of GG sources, and show that these techniques lead to high performance and low complexity for bit rates and dimensions that are of interest in a number of practical coding applications. We derive an analytical description of the granular and overload distortion valid for low and moderate bit rates, and also provide a description of quantizer performance in the limit of high rate and dimension.

Trellis coded vector quantization is known to offer a good rate-distortion performance, but at a considerable (and sometimes prohibitive) complexity cost. We present design techniques for vector quantizers with highly symmetric codebooks that facilitate low complexity quantization as well as partitioning into equiprobable sets for trellis coding. The quantization performance of this coder on the Laplacian source matches the performance of trellis based scalar-vector quantization, the best fixed-wordlength quantizer thus far reported, but requires less computational complexity. Furthermore, this coder is well-suited for use in joint source/channel coding systems where the codeword locations and labeling are chosen to minimize the effects of channel errors.

Seismic data have a number of unique characteristics that differentiate them from the still image and video data that are the focus of most lossy coding research efforts. Seismic data occupy three or four dimensions, and have a high degree of anisotropy with substantial amounts of noise. Two-dimensional coding approaches based on wavelets or the DCT achieve only modest compression ratios on such data because of these statistical properties, and because 2D approaches fail to fully leverage the redundancy in the higher dimensions of the data. We describe here a wavelet-based algorithm that operates directly in the highest dimension available, and which has been used to successfully compress geophysical data with no observable loss of geophysical information at compression ratios substantially greater than 100:1. This algorithm was successfully field tested on a vessel in the North Sea in July 1995, demonstrating the feasibility of performing on-board real-time compression and satellite downloading from marine seismic data acquisition platforms.

FPGAs can be used to build systems for automatic target recognition (ATR) that achieve an order of magnitude increase in performance over systems built using general purpose processors. This improvement is possible because the bit-level operations that comprise much of the ATR computational burden map extremely efficiently into FPGAs, and because the specificity of ATR target templates can be leveraged via fast reconfiguration. We describe here algorithms, design tools, and implementation strategies that are being used in a configurable computing system for ATR.

The ITU-T low-bit-rate video coding standard H.263 supports efficient transmission of digital video over narrow-band telecommunication channels. The standard provides an excellent framework for low bit rate video coding, and leaves substantial design flexibility for tasks such as motion estimation to the implementer. We propose an alternative to the sum of absolute difference (SAD) metric that is used as the criterion for identifying motion vectors in many video coding implementations. The SAD usually fails to identify the rate-distortion optimal motion vector for a block because it does not take into account of the number of bits used to code the motion vector. One solution which has been proposed in the past is to use the Lagrangian cost J=D+/spl lambda/R as the cost function in motion estimation. This allows near optimal motion vector search in the rate-distortion sense but is too complex to be used in a practical video coding system. We present an alternative motion estimation algorithm that considers rate-distortion trade-offs in a low complexity framework, resulting in both a higher coding efficiency and a faster encoding speed.

An algorithm for increasing error robustness in an H.263 video coding system in the absence of a feedback channel is proposed. For each 16/spl times/16 macroblock, the encoder accumulates a metric representing the vulnerability to channel errors. As each new frame is encoded, the accumulated metric for each block is examined, and those blocks deemed to have an unacceptably high metric are sent using intra as opposed to inter coding. This approach is fully compatible with H.263 and involves a negligible increase in encoder complexity and no change in the decoder complexity. Simulations performed using an H.263 bitstream corrupted by channel errors demonstrate a significant improvement over non-adaptive intra update strategies.

We describe a new image coding approach in which a 4-ary arithmetic coder is used to represent significant coefficient values and the lengths of zero runs between coefficients. This algorithm works by raster scanning within subbands, and therefore involves much lower addressing complexity than other algorithms such as zerotree coding that require the creation and maintenance of lists of dependencies across different decomposition levels. Despite its simplicity, and the fact that these dependencies are not explicitly utilized, the algorithm presented here is competitive with the best enhancements of zerotree coding. In addition, it performs comparably with adaptive subband splitting approaches that involve much higher implementation complexity.

Lattice vector quantization schemes offer high coding efficiency without the burden associated with generating and searching a codebook. The distortion associated with a given lattice is often expressed in terms of the G number, which is a measure of the mean square error per dimension generated by quantization of a uniform source. Subband image coefficients, however, are best modeled by a generalized Gaussian, leading to distortion characteristics that are quite different from those encountered for uniform, Laplacian, or Gaussian sources. We present here the distortion associated with Z, E/sub 8/, and Leech lattice quantization for coding of generalized Gaussian sources, and show that for low bit rates the Z lattice offers both the best performance and the lowest implementational complexity.

Video coding has been implemented by using rapid reconfiguration to time-share hardware for several sequential stages. This allows the number of gates to be reduced by a factor proportional to the number of coding stages at the expense of some reconfiguration overhead and the added memory and control needed to implement reconfiguration. The results of this work suggest that run-time reconfiguration is a powerful technique with potential for a wide range of applications in which temporal partitioning and adaptivity are feasible and desired.

Real-time video compression is a challenging subject for FPGA implementation because it typically has a large computational complexity and requires high data throughput. Previous implementations have used parallel banks of FPGAs or DSPs to meet these requirements. Using design techniques that maximize FPGA utilization, we have implemented two video compression systems, each of which uses a single FPGA. In this first system, algorithmic optimizations are made to create a low-complexity implementation that exploits the in-system programmability of the FPGA. This low-complexity implementation performs well, but is limited to a single compression algorithm. In the second system, the FPGA is augmented with an external, low-complexity, video signal processor (VSP) This combination of ASIC and FPGA is flexible enough to implement four common compression algorithms, and powerful enough to execute them in real time.

The design of a low complexity joint source channel codec for images using trellis coded quantization and convolutional codes is studied. It is shown that a low complexity joint source channel codec offering high robustness is enabled by using the same Ungerboeck trellis code to do both quantization and convolutional coding. Simulation results are presented for joint source channel coding of Gaussian sources over the additive white Gaussian noise channel (AWGN) under the restriction of BPSK modulation; coding of image subband coefficients is also performed. The results compare favorably with those previously reported for systems employing unified trellis source coding and convolutional channel coding, and for pseudo-Gray coded systems. The simulation results also show that there is an optimal allocation of transmission bandwidth between the source and channel codes.

A fixed-rate lattice vector quantizer for generalized Gaussian (GG) sources is presented. By using the contour of constant probability of a generalized Gaussian source to bound the integer lattice, this vector quantizer in the limit of high dimension achieves optimal boundary gains for GG sources. Low-complexity techniques for rate control, optimal codevector search and enumeration are developed. This coder achieves 8.60 dB for a generalized Gaussian source with shape parameter of 0.5 at 1 bit/sample (compared with a rate distortion bound of 9.23 dB) and 32.62 dB for the 512/spl times/512 "Lena" image at 0.25 bpp without the use of entropy coding. By using two small lookup tables, the nearest codeword search operation can be performed multiply-free and the overall quantization process costs one multiply and a few adds per sample.

In lattice vector quantization, the distortion associated with a given lattice is often expressed in terms of the G number, which is a measure of the mean square error per dimension generated by quantization of a uniform source. Subband image coefficients, however, are best modeled by a generalized Gaussian distribution, leading to distortion characteristics that are quite different from those encountered for uniform, Laplacian, or Gaussian sources. We have calculated the distortion associated with Z, E/sub 8/, and Leech (1967) lattice quantization for coding of generalized Gaussian sources and show that for low bit rates, the Z lattice offers both the best performance and the lowest implementational complexity.>

Video coding has been implemented by using rapid reconfiguration to time share hardware for several sequential stages. This allows the chip area to be reduced by a factor proportional to the number of coding stages at the expense of some reconfiguration overhead and the added memory and control needed to implement reconfiguration. The results of this work suggest that run-time reconfiguration is a powerful technique with potential for a wide range of video applications in which temporal algorithm partitioning and rapid adaptivity are feasible and desired.

Choice of filter bank in wavelet compression is a critical issue that affects image quality as well as system design. Although regularity is sometimes used in filter evaluation, its success at predicting compression performance is only partial. A more reliable evaluation can be obtained by considering an L-level synthesis/analysis system as a single-input, single-output, linear shift-variant system with a response that varies according to the input location module (2(L),2(L)). By characterizing a filter bank according to its impulse response and step response in addition to regularity, we obtain reliable and relevant (for image coding) filter evaluation metrics. Using this approach, we have evaluated all possible reasonably short (less than 36 taps in the synthesis/analysis pair) minimum-order biorthogonal wavelet filter banks. Of this group of over 4300 candidate filter banks, we have selected and present here the filters best suited to image compression. While some of these filters have been published previously, others are new and have properties that make them attractive in system design.

Choice of filter bank in wavelet compression is a critical issue that affects image quality as well as system design. Although regularity is sometimes used in filter evaluation, its success at predicting compression performance is only partial. A more reliable evaluation can be obtained by considering an L-level synthesis/analysis system as a single-input, single-output, linear shift-variant system with a response that varies according to the input location modulo (2/sup L/, 2/sup L/). By characterizing a filter bank according to its impulse response and step response in addition to regularity, the authors obtain reliable and relevant (for image coding) filter evaluation metrics. Using this approach, they have evaluated all possible reasonably short (less than 34 taps in the synthesis/analysis pair) minimum order biorthogonal wavelet filter banks. Of this group of over 4300 candidate filter banks, they have selected and presented the filters best suited to image compression. While some of these filters have been published previously, others are new and have properties that make them attractive in system design.>

Wireless video transmission over a dynamic network requires adaptation to changes in bandwidth, network traffic, and channel characteristics. New computing hardware and algorithms are needed that enable low-power, flexible, adaptive, and robust video communication in hostile environments with no access to an installed communications infrastructure. The coding algorithms we are developing are based on subband decomposition using integer-coefficient filters, and adaptively deliver video at rates between 60 kbits/sec and 600 kbits/sec in accordance with the available bandwidth. Robustness in the variable length coder is obtained by using low-overhead Reed-Solomon block codes, by performing intra-frame coding only, and by using end-of-frame and end-of-subband symbols to maintain both inter- and intra-frame synchronization.>

The two-dimensional Hartley transform is of particular interest not only as a tool for analysis and processing of images and other two-dimensional functions, but because it can be implemented optically without introducing the phase ambiguities associated with intensity-only observations of Fourier transforms. The Hartley transform property of producing real transforms from real inputs means that square law detection introduces only a sign ambiguity, which can be resolved much more easily than a phase ambiguity. This suggests applications in optical signal processing, holography, and optical diffraction.>

The unacceptability of block artifacts in medical image data compression has led to systems employing full-frame discrete cosine transform (DCT) compression. Although the DCT is the optimum fast transform when block coding is used, it is outperformed by the discrete Fourier transform (DFT) and discrete Hartley transform for images obtained using positron emission tomography and magnetic resonance imaging. Such images are characterized by a roughly circular region of non-zero intensity bounded by a region R in which the image intensity is essentially zero. Clipping R to its minimum extent can reduce the number of low-intensity pixels, but the practical requirement that images be stored on a rectangular grid means that a significant region of zero intensity must remain an integral part of the image to be compressed. The DCT therefore loses its advantage over the DFT because neither transform introduced significant artificial discontinuities.>

Full-frame irreversible compression of medical images is currently being performed using the discrete cosine transform (DCT). Although the DCT is the optimum fast transform for video compression applications, the authors show here that it is outperformed by the discrete Fourier transform (DFT) and discrete Hartley transform (DHT) for images obtained using positron emission tomography (PET) and magnetic resonance imaging (MRI), and possibly for certain types of digitized radiographs. This difference occurs because PET and MRI images are characterized by a roughly circular region D of non-zero intensity bounded by a region R in which the image intensity is essentially zero. Clipping R to its minimum extent can reduce the number of low-intensity pixels but the practical requirement that images be stored on a rectangular grid means that a significant region of zero intensity must remain an integral part of the image to be compressed. With this constraint imposed, the DCT loses its advantage over the DFT because neither transform introduces significant artificial discontinuities. The DFT and DHT have the further important advantage of requiring less computation time than the DCT.

A radar interferometric technique for topographic mapping of surfaces, implemented utilizing a single synthetic aperture radar (SAR) system in a nearly repeating orbit, is discussed. The authors characterize the various sources contributing to the echo correlation statistics, and isolate the term which most closely describes surficial change. They then examine the application of this approach to topographic mapping of vegetated surfaces which may be expected to possess varying backscatter over time. It is found that there is decorrelation increasing with time but that digital terrain model generation remains feasible. The authors present such a map of a forested area in Oregon which also includes some nearly unvegetated lava flows. Such a technique could provide a global digital terrain map.>