Xiaobei LIU Soo Ngee KOH Susumu YOSHIDA
Soft bit speech decoding, as a new approach of error concealment, is applied to the mixed excitation linear prediction (MELP) algorithm. Average residual redundancies of the quantized parameters are exploited in the error concealment process as an a priori knowledge of the source. Results show a significant SNR improvement for parameters decoded using the error concealment scheme.
The circular decoding algorithm for tail-biting convolutional codes is executed using a fixed number of computations and is suitable for DSP/ASIC implementations. This letter presents the performance and complexity trade-off in the circular decoding algorithm using an analytic bound on the error probability. An incremental performance improvement is shown as the complexity increases from O(L) to O(L+10K) where L is the length of the decoding trellis and K is the constraint length. The decoding complexity required to produce the maximum-likelihood performance is presented, which is applicable to many codes of practical interest.
Hiroshi HARADA Takako YAMAMURA Masayuki FUJISE
A method for estimating propagation characteristics is described that uses the characteristics of pilot-data-inserted orthogonal frequency division multiplexing (OFDM) signal and is suitable for high-mobility OFDM transmission scheme. Several pilot data are inserted periodically along the frequency axis before the inverse fast Fourier transformation (IFFT) process in the transmitter. At the receiver, the received OFDM signal is correlated with a prepared distinctive OFDM signal in which several pilot data are inserted in the same positions as in the transmitted OFDM symbols and zeros are inserted in the other positions. The propagation characteristics can be estimated precisely and used to cancel any interference caused by delayed waves. Computer simulation shows that this method can estimate the propagation characteristics, which can then be used to cancel the interference caused by delayed waves before the FFT at the receiver under fast multipath fading conditions.
Muhammad E.S. ELRABAA Mohab H. ANIS Mohamed I. ELMASRY
A new contention-free Domino logic (CF-Domino) that is especially suited for low threshold voltage (LVT) is reported. Its superior noise margin and speed over conventional Domino circuits for LVTs are demonstrated using HSPICE(R) simulations and a 0.25 µm CMOS technology with a supply voltage of 2.5 V. The impacts of the new technique on dynamic and leakage powers and area were evaluated. At a 3% area increase, and keeping the noise margins constant, the new CF-DOMINO achieves 20% less delay than conventional DOMINO as the threshold voltage scales from 450 mV down to 200 mV. It also achieved 13% less dynamic power and 5% less leakage at that threshold voltage.
Yegui XIAO Takahiro MATSUO Katsunori SHIDA
Adaptive Fourier analysis of sinusoidal signals in noise is of essential importance in many engineering fields. So far, many adaptive algorithms have been developed. In particular, a filter bank based algorithm called constrained notch Fourier transform (CNFT) is very attractive in terms of its cost-efficiency and easily controllable performance. However, its performance becomes poor when the signal frequencies are non-uniformly spaced (or spaced with unequal intervals) in the frequency domain. This is because the estimates of the discrete Fourier coefficients (DFCs) in the CNFT are inevitably corrupted by sinusoidal disturbances in such a case. This paper proposes, at first, a modified CNFT (MCNFT), to compensate the performance of the CNFT for noisy sinusoidal signals with known and non-uniformly spaced signal frequencies. Next, performance analysis of the MCNFT is conducted in detail. Closed form expression for the steady-state mean square error (MSE) of every DFC estimate is derived. This expression indicates that the MSE is proportional to the variance of the additive noise and is a complex function of both the frequency of each frequency component and the pole radius of the bandpass filter used in the filter bank. Extensive simulations are presented to demonstrate the improved performance of the MCNFT and the validity of the analytical results.
A new rewritable medium utilizing a guest-host (G-H) polymer-dispersed liquid-crystal (PDLC) film has been developed in our laboratory. The medium is thermally written and electrically erased. It is portable, like paper, and can store recorded data because of the memory effect of smectic-A liquid crystal (SmA LC), which exhibits bistable states of homeotropic and focal conic alignment. Dichroic dye is added to the SmA LC to form the G-H type. An evaluation of the characteristics revealed that this medium exhibits both high contrast and good reliability.
Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers H-coloring problems, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors can be represented by a graph H, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices can be used for adjacent vertices. Especially, H-coloring problem with a complete graph H of order k is equivalent to the traditional k-coloring problem. This paper presents sufficient conditions such that H-coloring problem can be reduced to an H-coloring problem, where H is a subgraph of H. And it shows a hierarchy about classes of H-colorable graphs for any complement graph H of a cycle of order odd n 5.
Naris RANGSINOPPAMAS Tanun JARUVITAYAKOVIT Prasit PRAPINMONGKOLKARN
In this paper, we propose a new consolidation algorithm called the Selective Backward Resource Management (BRM) cell Feedback (SBF) algorithm. It achieves a fast response and low consolidation noise by selectively forwarding BRM cell from the most congested branch to the source instead of waiting from all branches. Mathematical models are derived to quantitatively characterize the performance, i.e. the response time and ACR of the source, of SBF and previously proposed algorithms. The interoperation of consolidation algorithms in point-to-multipoint available bit rate (ABR) is investigated. We address response time, consolidation noise and the effect of asymmetrical round trip delay (RTD) from branch point to destinations aspects. All combinations of four different consolidation algorithms are interoperated in both local/metropolitan area network (LAN/MAN) and wide area network (WAN) configuration. By a simulation method, we found that the consolidation algorithm used at the uppermost stream branch point, especially in WAN configuration, plays an important role in determining the performance of the network. However, consolidation algorithm used at the lower stream branch point affects the network performance insignificantly. Hence, in order to achieve a good and effective performance of the consolidation algorithms interoperated network, a fast response with low consolidation noise algorithm should be used at the uppermost stream branch point and a simple and easy to implement algorithm should be used at the lower stream branch point.
Koji CHIDA Shigenori UCHIYAMA Taiichi SAITO
Since the invention of the RSA scheme, a lot of public-key encryption and signature schemes based on the intractability of integer factoring have been proposed. Most employ integers of the form N = p q, such as the RSA scheme, but some employ integers of the form N = pr q. It has been reported that RSA decryption speed can be greatly improved by using N = pr q integers for large r. On the other hand, Boneh et al. proposed a novel integer factoring method for integers such as N = pr q for large r. This factoring algorithm, the so-called Lattice Factoring Method, is based on the LLL-algorithm. This paper proposes a new method for factoring integers of the form N = pr q for large r and gives a new characterization of r such that factoring integers N = pr q is easier. More precisely, the proposed method strongly depends on the size and smoothness of the exponent, r. The theoretical consideration of and implementation of our method presented in this paper show that if r satisfies a certain condition our method is faster than both Elliptic Curve Method and Lattice Factoring Method. In particular, the theoretical consideration in this paper mainly employs the techniques described in the excellent paper by Adleman, Pomerance and Rumely that addresses primality testing.
Jun TAKAHASHI Hideki TODE Koso MURAKAMI
The advances in services using the present Internet mean that there will be increasing demand for Video on Demand (VoD) on the Internet in the near future. However, because of the best-effort characteristics of the Internet, it is important to suppress the degradation of communication quality caused by packet dropping when Internet traffic is congested. This paper focuses on MPEG transmission over the Internet, and suitable control mechanisms are established for an acceptable Quality of Service (QoS) improvement through detailed evaluation. Packets are classified using a frame-based scheme. The server applies the proposed End-to-End control scheme and shuffles the order of packets to avoid burst dropping, and may omit selected packets belonging to certain frames prior to forwarding. At the intermediate routers, transferred packets are transmitted according to Round Robin (RR) or Weighted Round Robin (WRR) scheduling, and are dropped statistically using selective Random Early Detection (RED) corresponding to frame attributes when there is congestion. We evaluate the proposed performance of transmission method using both computer simulations and empirical measurements of picture quality. The results show that when the traffic volume cannot be estimated in the intermediate routers, the combined use of RR, shuffling and conditional RED is effective, and when the traffic volume can be estimated, the combination of WRR, rate control and RED is effective.
In order for a service discipline to be used for guaranteed service networks at very high speed, its overall implementation must be scalable while it provides as wide a network schedulability region as possible. From this point of view, GPS-based service disciplines provide a narrow network schedulability region while EDF-based disciplines suffer from the implementation complexities of rate-controllers and admission control. Alternatively, although service disciplines based on service-curves can provide a wider network schedulability region than GPS-based and EDF-based disciplines, they may have even worse implementation complexities than EDF-based disciplines. In this paper, we propose to employ a service discipline based on our specific service-curves. We show that our service discipline has comparable implementation complexity to GPS-based disciplines while providing the same wide network schedulability region that EDF-based disciplines can provide. In fact, this service discipline is an SCED service discipline proposed in [14]. However, our specific service-curves provide the SCED service discipline with the same network schedulability region that EDF-based disciplines can provide, O(1) complexity for deadline calculation, and O(N) complexity for admission control where N is the number of sessions.
Hirotoshi HONMA Shigeru MASUYAMA
If there exist any two vertices in G whose distance becomes longer when a vertex u is removed, then u is defined as a hinge vertex. Finding the set of hinge vertices in a graph is useful for identifying critical nodes in an actual network. A number of studies concerning hinge vertices have been made in recent years. In a number of graph problems, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs in O(log n) time with O(n) processors on CREW PRAM for finding all hinge vertices of a trapezoid graph.
Jung-Sik JEONG Kei SAKAGUCHI Jun-ichi TAKADA Kiyomichi ARAKI
It is known that MUSIC and ESPRIT algorithms can estimate simultaneously both the instantaneous Direction of Arrival (DOA) and the instantaneous Angular Spread (AS) in multiple scattering environments. These algorithms use the Extended Array Mode Vector (EAMV) with complex angle. The previous work evaluated the performance of those algorithms by comparing the estimated DOA and the estimated AS with the DOA and the AS given in the EAMV, which uses the first-order approximation. Thus, this evaluation method has not clearly reflected the estimation accuracy of MUSIC and ESPRIT. This paper presents the joint estimation performance of MUSIC and ESPRIT by introducing the criteria for evaluation. For this, the spatial signature (SS) is reconstructed from the estimates of the DOA and the AS, and compared to the true SS in the meaning of data fitting.
We consider equalizer initialization problems when the transmitted symbol rate is higher than the available channel bandwidth. In this case, the coefficients of an adaptive equalizer in the receiver can be updated only once per a predefined symbol period, requiring unacceptably long training time. The training time can be reduced significantly if the equalizer begins the training process from a properly initialized condition. In this letter, a fast initialization method is analytically designed for a minimum mean squared error (MMSE) type equalizer. Finally, the initialization performance is verified by computer simulation.
Hiro-o SAITO Shiro MATUURA Tomomi MATSUI
In this paper, we consider a network design problem with hub-and-spoke structure. We propose a relaxation technique for the problem where the location of hub nodes is given and decides the allocation of non-hub nodes to one of the hub nodes. We linearize the non-convex quadratic objective function of the original problem, introducing Hitchcock transportation problems defined for each pair of non-hub nodes. We provide two linear relaxation problems, one based on the Hitchcock transportation problems and the other on the dual Hitchcock transportation problems. We show the tightness of the lower bounds obtained by our formulations by computational experiences.
Hongku KANG Wooncheol HWANG Kiseon KIM
We propose a subchannel power control scheme in the OFDM system, which transmits data with a variable power level for each subchannel based on the received SNR. The OFDM system, employing the D-QPSK modulation and the proposed subchannel power control with a grouping coefficient equal to 3, gives about 2.3 dB gain in Eb/N0 comparing with the conventional OFDM system, under the two-ray multipath channel with the mean value of the second-ray's attenuation coefficient equal to 0.25, for the required BER equal to 10-5.
Anna YAMAGUCHI Masayuki ARAI Hitoshi KUROSU Satoshi FUKUMOTO Kazuhiko IWASAKI
In this paper, we propose and analytically evaluate the use of punctured convolutional codes for recovering packets lost in multicast transmission. An independent erasure channel is assumed for packets transmission over a star topology. The analysis provides a method for determining the recoverability and the post-reconstruction receiving rate for a given convolutional code. We theoretically evaluate the effectiveness of the proposed approach taking into account two different parameters: the number of transmissions per packet and the number of packets needed to be sent to guarantee the reception of data. Finally, we compare the proposed approach with the scheme when parity packets are generated based on Reed-Solomon codes.
This letter investigates sidelobe levels of a two-bit digital phased array composed of a small number of elements. Among several phase shifter designs applicable to phased arrays, a two-bit design needs the least number of circuit elements so that the development and manufacturing need the lowest cost. Now the following questions arise. Is a two-bit phased array practical? How low can its sidelobe level be reduced? To answer the questions, three methods are tried to reduce the sidelobe level of a uniformly-excited linear array of isotropic elements. The methods are the quadratic-phase feed method, the partially randomizing method of periodic phase errors, and the genetic algorithm (GA) approach. Among the methods, the quadratic-phase feed method provides the lowest sidelobe level around -12.5 dB - -13.2 dB in the steering angles from 0 to 48 degrees for a 21-element, half-wavelength spacing array, and -11.2 dB - -13.0 dB in the steering angles from 0 to 30 degrees for an 11-element, 0.6-wavelength spacing array. Although it depends on the system requirement, these values would be acceptable in some applications, hence a two-bit phased array designed properly may be practical in an actual system.
Jacir Luiz BORDIM Jiangtao CUI Naohiro ISHII Koji NAKANO
A radio network is a distributed system with no central shared resource, consisting of n stations each equipped with a radio transceiver. One of the most important parameters to evaluate protocols in the radio networks is the number of awake time slots in which each individual station sends/receives a data packet. We are interested in devising energy-efficient initialization protocols in the single-hop radio network (RN, for short) that assign unique IDs in the range [1,n] to the n stations using few awake time slots. It is known that the RN can be initialized in O(log log n) awake time slots, with high probability, if every station knows the number n of stations in the RN. Also, it has been shown that the RN can be initialized in O(log n) awake time slots even if no station knows n. However, it has been open whether the initialization can be performed in O(log log n) awake time slots when no station knows n. Our main contribution is to provide the breakthrough: we show that even if no station knows n, the RN can be initialized by our protocol that terminates, with high probability, in O(n) time slots with no station being awake for more than O(log log n) time slots. We then go on to design an initialization protocol for the k-channel RN that terminates, with high probability, in O(n/k + (log n)2) time slots with no station being awake for more than O(log log n) time slots.
Le Minh TUAN Jaedon PARK Giwan YOON Jewoo KIM
We propose two novel blind LMS algorithms, called exponential step size LMS algorithms (ES-LMS), for adaptive array antennas with fast convergence speeds. Both of the proposed algorithms are much better at tracking signal sources than the conventional LMS algorithms. In addition, they require neither spatial knowledge nor reference signals since they use the finite symbol property of digital signal. Computer simulations verify performances of the two proposed algorithms.