The Poltyrev bound provides a very tight upper bound on the decoding error probability when using binary linear codes for transmission over the binary symmetric channel and the additive white Gaussian noise channel, making use of the code's weight spectrum. In the present work, the bound is extended to symmetric binary-input memoryless channels with a discrete output alphabet. The derived bound is demonstrated on a hybrid BSC-BEC channel. Additionally, a reduced-complexity bound is introduced at the cost of some loss in tightness.

Over the last decade, ransomware detection has become a central topic in cybersecurity research. Due to ransomware's direct interaction with storage devices, analyzing I/O streams has become an effective detection method and represents a vital area of focus for research. A major challenge in this field is the lack of publicly accessible data featuring individual command labeling. To address this problem, we introduce the Command LEvel Annotated Ransomware (CLEAR) dataset, a large-scale collection of storage devices' stream data. The dataset comprises 1,045 TiB of I/O traffic data, featuring malicious traffic from 137 ransomware variants. It offers two orders of magnitude more I/O traffic data and one order of magnitude more ransomware variants than any other publicly accessible dataset. Importantly, it is the only dataset that individually labels each I/O command as either ransomware or benign activity. This labeling enables the use of advanced sequential models, which we show to outperform existing state-of-the-art models by up to 82% in data loss prevention. Additionally, this allows us to create new tasks, such as data recovery, by selectively reverting only the commands recognized as ransomware while preserving benign activity. The CLEAR dataset also includes supplementary auxiliary features derived from the data, which we demonstrate to improve performance through feature ablation studies. Lastly, a critical aspect of any ransomware detection model is its robustness to new, unseen ransomware variants, as new strains constantly emerge. Therefore, we propose a benchmark based on our dataset to evaluate performance against unknown ransomware samples and illustrate its application across different models.

Channel quantization is commonly used in non-volatile memories and front-end communication systems. The general setting of channel quantization and mapping involves two phases: a contiguous quantization subject to a specified number of thresholds, referred to as the threshold-constrained, and a mapping with restricted output cardinality. The latter constraint stems from limitations in data throughput and the complexity of post-processing. The objective of this study is to maximize mutual information at the output of the channel quantization and mapping block. We demonstrate that, given a predefined mapping, an optimal solution exists for threshold-constrained using a dynamic programming algorithm. This approach is particularly suitable for non-volatile memory architectures, where the read process involves establishing read thresholds modeled as contiguous quantization. The incorporation of mapping is crucial due to constraints on output cardinality. Furthermore, we provide sufficient conditions for achieving the global optimal solution to the general channel quantization and mapping problem, which involves joint optimization of contiguous quantization and mapping.

In this paper, we introduce an explicit family of subcodes of Reed-Solomon (RS) codes that efficiently achieve list decoding capacity with a constant output list size. The codes are constructed by initially forming the tensor product of two RS codes with carefully selected evaluation sets, followed by specific cyclic shifts to the codeword rows. This process results in each codeword column being treated as an individual coordinate, reminiscent of prior capacity-achieving codes, such as folded RS codes and univariate multiplicity codes. This construction is easily shown to be a subcode of an interleaved RS code, equivalently, an RS code evaluated on a subfield. Alternatively, the codes can be constructed by the evaluation of bivariate polynomials over orbits generated bytwoaffine transformations with coprime orders, extending the earlier use of a single affine transformation in folded RS codes and the recent affine folded RS codes introduced by Bhandari et al. (IEEE T-IT, Feb. 2024). While our codes require large, yet constant characteristic, the two affine transformations facilitate achieving code length equal to the field size, without the restriction of the field being prime, contrasting with univariate multiplicity codes.

In a paper from 2015, Ding et al. (IEEE Trans. IT, May 2015) conjectured that for odd m, the minimum distance of the binary BCH code of length$2^{m}-1$and designed distance$2^{m-2}+1$is equal to the Bose distance calculated in the same paper. In this paper, we prove the conjecture. In fact, we prove a stronger result suggested by Ding et al.: the weight of the generating idempotent is equal to the Bose distance for both odd and even m. Our main tools are some new properties of the so-called fibbinary integers, in particular, the splitting field of related polynomials, and the relation of these polynomials to the idempotent of the BCH code.

