The Levenshtein sequence reconstruction problem studies the reconstruction of a transmitted sequence from multiple erroneous copies of it. A fundamental question in this field is to determine the minimum number of erroneous copies required to guarantee correct reconstruction of the original sequence. This problem is equivalent to determining the maximum possible intersection size of two error balls associated with the underlying channel. Existing research on the sequence reconstruction problem has largely focused on channels with a single type of error, such as insertions, deletions, or substitutions alone. However, relatively little is known for channels that involve a mixture of error types, for instance, channels allowing both deletions and substitutions. In this work, we study the sequence reconstruction problem for the single-deletion two-substitution channel, which allows one deletion and at most two substitutions applied to the transmitted sequence. Specifically, we prove that if two $q$-ary length-$n$ sequences have the Hamming distance $d\geq 2$, where $q\geq 2$ is any fixed integer, then the intersection size of their error balls under the single-deletion two-substitution channel is upper bounded by $(q^2-1)n^2-(3q^2+5q-5)n+O_q(1)$, where $O_q(1)$ is a constant independent from $n$ but dependent on $q$. Moreover, we show that this upper bound is tight up to an additive constant.

An analytical framework integrating performance characterization and coding theory is proposed to mitigate sneak path (SP) interference in resistive random-access memory (ReRAM) crossbar arrays. The core innovation is identified in the mathematical decomposition of ReRAM’s non-ergodic data-dependent channel into multiple stationary memoryless subchannels. Through information-theoretic analysis, an approximate finite-length characterization of the theoretical lower bound for decoding word error probability (WEP) is established. This is achieved by systematically analyzing the SP occurrence rate in constrained array geometries combined with comprehensive evaluation of both mutual information and dispersion metrics across the decomposed channel components. Building upon this decomposition paradigm, a systematic code construction methodology is developed using density evolution principles for sparse-graph code design. The designed codes not only exhibit capacity-approaching decoding thresholds but also yield word error rate simulation results that are close to the derived WEP bound under practical crossbar configurations.

Composite DNA is a recent novel method to increase the information capacity of DNA-based data storage above the theoretical limit of 2 bits/symbol. In this method, every composite symbol does not store a single DNA nucleotide but a mixture of the four nucleotides in a predetermined ratio. By using different mixtures and ratios, the alphabet can be extended to have much more than four symbols in the naire approach. While this method enables higher data content per synthesis cycle, potentially reducing the DNA synthesis cost, it also imposes significant challenges for accurate DNA sequencing since the baselevel errors can easily change the mixture of bases and their ratio, resulting in changes to the composite symbols. With this motivation, we propose efficient constrained coding techniques to enforce the biological constraints, including the runlength-limited constraint and the GC-content constraint, into every DNA synthesized oligo, regardless of the mixture of bases in each composite letter and their corresponding ratio. Our contributions include computing the capacity of the constrained channel, constructing efficient encoders/decoders, and providing the best options for the composite letters to obtain capacityapproaching codes. For certain codes' parameters, our methods incur only one redundant symbol.

In this work, we study the sequence reconstruction problem for the single-deletion single-substitution channel, assuming that the transmitted sequence belongs to a$q$-ary code with minimum Hamming distance at least 2, where$q \geq 2$is any fixed integer. Specifically, we prove that for any two$q$-ary sequences of length$n$and with Hamming distance$d \geq 2$, the size of the intersection of their error balls is upper bounded by$2 q n-3 q-2-\delta_{q, 2}$, where$\delta_{i, j}$is the Kronecker delta. We also prove the tightness of this bound by constructing two sequences whose error ball intersection size achieves this bound.

The sneak path (SP) issue presents a substantial challenge for resistive random-access memory (ReRAM), significantly affecting data storage reliability. The SP rate, which represents the proportion of memory cells impacted by SPs, is a crucial parameter influencing the probability of data detection errors. In this paper, we concentrate on analyzing the probability distribution of the SP rate in ReRAM arrays that incorporate imperfect selectors. Our research indicates that when ReRAM stores data following an independent and identically distributed (i.i.d.) Bernoulli distribution with parameter$q$, and the array size is large, the SP rate approximates a Gaussian distribution. The mean and variance of this distribution can be explicitly derived as functions of the number of selector failures, parameter$q$, and the array size.

High costs remain a primary limitation in the practical application of DNA storage, particularly in the synthesis process. This work focuses on a common synthesis method that generates multiple DNA strands in parallel from a fixed supersequence, one nucleotide at a time. The synthesis time is determined by the length of this supersequence. We investigate the maximum sizes and capacities of codes that restrict the maximum synthesis time while adhering to two critical biochemical constraints in a DNA storage channel: the runlength-limited constraint and the GC-content constraint. For specific parameters, we also present an encoding algorithm for codes that restrict the maximum synthesis time and satisfy both constraints.

Recent developments in storage- especially in the area of resistive random access memory (ReRAM)- are attempting to scale the storage density by regarding the information data as two-dimensional (2D), instead of one-dimensional (1D). Correspondingly, new types of 2D constraints are introduced into the input information data to improve the system reliability. While 1D constraints have been extensively investigated in the literature, the study for 2D constraints is much less profound. Particularly, given a constraint ${\mathcal{F}}$ and a design of 1D codes whose codewords satisfy ${\mathcal{F}}$, the problem of constructing efficient 2D codes, such that every row and every column in every codeword satisfy ${\mathcal{F}}$, has been a challenge.This work provides an efficient solution to the challenging coding problem above for the binary bounded-weight constrained codes that restrict the maximum number of 1’s (called weight). Formally, we propose a universal framework to design 2D codes that guarantee the weight of every row and every column of length n to be at most f(n) for any given function f(n). We show that if there exists a design of capacity-approaching 1D codes, then our method also provides capacity-approaching 2D codes for all f = ω(log n).

Resistive random-access memory (ReRAM) is a promising non-volatile memory technology. However, its crossbar array structure leads to a severe problem known as sneak path interference (SPI), which is correlated and data-dependent. From an information-theoretic perspective, memory systems like ReRAM can be considered as special types of communication channels. Inspired by deep learning applications in communication systems, the detection of ReRAM channels with SPI was formulated as a learning problem recently, and a multi-layer perceptron (MLP) network was employed to mitigate SPI. However, it requires a large amount of training data to achieve satisfactory performance. In this paper, we first propose a bidirectional long short-term memory (BiLSTM) based detector for ReRAM to exploit the correlation between memory cells introduced by SPI. Moreover, a few-shot learning algorithm based on meta-transfer learning (MTL) is proposed to further improve the generalization ability of the detector. The bit error rate (BER) bound and generalization bound are also derived to verify the effectiveness of our proposed schemes. Simulation results demonstrate that the BiLSTM-based detector with MTL can dramatically reduce the required training samples by four to five orders of magnitude while improving the BER performance compared to the existing MLP-based detection scheme.

Composite DNA is a novel approach that enables DNA-based data storage to exceed the theoretical limit of 2 bits per symbol. In this approach, every composite symbol does not store a single DNA nucleotide but a mixture of the four nucleotides in a predetermined ratio. By using different mixtures and ratios, the alphabet can be extended to have far more than four symbols compared to the naive approach. Although this method increases data density per synthesis cycle and potentially reduces DNA synthesis costs, it also introduces significant challenges for accurate DNA sequencing since the base-level errors can easily change the mixture of bases and their ratio, leading to changes in the composite symbols.With this motivation, we investigated error-correcting codes for composite DNA in a general setting. Consider a data storage scenario where m reads are provided for each composite DNA sequence, and for each composite symbol, the difference between the observation ratio and the original ratio in its base mixture is at most ϵ. We further assume that at most δm sequences have errors, for some 0 ≤ δ ≤ 1, and each of them suffers from at most t edit errors (i.e., substitutions, insertions, and deletions). Given arbitrary values of m, ϵ, δ and t, our task is to design a codebook such that every codeword can be uniquely reconstructed. In this work, we focus on single edit error, i.e., t = 1, and for several cases, we show that our proposed codes are asymptotically optimal.

Accurate modeling and estimation of the threshold voltages of the flash memory can facilitate the efficient design of channel codes and detectors. However, most flash memory channel models are based on Gaussian distributions, which fail to capture certain key properties of the threshold voltages, such as their heavy-tails. To enhance the model accuracy, we first propose a piecewise student's t-distribution mixture model (PSTMM), which features degrees of freedom to control the left and right tails of the voltage distributions. We further propose an PSTMM based expectation maximization (PSTMM-EM) algorithm to estimate model parameters for flash memories by alternately computing the expected values of the missing data and maximizing the likelihood function with respect to the model parameters. Simulation results demonstrate that our proposed algorithm exhibits superior stability and can effectively extend the flash memory lifespan by 1700 program/erase (PE) cycles compared with the existing parameter estimation algorithms.

The achievable rate of code over resistive random-access memory (ReRAM) channel with finite selector failures was published in our recent work. The rate was derived under the assumption of independent and identically distributed (i.i.d.) input. In this work, focusing on the ReRAM channel with a single selector failure in the memory array, we derive an upper bound on achievable rate under arbitrary input distribution. This upper bound is within 0.02 bits from the achievable rate of i.i.d. input, indicating that i.i.d. is very close to optimal for large memory arrays. Moreover, we analyze the achievable rate of random code over ReRAM channel with suboptimal decodings where the decoder ignores the channel correlation. Our result indicates that in this case the achievable rate is limited by the capacity of a memoryless channel. We reveal both weak and strong asymptotic properties of ReRAM channel to prove this. The proof can be directly extended to the case of ReRAM with an arbitrary number of selector failures in the memory array.

