Reliable matrix-vector multiplication (MVM) in edge devices is a key enabler for modern computational tasks such as AI inference. Novel memory technologies, such as MRAMs, enable highly efficient analog computation of MVM. While significantly improving speed and power consumption, these architectures suffer from reduced reliability. We introduce a coding scheme in which the parity constraints of the code are employed toward in-memory noise estimation, in addition to their traditional role of error correction. Our scheme relies on objects we call analog syndromes, which on one hand can be efficiently computed in memory, and on the other hand are shown analytically to provide more accurate estimation than classical logical syndromes. The scheme utilizes a previously introduced bilayer LDPC design with sub-block locality, and describes how to design the degree distributions.

In-memory computing architectures highly improve computation latency and power compared to von Neumann architectures suffering the memory wall. However, maintaining reliability is challenging due to the difficulty in implementing error-correction coding within memory. We propose a scheme in which strong codes can be used for in-memory computing, while avoiding their costly decoding when error rates are sufficiently small. The key idea and thrust of the paper is to complement the design of LDPC codes to also provide accurate estimation of the input bit-error rate (BER). Toward that, we derive analytical results and give code-design insights for BER estimation in two frameworks: minimizing the mean-squared error (MSE), and estimating threshold crossing as a hypothesis-testing problem.

We propose a novel low-complexity Noise-Recyclebased Decoder (NRD) for Multi-Level Cells (MLC) to obtain high storage rates. Our proposed scheme utilizes Block Partition (BP) mapping in multi-level flash memory. Based on multi-stage decoding, NRD method decodes layers sequentially, starting from the MSB (layer 1) to improve noise robustness. Specifically, a digital noise realization is estimated utilizing already decoded layers. This estimated noise is then recycled by subtraction in the subsequent layers pre-decoding to improve Bit Error Rate (BER). Noise Recycling (NR) approach assumes simultaneous reading of an entire MLC, ensuring a fixed correlated noise realization for decoding all layers within a cell. For noise shifts across multiple representation levels, we establish a reliability bound and show via simulations that the proposed NRD solution outperforms Independent Decoding (ID) with both BP and Gray mappings without NR. For a single-level noise shift, we analytically and through simulations demonstrate that the proposed scheme outperforms the baseline ID scheme with BP mapping and no NR, while achieving equal performance to ID with Gray mapping and no NR. We introduce new capacity and reliability bounds for MLC NAND flash memory using BP mapping under single-level noise shifts.

Flash memory-based processing-in-memory (flashbased PIM) offers high storage capacity and computational efficiency but faces significant reliability challenges due to noise in high-density multi-level cell (MLC) flash memories. Existing verify level optimization methods are designed for general storage scenarios and fail to address the unique requirements of flashbased PIM systems, where metrics such as mean squared error (MSE) and peak signal-to-noise ratio (PSNR) are critical. This paper introduces an integrated framework that jointly optimizes quantization and verify levels to minimize the MSE, considering both quantization and flash memory channel errors. We develop an iterative algorithm to solve the joint optimization problem. Experimental results on quantized images and SwinIR model parameters stored in flash memory show that the proposed method significantly improves the reliability of flash-based PIM systems.

As machine-learning models grow in size, their implementation requirements cannot be met by a single computer system. This observation motivates distributed settings, in which intermediate computations are performed across a network of processing units, while the central node only aggregates their outputs. However, distributing inference tasks across low-precision or faulty edge devices, operating over a network of noisy communication channels, gives rise to serious reliability challenges. We study the problem of an ensemble of devices, implementing regression algorithms, that communicate through additive noisy channels in order to collaboratively perform a joint regression task. We define the problem formally, and develop methods for optimizing the aggregation coefficients for the parameters of the noise in the channels, which can potentially be correlated. Our results apply to the leading state-of-the-art ensemble regression methods: bagging and gradient boosting. We demonstrate the effectiveness of our algorithms on both synthetic and real-world datasets.

Merkle trees play a crucial role in blockchain networks in organizing network state. They allow proving a particular value of an entry in the state to a node that maintains only the root of the Merkle trees, a hash-based signature computed over the data in a hierarchical manner. Verification of particular state entries is crucial in reaching a consensus on the execution of a block where state information is required in the processing of its transactions. For instance, a payment transaction should be based on the balance of the two involved accounts. The proof length affects the network communication and is typically logarithmic in the state size. In this paper, we take advantage of typical transaction characteristics for better organizing Merkle trees to improve blockchain network performance. We focus on the common transaction processing where Merkle proofs are jointly provided for multiple accounts. We first provide lower bounds for the communication cost that are based on the distribution of accounts involved in the transactions. We then describe algorithms that consider traffic patterns for significantly reducing it. The algorithms are inspired by various coding methods such as Huffman coding, partition and weight balancing. We also generalize our approach towards the encoding of smart contract transactions that involve an arbitrary number of accounts. Likewise, we rely on real blockchain data to show the savings allowed by our approach. The experimental evaluation is based on transactions from the Ethereum network and demonstrates cost reduction for both payment transactions and smart contract transactions.

Barrier-error channels have been suggested as a model for non-binary channels that are milder than symmetric-error channels. Such channels are motivated by practical applications in data storage and communications. The barrier-error model allows errors only to (downward) and from (upward) a specific symbol within the alphabet. We study a generalization of prior barrier-error models that considers different numbers of downward and upward errors. The results of this paper include a sufficient condition for error correction, code-size upper and lower bounds, a code construction decomposing to just two constituent symmetric-error codes (prior ones used many), and a decoding algorithm that decodes the two codes jointly. The decoder is shown empirically to achieve better block error rates when compared to previous algorithms.

In data-intensive applications, it is advantageous to perform partial processing close to the data, and communicate intermediate results to a central processor, instead of the data itself. When the communication or computation medium is noisy, the resulting degradation in computation quality at the central processor must be mitigated. We study this problem for the setup of binary classification performed by an ensemble of base functions communicating real-valued confidence levels. We propose a noise-mitigation solution that optimizes the transmission gains and aggregation coefficients of the base functions. Toward that, we formulate a post-training gradient-based optimization algorithm that minimizes the error probability given the training dataset and the noise parameters. We further derive lower and upper bounds on the optimized error probability, and show empirical results that demonstrate the enhanced performance achieved by our approach on real data.

We address the design of inference-oriented communication systems where multiple transmitters send partial inference values through noisy communication channels, and the receiver aggregates these channel outputs to obtain a reliable final inference. Since large data items are replaced by compact inference values, these systems lead to significant savings of communication resources. In particular, we present a principled framework to optimize communication-resource allocation for distributed boosting classifiers. Boosting classification algorithms make a final decision via a weighted vote from the outputs of multiple base classifiers. Since these base classifiers transmit their partial inference values over noisy channels, communication errors would degrade the final classification accuracy. We formulate communication resource allocation problems to maximize the final classification accuracy by taking into account the importance of base classifiers and the resource budget. To solve these problems rigorously, we formulate convex optimization problems to optimize: 1) transmit-power allocations and 2) transmit-rate allocations. This framework departs from classical communication-systems optimizations in seeking to maximize the classification accuracy rather than the reliability of the individual communicated bits. Results from numerical experiments demonstrate the benefits of our approach.

The min-entropy is a widely used metric to quantify the randomness of generated random numbers, which measures the difficulty of guessing the most likely output. It is difficult to accurately estimate the min-entropy of a non-independent and identically distributed (non-IID) source. Hence, NIST Special Publication (SP) 800-90B adopts ten different min-entropy estimators and then conservatively selects the minimum value among ten min-entropy estimates. Among these estimators, the longest repeated substring (LRS) estimator estimates the collision entropy instead of the min-entropy by counting the number of repeated substrings. Since the collision entropy is an upper bound on the min-entropy, the LRS estimator inherently providesoverestimatedoutputs. In this paper, we propose two techniques to estimate the min-entropy of a non-IID source accurately. The first technique resolves the overestimation problem by translating the collision entropy into the min-entropy. Next, we generalize the LRS estimator by adopting the general Rényi entropy instead of the collision entropy (i.e., Rényi entropy of order two). We show that adopting a higher order can reduce the variance of min-entropy estimates. By integrating these techniques, we propose a generalized LRS estimator that effectively resolves the overestimation problem and provides stable min-entropy estimates. Theoretical analysis and empirical results support that the proposed generalized LRS estimator improves the estimation accuracy significantly, which makes it an appealing alternative to the LRS estimator.

