Search

Energy is a primary constraint in processor design, and much of that energy is consumed in on-chip communication. Communication can be intra-core (e.g., from a register file to an ALU) or inter-core (e.g., over the on-chip network). In this paper, we use the on-chip network (OCN) as a case study for saving on-chip communication energy. We have identified a new way to reduce the OCN's link energy consumption by using line coding, a longstanding technique in information theory. Our line codes, called Low-Energy Line Codes (LELCs), reduce energy by reducing the frequency of voltage transitions of the links, and they achieve a range of energy/performance trade-offs.

Spatially-coupled (SC) codes is a class of convolutional LDPC codes that has been well investigated in classical coding theory thanks to their high performance and compatibility with low-latency decoders. We describe toric codes as quantum counterparts of classical two-dimensional spatially-coupled (2D-SC) codes, and introduce spatially-coupled quantum LDPC (SC-QLDPC) codes as a generalization. We use the convolutional structure to represent the parity check matrix of a 2D-SC code as a polynomial in two indeterminates, and derive an algebraic condition that is both necessary and sufficient for a 2D-SC code to be a stabilizer code. This algebraic framework facilitates the construction of new code families. While not the focus of this paper, we note that small memory facilitates physical connectivity of qubits, and it enables local encoding and low-latency windowed decoding. In this paper, we use the algebraic framework to optimize short cycles in the Tanner graph of 2D-SC hypergraph product (HGP) codes that arise from short cycles in either component code. While prior work focuses on QLDPC codes with rate less than 1/10, we construct 2D-SC HGP codes with small memories, higher rates (about 1/3), and superior thresholds., Comment: 26 pages, 7 figures

Data-driven applications are becoming ubiquitous. This dissertation is focused on developing advanced channel coding techniques for improved reliability and latency in a variety of data-hungry applications, from cloud storage, to memory devices, and quantum communications.The first line of our work focused on cloud storage. In order to accommodate the ever-growing data from various, possibly independent, sources and the dynamic nature of data usage rates in practical applications, modern cloud data storage systems are required to be scalable, flexible, and heterogeneous. The recent rise of the blockchain technology is also moving various information systems towards decentralization to achieve high privacy at low costs. We proposed channel codes with hierarchical locality that were the first to simultaneously achieve scalability and flexibility for both centralized cloud storage and decentralized storage networks (DSN). In particular, we proposed a joint coding scheme where each node receives extra protection through the cooperation with nodes in its neighborhood in a heterogeneous DSN with any given topology. Our proposed construction not only preserves desirable properties such as scalability and flexibility, which are critical in dynamic networks, but also adapts to arbitrary topologies, a property that is essential in DSNs but has been overlooked in existing works.The second line of our work focused on spatially-coupled (SC) codes design for advanced memory devices and quantum communications. SC codes have demonstrated potential in a variety of applications thanks to their excellent error-correcting performance and desirable structures that enable low latency decoding. While high memory SC codes are known to have superior performance, no prior work was able to produce practical codes due to computational complexity of the high-memory regime. We overcome this computational bottleneck in the finite-length construction of high-performance SC codes with high memory

Data-driven applications are becoming ubiquitous. This dissertation is focused on developing advanced channel coding techniques for improved reliability and latency in a variety of data-hungry applications, from cloud storage, to memory devices, and quantum communications.The first line of our work focused on cloud storage. In order to accommodate the ever-growing data from various, possibly independent, sources and the dynamic nature of data usage rates in practical applications, modern cloud data storage systems are required to be scalable, flexible, and heterogeneous. The recent rise of the blockchain technology is also moving various information systems towards decentralization to achieve high privacy at low costs. We proposed channel codes with hierarchical locality that were the first to simultaneously achieve scalability and flexibility for both centralized cloud storage and decentralized storage networks (DSN). In particular, we proposed a joint coding scheme where each node receives extra protection through the cooperation with nodes in its neighborhood in a heterogeneous DSN with any given topology. Our proposed construction not only preserves desirable properties such as scalability and flexibility, which are critical in dynamic networks, but also adapts to arbitrary topologies, a property that is essential in DSNs but has been overlooked in existing works.The second line of our work focused on spatially-coupled (SC) codes design for advanced memory devices and quantum communications. SC codes have demonstrated potential in a variety of applications thanks to their excellent error-correcting performance and desirable structures that enable low latency decoding. While high memory SC codes are known to have superior performance, no prior work was able to produce practical codes due to computational complexity of the high-memory regime. We overcome this computational bottleneck in the finite-length construction of high-performance SC codes with high memory

