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.

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.

Control scheme for accurately optimizing (and also automatically stabilizing) the interferometer phase bias of Symmetric-Mach-Zehnder (SMZ)-type ultrafast all-optical switches is proposed. In this control scheme, a weak cw light is used as a supervisory input light and its spectral power ratio at the switch output is used as a bipolar error signal. Our experimental result at 168-Gb/s 16:1 demultiplexing with a hybrid-integrated SMZ switch indicates the feasibility and the sensitivity of this control scheme.

We demonstrate a multi-wavelength (40WDM 10Gbit/s) optical packet router capable of processing 4 Gigapackets/s based on all-optical label generation and recognition using 16-bit, 20Gbit/s four-level phase coding superstructure fibre Bragg gratings. Error free operation is obtained for the switched packets when all 40 channels are transmitting simultaneously.

The purpose of this paper is to discuss length estimation based on digitized curves. Information on a curve in the Euclidean plane is lost after digitization. Higher resolution supports a convergence of a digital image towards the original curve with respect to Hausdorff metric. No matter how high resolution is assumed, it is impossible to know the length of an original curve exactly. In image analysis we estimate the length of a curve in the Euclidean plane based on an approximation. An approximate polygon converges to the original curve with an increase of resolution. Several approximation methods have been proposed so far. This paper proposes a new approximation method which generates polygonal curves closer (in the sense of Hausdorff metric) in general to its original curves than any of the previously known methods and discusses its relevance for length estimation by proving a Convergence Theorem.

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.

The one dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industries. As the setup costs of cutting patterns become more dominant in recent cutting industry, we consider a variant of 1D-CSP, in which the total number of applications of cutting patterns is minimized under the constraint that the number of different cutting patterns is specified in advance. We propose a local search algorithm that uses the neighborhood obtained by perturbating one cutting pattern in the current set of patterns, where the perturbations are done by utilizing the dual solution of the auxiliary linear programming problem (LP). In this process, in order to solve a large number of LPs, we start the criss-cross variation of the simplex algorithm from the optimal simplex tableau of the previous solution, instead of starting it from scratch. According to our computational experiment, it is observed that the proposed algorithm obtains a wide variety of good solutions which are comparable to the existing heuristic approaches.

Our work introduces a speech enhancement algorithm that modifies on-line the spectral representation of degraded speech to approximate the spectral coefficients of high quality speech. The proposed framework is based on the application of Discrete Fourier Transform (DFT) to a large ensemble of clean speech frames and the estimation of parametric, heavy-tail non-Gaussian probability distributions for the spectral magnitude. Each clean spectral band possesses a unique pdf. This is selected according to the smallest Kullback-Leibler divergence between each candidate heavy-tail pdf and the non-parametric pdf of the magnitude of each spectral band of the clean ensemble. The parameters of the distributions are derived by Maximum Likelihood Estimation (MLE). A maximum a-posteriori (MAP) formulation of the degraded spectral bands leads to soft threshold functions, optimally derived from the statistics of each spectral band and effectively reducing white and slowly varying coloured Gaussian noise. We evaluate the new algorithm on the task of improving the quality of speech perception as well as Automatic Speech Recognition (ASR) and demonstrate its robustness at SNRs as low as 0 dB.

TLSP (Thread-Level Speculative Parallel processing) architecture is a growing processor architecture. Parallelism of a program executed on this architecture is ruled by the combination of techniques which relax data dependences. In this paper, we evaluate the limits of parallelism of the TLSP architecture by using abstract machine models. We have three major results. First, if we use solely each technique which relaxes data dependences, "renaming" has a large effect on the TLSP architecture. Second, combinatorial use of "memory disambiguation" and "renaming" leads to huge parallelism. Third, constant effects are obtained by concurrent use of "value prediction" and other techniques.

In this paper, we propose a novel pulse-coupled neural network (PCNN) simulator using a programmable gate array (PGA) technique. The simulator is composed of modified phase-locked loops (PLLs) and a programmable gate array (PGA). The PLL, which is modified by the addition of multiple inputs and multiple feedbacks, works as a neuron. The PGA, which controls the network connection, works as nodes of dendritic trees. This simulator, which has 16 neurons and 32 32 network connections, is designed on a chip (4.73mm 4.73mm), and its basic operations such as synchronization, an oscillatory associative memory, and FM interactions are confirmed using circuit simulator SPICE.

