Design and characterization of optimal FIR filters with arbitraryphase

An algorithm for designing a Chebyshev optimal FIR filter that approximates an arbitrary complex-valued frequency response is presented. This algorithm computes the optimal filter by solving the dual to the filter design problem. It is guaranteed to converge theoretically and requires O(N²) computations per iteration for a filter of length N. For the first time, properties of the optimal filter are derived, and the case where the desired filter has arbitrary constant group delay is studied in detail     

Complete classification of roots to one-dimensional median andrank-order filters

The set of roots to the one-dimensional median filter is completely determined. Let 2N+1 be the filter window width. It has been shown that if a root contains a monotone segment of length N+1, then it must be locally monotone N+2. For roots with no monotone segment of length N+1, it is proved that the set of such roots is finite, and that each such root is periodic. The methods used are constructive, so given N, one can list all possible roots of this type. The results developed for the median filter also apply to rank-order filters     

Reliable and fast reconfigurable hierarchical interconnectionnetworks for linear WSI arrays

A self-pruning binary tree (SPBT) interconnection network architecture that tolerate faults in a wafer scale integration (WSI) environment is proposed. The goal of the SPBT network is to provide a reliable and a quickly reconfigured interconnection network architecture for linear WSI arrays. The proposed architecture uses a bottom-up approach to reconfigure a linear pipelined array on a potentially defective WSI array using a binary tree interconnection scheme. The binary tree is generated by successive formation of hierarchical modules. For N processing elements (PEs) on the wafer, reconfiguration time is O(log N). The propagation delay is bounded by Θ(log N) and is independent of the number of faulty PEs. Faults in the switching network as well as faulty processing elements are tolerated     

A system for systolic modules for the MUSIC algorithm

The authors believe that special-purpose architectures for digital signal processing (DSP) real-time applications will use closely coupled processing elements as array processor modules to implement the various portions of the new algorithms, and several such modules will cooperate in a pipelined manner to implement complete algorithms. Such an architecture, based upon systolic modules, for the MUSIC algorithm is presented. The architecture is suitable for VLSI implementation. The throughput of the pipelined approach is O(N), whereas the sequential approach is O(N³)     

In the optimum design of the block adaptive FIR digital filter

A general optimum block adaptive (GOBA) algorithm for adaptive FIR (finite impulse response) filtering is presented. In this algorithm, the correction terms for the filter coefficients in each block, instead of the convergence factors, are optimized in a least squares sense. There are no constraints on the block length L and the filter tap number N. It is shown that the GOBA algorithm is reduced to the normalized LMS algorithm when L⩾N. The convergence of the GOBA algorithm can be assured if the correlation matrix of the input signal is positive definite. Computer simulations based on an efficient computing procedure confirm that the GOBA algorithm achieves faster convergence with slightly degraded convergence accuracy in stationary environments and better weight tracking capability in nonstationary environments as compared to existing block adaptive algorithms with no constraints on L and N     

A new time domain, multistage permutation algorithm [switchingsystems]

It is shown that a frame of N time slots can be arbitrarily permuted with 2log₂N-1 controlled exchange switches with associated delay elements. This is an improvement over previously known interconnection networks that require O( N) exchange elements. The proof utilizes the recursive algorithm of V.E. Benes (1965) and the time interchange properties of a particular configuration of a single exchange element. The architecture is especially applicable in optical systems, since optical exchange switches are among the simplest optical logic devices to build, are inherently very fast, and are the best developed, although expensive     

Realization of IIR LDM digital filters

A method is presented of realizing an infinite impulse response (IIR) digital filter (DF) using linear delta modulation (LDM) as a simple analog/digital (A/D) converter. This method makes the realization of IIR digital filters much simpler than that of conventional ones because it does not require hardware multipliers or a pulse code modulation (PCM) A/D converter. Compared to the finite impulse response (FIR) LDMDF, this IIR LDMDF requires significantly less computation time     

A multibus train communication (AMTRAC) architecture for high-speedfiber optic networks

