Image coding with geometric wavelets.

This paper describes a new and efficient method for low bit-rate image coding which is based on recent development in the theory of multivariate nonlinear piecewise polynomial approximation. It combines a binary space partition scheme with geometric wavelet (GW) tree approximation so as to efficiently capture curve singularities and provide a sparse representation of the image. The GW method successfully competes with state-of-the-art wavelet methods such as the EZW, SPIHT, and EBCOT algorithms. We report a gain of about 0.4 dB over the SPIHT and EBCOT algorithms at the bit-rate 0.0625 bits-per-pixels (bpp). It also outperforms other recent methods that are based on "sparse geometric representation." For example, we report a gain of 0.27 dB over the Bandelets algorithm at 0.1 bpp. Although the algorithm is computationally intensive, its time complexity can be significantely reduced by collecting a "global" GW n-term approximation to the image from a collection of GW trees, each constructed separately over tiles of the image.     

Dyadic-based factorizations for regular paraunitary filterbanks and M-band orthogonal wavelets with structural vanishing moments

Paraunitary filterbanks (PUFBs) can be designed and implemented using either degree-one or order-one dyadic-based factorization. This work discusses how regularity of a desired degree is structurally imposed on such factorizations for any number of channels M /spl ges/ 2, without necessarily constraining the phase responses. The regular linear-phase PUFBs become a special case under the proposed framework. We show that the regularity conditions are conveniently expressed in terms of recently reported M-channel lifting structures, which allow for fast, reversible, and possibly multiplierless implementations in addition to improved design efficiency, as suggested by numerical experience. M-band orthonormal wavelets with structural vanishing moments are obtained by iterating the resulting regular PUFBs on the lowpass channel. Design examples are presented and evaluated using a transform-based image coder, and they are found to outperform previously reported designs.     

Resilient functions over finite fields

Resilient functions play an important role in the art of information security. In this correspondence, we discuss the existence, construction, and enumeration of resilient functions over finite fields. We show that, for each finite field GF(q) with q > 3, we can easily construct a large number of (q, n, 1, n - 1) resilient functions, most of which include mixing terms. We give a general structure for (q, m + 1, m, 1) resilient functions, and present an example which is not of this general structure. We prove that (q, m + 2, m, 2) resilient functions exist for any m such that 1 < m < q when q > 2. We prove that (q, m + t, m, t) resilient functions exist for any (m, t) such that 1 < m < q and 2 < t < q when q > 3. By making some simple generalizations of former results, we also provide some new methods for constructing resilient functions.     

Hartley transforms over finite fields

A general framework is presented for constructing transforms in the field of the input which have a convolution-like property. The construction is carried out over finite fields, but is shown to be valid over the real and complex fields as well. It is shown that these basefield transforms can be viewed as “projections” of the discrete Fourier transform (DFT) and that they exist for all lengths N for which the DFT is defined. The convolution property of the basefield transforms is derived and a condition for such transforms to have the self-inverse property is given. Also, fast algorithms for these basefield transforms are developed, showing gains when compared to computations using the FFT. Application of the methodology to Hartley transforms over R leads to a simple derivation of fast algorithms for computing real Hartley transforms     

Digital oscillators over finite fields

This paper shows how the error-free computational property of finite fields can be used to eliminate aperiodicity and SNR degradation problems in digital oscillators. Galois fields are used to eliminate representation and truncation errors in the computation of sinusoid samples. Theorems are presented that characterize those fields that admit all operands necessary for sample generation at a given phase resolution. Two finite field oscillator architectures, exponential feedback, and direct forms are presented, and various design issues associated with operand representation and arithmetic are discussed. It is also shown how field arithmetic can be replaced by arithmetic in the direct product ring associated with a set of specially chosen small fields. This is important in high-speed applications where the loop delay must be minimized. We also present analytical estimates of clocking frequency, latency, and phase and frequency resolution for both architectures. Finally, we present an example ASIC design of a finite ring digital oscillator in 2μ CMOS technology     

A study of two-channel complex-valued filterbanks and wavelets withorthogonality and symmetry properties

We investigate two-channel complex-valued filterbanks and wavelets that simultaneously have orthogonality and symmetry properties. First, the conditions for the filterbank to be orthogonal, symmetric, and regular (for generating smooth wavelets) are presented. Then, a complete and minimal lattice structure is developed, which enables a general design approach for filterbanks and wavelets with arbitrary length and arbitrary order of regularity. Finally, two integer implementation methods that preserve the perfect reconstruction property of the filterbank are proposed. Their performances are evaluated via experimental results     

Paraunitary filter banks over finite fields

