An n-dimensional folded hypercube, denoted by FQn, is an enhanced n-dimensional hypercube with one extra link between nodes that have the furthest Hamming distance. Let FFv (respectively, FFe) denote the set of faulty nodes (respectively, faulty links) in FQn. Under the assumption that every fault-free node in FQn is incident to at least two fault-free links, Hsieh et al. (Inform. Process. Lett. 110 (2009) pp.41-53) showed that if |FFv|+|FFe| ≤ 2n-4 for n ≥ 3, then FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv|. In this paper, we show that, under the same conditional fault model, FQn with n ≥ 5 can tolerate more faulty elements and provides the same lower bound of the length of a longest fault-free cycle, i.e., FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv| if |FFv|+|FFe| ≤ 2n-3 for n ≥ 5.

We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino.

In the paper [4], the authors generalized the Cipolla-Lehmer method [2][5] for computing square roots in finite fields to the case of r-th roots with r prime, and compared it with the Adleman-Manders-Miller method [1] from the experimental point of view. In this paper, we compare these two methods from the theoretical point of view.

We study non-malleability of multiple public-key encryption (ME) schemes. The main difference of ME from the threshold public-key encryption schemes is that there is no dealer to share a secret among users; each user can independently choose their own public-keys; and a sender can encrypt a message under ad-hoc multiple public keys of his choice. In this paper we tackle non-malleability of ME. We note that the prior works only consider confidentiality of messages and treat the case that all public keys are chosen by honest users. In the multiple public-key setting, however, some application naturally requires non-malleability of ciphertexts under multiple public keys including malicious users'. Therefore, we study the case and have obtained the following results:·We present three definitions of non-malleability of ME, simulation-based, comparison-based, and indistinguishability-based ones. These definitions can be seen as an analogue of those of non-malleable public-key encryption (PKE) schemes. Interestingly, our definitions are all equivalent even for the “invalid-allowing” relations. We note that the counterparts of PKE are not equivalent for the relations.·The previous strongest security notion for ME, “indistinguishability against strong chosen-ciphertext attacks (sMCCA)” [1], does not imply our notion of non-malleability against chosen-plaintext attacks.·Non-malleability of ME guarantees that the single message indistinguishability-based notion is equivalent to the multiple-message simulation-based notion, which provides designers a fundamental benefit.·We define new, stronger decryption robustness for ME. A non-malleable ME scheme is meaningful in practice if it also has the decryption robustness.·We present a constant ciphertext-size ME scheme (meaning that the length of a ciphertext is independent of the number of public-keys) that is secure in our strongest security notion of non-malleability. Indeed, the ciphertext overhead (i.e., the length of a ciphertext minus that of a plaintext) is the combined length of two group elements plus one hash value, regardless of the number of public keys. Then, the length of the partial decryption of one user consists of only two group elements, regardless of the length of the plaintext.

Majority-logic algorithms are devised for decoding non-binary LDPC codes in order to reduce computational complexity. However, compared with conventional belief propagation algorithms, majority-logic algorithms suffer from severe bit error performance degradation. This paper presents a low-complexity reliability-based algorithm aiming at improving error correcting ability of majority-logic algorithms. Reliability measures for check nodes are novelly introduced to realize mutual update between variable message and check message, and hence more efficient reliability propagation can be achieved, similar to belief-propagation algorithm. Simulation results on NB-LDPC codes with different characteristics demonstrate that our algorithm can reduce the bit error ratio by more than one order of magnitude and the coding gain enhancement over ISRB-MLGD can reach 0.2-2.0dB, compared with both the ISRB-MLGD and IISRB-MLGD algorithms. Moreover, simulations on typical LDPC codes show that the computational complexity of the proposed algorithm is closely equivalent to ISRB-MLGD algorithm, and is less than 10% of Min-max algorithm. As a result, the proposed algorithm achieves a more efficient trade-off between decoding computational complexity and error performance.

We discuss how to recover RSA secret keys from noisy key bits with erasures and errors. There are two known algorithms recovering original secret keys from noisy keys. At Crypto 2009, Heninger and Shacham proposed a method for the case where an erroneous version of secret keys contains only erasures. Subsequently, Henecka et al. proposed a method for an erroneous version containing only errors at Crypto 2010. For physical attacks such as side-channel and cold boot attacks, we need to study key recovery from a noisy secret key containing both erasures and errors. In this paper, we propose a method to recover a secret key from such an erroneous version and analyze the condition for error and erasure rates so that our algorithm succeeds in finding the correct secret key in polynomial time. We also evaluate a theoretical bound to recover the secret key and discuss to what extent our algorithm achieves this bound.

Extremely low voltage operation near or below threshold voltage is a key circuit technology to improve the energy efficiency of information systems and to realize ultra-low power sensor nodes. However, it is difficult to operate conventional analog circuits based on amplifier at low voltage. Furthermore, PVT (Process, Voltage and Temperature) variation and random Vth variation degrade the minimum operation voltage and the energy efficiency in both digital and analog circuits. In this paper, extremely low power analog circuits based on comparator and switched capacitor as well as extremely low power digital circuits are presented. Many kinds of circuit technologies are applied to cope with the variation problem. Finally, image processing SoC that integrates digital and analog circuits is presented, where improvement of total performance by a cooperation of analog circuits and digital circuits is demonstrated.

