There are several kinds of coloring of digraphs, such as vertex-coloring and arc-coloring. We call an arc-coloring of a digraph G the first type if it is an assignment of colors to the arc set of G in which no two consecutive arcs have the same color. In some researches, the arc-coloring of first type has been associated with the minimum number of the vertex-coloring called chromatic number. Considering the class of line digraphs, an arc-coloring of a digraph G of the first type is equivalent to the vertex-coloring of its line digraph L(G). In this paper, we study the arc-coloring of the first type and the vertex-coloring of line digraphs. We give the upper bound of the chromatic number of L(G) by the chromatic number of a digraph G which admits loops. It is also shown that there exists quite a small integer k so that the iterated line digraph Lk(G) is 3-vertex-colorable. As a consequence, we derive the chromatic number of de Bruijn and Kautz digraphs.

A novel interference reduction method, transmit power and window control (TPWC), is proposed to enhance the system capacity in the downlink of code division multiple access (CDMA) cellular packet systems. TPWC measures the propagation conditions and calculates the required instantaneous transmit power between a base station (BS) and a mobile station (MS). Then, TPWC sends packets only during a transmit time-window, in which the packets can be sent with less power than a predetermined threshold. TPWC reduces the average transmit power at the cost of an extra transmission delay at the BS. Computer simulations show that TPWC enhances the system capacity by two-fold in a CDMA cellular packet system when each MS has a loading ratio of 0.5 and an average delay allowance of 5 ms for the unit packet length of 1 ms. Furthermore, this paper proposes a multi-link packet transmission (MLPT) scheme in order to reduce the delay caused by TPWC. When an MS is at the cell edge, packets are distributed by MLPT to multiple BSs, from which packets are sent to the MS; thus, the transmission delay can be reduced by utilizing the transmit windows of each BS.

This paper investigates the gain of inter-Node B macro diversity for a scheduled-based shared channel using single-carrier FDMA radio access in the Evolved UTRA (UMTS Terrestrial Radio Access) uplink based on system-level simulations. More specifically, we clarify the gain of inter-Node B soft handover (SHO) with selection combining at the radio frame length level (=10 msec) compared to that for hard handover (HHO) for a scheduled-based shared data channel, considering the gains of key packet-specific techniques including channel-dependent scheduling, adaptive modulation and coding (AMC), hybrid automatic repeat request (ARQ) with packet combining, and slow transmission power control (TPC). Simulation results show that the inter-Node B SHO increases the user throughput at the cell edge by approximately 10% for a short cell radius such as 100-300 m due to the diversity gain from a sudden change in other-cell interference, which is a feature specific to full scheduled-based packet access. However, it is also shown that the gain of inter-Node B SHO compared to that for HHO is small in a macrocell environment when the cell radius is longer than approximately 500 m due to the gains from hybrid ARQ with packet combining, slow TPC, and proportional fairness based channel-dependent scheduling.

A VLIW (Very Long Instruction Word) architecture with a new code compaction method has been proposed. For a 3D-geometry processor, we consider two types of 2-issue VLIW architectures, the floating-point execution accelerating VLIW (FP-VLIW) and the data-move enhancing VLIW (MV-VLIW) architectures, as expansions of a Single-Streaming Single Instruction, Multiple Data (SS-SIMD) architecture. To solve the code bloat problem which is common to VLIW architectures, the proposed method makes it possible to compact original codes into the VLIW codes by software tools and decompact the VLIW codes by a simple hardware decompactor composed of an instruction swap circuit on a chip. Speeds and code densities of the two VLIWs with the code compaction are compared to the SS-SIMD with the same instruction set and the same building blocks. The FP-VLIW shows the fastest speed performance in the evaluation results of the viewperf CDRS-03 benchmark programs. It is 36% faster than the SS-SIMD used as reference. The proposed compaction method keeps the 95% code density of the SS-SIMD. One test program shows that the code density of the MV-VLIW is higher than that of the SS-SIMD. This result demonstrates that the merit of compacting nops can be greater than the VLIW penalty. The FP-VLIW architecture with the code compaction achieves 1.36 times the speed performance without significant code-density deterioration.

Let f and g be two maps from a set E into a set F such that f(x) g(x) for every x in E. Sahili [8] has shown that, if min {|f-1(z)|,|g-1(z)|}≤ n for each z∈ F, then E can be partitioned into at most 2n+1 sets E1,..., E2n+1 such that f(Ei)∩ g(Ei)= for each i=1,..., 2n+1. He also asked if 2n+1 is the best possible bound. By using Sahili's formulation of the problem in terms of the chromatic number of line digraphs, we improve the upper bound from 2n+1 to O(log n). We also investigate extended version for more than two maps.