Spatially-coupled (SC) codes, known for their threshold saturation phenomenon and low-latency windowed decoding algorithms, are ideal for streaming applications and data storage systems. SC codes are constructed by partitioning an underlying block code, followed by rearranging and concatenating the partitioned components in a convolutional manner. The number of partitioned components determines the memory of SC codes. In this paper, we investigate the relation between the performance of SC codes and the density distribution of partitioning matrices. While adopting higher memories results in improved SC code performance, obtaining finite-length, high-performance SC codes with high memory is known to be computationally challenging. We break this computational bottleneck by developing a novel probabilistic framework that obtains (locally) optimal density distributions via gradient descent. Starting from random partitioning matrices abiding by the obtained distribution, we perform low-complexity optimization algorithms that minimize the number of detrimental objects to construct high-memory, high-performance quasi-cyclic SC codes. We apply our framework to various objects of interests, from the simplest short cycles, to more sophisticated objects such as concatenated cycles aiming at finer-grained optimization. Simulation results show that codes obtained through our proposed method notably outperform state-of-the-art SC codes with the same constraint length and optimized SC codes with uniform partitioning. The performance gain is shown to be universal over a variety of channels, from canonical channels such as additive white Gaussian noise and binary symmetric channels, to practical channels underlying flash memory and magnetic recording systems., Comment: 26 pages, 30 figures, 2 tables, the manuscript has been submitted to IEEE Transactions on Information Theory. arXiv admin note: substantial text overlap with arXiv:2101.09962

Markov random fields (MRFs) appear in many problems in machine learning and statistics. From a computational learning theory point of view, a natural problem of learning MRFs arises: given samples from an MRF from a restricted class, learn the structure of the MRF, that is the neighbors of each node of the underlying graph. In this work, we start at a known near-optimal classical algorithm for this learning problem and develop a modified classical algorithm. This classical algorithm retains the run time and guarantee of the previous algorithm and enables the use of quantum subroutines. Adapting a previous quantum algorithm, the Quantum Sparsitron, we provide a polynomial quantum speedup in terms of the number of variables for learning the structure of an MRF, if the MRF has bounded degree., Comment: 35 pages

Computational storage, known as a solution to significantly reduce the latency by moving data-processing down to the data storage, has received wide attention because of its potential to accelerate data-driven devices at the edge. To meet the insatiable appetite for complicated functionalities tailored for intelligent devices such as autonomous vehicles, properties including heterogeneity, scalability, and flexibility are becoming increasingly important. Based on our prior work on hierarchical erasure coding that enables scalability and flexibility in cloud storage, we develop an efficient decoding algorithm that corrects a mixture of errors and erasures simultaneously. We first extract the basic component code, the so-called extended Cauchy (EC) codes, of the proposed coding solution. We prove that the class of EC codes is strictly larger than that of relevant codes with known explicit decoding algorithms. Motivated by this finding, we then develop an efficient decoding method for the general class of EC codes, based on which we propose the local and global decoding algorithms for the hierarchical codes. Our proposed hybrid error correction not only enables the usage of hierarchical codes in computational storage at the edge, but also applies to any Cauchy-like codes and allows potentially wider applications of the EC codes., Comment: 29 pages (single column), 0 figures, to be submitted to IEEE Transactions on Communications