DNA synthesis remains the most costly part of the DNA data storage. In this work, we consider a popular synthesis method that generates multiple DNA strands in parallel from a fixed supersequence$S$, one nucleotide at a time. Under this assumption, the synthesis time (or the number of synthesis cycles) is then determined by the length of the common supersequence. In this work, we propose constructions of quaternary codes that simultaneously (i) restrict the maximum synthesis time, (ii) correct a single deletion or insertion error, and (iii) satisfy the runlength limited constraint, a crucial biochemical constraint in a DNA storage channel. For certain parameters, we provide an improved construction of DNA codes with a smaller synthesis time while costing less redundancy as compared to the best-known result in the literature.

Motivated by the information transmission in neurons with various applications in in-vivo nano-machines or emerging medical applications, Ye and Elishco [2023] introduced a communication channel, called the absorption channel, and proposed codes correcting absorption errors. For a non-binary alphabet$\Sigma_{q}$, the authors presented constructions of codes of length$n$correcting a single absorption and the best construction yielded a redundancy of$\log_{q}n+12\log_{q}\log_{q}n+O(1)$symbols. In this work, we make progress on the code design problem above and show that the redundancy can be further reduced significantly as follows: When$q=3$, we construct “nearly optimal” ternary codes of length$n$with at most$\log_{3}n+5.43$redundant symbols. Note that such a redundancy is optimal up to a constant. • For a general alphabet$\Sigma_{q}$, we construct q-ary codes of length$n$correcting a single absorption error with$\log_{q}n+3\log_{q}\log_{q}n+O(1)$redundant symbols, providing an alternative. simpler construction that improves the results given by Ye and Elishco.

In this paper, for any fixed integer$q > 2$, we construct q-ary codes correcting a burst of at most$t$deletions with redundancy$\log n+8$log log$n$+ o(log log$n) >+\gamma_{q,t}$bits and near-linear encoding/decoding complexity, where$n$is the message length and$\gamma_{q,t}$is a constant that only depends on$q$and$t$. In previous works there are constructions of such codes with redundancy$\log n+O$(log$q$log log n) bits or$\log n+O$($t$2log log n)$+O(t\log q)$. The redundancy of our new construction is independent of$q$and$t$in the second term.

The achievable rate of code over resistive random-access memory (ReRAM) channel with finite selector failures was published in our recent work. The rate was derived under the assumption of independent and identically distributed (i.i.d.) input. In this work, focusing on the ReRAM channel in the case of single selector failure, we derive an upper bound on achievable rate under arbitrary input distribution. This upper bound is within 0.02 bits from the achievable rate of i.i.d. input, indicating that i.i.d. is very close to optimal for large memory arrays.

The NAND flash memory channel is corrupted by different types of noises, such as the data retention noise and the wear-out noise, which lead to unknown channel offset and make the flash memory channel non-stationary. In the literature, machine learning-based methods have been proposed for data detection for flash memory channels. However, these methods require a large number of training samples and labels to achieve a satisfactory performance, which is costly. Furthermore, with a large unknown channel offset, it may be impossible to obtain enough correct labels. In this paper, we reformulate the data detection for the flash memory channel as a transfer learning (TL) problem. We then propose a model-based deep TL (DTL) algorithm for flash memory channel detection. It can effectively reduce the training data size from 106samples to less than 104samples. Moreover, we propose an unsupervised domain adaptation (UDA)-based DTL algorithm using moment alignment, which can detect data without any labels. Hence, it is suitable for scenarios where the decoding of error-correcting code fails and no labels can be obtained. Finally, a UDA-based threshold detector is proposed to eliminate the need for a neural network. Both the channel raw error rate analysis and simulation results demonstrate that the proposed DTL-based detection schemes can achieve near-optimal bit error rate (BER) performance with much less training data and/or without using any labels.

The problem of correcting deletions and insertions has recently received significantly increased attention due to the DNA-based data storage technology, which suffers from deletions and insertions with extremely high probability. In this work, we study the problem of constructing non-binary burst-deletion/insertion correcting codes. Particularly, for the quaternary alphabet, our designed codes are suited for correcting a burst of deletions/insertions in DNA storage. Non-binary codes correcting a single deletion or insertion were introduced by Tenengolts (1984), and the results were extended to correct a fixed-length burst of deletions or insertions by Schoeny et al. (2017). Recently, Wang et al. (2021) proposed constructions of non-binary codes of length n, correcting a burst of length at most two for q-ary alphabets with redundancy$\log n+O(\log q \log \log n)$bits, for arbitrary even q. The common idea in those constructions is to convert non-binary sequences into binary sequences, and the error decoding algorithms for the q-ary sequences are mainly based on the success of recovering the corresponding binary sequences, respectively. In this work, we look at a natural solution that the error detection and correction algorithms are performed directly over q-ary sequences, and for certain cases, our codes provide a more efficient encoder with lower redundancy than the best-known encoder in the literature. Particularly, (Single-error correction codes) We first present a new version of non-binary VT codes that are capable of correcting a single deletion or single insertion, providing an alternative simpler and more efficient encoder of the construction by Tenengolts (1984). Our construction is based on the differential vector, and the codes are referred to as the differential VT codes. In addition, we provide linear-time algorithms that encode user messages into these codes of length n over the q-ary alphabet for$q \geqslant 2$with at most$\lceil \log _{q} n\rceil +1$redundant symbols, while the optimal redundancy required is at least$\log _{q} n+\log _{q} (q-1)$symbols. Our designed encoder reduces the redundancy of the best-known encoder of Tenengolts (1984) by at least 2 redundant symbols or equivalently$2\log _{2} q$bits. (Burst-error correction codes) We use the idea of the binary shifted VT codes to define the q-ary differential shifted VT codes, and propose non-binary codes correcting a burst of up to two deletions (or two insertions) with redundancy$\log n+3\log \log n+ O(\log q)$bits, which improves a recent result of Wang et al. (2021) with redundancy$\log n+O(\log q \log \log n)$bits for all$q\geqslant 8$. We then extend the construction to design non-binary codes correcting a burst of either exactly or at most t deletions (or insertions) for arbitrary$t\geqslant 2$.

Non-volatile memory (NVM) channels suffer from unknown offsets due to the presence of various impairments of the memory devices. Machine learning based methods have been proposed for data detection for NVMs under unknown channel offsets. However, the existing methods require a large number of training samples and labels to achieve a satisfactory data detection performance, which will result in large read latency and more power consumption. In this paper, we formulate a deep learning based data detection framework as a transfer learning problem. A deep transfer learning (DTL) based data detection scheme is proposed to reduce the number of required training samples and labels. The optimal symbol error rate is also derived as the performance benchmark by assuming that the perfect channel knowledge is known to the detector. Our experiment results demonstrate that the proposed DTL-based data detection scheme can achieve near-optimal performance with the training data size being reduced by two orders of magnitude compared with the original deep learning-based detector.

In this work, we present a new version of non-binary VT codes that are capable of correcting a single deletion or single insertion. Moreover, we provide the first-known linear-time algorithms that encode user messages into these codes of length$n$over the q-ary alphabet for$q$> 2 with at most [logq$n$] + 1 redundant symbols, while the optimal redundancy required is at least logq$n$+ logq(q - 1) symbols. Our designed encoder reduces the redundancy of the best known encoder of Tenengolts (1984) by at least 2 + logq(3) redundant symbols, or equivalently 2 log2q + 3 redundant bits.

In this work, we investigate a challenging problem, which has been considered to be an important criterion in designing codewords for DNA computing purposes, namely secondary structure avoidance in single-stranded DNA molecules. In short, secondary structure refers to the tendency of a single-stranded DNA sequence to fold back upon itself, thus becoming inactive in the computation process. The main contribution of this work is to provide an explicit construction of DNA codes that completely avoid the formation of secondary structures of arbitrary stem length.Formally, given codeword length n and arbitrary integer m ⩾ 2, we provide efficient methods to construct DNA codes of length n that avoid secondary structure of any stem length more than or equal to m. Particularly, when m = 3, our constructions yield a family of DNA codes of rate 1.3031 bits/nt, while the highest rate found in the prior art was 1.1609 bits/nt. In addition, for m ⩾ 3log n+4, we provide an efficient encoder that incurs only one redundant symbol.

In this work, we propose efficient constrained coding schemes to significantly reduce the sneak path interference (SPI), a fundamental and challenging problem, in crossbar resistive memory arrays. Particularly, we attempt to combat the sneak path effect locally as follows. For arrays of size n × n, we study coding methods that enforce every sliding window of size m×m (where each window refers to a subarray consisting of consecutive rows and consecutive columns), for some m2/2 − δ for δ ⩾ 0, and this constraint is called the locally bounded-weight constraint, or•Sneak-path-free: the written bits in every window do not induce any sneak path to any cell, and this constraint is called the locally sneak-path-free constraint.In this work, we study the maximum information rate that can be achieved (or channel capacity) and design codes for each constraint. Particularly, for the first constraint, for arbitrary m ⩾ 4 and$\delta \leq m\left( {\sqrt m /2 - 1} \right) = \Theta \left( {m\sqrt m } \right)$, we provide an efficient construction of codes with the code rate 1 − 2/$\sqrt m $, while the highest rate found in the prior art is approximately 1 − 1/m, which was only applicable for m = n − o(n) and δ = 0.

In this paper, we construct non-binary, more specifically, q-ary, two-deletion correcting codes with redundancy 5 log n + O(log q log log n) bits and encoding complexity near-linear in n, where q > 2 is an even integer and n is the message length. The redundancy of our construction is log n bits higher than the best known explicit binary two-deletion codes (Guruswami et al, IEEE Trans. Inf. Theory 2021) and is the lowest in all known explicit non-binary two-deletion codes.

