Tongxin YANG Tomoaki UKEZONO Toshinori SATO
Multiplication is a key fundamental function for many error-tolerant applications. Approximate multiplication is considered to be an efficient technique for trading off energy against performance and accuracy. This paper proposes an accuracy-controllable multiplier whose final product is generated by a carry-maskable adder. The proposed scheme can dynamically select the length of the carry propagation to satisfy the accuracy requirements flexibly. The partial product tree of the multiplier is approximated by the proposed tree compressor. An 8×8 multiplier design is implemented by employing the carry-maskable adder and the compressor. Compared with a conventional Wallace tree multiplier, the proposed multiplier reduced power consumption by between 47.3% and 56.2% and critical path delay by between 29.9% and 60.5%, depending on the required accuracy. Its silicon area was also 44.6% smaller. In addition, results from two image processing applications demonstrate that the quality of the processed images can be controlled by the proposed multiplier design.
Tomoki SUGIURA Jaehoon YU Yoshinori TAKEUCHI
A phase locking value (PLV) in electrocorticography is an essential indicator for analysis of cognitive activities and detection of severe diseases such as seizure of epilepsy. The PLV computation requires a simultaneous pursuit of high-throughput and low-cost implementation in hardware acceleration. The PLV computation consists of bandpass filtering, Hilbert transform, and mean phase coherence (MPC) calculation. The MPC calculation includes trigonometric functions and divisions, and these calculations require a lot of computational amounts. This paper proposes an MPC calculation method that removes high-cost operations from the original MPC with mathematically identical derivations while the conventional methods sacrifice either computational accuracy or throughput. This paper also proposes a hardware implementation of MPC calculator whose latency is 21 cycles and pipeline interval is five cycles. Compared with the conventional implementation with the same standard cell library, the proposed implementation marks 2.8 times better hardware implementation efficiency that is defined as throughput per gate counts.
Masayuki ARAI Shingo INUYAMA Kazuhiko IWASAKI
As semiconductor device manufacturing technology evolves toward higher integration and reduced feature size, the gap between the defect level estimated at the design stage and that reported for fabricated devices has become wider, making it more difficult to control total manufacturing cost including test cost and cost for field failure. To estimate fault coverage more precisely considering occurrence probabilities of faults, we have proposed weighted fault coverage estimation based on critical area corresponding to each fault. Previously different fault models were handled separately; thus, pattern compression efficiency and runtime were not optimized. In this study, we propose a fast test pattern generation scheme that considers weighted bridge and open fault coverage in an integrated manner. The proposed scheme applies two-step test pattern generation, wherein test patterns generated at second step that target only bridge faults are reordered with a search window of fixed size, achieving O(n) computational complexity. Experimental results indicate that with 10% of the initial target fault size and a fixed, small window size, the proposed scheme achieves approximately 100 times runtime reduction when compared to simple greedy-based reordering, in exchange for about 5% pattern count increment.
Shotaro SUGIYAMA Hiromitsu AWANO Makoto IKEDA
A 256-bit $mathbb{F}_p$ ECDSA crypto processor featuring low latency, low energy consumption and capability of changing the Elliptic curve parameters is designed and fabricated in SOTB 65nm CMOS process. We have demonstrated the lowest ever reported signature generation time of 31.3 μs at 238MHz clock frequency. Energy consumption is 3.28 μJ/signature-generation, which is same as the lowest reported till date. We have also derived addition formulae on Elliptic curve useful for reduce the number of registers and operation cycles.
Yusuke INOUE Takatsugu ONO Koji INOUE
On-line object tracking (OLOT) has been a core technology in computer vision, and its importance has been increasing rapidly. Because this technology is utilized for battery-operated products, energy consumption must be minimized. This paper describes a method of adaptive frame-rate optimization to satisfy that requirement. An energy trade-off occurs between image capturing and object tracking. Therefore, the method optimizes the frame-rate based on always changed object speed for minimizing the total energy while taking into account the trade-off. Simulation results show a maximum energy reduction of 50.0%, and an average reduction of 35.9% without serious tracking accuracy degradation.
Masaru OYA Masao YANAGISAWA Nozomu TOGAWA
Modern digital integrated circuits (ICs) are often designed and fabricated by third parties and tools, which can make IC design/fabrication vulnerable to malicious modifications. The malicious circuits are generally referred to as hardware Trojans (HTs) and they are considered to be a serious security concern. In this paper, we propose a logic-testing based HT detection and classification method utilizing steady state learning. We first observe that HTs are hidden while applying random test patterns in a short time but most of them can be activated in a very long-term random circuit operation. Hence it is very natural that we learn steady signal-transition states of every suspicious Trojan net in a netlist by performing short-term random simulation. After that, we simulate or emulate the netlist in a very long time by giving random test patterns and obtain a set of signal-transition states. By discovering correlation between them, our method detects HTs and finds out its behavior. HTs sometimes do not affect primary outputs but just leak information over side channels. Our method can be successfully applied to those types of HTs. Experimental results demonstrate that our method can successfully identify all the real Trojan nets to be Trojan nets and all the normal nets to be normal nets, while other existing logic-testing HT detection methods cannot detect some of them. Moreover, our method can successfully detect HTs even if they are not really activated during long-term random simulation. Our method also correctly guesses the HT behavior utilizing signal transition learning.
Takafumi HAYASHI Takao MAEDA Anh T. PHAM Shinya MATSUFUJI
The present paper introduces a novel type of structured ternary sequences having a zero-correlation zone (zcz) for both periodic and aperiodic correlation functions. The cross-correlation function and the side lobe of the auto-correlation function of the proposed sequence set are zero for phase shifts within the zcz. The proposed zcz sequence set can be generated from an arbitrary pair of an Hadamard matrix of order lh and a binary/ternary perfect sequence of length lp. The sequence set of order 0 is identical to the r-th row of the Hadamard matrix. For m ≥ 0, the sequence set of order (m+1) is constructed from the sequence set of order m by sequence concatenation and interleaving. The sequence set has lp subsets of size 2lh. The periodic correlation function and the aperiodic correlation function of the proposed sequence set have a zcz from -(2m+1-1) to 2m+1-1. The periodic correlation function and the aperiodic correlation function of the sequences of the i-th subset and k-th subset have a zcz from -2m+2-(lh+1)((j-k) mod lp) to -2m+2-(lh+1)((j-k) mod lp). The proposed sequence is suitable for a heterogeneous wireless network, which is one of the candidates for the fifth-generation mobile networks.
Tsukasa YOSHIDA Kazuho WATANABE
Lasso regression based on the L1 regularization is one of the most popular sparse estimation methods. It is often required to set appropriately in advance the regularization parameter that determines the degree of regularization. Although the empirical Bayes approach provides an effective method to estimate the regularization parameter, its solution has yet to be fully investigated in the lasso regression model. In this study, we analyze the empirical Bayes estimator of the one-parameter model of lasso regression and show its uniqueness and its properties. Furthermore, we compare this estimator with that of the variational approximation, and its accuracy is evaluated.
In this study, spatially coupled low-density parity-check (SC-LDPC) codes on the two-dimensional array erasure (2DAE) channel are devised, including a method for generating new SC-LDPC codes with a restriction on the check node constraint. A density evolution analysis confirms the improvement in the threshold of the proposed two-dimensional SC-LDPC code ensembles over the one-dimensional SC-LDPC code ensembles. We show that the BP threshold of the proposed codes can approach the corresponding maximum a posteriori (MAP) threshold of the original residual graph on the 2DAE channel. Moreover, we show that the rates of the residual graph of the two-dimensional LDPC block code ensemble are smaller than those of the one-dimensional LDPC block code ensemble. In other words, a high performance can be obtained by choosing the two-dimensional SC-LDPC codes.
Performance of network coded cooperation over the Gaussian channel in which multiple communication nodes send each one's message to a common destination is analyzed. The nodes first broadcast the message, and subsequently relay the XOR of subset of decoded messages to the destination. The received vector at the destination can be equivalently regarded as the output of a point-to-point channel, except that the underlying codes are drawn probabilistically and symbol errors may occur before transmission of a codeword. We analyze the error performance of this system from coding theoretic viewpoint.
Locally repairable codes, which can repair erased symbols from other symbols, have attracted a good deal of attention in recent years because its local repair property is effective on distributed storage systems. (ru, δu)u∈[s]-locally repairable codes with multiple localities, which are an extension of ordinary locally repairable codes, can repair δu-1 erased symbols simultaneously from a set consisting of at most ru symbols. An upper bound on the minimum distance of these codes and a construction method of optimal codes, attaining this bound with equality, were given by Chen, Hao, and Xia. In this paper, we discuss the parameter restrictions of the existing construction, and we propose explicit constructions of optimal codes with multiple localities with relaxed restrictions based on the encoding polynomial introduced by Tamo and Barg. The proposed construction can design a code whose minimum distance is unrealizable by the existing construction.
Ryo SHIBATA Gou HOSOYA Hiroyuki YASHIMA
Racetrack memory (RM) has attracted much attention. In RM, insertion and deletion (ID) errors occur as a result of an unstable reading process and are called position errors. In this paper, we first define a probabilistic channel model of ID errors in RM with multiple read-heads (RHs). Then, we propose a joint iterative decoding algorithm for spatially coupled low-density parity-check (SC-LDPC) codes over such a channel. We investigate the asymptotic behaviors of SC-LDPC codes under the proposed decoding algorithm using density evolution (DE). With DE, we reveal the relationship between the number of RHs and achievable information rates, along with the iterative decoding thresholds. The results show that increasing the number of RHs provides higher decoding performances, although the proposed decoding algorithm requires each codeword bit to be read only once regardless of the number of RHs. Moreover, we show the performance improvement produced by adjusting the order of the SC-LDPC codeword bits in RM.
Manabu KOBAYASHI Toshiyasu MATSUSHIMA Shigeichi HIRASAWA
F.P. Preparata et al. have proposed a fault diagnosis model to find all faulty units in the multicomputer system by using outcomes which each unit tests some other units. In this paper, for probabilistic diagnosis models, we show an efficient diagnosis algorithm to obtain a posteriori probability that each of units is faulty given the test outcomes. Furthermore, we propose a method to analyze the diagnostic error probability of this algorithm.
Tetsunao MATSUTA Tomohiko UYEMATSU
In the successive refinement problem, a fixed-length sequence emitted from an information source is encoded into two codewords by two encoders in order to give two reconstructions of the sequence. One of two reconstructions is obtained by one of two codewords, and the other reconstruction is obtained by all two codewords. For this coding problem, we give non-asymptotic inner and outer bounds on pairs of numbers of codewords of two encoders such that each probability that a distortion exceeds a given distortion level is less than a given probability level. We also give a general formula for the rate-distortion region for general sources, where the rate-distortion region is the set of rate pairs of two encoders such that each maximum value of possible distortions is less than a given distortion level.
Akira YAMAWAKI Hiroshi KAMABE Shan LU
In multilevel flash memory, in general, multiple read thresholds are required to read a single logical page. Random I/O (RIO) code, introduced by Sharon and Alrod, is a coding scheme that enables the reading of one logical page using a single read threshold. It was shown that the construction of RIO codes is equivalent to the construction of write-once memory (WOM) codes. Yaakobi and Motwani proposed a family of RIO codes, called parallel RIO (P-RIO) code, in which all logical pages are encoded in parallel. In this paper, we utilize coset coding with Hamming codes in order to construct P-RIO codes. Coset coding is a technique to construct WOM codes using linear binary codes. We leverage information on the data of all pages to encode each page. Our P-RIO codes, using which more pages can be stored than RIO codes constructed via coset coding, have parameters for which RIO codes do not exist.
Yuta NAKAHARA Toshiyasu MATSUSHIMA
Spatially “Mt. Fuji” coupled (SFC) low density parity check (LDPC) codes are constructed as a chain of block LDPC codes. A difference between the SFC-LDPC codes and the original spatially coupled (SC) LDPC codes is code lengths of the underlying block LDPC codes. The code length of the block LDPC code at the middle of the chain is larger than that at the end of the chain. It is experimentally confirmed that the bit error probability in the error floor region of the SFC-LDPC code is lower than that of the SC-LDPC code whose code length and design rate are the same as those of the SFC-LDPC code. In this letter, we calculate the weight distribution of the SFC-LDPC code and try to explain causes of the low bit error rates of the SFC-LDPC code.
In 1973, Arimoto proved the strong converse theorem for the discrete memoryless channels stating that when transmission rate R is above channel capacity C, the error probability of decoding goes to one as the block length n of code word tends to infinity. He proved the theorem by deriving the exponent function of error probability of correct decoding that is positive if and only if R > C. Subsequently, in 1979, Dueck and Körner determined the optimal exponent of correct decoding. Recently the author determined the optimal exponent on the correct probability of decoding have the form similar to that of Dueck and Körner determined. In this paper we give a rigorous proof of the equivalence of the above exponet function of Dueck and Körner to a exponent function which can be regarded as an extention of Arimoto's bound to the case with the cost constraint on the channel input.
Let X, Y be two correlated discrete random variables. We consider an estimation of X from encoded data φ(Y) of Y by some encoder function φ(Y). We derive an inequality describing a relation of the correct probability of estimation and the mutual information between X and φ(Y). This inequality may be useful for the secure analysis of crypto system when we use the success probability of estimating secret data as a security criterion. It also provides an intuitive meaning of the secrecy exponent in the strong secrecy criterion.
Long LING Xianhua NIU Bosen ZENG Xing LIU
The construction of frequency hopping sequences with good Hamming correlation is the foundation of research in frequency hopping communication. In this letter, classes of optimal low hit zone frequency hopping sequence set are constructed based on the interleaving technology. The results of the study show that the sequence set with large family size is optimal for the Peng-Fan-Lee bound. And all the sequences in the set are inequivalent.
Shinichi NISHIZAWA Hidetoshi ONODERA
This paper describes a design methodology for process variation aware D-Flip-Flop (DFF) using regression analysis. We propose to use a regression analysis to model the worst-case delay characteristics of a DFF under process variation. We utilize the regression equation for transistor width tuning of the DFF to improve its worst-case delay performance. Regression analysis can not only identify the performance-critical transistors inside the DFF, but also shows these impacts on DFF delay performance in quantitative form. Proposed design methodology is verified using Monte-Carlo simulation. The result shows the proposed method achieves to design a DFF which has similar or better delay characteristics in comparison with the DFF designed by an experienced cell designer.