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.

Cowen gave a universal compact routing algorithm with a stretch factor of three and table-size of O(n2/3log4/3n) based on a simple and practical model. (The table-size is later improved to O(n1/2log3/2n).) This paper considers, using the same model, how the necessary table-size differs if the stretch factor must be less than three. It is shown that: (i) There is a routing algorithm with a stretch factor of two whose table-size is (n -+ 2)log n. (ii) There is a network for which any routing algorithm that follows the model and with a stretch factor of less than three needs a table-size of (n - 2)log n in at least one node. Thus, we can only reduce roughly an additive log n (i.e., table-entries) from the trivial table-size of n log n which obviously enables shortest-path routing. Furthermore it turns out that we can reduce only an additive log n (i.e., only one table-entry) from the trivial n log n if we have to achieve a stretch factor of less than two. Thus the algorithm (i) is (roughly) tight both in its stretch factor and in its table-size.

In this letter we first introduce a new generalized cyclotomic sequence of order four with respect to pq, then we calculate the linear complexity and minimal polynomial of this sequence. Our results show that the new binary sequence is quite good from the linear complexity viewpoint.

The complete subtree (CS) method is one of the most well-known broadcast encryptions which do not enforce the receivers to keep "online." This paper is to reduce the size of secret information which must be stored in a terminal of the method. In the original CS method, the size of the secret information increases as the number of terminals increases. It is shown in this paper that, by making use of a one-way trapdoor permutation, we can make the size constant regardless of the number of terminals. The security of the proposed scheme is investigated, and detailed comparison with other similar schemes is presented. The proposed scheme is suitable for practical implementations of the CS method.

A low-complexity step-by-step decoding algorithm for t-error-correcting binary Bose-Chaudhuri-Hocquenghem (BCH) codes is proposed. Using logical analysis, we obtained a simple rule which can directly determine whether a bit in the received word is correct. The computational complexity of this decoder is less than the conventional step-by-step decoding algorithm, since it reduces at least half of the matrix computations and the most complex element in the conventional step-by-step decoder is the "matrix-computing" element.

We discuss a typical profile of the k-error linear complexity for balanced binary exponent periodic sequences and the number of periodic distinct sequences by their profiles. A numerical example with period 16 is also shown.

This paper presents an efficient scaling-simulation algorithm that simulates operations of the reconfigurable mesh (RM) of size n n using the mesh with multiple partitioned buses (MMPB) of size m m (m < n). The RM and the MMPB are the two-dimensional mesh-connected computers equipped with broadcasting buses. The broadcasting buses of the RM can be used to dynamically obtain various interconnection patterns among the processors during the execution of programs, while those of the MMPB are placed only to every row and column and are statically partitioned in advance by a fixed length. We show that the RM of size n n can be simulated in steps by the MMPB of size m m (m < n), where L is the number of broadcasting buses in each row/column of the simulating MMPB. Although the time-complexity of our algorithm is less efficient than that of the fastest RM scaling-simulation algorithm, the simulating model of our algorithm is the MMPB model where the bus-reconfiguration is not allowed.

This paper presents a design procedure of a directional coupler consisting of a twofold symmetric four-port circuit with four identical matching networks at each port. The intrinsic power-split ratio and the equivalent admittance of the directional coupler are formularized in terms of the eigenadmittances of the original four-port without the matching networks. These formulas are useful for judgment on the realizability of a directional coupler in a given circuit structure and for design of the matching networks. Actually, the present procedure is applied to designing various quadrature hybrids and directional couplers, and its practical usefulness as well as several new circuit structures are demonstrated.

Adaptive routing algorithms, which dynamically select the route of a packet, have been widely studied for interconnection networks in massively parallel computers. An output selection function (OSF), which decides the output channel when some legal channels are free, is essential for an adaptive routing. In this paper, we propose a simple and efficient OSF called minimal multiplexed and least-recently-used (MMLRU). The MMLRU selection function has the following simple strategies for distributing the traffic: 1) each router locally grasps the congestion information by the utilization ratio of its own physical channels; 2) it is divided into the two selection steps, the choice from available physical channels and the choice from available virtual channels. The MMLRU selection function can be used on any type of network topology and adaptive routing algorithm. Simulation results show that the MMLRU selection function improves throughput and latency especially when the number of dimension becomes larger or the number of nodes per dimension become larger.

It is known that the original Grover Search (GS) can be modified to use a general value for the phase θ of the diffusion transform. Then, if the number of answers is relatively large, this modified GS can find one of the answers with probability one in a single iteration. However, such a quick and error-free GS can only be possible if we can initially adjust the value of θ correctly against the number of answers, and this seems very hard in usual occasions. A natural question now arises: Can we enjoy a merit even if GS is used without such an adjustment? In this paper, we give a positive answer using the balls-and-bins game in which the random sampling of bins is replaced by the quantum sampling, i.e., a single round of modified GS. It is shown that by using the quantum sampling: (i) The maximum load can be improved quadratically for the static model of the game and this improvement is optimal. (ii) That is also improved to O(1) for the continuous model if we have a certain knowledge about the total number of balls in the bins after the system becomes stable.

To investigate cyber-criminals, Police sometimes asks Administrator of a computer system to disclose the whole transaction log. Administrator, however, wants to protect the privacy of innocent users. This paper presents a solution for the disclosure/privacy problem of transaction log. In this scheme, Police can search over the encrypted records of the transaction log by keywords. The administrator discloses only the records which include the keyword, but nothing more. Police can verify that the administrator faithfully disclosed all the records which include the keyword.