This paper proposes likelihood function generation of complexity-reduced Maximum Likelihood Detection with QR Decomposition and M-algorithm (QRM-MLD) suitable for soft-decision Turbo decoding and investigates the throughput performance using QRM-MLD with the proposed likelihood function in multipath Rayleigh fading channels for Orthogonal Frequency and Code Division Multiplexing (OFCDM) multiple-input multiple-output (MIMO) multiplexing. Simulation results show that by using the proposed likelihood function generation scheme for soft-decision Turbo decoding following QRM-MLD in 4-by-4 MIMO multiplexing, the required average received signal energy per bit-to-noise power spectrum density ratio (Eb/N0) at the average block error rate (BLER) of 10-2 at a 1-Gbps data rate is significantly reduced compared to that using hard-decision decoding in OFCDM access with 16 QAM modulation, the coding rate of 8/9, and 8-code multiplexing with a spreading factor of 8 assuming a 100-MHz bandwidth. Furthermore, we show that by employing QRM-MLD associated with soft-decision Turbo decoding for 4-by-4 MIMO multiplexing, the throughput values of 500 Mbps and 1 Gbps are achieved at the average received Eb/N0 of approximately 4.5 and 9.3 dB by QPSK with the coding rate of R = 8/9 and 16QAM with R = 8/9, respectively, for OFCDM access assuming a 100-MHz bandwidth in a twelve-path Rayleigh fading channel.

This paper describes a kind of 3D graphics geometry processor architecture for high performance/cost 3D graphics, its application to a real chip, and the results of performance evaluation. In order to establish the high speed geometry processing, dedicated hardware is introduced for accelerating special operations, such as power calculations, clip tests, and program address generation. The dedicated hardware consists of a modified floating-point multiplier in a four-parallel SIMD processing core, a clip test unit, and an internal program address generation scheme optimized to geometry processing mode. Special instructions corresponding to the dedicated schemes are also defined and added. The parallelism of the SIMD core is adjusted to a geometry data structure. Employing dedicated hardware and software significantly accelerates these complicated operations deriving from geometry algorithms. The collaboration of the hardware design and the software design considerably reduces instruction step counts for complex processing. Two kinds of program are dealt with in the proposed architecture. One is a special case program containing few conditional jump instructions, and the other is a general case program combining many program routines. The proposed program address generation scheme provides the automatic selection of a program optimized to each geometry processing mode. By this program address generation scheme and the program types, the frequency of the conditional jump operations, that usually disturb a pipeline operation, are minimized under practical use. Additionally, the programmable design and this program address generation scheme facilitate the load balancing of the geometry calculations with the CPU. A programmable geometry processor was fabricated by using 0.35 µm CMOS process as an application of this architecture. One point three million transistors are integrated in a 11.84 12.07 mm2 die. The increase of the gate counts for all the dedicated hardware is a total of 24 K gates and is approximately only a 7.4% increase of the total gate count. This chip operates at 150 MHz, and achieves the processing performance of 5.8 M vertex/sec. The result shows that the proposed programmable architecture (ESIMD: Enhanced SIMD) is 2.3 times more cost effective than a programmable geometry LSI reported previously.

This paper presents the best transmit diversity schemes for three types of common/shared control signals from the viewpoint of the block error rate (BLER) performance in the Evolved UTRA downlink employing OFDM radio access. This paper also presents the coverage performance of the common/shared control signals using transmit diversity with respect to the outage probability that satisfies the required BLER performance, which is a major factor determining the cell configuration. Simulation results clarify that Space-Frequency Block Code (SFBC) and the combination of SFBC and Frequency Switched Transmit Diversity (FSTD) are the best transmit diversity schemes among the open-loop type transmit diversity candidates for two-antenna and four-antenna transmission cases, respectively. Furthermore, we show through system-level simulations that SFBC is very effective in reducing the outage probability at the required BLER for the physical broadcast channel (PBCH), for the common control signal with resource block (RB)-level assignment such as the dynamic broadcast channel (D-BCH) and paging channel (PCH), and in increasing the number of accommodated L1/L2 control signals over one transmission time interval duration, using mini-control channel element (CCE)-level assignment.