Spatially-coupled (SC) codes, known for their threshold saturation phenomenon and low-latency windowed decoding algorithms, are ideal for streaming applications. They also find application in various data storage systems because of their excellent performance. SC codes are constructed by partitioning an underlying block code, followed by rearranging and concatenating the partitioned components in a "convolutional" manner. The number of partitioned components determines the "memory" of SC codes. While adopting higher memories results in improved SC code performance, obtaining optimal SC codes with high memory is known to be hard. In this paper, we investigate the relation between the performance of SC codes and the density distribution of partitioning matrices. We propose a probabilistic framework that obtains (locally) optimal density distributions via gradient descent. Starting from random partitioning matrices abiding by the obtained distribution, we perform low complexity optimization algorithms over the cycle properties to construct high memory, high performance quasi-cyclic SC codes. Simulation results show that codes obtained through our proposed method notably outperform state-of-the-art SC codes with the same constraint length and codes with uniform partitioning., Comment: 8 pages, 10 figures, 1 table, the shortened version has been submitted to ISIT 2021

Permutation codes have recently garnered substantial research interest due to their potential in various applications including cloud storage systems, genome resequencing and flash memories. In this paper, we study the theoretical bounds and constructions of permutation codes in the generalized Cayley metric. The generalized Cayley metric captures the number of generalized transposition errors in a permutation, and subsumes previously studied error types, including transpositions and translocations, without imposing restrictions on the lengths and positions of the translocated segments. Relying on the breakpoint analysis proposed by Chee and Vu, we first propose a coding scheme that is order-optimal albeit not constructive based on this method. We then develop another construction of permutation codes in the generalized Cayley distance. This scheme is both explicit and systematic. We also prove the existence of order- optimal systematic codes and offer a concrete construction based on this method. For the generalized Cayley metric, we prove that our coding schemes have less redundancy than the existing codes based on interleaving when the codelength is sufficiently large and the number of errors is relatively small.

Permutation codes have recently garnered substantial research interest due to their potential in various applications including cloud storage systems, genome resequencing and flash memories. In this paper, we study the theoretical bounds and constructions of permutation codes in the generalized Cayley metric. The generalized Cayley metric captures the number of generalized transposition errors in a permutation, and subsumes previously studied error types, including transpositions and translocations, without imposing restrictions on the lengths and positions of the translocated segments. Relying on the breakpoint analysis proposed by Chee and Vu, we first propose a coding scheme that is order-optimal albeit not constructive based on this method. We then develop another construction of permutation codes in the generalized Cayley distance. This scheme is both explicit and systematic. We also prove the existence of order- optimal systematic codes and offer a concrete construction based on this method. For the generalized Cayley metric, we prove that our coding schemes have less redundancy than the existing codes based on interleaving when the codelength is sufficiently large and the number of errors is relatively small.

From currency to cloud storage systems, the continuous rise of the blockchain technology is moving various information systems towards decentralization. Blockchain-based decentralized storage networks (DSNs) offer significantly higher privacy and lower costs to customers compared with centralized cloud storage associated with specific vendors. Coding is required in order to retrieve data stored on failing components. While coding solutions for centralized storage have been intensely studied, topology-aware coding for heterogeneous DSNs have not yet been discussed. In this paper, we propose a joint coding scheme where each node receives extra protection through the cooperation with nodes in its neighborhood in a heterogeneous DSN with any given topology. As an extension of, which also subsumes, our prior work on coding for centralized cloud storage, our proposed construction preserves desirable properties such as scalability and flexibility in networks with varying topologies., Comment: 6 pages, 7 figures, the edits in this version are in response to the reviews we received on the short version accepted recently at ISIT 2020

Graph based codes such as low density parity check (LDPC) codes have been shown promising for the information reconciliation phase in quantum key distribution (QKD). However, existing graph coding schemes have not fully utilized the properties of the QKD channel. In this work, we first investigate the channel statistics for discrete variable (DV) QKD based on energy-time entangled photons. We then establish a so-called balanced modulation scheme that is promising for this channel. Based on the modulation, we propose a joint local-global graph coding scheme that is expected to achieve good error-correction performance., Comment: 5 pages, 5 figures, presented on the 53rd Asilomar Conference on Signals, Systems and Computers