In this paper, we consider the decoding of fountain codes where the received symbols may have errors. It is motivated by the application of fountain codes in DNA-based data storage systems where the inner code decoding, which generally has undetectable errors, is performed before the outer fountain code decoding. We propose a novel and efficient decoding algorithm, namely basis-finding algorithm (BFA), followed by three implementations. The key idea of the BFA is to find a basis of the received symbols, and then use the most reliable basis elements to recover the source symbols with the inactivation decoding. Gaussian elimination is used to find the basis and to identify the most reliable basis elements. As a result, the BFA has polynomial time complexity. For random fountain codes, we are able to derive some theoretical bounds for the frame error rate (FER) of the BFA. Extensive simulations with Luby transform (LT) codes show that, the BFA has significantly lower FER than the belief propagation (BP) algorithm except for an extremely large amount of received symbols, and the FER of the BFA generally decreases as the average weight of basis elements increases.

In this work, we study two types of constraints on two-dimensional binary arrays. Given$p\in [{0,1}],\epsilon \in [{0,1/2}]$, we study 1) the$p$-bounded constraint: a binary vector of size$n$is said to be$p$-bounded if its weight is at most$pn$, and 2) the$\epsilon $-balanced constraint: a binary vector of size$n$is said to be$\epsilon $-balanced if its weight is within$\big [(1/2-\epsilon)n, (1/2+\epsilon)n\big]$. Such constraints are crucial in several data storage systems, those regard the information data as two-dimensional (2D) instead of one-dimensional (1D), such as the crossbar resistive memory arrays and the holographic data storage. In this work, efficient encoding/decoding algorithms are presented for binary arrays so that the weight constraint (either$p$-bounded constraint or$\epsilon $-balanced constraint) is enforced over every row and every column, regarded as 2D row-column (RC) constrained codes; or over every window (where each window refers to as a subarray consisting of consecutive rows and consecutive columns), regarded as 2D sliding-window (SW) constrained codes. While low-complexity designs have been proposed in the literature, mostly focusing on 2D RC constrained codes where$p=1/2$and$\epsilon =0$, this work provides efficient coding methods that work for both 2D RC constrained codes and 2D SW constrained codes, and more importantly, the methods are applicable for arbitrary values of$p$and$\epsilon $. Furthermore, for certain values of$p$and$\epsilon $, we show that, for sufficiently large array size, there exists linear-time encoding/decoding algorithm that incurs at most one redundant bit.

In this paper, we construct$q$-ary two-deletion correcting codes and burst-deletion correcting codes, where$q\geq 2$is an even integer. For two-deletion codes, our construction has redundancy$5\log n+O(\log q\log \log n)$and has encoding complexity near-linear in$n$, where$n$is the length of the message sequences. For burst-deletion codes, we first present a construction of binary codes with redundancy$\log n+9\log \log n+\gamma _{t}+o(\log \log n)$bits$(\gamma _{t}$is a constant that depends only on$t$) and capable of correcting a burst of at most$t$deletions, which improves the Lenz-Polyanskii Construction (ISIT 2020). Then we give a construction of$q$-ary codes with redundancy$\log n+(8\log q+9)\log \log n+\gamma _{t}+o(\log \log n)$bits and capable of correcting a burst of at most$t$deletions.

The maximum achievable rate is derived for resistive random-access memory (ReRAM) channel with sneak-path interference. Based on the mutual information spectrum analysis, the maximum achievable rate of ReRAM channel with independent and identically distributed (i.i.d.) binary inputs is derived as an explicit function of channel parameters such as the distribution of cell selector failures and channel noise level. Due to the randomness of cell selector failures, the ReRAM channel demonstrates multi-status characteristic. For each status, it is shown that as the array size is large, the fraction of cells affected by sneak paths approaches a constant value. Therefore, the mutual information spectrum of the ReRAM channel is formulated as a mixture of multiple stationary channels. Maximum achievable rates of the ReRAM channel with different settings, such as single- and across-array codings, with and without data shaping, and optimal and treating-interference-as-noise (TIN) decodings, are compared. These results provide valuable insights on the code design for ReRAM.

In this paper, we propose a mutual information-maximizing quantized layered min-sum (MIM-QLMS) decoder for quasi-cyclic low-density parity-check (QC-LDPC) codes. Our proposed decoder operates similarly to a layered min-sum decoder with additional reconstruction and quantization operations by using single-input lookup tables (LUTs). In particular, we first develop the protograph-based MIM density evolution to design the LUTs, which may differ for each iteration and each edge in the protograph of the QC-LDPC codes. Furthermore, to minimize the memory requirement for storing the LUTs, we propose an optimization method to unify all LUTs into only four distinct LUTs, which can be used for all decoding iterations. To the best of our knowledge, the proposed MIM-QLMS decoders are the first class of layered finite alphabet iterative decoders (FAIDs) that are designed based on accurately tracking the probability distributions of the exchanged messages. Simulation results show that for 3-bit (resp. 4-bit) exchanged message precision, the proposed MIM-QLMS decoders can reasonably (resp. generally) outperform the state-of-the-art layered FAIDs and the layered normalized min-sum decoder, in terms of both the error rate performance and the average number of iterations.

In this work, given n,ϵ > 0, two efficient encoding (decoding) methods are presented for mapping arbitrary data to (from) n×n binary arrays in which the weight of every row and every column is within [(1/2–ϵ)n, (1/2+ϵ)n], which is referred to as the ϵ-balanced constraint. The first method combines the divide and conquer algorithm and a modification of the Knuth’s balancing technique, resulting a redundancy of Θ(n) bits. On the other hand, for sufficiently large n, the second method uses the sequence replacement technique, which costs only 1 redundant bit. The latter method reduces significantly the redundancy of the best known encoder for two-dimensional p-bounded weight constrained codes from (n + 3) bits to a single bit.

Advances in synthesis and sequencing technologies have made DNA macromolecules an attractive medium for digital information storage. Compared with the ex vivo method that stores data in a non-biological environment, there have been considerations and attempts to store data in living organisms, also known as the in vivo method or live DNA due to several magnificent advantages. Data stored in this medium is prone to errors arising from various mutations such as point mutations (when there is a change in a single nucleotide in DNA, i.e. deletion, insertion, or substitution) or chromosomal alterations (that change the structure of a segment of DNA, i.e. tandem duplication, inversion).In this paper, we provide error-correcting codes for errors caused by inversions, that reverse the order of a segment of DNA. In particular, we construct families of codes for correcting single inversion of a fixed length or variable length up to a given constant k with at most log n+Θ(1) redundant bits, where the redundancy matches the optimal value up to only a constant additive term. Moreover, our codes remain order-optimal, i.e. the redundancy is at most log n + o(log n), when k = o(log n). The redundancy can be further reduced when k ≪ 3.

In this paper, we present an explicit construction of list-decodable codes for single-deletion and single-substitution with list size two and redundancy 3log n+4, where n is the block length of the code. Our construction has lower redundancy than the best known explicit construction by Gabrys et al. (arXiv 2021), whose redundancy is 4log n + O(1).

Abstract The error‐correcting performance of multi‐level‐cell (MLC) NAND flash memory is closely related to the block length of error‐correcting codes (ECCs) and log‐likelihood‐ratios of the read‐voltage thresholds. Driven by this issue, this paper optimizes the read‐voltage thresholds for MLC flash memory to improve the decoding performance of ECCs with finite block length. First, through the analysis of channel coding rate and decoding error probability under finite block length, the optimization problem of read‐voltage thresholds to minimize the maximum decoding error probability is formulated. Second, a cross‐iterative search algorithm to optimize read‐voltage thresholds under the perfect knowledge of flash memory channel is developed. However, it is challenging to analytically characterize the voltage distribution under the effect of data retention noise. To address this problem, a deep neural network (DNN)‐aided optimization strategy to optimize the read‐voltage thresholds is developed, where a multi‐layer perception network is employed to learn the relationship between voltage distribution and read‐voltage thresholds. Simulation results show that, compared with the existing schemes, the proposed DNN‐aided read‐voltage threshold optimization strategy with a well‐designed Low Density Parity Check (LDPC) code can not only improve the program‐and‐erase endurance but also reduce the read latency.

Resistive random-access memory is one of the most promising candidates for the next generation of non-volatile memory technology. However, its crossbar array structure causes severe “sneak-path” interference, which also leads to strong inter-cell correlation. Recent works have mainly focused on sub-optimal data detection schemes by ignoring inter-cell correlation and assuming sneak-path interference is independent between different array cells. In this paper, we propose a near-optimal data detection scheme that can approach the performance bound of the optimal detection scheme. Our detection scheme leverages a joint data and sneak-path interference recovery and can use all inter-cell correlations. The proposed scheme is suitable for data detection of large memory arrays with only linear operation complexity.

Despite the great promises that the resistive random access memory (ReRAM) has shown as the next generation of non-volatile memory technology, its crossbar array structure leads to a severe sneak path interference to the signal read back from the memory cell. In this paper, we first propose a novel belief propagation (BP) based detector for the sneak path interference in ReRAM. Based on the conditions for a sneak path to occur and the dependence of the states of the memory cells that are involved in the sneak path, a Tanner graph for the ReRAM channel is constructed, inside which specific messages are updated iteratively to get a better estimation of the sneak path affected cells. We further combine the graph of the designed BP detector with that of the BP decoder of the polar codes to form a joint detector and decoder. Tailored for the joint detector and decoder over the ReRAM channel, effective polar codes are constructed using the genetic algorithm. Simulation results show that the BP detector can effectively detect the cells affected by the sneak path, and the proposed polar codes and the joint detector and decoder can significantly improve the error rate performance of ReRAM.

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. The common setup assumes the codebook to be the entire space and the problem is to determine the minimum number of distinct reads that is required to reconstruct the transmitted codeword. Motivated by modern storage devices, we study a variant of the problem where the number of noisy reads$N$is fixed. Specifically, we designreconstruction codesthat reconstruct a codeword from$N$distinct noisy reads. We focus on channels that introduce a single edit error (i.e. a single substitution, insertion, or deletion) and their variants, and design reconstruction codes for all values of$N$. In particular, for the case of a single edit, we show that as the number of noisy reads increases, the number of redundant symbols required can be gracefully reduced from$\log _{q} n+O(1)$to$\log _{q} \log _{q} n+O(1)$, and then to$O(1)$, where$n$denotes the length of a codeword. We also show that these reconstruction codes are asymptotically optimal. Finally, via computer simulations, we demonstrate that in certain cases, reconstruction codes can achieve similar performance as classical error-correcting codes with less redundant symbols.