In data-intensive applications, it is advantageous to perform some partial processing close to the data, and communicate to a central processor the partial results instead of the data itself. When the communication medium is noisy, one must mitigate the resulting degradation in computation quality. We study this problem for the setup of binary classification performed by an ensemble of functions communicating real-valued confidence levels. We propose a noise-mitigation solution that works by optimizing the aggregation coefficients at the central processor. Toward that, we formulate a post-training gradient algorithm that minimizes the error probability given the dataset and the noise parameters. We further derive lower and upper bounds on the optimized error probability, and show empirical results that demonstrate the enhanced performance achieved by our scheme on real data.

We address the problem of compressing genomic read data produced by modern shotgun sequencing technologies, where a reference genome, closely similar to the sequenced one, is available only at the decoder. This problem, addressed by distributed source coding techniques, requires an alignment and validation layer in the decoder. In this work, we extend a previous work, to allow a single deletion along with the previously addressed multiple substitutions. The results include a new distance for efficient alignment under deletion and substitutions, a derivation of the exact distribution of this distance on random sequences, as well as procedures to recover the read from multiple invocations of a substitutions-only decoder.

The min-entropy is a widely used metric to quantify the randomness of generated random numbers, which measures the difficulty of guessing the most likely output. It is difficult to accurately estimate the min-entropy of a non-independent and identically distributed (non-IID) source. Hence, NIST Special Publication (SP) 800-90B adopts ten different min-entropy estimators and then conservatively selects the minimum value among ten min-entropy estimates. Among these estimators, the longest repeated substring (LRS) estimator estimates the collision entropy instead of the min-entropy by counting the number of repeated substrings. Since the collision entropy is an upper bound on the min-entropy, the LRS estimator inherently provides overestimated outputs. In this paper, we propose two techniques to estimate the min-entropy of a non-IID source accurately. The first technique resolves the overestimation problem by translating the collision entropy into the min-entropy. Next, we generalize the LRS estimator by adopting the general Rényi entropy instead of the collision entropy (i.e., Rényi entropy of order two). We show that adopting a higher order can reduce the variance of min-entropy estimates. By integrating these techniques, we propose a generalized LRS estimator that effectively resolves the overestimation problem and provides stable min-entropy estimates. Theoretical analysis and empirical results support that the proposed generalized LRS estimator improves the estimation accuracy significantly, which makes it an appealing alternative to the current-standard LRS estimator.

Magnetic random-access memory (MRAM) is a promising memory technology due to its high density, non-volatility, and high endurance. However, achieving high memory fidelity incurs high write-energy costs, which should be reduced for large-scale deployment of MRAMs. In this paper, we formulate abiconvexoptimization problem to optimize write fidelity given energy and latency constraints. The basic idea is to allocate non-uniform write pulses depending on the importance of each bit position. The fidelity measure we consider is mean squared error (MSE), for which we optimize write pulses via alternating convex search (ACS). We derive analytic solutions and propose analternating water-fillingalgorithm by casting the MRAM’s write operation as communication over parallel channels. Hence, the proposed alternating water-filling algorithm is computationally more efficient than the original ACS while their solutions are identical. Since the formulated biconvex problem is non-convex, both the original ACS and the proposed algorithm do not guarantee global optimality. However, the MSEs obtained by the proposed algorithm are comparable to the MSEs by complicated global nonlinear programming solvers. Furthermore, we prove that our algorithm can reduce the MSE exponentially with the number of bits per word. For an 8-bit accessed word, the proposed algorithm reduces the MSE by a factor of 21. We also evaluate MNIST dataset classification supposing that the model parameters of deep neural networks are stored in MRAMs. The numerical results show that the optimized write pulses can achieve 40% write-energy reduction for the same classification accuracy.

We study spatially coupled LDPC codes that allow access to sub-blocks much smaller than the full code block. Sub-block access is realized by a semi-global decoder that decodes a chosen target sub-block by only accessing the target, plus a prescribed number of helper sub-blocks adjacent in the code chain. This paper develops a theoretical methodology for analyzing the semi-global decoding performance of spatially coupled LDPC codes constructed from protographs. The main result shows that semi-global decoding thresholds can be derived from certain thresholds we define for the single-sub-block graph. These characterizing thresholds are also used for deriving lower bounds on the decoder’s performance over channels with variability across sub-blocks, which are motivated by applications in data storage.

This paper studies coding on channels with the barrier property: only errors to and from a special barrier state are possible. This model is motivated by storage media that have heterogeneous state structure, not admitting the usual multi-bit scaling of the representation states. Our contributions include derivation of the channel capacity, efficient maximum-likelihood and list decoding algorithms, and finite-block-length analysis using random codes. This work is the first that addresses a barrier channel with separate parameters for the transitions into and out of the barrier state. Earlier work addressed special-case single-parameter models, and focused primarily on the worst-case coding performance.

Boosting is a well-known method in machine learning for combining multiple weak classifiers into one strong classifier. When used in distributed setting, accuracy is hurt by classifiers that flip or straggle due to communication and/or computation unreliability. While unreliability in the form of noisy data is well-treated by the boosting literature, the unreliability of the classifier outputs has not been explicitly addressed. Protecting the classifier outputs with an error/erasure-correcting code requires reliable encoding of multiple classifier outputs, which is not feasible in common distributed settings. In this paper we address the problem of training boosted classifiers subject to straggling or flips at classification time. We propose two approaches: one based on minimizing the usual exponential loss but in expectation over the classifier errors, and one by defining and minimizing a new worst-case loss for a specified bound on the number of unreliable classifiers.

In this paper we present a new compression scheme for genomic read data produced by modern sequencing technologies. In this setting, a reference genome similar to the one being sequenced is available only at the decoder, while the starting index of each read in this reference in unknown. The proposed scheme significantly reduces the encoding complexity relative to known reference-based compression schemes. The results include a code construction based on generalized concatenation coset codes, analysis of the decoding failure probability, and optimization of the scheme parameters for minimal compression rate.

In a distributed information application an encoder compresses an arbitrary vector while a similar reference vector is available to the decoder as side information. For the Hamming-distance similarity measure, and when guaranteed perfect reconstruction is required, we present two contributions to the solution of this problem. One result shows that when a set of potential reference vectors is available to the encoder, lower compression rates can be achieved when the set satisfies a certain clustering property. Another result reduces the best known decoding complexity from exponential in the vector length$n$to$O(n^{1.5})$by generalized concatenation of inner coset codes and outer error-correcting codes. One potential application of the results is the compression of DNA sequences, where similar (but not identical) reference vectors are shared among senders and receivers.

This paper presents a new erasure code called Treeplication designed for distributed recovery of the full information word, while most prior work in coding for distributed storage only supports distributed repair of individual symbols. A Treeplication code for k information symbols is defined on a binary tree with 2k-1 vertices, along with a distribution for selecting code symbols from the tree layers. We analyze and optimize the code under a random-multiset model, which captures the system property that the nodes available for recovery are drawn randomly from the nodes storing the code symbols. Treeplication codes are shown to have full-recovery communication-cost comparable to replication, while offering much better recoverability.