In order to accommodate the ever-growing data from various, possibly independent, sources and the dynamic nature of data usage rates in practical applications, modern cloud data storage systems are required to be scalable, flexible, and heterogeneous. The recent rise of the blockchain technology is also moving various information systems towards decentralization to achieve high privacy at low costs. While codes with hierarchical locality have been intensively studied in the context of centralized cloud storage due to their effectiveness in reducing the average reading time, those for decentralized storage networks (DSNs) have not yet been discussed. In this paper, we propose a joint coding scheme where each node receives extra protection through the cooperation with nodes in its neighborhood in a heterogeneous DSN with any given topology. This work extends and subsumes our prior work on coding for centralized cloud storage. In particular, our proposed construction not only preserves desirable properties such as scalability and flexibility, which are critical in dynamic networks, but also adapts to arbitrary topologies, a property that is essential in DSNs but has been overlooked in existing works., Comment: 25 pages (single column), 19 figures, submitted to the IEEE Transactions on Information Theory (TIT)

In order to accommodate the ever-growing data from various, possibly independent, sources and the dynamic nature of data usage rates in practical applications, modern cloud data storage systems are required to be scalable, flexible, and heterogeneous. Codes with hierarchical locality have been intensively studied due to their effectiveness in reducing the average reading time in cloud storage. In this paper, we present the first codes with hierarchical locality that achieve scalability and flexibility in heterogeneous cloud storage using small field size. We propose a double-level construction utilizing so-called Cauchy Reed-Solomon codes. We then develop a triple-level construction based on this double-level code; this construction can be easily generalized into any hierarchical structure with a greater number of layers since it naturally achieves scalability in the cloud storage systems., Comment: 7 pages, 1 figure, a shortened 6 pages version has been submitted to IEEE GLOBECOM 2019

Permutation codes have recently garnered substantial research interest due to their potential in various applications including cloud storage systems, genome resequencing and flash memories. In this paper, we study the theoretical bounds and constructions of permutation codes in the generalized Cayley metric. The generalized Cayley metric captures the number of generalized transposition errors in a permutation, and subsumes previously studied error types, including transpositions and translocations, without imposing restrictions on the lengths and positions of the translocated segments. Relying on the breakpoint analysis proposed by Chee and Vu, we first propose a coding scheme that is order-optimal albeit not constructive based on this method. We then develop another construction of permutation codes in the generalized Cayley distance. This scheme is both explicit and systematic. We also prove the existence of order-optimal systematic codes and offer a concrete construction based on this method. For the generalized Cayley metric, we prove that our coding schemes have less redundancy than the existing codes based on interleaving when the codelength is sufficiently large and the number of errors is relatively small., Comment: 18 pages; 0 figures; published on IEEE Transactions on Information Theory

The complexity class PPA consists of NP-search problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from graph theory, combinatorics, algebra and number theory, but only a few of these are known to be complete in the class. Before this work, the known complete problems were all discretizations or combinatorial analogues of topological fixed point theorems. Here we prove the PPA-completeness of two problems of radically different style. They are PPA-Circuit CNSS and PPA-Circuit Chevalley, related respectively to the Combinatorial Nullstellensatz and to the Chevalley-Warning Theorem over the two elements field GF(2). The input of these problems contain PPA-circuits which are arithmetic circuits with special symmetric properties that assure that the polynomials computed by them have always an even number of zeros. In the proof of the result we relate the multilinear degree of the polynomials to the parity of the maximal parse subcircuits that compute monomials with maximal multilinear degree, and we show that the maximal parse subcircuits of a PPA-circuit can be paired in polynomial time.

The complexity class PPA consists of NP-search problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from graph theory, combinatorics, algebra and number theory, but only a few of these are known to be complete in the class. Before this work, the known complete problems were all discretizations or combinatorial analogues of topological fixed point theorems. Here we prove the PPA-completeness of two problems of radically different style. They are PPA-Circuit CNSS and PPA-Circuit Chevalley, related respectively to the Combinatorial Nullstellensatz and to the Chevalley-Warning Theorem over the two elements field GF(2). The input of these problems contain PPA-circuits which are arithmetic circuits with special symmetric properties that assure that the polynomials computed by them have always an even number of zeros. In the proof of the result we relate the multilinear degree of the polynomials to the parity of the maximal parse subcircuits that compute monomials with maximal multilinear degree, and we show that the maximal parse subcircuits of a PPA-circuit can be paired in polynomial time.