In real and complex fields, unitary and paraunitary (PU) matrices have found many applications in signal processing. There has been interest in extending these ideas to the case of finite fields. We study the theory of PU filter banks (FBs) in GF(q) with q prime. Various properties of unitary and PU matrices in finite fields are studied. In particular, a number of factorization theorems are given. We show that (i) all unitary matrices in GF(q) are factorizable in terms of Householder-like matrices and permutation matrices, and (ii) the class of first-order PU matrices (the lapped orthogonal transform in finite fields) can always be expressed as a product of degree-one or degree-two building blocks. If q>2, we do not need degree-two building blocks. While many properties of PU matrices in finite fields are similar to those of PU matrices in complex field, there are a number of differences. For example, unlike the conventional PU systems, in finite fields, there are PU systems that are unfactorizable in terms of smaller building blocks. In fact, in the special case of 2×2 systems, all PU matrices that are factorizable in terms of degree-one building blocks are diagonal matrices. We derive results for both the cases of GF(2) and GF(Q) with q>2. Even though they share some similarities, there are many differences between these two cases     

A new design algorithm for two-band orthonormal rational filterbanks and orthonormal rational wavelets

We present a new algorithm for the design of orthonormal two-band rational filter banks. Owing to the connection between iterated rational filter banks and rational wavelets, this is also a design algorithm for orthonormal rational wavelets. It is basically a simple iterative procedure, which explains its exponential convergence and adaptability under various linear constraints (e,g., regularity). Although the filters obtained from this algorithm are suboptimally designed, they show excellent frequency selectivity. After an in-depth account of the algorithm, we discuss the properties of the rational wavelets generated by some designed filters. In particular, we stress the possibility to design “almost” shift error-free wavelets, which allows the implementation of a rational wavelet transform     

Multiview coding and error correction coding for 3D video over noisy channels

We consider the joint source–channel coding problem of stereo video transmitted over AWGN and flat Rayleigh fading channels. Multiview coding (MVC) is used to encode the source, as well as a type of spatial scalable MVC. Our goal is to minimize the total number of bits, which is the sum of the number of source bits and the number of forward error correction bits, under the constraints that the quality of the left and right views must each be greater than predetermined PSNR thresholds at the receiver. We first consider symmetric coding, for which the quality thresholds are equal. Following binocular suppression theory, we also consider asymmetric coding, for which the quality thresholds are unequal. The optimization problem is solved using both equal error protection (EEP) and a proposed unequal error protection (UEP) scheme. An estimate of the expected end-to-end distortion of the two views is formulated for a packetized MVC bitstream over a noisy channel. The UEP algorithm uses these estimates for packet rate allocation. Results for various scenarios, including non-scalable/scalable MVC, symmetric/asymmetric coding, and UEP/EEP, are provided for both AWGN and flat Rayleigh fading channels. The UEP bit savings compared to EEP are given, and the performances of different scenarios are compared for a set of stereo video sequences.     

Discrete cosine transform in error control coding

The authors define a new class of real-number linear block codes using the discrete cosine transform (DCT). They also show that a subclass with a BCH-like structure can be defined and, therefore, encoding/decoding algorithms for BCH codes can be applied, A (16,10) DCT code is given as an example     

Discrete Hartley transform in error control coding

A new class of real-valued linear code obtained by using the discrete Hartley transform (DHT) is defined. The authors have derived the limitation on the choice of parity frequencies so as to define DHT codes with the cyclic-shift property. Then, by introducing the well-established encoding/decoding algorithm for cyclic codes in error control coding, they have constructed the encoder/decoder for the DHT cyclic codes     

Finding roots of polynomials over finite fields

We propose an improved algorithm for finding roots of polynomials over finite fields. This makes possible significant speedup of the decoding process of Bose-Chaudhuri-Hocquenghem, Reed-Solomon, and some other error-correcting codes.     

The fractional Fourier transform over finite fields

The central contribution of this paper is the definition of the fractional Fourier transform over finite fields (GFrFT). In order to introduce the GFrFT, concepts related to trigonometry in finite fields are reviewed and some new ideas put forward. In particular, graphic representations of elements in a finite field are suggested and analogies with real and complex numbers are discussed. A modified version of the finite field Fourier transform is given and its eigenstructure is analyzed. This allows us to develop GFrFT theory and investigate its main characteristics. Some illustrative examples are also given throughout the paper.     

The theory and design of arbitrary-length cosine-modulated filterbanks and wavelets, satisfying perfect reconstruction