In this paper, we introduce a novel explicit family of subcodes of Reed-Solomon (RS) codes that efficiently achieve list decoding capacity with a constant output list size. Our approach builds upon the idea of large linear subcodes of RS codes evaluated on a subfield, similar to the method employed by Guruswami and Xing (STOC 2013). However, our approach diverges by leveraging the idea of permuted product codes, thereby simplifying the construction by avoiding the need of subspace designs. Specifically, the codes are constructed by initially forming the tensor product of two RS codes with carefully selected evaluation sets, followed by specific cyclic shifts to the codeword rows. This process results in each codeword column being treated as an individual coordinate, reminiscent of prior capacity-achieving codes, such as folded RS codes and univariate multiplicity codes. This construction is easily shown to be a subcode of an interleaved RS code, equivalently, an RS code evaluated on a subfield.11Due to space limitation the proofs are omitted and can be found in [1].

We present$O(m^{3})$algorithms for specifying the support of minimum-weight codewords of extended binary BCH codes of length$n=2^{m}$and designed distance$d(m,s,i):=2^{m-1-s}-2^{m-1-i-s}$for some values of$m,i,s$, where m may grow to infinity. Here, the support is specified as the sum of two sets: a set of$2^{2i-1}-2^{i-1}$elements, and a subspace of dimension$m-2i-s$, specified by a basis. In some detail, for designed distance$6\cdot 2^{j}$,$j\in \{0,\ldots ,m-4\}$, we have a deterministic algorithm for even$m\geq 4$, and a probabilistic algorithm with success probability$1-O(2^{-m})$for odd$m\gt 4$. For designed distance$28\cdot 2^{j}$,$j\in \{0,\ldots , m-6\}$, we have a probabilistic algorithm with success probability$\geq \frac {1}{3}-O(2^{-m/2})$for even$m\geq 6$. Finally, for designed distance$120\cdot 2^{j}$,$j\in \{0,\ldots , m-8\}$, we have a deterministic algorithm for$m\geq 8$divisible by 4. We also show how Gold functions can be used to find the support of minimum-weight words for designed distance$d(m,s,i)$(for$i\in \{0,\ldots ,\lfloor m/2\rfloor \}$, and$s\leq m-2i$) whenever$2i|m$. Our construction builds on results of Kasami and Lin, who proved that for extended binary BCH codes of designed distance$d(m,s,i)$(for integers$m\geq 2$,$0\leq i\leq \lfloor m/2\rfloor $, and$0\leq s\leq m-2i$), the minimum distance equals the designed distance. The proof of Kasami and Lin makes use of a non-constructive existence result of Berlekamp, and a constructive “down-conversion theorem” that converts some words in BCH codes to lower-weight words in BCH codes of lower designed distance. Our main contribution is in replacing the non-constructive counting argument of Berlekamp by a low-complexity algorithm. In one aspect, the current paper extends the results of Grigorescu and Kaufman, who presented explicit minimum-weight codewords for extended binary BCH codes of designed distance exactly 6 (and hence also for designed distance$6\cdot 2^{j}$, by a well-known “up-conversion theorem”), as we cover more cases of the minimum distance. In fact, we prove that the codeword constructed by Grigorescu and Kaufman is a special case of the current construction. However, the minimum-weight codewords we construct do not generate the code, and are not affine generators, except, possibly, for a designed distance of 6.

Recent years have witnessed a significant increase in the storage density of NAND flash memory, making it a critical component in modern electronic devices. However, with the rise in storage capacity comes an increased likelihood of errors in data storage and retrieval. The growing number of errors poses ongoing challenges for system designers and engineers, in terms of the characterization, modeling, and optimization of NAND-based systems. We present a novel approach for modeling and preventing errors by utilizing the capabilities of generative and unsupervised machine learning methods. As part of our research, we constructed and trained a neural modulator that translates information bits into programming operations on each memory cell in NAND devices. Our modulator, tailored explicitly for flash memory channels, provides a smart writing scheme that reduces programming errors as well as compensates for data degradation over time. Specifically, the modulator is based on an auto-encoder architecture with an additional channel model embedded between the encoder and the decoder. A conditional generative adversarial network (cGAN) was used to construct the channel model. Optimized for the end-of-life work-point, the learned memory system outperforms the prior art by up to 56\% in raw bit error rate (RBER) and extends the lifetime of the flash memory block by up to 25\%.