The complexity class PPA consists of NP-search problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from graph theory, combinatorics, algebra and number theory, but only a few of these are known to be complete in the class. Before this work, the known complete problems were all discretizations or combinatorial analogues of topological fixed point theorems. Here we prove the PPA-completeness of two problems of radically different style. They are PPA-Circuit CNSS and PPA-Circuit Chevalley, related respectively to the Combinatorial Nullstellensatz and to the Chevalley-Warning Theorem over the two elements field GF(2). The input of these problems contain PPA-circuits which are arithmetic circuits with special symmetric properties that assure that the polynomials computed by them have always an even number of zeros. In the proof of the result we relate the multilinear degree of the polynomials to the parity of the maximal parse subcircuits that compute monomials with maximal multilinear degree, and we show that the maximal parse subcircuits of a PPA-circuit can be paired in polynomial time., Comment: 26 pages

How banks set the mortgage interest rates and the sizes of the mortgage margins they obtain from making mortgage loans always attract attention from households, government authorities, politicians and market actors. This thesis studies the relationship between Swedish mortgage interest rates and mortgage lending institutions’ costs of obtaining funds, and how the gross margins of mortgage interest rates influence the banks stock returns. In general, banks’ mortgage margins are correlated with their funding costs, which are typically reflected in the yields of mortgage bonds (covered bonds), interbank rates (STIBOR) and the repo rate. How-ever the correlations change over time and sometimes the mortgage margins are relatively low and sometimes relatively high. Since mortgage loans play an important role in banks’ lending business, the related interest rate margins should influence banks’ profitability and therefore the performance of their stock. Everything else equal, higher margins should result in higher stock returns. I have collected and constructed a time-series data set based on Swedbank mortgage rates, Swedbank stock prices, yields on government bonds, yields on mortgage bonds, STIBOR interest rates, and repo rate. Both descriptive analysis and econometric models are applied to analyze the time-varying characteristics of the financial data. The thesis covers unconditional correlation (Pearson correlations), and conditional correlation through applying DCC-GARCH models. Besides, ARCH and GARCH models are employed to measure the ARCH and GARCH effects of the spread (premium) terms between interest rates. The results from descriptive analysis and econometric models present the tight relationships between the mortgage interest rates and the corresponding funding costs, and show the posi-tive but low correlations between mortgage margins and bank’s stock returns. The results also support the existence of time-vary volatilities (risk) of spread (premium) terms and

How banks set the mortgage interest rates and the sizes of the mortgage margins they obtain from making mortgage loans always attract attention from households, government authorities, politicians and market actors. This thesis studies the relationship between Swedish mortgage interest rates and mortgage lending institutions’ costs of obtaining funds, and how the gross margins of mortgage interest rates influence the banks stock returns. In general, banks’ mortgage margins are correlated with their funding costs, which are typically reflected in the yields of mortgage bonds (covered bonds), interbank rates (STIBOR) and the repo rate. How-ever the correlations change over time and sometimes the mortgage margins are relatively low and sometimes relatively high. Since mortgage loans play an important role in banks’ lending business, the related interest rate margins should influence banks’ profitability and therefore the performance of their stock. Everything else equal, higher margins should result in higher stock returns. I have collected and constructed a time-series data set based on Swedbank mortgage rates, Swedbank stock prices, yields on government bonds, yields on mortgage bonds, STIBOR interest rates, and repo rate. Both descriptive analysis and econometric models are applied to analyze the time-varying characteristics of the financial data. The thesis covers unconditional correlation (Pearson correlations), and conditional correlation through applying DCC-GARCH models. Besides, ARCH and GARCH models are employed to measure the ARCH and GARCH effects of the spread (premium) terms between interest rates. The results from descriptive analysis and econometric models present the tight relationships between the mortgage interest rates and the corresponding funding costs, and show the posi-tive but low correlations between mortgage margins and bank’s stock returns. The results also support the existence of time-vary volatilities (risk) of spread (premium) terms and