Two implementation schemes for a two-step SOVA (Soft Output Viterbi Algorithm) decoder are proposed and verified in a chip. One uses the combination of trace back (TB) logic to find the survivor state and double trace back logic to find the weighting factor of a two-step SOVA. The other is that the reliability values are divided by a scaling factor in order to compensate for the distortion brought by overestimating those values in SOVA. We introduced a fixed scaling factor of 0.25 or 0.33 for a rate 1/3 and designed an 8-state Turbo decoder with a 256-bit frame size to lower the reliability values. The implemented architecture of the two-step SOVA decoder allows important savings in area and high-speed processing compared with the one-step SOVA decoder using register exchange (RE) or trace-back (TB) method. The chip is fabricated using 0.65 µm gate array at Samsung Electronics and it shows higher SNR performance by 2 dB at the BER 10-4 than that of a two-step SOVA decoder without a scaling factor.

This paper presents an extension of the database query language SQL to include queries against a database with natural language annotations. The proposed scheme is based on Concept Coupling Model, a language model for handling natural language sentence structures. Integration of the language model with the conventional relational data model provides a unified environment for manipulating information sources comprised of relational tables and natural language texts.

This paper presents an improved phoneme-history-dependent (PHD) search algorithm. This method is an optimum algorithm under the assumption that the starting time of a recognized word depends on only a few preceding phonemes (phoneme history). The computational cost and the number of recognition errors can be reduced if the phoneme-history-dependent search uses re-selection of the preceding word and an appropriate length of phoneme histories. These improvements increase the speed of decoding and help to ensure that the resulting word graph has the correct word sequence. In a 65k-word domain-independent Japanese read-speech dictation task and 1000-word spontaneous-speech airline-ticket-reservation task, the improved PHD search was 1.2-1.8 times faster than a traditional word-dependent search under the condition of equal word accuracy. The improved search reduced the number of errors by a maximum of 21% under the condition of equal processing time. The results also show that our search can generate more compact and accurate word graphs than those of the original PHD search method. In addition, we investigated the optimum length of the phoneme history in the search.

A minor component analysis approach based on the generalized sidelobe canceler is presented to realize the blind suppression of multiple-access interference in multicarrier code division multiple access systems. With a rough user-code and timing estimations, this proposed method of less computation performs the same as minimum mean square error detectors and outperforms existing blind detectors. Simulation results illustrate the effectiveness of the blind multiuser detection.

This paper discusses formal modeling and performance evaluation for a type of dynamic change of workflow, called Migrate. Workflow means the flow of work and is designed to process similar instances, called cases. Companies need to continuously refine their current workflow in order to adapt them to various requirements. The change of a current workflow is called dynamic change of the workflow. Before changing a workflow, there exist cases in the workflow. If these cases are ignored or fall into deadlock, the changed workflow would become inconsistent. Since Ellis et al. proposed three change types, Flush, Abort, and Synthetic Cut-Over that keep consistency of workflows in 1995, various change types have been proposed, in which there is a promising change type called Migrate that is proposed by Sadiq et al. Sadiq et al. proposed the concept of Migrate, but did not give a formal model of Migrate. Meanwhile, we have proposed a measure, called change time, in order to evaluate dynamic change of workflows, and used this measure to evaluate the performance on change time for Ellis et al. 's three change types. However, the performance evaluation on change time for Migrate has not been done. In this paper, we first give a Petri-nets-based model of Migrate. Then we present a method of computing change time based on the net model. Finally, we apply the method to 270 examples and show the comparison results between Migrate and Ellis et al. 's three change types.

With the advance of high-speed network technologies, availability and popularity of streaming media contents over the Internet has grown rapidly in recent years. Because of their distinct statistical properties and user viewing patterns, traditional delivery and caching schemes for normal web objects such as HTML files or images can not be efficiently applied to streaming media such as audio and video. In this paper, we therefore propose an integrated caching scheme for streaming media with segment-based caching and hierarchically distributed proxies. Firstly, each stream is divided into segments and their caching algorithms are considered to determine how to distribute the segments into different level proxies efficiently. Secondly, by introducing two kinds of segment priorities, segment replacing algorithms are proposed to determine which stream and which segments should be replaced when the cache is full. Finally, a Web-friendly caching scheme is proposed to integrate the streaming caching with the conventional caching of normal web objects. Performance of the proposed algorithms is verified by carrying out simulations.

