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 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.

Polarimetric SAR interferometry has been successful and attractive for forest parameters (tree height and canopy extinction) estimation. In this paper, we propose to use the ESPRIT algorithm to extract the interferometric phase of local scatterers with polarimetric and interferometric SAR data. Two or three local scattering waves can be extracted at each image patch when a fully polarimetric data set (HH, HV, VV) is available. Furthermore, the ESPRIT can estimate two dominant local scattering centers when only a dual polarimetric data set (e.g., VV and VH) is provided. In order to demonstrate effectiveness the proposed technqiue, we examined the relation between local scattering centers extracted by this method and complex coherence of the coherent scattering model for vegetation cover. The results show that the three-wave estimation can be more accurate than the two-wave case. The extracted interferometric phases with full and dual polarization data sets correspond to effective ground and canopy scattering centers. In this investigation, SIR-C/X-SAR data of the Tien Shan flight-pass are used.

A Radio Network (RN, for short) is a distributed system with no central arbiter, consisting of p radio stations each of which is endowed with a radio transceiver. In this work we consider single-hop, single channel RNs, where each station S(i), (1ip), initially stores si items which are tagged with the unique destination they must be routed. Since each item must be transmitted at least once, every routing protocol must take at least n = s1 + s2 + + sp time slots to route each item to its final destination. Similarly, each station S(i), (1ip), must be awake for at least si + di time slots to broadcast si items and to receive di items, where di denotes the number of items destined for S(i). The main contribution of this work is to present a randomized time- and energy-optimal routing protocol on the RN. Let qi, (1ip), be the number of stations that have items destined for S(i), q=q1 +q2 ++ qp, and ri be the number of stations for which S(i) has items. When qi is known to station S(i), our routing protocol runs, with probability exceeding 1 - , (f > 1), in n + O(q + log f) time slots with each station S(i) being awake for at most si + di + O(qi + ri + log f) time slots. Since qidi, risi, and qn always hold, our randomized routing protocol is optimal. We also show that, when the value of di is known to S(i), our routing protocol runs, with probability exceeding 1 - , (f > 1), in O(n + log f) time slots with no station being awake for more than O(si + di + log f) time slots.

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.

Although the subgraph isomorphism problem has various important applications, it is generally NP-complete and difficult to solve. Though a custom computing circuit can reduce the execution time substantially, it requires considerable hardware resources and is inapplicable to large problems. This paper examines the feasibility of data dependent designs, which are particularly suitable to a Field Programmable Gate Array (FPGA). The data dependent approach drastically reduces hardware requirements. For graphs of 32 vertices, the average logic scale of data dependent circuits is only 5% of the corresponding data independent circuit. The data dependent circuit is estimated to be maximally 460 times faster than the software. Even if the circuit generation time is included, a data dependent circuit is estimated to be 2.04 times faster than software for graphs of 32 vertices. The performance gain would increase for larger graphs.

The strong RSA assumption is an assumption that the following problem is hard to solve: Given an RSA modulus and a ciphertext, find a pair of plaintext and exponent corresponding to them. It differs from the standard RSA assumption in a sense that in the strong version, no exponent is given as an input. The strong RSA assumption is considered to be stronger than the RSA assumption, but their exact relationship is not known. We investigate the strength of the strong RSA assumption and show that the strong RSA assumption restricted to low exponents is equivalent to the assumption that RSA problem is intractable for any low exponent. We also show that in terms of algebraic computation, the strong RSA assumption is properly stronger than the RSA assumption if there exists an RSA modulus n such that gcd((n),3)=1 and RSA problem is intractable.

We fabricated 1.3µm AlGaInAs inner-stripe laser diodes (LDs), employing a GaInAsP waveguide layer and an n-InP current blocking layer. We compared the effects of the thickness of n-InP current blocking layer. A blocking layer with 500nm thick restricts the leakage current significantly. The inner-stripe LD was compared with the conventional ridge LD. I-L characteristics of both types of LDs were measured. Threshold currents of the inner-stripe LD and the ridge LD were 8.5 and 10.6mA, respectively. A threshold current of the inner-stripe LD is smaller than that of ridge LD. And the resistance of the inner-stripe LD was a few ohms lower than that of the ridge LD. Output power of 88mW was obtained at 200mA with 300µ m-long cavity. This was twice the power of a conventional ridge laser. The characteristic temperature of the inner-stripe LD was obtained 76 K from 20 to 85. We obtained a good linearity up to 100mA at 85. Therefore the inner-stripe LD has an advantage of high power devices.

We discuss applications of quantum computation to geometric data processing. Especially, we give efficient algorithms for intersection problems and proximity problems. Our algorithms are based on Brassard et al. 's amplitude amplification method, and analogous to Buhrman et al. 's algorithm for element distinctness. Revealing these applications is useful for classifying geometric problems, and also emphasizing potential usefulness of quantum computation in geometric data processing. Thus, the results will promote research and development of quantum computers and algorithms.

The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This paper proposes an O(n3) time algorithm for solving the minimum vertex ranking spanning tree problem on an interval graph.