This paper presents a newly developed architecture for a highly parallel DSP suited for realtime image reaognition. The programmable DSP was designed for a variety of image recognition systems, such as computer vision systems, character recognition systems and others. The DSP consists of functional units suited for image recognition: a SIMD processing core, a hierarchical bus, an Address Generation Unit, Data Memories, a DMA controller, a Link Unit, and a Control Unit. The high performance of 3.2GOPS is realized by the eight-parallel SIMD core with a optimized pipeline structure for image recognition algorithms. The DSP supports flexible data transfers including an extraction of lacal images from raster scanned image data, a table-loop-up, a data-broadcasting, and a data-shifting among processing units in the SIMD core, for effective execution of various image processing algorithms. Hence, the DSP can process a 55 spatial filtering for 512512 images within 13.1 msec. Adopting the DSP to a Japanese character recognition system, the speed of 924 characters/sec can be achieved for feature extractions and feature vectors matchings. The DSP can be integrated in a 14.514.5 mm2 single-chip, using 0.5 µm CMOS technology. In this paper, the key features of the architecture and the new techniques enabling efficient operation of the eight parallel processing units are described. Estimation of the performance of the DSP is also presented.

This paper proposes an adaptive selection algorithm for the surviving symbol replica candidates (ASESS) based on the maximum reliability in maximum likelihood detection with QR decomposition and the M-algorithm (QRM-MLD) for Orthogonal Frequency Division Multiplexing (OFDM) multiple-input multiple-output (MIMO) multiplexing. In the proposed algorithm, symbol replica candidates newly-added at each stage are ranked for each surviving symbol replica from the previous stage using multiple quadrant detection. Then, branch metrics are calculated only for the minimum number of symbol replica candidates with a high level of reliability using an iterative loop based on symbol ranking results. Computer simulation results show that the computational complexity of the QRM-MLD employing the proposed ASESS algorithm is reduced to approximately 1/4 and 1/1200 compared to that of the original QRM-MLD and that of the conventional MLD with squared Euclidian distance calculations for all symbol replica candidates, respectively, assuming the identical achievable average packet error rate (PER) performance in 4-by-4 MIMO multiplexing with 16QAM data modulation. The results also show that 1-Gbps throughput is achieved at the average received signal energy per bit-to-noise power spectrum density ratio (Eb/N0) per receiver antenna of approximately 9 dB using the ASESS algorithm in QRM-MLD associated with 16QAM modulation and Turbo coding with the coding rate of 8/9 assuming a 100-MHz bandwidth for a 12-path Rayleigh fading channel (root mean square (r.m.s.) delay spread of 0.26 µs and maximum Doppler frequency of 20 Hz).

On the reverse (mobile-to-base) link of direct sequence code division multiple access (DS-CDMA) mobile radio, closed-loop fast transmit power control (TPC) must be sufficiently fast to track fast multipath fading. However, in urban areas, the line-of-sight (LOS) path may appear abruptly when a mobile station appears from behind a building and later suddenly the LOS may disappear, resulting in an abrupt path-loss change in the order of 30 to 40 dB. This "on-off" path loss change can be considered as a special case of shadowing. This "on-off" shadowing causes two problems at the base station: generation of severe multiple access interference (MAI) to other users when the LOS path appears and degradation of the quality of its own signal when the LOS path disappears. This paper proposes a new closed-loop fast TPC based on Markov-state transitions (called Markov fast TPC). State transition is determined by the past history of the received binary TPC commands sent from the base station. The TPC step size is associated with each state. By changing the step size between as small as 0.8 dB and as large as 4 dB, the Markov fast TPC can better track "on-off" shadowing as well as multipath fading compared to conventional one-state closed-loop fast TPC. A new SIR estimation method used in TPC command generation is also proposed. The TPC error is evaluated by computer simulation to demonstrate the adaptability of the proposed Markov fast TPC in a Rayleigh fading channel superimposed by "on-off" shadowing.

This paper presents a resilient cache memory for dynamic variation tolerance in a 40-nm CMOS. The cache can perform sustained operations under a large-amplitude voltage droop. To realize sustained operation, the resilient cache exploits 7T/14T bit-enhancing SRAM and on-chip voltage/temperature monitoring circuit. 7T/14T bit-enhancing SRAM can reconfigure itself dynamically to a reliable bit-enhancing mode. The on-chip voltage/temperature monitoring circuit can sense a precise supply voltage level of a power rail of the cache. The proposed cache can dynamically change its operation mode using the voltage/temperature monitoring result and can operate reliably under a large-amplitude voltage droop. Experimental result shows that it does not fail with 25% and 30% droop of Vdd and it provides 91 times better failure rate with a 35% droop of Vdd compared with the conventional design.