Consider the computations at a node in a message passing algorithm. Assume that the node has incoming and outgoing messages$\mathbf {x} = (x_{1}, x_{2}, \ldots, x_{n})$and$\mathbf {y} = (y_{1}, y_{2}, \ldots, y_{n})$, respectively. In this paper, we investigate a class of structures that can be adopted by the node for computing$\mathbf {y}$from$\mathbf {x}$, where each$y_{j}, j = 1, 2, \ldots, n$is computed via a binary tree with leaves$\mathbf {x}$excluding$x_{j}$. We make three main contributions regarding this class of structures. First, we prove that the minimum complexity of such a structure is$3n - 6$, and if a structure has such complexity, its minimum latency is$\delta + \lceil \log (n-2^{\delta }) \rceil $with$\delta = \lfloor \log (n/2) \rfloor $, where the logarithm always takes base two. Second, we prove that the minimum latency of such a structure is$\lceil \log (n-1) \rceil $, and if a structure has such latency, its minimum complexity is$n \log (n-1)$when$n-1$is a power of two. Third, given$(n, \tau)$with$\tau \geq \lceil \log (n-1) \rceil $, we propose a construction for a structure which we conjecture to have the minimum complexity among structures with latencies at most$\tau $. Our construction method runs in$O(n^{3} \log ^{2}(n))$time, and the obtained structure has complexity at most (generally much smaller than)$n \lceil \log (n) \rceil - 2$.

We consider construction of deletion and substitution correcting codes with low redundancy and efficient encoding/ decoding. First, by simplifying the method of Simaet al. (ISIT 2020), we construct a family of binary single-deletion$s$-substitution correcting codes with redundancy$(s+1) (2s+1)\log _{2} n+o(\log _{2} n)$and encoding complexity$O(n^{2})$, where$n$is the blocklength of the code and$s\geq 1$. The construction can be viewed as a generalization of Smagloyet al.’s construction (ISIT 2020), and for the special case of$s=1$, our construction is a slight improvement in redundancy of the existing works. Further, we modify the syndrome compression technique by combining a precoding process and construct a family of systematic$t$-deletion$s$-substitution correcting codes with polynomial time encoding/decoding algorithms for both binary and nonbinary alphabets, where$t\geq 1$and$s\geq 1$. Specifically, our binary$t$-deletion$s$-substitution correcting codes of length$n$have redundancy$(4t+3s)\log _{2}n+o(\log _{2}n)$, whereas, for$q$being a prime power, the redundancy of$q$-ary$t$-deletion$s$-substitution codes is asymptotically$\left({4t+4s-1-\lfloor \frac {2s-1}{q}\rfloor }\right)\vphantom {{\lfloor \frac {2s-1}{q}\rfloor }_{j}}\log _{q} n + o(\log _{q}n)$as$n\to \infty $. We also construct a family of binary systematic$t$-deletion correcting codes (i.e.,$s=0$) with redundancy$(4t-1)\log _{2} n+o(\log _{2} n)$. The proposed constructions improve upon the redundancy of the state-of-the-art constructions.

We study segmented edit channels where the channel input is divided into disjoint segments, and each segment suffers at most one error, either a deletion or an insertion. The model was first introduced by Liu and Mitzenmacher [2010] over the binary alphabet, and was extended for the q-ary alphabet by Abroshan et al. [2018]. In this work, we first propose an efficient construction for segments with less redundancy than previous works, hence significantly improving the redundancy over the entire sequence, for any q-ary alphabet where$q$≥ 3. Additionally, motivated by the applications of constrained codes in DNA-based data storage systems and energy harvesting communication channels, to reduce the probability of having errors, we also impose certain weight constraints in every segment instead of over the whole sequence. In particular, for DNA storage systems, besides error correction capability, our coding method guarantees that all segments in every codeword are almost GC-balanced.

In this work, given$n, p > 0$, efficient encoding/decoding algorithms are presented for mapping arbitrary data to and from$n\times n$binary arrays in which the weight of every row and every column is at most$pn$. Such constraint, referred as$p$-bounded-weight-constraint, is crucial for reducing the parasitic currents in the crossbar resistive memory arrays, and has also been proposed for certain applications of the holographic data storage. While low-complexity designs have been proposed in the literature for only the case$p=1/2$, this work provides efficient coding methods that work for arbitrary values of$p$. The coding rate of our proposed encoder approaches the channel capacity for all$p$.

The sneak path (SP) interference problem in resistive random access memory (ReRAM) severely affects the data storage reliability. Recent works showed that the occurrence of the SP is highly related to the selector failures (SFs) in the resistive memory arrays. In this work, we propose a novel scheme to detect the location of the failed selector, based on the signal read back from the memory array. The detected SF location information can be used to assist the data detection to mitigate the SP interference or to construct SP-free constrained codes.

In this paper, by applying the precoding technique in conjunction with the syndrome compression approach, we construct systematic$t$-deletion$s$-substitution correcting codes, where$t$and$s$are fixed positive integers. The redundancy of our construction is$(4t+3s)\log n+o(\log n)$for the binary case and$(4t+4s-1- \mathrm{L}\frac{2s-1}{q}\rfloor)\bar{\mathrm{l}}\text{og}_{q}n+o(\bar{\mathrm{l}}\text{og}_{q}n)$for the$q$-ary case, where$n$is the length of the codes and$q> 2$is a fixed prime power.11If$x$is a positive real number, then$\log_{q}\alpha$is the logarithm of$x$with base$q$; if$q=2$, we simply denote$\log x=\text{lo}\bar{\mathrm{g}}_{q}x$. We also construct binary t-deletion correcting codes (i.e.,$s=0$) with redundancy$(4t-1)\log n+o(\log n)$. The encoding/decoding complexities of all constructions are polynomial in$n$.

In this article, under a general cost function C, we present a dynamic programming (DP) method to obtain an optimal sequential deterministic quantizer (SDQ) for q-ary input discrete memoryless channel (DMC). The DP method has complexity O(q (N-M)2M), where N and M are the alphabet sizes of the DMC output and quantizer output, respectively. Then, starting from the quadrangle inequality, two techniques are applied to reduce the DP method's complexity. One technique makes use of the Shor-Moran-Aggarwal-Wilber-Klawe (SMAWK) algorithm and achieves complexity O(q (N-M) M). The other technique is much easier to be implemented and achieves complexity O(q (N2- M2)). We further derive a sufficient condition under which the optimal SDQ is optimal among all quantizers and the two techniques are applicable. This generalizes the results in the literature for binary-input DMC. Next, we show that the cost function of α-mutual information ( α-MI)-maximizing quantizer belongs to the category of C. We further prove that under a weaker condition than the sufficient condition we derived, the aforementioned two techniques are applicable to the design of α-MI-maximizing quantizer. Finally, we illustrate the particular application of our design method to practical pulse-amplitude modulation systems.

This paper investigates a cache-aided cloud radio access network (C-RAN), comprising a central unit, K base stations (BSs) each with NTantennas, and M users each with NRantennas, where each BS and user have local caches to store some popular contents from the central unit. For this cache-aided network, we propose the linear network coded (NC) wireless caching that consists of linear wireless network coding assisted cache placement phase and signal-space alignment (SSA) enabled content delivery phase. In the cache placement phase, we design a joint NC caching function at the BSs to store linear combinations of messages from the central unit, as a form of linear wireless network coding. In the content delivery phase, we design the SSA pattern based on the NC caching to guide the precoding designs at BSs. Then, each user can reliably decode its requested messages by receiver shaping and reverse NC operation. The primary contribution of this work is to achieve the coding gain induced by the integration of linear wireless network coding and SSA, which has been not exploited in the field of wireless coded caching. In particular, to deal with high temporal variability of user requests, we show that the proposed cache placement is invariant to different user requests in the worst-case caching, without any shared caching messages at different BSs. Furthermore, we verify that the proposed scheme is also compatible with the insufficient caching scenario at the BSs. In addition, we analyze the achievable sum degrees of freedom (DoF) for the proposed caching network. Both analytical and numerical results verify that the proposed caching scheme achieves a higher sum DoF than the existing related works.

Resistive random-access memory (ReRAM) is a promising candidate for the next generation non-volatile memory technology due to its simple read/write operations and high storage density. However, its crossbar array structure causes a severe interference effect known as the “sneak path.” In this paper, we propose channel coding techniques that can mitigate both the sneak-path interference and the channel noise. The main challenge is that the sneak-path interference is data-dependent, and also correlated within a memory array, and hence the conventional error correction coding scheme will be inadequate. In this work, we propose an across-array coding strategy that assigns a codeword to multiple independent memory arrays, and exploit a real-time channel estimation scheme to estimate the instantaneous status of the ReRAM channel. Since the coded bits from different arrays experience independent channels, a “diversity” gain can be obtained during decoding, and when the codeword is adequately distributed over different memory arrays, the code actually performs as that over an uncorrelated channel. By performing decoding based on the scheme of treating-interference-as-noise (TIN), the ReRAM channel over different memory arrays is equivalent to a block varying channel we defined, for which we propose both the capacity bounds and a coding scheme. The proposed coding scheme consists of a serial concatenation of an optimized error correction code with a data shaper, which enables the ReRAM system to achieve a near capacity limit storage efficiency.