This paper presents a new reconfigurable hardware paradigm, called evolvable hardware (EHW), and its application to the biomedical engineering problem of an artificial hand controller. Evolvable hardware is based on the idea of combining a reconfigurable hardware device with an artificial intelligence robust search technique called genetic algorithms (GAs) to execute reconfiguration autonomously. The first version of the EHW chip was designed in 1998, and this paper describes the latest improvements to the EHW chip, as well as outlining its architecture and the hardware implementation of the GA operations. Execution speed for genetic operations is shown to be about 38.7 times faster with the hardware implementation than with software program running on an AMD Athlon processor (1.2GHz). As an application of the EHW chip, this paper introduces a controller for a multi-functional prosthetic-hand, and presents experimental data in which a practical myoelectric pattern classification rate of 97.8% was achieved through the application of the EHW chip.

Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). In this paper, we prove that any series-parallel simple graph G has an L-edge-coloring if |L(e)| max{3,d(v),d(w)} for each edge e = vw, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. Our proof yields a linear algorithm for finding an L-edge-coloring of series-parallel graphs.

A dual greedy polyhedron is defined by a system of linear inequalities, where the right-hand sides are given by a submodular function and the coefficients matrix is given by the incidence vectors of antichains of a rooted forest. Faigle and Kern introduced this concept and showed that a dual greedy algorithm works for the linear program over dual greedy polyhedra. In this paper, we show that a dual greedy polyhedron is the isomorphic image of an ordinary submodular polyhedron under the Mobius function of the underlying rooted forest. This observation enables us to reduce linear optimization problems over dual greedy polyhedra to those over ordinary submodular polyhedra. We show a new max-min theorem for intersection of two dual greedy polyhedra as well.

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.

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

This paper presents an innovative 155Mb/s burst-mode laser transmitter chip, which was designed and successfully demonstrated, and contains several new subsystems: a digitally programmed current source, programmable up to 120mA with a resolution of 0.1mA, a fast but accurate intermittent optical level monitoring circuit, and a digital Automatic Power Control (APC) algorithm. This generic and intelligent chip was developed in a standard digital 0.35µm CMOS process. Extensive testing showed a high yield and algorithm stability, as well as excellent performance. During initialization, when the transmitter is connected to the Passive Optical Network (PON) for the first time, maximum three Laser Control Fields (LCF) are needed, with a length of 17bytes (0.88microsecond at 155Mb/s), to stabilize the laser output power. In this short time, the chip can regulate the launched optical output power of any FSAN (Full Service Access Network) compliant laser diode to the required level, even in the extreme circumstances caused by outdoor operation or by battery backup operation during power outages. Other tests show that the chip can further stabilize and track this launched optical power with a tolerance lower than 1dB over a wide temperature range, during the burst mode data transmission. The APC algorithm intermittently adjusts the optical power to be transmitted in a digital way, starting from loosely specified but safe preset values, to the required stable logic "1" and "0" level. No laborious calibration of the laser characteristic curve and storage of the calibration values in lookup tables are needed, nor any off-chip adjustable component. The power consumption is significantly reduced by disabling inactive circuitry and by gating the digital high-speed clock. Although this laser transmitter was developed for FSAN PON applications, which are standardized at a speed of 155Mb/s upstream, the design concept is quite generic and can be applied for developing a wide range of burst mode laser transmitters, such as required for Gigabit PON systems or other TDMA networks.

A parity check matrix for a binary linear code defines a bipartite graph (Tanner graph) which is isomorphic to a subgraph of a factor graph which explains a mechanism of the iterative decoding based on the sum-product algorithm. It is known that this decoding algorithm well approximates MAP decoding, but degradation of the approximation becomes serious when there exist cycles of short length, especially length 4, in Tanner graph. In this paper, based on the generating idempotents, we propose some methods to design parity check matrices for cyclic codes which define Tanner graphs with no cycles of length 4. We also show numerically error performance of cyclic codes by the iterative decoding implemented on factor graphs derived from the proposed parity check matrices.

A "based" plane triangulation is a plane triangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane triangulations with at most n vertices and with maximum degree at most D. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulation but the difference from the previous triangulation. By modifying the algorithm we can generate all biconnected based plane triangulations with exactly n vertices and maximum degree at most D in O(1) time per triangulation, and all biconnected (non-based) plane triangulations with exactly n vertices and maximum degree at most D in O(n3) time per triangulation without duplications.

The alternative c-means algorithm has recently been presented by Wu and Yang for robust clustering of data. In this letter, we analyze the convergence of this algorithm by transforming it into an equivalent form with the Legendre transform. It is shown that this algorithm converges to a local optimal solution from any starting point.

A heterogeneous parallel computing environment consisting of different types of workstations and communication links plays an important role in parallel computing. In many applications on the system, collective communication operations are commonly used as communication primitives. Thus, design of the efficient collective communication operations is the key to achieve high-performance parallel computing. But the heterogeneity of the system complicates the design. In this paper, we consider design of an efficient gather operation, one of the most important collective operations. We show that an optimal gather schedule is found in O(n2k-1) time for the heterogeneous parallel computing environment with n processors of k distinct types, and that a nearly-optimal schedule is found in O(n) time if k=2.