A Hyper-Universal Switch Box (HUSB) [1]-[3] can yield a feasible (detailed) routing solution for any given routing requirement of multi-pin nets or multi-point connections of surrounding terminals. This flexible routing structure obviously possesses multiple potential applications for re-configurable systems such as FPGAs and communication switching networks [4],[5]. Based on the same decomposition theory developed in the design scheme of such powerful switching structure, a simple routing algorithm can also be developed. The router is exact in terms of its assured capability in finding a routing solution, and it is efficient due to the divide and conquer nature and simple mapping scheme for pre-analyzed routing patterns saved in data base.

A novel postprocessing algorithm for concealing spatial block errors in block-based coded images is proposed using block classification with a variable operating region (VOR). In the proposed algorithm, a missing block is classified as flat, edge, or complex based on local information from the surrounding blocks which is extracted using a Sobel operation in a VOR. In this case, the VOR is determined adaptively according to the number of edge directions in the missing block. Using the classification, the flat blocks are then concealed by the linear interpolation (LI) method, the edge blocks are concealed by the boundary multi-directional interpolation (BMDI) method, and the complex blocks are concealed by a combined linear interpolation and boundary matching (CLIBM) method. Experimental results demonstrated that the proposed algorithm improved the PSNR and visual quality of the concealment for both original images and JPEG compressed images, and produced better results than conventional algorithms.

In this paper, we propose a new multistage (iterative) structure where Kalman channel estimation and parallel interference cancellation multiuser detection are conducted in every stage (iteration). The proposed scheme avoids the complexity of the decorrelator in front of Kalman channel estimator, and has better performance than the previous scheme.

In an attempt to improve the performance under frequency selective fading environment, we develop in this paper an orthogonal frequency division multiplex (OFDM) system in which adaptive interleaving is applied. The adaptive interleaving is a method that assigns symbols adaptively to the subcarriers in order to cope with frequency selective fading based on a channel state information (CSI) sent back from the reception end. The concept of adaptive interleaving is to maximize a free Euclidean distance in the limited interleave size. In this paper, we extend the method by an introduction of bit interleaving and multiple trellis coded modulation (MTCM). MTCM assigns two or more symbols to one trellis branch and shows good performance in frequency selective fading. If we could assign those set of symbols with an aid of the adaptive interleaving, the performance improvement can be expected. Another improvement method considered in this paper is the use of bit interleaving. The bit interleaving techniques randomize the effect of channel more efficiently compared to the case of symbols interleaving. Thus the further performance improvement is expected. One draw back is that since the interleaving process is done in bit level, bit interleaving can not be applied to TCM nor MTCM. In this paper, we mainly focus on adaptive bit and symbol interleaving and discuss the performance from the point of interleaving effect, and the error correcting code (convolutional code and MTCM).

This paper introduces a design for testability (DFT) scheme for delay faults of a controller-data path circuit. The scheme makes use of both scan and non-scan techniques. First, the data path is transformed into a hierarchically two-pattern testable (HTPT) data path based on a non-scan approach. Then an enhanced scan (ES) chain is inserted on the control lines and the status lines. The ES chain is extended via the state register of the controller. If necessary, the data path is further modified. Then a test controller is designed and integrated to the circuit. Our approach is mostly based on path delay fault model. However the multiplexer (MUX) select lines and register load lines are tested as register transfer level (RTL) segments. For a given circuit, the area overhead incurred by our scheme decreases substantially with the increase in bit-width of the data path of the circuit. The proposed scheme supports hierarchical test generation and can achieve fault coverage similar to that of the ES approach.

We developed a new MU-type fixed optical attenuator for 4.5 mm pitch packaging. We succeeded in miniaturizing the attenuator by adopting a design employing an MUJ plug. This fixed optical attenuator achieved a tensile strength of greater than 70 N, which is the same as that of a conventional fixed optical attenuator, and also exhibited good environmental and mechanical durability. The new fixed optical attenuator can be used in existing communication devices in which 4.5 mm pitch MU adaptors are already installed.