An indel refers to a single insertion or deletion, while an edit refers to a single insertion, deletion or substitution. In this article, we investigate codes that correct either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with ⌈log n⌉+ O(loglog n) redundancy bits, while the other corrects a single indel with ⌈log n⌉+2 redundant bits. These two encoders are order-optimal. The former encoder is the first known order-optimal encoder that corrects a single edit, while the latter encoder (that corrects a single indel) reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, we impose an additional constraint: the GC-balanced constraint and require that exactly half of the symbols of any DNA codeword to be either C or G. In particular, via a modification of Knuth's balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single indel or a single edit. These are the first known constructions of GC-balanced codes that correct a single indel or a single edit.

The subblock energy-constrained codes (SECCs) and sliding window-constrained codes (SWCCs) have recently attracted attention due to various applications in communication systems such as simultaneous energy and information transfer. In a SECC, each codeword is divided into smaller non-overlapping windows, called subblocks, and every subblock is constrained to carry sufficient energy. In a SWCC, however, the energy constraint is enforced over every window. In this work, we focus on the binary channel, where sufficient energy is achieved theoretically by using relatively high weight codes, and study the bounded SECCs and bounded SWCCs, where the weight in every window is bounded between a minimum and maximum number. Particularly, we focus on the cases of parameters that there is no rate loss, i.e. the channel capacity is one, and propose two methods to construct capacity-approaching codes with low redundancy and linear-time complexity, based on Knuth’s balancing technique and sequence replacement technique. These methods can be further extended to construct SECCs and SWCCs. For certain codes parameters, our methods incur only one redundant bit. We also impose the minimum distance constraint for error correction capability of the designed codes, which helps to reduce the error propagation during decoding as well.

We propose coding techniques that simultaneously limit the length of homopolymers runs, ensure the GC-content constraint, and are capable of correcting a single edit error in strands of nucleotides in DNA-based data storage systems. In particular, for givenl, ∈ > 0, we propose simple and efficient encoders/decoders that transform binary sequences into DNA base sequences (codewords), namely sequences of the symbols A, T, C and G, that satisfy all of the following properties: 1) runlength constraint: the maximum homopolymer run in each codeword is at mostl; 2) GC-content constraint: the GC-content of each codeword is within [0.5-∈,0.5+∈]; 3) error-correction: each codeword is capable of correcting a single deletion, or single insertion, or single substitution error. While various combinations of these properties have been considered in the literature, this work provides generalizations of codes constructions that satisfy all the properties with arbitrary parameters ofland ∈. Furthermore, for practical values ofland ∈, we show that our encoders achieve higher rates than existing results in the literature and approach capacity. Our methods have low encoding/decoding complexity and limited error propagation.

In this paper, we propose channel coding techniques that can mitigate both the sneak-path interference and the channel noise for resistive random-access memory (ReRAM) channels. The main challenge is that the sneak-path interference is data-dependent, and also correlated within a memory array, and hence the conventional error correction coding scheme will be inadequate. We propose an across-array coding scheme, which assigns a code-word to multiple independent memory arrays. Since the coded bits from different arrays experience independent channels, a “diversity” gain can be obtained during decoding, and when the code-word is adequately distributed over different memory arrays, the code actually performs as that over an uncorrelated channel. We also present a real-time channel estimation scheme together with an elementary signal estimator (ESE) to obtain the instant channel status as well as the soft information of the channel coded bits for decoding. By further combining with a data shaping technique to produce an optimized channel input distribution, significant error performance gain is obtained.

A nucleotide substitution is said to occur when a base in {A, T} is substituted for a base in {C, G}, or vice versa. Recent experiment (Heckel et al. 2019) showed that a nucleotide substitution occurs with a significantly higher probability than other substitution errors. A nucleotide edit refers to a single insertion, deletion or nucleotide substitution. In this paper, we investigate codes that corrects a single nucleotide edit and provide linear-time algorithms that encode binary messages into these codes of length n. Specifically, we provide an order-optimal encoder which corrects a single nucleotide edit with log n + log log n + O(1) redundant bits. We also demonstrate that the codewords obey certain runlength constraints and that the code can be modified to accommodate certain GC-content constraints..

The subblock energy-constrained codes (SECCs) have recently attracted attention due to various applications in communication systems such as simultaneous energy and information transfer. In a SECC, each codeword is divided into smaller subblocks, and every subblock is constrained to carry sufficient energy. In this work, we study SECCs under more general constraints, namely bounded SECCs and sliding-window constrained codes (SWCCs), and propose two methods to construct such codes with low redundancy and linear-time complexity, based on Knuth's balancing technique and sequence replacement technique. For certain codes parameters, our methods incur only one redundant bit.

In this paper, we first propose coding techniques for DNA-based data storage which account the maximum homopolymer runlength and the GC-content. In particular, for arbitrary ℓ,ε>0, we propose simple and efficient (ℓ,ε)-constrained encoders that transform binary sequences into DNA base sequences (codewords), that satisfy the following properties: · Runlength constraint: the maximum homopolymer run in each codeword is at most ℓ, · GC-content constraint: the GC-content of each codeword is within [0.5-ε, 0.5+ε]. For practical values of ℓ and ε, our codes achieve higher rates than the existing results in the literature. We further design efficient (ℓ, ε)-constrained codes with error-correction capability. Specifically, the designed codes satisfy the runlength constraint, the GC-content constraint, and can correct a single edit (i.e. a single deletion, insertion, or substitution) and its variants. To the best of our knowledge, no such codes are constructed prior to this work.

Motivated by the application of fountain codes in the DNA-based data storage systems, in this paper, we propose the basis-finding algorithm (BFA) for decoding fountain codes for an erasure-error channel where each received symbol has a fixed probability to be correct. The key idea of the BFA is to find a basis of the received symbols, and then use the most reliable basis elements to recover the source symbols with the inactivation decoding. Gaussian elimination can be used to find the basis and to identify the most reliable basis elements. For random fountain codes, we are able to derive some theoretical bounds for the frame error rate (FER) of the BFA, which reveal that the BFA can perform very well for decoding fountain codes for the considered channel.

The protograph low‐density parity‐check (LDPC) codes possess many attractive properties, such as the low encoding/decoding complexity and better error floor performance, and hence have been successfully applied to different types of communication and data storage channels. In this study, the authors design protograph LDPC codes for communication systems corrupted by the impulsive noise, which are modelled as additive white symmetric alpha‐stable noise (AWS SN) channels. They start by presenting a novel simulation‐based protograph extrinsic information transfer analysis to derive the iterative decoding threshold of the protograph codes. By further applying the asymptotic weight distribution analysis, the authors design new protograph codes for the AWS SN channel. Both theoretical analysis and simulation results demonstrate that the proposed protograph codes can provide better error rate performance than the prior art AR4JA code, the irregular codes optimised for the AWGN channel, as well as the irregular codes optimised for the AWS SN channel.

The practical NAND flash memory suffers from various non-stationary noises that are difficult to be predicted. For example, the data retention noise induced channel offset is unknown during the readback process, and hence severely affects the reliability of data recovery from the memory cell. In this paper, we first propose a novel recurrent neural network (RNN)-based detector to effectively detect the data stored in the multi-level-cell (MLC) flash memory without the prior knowledge of the channel. However, compared with the conventional threshold detector, the proposed RNN detector introduces much longer read latency and more power consumption. To tackle this problem, we further propose an RNN-aided (RNNA) dynamic threshold detector, whose detection thresholds can be derived based on the outputs of the RNN detector. We thus only need to activate the RNN detector periodically when the system is idle. Moreover, to enable soft-decision decoding of error-correction codes, we first show how to obtain more read thresholds based on the hard-decision read thresholds derived from the RNN detector. We then propose integer-based reliability mappings based on the designed read thresholds, which can generate the soft information of the channel. Finally, we propose to apply density evolution (DE) combined with the differential evolution algorithm to optimize the read thresholds for low-density parity-check (LDPC) coded flash memory channels. Computer simulation results demonstrate the effectiveness of our proposed RNNA dynamic read thresholds design, for both the uncoded and LDPC-coded flash memory channels, without any prior knowledge of the channel.

A very low-complexity on-off division multiple access (ODMA) scheme is proposed for K-user non-orthogonal multiple access (NOMA) systems. At the transmission side, each user employs the same length-m channel code whose coded bits, after modulation, are sent in a random time-hopping manner. Specifically, m coded bits are randomly scheduled and sent using n time slots with n≫m, i.e., only m slots are used for signal transmission and the other n- m slots are idle. The slot selection, referred to as an on-off pattern, is unique to each user, and it is the only means of user separation. Consequently, at each time slot only a very few users (i.e., 2 or 3) may simultaneously access the channel, leading to a super-sparse access system. Due to the sparse access property, a very low-complexity iterative multi-user decoding method can be implemented on an almost tree-like factor graph. Compared with existing iteratively decodable code division multiple access (CDMA) schemes, such as sparse-CDMA and interleave division multiple access (IDMA), ODMA does not rely on repetition (spreading) or user interleaving. In fact, we show that in using extrinsic information transfer (EXIT) analysis and simulation, idling is more effective than repetition in terms of enhancing the multi-user iterative decoding performance. By replacing repetition with idling, a remarkable multi-user decoding performance gain is achieved and, at the same time, the decoding complexity is significantly reduced.