In this paper, we propose an efficient protocol for proving the correctness of shuffling and an efficient protocol for simultaneously proving the correctness of both shuffling and decryption. The former protocol is the most efficient in computational and communication complexity among 3-move honest verifier perfect zero-knowledge protocols for proving a shuffling of ElGamal cipher-texts. The latter protocol is the most efficient in computational, communication, and round complexity, as a whole, in proving the correctness of both shuffling and decryption of ElGamal cipher-texts. The proposed protocols will be a building block of an efficient, universally verifiable mix-net, whose application to voting systems is prominent.

Test compression / decompression is an efficient method for reducing the test application cost. In this letter we propose a response compression method based on Huffman coding. The proposed method guarantees zero-aliasing and it is independent of the fault model and the structure of a circuit-under-test. Experimental results of the compression ratio and the size of the encoder for the proposed method are presented.

This paper deals with broadcast encryption schemes, in which a sender can send information securely to a group of receivers excluding some receivers over a broadcast channel. In this paper we propose modifications of the Complete Subtree (CS), the Subset Difference (SD) and the Layered Subset Difference (LSD) methods based on the Master Key Tree (MKT). Our modifications eliminate log N keys or labels from receivers' storage, in exchange for an increase in the computational overhead, where N is the total number of receivers. We also propose modifications of the SD and LSD methods by applying the Trapdoor One-way Permutation Tree (TOPT) which is originally proposed in order to modify the CS method. Our modifications based on TOPT also eliminate log N labels, and the computational cost is much smaller than MKT based methods.

We propose a practical blind channel identification algorithm based on the principal component analysis. The algorithm estimates (1) the channel order, (2) the noise variance, and then identifies (3) the channel impulse response, from the autocorrelation of the channel output signal without using the eigenvalue and singular-value decomposition. The special features of the proposed algorithm are (1) practical method to find the channel order and (2) reduction of computational complexity. Numerical examples show the effectiveness of the proposed algorithm.

This paper proposes a Real-Time Compression Architecture (RTCA), which maximizes the efficiency of web services, while reducing the response time at the same time. The developed architecture not only guarantees the freshness of compressed contents but also minimizes the time needed to compress the message, especially when the traffic is heavy.

Test data volume and power consumption for scan-based designs are two major concerns in system-on-a-chip testing. However, test set compaction by filling the don't-cares will invariably increase the scan-in power dissipation for scan testing, then the goals of test data reduction and low-power scan testing appear to be conflicted. Therefore, in this paper we present a selective scan chain reconfiguration method for test data compression and scan-in power reduction. The proposed method analyzes the compatibility of the internal scan cells for a given test set and then divides the scan cells into compatible classes. After the scan chain reconfiguration a dictionary is built to indicate the run-length of each compatible class and only the scan-in data for each class should be transferred from the ATE to the CUT so as to reduce test data volume. Experimental results for the larger ISCAS'89 benchmarks show that the proposed approach overcomes the limitations of traditional run-length coding techniques, and leads to highly reduced test data volume with significant power savings during scan testing in all cases.

This paper presents a VLSI design methodology for the MAC-level DWT/IDWT processor based on a novel limited-resource scheduling algorithm. The r-split Fully-specified Signal Flow Graph (FSFG) of limited-resource FIR filtering has been developed for the scheduling of the MAC-level DWT/IDWT signal processing. Given a set of architecture constraints and DWT parameters, the scheduling algorithm can generate four scheduling matrices that drive the data path to perform the DWT computation. Because the memory for the inter-octave is considered with the register of FIR filter, the memory size is less than the traditional architecture. Besides, based on the limited-resource scheduling algorithm, an automated DWT processor synthesizer has been developed and generates constrained DWT processors in the form of silicon intelligent property (SIP). The DWT SIP can be embedded into a SOC or mapped to program codes for commercial off-the-shelf (COTS) DSP processors with programmable devices. As a result, it has been successfully proven that a variety of DWT SIPs can be efficiently realized by tuning the parameters and applied for signal processing applications.

This study proposes an edge-based single-resolution compression scheme for triangular mesh connectivity. The proposed method improves upon EdgeBreaker. Nearly all of these algorithms are either multiple traversals or operate in reverse order. Operating in reverse order should work only off-line in the EdgeBreaker decompression process. Many restrictions on applications will be caused by these factors. To overcome these restrictions, the algorithm developed here can both encode and decode 3D models in a straightforward manner by single traversal in sequential order. Most algorithms require complicated operations when the triangular mesh is split. This study investigates spatial locality to minimize costs in split operations. Meanwhile, some simplification rules are proposed by considering geometric characteristics which ignore the last triangle when a split occurs. The proposed method improves not only the compression ratio but also the execution time.

In this paper, we present a test data compression technique to reduce test data volume for multiscan-based designs. In our method the internal scan chains are divided into equal sized groups and two dictionaries were build to encode either an entire slice or a subset of the slice. Depending on the codeword, the decompressor may load all scan chains or may load only a group of the scan chains, which can enhance the effectiveness of dictionary-based compression. In contrast to previous dictionary coding techniques, even for the CUT with a large number of scan chains, the proposed approach can achieve satisfied reduction in test data volume with a reasonable smaller dictionary. Experimental results showed the proposed test scheme works particularly well for the large ISCAS'89 benchmarks.