Kari H. A. KARKKAINEN Pentti A. LEPPANEN
Two families of rapidly synchronizable spreading codes are compared using the same component codes. The influence of component code choice is also discussed. It is concluded that correlation, code-division multiple-access (CDMA) and information security (measured by the value of linear complexity) properties of Kronecker sequences are considerably better than those of Combination sequences. Combination sequences cannot be recommended for CDMA use unless the number of active users is few. CDMA performance of Kronecker sequences is almost comparable with that of linear pseudonoise (PN) code families of equal length when a Gold or Kasami code is used as the innermost code and the Barker code is used as the outermost code to guarantee satisfactory correlation and CDMA properties. Kronecker sequences possess a considerably higher value of linear complexity than those of the corresponding non-linear Geffe and majority logic type combination sequences. This implies they are highly non-linear codes due to the Kronecker product construction method. It is also observed that the Geffe type Boolean combiner resulted in better correlation and CDMA performance than with majority logic. The use of the purely linear exclusive-or combiner for considerable reduction of code synchronization time is not found recommendable although it results in good CDMA performance.
This paper is concerned with a concept called universality or completeness of sets of logic devices. Universality characterizes sets of logic devices which can be used for the construction of arbitrary logic circuits. The elemental universality proposed here is the most general condition of universality which covers logic devices with/without delay time and combinational/sequential circuits. The necessary and sufficient condition of elemental universality shows that nonlinearity and nonmonotonicity are essential conditions for the realization of various digital mechanisms.
K-randomness and Martin-Lof randomness are among many formalizations of randomness of infinite sequences, and these two are known to be equivalent. We can naturally modify the former to the definition of partial randomness. However, it is not obvious how to modify the latter to the definition of partial randomness. In this paper, we show that we can modify Martin-Lof randomness to a definition of partial randomness that is equivalent to the definition obtained by naturally modifying K-randomness. The basic idea is to modify the notion of measures used in the definition of Martin-Lof tests.
Shigenori KINJO Masafumi OSHIRO Hiroshi OCHI
Two-dimensional (2-D) adaptive digital filters (ADFs) for 2-D signal processing have become a fascinating area of the adaptive signal processing. However, conventional 2-D FIR ADF's require a lot of computations. For example, the TDLMS requires 2N2 multiplications per pixel. We propose a new 2-D adaptive filter using the FFTs. The proposed adaptive filter carries out the fast convolution using overlap-save method, and has parallel structure. Thus, we can reduce the computational complexity to O(log2N) per pixel.
Tomonori IZUMI Toshihiko YOKOMARU Atsushi TAKAHASHI Yoji KAJITANI
The packing problem is to pack given items into given containers as efficiently as possible under various constraints. It is fundamental and significant with variations and applications. The Set-Bin-Packing (SBP) is a class of packing problems: Pack given items into as few bins which have the same capacity where every item is a set and a bin can contain items as long as the number of distinct elements in the union of the items equals to or less than the capacity. One of applications is in FPGA technology mapping, which is our initial motivation. In this paper, the computational complexity of SBP is studied with respect to three parameters α, γ, and δ which are the capacity, the upper bound of the number of elements in an item, and the upper bound of the number of items having an element, respectively. In contrast that the well known Integer-Bin-Packing (IBP) is NP-hard but is proved that even a simplest heuristics First-Fit-Decreasing (FFD) outputs exact solutions as long as α 6, our result reveals that SBP remains NP-hard for a small values of these parameters. The results are summarized on a 3D map of computational complexities with respect to these three parameters.
Yukihisa OKADA Ichiro KOIWA Kinya ASHIKAGA Katsuaki KAIFU
We prepared alkoxide solutions to fabricate SrBi2Ta2O9 (SBT) ferroelectric capacitors with IrO2 electrodes. In this process, to minimize excess bismuth, the Sr : Bi : Ta mole ratio was kept at 0. 9 : 2. 1 : 2. 0, i. e. , nearly stoichiometric. Three types of solution - mixed-only (MIX), complexed (COMP), and hydrolyzed (HYD) - were used. The HYD capacitor had low absolute leakage current, 10-7 A/cm2 order, and good saturation properties to 6 V. When voltage was applied to each capacitor at 2 to 6 V, MIX and COMP capacitors showed only partial hysteresis loops due to a high leakage current, reflecting the I-V characteristics. These results are probably due to film density caused by metaloxane network bonding. A fatigue endurance test was conducted using cycling of polarization switching at 6 V using the HYD capacitor with IrO2 electrodes. Slight changes were, however, observed in hysteresis loop configuration, but good hysteresis properties were kept up to 1. 04 1012 cycles. We compared SBT ferroelectric thin films fabricated with Pt electrodes and with IrO2 electrodes. Scarcely any difference due to SBT in the XRD pattern was seen, depending on the substrate material. We found that the use of IrO2 electrodes had the effect of decreasing the crystallization temperature. On Pt and IrO2 electrodes, the two films have surface morphology quite different from that of the rod-like structure wellknown for SBT films prepared using a metal 2-ethylhexanate solution. Their surfaces show a similar morphology with relatively large, closely packed grains. A comparison of the I-V characteristics after reannealing showed that the capacitor with IrO2 electrodes had a higher leakage current than that with Pt electrodes. The leakage current was probably due to the density of the film and interface between the SBT film and electrodes.
Georgios Y. LAZAROU Victor S. FROST Joseph B. EVANS Douglas NIEHAUS
Predicting the performance of high speed wide area ATM networks (WANs) is a difficult task. Evaluating the performance of these systems by means of mathematical models is not yet feasible. As a result, the creation of simulation models is usually the only means of predicting and evaluating the performance of such systems. In this paper, we use measurements to validate simulation models of TCP/IP over high speed ATM wide area networks. Validation of simulations with measurements is not common; however, it is needed so that simulation models can be used with confidence to accurately characterize the performance of ATM WANs. In addition, the appropriate level of complexity of the simulation models needs to be determined. The results show that under appropriate conditions simulation models can accurately predict the performance of complex high speed ATM wide area networks. This work also shows that the user perceived performance is dependent on host processing demands.
It is shown from the Hilberts theory that if the real function Π(θ) has no zeros over the interval [0, 2π], it can be factorized into a product of the factor π+(θ) and its complex conjugate π-(θ)(=). This factorization is tested to decompose a real far-zone field pattern having zeros. To this end, the factorized factors are described in terms of bicomplex mathematics. In our bicomplex mathematics, the temporal imaginary unit "j" is newly defined to distinguish from the spatial imaginary unit i, both of which satisfy i2=-1 and j2=-1.
Xiaoxing ZHANG Xiayu NI Masahiro IWAHASHI Noriyoshi KAMBAYASHI
In this paper, two universal building blocks for complex filter using CCIIs, CFCCIIs, grounded resistors and grounded capacitors are presented. These can be used to realize various complex bandpass filters with arbitrary order. The paper shows that the response error of the proposed circuit caused by nonideality of active components is more easily compensated than that of the conventional one employing op-amps, and that the sensitivities for all components are relatively small. Experimental results are used for verifying the validity of the proposed circuits.
This correspondence reports novel computationally efficient algorithms for multiplication of bicomplex numbers, which belong to hypercomplex numbers. The proposed algorithms require less number of real multiplications than existing methods. Furthermore, they give more effective implementation when applied to constant coefficient digital filters.
Teruyuki MIYAJIMA Kazuo YAMANAKA
In this paper, three issues concerning the linear adaptive receiver using the LMS algorithm for single-user demodulation in direct-sequence/code-division multiple-access (DS/CDMA) systems are considered. First, the convergence rate of the LMS algorithm in DS/CDMA environment is considered theoretically. Both upper and lower bounds of the eigenvalue spread of the autocorrelation matrix of receiver input signals are derived. It is cleared from the results that the convergence rate of the LMS algorithm becomes slow when the signal power of interferer is large. Second, fast converging technique using a prefilter is considered. The LMS based adaptive receiver using an adaptive prefilter adjusted by a Hebbian learning algorithm to decorrelate the input signals is proposed. Computer simulation results show that the proposed receiver provides faster convergence than the LMS based receiver. Third, the complexity reduction of the proposed receiver by prefiltering is considered. As for the reduced complexity receiver, it is shown that the performance degradation is little as compared with the full complexity receiver.
In this paper we consider all self-orthogonal [n, 1/2(n-1)] codes for n odd and 3 n 19, all self-dual [n, 1/2n] codes for n even and 2 n 24 and some other codes over GF(2) and answer to a question which of them have efficient coordinate ordering. As a result the exact values of their state complexities are determined. Sufficient conditions for codes to have an efficient coordinate ordering are derived also.
This paper proposes a new speech codec based on CELP for PHS multimedia communication. PHS portable terminals should consume as little power as possible, and the codec used in them has to be robust against channel errors. Therefore, the proposed codec operates with low computational complexity while reducing the deterioration in speech quality due to channel errors. This codec uses two new schemes to reduce computational complexity. One is moving average scalar quantization for the filter coefficients of the synthesis filter. This scheme requires 90% less complexity to quantize synthesis filter coefficients compared to the widely used vector quantization. The other is pre-selection for selecting an algebraic codebook used as random excitation source. An orthogonalization scheme is used for stable pre-selection. Deterioration of speech quality is suppressed by using CRC and parameter estimation for error protection. Two types of codec are proposed: a 10-ms frame type that transmits 160 bits every 10-ms and a 15-ms frame type that transmits 160 bits every 15 ms. The computational complexity of these codecs is less than 5 MOPS. In a nochannel error environment, the speech quality is equal to that of ITU-TG.726 at 32.0 kbit/s. With 0.3% channel error, both codecs offer more comfortable conversation than G.726. Moreover, at 1.0% channel error, the 10-ms frame type still provides comfortable conversation.
Emilio GAGO - RIBAS Maria J.Gonzalez MORALES Carlos Dehesa MARTINEZ
Gaussian beams constitute a very powerful tool to analyze radiation and scattering problems in high frequency regimes. The analysis of this kind of beams may be done by performing an analytical continuation of the real sources into the complex space. This is also a very powerful technique that arise, not only to this kind of solutions, but also to other solutions that may be very useful even for low frequency regimes. A complete parametrization of real propagation space in terms of the different type of complex beams solutions is presented in this paper. The analysis in the complex domain arises to different regions in the real space which may be anticipated and described through analytical transition regions. Some important conclusions may be derived from the results obtained, in particular the results related to the complex far field condition.
A bicomplex representation for time-harmonic electromagnetic fields appearing in scattering and diffraction problems is given using two imaginary units i and j. Fieldsolution integral-expressions obtained in the high-frequency and low-frequency limits are shown to provide the new relation between high-frequency diffraction and low-frequency scattering. Simple examples for direct scattering problems are illustrated. It may also be possible to characterize electric or magnetic currents induced on the obstacle in terms of geometrical optics far-fields. This paper outlines some algebraic rules of bicomplex mathematics for diffraction or scattering fields and describes mathematical evidence of the solutions. Major discussions on the relationship between high-frequency and low-frequency fields are relegated to the companion paper which will be published in another journal.
This paper presents a new generation method of the periodic orthogonal numerical sequences with small maximum amplitude. In the generation method, complex exponential sequences are used as the generating sequences and such periodic orthogonal numerical sequences are constructed from the discrete Fourier transform of the generating sequences. Until now, there has not been found a generation algorithm to derive such sequences with any period. It is shown that the proposed generation method can derive periodic orthogonal real sequences with the maximum amplitude less than 1.5 for the period 1N200 and periodic orthogonal coplex sequences with all the sbsolute amplitude value of 1 for any period.
Debatosh DEBNATH Tsutomu SASAO
This paper presents an exact minimization algorithm for AND-OR-EXOR three-level networks, where a single two-input exclusive-OR (EXOR) gate is used. The network realizes an EXOR of two sum-of-products expressions (EX-SOP), where the two sum-of-products expressions (SOP) can share products. The objective is to minimize the total number of different products in the two SOPs. An algorithm for the exact minimization of EX-SOPs with up to five variables are shown. Up to five variables, EX-SOPs for all the representative functions of NP-equivalence classes were minimized. For five-variable functions, we confirmed that minimum EX-SOPs require up to 9 products. For n-variable functions, minimum EX-SOPs require at most 92n-5 (n6) products.
Xiaoxing ZHANG Xiayu NI Masahiro IWAHASHI Noriyoshi KAMBAYASHI
In this paper, implementation of a first-order active complex filter with variable parameter using operational transconductance amplifiers (OTAs) and grounded copacitors is presented. The proposed configurations can be used as s key building block to realize high-order active complex filters with variable parameter in cascade and leapfrog configuration. Experimental results which are in good agreement with theoretical responses are also given o demonstrate the feasibility of the proposed configurations.
Shao-Chin SUNG Kunihiko HIRAISHI
Obradovic and Parberry showed that any n-input k-ary function can be computed by a depth 4 unit-weight k-ary threshold circuit of size O(nkn). They also showed that any n-input k-ary symmetric function can be computed by a depth 6 unit-weight k-ary threshold circuit of size O(nk+1). In this paper, we improve upon and expand their results. The k-ary threshold circuits of nonunit weight and unit weight are considered. We show that any n-input k-ary function can be computed by a depth 2 k-ary threshold circuit of size O(kn-1). This means that depth 2 is optimal for computing some k-ary functions (e.g., a PARITY function). We also show that any n-input k-ary function can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(kn). Next, we show that any n-input k-ary symmetric function can be computed by a depth 3 k-ary threshold circuit of size O(nk-1), and can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(knk-1). Finally, we show that if the weights of the circuit are polynomially bounded, some k-ary symmetric functions cannot be computed by any depth 2 k-ary threshold circuit of polynomial-size.
Xiaoxing ZHANG Masahiro IWAHASHI Noriyoshi KAMBAYASHI
In this paper a novel narrow-band bandpass filter with an output pair of analytic signals is presented. Since it is based on the complex analog filter, both synthesis and response characteristics of this filter are different from conventional bandpass filters. In the design of this filter, the frequency shift method is employed and the conventional lowpass to bandpass frequency transformation is not required. The analysis and examples show that the output signal pair of the proposed filter possesses same filtering characteristics and a 90 degree phase shifting characteristics in the passband. Therefore, the proposed filter will be used for a single sideband (SSB) signal generator without quadrature generator.