We present a new fast Chase decoding algorithm for binary BCH codes. The new algorithm reduces the complexity in comparison to a recent fast Chase decoding algorithm for Reed–Solomon (RS) codes by the authors (IEEE Trans. IT, 2022), by requiring only a single Kötter iteration per edge of the decoding tree. In comparison to the fast Chase algorithms presented by Kamiya (IEEE Trans. IT, 2001) and Wu (IEEE Trans. IT, 2012) for binary BCH codes, the polynomials updated throughout the algorithm of the current paper typically have a much lower degree. To achieve the complexity reduction, we build on a new isomorphism between two solution modules in the binary case, and on a degenerate case of the soft-decision (SD) version of the Wu list decoding algorithm. Roughly speaking, we prove that when the maximum list size is 1 in Wu list decoding of binary BCH codes, assigning a multiplicity of 1 to a coordinate has the same effect as flipping this coordinate in a Chase-decoding trial. The solution-module isomorphism also provides a systematic way to benefit from the binary alphabet for reducing the complexity in bounded-distance hard-decision (HD) decoding. Along the way, we briefly develop the Gröbner-bases formulation of the Wu list decoding algorithm for binary BCH codes, which is missing in the literature.

We consider the repair problem for Reed–Solomon (RS) codes, evaluated on an$\mathbb {F}_{q}$-linear subspace$U\subseteq \mathbb {F}_{q^{m}} $of dimension$d$, where$q$is a prime power,$m$is a positive integer, and$\mathbb {F}_{q}$is the Galois field of size$q$. For$q>2$, we show the existence of a linear repair scheme for the RS code of length$n=q^{d}$and codimension$q^{s}$,$s < d$, evaluated on$U$, in which each of the$n-1$surviving nodes transmits only$r$symbols of$\mathbb {F}_{q}$, provided that$ms\geq d(m-r)$. For the case$q=2$, we prove a similar result, with some restrictions on the evaluation linear subspace$U$. Our proof is based on a probabilistic argument, however the result is not merely an existence result; the success probability is fairly large (at least$1/3$) and there is a simple criterion for checking the validity of the randomly chosen linear repair scheme. Our result extend the construction of Dau–Milenkovic to the range$r < m-s$, for a wide range of parameters.

We present a simple syndrome-based fast Chase decoding algorithm for Reed–Solomon (RS) codes. Such an algorithm was initially presented by Wu (IEEE Trans. IT, Jan. 2012), building on properties of the Berlekamp–Massey (BM) algorithm. Wu devised a fast polynomial-update algorithm to construct the error-locator polynomial (ELP) as the solution of a certain linear-feedback shift register (LFSR) synthesis problem. This results in a conceptually complicated algorithm, divided into 8 subtly different cases. Moreover, Wu’s polynomial-update algorithm is not immediately suitable for working with vectors of evaluations. Therefore, complicated modifications were required in order to achieve a true “one-pass” Chase decoding algorithm, that is, a Chase decoding algorithm requiring$O(n)$operations per modified coordinate, where$n$is the RS code length. The main result of the current paper is a conceptually simple syndrome-based fast Chase decoding of RS codes. Instead of developing a theory from scratch, we use the well-established theory of Gröbner bases for modules over$\mathbb {F}_{q}[X]$(where$\mathbb {F}_{q}$is the finite field of$q$elements, for$q$a prime power). The basic observation is that instead of Wu’s LFSR synthesis problem, it is much simpler to consider “the right” minimization problem over amodule. The solution to this minimization problem is a simple polynomial-update algorithm that avoids syndrome updates and works seamlessly with vectors of evaluations. As a result, we obtain a conceptually simple algorithm for one-pass Chase decoding of RS codes. Our algorithm is general enough to work with any algorithm that finds a Gröbner basis for the solution module of the key equation as the initial algorithm (including the Euclidean algorithm), and it is not tied only to the BM algorithm.

We consider the repair problem for Reed-Solomon (RS) codes, evaluated on an$\mathbb{F}_{q}$-linear subspace$U \subseteq \mathbb{F}_{q^{m}}$of dimension$d$, where$q$is a prime power,$m$is a positive integer, and$\mathbb{F}_{q}$is the Galois field of size$q$. For$q > 2$, we show the existence of a linear repair scheme for the RS code of length$n=q^{d}$and codimension$q^{s}, s < d$, evaluated on$U$, in which each of the$n-1$surviving nodes transmits only$r$symbols of$\mathbb{F}_{q}$, provided that$ms\geq d(m-r)$. For the case$q=2$, we prove a similar result, with some restrictions on the evaluation linear subspace$U$. Our proof is based on a probabilistic argument, however the result is not merely an existence result; the success probability is fairly large (at least 1/3) and there is a simple criterion for checking the validity of the randomly chosen linear repair scheme.