A multibus train (ordered demand assignment) communication architecture, using the AMTRAC protocol (for efficient utilization of fiber-optic-based very-high-speed networks) is presented. Taking advantage of the emerging WDM (wavelength-division multiplexing) and FDM (frequency-division multiplexing) technologies, the proposed solution introduces a coordinated multichannel control combining the performance advantages of two known approaches for high-speed communication: multichannel and train protocols. As a result an AMTRAC-based high-speed network achieves channel utilization significantly higher than previous approaches. For a network consisting of N stations, with propagation delay to packet transmission time ratio given by a, the AMTRAC architecture reaches a capacity of 1/(1+a/N ²)     

K-band quasi-planar tapped combline filter and diplexer

Quasi-planar realizations of a combline bandpass filter and diplexer using multiple coupled suspended substrate striplines (MCSSSs) have demonstrated good performance at K-band without any tuning. The N MCSSSs excite N zero-cutoff-frequency quasi-TEM modes. A computer-aided filter design approach employing a rigorous spectral domain approach and 2N-port microwave circuit theory accounts for the effects of the N quasi-TEM modes, the couplings through nonadjacent MCSSSs, and cover height. Two 19.5-20.5 GHz MCSSS combline filters with different cover heights have been built and tested to compare their filter characteristics. The reduction in cover height has been found to decrease the amount of nonadjacent coupling through MCSSSs and to result in better filter stopband performance. An 18.5-19 GHz and 20-20.5 GHz MCSSS diplexer is also presented. All the measured results for the combline filters and diplexers agree well with the theoretic calculations     

A stable and distortion-free IIR echo and howling canceler

The authors propose a configuration for an infinite impulse response (IIR) adaptive echo and howling canceller, which consists of a two-channel maximum entropy lattice filter and its inverse filter. The echo is canceled by the adaptive lattice filter, while the signal distortion is eliminated by the inverse lattice. With stability guaranteed without the necessity of testing, the structure costs O (N) multiplications per sampling period. The algorithm can also be greatly simplified for white input cases     

Systolic arrays for the discrete Hartley transform

Recently, R.N. Bracewell (1983) introduced the discrete Hartley transform (DHT) as an alternative to the discrete Fourier transform (DFT). Two linear systolic array models for the (DHT) are derived. One model requires O(2N-1) in the computational phase and O(N) in the preloading phase. The other model requires O(2N-1) in the computational phase and O(N) in the output phase. A square systolic array for two-dimensional DHT is also constructed by combining the individual advantages of each model. The CORDIC algorithm is proposed as an alternative to conventional multipliers. To speed up the systolic array, two-level pipelining with CORDIC is also possible     

Fast cosine transform of Toeplitz matrices, algorithm andapplications

A fast algorithm for the discrete cosine transform (DCT) of a Toeplitz matrix of order N is derived. Only O(N log N)+O(M) time is needed for the computation of M elements. The storage requirement is O(N). The method carries over to other transforms (DFT, DST) and to Hankel or circulant matrices. Some applications of the algorithm are discussed     

A new 2-D systolic digital filter architecture without global broadcast

In this paper, we propose two-dimensional (2-D) systolic-array infinite-impulse response (IIR) and finite-impulse response (FIR) digital filter architectures without global broadcast, by the hybrid of a modified reordering scheme and a new systolic transformation. This architecture has local broadcast, lower-quantization error, and zero latency without sacrificing the number of multipliers, as well as delay elements under the satisfactory critical period. Furthermore, we extend this new architecture to a useful 2-D systolic cascade-form architecture and provide the comprehensive error analysis for the proposed architectures.     

A technique for realizing linear phase IIR filters

A real-time IIR filter structure is presented that possesses exact phase linearity with 10~1000 times fewer general multiplies than conventional FIR filters of similar performance and better magnitude characteristics than equiripple or maximally flat group delay IIR filters. This structure is based on a technique using local time reversal and single pass sectioned convolution methods to realized a real-time recursive implementation of the noncausal transfer function H(z^-1). The time reversed section technique used to realize exactly linear phase IIR filters is described. The effects of finite section length on the sectional convolution are analyzed. A simulation methodology is developed to address the special requirements of simulating a time reversed section filter. A design example is presented, with computer simulation to illustrate performance, in terms of overall magnitude response and phase linearity, as a function of finite section length. Nine example filter specifications are used to compare the performance and complexity of the time reversed section technique to those of a direct FIR implementation     

Perfect N-phase sequences and arrays [spread spectrumcommunication]