The process of DNA-based data storage (DNA storage for short) can be mathematically modelled as a communication channel, termed DNA storage channel, whose inputs and outputs are sets of unordered sequences. To design error correcting codes for DNA storage channel, a new metric, termed the sequence-subset distance, is introduced, which generalizes the Hamming distance to a distance function defined between any two sets of unordered vectors and helps to establish a uniform framework to design error correcting codes for DNA storage channel. We further introduce a family of error correcting codes, referred to as sequence-subset codes, for DNA storage and show that the error-correcting ability of such codes is completely determined by their minimum distance. We derive some upper bounds on the size of the sequence-subset codes including a tight bound for a special case, a Singleton-like bound and a Plotkin-like bound. We also propose some constructions, including an optimal construction for that special case, which imply lower bounds on the size of such codes.

A severe problem for mutual information-maximizing lookup table (MIM-LUT) decoding of low-density parity-check (LDPC) code is the high memory cost for using large tables, while decomposing large tables to small tables deteriorates decoding error performance. In this paper, we propose a systematic method, called mutual information- maximizing quantized belief propagation (MIM-QBP) decoding, to remove the lookup tables used for MIM-LUT decoding. Our method leads to a very practical decoder, namely the MIM-QBP decoder, which can be implemented based only on simple mappings and additions. Simulation results show that the proposed MIM-QBP decoder can outperform the state-of-the-art MIM-LUT decoder. Moreover, the MIM-QBP decoder with only 3 bits per message can outperform the floating-point belief propagation (BP) decoder at high signal-to-noise ratio (SNR) regions with a maximum of 10 iterations.

Mobile edge computing (MEC) enables feasible and scalable computation services for delay-sensitive and delay-tolerant tasks from mobile users. This paper considers an MEC network that consists of multiple users, multiple edge nodes (ENs), and a remote cloud computing server, where the ENs and the cloud server execute the delay-sensitive and delay-tolerant tasks respectively. First, we propose a unified linear network coded (NC) task offloading policy at the ENs to either execute the delay-sensitive tasks or assist the cloud server in the execution of delay-tolerant tasks. For the delay-sensitive task, the users jointly precode their task input messages according to a signal space alignment pattern, such that each EN can compute the linear NC messages for its intended user. For the delay-tolerant task, we put forth a compute-and-upload strategy for the ENs to upload their computed NC messages to the cloud server, such that the cloud server can first recover the input messages from all users and then execute the computation. Second, we develop the EN computation rules for different types of tasks. Finally, we characterize the computation load and normalized uploading time for the proposed task offloading. Our analytical results show that the proposed task offloading scheme is applicable to different NC computation with flexible requirements on computation load and uploading time.

The memory physics induced unknown offset of the channel is a critical and difficult issue to be tackled for many non-volatile memories (NVMs). In this paper, we first propose novel neural network (NN) detectors by using the multilayer perceptron (MLP) network and the recurrent neural network (RNN), which can effectively tackle the unknown offset of the channel. However, compared with the conventional threshold detector, the NN detectors will incur a significant delay of the read latency and more power consumption. Therefore, we further propose a novel dynamic threshold detector (DTD), whose detection threshold can be derived based on the outputs of the proposed NN detectors. In this way, the NN-based detection only needs to be invoked when the error correction code (ECC) decoder fails, or periodically when the system is in the idle state. Thereafter, the threshold detector will still be adopted by using the adjusted detection threshold derived base on the outputs of the NN detector, until a further adjustment of the detection threshold is needed. Simulation results demonstrate that the proposed DTD based on the RNN detection can achieve the error performance of the optimum detector, without the prior knowledge of the channel.

In this paper, we present a general framework of applying dynamic programming (DP) to the sequential deterministic quantization for discrete memoryless channels (DMCs) with pre-labelled outputs. The DP has complexity O(q(N -M)2M), where q, N, and M are alphabet sizes of the DMC input, DMC output, and the quantizer output, respectively. Then, starting from the quadrangle inequality (QI), we apply two techniques to reduce the DP's complexity. One technique makes use of the SMAWK algorithm with complexity O(q(N - M)M), while the other technique is much easier to be implemented and has complexity O(q(N2- M2)). Moreover, we give a sufficient condition on the channel transition probability, under which the two low-complexity techniques can be applied for designing quantizers that maximize the α-mutual information, which is a generalized objective function for channel quantization. This condition works for the general q-ary input case, including the previous work for q = 2 as a subcase.

We introduce a new metric, termed sequence-subset distance, and a new family of codes with respect to this new metric, termed sequence-subset codes, on the power set of the set of all sequences of the same length over a finite alphabet. This new metric and family of codes are motivated by the problem of designing error correcting codes for DNA-based data storage, which can be mathematically modelled as a communication channel whose inputs and outputs are sets of unordered sequences. We derive some upper bounds on the size of the sequence-subset codes including a tight bound for a special case and a Singleton-like bound, and present some constructions of such codes.

We apply the central limit theorem for deriving approximations to the auto-correlation function and power density function (spectrum) of second-order spectral null (dc2-balanced) codes. We show that the auto-correlation function of dc2-balanced codes can be accurately approximated by a cubic function. We show that the difference between the approximated and exact spectrum is less than 0.03 dB for codeword length n=256.

As emerging memories such as spin-torque transfer magnetic random access memory (STT-MRAM) suffer from reliability issues caused by process variations and thermal fluctuations, the design of channel quantizer with the minimum number of quantization bits is critical to support effective error correction coding for ensuring high-density and high-speed memory data storage. In this paper, we first propose a quantized channel model for STT-MRAM. Based on the quantized channel model, we derive various information theoretic bounds, including the mutual information, cutoff rate, and the Polyanskiy-Poor-Verdú (PPV) finite-length performance bound. By using these bounds as design criteria, we optimize the quantizer design for the polar-coded STT-MRAM channel. Moreover, we also propose a polar-code-specific quantization design with the successive cancellation decoding algorithm, by using the block error probability bound obtained from density evolution (DE). Simulation results show that all our proposed quantizers generally outperform the prior art greedy merging quantizer. In addition, both the cutoff rate and PPV bound based quantizers outperform the most widely applied mutual information based quantizer for short-length polar codes with 2-bit quantization. Furthermore, the DE quantizer designed specifically for polar codes achieves the best performance among all the proposed quantizers.

Multilevel flash memories enable multiple bits to be stored in a single memory cell and hence a significant increase of the storage capacity. The multiple bits that are used for labeling the threshold voltage level of a memory cell belong to different pages. A multilevel flash memory channel resembles a multi-user channel with asymmetric noise, while the data of different pages, which are encoded independently, resembles data of multiple users. In this paper, performance analyses are proposed for this channel by using the union bound technique. In particular, we investigated two different binary labeling schemes of a cell level, the Gray labeling and non-Gray labeling with three maximum-likelihood (ML)-based decoding schemes, which are the joint multi-page ML decoding, page-separate ML decoding, and default setting ML decoding. Our analysis reveals an asymptotic diminishing rate of decoding errors as the channel noise approaches zero, based on which the code design criteria are proposed. It is shown theoretically that the Gray mapping has no joint (i.e., multi-page) decoding gain. The corresponding diminishing decoding error rate is dominated by the weakest code in each page and hence a separate decoding scheme is adequate. On the other hand, the non-Gray mapping has a joint decoding gain which means the weak code can exploit the decoding of the strong code and the diminishing rate of its decoding errors is not subject to the cask effect. Therefore, for Gray mapping, a symmetric coding scheme using equal-strength code for each page achieves better error performance, while for non-Gray mapping with joint decoding, the symmetric coding is not necessary. Moreover, by using the asymmetric coding scheme through assigning different code rates to different pages, the non-Gray mapping can achieve higher overall sum rate than Gray mapping with a similar decoding error rate performance.