Yield enhancements and quality improvements must be considered as factors of the utmost importance in VLSI (Very Large Scale Integration circuits) manufacturing in order to reduce cost and ensure customer satisfaction. This paper will present a study of the yield theory, an analysis of actual manufacturing data, and the challenges of yield enhancement.

This paper describes a simple packet combining scheme with maximum likelihood detection (MLD) for multiple-input multiple-output with orthogonal frequency division multiplexing (MIMO-OFDM) in relay channels to construct reliable wireless links in wireless local area networks (LANs). Our MLD-based approach employs the multiplexed sub-stream signals in different transmit slots. The proposed scheme uses an additional combining process before MLD processing. Moreover, the proposed scheme sets the cyclic shift delay (CSD) operation in the relay terminal. We evaluate the performance of the proposed scheme by the packet error rate (PER) and throughput performance in the decode-and-forward (DF) strategy. First, we show that the proposed scheme offers approximately 4.5dB improvement over the conventional scheme in the received power ratio of the relay terminal to the destination terminal at PER =0.1. Second, the proposed scheme achieves about 1.6 times the throughput of the conventional scheme when the received power ratio of the relay terminal to the destination terminal is 3dB.

With the development of global navigation satellite systems (GNSS), the interference among global navigation satellite systems, known as the radio frequency compatibility problem, has become a matter of great concern to system providers and user communities. The acceptable compatibility threshold should be determined in the radio frequency compatibility assessment process. However, there is no common standard for the acceptable threshold in the radio frequency compatibility assessment. This paper firstly introduces the comprehensive radio frequency compatibility methodology combining the spectral separation coefficient (SSC) and code tracking spectral sensitivity coefficient (CT_SSC). Then, a method for determination of the acceptable compatibility threshold is proposed. The proposed method considers the receiver processing phase including acquisition, code and carrier tracking and data demodulation. Simulations accounting for the interference effects are carried out at each time step and every place on earth. The simulations mainly consider the signals of GPS, Galileo and BeiDou Navigation Satellite System (BDS) in the L1 band. Results show that all of the sole systems are compatible with other GNSS systems with respect to a special receiver configuration used in the simulations.

Computational fluid dynamics (CFD) is an important tool for designing aircraft components. FaSTAR (Fast Aerodynamics Routines) is one of the most recent CFD packages and has various subroutines. However, its irregular and complicated data structure makes it difficult to execute FaSTAR on parallel machines due to memory access problem. The use of a reconfigurable platform based on field programmable gate arrays (FPGAs) is a promising approach to accelerating memory-bottlenecked applications like FaSTAR. However, even with hardware execution, a large number of pipeline stalls can occur due to read-after-write (RAW) data hazards. Moreover, it is difficult to predict when such stalls will occur because of the unstructured mesh used in FaSTAR. To eliminate this problem, we developed an out-of-order mechanism for permuting the data order so as to prevent RAW hazards. It uses an execution monitor and a wait buffer. The former identifies the state of the computation units, and the latter temporarily stores data to be processed in the computation units. This out-of-order mechanism can be applied to various types of computations with data dependency by changing the number of execution monitors and wait buffers in accordance with the equations used in the target computation. An out-of-order system can be reconfigured by automatic changing of the parameters. Application of the proposed mechanism to five subroutines in FaSTAR showed that its use reduces the number of stalls to less than 1% compared to without the mechanism. In-order execution was speeded up 2.6-fold and software execution was speeded up 2.9-fold using an Intel Core 2 Duo processor with a reasonable amount of overhead.

The large Doppler offset that exists in high dynamic environments poses a serious impediment to the acquisition of direct sequence spread spectrum (DSSS) signals. To ensure acceptable detection probabilities, the frequency space has to be finely divided, which leads to complicated acquisition structures and excessively long acquisition time at low SNR. A local frequency folding (LFF) method designed for combined application with established techniques dedicated to PN-code synchronization is proposed in this paper. Through modulating local PN-code block with a fixed waveform obtained by folding all frequency cells together, we eliminate the need for frequency search and ease the workload of acquisition. We also analyze the performance of LFF and find that the detection performance degradation from folding can be compensated by FFT-based coherent integration. The study is complemented with numerical simulations showing that the proposed method has advantages over unfolding methods with respect to detection probability and mean acquisition time, and the advantage becomes obvious but limited if the folded number gets larger.

Excimer laser annealing at 308nm in UV and semiconductor blue laser-diode annealing at 445nm were performed and compared in term of the crystallization depending on electrical properties of Si films. As a result for the thin Si films of 50nm thickness, both lasers are very effective to enlarge the grain size and to activate electrically the dopant atoms in the CVD Si film. Smooth Si surface can be obtained using blue-laser annealing of scanned CW mode. By improving the film quality of amorphous Si deposited by sputtering for subsequent crystallization, both laser annealing techniques are effective for LTPS applications not only on conventional glass but also on flexible sheet. By conducting the latter advanced annealing technique, small grain size as well as large grains can be controlled. As blue laser is effective to crystallize even rather thicker Si films of 1µm, high performance thin-film photo-sensor or photo-voltaic applications are also expected.