In multi-level-cell memory, such as flash and phase-change memory, shrinking cell size and the growing number of levels per cell worsen the access rate to capacity ratio and even reduce access rate. We present minimal maximum-level programming, a scheme for expediting cell programming by sharing physical cells among multiple data sectors and exploiting the fact that making moderate changes to a cell's charge level is faster than making large ones. In particular, we encode the data such that in the k th writing of data to a cell, only the lowest k+1 levels are utilized. Unlike in previously proposed cell-sharing schemes, different same-size data sectors occupy different numbers of physical cells, and a cell may hold a fraction of a bit of a given data sector. Nevertheless, the exposed sector size remains unchanged. Data are encoded, but without redundancy. In a four-level cell example, we achieve up to 75% reduction in write latency. Read latency may be degraded, depending on the percentage of utilized capacity.

In multi-level-cell (MLC) memory such as Flash and Phase-change memory, shrinking cell size and the growing number of levels per cell worsen the access-rate to capacity ratio and even reduce access rate. We present Minimal Maximum-Level Programming (MMLP), a scheme for expediting cell writing by sharing physical cells among multiple data pages and exploiting the fact that making moderate changes to a cell's level is faster than making large ones. Reading is also expedited by requiring fewer reference comparisons. In a four-level cell example, we achieve a 32% reduction in write/read latency relative to prior art with negligible area overhead.

In write-once memory (e.g., Flash), a cell's level can only be raised, and erasure is only in bulk. The total number of erasures (endurance) is limited, and drops sharply with technology shrinkage and with cell-capacity increase. The normalized write capacity (ratio of total amount of data that can be written to storage capacity) drops similarly. Various coding schemes enable overwrites at the expense of storage capacity. With all of them, whenever desired data cannot be written to its current page, the page is “retired” for subsequent erasure. Interestingly, however, a retired page can still be used for writing other data, and it has been proposed to try and use retired pages. Simulation results are promising. In this paper, after briefly presenting Retired Page Utilization, we cast it as a cross-page coding technique. We employ Markovian analysis to derive the expected number of random-data writes with RPU, and show how the required state space can sometimes be substantially reduced.

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.

In NAND Flash memory featuring multi-level cells (MLC), the width of threshold voltage distributions about their nominal values affects the permissible number of levels and thus storage capacity. Unfortunately, inter-cell coupling causes a cell's charge to affect its neighbors' sensed threshold voltage, resulting in an apparent broadening of these distributions. We present a novel approach, whereby the data written to Flash is constrained, e.g., by forbidding certain adjacent-cell level combinations, so as to limit the maximum voltage shift and thus narrow the distributions. To this end, we present a new family of constrained codes. Our technique can serve for capacity enhancement (more levels) or for improving endurance, retention and bit error rate (wider guard bands between adjacent levels). It may also be combined with various programming order techniques that mitigate the inter-cell coupling effects and with decoding techniques that compensate for them.

Network-on-Chip (NoC) links consume a significant fraction of the total NoC power. We present Selective Packet Interleaving (SPI), a flit transmission scheme that reduces power consumption in NoC links. SPI decreases the number of bit transitions in the links by exploiting the multiplicity of virtual channels in a NoC router. SPI multiplexes flits to the router's output link so as to minimize the number of bit transitions from the previously transmitted flit. Analysis and simulations demonstrate a reduction of up to 55% in the number of bit transitions and up to 40% savings in power consumed on the link. SPI benefits grow with the number of virtual channels. SPI works better for links with a small number of bits in parallel. While SPI compares favorably against bus inversion, combining both schemes helps to further reduce bit transitions.

In the current deep sub-micron age, interconnect reliability is a subject of major concern, and is crucial for a successful product. Coding is a widely-used method to achieve communication reliability, which can be very useful in a network-on-chip (NoC). A key challenge for NoC error detection is to provide a defined detection level, while minimizing the number of redundant parity bits, using small encoder and decoder circuits, and ensuring shortest path routing. We present parity routing (PaR), a novel method to reduce the number of redundant bits transmitted. PaR exploits NoC path diversity to reduce the number of redundant parity bits. Our analysis shows that, for example, on a 4×4 NoC with a demand of one parity bit, PaR reduces the redundant information transmitted by 75%, and the savings increase asymptotically to 100% with the size of the NoC. In addition, we show that PaR can yield power savings due to the reduced number of bit transmissions and simple decoding process. Furthermore, PaR utilizes low complexity, small-area circuits.