Reconfigurable architectures have been focused for its potential on achieving high performance by reconfiguring special purpose circuits for a target application and its flexibility due to its ability of reconfiguring. We have set our sights on use of a reconfigurable architecture as a general-purpose computer by extending the advantageous properties of the architecture. To achieve the goal, a generalized execution model for reconfigurable architecture is required, so we have proposed an Ideal PARallel Structure (I-PARS) execution model. In the I-PARS execution model, any programs based on its model has no restriction depending on hardware structures based on a specific reconfigurable processor, which makes it easier to develop software. Further, we have proposed a PARS architecture which executes programs based on the I-PARS execution model effectively. The PARS architecture has a large reconfigurable part for highly parallel execution, which utilizes parallelism described on the I-PARS execution model. For effective utilization of the reconfigurable part in the PARS architecture, it has an ability to reconfigure and execute operations simultaneously in one cycle. Further, the PARS architecture supports branch operations to introduce control flow in an execution on the architecture, which makes it possible to skip an execution which does not produce a valid result. In this paper, we introduce the detailed structure of an implemented prototype processor based on the PARS architecture. In the implementation, 420,377 CMOS transistors were used, which was only 3.8% of the number of transistors used in the UltraSPARC-III in logic circuits. Additionally, we evaluated the performance of the prototype processor by using some benchmark programs. From the evaluation results, we found that the prototype processor could achieve nearly the same performance and be implemented with extremely the less number of transistors compared with UltraSPARC-III 750MHz.

This paper studies the necessity of local CFAR processing in CFAR detection with multisensors. This necessity is shown by comparison between centralized CFAR detection and the distributed CFAR detection scheme based on local CFAR processing, under three typical backgrounds and in several cases of mismatching ρ, the relative ratio of local clutter power level in sensors in a homogeneous background. Results show that centralized CFAR processing can not be considered as CFAR without exact prior knowledge of ρ. In addition, even if the knowledge of ρ is available, the great difference among local clutter power levels can also result in severe performance degradation of centralized CFAR processing. In contrast, the distributed CFAR detection based on local CFAR processing is not affected by ρ at all, a fact which was proposed in a previous published paper. Therefore, the CFAR processing must be made locally in sensors for CFAR detection with multisensors.

We have formed simple polarization-controller arrays by inserting liquid crystal (LC) in trenches cut across planar lightwave circuits (PLCs). We fabricated LC layers for use as polarization controllers on PLCs in two ways; in one, the ultra-thin layer of LC is held in a cell that is inserted into a trench on the PLC while in the other, the trench is directly filled with the LC. The ultra-thin LC cell can change the phase of 1.55-µm light from 0 to 3π while the LC filling can change the phase of light at the same wavelength from 0 to 12π below 5Vrms. Two former parallel-aligned ultra-thin LC cells, where the directions of alignment of the liquid crystals are rotated by 45 relative to each other, are capable of converting light with an arbitrary input polarization to TE or TM polarization. Ultra-thin cells of twisted nematic LC can switch the polarization between TE and TM modes with an extinction ratio of -15dB. The array we fabricated had a pitch of 1 mm and 5 elements, but an array with more than 100 elements and a pitch below 125µm will easily be possible by using finely patterned transparent electrodes. We have also applied our techniques to the fabrication of LC-based variable optical attenuators (VOA) on the PLC.

Partial face images, e.g., eyes, nose, and ear images are significant for face recognition. In this paper, we present a method for partial face extraction and recognition based on Radial Basis Function (RBF) networks. Focus has been centered on using ear images because they are not influenced by facial expression, and the influences of aging are negligible. Original human side face image with 320240 pixels is input, and then the RBF network locates the ear and extracts it with a 200120 pixel image. Next, another RBF network is constructed for the purpose of recognition. An algorithm that determines the radius of an RBF function is proposed. Dynamic radius, so called as compared to static one, is found through the algorithm that makes RBF functions adaptable to the training samples. We built a database that contains 600 side face images, from 100 people, to test the method and the results of both extraction and recognition are satisfied.