We prove that for any positive integers n and k such that n ≥ k ≥ 1, there exists an [n, k] generalized Reed-Solomon (GRS) code that has a sparsest and balanced generator matrix (SBGM) over any finite field of size q ≥ n+[(k(k-1))/n], where sparsest means that each row of the generator matrix has the least possible number of nonzeros, while balanced means that the number of nonzeros in any two columns differ by at most one. Previous work by Dau et al (ISIT'13) showed that there always exists an MDS code that has an SBGM over any finite field of size q ≥ \binomn-1k-1 I, and Halbawi et al (ISIT'16, ITW'16) showed that there exists a cyclic Reed-Solomon code (i.e., n=q-1) with an SBGM for any prime power q. Hence, this work extends both of the previous results.

We investigate machine learning based on clustering techniques that are suitable for the detection of n-symbol words of q-ary symbols transmitted over a noisy channel with partially unknown characteristics. We consider the detection of the n-symbol q-ary data as a classification problem, where objects are recognized from a corrupted vector, which is obtained by an unknown corruption process.

For the problem of multiple users simultaneously communicating with a single receiver, a sparse multiple access scheme is proposed. Each user employs a low-density parity-check (LDPC) code. To mitigate multi-user interference, the codeword of each user is randomly punctured and the punctured bits are replaced by idle slots. That is, only a small random set of users are active at each time. The restriction of number of concurrent users significantly reduces the multi-user decoding complexity. Moreover, this puncture facilitates an efficient message-passing decoding over a sparse graph. With a joint optimization of the degree distribution of the LDPC code and the column weight distribution of the puncture matrix, capacity-approaching performance is achieved.

Codes with locality, also known as locally repairable codes (LRC), are designed for distributed storage systems (DSS) to reduce the disk I/O complexity for node repair. A linear code is said to have (r, δ)-locality if each code symbol is contained in a local code of length ≤ r + δ - 1 and minimum distance ≥ δ. For such codes, a generalized Singleton bound of the minimum distance was proven by Prakash et al (ISIT'12).In this paper, we consider the problem of constructing optimal codes with (r, δ)-locality. Specifically, we present three classes of linear codes that have (r, δ)-locality and whose minimum distance achieves the generalized Singleton bound. For δ = 2, we provide a combinatorial description of the largest possible d such that there exists a linear code with (r, δ)-locality and minimum distance d.

This paper presents novel soft-decision decoding (SDD) of error correction codes (ECCs) that substantially improve the reliability of DNA-based data storage system compared with conventional hard-decision decoding (HDD). We propose a simplified system model for DNA-based data storage according to the major characteristics and different types of errors associated with the prevailing DNA synthesis and sequencing technologies. We compute analytically the error-free probability of each sequenced DNA oligonucleotide (oligo), based on which the soft-decision log-likelihood ratio (LLR) of each oligo can be derived. We apply the proposed SDD algorithms to the recently proposed DNA Fountain scheme. Simulation results show that SDD achieves an error rate improvement of two to three orders of magnitude over HDD, thus demonstrating its potential to improve the information density of DNA-based data storage systems.

Channel output quantization plays a vital role in high-speed emerging memories such as the spin-torque transfer magnetic random access memory (STT-MRAM), where high-precision analog-to-digital converters (ADCs) are not applicable. In this paper, we investigate the design of the 1-bit quantizer which is highly suitable for practical applications. We first propose a quantized channel model for STT-MRAM. We then analyze various information theoretic bounds for the quantized channel, including the channel capacity, cutoff rate, and the Polyanskiy-Poor-Verdu ́(PPV) finite-length performance bound. By using these channel measurements as criteria, we design and optimize the 1-bit quantizer numerically for the STTMRAM channel. Simulation results show that the proposed quantizers significantly outperform the conventional minimum mean-squared error (MMSE) based Lloyd-Max quantizer, and can approach the performance of the 1-bit quantizer optimized by error rate simulations.

We consider the transmission and storage of encoded strings of symbols over a noisy channel, where dynamic threshold detection is proposed for achieving resilience against unknown scaling and offset of the received signal. We derive simple rules for dynamically estimating the unknown scale (gain) and offset. The estimates of the actual gain and offset so obtained are used to adjust the threshold levels or to re-scale the received signal within its regular range. Then, the re-scaled signal, brought into its standard range, can be forwarded to the final detection/decoding system, where optimum use can be made of the distance properties of the code by applying, for example, the Chase algorithm. A worked example of a spin-torque transfer magnetic random access memory with an application to an extended (72, 64) Hamming code is described, where the retrieved signal is perturbed by additive Gaussian noise and unknown gain or offset.

This paper addresses binary message-passing (MP) decoding for nonbinary low-density parity-check (NB-LDPC) codes based on the binary image of Galois field symbols. The parity-check matrix of NB-LDPC codes in binary form is used to perform MP. The corresponding nonbinary check node (CN) update and variable node (VN) update can thus be decomposed to a set of binary sub-CN updates and sub-VN updates with much lower computational complexity. In particular, we start from adapting the binary parity-check matrix with Gaussian elimination. Then, we add redundant rows to the parity-check matrix instead of adaptation to further improve the performance. A min-max operation based on the expanded matrix is proposed for the CN update. It not only decreases the computational complexity incurred by Gaussian elimination but also improves the error performance. Simulation results show that the bit-level decoding with min-max operation can achieve similar error performance as the extended min-sum algorithm, but the computational complexity can be lower than the min-sum algorithm for binary LDPC codes.

We present composition check codes for noisy storage and transmission channels with unknown gain and/or offset. In the proposed composition check code, like in systematic error correcting codes, the encoding of the main data into a constant composition code is completely avoided. To the main data, a coded label is appended that carries information regarding the composition vector of the main data. Slepian's optimal detection technique of codewords that are taken from a constant composition code is applied for detection. A first Slepian detector detects the label and subsequently restores the composition vector of the main data. The composition vector, in turn, is used by a second Slepian detector to optimally detect the main data. We compute the redundancy and error performance of the new method, and results of computer simulations are presented.

We consider the locally repairable codes (LRCs), aiming at sequentially recovering multiple erasures; in particular, we propose and study the so-called (n, k, r, t)-sequential LRCs (SLRC) as an [n, k] linear code, where any t' (≤ t) erasures can be sequentially recovered, each by r (2 ≤ r <; k) other code symbols. Here, sequential recovering means that the erased symbols are recovered one by one, and an already recovered symbol can be used to recover the remaining erased symbols. This important recovering method, in contrast with the extensively studied parallel recovering, is currently far from being thoroughly understood; more specifically, there are to date no codes constructed for arbitrary t ≥ 3 erasures and bounds to evaluate the performance of such codes. We first derive a tight upper bound on the code rate of the (n, k, r, t)-SLRC for t = 3 and r ≥ 2. We then propose two constructions of binary (n, k, r, t)-SLRCs for general r, t ≥ 2 (existing constructions only deal with t ≤7 erasures). The first construction generalizes the method of direct product construction. The second construction is based on the resolvable configurations and yields SLRCs for any r ≥ 2 odd t ≥ 3. For both constructions, the rates are optimal for t ∈ {2, 3} and are higher than most of the existing LRC families for arbitrary t ≥ 4.

This paper considers a multiuser communication network, where a receiver is set to compute functions of the messages from K users. All user nodes and the receiver are equipped with multi-antenna. We propose a space-time (ST) coded multiple-input multiple-output (MIMO) linear physical-layer network coding (LPNC) scheme that promises full-rate and full-diversity, while achieving the maximum coding gain of LPNC. In the proposed framework, the users' messages are encoded by the same linear dispersion ST code and transmitted simultaneously. The receiver exploits the MIMO LPNC mapping in reconstructing an arbitrary number of linearly network-coded (NC) messages. We derive the NC generator matrix that leads to the greatest coding gain and minimized error probability at the receiver. On top of that, we analytically show that the proposed ST coded LPNC scheme guarantees the full-diversity and full-rate transmission. The proposed method applies to a wide range of network configurations. Two case studies on: (1) MIMO two-way relay network and (2) MIMO multiple-access relay network are presented in this paper. For both case studies, numerical results are shown to demonstrate the performance improvement of the proposed scheme over conventional schemes by more than 4 dB, while the full-rate and full-diversity behaviors are in line with our analysis.

A union bound analysis is given for codes over binary asymmetric channels. By considering a random mapping that modulates each coded bit equiprobably to the signal constellation point, an average union bound is derived explicitly as a function of the code's weight spectrum. The bound can be used for estimating the error floor performance of maximum-likelihood decoding or near optimal decodings.

A union bound and its asymptotic analysis are presented for multilevel flash memory channels. The bound reveals an asymptotic decoding error behaviour under the maximum-likelihood decoding, based on which code design criteria are proposed.

This paper presents two low-complexity edge-based scheduling schemes, referred to as the e-Flooding and e-Shuffled schedules, for the belief-propagation (BP) decoding of low-density parity-check and Reed-Solomon codes. The proposed schedules selectively update the edges of the code graph based on the run-time reliability of variable and check nodes. Specifically, new message update is propagated exclusively along the unreliable edges of the code graph. This reduces the decoding complexity of BP algorithm as only a partial set of message updates is computed per decoding iteration. Besides, restricting the flow of message updates may also precludes the occurrence of some short graph cycles, which helps to preserve the BP message independence at certain variable and check nodes. Using numerical simulations, it is shown that the proposed edge-based schedules reduce the BP decoding complexity by more than 90% compared with the prior-art BP schedules, while simultaneously improving the error-rate performance, at medium-to-high signal-to-noise ratio over additive white Gaussian noise channel.

The multilevel-cell NAND flash memory experiences permanent hard errors due to cell defects (stuck cells). To overcome this problem, stuck cells are either regarded as erasures by the decoder based upon the knowledge of stuck cell location, or the entire memory block containing the stuck cells is marked as bad block and made unavailable for future usage. In this paper, a multiround inferred stuck-cell erasure belief-propagation (BP) decoding (ISED) is proposed in which the stuck cell locations are assumed to be unknown to the decoder. To perform the inferred erasure decoding, the input channel log-likelihood ratio (LLR) information is attenuated before BP decoding by modifying the threshold voltage distribution functions. In case of decoding failure, the probable stuck cell locations are inferred by using the flash's read-back voltage signal and the decoded code-word bits. For all such inferred stuck cells, the input LLRs are set to zero for subsequent rounds of BP decoding. As the likely incorrect LLRs corresponding to the stuck cells are erased, the performance of BP decoder is substantially improved. Simulation results show that the error-rate performance is improved by more than two orders of magnitude with a moderate increase in decoding complexity under the proposed ISED scheme.

In this study, the authors investigate the performance of iterative detection and decoding for non‐binary low‐density parity‐check (LDPC) coded partial‐response (PR) channels, where written‐in errors are present to introduce bit‐flipping to LDPC code bits prior to the transmission over PR channels. From a probabilistic perspective, the written‐in errors are modelled as the output of a binary symmetrical channel (BSC) with crossover probability equal to the write error probability. Several iterative receivers are presented for the considered system. Specifically, the authors propose a symbol‐level Bahl‐Cocke‐Jelinek‐Raviv (BCJR) channel detector based on a sectionalised representation of the joint BSC and PR trellis to produce directly the soft information of non‐binary LDPC code symbols, thus avoiding suboptimal symbol/bit log‐likelihood ratio conversions as required in bit‐level detection schemes. Simulation results show that the proposed symbol‐level iterative receiver provides much better bit‐error‐rate performance over bit‐level schemes. Moreover, the proposed receiver enables non‐binary LDPC codes to achieve a notable coding gain over their binary counterparts for channels affected with written‐in errors.

The multi-level-cell (MLC) NAND flash channel exhibits nonstationary behavior over increasing program and erase (PE) cycles and data retention time. In this paper, an optimization scheme for adjusting the read (quantized) and write (verify) voltage levels to adapt to the nonstationary flash channel is presented. Using a model-based approach to represent the flash channel, incorporating the programming noise, random telegraph noise (RTN), data retention noise and cell-to-cell interference as major signal degradation components, the write-voltage levels are optimized by minimizing the channel error probability. Moreover, for selecting the quantization levels for the read-voltage to facilitate soft LDPC decoding, an entropy-based function is introduced by which the voltage erasure regions (error dominating regions) are controlled to produce the lowest bit/frame error probability. The proposed write and read voltage optimization schemes not only minimize the error probability throughout the operational lifetime of flash memory, but also improve the decoding convergence speed. Finally, to minimize the number of read-voltage quantization levels while ensuring LDPC decoder convergence, the extrinsic information transfer (EXIT) analysis is performed over the MLC flash channel.

Cell-to-cell interference (CCI), arising from parasitic coupling-capacitance between adjacent cells, is a major factor for the degradation of cell threshold voltage in today's flash memory chips. In this paper, three novel postprocessing detection schemes that exploit the a priori information of neighboring/interfering cells for mitigating the CCI effect in multilevel cell NAND flash memory are presented. The proposed schemes are referred to as the Even-A-Priori (Even-AP), the All-A-Priori (All-AP), and the All-AP-coupling-capacitance ratio (CCR) detectors. The main idea is to remove the CCI component from the interfering cells before CCI cancellation from the victim cell. Specifically, the mean CCRs along the victim cell's vertical and diagonal directions are estimated to enable more accurate CCI cancellation. Performance analysis and simulation results show that the channel signal-to-noise ratio performance can be improved by up to 2 dB at a cell storage capacity of 1.8 bits/cell, which is significantly improved compared with some prior-art detection schemes.

In this paper, we propose an iterative symbol-level detection and decoding scheme for nonbinary low-density parity-check (LDPC) coded generalized two-dimensional (2D) intersymbol interference (ISI) channels. The proposed 2D channel detector consists of two constituent detectors that work iteratively to mitigate downtrack and crosstrack interference. The downtrack detector is based on the nonbinary BCJR algorithm; while the crosstrack detector performs the sum-product algorithm (SPA) over a cycle-free symbol-level factor graph of the crosstrack channel, which can be directly concatenated to the nonbinary LDPC code graph without resorting to bit/symbol log-likelihood ratio (LLR) conversions. Simulation results show that the proposed symbol-level receiver outperforms bit-level schemes and also enables nonbinary LDPC codes to achieve a noticeable performance gain over binary codes when transmitted over severely ISI-distorted 2D channels.

Non‐binary low‐density parity‐check (NB‐LDPC) codes can be directly constructed by using algebraic methods, or indirectly constructed by mapping well‐designed binary parity‐check matrices to non‐binary parity‐check matrices. Given the Tanner graph (TG) of a NB‐LDPC code, the selection of edge weights in the TG significantly affects the performance of the NB‐LDPC code. The authors introduce an edge weight distribution (EWD) parameter for the TG of NB‐LDPC codes. By utilising particle swarm optimisation (PSO), the EWD is optimised and it has been demonstrated that the optimal EWD approaches a two‐element distribution for large field size and high average variable‐node degree. With the optimised EWD, the authors construct a class of field‐compatible LDPC (FC‐LDPC) codes over GF( q ) whose parity‐check matrices only include elements 0, 1 and 2, and can be encoded and decoded over different field sizes. The simulations demonstrate that the performance of the proposed FC‐LDPC codes improves monotonically with increasing field size, and significantly outperforms that of the corresponding algebraic NB‐LDPC codes or NB‐LDPC codes generated with uniform distribution of non‐zero elements over GF( q ).

An algorithm based on the fitting of modified Extrinsic Information Transfer (EXIT) chart is proposed to calculate the thresholds of low-density parity-check (LDPC) codes optimized for the two-dimensional (2D) intersymbol interference (ISI) channels encountered in high-density magnetic recording, such as bit-patterned magnetic recording (BPMR) and two-dimensional magnetic recording (TDMR). The modified EXIT chart algorithm determines the LDPC threshold by fitting the EXIT curve of the variable node decoder (VND) combined with 2D detector (2D-DET) to the EXIT curve of the check node decoder (CND). Both the optimal Bahl-Cocke-Jelinek-Raviv (BCJR) 2D-DET and reduced-complexity Gaussian-approximated iterative row-column 2D-DET are considered.

This paper proposes efficient distance-enhancing constrained codes with parity-check (PC) constraints for data storage channels. We first propose simple and efficient finitestate encoding methods to design various distance-enhancing constrained codes, including a repeated minimum transition runlength (RMTR) code for optical recording channels, as well as a maximum transition run (MTR) code for magnetic recording channels. We further propose a general and systematic code design methodology, which can efficiently combine constrained codes with PC codes. The constrained codes can be any distanceenhancing constrained codes. The PC codes can be any linear binary PC codes. The rates of the designed codes are only a few tenths of a percent below the theoretical maximum. The proposed method enables soft information to be available to the PC decoder and soft decoding of PC codes. Examples of several newly designed distance-enhancing constrained PC codes are illustrated. Simulation results with blu-ray disc (BD) systems show that the proposed new RMTR code and RMTR constrained 4-bit PC code perform 0.2 dB and 0.85 dB better than the standard 17PP code, respectively, at error correction code (ECC) failure rate (EFR) of 10-12and high recording density.

The Wijngaarden-Immink (WI) scheme is a combined modulation/ECC coding scheme, where arbitrary user data are translated into a constrained sequence in which predefined positions are reserved for error-correcting codes (ECC) parity. Besides offering the benefit of combined modulation/ECC coding, the WI scheme has two extra benefits. They are (a) error propagation is limited to the constrained symbols, since symbols on the unconstrained positions are not related, and (b) code hardware is limited to a lookup table of the coded part. We will describe classes of simple bit-stuffing schemes that require less redundancy than predicted by the bound based on the performance of maxentropic constrained systems presented by Campello and Poo.

This paper proposes distance-enhancing constrained codes for optical recording channels. The repeated minimum transition runlength (RMTR) constraints are first investigated, based on error event analysis and capacity calculation. A new RMTR constrained code is then proposed. Compared with the codes used in standard systems, it imposes the minimum achievable RMTR constraint on the channel bit stream with the least decoding window length, without introducing additional code rate loss. A systematic method is further proposed, which can efficiently combine the RMTR code with the parity-check (PC) codes. Simulation results show that the new RMTR constrained PC code performs 1.1 dB better than the 17PP code, at BER = 10-5and high recording density.

The Wijngaarden-Immink (WI) scheme is a combined modulation/ECC coding scheme, where arbitrary user data are translated into a constrained sequence in which predefined positions are reserved for ECC parity. Besides offering the benefit of combined modulation/ECC coding, the WI scheme has two extra benefits. They are a) error propagation is limited to the constrained symbols, since symbols on the unconstrained positions are not related, and b) code hardware is limited to a look-up table of the coded part. We will describe classes of simple bit-stuffing schemes that require less redundancy than predicted by the bound based on the performance of maxentropic constrained systems presented by Campello et al. [1] and Poo et al. [2].