It is well known that FIR filter banks that satisfy the perfect-reconstruction (PR) property can be obtained by cosine modulation of a linear-phase prototype filter of length N=2mM, where M is the number of channels. In this paper, we present a PR cosine-modulated filter bank where the length of the prototype filter is arbitrary. The design is formulated as a quadratic-constrained least-squares optimization problem, where the optimized parameters are the prototype filter coefficients. Additional regularity conditions are imposed on the filter bank to obtain the cosine-modulated orthonormal bases of compactly supported wavelets. Design examples are given     

Solving sparse linear equations over finite fields

A "coordinate recurrence" method for solving sparse systems of linear equations over finite fields is described. The algorithms discussed all requireO(n_{1}(omega + n_{1})log^{k}n_{1})field operations, wheren_{1}is the maximum dimension of the coefficient matrix,omegais approximately the number of field operations required to apply the matrix to a test vector, and the value ofkdepends on the algorithm. A probabilistic algorithm is shown to exist for finding the determinant of a square matrix. Also, probabilistic algorithms are shown to exist for finding the minimum polynomial and rank with some arbitrarily small possibility of error.     

Synchronous fibre-optic code division multiple access networks with error control coding

For a fibre-optic synchronous code division multiple access (S/CDMA) network, the number of users able to simultaneously utilise the network is a major concern. A theoretical analysis of the S/CDMA network employing error control codes to enhance the reliability of the network and to increase the number of concurrent users is presented. The error probabilities for both the uncoded and coded systems are analysed. The example shows that by using a (63, 36) BCH code the influence of interference arising from other users can be greatly reduced and the number of active users can also be increased significantly.<>     

On the performance of error control coding with diversity formobile channels

Upper bounds on the bit error probability are applied to evaluate the error performance of coded systems over non-interleaved and partially interleaved Rician fading mobile channels. The correlation between successive received symbols is exploited to bound the error performance. The bound allows useful evaluation of coding gains on realistic communication systems without going into lengthy computer simulations. By further defining the maximum energy degradation factors, compact upper bounds are expressed in a similar way as on the fully interleaved or memoryless channels. The maximum energy degradation factors are computed for a wide variety of mobile channel conditions. These factors give an interesting evaluation of the fading conditions and may be used to design coded communication systems on mobile channels. Furthermore, independent space or frequency diversity may be taken into account in these bounds and it is shown that the energy degradation due to correlation is independent of this added independent diversity     

Design and multiplier-less implementation of a class of two-channel PR FIR filterbanks and wavelets with low system delay

A new method for designing two-channel PR FIR filterbanks with low system delay is proposed. It is based on the generalization of the structure previously proposed by Phoong et al. (1995) Such structurally PR filterbanks are parameterized by two functions (/spl beta/(z) and /spl alpha/(z)) that can be chosen as linear-phase FIR or allpass functions to construct FIR/IIR filterbanks with good frequency characteristics. The case of using identical /spl beta/(z) and /spl alpha/(z) was considered by Phoong et al. with the delay parameter M chosen as 2N-1. In this paper, the more general ease of using different nonlinear-phase FIR functions for /spl beta/(z) and /spl alpha/(z) is studied. As the linear-phase constraint is relaxed, the lengths of /spl beta/(z) and /spl alpha/(z) are no longer restricted by the delay parameters of the filterbanks. Hence, higher stopband attenuation can still be achieved at low system delay. The design of the proposed low-delay filterbanks is formulated as a complex polynomial approximation problem, which can be solved by the Remez exchange algorithm or analytic formula with very low complexity. In addition, the orders and delay parameters can be estimated from the given filter specifications using a simple empirical formula. Therefore, low-delay two-channel PR filterbanks with flexible stopband attenuation and cutoff frequencies can be designed using existing filter design algorithms. The generalization of the present approach to the design of a class of wavelet bases associated with these low-delay filterbanks and its multiplier-less implementation using the sum of powers-of-two coefficients are also studied.     

An error resilient video coding and transmission solution over error-prone channels

With the rapid development of network and multimedia technology, the error control in video coding and video transmission over error-prone channels has become increasingly important. The DCT based predictive coding and VLC based entropy coding greatly increase the coding efficiency, but make the compressed video stream very sensitive to transmission errors. Therefore, this paper proposes a reliable error resilient video coding and video transmission framework. In order to improve the robustness to packet loss errors, an error resilient video coding algorithm named Z-FMO is proposed. Some channel may bring random bit errors, an adaptive error concealment algorithm based on macroblock boundary gradient namely ECMBG is proposed aiming at such problem. As the indispensable part of a video transmission system, we implement an adaptive video transmission control algorithm JCBAF. Experimental results show that the proposed framework performs well both in R-D performance and subjective quality.