In this paper, we present an Internet personal live-broadcasting server system. Our solution is not only for experts but also for amateur users who want to broadcast using simple multimedia equipment. For scalable broadcasting services, we developed multiple-channel establishment and channel expansion. Concurrent services for a large number of broadcasting channels are effectively provided. Also, the capacity of channels can be expanded as the number of participants increases. Furthermore, for the sake of complete live broadcasting with high-quality transmission, the system supports both TCP (transmission control protocol) and UDP (user datagram protocol) according to the status of network environments as well as the received packet loss in the user system. The performance of the system is effectively evaluated at such practical commercial sites as well-known community and E-business sites.

The authors proposed a switching beam slot array antenna with a 4-way Butler matrix. All are integrated in one substrate with post-wall waveguide techniques. The planar Butler matrix is realized by using short slot directional couplers (cross coupler). Experiments in 26GHz band confirmed the key operation of this antenna; almost identical four beams are switched to cover the total of horizontal 90-degree sector with equal angular spacing.

Fingerprinting is one of the digital watermarking techniques, and is becoming more important as a copyright protection technique. Fingerprinting must resist collusion attacks. As a security index, "c-secureness" has been proposed, but it has been known that there is indeed no c-secure code. In this paper, we introduce a new index to measure the resilience of fingerprinting for collusion attacks and obtain some upper bounds and a lower bound on the index.

We designed an FPGA-based parallel machine called "RASH"(Reconfigurable Architecture based on Scalable Hardware) for high speed and flexible signal/data processing. Cryptanalysis is one of the killer applications for FPGA-based machines because huge amounts of logical and/or simple arithmetic operations are required and FPGA is suitable for this. One of the well-known activities in cryptanalysis is the DES (Data Encryption Standard) cracking contest conducted by RSA Data Security. TMTO (Time-Memory Trade-Off) Cryptanalysis is a practical method to dramatically shorten the time for key search when plaintext is given in advance. A string of ASCII characters is used as the key much like a password. The ASCII character is 7-bit character and is changed to 96 kinds of value. The 56-bit DES key is given with a string of 8 ASCII characters. Although the DES key has 64 trillion(=256) possibilities, the key that is given with a string has only 6.4 trillion(=968) possibilities. Therefore, we improve TMTO cryptanalysis so that we search only the limited key by ASCII characters and reduce the quantity of computation. In this paper, we demonstrate how TMTO cryptanalysis for limited key is well suited to our FPGA-based RASH machine. By limiting the key to a string, DES key will be found at 80% probability within 45 minutes after ciphertext is given on 10 units of RASH. The precomputation before starting key search takes 3 weeks on the same RASH configuration.

Burst switched WDM optical networks are coming up as suitable network architectures for future Optical Internet backbones. However, the lack of optical processing capabilities results in increased burst blocking probability, which in turn lead to very limited network performance. Efficient contention resolution algorithm is therefore necessary. In this paper, we propose a distributed wavelength assignment algorithm named Priority-based Wavelength Assignment (PWA) for such networks. Each node selectively assigns wavelengths based on the wavelength priority information "learned" from its wavelength utilization history in a distributed manner. As the learning process progresses, nodes in the same part of the network tend to assign different wavelengths to avoid contentions. Simulation results show that the PWA can effectively reduce the blocking probability and increase the performance of burst optical networks compared to previous algorithms such as random assignment.

An optical fiber line testing system is essential for reducing maintenance costs and improving service reliability in optical access networks. NTT has already developed such a system called AURORA (AUtomatic optical fibeR opeRAtions support system). As we already use the 1310 and 1550nm wavelengths for communication, we use the 1650nm wavelength for maintenance testing in accordance with ITU-T recommendation L.41. Recently, a long wavelength band (L-band) that extends to 1625nm has begun to be used for WDM transmission. With a view to monitoring optical fiber cables transmitting L-band communication light, an attractive way of separating the U-band wavelength of the test lights from the L-band wavelength of the communication light is to use a chirped fiber Bragg grating (FBG) filter because of its steep optical spectrum. However, it is difficult to measure fiber characteristics with an optical time-domain reflectometer (OTDR), because multi-reflections appear in the OTDR trace when FBG filters are installed at both ends of an optical fiber line. In this paper, we consider this problem and show that the reflection loss at the port of a test access module (TAM) must be more than 36.6dB. We also describe the system design for an extended optical fiber line testing system using an L/U-band optical coupler, which has two chirped FBGs between two 4-port circulators for L-band WDM transmission. In this system, the reflection loss at a TAM port was 38.1dB, and we confirmed that there was no degradation in the OTDR trace caused by multi-reflections at the optical filters.