Karger, Motwani and Sudan presented a graph coloring algorithm based on semidefinite programming, which colors any k-colorable graph with maximum degree Δ using (Δ1-2/k) colors. This algorithm leads to an algorithm for k-colorable graph using (n 1-3/(k+1)) colors. This improved Wigderson's algorithm, which uses O(n1-1/(k-1)) colors, containing as a subroutine an algorithm using (Δ+1) colors for graphs with maximum degree Δ. It is easy to imagine that an algorithm which uses less colors in terms of Δ leads to an algorithm which uses less colors in terms of n. In this paper, we consider this influence assuming that we have an algorithm which uses (Δ 1-x/k) colors for 2

12 on/off power splitters at λ=0.63µm have been produced in LiNbO3 substrates using strain-induced channel waveguides formed by magnetron deposition of surface metal films and lift-off technology. The static strain resulting from thermal expansion mismatch between the substrate and the metal films induces a localized increase in the refractive index via the strain-optic effect. On/off voltage of about 25V has been demonstrated.

The problem of constructing the suffix tree of a tree is a generalization of the problem of constructing the suffix tree of a string. It has many applications, such as in minimizing the size of sequential transducers and in tree pattern matching. The best-known algorithm for this problem is Breslauer's O(nlog |Σ|) time algorithm where n is the size of the CS-tree and |Σ| is the alphabet size, which requires O(nlog n) time if |Σ| is large. We improve this bound by giving an optimal linear time algorithm for integer alphabets. We also describe a new data structure, the Bsuffix tree, which enables efficient query for patterns of completely balanced k-ary trees from a k-ary tree or forest. We also propose an optimal O(n) algorithm for constructing the Bsuffix tree for integer alphabets.

Counting the number of points of Jacobian varieties of hyperelliptic curves over finite fields is necessary for construction of hyperelliptic curve cryptosystems. Recently Gaudry and Harley proposed a practical scheme for point counting of hyperelliptic curves. Their scheme consists of two parts: firstly to compute the residue modulo a positive integer m of the order of a given Jacobian variety, and then search for the order by a square-root algorithm. In particular, the parallelized Pollard's lambda-method was used as the square-root algorithm, which took 50CPU days to compute an order of 127 bits. This paper shows a new variation of the baby step giant step algorithm to improve the square-root algorithm part in the Gaudry-Harley scheme. With knowledge of the residue modulo m of the characteristic polynomial of the Frobenius endomorphism of a Jacobian variety, the proposed algorithm provides a speed up by a factor m, instead of in square-root algorithms. Moreover, implementation results of the proposed algorithm is presented including a 135-bit prime order computed about 15 hours on Alpha 21264/667 MHz and a 160-bit order.

The rapid spread of the Internet has led to the construction of broadband networks and the steady installation of optical fiber to the home. The air blowing cable system makes it possible to construct optical fiber networks efficiently and economically when the service demand is unpredictable. We have installed this system for intra-building applications. In this paper, we report ways of applying the air blowing system to aerial distribution using access networks. We showed that certain problems must be overcome before the system can be used for aerial applications. We describe these problems, which include those related to installation distance and environmental conditions and also the system components. In particular, the characteristics at high temperature were degraded because of a reduction in the flux. However, we were able to improve these characteristics by adopting the flexibility of the optical fiber unit.

The power dissipation tolerances for InP/ InGaAs uni-travelling-carrier photodiodes (UTC-PDs) and pin-PDs under high power optical inputs are compared. Catastrophic failures occur at constant power dissipations of 240 and 160mW for the UTC-PDs and pin-PDs, respectively. Scanning electron microscope observations confirm that the areas of destruction are located in the high electric-field region in the depletion layer.

A new algorithm for efficient arithmetic in an optimal extension field is proposed. The new algorithm improves the speeds of multiplication, squaring, and inversion by performing two subfield multiplications simultaneously within a single integer multiplication instruction of a CPU. Our algorithm is used to improve throughputs of elliptic curve operations.

Consider an undirected graph G=(V,E) with n (=|V|) vertices and m (=|E|) edges. It is well-known that the problem of computing the sequence Nn-1,Nn,...,Nm is #P-complete (see e.g.,[3]), where Ni denotes the number of connected spanning subgraphs with i (n-1!im) edges in G. In this paper, by proving new inequalities on the sequence Nn-1,Nn,...,Nm, we show an interesting and stronger property that the sequence γn-1,γn,...,γm, where γi denotes the average number of spanning trees in the connected spanning subgraphs with i edges, is a convex sequence as well as a monotonically increasing sequence, although this property does not hold for the sequence Nn-1,Nn,...,Nm.