This paper proposes a general and systematic code design method to efficiently combine constrained codes with parity-check (PC) codes for optical recording. The proposed constrained PC code includes two component codes: the normal constrained (NC) code and the parity-related constrained (PRC) code. They are designed based on the same finite state machine (FSM). The rates of the designed codes are only a few tenths below the theoretical maximum. The PC constraint is defined by the generator matrix (or generator polynomial) of a linear binary PC code, which can detect any type of dominant error events or error event combinations of the system. Error propagation due to parity bits is avoided, since both component codes are protected by PCs. Two approaches are proposed to design the code in the non-return-to-zero-inverse (NRZI) format and the non-return-to-zero (NRZ) format, respectively. Designing the codes in NRZ format may reduce the number of parity bits required for error detection and simplify post-processing for error correction. Examples of several newly designed codes are illustrated. Simulation results with the Blu-Ray disc (BD) systems show that the new d = 1 constrained 4-bit PC code significantly outperforms the rate 2/3 code without parity, at both nominal density and high density.

The full-complexity soft-input/soft-output (SISO) multiuser detector based on the a posteriori probability (APP) algorithm has a computational complexity growing exponentially with the number of users. In this paper, we consider the multiuser detection problem from a combinatorial optimization viewpoint and develop a novel class of SISO multiuser detectors based on local search (LS) heuristics. By restricting the search to a small subset of the solution space and producing the APP based on a candidate list of potential solutions, the proposed detector can achieve bit-error-rate (BER) performance close to that of the APP algorithm with a significantly lower computational complexity.

The relationship between the number of encoder states and the probable size of certain runlength-limited (RLL) codes is derived analytically. By associating the number of encoder states with (generalized) Fibonacci numbers, the minimum number of encoder states is obtained, which maximizes the rate of the designed code, irrespective of the codeword length.

This paper proposes a general and systematic way to efficiently combine constrained codes with parity-check (PC) codes for optical recording. The proposed constrained PC code includes two component codes: the normal constrained (NC) code and the parity-related constrained (PRC) code. They are designed based on the same finite state machine (FSM). The code rates are only a few tenths below the theoretical maximum. The parity-check constraint is defined by the generator matrix (or generator polynomial) of a linear binary PC code, which can detect any type of dominant error events as well as error event combinations of the system. Two approaches are proposed to design the code in the non-return-to-zero-inverse (NRZI) format and the non-return-to-zero (NRZ) format, respectively. Designing the codes in NRZ format may reduce the number of parity bits required for error detection and simplify post-processing for error correction. Finally, examples of several newly designed codes and their performances are illustrated

The number of encoder states is a key measure of complexity of a finite-state constrained code. In this paper, we derive analytically the relationship between the number of encoder states and the size of capacity approaching d = 1 codes. By defining the number of encoder states as (generalized) Fibonacci numbers, we obtain the optimum encoder states, which maximize the size of the designed code with minimum number of states, for any desired codeword length