We determine the linear complexity of binary sequences derived from the polynomial quotient modulo p defined by $F(u)equiv rac{f(u)-f_p(u)}{p} ~(mod~ p), qquad 0 le F(u) le p-1,~uge 0,$ where fp(u)≡f(u) (mod p), for general polynomials $f(x)in mathbb{Z}[x]$. The linear complexity equals to one of the following values {p2-p,p2-p+1,p2-1,p2} if 2 is a primitive root modulo p2, depending on p≡1 or 3 modulo 4 and the number of solutions of f'(u)≡0 (mod) p, where f'(x) is the derivative of f(x). Furthermore, we extend the constructions to d-ary sequences for prime d|(p-1) and d being a primitive root modulo p2.

In this letter, we present a new scheme to find small fundamental instantons (SFIs) of regular low-density parity-check (LDPC) codes for the linear programming (LP) decoding over the binary symmetric channel (BSC). Based on the fact that each instanton-induced graph (IIG) contains at least one short cycle, we determine potential instantons by constructing possible IIGs which contain short cycles and additional paths connected to the cycles. Then we identify actual instantons from potential ones under the LP decoding. Simulation results on some typical LDPC codes show that our scheme is effective, and more instantons can be obtained by the proposed scheme when compared with the existing instanton search method.

This paper proposes a novel and an efficient method termed hypersphere sampling to estimate the circuit yield of low-failure probability with a large number of variable sources. Importance sampling using a mean-shift Gaussian mixture distribution as an alternative distribution is used for yield estimation. Further, the proposed method is used to determine the shift locations of the Gaussian distributions. This method involves the bisection of cones whose bases are part of the hyperspheres, in order to locate probabilistically important regions of failure; the determination of these regions accelerates the convergence speed of importance sampling. Clustering of the failure samples determines the required number of Gaussian distributions. Successful static random access memory (SRAM) yield estimations of 6- to 24-dimensional problems are presented. The number of Monte Carlo trials has been reduced by 2-5 orders of magnitude as compared to conventional Monte Carlo simulation methods.

k-NN classification has been applied to classify normal tissues in MR images. However, the intensity inhomogeneity of MR images forces conventional k-NN classification into significant misclassification errors. This letter proposes a new interleaved method, which combines k-NN classification and bias field estimation in an energy minimization framework, to simultaneously overcome the limitation of misclassifications in conventional k-NN classification and correct the bias field of observed images. Experiments demonstrate the effectiveness and advantages of the proposed algorithm.

In this paper, we propose a message passing decoding algorithm which lowers decoding error rates in the error floor regions for non-binary low-density parity-check (LDPC) codes transmitted over the binary erasure channel (BEC) and the memoryless binary-input output-symmetric (MBIOS) channels. In the case for the BEC, this decoding algorithm is a combination with belief propagation (BP) decoding and maximum a posteriori (MAP) decoding on zigzag cycles, which cause decoding errors in the error floor region. We show that MAP decoding on the zigzag cycles is realized by means of a message passing algorithm. Moreover, we extend this decoding algorithm to the MBIOS channels. Simulation results demonstrate that the decoding error rates in the error floor regions by the proposed decoding algorithm are lower than those by the BP decoder.

A promising application of a single-flux quantum (SFQ) circuit is read-out circuitry for a multi-channel superconductive sensor array. In such applications, the SFQ read-out circuit is expected to operate outside a magnetic shield. We investigated an SFQ circuit structure, which is tolerant to an external magnetic field, using the AIST 2.5kA/cm2 Nb standard 2 process, which has four Nb wiring layers including the ground plane. By covering the entire circuit using an upper Nb wiring layer called the control (CTL) layer, the influences of the external magnetic field on the SFQ circuit operation can be avoided. We experimentally evaluated the sheet inductance of the wiring layer underneath the CTL shielding layer to design a magnetic-field-tolerant SFQ circuit. We implemented and measured test circuits comprising toggle flip-flops (TFFs) to evaluate their magnetic field tolerances. The operating margin and maximum operating frequency of the designed TFF did not deteriorate with increases in the magnetic field applied to the test circuit, whereas the operating margin of the conventional TFF was reduced by applying the magnetic field. We have also demonstrated the high-speed operation of the designed TFF operated in an unshielded environment at a frequency of up to 120GHz with a wide operating margin.

This paper proposes an adaptive marker coding (AMC) for correction of insertion/deletion/substitution errors. Unlike the conventional marker codings which select marker-bit values deterministically, the AMC adaptively reverses the first and last bits of each marker as well as bits surrounding the marker. Decoding is based on a forward-backward algorithm which takes into account the dependency of bit-values around the marker. Evaluation shows that, for a channel with insertion/deletion error probability 1.8×10-2, the decoded BER of existing marker coding of rate 9/16 is 4.25×10-3, while that of the proposed coding with the same code rate is 1.73×10-3.