Perfect sequences and arrays have periodic autocorrelation functions whose out-of-phase values are zero. Time-discrete N-phase sequences and arrays have complex elements of magnitude one, and one of (2π/N)n, 0⩽n<N , different phase values. Existence conditions and construction methods for perfect N-phase sequences and arrays with a small alphabet of possible phase values are introduced. Combining the existence conditions with, methods of advanced computer search, new perfect N-phase arrays have been found. The resulting lowest number N of perfect N-phase sequences and arrays up to 40 elements are given in a table, after having applied the construction methods     

On the performance of an ATM switch with multichannel transmissiongroups

A routing architecture applying the concept of multichannel transmission groups (MCTGs) for ATM systems is proposed. A queuing analysis of an internally nonblocking ATM switch employing this MCTG concept with partially shared output buffers is presented. The analysis is based on the discrete-time DA///D/c /B queuing model. Both bulk input traffic bulk-size distribution (A) and deterministic traffic (D₁ +. . .+D_N) are considered. The impact of switch speedup on the performance is also taken into account. It is shown that the MCTG architecture yields better performance in terms of delay and cell loss probability than its single channel counterpart. It is also found that the switch speedup required to closely approximate the optimal performance obtained by having the switch fabric run N times as fast as the input and output channels, where N is the size of the switch, is rather small compared to N. This makes the practical realization of the proposed switch architecture feasible     

The impedance matrix localization (IML) method for moment-methodcalculations

The impedance matrix localization (IML) method, a modification of the standard method of moments that can be implemented as a modification to existing computer programs, is examined. This modification greatly eases the excessive storage requirements and long computation times of moment-method approaches by using novel bases and testing function that localize the important interactions to only a small number of elements within the impedance matrix elements can be made so small (typically 10 ^-4 to 10^-6 in relative magnitude) that they may be approximated by zero. In the case of a two-dimensional body with unknowns on its surface, both analytical arguments and numerical calculations suggest that, for an N×N matrix, about 100N matrix elements will need to be kept, even for very large N. The resulting sparse matrix requires storage for only 100N complex numbers rather than for N² numbers. Similar results are expected in three dimensions. The structure of the resulting matrix problem allows the use of highly efficient solution methods. Results are given for one such possibility: iteration preconditioned by incomplete LU decomposition     

A selective ARQ protocol with a finite-length buffer

Of the automatic-repeat-request (ARQ) techniques commonly used in communication systems, selective protocols, while the most efficient, have the notable drawback of requiring large buffers at the receiver side. A selective ARQ protocol with a finite-length buffer is described. If N is the number of codewords transmittable in the round-trip delay, the protocol requires a buffer length N+N_a , N_a⩾2 being an integer. A lower bound on the throughput of the protocol is derived. It achieves higher throughputs than similar schemes giving results comparable to those for selective protocols with infinite-length buffer for high error rates in the communication channel     

On the Hamming distance properties of group codes

Under certain mild conditions, the minimum Hamming distance D of an (N, K, D) group code C over a non-abelian group G is bounded by D⩽N -2K+2 if K⩽N/2, and is equal to 1 if K>N/2. Consequently, there exists no (N, K, N-K+1) group code C over an non-abelian group G if 1<K<N. Moreover, any normal code C with a non-abelian output space has minimum Hamming distance equal to D=1. These results follow from the fact that non-abelian groups have nontrivial commutator subgroups. Finally, if C is an (N, K, D) group code over an abelian group G that is not elementary abelian, then there exists an (N, K, D) group code over a smaller elementary abelian group G'. Thus, a group code over a general group G cannot have better parameters than a conventional linear code over a field of the same size as G     

Quadtree-structured recursive plane decomposition coding of images

The approximation of two-dimensional highly correlated grey value functions can be performed using a linear model of the type f( x, y)=a+bx+cy. The set of plane parameters (PPs) [a, b, c] can be determined in the least squares sense for a block of size N×N pixels, for example. Starting with a block size of 2×2 pixels, it is shown that the PPs obey a recursive law such that the PPs of a 2N×2N block can be computed recursively when only the PPs of the four adjacent subblocks of size N×N in the lower decomposition level are known. This concept of recursive plane decomposition (RPD) is embedded in a quadtree data structure to obtain a new variable block size image coding algorithm that offers a high performance at a low computational cost. Extensive comparisons to other state-of-the-art image coding algorithms are reported