Naoko KIFUNE Hironori UCHIKAWA
At a flash memory, each stored data frame is protected by error correction codes (ECC) such as Bose-Chaudhuri-Hocquenghem (BCH) codes from random errors. Exclusive-OR (XOR) based erasure codes like RAID-5 have also been employed at the flash memory to protect from memory block defects. Conventionally, the ECC and erasure codes are used separately since their target errors are different. Due to recent aggressive technology scaling, additional error correction capability for random errors is required without adding redundancy. We propose an algorithm to improve error correction capability by using XOR parity with a simple counter that counts the number of unreliable bits in the XOR stripe. We also propose to apply Chase decoding to the proposed algorithm. The counter makes it possible to reduce the false correction and execute the efficient Chase decoding. We show that combining the proposed algorithm with Chase decoding can significantly improve the decoding performance.
Yubo LI Kangquan LI Longjiang QU Chao LI
MDS transformation plays an important role in resisting against differential cryptanalysis (DC) and linear cryptanalysis (LC). Recently, M. Sajadieh, et al.[15] designed an efficient recursive diffusion layer with Feistel-like structures. Moreover, they obtained an MDS transformation which is related to a linear function and the inverse is as lightweight as itself. Based on this work, we consider one specific form of linear functions to get the diffusion layer with low XOR gates for the hardware implementation by using temporary registers. We give two criteria to reduce the construction space and obtain six new classes of lightweight MDS transformations. Some of our constructions with one bundle-based LFSRs have as low XOR gates as previous best known results. We expect that these results may supply more choices for the design of MDS transformations in the (lightweight) block cipher algorithm.
Takashi WATANABE Yuta KARASAWA
The cycling wheelchair “Profhand” was developed in Japan as locomotion and lower limb rehabilitation device for hemiplegic subjects and elderly persons. Functional electrical stimulation (FES) control of paralyzed lower limbs enables application of the Profhand to paraplegic subjects as a rehabilitation device. In this paper, simplified muscle stimulation control for FES cycling with Profhand was examined for practical application, because cycling speed was low and not stable in our preliminary study and there was a difficulty in setting stimulation electrodes for the gluteus maximus. First, a guideline of target cycling speed to be achieved by FES cycling was determined from voluntary cycling with healthy subjects in order to evaluate FES cycling control. The cycling speed of 0.6m/s was determined as acceptable value and 1.0m/s was as ideal one. Then, stimulation to the gluteus maximus and that to the dorsiflexor muscles in addition to the quadriceps femoris were examined for simple FES cycling control for Profhand with healthy subjects. Stimulation timing was adjusted automatically during cycling based on muscle response time to electrical stimulation and cycling speed, which was shown to be effective for FES cycling control. Simple FES cycling control with Profhand removing stimulation to the gluteus maximus was found to be feasible. Stimulation to the dorsiflexor muscles with the quadriceps femoris was suggested to be effective for practical, simple FES cycling with Profhand in case of removing the gluteus maximus stimulation.
Mitsuru SHIOZAKI Kousuke OGAWA Kota FURUHASHI Takahiko MURAYAMA Masaya YOSHIKAWA Takeshi FUJINO
In modern hardware security applications, silicon physical unclonable functions (PUFs) are of interest for their potential use as a unique identity or secret key that is generated from inherent characteristics caused by process variations. However, arbiter-based PUFs utilizing the relative delay-time difference between equivalent paths have a security issue in which the generated challenge-response pairs (CRPs) can be predicted by a machine learning attack. We previously proposed the RG-DTM PUF, in which a response is decided from divided time domains allocated to response 0 or 1, to improve the uniqueness of the conventional arbiter-PUF in a small circuit. However, its resistance against machine learning attacks has not yet been studied. In this paper, we evaluate the resistance against machine learning attacks by using a support vector machine (SVM) and logistic regression (LR) in both simulations and measurements and compare the RG-DTM PUF with the conventional arbiter-PUF and with the XOR arbiter-PUF, which strengthens the resistance by using XORing output from multiple arbiter-PUFs. In numerical simulations, prediction rates using both SVM and LR were above 90% within 1,000 training CRPs on the arbiter-PUF. The machine learning attack using the SVM could never predict responses on the XOR arbiter-PUF with over six arbiter-PUFs, whereas the prediction rate eventually reached 95% using the LR and many training CRPs. On the RG-DTM PUF, when the division number of the time domains was over eight, the prediction rates using the SVM were equal to the probability by guess. The machine learning attack using LR has the potential to predict responses, although an adversary would need to steal a significant amount of CRPs. However, the resistance can exponentially be strengthened with an increase in the division number, just like with the XOR arbiter-PUF. Over one million CRPs are required to attack the 16-divided RG-DTM PUF. Differences between the RG-DTM PUF and the XOR arbiter-PUF relate to the area penalty and the power penalty. Specifically, the XOR arbiter-PUF has to make up for resistance against machine learning attacks by increasing the circuit area, while the RG-DTM PUF is resistant against machine learning attacks with less area penalty and power penalty since only capacitors are added to the conventional arbiter-PUF. We also attacked RG-DTM PUF chips, which were fabricated with 0.18-µm CMOS technology, to evaluate the effect of physical variations and unstable responses. The resistance against machine learning attacks was related to the delay-time difference distribution, but unstable responses had little influence on the attack results.
Jianming WU Shunji MIYAZAKI Kazuhisa OHBUCHI Tomohiko TANIGUCHI
In this paper, we investigate the system performance of decode and forward based bi-directional relaying based on symbol-wise XOR operation. This technique gives more freedom in selecting the modulation and coding scheme at relay stations, and significantly relaxes the transmission bottleneck. However, the performance degradation occurs when the modulation orders of both links differ from each other. To mitigate such an impact, we exploit a repetition coding scheme in conjunction with a redundant modulation code scheme by overlapping MCS levels. To this end, a system level simulation proves that the proposed scheme achieves about 43% capacity gain over bit-wise XOR based bi-directional relaying and gives additional 10% gain over symbol-wise XOR based bi-directional relaying.
Jun KURIHARA Shinsaku KIYOMOTO Kazuhide FUKUSHIMA Toshiaki TANAKA
In Shamir's (k,n)-threshold secret sharing scheme [1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. However, there is no fast ideal (k,n)-threshold scheme, where k ≥ 3 and n is arbitrary. This paper proposes a new fast (3,n)-threshold scheme by using just EXCLUSIVE-OR(XOR) operations to make shares and recover the secret, which is an ideal secret sharing scheme similar to Shamir's scheme. Furthermore, we evaluate the efficiency of the scheme, and show that it is more efficient than Shamir's in terms of computational cost. Moreover, we suggest a fast (k,n)-threshold scheme can be constructed in a similar way by increasing the sets of random numbers constructing pieces of shares.
Debatosh DEBNATH Tsutomu SASAO
This paper presents a design method for AND-OR-EXOR three-level networks, where a single two-input exclusive-OR (EXOR) gate is used. The network realizes an EXOR of two sum-of-products expressions (EX-SOPs). The problem is to minimize the total number of products in the two sum-of-products expressions (SOPs). We introduce the notion of µ-equivalence of logic functions to develop exact minimization algorithms for EX-SOPs with up to five variables. We minimized all the NP-representative functions for up to five variables and showed that five-variable functions require 9 or fewer products in minimum EX-SOPs. For n-variable functions, minimum EX-SOPs require at most 9·2n-5 (n ≤ 6) products. This upper bound is smaller than 2n-1, which is the upper bound for SOPs. We also found that, for five-variable functions, on the average, minimum EX-SOPs require about 40% fewer literals than minimum SOPs.
This paper presents two improved triple parity placement schemes, the HDD1 (Horizontal and Dual Diagonal) scheme and the HDD2 scheme, to enhance the reliability of a disk array system. Both the schemes can tolerate up to three column disk failures by using three types of parity information (horizontal, diagonal, and anti-diagonal parities) in a disk array. HDD1 scheme can decrease the frequency of bottlenecks because its horizontal and anti-diagonal parities are uniformly distributed over a disk array, with its diagonal parities placed in dedicated column disks. HDD2 scheme possesses one more column disks than HDD1 to store the horizontal parities and an additional diagonal parity; its anti-diagonal and diagonal parities are placed in the same way as in HDD1 scheme, only with a minor difference. The encoding and decoding algorithms of the two schemes are rather simple and straightforward, some steps of its procedure can even be executed in parallel, which makes the disk failure recovery faster.
Debatosh DEBNATH Tsutomu SASAO
Fixed polarity Reed-Muller expressions (FPRMs) exhibit several useful properties that make them suitable for many practical applications. This paper presents an exact minimization algorithm for FPRMs for incompletely specified functions. For an n-variable function with α unspecified minterms there are 2n+α distinct FPRMs, and a minimum FPRM is one with the fewest product terms. To find a minimum FPRM the algorithm requires to determine an assignment of the incompletely specified minterms. This is accomplished by using the concept of integer-valued functions in conjunction with an extended truth vector and a weight vector. The vectors help formulate the problem as an assignment of the variables of integer-valued functions, which are then efficiently manipulated by using multi-terminal binary decision diagrams for finding an assignment of the unspecified minterms. The effectiveness of the algorithm is demonstrated through experimental results for code converters, adders, and randomly generated functions.
Ryoji ISHIKAWA Takashi HIRAYAMA Goro KODA Kensuke SHIMIZU
The utilization of EXOR gates often decreases the number of gates needed for realizing practical logical networks, and enhances the testability of networks. Therefore, logic synthesis with EXOR gates has been studied. In this paper we propose a new logic representation: an ESPP (EXOR-Sum-of-Pseudoproducts) form based on pseudoproducts. This form provides a new three-level network with EXOR gates. Some functional classes in ESPP forms can be realized with shorter expressions than in conventional forms such as the Sum-of-Products. Since many practical functions have the properties of such classes, the ESPP form is useful for making a compact form. We propose a heuristic minimization algorithm for ESPP, and we demonstrate the compactness of ESPPs by showing our experimental results. We apply our technique to some logic function classes and MCNC benchmark networks. The experimental results show that most ESPP forms have fewer literals than conventional forms.
Kenshi MATSUO Tetsuya KOYAMA Eiji TAKIMOTO Akira MARUOKA
We study relationships between the class of Boolean formulas called exclusive-or expansions based on monotone DNF formulas (
Ryoji ISHIKAWA Goro KODA Kensuke SHIMIZU
The discrete nature of data in a functional domain can generally be replaced by the global nature of data in the spectrum domain. In this paper we propose a fast procedure to detect autosymmetric function as an application of the spectrum technique. The autosymmetric function differs from the usual symmetric function and strongly relates with EXOR-based representations. It is known that many practical logical networks are autosymmetric, and this nature allows a useful functional class to realize a compact network with EXOR gates. Our procedure is able to detect autosymmetric functions quickly by using spectral coefficients. In experiments, our technique can detect the autosymmetry of most networks with a small number of checks of the spectrum.
Takashi HIRAYAMA Yasuaki NISHITANI Toru SATO
It has been considered difficult to obtain the minimum AND-EXOR expression of a given function with six variables in a practical computing time. In this paper, a faster algorithm of minimizing AND-EXOR expressions is proposed. We believe that our algorithm can compute the minimum AND-EXOR expressions of any six-variable and some seven-variable functions practically. In this paper, we first present a naive algorithm that searches the space of expansions of a given n-variable function f for a minimum expression of f. The space of expansions are generated by using all combinations of (n-1)-variable product terms. Then, how to prune the branches in the search process and how to restrict the search space to obtain the minimum solutions are discussed as the key point of reduction of the computing time. Finally a faster algorithm is constructed by using the methods discussed. Experimental results to demonstrate the effectiveness of these methods are also presented.
The authors propose and experimentally demonstrate an all-optical exclusive OR (XOR) logic gate based on self-phase modulation (SPM) of a semiconductor optical amplifier (SOA). The scheme is insensitive to the polarization of the input signal and requires no additional synchronized clock. The output of the XOR gate showed the contrast ratio of more than 17 dB for the input signal at 2.5 GHz.
Jar-Ferr YANG Shu-Sheng HAO Wei-Yuan LU
In this paper, we propose fast block matching criteria to reduce the implementation complexity of motion estimation in VLSI video coders. Based on generalized quantization of pixel difference measures, the block matching criteria combined with bitmap exclusive-OR (XOR) concept can be realized by short length adders and a multi-input binary counter. The proposed approach can be treated as a generalization of the pixel difference classification (PDC) criterion. Simulation results show that the proposed block-matching criteria along with various block search algorithms achieve better results than the PDC and obtain nearly the same performance as the mean absolute difference (MAD) criterion. However, the complete gate-level synthesis of the proposed matching criterion is much less than those of the MAD and the PDC in the VLSI implementation.
Shoji OTAKA Ryuichi FUJIMOTO Hiroshi TANIMOTO
A direct conversion transmitter IC including a proposed frequency doubler, a quadrature modulator, and a 3-bit variable attenuator was fabricated using BiCMOS technology with fT of 12 GHz. This architecture employing frequency doubler is intended for realizing wireless terminals that are low in cost and small in size. The architecture is effective for reducing serious interference between PA and VCO by making the VCO frequency different from that of PA. The proposed frequency doubler comprises a current-driven 90 phase-shifter and an ECL-EXOR circuit for both low power operation and wide input power range of local oscillator (LO). The proposed frequency doubler keeps high output power even when rectangular wave from LO is applied owing to use of the current-driven 90 phase-shifter instead of a voltage-driven 90 phase-shifter. An LO leakage of less than -25 dBc, an image rejection ratio in excess of 45 dBc, and a maximum attenuation of 21 dB were measured. The transmitter IC successfully operates at LO power above -15 dBm and consumes 68 mA from 2.7 V power supply voltage. An active die size is 1.5 mm3 mm.
Shigeru YAMASHITA Hiroshi SAWADA Akira NAGOYA
This paper presents a new efficient method for finding an "optimal" bi-decomposition form of a logic function. A bi-decomposition form of a logic function is the form: f(X) = α(g1(X1), g2(X2)). We call a bi-decomposition form optimal when the total number of variables in X1 and X2 is the smallest among all bi-decomposition forms of f. This meaning of optimal is adequate especially for the synthesis of LUT (Look-Up Table) networks where the number of function inputs is important for the implementation. In our method, we consider only two bi-decomposition forms; (g1 g2) and (g1 g2). We can easily find all the other types of bi-decomposition forms from the above two decomposition forms. Our method efficiently finds one of the existing optimal bi-decomposition forms based on a branch-and-bound algorithm. Moreover, our method can also decompose incompletely specified functions. Experimental results show that we can construct better networks by using optimal bi-decompositions than by using conventional decompositions.
Gil-Yoon KIM Yunju BAEK Heung-Kyu LEE
In this paper, we give a solution to the problem of conflict-free access of various slices of data in parallel processor for image processing. Image processing operations require a memory system that permits parallel and conflict-free access of rows, columns, forward diagonals, backward diagonals, and blocks of two-dimensional image array for an arbitrary location. Linear skewing schemes are useful methods for those requirements, but these schemes require complex Euclidean division by prime number. On the contrary, nonlinear skewing schemes such as XOR-schemes have more advantages than the linear ones in address generation, but these schemes allow conflict-free access of some array slices in restricted region. In this paper, we propose a new XOR-scheme which allows conflict-free access of arbitrarily located various slices of data for image processing, with a two-fold the number of memory modules than that of processing elements. Further, we propose an efficient data alignment network which consists of log N + 2-stage multistage interconnection network utilizing Omega network.
Considering the pattern classification/recognition tasks, the influence of the activation function on fault tolerance property of feedforward neural networks is empirically investigated. The simulation results show that the activation function largely influences the fault tolerance and the generalization property of neural networks. It is found that, neural networks with symmetric sigmoid activation function are largely fault tolerant than the networks with asymmetric sigmoid function. However the close relation between the fault tolerance and the generalization property was not observed and the networks with asymmetric activation function slightly generalize better than the networks with the symmetric activation function. First, the influence of the activation function on fault tolerance property of neural networks is investigated on the XOR problem, then the results are generalized by evaluating the fault tolerance property of different NNs implementing different benchmark problems.
Tsunemasa HAYASHI Atsushi TAKAHARA Kennosuke FUKAMI
This paper presents an FPGA architecture for high-speed systems, such as next-generation B-ISDN telecommunications systems. Such a system requires an LSI in which an over-10K-gate circuit can be implemented and that has a clock cycle rate of 80MHz. So far, the FPGA architecture has only been discussed in terms of its circuit structure. In contrast we consider the circuit structure of the FPGA along with the performance of its dedicated CAD system. We evaluate several FPGA logic-element structures with a technology mapping method. From these experiments, a multiplexor-based logic-element is found to be suitable for implementing such a high-speed circuit using the BDD-based technology mapping method. In addition, we examine how to best utilize the characteristics of the selected logic-cell structure in designing the wiring structure. It is found that the multiplexor-based cell can be connected efficiently in a clustered wiring structure.