A new type of spatially coupled low-density parity-check (SC-LDPC) codes motivated by practical storage applications is presented. SC-LDPCL codes (suffix `L' stands for locality) can be decoded locally at the level of sub-blocks that are much smaller than the full code block, thus offering flexible access to the coded information alongside the strong reliability of the global full-block decoding. Toward that, we propose constructions of SC-LDPCL codes that allow controlling the trade-off between local and global correction performance. In addition to local and global decoding, the paper develops a density-evolution analysis for a decoding mode we call semi-global decoding, in which the decoder has access to the requested sub-block plus a prescribed number of sub-blocks around it. SC-LDPCL codes are also studied under a channel model with variability across sub-blocks, for which decoding-performance lower bounds are derived.

A new approach for designing bilayer and multi-layer LDPC codes is proposed and studied in the asymptotic regime. The ensembles are defined through individual uni-variate degree distributions, one for each layer. We present a construction that: 1) enables low-complexity decoding for high-SNR channel instances, 2) provably approaches capacity for low-SNR instances, 3) scales linearly (in terms of design complexity) in the number of layers. For the setup where decoding the second layer is significantly more costly than the first layer, we propose an optimal-cost decoding schedule and study the trade-off between code rate and decoding cost.

Magnetic random-access memory (MRAM) is a promising memory technology due to its high density, non-volatility, and high endurance. However, achieving high memory fidelity incurs significant write-energy costs, which should be reduced for the large-scale deployment of MRAMs. In this paper, we formulate an optimization problem to maximize the memory fidelity given energy constraints, and propose a biconvex optimization approach to solve it. The basic idea is to allocate non-uniform write pulses depending on the importance of each bit position. We consider the mean squared error (MSE) as a fidelity metric and propose an iterative water-filling algorithm to minimize the MSE. Although the iterative algorithm does not guarantee the global optimality, we can choose a proper starting point that decreases the MSE exponentially and guarantees fast convergence. For an 8-bit accessed word, the proposed algorithm reduces the MSE by a factor of 21.

SC-LDPC codes with sub-block locality can be decoded locally at the level of sub-blocks that are much smaller than the full code block, thus providing fast access to the coded information. The same code can also be decoded globally using the entire code block, for increased data reliability. In this paper, we pursue the analysis and design of such codes from both finite-length and asymptotic lenses. This mixed approach has rarely been applied in designing SC codes, but it is beneficial for optimizing code graphs for local and global performance simultaneously. Our proposed framework consists of two steps: 1) designing the local code for both threshold and cycle counts, and 2) designing the coupling of local codes for the best cycle count in the global design.

Refresh is an important operation to prevent loss of data in dynamic random-access memory (DRAM). However, frequent refresh operations incur considerable power consumption and degrade system performance. Refresh power cost is especially significant in high-capacity memory devices and battery-powered edge/mobile applications. In this paper, we propose a principled approach to optimizing the refresh power allocation. Given a model for the bit error rate dependence on power, we formulate a convex optimization problem to minimize the word mean squared error for a refresh power constraint; hence we can guarantee the optimality of the obtained refresh power allocations. In addition, we provide an integer programming problem to optimize the discrete refresh interval assignments. For an 8-bit accessed word, numerical results show that the optimized nonuniform refresh intervals reduce the refresh power by 29% at a peak signal-to-noise ratio of 50dB compared to the uniform assignment.

We study a new decoding strategy of multi-block SC-LDPC codes motivated by data-storage applications. To decode a sub-block out of the full code block, our proposed decoder accesses a small number of sub-blocks around the desired sub-block. We call this decoding strategy "semi-global decoding", and parametrize it by its access cost: the number of accessed sub-blocks. We provide a theoretical characterization of decoding performance, and evaluate this performance for random-access SC-LDPC ensembles.

Resistive memory is a promising technology for achieving unprecedented storage densities and new in-memory computing features. However, to fulfill their promise, resistive memories require array architectures suffering from a severe interference effect called “sneak paths.” In this paper, we address the sneak-path problem through a communication-theory framework. Starting from the fundamental problem of readout with parallel-resistance interference, we develop several tools for detection and coding that significantly improve memory reliability. For the detection problem, we formulate and derive the optimal detector for a realistic array model, and then propose simplifications that enjoy similarly good performance and simpler implementation. Complementing detection for better error rates is done by a new coding scheme that shapes the stored bits to get lower sneak-path incidence. For the same storage rates, the new coding scheme exhibits error rates lower by an order of magnitude compared to known shaping techniques.

In this paper, we introduce a new channel model termed as the q-ary multi-bit channel. This channel models a memory device, where q-ary symbols (q = 2s) are stored in the form of current/voltage levels. The symbols are read in a measurement process, which provides a symbol bit in each measurement step, starting from the most significant bit. An error event occurs when not all the symbol bits are known. To deal with such error events, we use GF(q) lowdensity parity-check (LDPC) codes and analyze their decoding performance. We start with iterative-decoding threshold analysis and derive optimal edge-label distributions for maximizing the decoding threshold. We later move to a finite-length iterative decoding analysis and propose an edge-labeling algorithm for the improved decoding performance. We then provide a finite-length maximum-likelihood decoding analysis for both the standard non-binary random ensemble and LDPC ensembles. Finally, we demonstrate by simulations that the proposed edge-labeling algorithm improves the finite-length decoding performance by orders of magnitude.

We construct error-correcting write-once memory (WOM) codes that guarantee correction of any specified number of errors in q-level memories. The constructions use suitably designed short q-ary WOM codes and concatenate them with outer error-correcting codes over different alphabets using suitably designed mappings. With a new storage-efficiency measure, we call EC-rate and show that for common error types the codes save redundancy and implementation complexity over straightforward concatenation. In addition to constructions for guaranteed error correction, we extend the error-correcting WOM scheme to binary multi-level coding for random errors, and toward soft-decision decoding provide an efficient way to extract reliability information without using higher-precision readout.

This paper presents a theoretical study of a new type of LDPC codes that is highly motivated by practical storage applications. LDPCL codes (suffix L represents locality) are LDPC codes that can be decoded either as usual over the full code block, or locally when a smaller sub-block is accessed (to reduce latency). LDPCL codes are designed to maximize the error-correction performance vs. rate in the usual (global) mode, while at the same time providing a certain performance in the local mode. We develop a theoretical framework for the design of LDPCL codes over the binary erasure channel. Our results include generalizing the density-evolution analysis to two dimensions, proving the existence of a decoding threshold and showing how to compute it, and constructing capacity-achieving sequences for any pair of local and global thresholds. Proofs and more results are made available at the arXiv (http://arxiv.org/abs/1801.03951).

Recent advances in coding for distributed storage systems have reignited the interest in scalar codes over extension fields. In parallel, the rise of large-scale distributed systems has motivated the study of computing in the presence of stragglers, i.e., servers that are slow to respond or unavailable. This paper addresses storage systems that employ linear codes over extension fields. A common task in such systems is the reconstruction of the entire dataset using sequential symbol transmissions from multiple servers, which are received concurrently at a central data collector. However, a key bottleneck in the reconstruction process is the possible presence of stragglers, which may result in excessive latency. To mitigate the straggler effect, the reconstruction should be possible given any sufficiently large set of sequentially received symbols, regardless of their source. In what follows, an algebraic framework for this scenario is given, and a number of explicit constructions are provided. Our main result is a construction that uses a recursive composition of generalized Reed-Solomon codes over smaller fields. In addition, we show links of this problem to Gabidulin codes and to universally decodable matrices.

We construct error-correcting WOM (write-once memory) codes that can correct any specified number of errors in q-Ievel memories. The constructions use suitably designed short q-ary WOM codes and concatenate them with outer error-correcting codes over different alphabets, using suitably designed mappings. With a new storage-efficiency measure we call EC-rate, we show that for common error types the codes save redundancy and implementation complexity over straightforward concatenation.

This paper presents a new erasure code called Treeplication which features the benefits of both coding and replication. A Treeplication code for k data fragments is defined on a binary tree with 2k-1 vertices, along with a distribution for selecting code fragments from the tree layers. The tree structure allows to optimize the recoverability of random subsets of code fragments, while at the same time behaving similarly to replication in recovering individual data fragments. The significant performance advantages over both replication and existing erasure codes motivate the use of Treeplication in decentralized distributed storage systems.

Switch codes, first proposed by Wang et al., are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch is required to write n incoming packets and read k outgoing packets while using m memory banks, each able to write and read one packet per time unit. Each set of n packets written to the switch simultaneously is called a generation. The objective is to store the packets in the banks such that every request of k packets, which can belong to previous generations, can be handled by reading at most one packet from every bank. In this paper, we study a new type of switch codes that can simultaneously deliver large packet request and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. For this new request model, we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. For binary codes, we also study an intermediate model in which a coded packet is formed by the XOR operations of at most two input packets. We present several code constructions and prove the optimality of one family of these codes by providing the corresponding lower bound. Finally, we introduce a construction of conventional switch codes, which improves upon the best known results for the case n = k.

We present a constraint-coding scheme to correct asymmetric magnitude-1 errors in multi-level non-volatile memories. For large numbers of such errors, the scheme is shown to deliver better correction capability compared with known alternatives, while admitting low-complexity of decoding. Our results include an algebraic formulation of the constraint, necessary and sufficient conditions for correctability, a maximum-likelihood decoder running in complexity linear in the alphabet size, and upper bounds on the probability of failing to correct t errors. Besides the superior rate-correction tradeoff, another advantage of this scheme over standard error-correcting codes is the flexibility to vary the code parameters without significant modifications.

Data compression is a well-studied (and well-solved) problem in the setup of long coding blocks. But important emerging applications need to compress data to memory words of small fixed widths. This new setup is the subject of this paper. In the problem we consider, we have two sources with known discrete distributions, and we wish to find codes that maximize the success probability that the two source outputs are represented in L bits or less. A good practical use for this problem is a table with two-field entries that is stored in a memory of a fixed width L. Such tables of very large sizes are common in network switches/routers and in data-intensive machine-learning applications. After defining the problem formally, we solve it optimally with an efficient code-design algorithm. We also solve the problem in the more constrained case where a single code is used in both fields (to save space for storing code dictionaries). For both code-design problems we find decompositions that yield efficient dynamic-programming algorithms. With the help of an empirical study we show the success probabilities of the optimal codes for different distributions and memory widths. In particular, this paper demonstrates the superiority of the new codes over existing compression algorithms.

This paper studies the problem of reliable resistive-memory readout through the rigorous lens of communication theory. The most dominant reliability issue in resistive memory can be modeled as interference of resistances in parallel to a measured resistance. For this special type of interference we develop detection and coding schemes that are shown to effectively mitigate the effects of sneak-path errors. The uniqueness of this study is that the proposed models combine theoretical rigor with practical richness, hence enabling deep contributions to very real problems.

Fault Management (FM) is a cardinal feature in communication networks. One of the most common FM approaches is to use periodic keepalive messages. Hence, switches and routers are required to transmit a large number of FM messages periodically, requiring a hardware-based packet generator that periodically transmits a set of messages that are stored in an expensive on-chip memory. With the rapid growth of carrier networks, and as 5G technologies emerge, the number of users and the traffic rates are expected to significantly increase over the next few years. Consequently, we expect the on-chip memories used for FM to become a costly component in switch and router chips. We introduce a novel approach in which FM messages are stored in compressed form in the on-chip memory, allowing to significantly reduce the memory size. We present FM-Delta, a simple hardware-friendly delta encoding algorithm that allows FM messages to be compressed by a factor of 2.6. We show that this compression ratio is very close to the results of the zlib compression library, which requires much higher implementation complexity.

We define multi-block interleaved codes as codes that allow reading information from either a small sub-block or from a larger full block. The former offers faster access, while the latter provides better reliability. We specify the correction capability of the sub-block code through its gap t from optimal minimum distance, and look to have full-block minimum distance that grows with the parameter t. We construct two families of such codes when the number of sub-blocks is 3. The codes match the distance properties of known integrated-interleaving codes, but with the added feature of mapping the same number of information symbols to each sub-block. As such, they are the first codes that provide read access in multiple size granularities and correction capabilities.

In this paper, we address the finite-length decoding performance of LDPC codes over the q-ary multi-bit channel (QMBC). The QMBC is defined over the full q-ary symbols, while addressing the differences in reliability between the bits composing the symbols. We show that unlike the binary erasure channel, the QMBC iterative decoder does not necessarily halt at stopping sets. Instead, its performance depends on the edge-label configuration of the LDPC code graph. We characterize good edge-label configurations, and propose an edge-labeling algorithm for improved iterative-decoding performance. We then provide finite-length maximum-likelihood decoding analysis for both the standard non-binary random ensemble and LDPC ensembles. Finally, simulations are presented to demonstrate the advantages of the proposed edge-labeling algorithm.

Data compression is a well-studied (and well-solved) problem in the setup of long coding blocks. But important emerging applications need to compress data to memory words of small fixed widths. This new setup is the subject of this paper. In the problem we consider we have a source with a known discrete distribution, and we wish to find a code that maximizes the success probability that two source instances can be represented together in L bits or less. A good practical use for this problem is a table with two-element entries that is stored in a memory of a fixed width L. Such tables of very large sizes are used in data-intensive computing applications. We solve the problem by efficiently finding an optimal code that uses a dictionary of linear size in the number of source elements.

Every bit of information in a storage or memory device is bound by a multitude of performance specifications, and is subject to a variety of reliability impediments. At the other end, the physical processes tamed to remember our bits offer a constant source of risk to their reliability. These include a variety of noise sources, access restrictions, intercell interferences, cell variabilities, and many more issues. Tying together this vector of performance figures with that vector of reliability issues is a rich matrix of emerging coding tools and techniques. Channel coding schemes ensure target reliability and performance and have been at the core of memory systems since their nascent age. In this survey, we first overview the fundamentals of channel coding and summarize well-known codes that have been used in nonvolatile memories (NVMs). Next, we demonstrate why the conventional coding approaches ubiquitously based on symmetric channel models and optimization for the Hamming metric fail to address the needs of modern memories. We then discuss several recently proposed innovative coding schemes. Behind each coding scheme lies an interesting theoretical framework, building on deep ideas from mathematics and the information sciences. We also survey some of the most fascinating bridges between deep theory and storage performance. While the focus of this survey is primarily on the pervasive multilevel NAND Flash, we envision that other benefiting memory technologies will include phase change memory, resistive memories, and others.

The objective of low-delay codes is to protect communication streams from erasure bursts by minimizing the time between the packet erasure and its reconstruction. Previous work has concentrated on the constant-delay scenario, where all erased packets need to exhibit the same decoding delay. We consider the case of heterogeneous delay, where the objective is to minimize the average delay across the erased packets in a burst. We derive delay lower bounds for the average case, and show that they match the constant-delay bounds only at a single rate point R = 0.5. We then construct codes with optimal average delays for the entire range of code rates. The construction for rates R ≤ 0.5 achieves optimality for every erasure instance, while the construction for rates R > 0.5 is optimal for a (1- R)/R fraction of all burst instances and close to optimal for the remaining fraction. The paper also studies the benefits of delay heterogeneity within the application of sensor communications. It is shown that a carefully designed code can significantly improve the temporal precision at the receiving node following erasure-burst events.

Network switches and routers scale in rate by distributing the packet read/write operations across multiple memory banks. Rate scaling is achieved so long as sufficiently many packets can be written and read in parallel. However, due to the non-determinism of the read process, parallel pending read requests may contend on memory banks, and thus significantly lower the switching rate. In this paper, we provide a constructive study of codes that guarantee fully parallel data reconstruction without contention. We call these codes “switch codes,” and construct three optimal switch-code families with different parameters. All the constructions use only simple XOR-based encoding and decoding operations, an important advantage when operated in ultra-high speeds. Switch codes achieve their good performance by spanning simultaneous disjoint local-decoding sets for all their information symbols. Switch codes may be regarded as an extreme version of the previously studied batch codes, where the switch version requires parallel reconstruction of all the information symbols.

Network switches and routers need to serve packet writes and reads at rates that challenge the most advanced memory technologies. As a result, scaling the switching rates is commonly done by parallelizing the packet I/Os using multiple memory units. For improved read rates, packets can be coded upon write, thus giving more flexibility at read time to achieve higher utilization of the memory units. This paper presents a detailed study of coded network switches, and in particular, how to design them to maximize the throughput advantages over standard uncoded switches. Toward that objective, the paper contributes a variety of algorithmic and analytical tools to improve and evaluate the throughput performance. The most interesting finding of this paper is that the placement of packets in the switch memory is the key to both high performance and algorithmic efficiency. One particular placement policy we call “design placement” is shown to enjoy the best combination of throughput performance and implementation feasibility.

Switch codes, first proposed by Wang et al., are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch consists of n input ports, k output ports, and m banks which store new arriving packets from the input ports in each time slot, called a generation. The objective is to store the packets in the banks such that every request of k packets by the output ports, which can be from previous generations, can be handled by reading at most one packet from every bank. In this paper we study a new type of switch codes that can simultaneously deliver large symbol requests and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. For this new request model we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. We present several code constructions and prove the optimality of one family of these codes by providing the corresponding lower bound. Lastly, we introduce a construction of switch codes for the case n = k, which improves upon the best known results for this case.

We study the problem of write disturbs due to write sneak paths in memristor crossbar arrays. A write sneak path is a bit configuration in the array that causes a write of one cell to undesirably flip the value of another cell. We study the configurations that cause such write sneak paths, and characterize them in terms of tight constraints to prevent them. We show that thanks to the flexibility to choose the write order, the resulting constraints are milder compared to known similar ones for read sneak paths. In addition, we derive the array constraints when parallel write is allowed in the rows or column only, and in both the rows and columns.

Coded switches write incoming packets with redundancy to increase the flexibility to read them later without contention. An important question pertaining to coded switches is what policy to follow when placing the coded packets in the switch memory. We study this question by proposing two such placement policies: cyclic placement and (block-) design placement. We show that these policies offer many advantages in switching throughput, algorithmic efficiency, and analysis amenability.

In recent years, due to the spread of multi-level nonvolatile memories (NVM), q-ary write-once memories (WOM) codes have been extensively studied. By using WOM codes, it is possible to rewrite NVMs t times before erasing the cells. The use of WOM codes enables to improve the performance of the storage device, however, it may also increase errors caused by inter-cell interference (ICI). This work presents WOM codes that restrict the imbalance between code symbols throughout the write sequence, hence decreasing ICI. We first specify the imbalance model as a bound d on the difference between codeword levels. Then a 2-cell code construction for general q and input size is proposed. An upper bound on the write count is also derived, showing the optimality of the proposed construction. The new codes are also shown to be competitive with known codes not adhering to the bounded imbalance constraint.

We study the inherent space requirements of reliable storage algorithms in asynchronous distributed systems. A number of recent works have used codes in order to achieve a better storage cost than the well-known replication approach. However, a closer look reveals that they incur extra costs in certain scenarios. Specifically, if multiple clients access the storage concurrently, then existing asynchronous code-based algorithms may store a number of copies of the data that grows linearly with the number of concurrent clients. We prove here that this is inherent. Given three parameters, (1) the data size -- D bits, (2) the concurrency level -- c, and (3) the number of storage node failures that need to be tolerated -- f, we show a lower bound of Omega(min(f,c)D) bits on the space complexity of asynchronous distributed storage algorithms. Intuitively, this implies that the asymptotic storage cost is either as high as with replication, namely O(fD), or as high under concurrency as with the aforementioned code-based algorithms, i.e., O(cD).

With the increasing demand for network bandwidth, network switches face the challenge of serving growing data rates. To parallelize the process of writing and reading packets to the switch memory, multiple memory units (MUs) are deployed in parallel in the switch fabric. However, memory contention may occur if packets requested to read happen to share one or more MUs, due to memory bandwidth limitations. Avoiding such contention in the write stage is limited as the reading schedule of packets is not known upon arrival of the packets to the switch. Thus, efficient packet placement and read policies are required.

In recent years, due to the spread of multi-level nonvolatile memories (NVMs), q-ary write-once memory (WOM) codes have been extensively studied. By using WOM codes, it is possible to rewrite NVMs t times before erasing the cells. Use of WOM codes enables the improvement of the performance of the storage device; however, it may also increase errors caused by inter-cell interference (ICI). This paper presents WOM codes that restrict the imbalance between code symbols throughout the write sequence, hence decreasing ICI. We first specify the imbalance model as a bound d on the difference between codeword levels. Then, a two-cell code construction for general q and input size is proposed. An upper bound on the write count is also derived, showing the optimality of the proposed construction. In addition to direct WOM constructions, we derive closed form optimal write regions for codes constructed with continuous lattices. On the coding side, the proposed codes are shown to be competitive with known codes not adhering to the bounded imbalance constraint. On the memory side, we show how the codes can be deployed within flash wordlines, and quantify their bit-error rate advantage using accepted ICI models.

In a memristor crossbar array, functioning as a memory array, a memristor is positioned on each row-column intersection, and its resistance, low or high, represents two logical states. The state of every memristor can be sensed by the current flowing through the memristor. In this paper, we study the sneak path problem in crossbar arrays, in which current can sneak through other cells, resulting in reading a wrong state of the memristor. Our main contributions are modeling the error channel induced by sneak paths, a new characterization of arrays free of sneak paths, and efficient methods to read the array cells while avoiding sneak paths. To each read method, we match a constraint on the array content that guarantees sneak-path free readout, determine the resulting capacity, and provide an efficient encoder that achieves the capacity.

In this paper, we develop a new channel model, which we name the q-ary partial erasure channel (QPEC). The QPEC has a q-ary input, and its output is either the input symbol or a set of M (2 ≤ M ≤ q) symbols, containing the input symbol. This channel serves as a generalization to the binary erasure channel and mimics situations when a symbol output from the channel is known only partially; that is, the output symbol contains some ambiguity, but is not fully erased. This type of channel is motivated by non-volatile memory multi-level read channels. In such channels, the readout is obtained by a sequence of current/voltage measurements, which may terminate with a partial knowledge of the stored level. Our investigation is concentrated on the performance of low-density parity-check (LDPC) codes when used over this channel, thanks to their low decoding complexity using belief propagation. We provide the exact QPEC density-evolution equations that govern the decoding process, and suggest a cardinality-based approximation as a proxy. We then provide several bounds and approximations on the proxy density evolutions, and verify their tightness through numerical experiments. Finally, we provide tools for the practical design of LDPC codes for use over the QPEC.

One key requirement for fountain (rateless) coding schemes is to achieve a high intermediate symbol recovery rate. Recent coding schemes have incorporated the use of a feedback channel to improve the intermediate performance of traditional rateless codes; however, these codes with feedback are designed based on uniformly at random selection of input symbols. In this paper, on the other hand, we develop feedback-based fountain codes with dynamically adjusted nonuniform symbol selection distributions, and show that this characteristic can enhance the intermediate decoding rate. We provide an analysis of our codes, including bounds on computational complexity and failure probability for a maximum likelihood decoder; the latter is tighter than bounds known for classical rateless codes. Through numerical simulations, we also show that the feedback information paired with a nonuniform selection distribution can highly improve the symbol recovery rate, and that the amount of feedback sent can be tuned to the specific transmission properties of a given feedback channel.

This paper proposes a general optimization framework to allocate computing resources to the compression of massive and heterogeneous data sets incident upon a communication or storage system. The framework is formulated using abstract parameters, and builds on rigorous tools from optimization theory. The outcome is a set of algorithms that together can reach optimal compression allocation in a realistic scenario involving a multitude of content types and compression tools. This claim is demonstrated by running the optimization algorithms on publicly available data sets, and showing up to 25% size reduction, with equal compute-time budget using standard compression tools.

Wireless communication systems, such as RFIDs and wireless sensor networks, are increasingly being used in security-sensitive applications, e.g. credit card transactions or monitoring patient health in hospitals. Wireless jamming by transmitting artificial noise, which is traditionally used as an offensive technique for disrupting communication, has recently been explored as a means of protecting sensitive communication from eavesdroppers.

The objective of low-delay codes is to protect communication streams from erasure bursts by minimizing the time between the packet erasure and its reconstruction. Previous work has concentrated on the constant-delay scenario, where all erased packets need to exhibit the same decoding delay. We consider the case of heterogeneous delay, where the objective is to minimize the average delay across the erased packets in a burst. We derive delay lower bounds for the average case, and show that they match the constant-delay bounds only at a single rate point 0.5. We then construct codes with optimal average delays for the entire range of code rates. The construction for rates under 0.5 achieves optimality for every erasure instance, while the construction for rates above 0.5 is optimal for an infinite number, but not all, of the erasure instances.

This paper develops a framework to calculate Hamming similarity between vectors stored in resistive memory. A single-parameter model is proposed for the resistive measurement channel, which is then used to analytically reveal an interesting tradeoff between this parameter and succeeding in the calculation task. We suggest coding techniques that can improve this tradeoff under natural usage assumptions. The proposed constructions work to change the Hamming weight of the stored vectors without corrupting the Hamming distance between pairs of vectors.

Network switches and routers need to serve packet writes and reads at rates that challenge the most advanced memory technologies. As a result, scaling the switching rates is commonly done by parallelizing the packet I/Os using multiple memory units. For improved read rates, packets can be coded with an [n,k] MDS code, thus giving more flexibility at read time to achieve higher utilization of the memory units. In the paper, we study the usage of [n,k] MDS codes in a switching environment. In particular, we study the algorithmic problem of maximizing the instantaneous read rate given a set of packet requests and the current layout of the coded packets in memory. The most interesting results from practical standpoint show how the complexity of reaching optimal read rate depends strongly on the writing policy of the coded packets.

We present a constraint-coding scheme to correct large numbers of asymmetric magnitude-1 errors in multi-level non-volatile memories. The scheme is shown to deliver better correction capability compared to known alternatives, while admitting low-complexity of decoding. Our results include an algebraic formulation of the constraint, necessary and sufficient conditions for correctability, a maximum-likelihood decoder running in complexity linear in the alphabet size, and lower bounds on the probability to correct t errors. Besides the superior rate-correction tradeoff, another advantage of this scheme over standard error-correcting codes is the flexibility to vary the code parameters without significant modifications.

In this paper, we study a construction of binary switch codes. A switch code is a code such that a multi-set request of information symbols can be simultaneously recovered from disjoint sets of codeword symbols. Our construction is optimal in the sense that it has the smallest codeword length given its average encoding degree, which is logarithmic in the code dimension. Moreover, the number of queries needed to recover any information symbol in the request is at most 2. As a result, our construction is the first family of switch codes with low encoding and decoding complexity.

In this paper, we discuss practical design of low-density parity-check (LDPC) codes for the q-ary partial erasure channel (QPEC). This channel is an extension of the binary erasure channel (BEC), where partial information on the output is available. We provide a linear programming (LP) optimization for the design of good degree distributions, and compare our code design results to codes obtained using an LP optimization formulated for the BEC. We show superior performance in terms of code rate and complexity, when designing an LDPC code for a desired decoding threshold.

Security-sensitive applications, such as patient health monitoring and credit card transactions, are increasingly utilizing wireless communication systems, RFIDs, wireless sensor networks, and other wireless communication systems. The use of interference-emitting jammers to protect these sensitive communications has been recently explored in the literature, and has shown high potential. In this paper we consider optimization problems relating to the temporal distributions of jammers' activity, and the suitable coding regimes used for communication. Solving the joint problem optimally enables comprehensive security in space, at a low power consumption and low communication overhead. The joint optimization of jamming in space and time is driven by a new framework that uses the bit-error probability as a measure of communication quality. Under this framework, we show how to guarantee information-theoretic security within a geographic region, and with increased flexibility to tailor the coding regime to the problem's geometry. We present efficient algorithms for different settings, and provide simulations for various scenarios using the bit-error probability functions. These simulations demonstrate the efficiency of the scheme. We believe that our scheme can lead to practical, economical and scalable solutions for providing another layer of protection of sensitive data, in cases where encryption schemes are limited or impractical.

We present here a synopsis of a keynote presentation given by Idit Keidar at OPODIS 2015, the International Conference on Principles of Distributed Systems, which took place in Rennes, France, on December 14-17 2015.

Multi-level memory cells are used in non-volatile memories to increase the storage density. Using multi-level cells, however, imposes lower read and write speeds, limiting their usability with high-performing applications. In this work we study the tradeoff between storage density and write/read speeds using codes. The contributions are codes that give high-performance write and read processes with minimal reduction in storage density. We describe the codes, give a detailed analytical treatment of their information rate and speed, provide encoding/decoding algorithms, and compare them with more basic access schemes and upper bounds. Using performance coding enables accessing the memory with variable access speeds, thus creating heterogenous storage devices serving a variety of applications with improved efficiency.

An online fountain code is defined as a fountain code for which an optimal encoding strategy can be found efficiently given any instantaneous decoding state. This property is important for data distribution in practical networks. In this paper, we formalize the problem of online fountain code construction, and propose new online fountain codes that outperform known ones in having factor 3-5 lower redundancy overhead. The bounding of the code overhead is carried out using the analysis of the dynamics of random-graph processes.

In this paper, we develop a new channel model, which we name the q-ary partial erasure channel (QPEC). QPEC has a q-ary input, and its output is either one symbol or a set of M possible values. This channel mimics situations when current/voltage levels in measurement channels are only partially known, due to high read rates or imperfect current/voltage sensing. Our investigation is concentrated on the performance of low-density parity-check (LDPC) codes when used over this channel, due to their low decoding complexity with iterative-decoding algorithms. We give the density evolution equations of this channel, and develop its decoding-threshold analysis. Part of the analysis shows that finding the exact decoding threshold efficiently lies upon a solution to an open problem in additive combinatorics. For this part, we give bounds and approximations.

Multi-level memory cells are used in non-volatile memories in order to increase the storage density. Using multi-level cells, however, imposes higher read and write latencies limiting high speed applications. In this work we study the tradeoff between storage density and write/read performance using codes. The contributions are codes that give high-performance write and read processes with minimal reduction in storage density. We describe the codes, give an analytical treatment of their information rate and speed, and compare them with more basic access schemes and upper bounds.

Multi-write codes hold great promise to reduce write amplification in flash-based storage devices. In this work we propose two novel mapping architectures that show clear advantage over known schemes using multi-write codes, and over schemes not using such codes. We demonstrate the advantage of the proposed architectures by evaluating them with industry-accepted benchmark traces. The results show write amplification savings of double-digit percentages, for as low as 10% over-provisioning. In addition to showing the superiority of the new architectures on real-world workloads, the paper includes a study of the write-amplification performance on synthetically-generated workloads with time locality. In addition, some analytical insight is provided to assist the deployment of the architectures in real storage devices with varying device parameters.

For an array of memory cells that are read by threshold measurements, we ask the question of how to choose the measurements in the read sequence to minimize the number of measurements before the array is fully read. We propose and study analytically and experimentally various adaptive read algorithms, and provide corresponding lower bounds on the average number of measurements. We show that new two-dimensional read algorithms improve over the best one-dimensional ones. We further adapt the read algorithms to the case where the cell levels are not uniformly distributed, as motivated by partially-erased memory arrays.

With the rise of datacenter virtualization, the number of entries in the forwarding tables of datacenter switches is expected to scale from several thousands to several millions. Unfortunately, such forwarding table sizes would not fit on-chip memory using current implementations. In this paper, we investigate the compressibility of forwarding tables. We first introduce a novel forwarding table architecture with separate encoding in each column. It is designed to keep supporting fast random accesses and fixed-width memory words. Then, we show that although finding the optimal encoding is NP-hard, we can suggest an encoding whose memory requirement per row entry is guaranteed to be within a small additive constant of the optimum. Next, we analyze the common case of two-column forwarding tables, and show that such tables can be presented as bipartite graphs. We deduce graph-theoretical bounds on the encoding size. We also introduce an algorithm for optimal conditional encoding of the second column given an encoding of the first one. In addition, we explain how our architecture can handle table updates. Last, we evaluate our suggested encoding techniques on synthetic forwarding tables as well as on real-life tables.

Binary codes over 2D arrays are very useful in data storage, where each array column represents a storage device or unit that may suffer failure. In this paper, we propose a new framework for probabilistic construction of codes on 2D arrays. Instead of a pure combinatorial erasure model used in traditional array codes, we propose a mixed combinatorial-probabilistic model of limiting the number of column failures, and assuming a binary erasure channel in each failing column. For this model, we give code constructions and detailed analysis that allow sustaining a large number of column failures with graceful degradation in the fraction of erasures correctable in failing columns. Another advantage of the new framework is that it uses low-complexity iterative decoding. The key component in the analysis of the new codes is to analyze the decoding graphs induced by the failed columns, and infer the decoding performance as a function of the code design parameters, as well as the array size and failure parameters. A particularly interesting class of codes, called probabilistically maximum distance separable (MDS) array codes, gives fault-tolerance that is equivalent to traditional MDS array codes. The results also include a proof that the 2D codes outperform standard 1D low-density parity-check codes.

To the body of works on rewrite codes for constrained memories, we add a comprehensive study in a direction that is especially relevant to practical storage. The subject of this paper is codes for the q-ary extension of the write-once memories model, with input sizes that are fixed throughout the write sequence. Seven code constructions are given with guarantees on the number of writes they can support. For the parameters addressed by the constructions, we also prove upper bounds on the number of writes, which prove the optimality of three of the constructions. We concentrate on codes with short block lengths to keep the complexity of decoding and updates within the feasibility of practical implementation. Even with these short blocks the constructed codes are shown to be within a small additive constant from capacity for an arbitrarily large number of input bits. Part of the study addresses a new rewrite model where some of the input bits can be updated multiple times in a write sequence (hot bits), while other are updated at most once (cold bits). We refer to this new model as hot/cold rewrite codes. It is shown that adding cold bits to a rewrite code has a negligible effect on the total number of writes, while adding an important feature of leveling the physical wear of memory cells between hot and cold input data.

With the rise of datacenter virtualization, the number of entries in forwarding tables is expected to scale from several thousands to several millions. Unfortunately, such forwarding table sizes can hardly be implemented today in on-chip memory. In this paper, we investigate the compressibility of forwarding tables. We first introduce a novel forwarding table architecture with separate encoding in each column. It is designed to keep supporting fast random accesses and fixed-width memory words. Then, we suggest an encoding whose memory requirement per row entry is guaranteed to be within a small additive constant of the optimum. Next, we analyze the common case of two-column forwarding tables, and show that such tables can be presented as bipartite graphs. We deduce graph-theoretical bounds on the encoding size. We also introduce an algorithm for optimal conditional encoding of the second column given an encoding of the first one. In addition, we explain how our architecture can handle table updates. Last, we evaluate our suggested encoding techniques on synthetic forwarding tables as well as on real-life tables.

In a memristor crossbar array, a memristor is positioned on each row-column intersection, and its resistance, low or high, represents two logical states. The state of every memristor can be sensed by the current flowing through the memristor. In this work, we study the sneak path problem in crossbars arrays, in which current can sneak through other cells, resulting in reading a wrong state of the memristor. Our main contributions are a new characterization of arrays free of sneak paths, and efficient methods to read the array cells while avoiding sneak paths. To each read method we match a constraint on the array content that guarantees sneak-path free readout, and calculate the resulting capacity.

For an array of memory cells that are read by threshold measurements, we ask the question of how to choose the measurements in the read sequence to minimize the number of measurements before the array is fully read. We propose and study analytically various adaptive read algorithms, and provide a corresponding lower bound on the average number of measurements. We show that new two-dimensional read algorithms improve over the best one-dimensional ones.

To enable direct access to a memory word based on its index, memories make use of fixed-width arrays, in which a fixed number of bits is allocated for the representation of each data entry. In this paper we consider the problem of encoding data entries of two fields, drawn independently according to known and generally different distributions. Our goal is to find two prefix codes for the two fields, that jointly maximize the probability that the total length of an encoded data entry is within a fixed given width. We study this probability and develop upper and lower bounds. We also show how to find an optimal code for the second field given a fixed code for the first field.

A network switch routes data packets between its multiple input and output ports. Packets from input ports are stored upon arrival in a switch fabric comprising multiple memory banks. This can result in memory contention when distinct output ports request packets from the same memory bank, resulting in a degraded switching bandwidth. To solve this problem, we propose to add redundant memory banks for storing the incoming packets. The problem we address is how to minimize the number of redundant memory banks given some guaranteed contention resolution capability. We present constructions of new switch memory architectures based on different coding techniques. The codes allow decreasing the redundancy by 1/2 or 2/3, depending on the request specifications, compared to non-coding solutions.

The number of monomials required to interpolate a received word in an algebraic list decoder for Reed–Solomon codes depends on the instantaneous channel error, and not only on the decoder design parameters. The implications of this fact are that the decoder should be able to exhibit lower decoding complexity for low-weight errors and, consequently, enjoy a better average-case decoding complexity and a higher decoding throughput. On the analytical side, this paper studies the dependence of interpolation costs on instantaneous errors, in both hard- and soft-decision decoders. On the algorithmic side, it provides an efficient interpolation algorithm, based on the state-of-the-art interpolation algorithm, that enjoys reduced running times for reduced interpolation costs.

We construct new WOM codes with practical design considerations. First the problem of 2 cell q-ary WOM codes is addressed with a construction that uses lattice tilings. The resulting codes for arbitrary numbers of input bits are shown to be within a small additive constant from the capacity. Then we introduce a new model of WOM codes that support data bits with different update requirements. Differentiation between frequently written (hot) bits and rarely written (cold) ones allows a large number of re-writes while leveling the wear between the hot and cold input bits.

A new family of low-complexity array codes is proposed for correcting 4 column erasures. The new codes are tailored for the new error model of clustered column erasures that captures the properties of high-order failure combinations in storage arrays. The model of clustered column erasures considers the number of erased columns, together with the number of clusters into which they fall, without pre-defining the sizes of the clusters. This model addresses the problem of correlated device failures in storage arrays, whereby each failure event may affect multiple devices in a single cluster. The new codes correct essentially all combinations of clustered 4 erasures, i.e., those combinations that fall into three or less clusters. The new codes are significantly more efficient, in all relevant complexity measures, than the best known 4-erasure correcting codes. These measures include encoding complexity, decoding complexity and update complexity.

For the recently proposed model of symbol-pair channels, we advance the pair-error coding theory with algebraic cyclic-code constructions and asymptotic bounds on code rates. Cyclic codes for pair-errors are constructed by a careful use of duals of known tools from cyclic-code theory. Asymptotic lower bounds on code rates show that codes for pair-errors provably exist for rates strictly higher than codes for the Hamming metric.

Probabilistic construction of codes on two-dimensional arrays is proposed and analyzed. Instead of a pure combinatorial erasure model used in traditional array codes, we propose a mixed combinatorial-probabilistic model of limiting the number of column failures, with assuming a binary erasure channel in each failing column. In addition, motivated by practical applications, we maintain an array with a fixed number of columns, while allowing the column size to grow to infinity. As a result, we obtain a framework that allows developing powerful constructions and analysis techniques previously only applicable in the theory of iteratively decoded one-dimensional low-density parity-check codes. The new array-code ensembles are shown to approach the performance of traditional MDS codes, with a simple decoder that offers better scalability in the number of column failures.

A fountain coding framework is proposed that endows receivers with the ability to monitor and control the decoding progress given the instantaneous network conditions. These online features allow an optimal recovery from losses manifested by adversarial or other not purely random processes. A uni-partite graph structure and accompanying algorithms are used to efficiently calculate optimal instantaneous degrees. Using analysis of random-graph processes, the average overhead of a simplified scheme is shown to be upper bounded by 0.236, significantly lower than any known on-line fountain scheme.

A new coding framework is established for channels whose outputs are overlapping pairs of symbols. Such channels are motivated by storage applications in which the spatial resolution of the reader may be insufficient to isolate adjacent symbols. Reading symbols as pairs changes the coding-theoretic error model from the standard bounded number of symbol errors to a bounded number of pair errors. Starting from the most basic coding-theoretic questions, the paper studies codes that protect against pair-errors. It provides answers on pair-error correctability conditions, code construction and decoding, and lower and upper bounds on code sizes. Asymptotic analysis of pair-error correction shows that there exist pair-error codes with rates that are strictly higher than the best known codes in the Hamming metric.

A new coding framework is established for channels whose outputs are overlapping pairs of symbols. Such channels are motivated by storage applications in which the spatial resolution of the reader may be lower than that of the process that was used to store the data. Reading symbols as pairs changes the error model from the standard bounded number of symbol errors to a bounded number of pair errors. Starting from the most basic coding-theoretic questions, the paper studies codes that protect against pair-errors. It provides answers on pair-error correctability, code construction and decoding, and lower and upper bounds on code sizes.

New code constructions are proposed for the wiretap channel with security and error-correction guarantees. For the case of error-free main channels, two families of codes are constructed with optimal encoding and decoding complexities for their wire-tap security. For the case of main channels with errors, two concatenation types are studied for the wire-tap and error-correcting codes. For each of these concatenated schemes, code families are constructed that give optimal cooperation between the wire-tap and error-correction properties. The motivation to study low-complexity wire-tap codes with security and error-correction guarantees comes from data storage applications. Due to imperfect physical erasure processes, important secret information needs to be protected from adversarial access to residual, post erasure, information, and at the same time be protected from errors when read by the legitimate device user.

Shingled magnetic recording is a promising technology to increase the capacity of hard-disk drives with no significant cost impact. Its main drawback is that random-write access to the disk is restricted due to overlap in the layout of data tracks. For computing and storage systems to enjoy the increased capacity, it is necessary to mitigate these access restrictions, and present a storage device that serves unrestricted read/write requests with adequate performance. This paper proposes two different indirection systems to mask access restrictions and optimize performance. The first one is a diskcache based architecture that provides unrestricted access with manageable drop in performance. A second, more complex indirection system, utilizes a new storage unit called S-block. It is shown that the S-block architecture allows good sustained random-write performance, a point where the disk-cache architecture fails. The organization and algorithms of both architectures are specified in detail. Each was implemented and simulated as a discrete-event simulation, mimicking its operation on real storage devices. For the performance evaluation both synthetic workloads and traces from real workloads were used.

Several physical effects that limit the reliability and performance of multilevel flash memories induce errors that have low magnitudes and are dominantly asymmetric. This paper studies block codes for asymmetric limited-magnitude errors over$q$-ary channels. We propose code constructions and bounds for such channels when the number of errors is bounded by$t$and the error magnitudes are bounded by$\ell $. The constructions utilize known codes for symmetric errors, over small alphabets, to protect large-alphabet symbols from asymmetric limited-magnitude errors. The encoding and decoding of these codes are performed over the small alphabet whose size depends only on the maximum error magnitude and is independent of the alphabet size of the outer code. Moreover, the size of the codes is shown to exceed the sizes of known codes (for related error models), and asymptotic rate-optimality results are proved. Extensions of the construction are proposed to accommodate variations on the error model and to include systematic codes as a benefit to practical implementation.

Three new families of lowest density maximum-distance separable (MDS) array codes are constructed, which are cyclic or quasi-cyclic. In addition to their optimal redundancy (MDS) and optimal update complexity (lowest density), the symmetry offered by the new codes can be utilized for simplified implementation in storage applications. The proof of the code properties has an indirect structure: first MDS codes that are not cyclic are constructed, and then transformed to cyclic codes by a minimum-distance preserving transformation.

A new error model is proposed for codes over channels with memory. According to this error model, both the number of symbol errors and the number of error clusters are used to characterize permissible errors. Considering this model as a generalization of random erasures in array codes naturally captures the properties of high-order failure events in disk arrays. A new family of codes tailored to such a model is shown to provide significant complexity improvements compared to known array codes.

Several physical effects that limit the reliability and performance of Multilevel Flash memories induce errors that have low magnitude and are dominantly asymmetric. This paper studies block codes for asymmetric limited-magnitude errors over q-ary channels. We propose code constructions for such channels when the number of errors is bounded by t. The construction uses known codes for symmetric errors over small alphabets to protect large-alphabet symbols from asymmetric limited-magnitude errors. The encoding and decoding of these codes are performed over the small alphabet whose size depends only on the maximum error magnitude and is independent of the alphabet size of the outer code. An extension of the construction is proposed to include systematic codes as a benefit to practical implementation.

We construct two infinite families of low density MDS array codes which are also cyclic. One of these families includes the first such sub-family with redundancy parameter r > 2. The two constructions have different algebraic formulations, though they both have the same indirect structure. First MDS codes that are not cyclic are constructed and then by applying a certain mapping to their parity check matrices, non-equivalent cyclic codes with the same distance and density properties are obtained. Using the same proof techniques, a third infinite family of quasi-cyclic codes can be constructed

In this paper we consider the per-node run-time complexity of network multicast codes. We show that the randomized algebraic network code design algorithms described extensively in the literature result in codes that on average require a number of operations that scales quadratically with the block-length m of the codes. We then propose an alternative type of linear network code whose complexity scales linearly in m and still enjoys the attractive properties of random algebraic network codes. We also show that these codes are optimal in the sense that any rate-optimal linear network code must have at least a linear scaling in run-time complexity

Non-uniform demand networks are defined as a useful connection model, in between multicasts and general connections. In these networks, each sink demands a certain number of messages, without specifying their identities. We study the solvability of such networks and give a tight bound on the number of sinks for which the min cut condition is sufficient. This sufficiency result is unique to the non-uniform demand model and does not apply to general connection networks. We propose constructions to solve networks at, or slightly below capacity, and investigate the effect large alphabets have on the solvability of such networks. We also show that our efficient constructions are suboptimal when used in networks with more sinks, yet this comes with little surprise considering the fact that the general problem is shown to be NP-hard

The miscorrection probability of a list decoder is the probability that the decoder will have at least one noncausal codeword in its decoding sphere. Evaluating this probability is important when using a list-decoder as a conventional decoder since in that case we require the list to contain at most one codeword for most of the errors. A lower bound on the miscorrection is the main result. The key ingredient in the proof is a new combinatorial upper bound on the list-size for a general q-ary block code. This bound is tighter than the best known on large alphabets, and it is shown to be very close to the algebraic bound for Reed-Solomon codes. Finally we discuss two known upper bounds on the miscorrection probability and unify them for linear MDS codes.