Jorge AGUILAR-TORRENTERA Gerardo GARCÍA-SÁNCHEZ Ramón RODRÍGUEZ-CRUZ Izzat Z. DARWAZEH
In this paper, the analog code modulation characteristics of distributed-based transversal filters (DTFs) suitable for use in spectrally encoded CDMA systems are presented. The DTF is verified as an appropriate method to use in high-speed CDMA systems as opposed to previously proposed methods, which are intended for Direct Sequence (DS) CDMA systems. The large degree of freedom of DTF design permits controlling the filter pulse response to generate well specified temporal phase-coded signals. A decoder structure that performs bipolar detection of user subbands giving rise to a Spectral-Amplitude Encoded CDMA system is considered. Practical implementations require truncating the spreading signals by a time window of duration equal to the span time of the tapped delay line. Filter functions are chosen to demodulate the matched channel and achieve improved user interference rejection avoiding the need for transversal filters featuring a large number of taps. As a proof-of-concept of the electronic SAE scheme, practical circuit designs are developed at low speeds (3-dB point at 1 GHz) demonstrating the viability of the proposal.
Tadashi WADAYAMA Taisuke IZUMI
Several types of capacitive crosstalk avoidance codes have been devised in order to prevent capacitive crosstalk in on-chip buses. These codes are designed to prohibit transition patterns prone to capacitive crosstalk from any two consecutive words transmitted to on-chip buses. The present paper provides a rigorous analysis of the asymptotic rate for (p,q)-transition free word sequences under the assumption that coding is based on a stateful encoder and a stateless decoder. Here, p and q represent k-bit transition patterns that should not appear in any two consecutive words at the same adjacent k-bit positions. The maximum rate for the sequences is proven to be equal to the subgraph domatic number of the (p,q)-transition free graph. Based on the theoretical results for the subgraph domatic partition problem, lower and upper bounds on the asymptotic rate are derived. We also show that the asymptotic rate 0.8325 is achievable for p=01 and q=10 transition free word sequences.
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.
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.
Tomohiko UYEMATSU Tetsunao MATSUTA
This paper considers a joint channel coding and random number generation from the channel output. Specifically, we want to transmit a message to a receiver reliably and at the same time the receiver extracts pure random bits independent of the channel input. We call this problem as the joint channel coding and intrinsic randomness problem. For general channels, we clarify the trade-off between the coding rate and the random bit rate extracted from the channel output by using the achievable rate region, where both the probability of decoding error and the approximation error of random bits asymptotically vanish. We also reveal the achievable rate regions for stationary memoryless channels, additive channels, symmetric channels, and mixed channels.
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.
Shan LU Hiroshi KAMABE Jun CHENG Akira YAMAWAKI
Recent years have seen increasing efforts to improve the input/output performance of multilevel flash memory. In this regard, we propose a coding scheme for two-page unrestricted-rate parallel random input-output (P-RIO) code, which enables different code rates to be used for each page of multilevel memory. On the second page, the set of cell-state vectors for each message consists of two complementary vectors with length n. There are a total of 2n-1 sets that are disjoint to guarantee that they are uniquely decodable for 2n-1 messages. On the first page, the set of cell-state vectors for each message consists of all weight-u vectors with their non-zero elements restricted to the same (2u-1) positions, where the non-negative integer u is less than or equal to half of the code length. Finding cell-state vector sets such that they are disjoint on the first page is equivalent to the construction of constant-weight codes, and the number of disjoint sets is the best-known number of code words in the constant-weight codes. Our coding scheme is constructive, and the code length is arbitrary. The sum rates of our proposed codes are higher than those of previous work.
Dongshin YANG Yutaka JITSUMATSU
Compressed Sensing (CS) is known to provide better channel estimation performance than the Least Square (LS) method for channel estimation. However, multipath delays may not be resolved if they span between the grids. This grid problem of CS is an obstacle to super resolution channel estimation. An Atomic Norm (AN) minimization is one of the methods for estimating continuous parameters. The AN minimization can successfully recover a spectrally sparse signal from a few time-domain samples even though the dictionary is continuous. There are studies showing that the AN minimization method has better resolution than conventional CS methods. In this paper, we propose a channel estimation method based on the AN minimization for Spread Spectrum (SS) systems. The accuracy of the proposed channel estimation is compared with the conventional LS method and Dantzig Selector (DS) of the CS. In addition to the application of channel estimation in wireless communication, we also show that the AN minimization can be applied to Global Positioning System (GPS) using Gold sequence.
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.
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.
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.
Mengbo ZHANG Lunwen WANG Yanqing FENG Haibo YIN
Spectrum sensing is the first task performed by cognitive radio (CR) networks. In this paper we propose a spectrum sensing algorithm for orthogonal frequency division multiplex (OFDM) signal based on deep learning and covariance matrix graph. The advantage of deep learning in image processing is applied to the spectrum sensing of OFDM signals. We start by building the spectrum sensing model of OFDM signal, and then analyze structural characteristics of covariance matrix (CM). Once CM has been normalized and transformed into a gray level representation, the gray scale map of covariance matrix (GSM-CM) is established. Then, the convolutional neural network (CNN) is designed based on the LeNet-5 network, which is used to learn the training data to obtain more abstract features hierarchically. Finally, the test data is input into the trained spectrum sensing network model, based on which spectrum sensing of OFDM signals is completed. Simulation results show that this method can complete the spectrum sensing task by taking advantage of the GSM-CM model, which has better spectrum sensing performance for OFDM signals under low SNR than existing methods.
For an odd prime p and a positive integer k ≥ 2, we propose and analyze construction of perfect pk-ary sequences of period pk based on cubic polynomials over the integers modulo pk. The constructed perfect polyphase sequences from cubic polynomials is a subclass of the perfect polyphase sequences from the Mow's unified construction. And then, we give a general approach for constructing optimal families of perfect polyphase sequences with some properties of perfect polyphase sequences and their optimal families. By using this, we construct new optimal families of pk-ary perfect polyphase sequences of period pk. The constructed optimal families of perfect polyphase sequences are of size p-1.
Deng TANG Shaojing FU Yang YANG
Semi-bent functions have very high nonlinearity and hence they have many applications in symmetric-key cryptography, binary sequence design for communications, and combinatorics. In this paper, we focus on studying the additive autocorrelation of semi-bent functions. We provide a lower bound on the maximum additive autocorrelation absolute value of semi-bent functions with three-level additive autocorrelation. Semi-bent functions with three-level additive autocorrelation achieving this bound with equality are said to have perfect three-level additive autocorrelation. We present two classes of balanced semi-bent functions with optimal algebraic degree and perfect three-level additive autocorrelation.
Fanxin ZENG Xiping HE Guojun LI Guixin XUAN Zhenyu ZHANG Yanni PENG Sheng LU Li YAN
This paper improves the family size of quadrature amplitude modulation (QAM) complementary sequences with binary inputs. By employing new mathematical description: B-type-2 of 4q-QAM constellation (integer q ≥ 2), a new construction yielding 4q-QAM complementary sequences (CSs) with length 2m (integer m ≥ 2) is developed. The resultant sequences include the known QAM CSs with binary inputs as special cases, and the family sizes of new sequences are approximately 22·2q-4q-1(22·2q-3-1) times as many as the known. Also, both new sequences and the known have the same the peak envelope power (PEP) upper bounds, when they are used in an orthogonal frequency-division multiplexing communication system.
Chun-Lin LIN Tzu-Hsiang LIN Ruey-Yi WEI
Bit-interleaved coded modulation with iterative decoding (BICM-ID) is suitable for correlated Rayleigh fading channels. Additionally, BICM-ID using differential encoding can avoid the pilot overhead. In this paper, we consider BICM-ID using 16-DAPSK (differential amplitude and phase-shift keying). We first derive the probability of receiving signals conditioned on the transmission of input bits for general differential encoding; then we propose two new 16-DAPSK bit labeling methods. In addition, convolutional codes for the new bit labeling are developed. Both the minimum distance and the simulation results show that the proposed labeling has better error performance than that of the original differential encoding, and the searched new codes can further improve the error performance.
Teruaki KITASUKA Takayuki MATSUZAKI Masahiro IIDA
The order/degree problem consists of finding the smallest diameter graph for a given order and degree. Such a graph is beneficial for designing low-latency networks with high performance for massively parallel computers. The average shortest path length (ASPL) of a graph has an influence on latency. In this paper, we propose a novel order adjustment approach. In the proposed approach, we search for Cayley graphs of the given degree that are close to the given order. We then adjust the order of the best Cayley graph to meet the given order. For some order and degree pairs, we explain how to derive the smallest known graphs from the Graph Golf 2016 and 2017 competitions.
Taishin NAKAMURA Hisashi YAMAMOTO Tomoaki AKIBA
An optimal arrangement problem involves finding a component arrangement to maximize system reliability, namely, the optimal arrangement. It is useful to obtain the optimal arrangement when we design a practical system. An existing study developed an algorithm for finding the optimal arrangement of a connected-(r, s)-out-of-(m, n): F lattice system with r=m-1 and n<2s. However, the algorithm is time-consuming to find the optimal arrangement of a system having many components. In this study, we develop an algorithm for efficiently finding the optimal arrangement of the system with r=m-1 and s=n-1 based on the depth-first branch-and-bound method. In the algorithm, before enumerating arrangements, we assign some components without computing the system reliability. As a result, we can find the optimal arrangement effectively because the number of components which must be assigned decreases. Furthermore, we develop an efficient method for computing the system reliability. The numerical experiment demonstrates the effectiveness of our proposed algorithm.