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).

Temperature control is of utmost importance in transmission systems. In this paper, a binary channel model is considered in which the transmission of a one causes a temperature increase while communicating a zero causes a temperature drop. By putting constraints on the input sequences, it is guaranteed that the channel temperature will not exceed a certain pre-determined maximum. In the asymptotic regime, the capacity of such a channel is studied. For the non-asymptotic regime, fixed-length codes are presented, with the property that codewords can be freely cascaded without violating the temperature constraint. Optimization of the code size is investigated and codewords are enumerated using generating functions.

The thermal-aware channel has been studied recently to control the temperature of some electronic devices for better performance and longer lifetime. In this work, we consider a thermal-aware channel model where multiple wires are available to the user. The user can use one wire or several wires to write an information word. Particularly, we study the two extreme cases. In the first case, only one wire is permitted for writing the information. The other extreme case is that we are allowed to write information on all the wires in parallel. In the first case, when we send a message through a wire that reaches the highest allowed temperature, we switch to another available wire. We determine the minimum number of wires required to send any arbitrary message. Given the number of wires, our second task is to determine the constrained codewords that can be sent through these wires. We compute the maximum information rate achieved and provide some constructions of codes satisfying these constraints. In the second case when all the wires are available for writing many, interesting questions arise and we briefly describe one of them and its solutions.

In DNA-based data storage, sequencing the stored DNA is essential in reading the stored data. Nanopore sequencing, an emerging sequencing technology, has attracted a lot of attention recently owing to their various advantages, in particular, it is portable, scalable, automated and rapid. However, several kinds of errors, including inter-symbol interference, noisy measurement, backtracking, and skipping, reduce the accuracy of the technology. Several coding schemes have been proposed recently to deal with various kinds of error sources, especially inter-symbol interference and noisy measurement. In this work, we focus on backtracking and skipping errors and aim to design a good coding scheme to combat these errors. We first note that backtracking and skipping errors can be modelled as synchronization errors, including duplication and deletion errors. Next, we propose new families of codes to locate and correct all synchronization errors caused by backtracking and skipping. The proposed codes are constrained codes avoiding prescribed set of patterns. Then, we focus on studying these constrained codes. In particular, we present a method to compute their maximal asymptotic rates. For illustration, we use experimental data available online to compute the numerical results for maximal asymptotic rates of these codes.

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.

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.

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.

High temperatures in electronic devices have a negative effect on their performance. Various techniques have been proposed and studied to address and combat this thermal challenge. To guarantee that the peak temperature of the devices will be bounded by some maximum temperature, the transmitted signal has to satisfy some constraints.With this motivation, we study the constrained channel that only accepts sequences that satisfy prescribed thermal constraints. The main goal in this paper is to compute the capacity of this channel. We provide the exact capacity of the channel with some certain parameters and we also present some bounds on the capacity in various cases.Finally, we consider the model that multiple wires are available to use and find out the smallest number of wires required to satisfy the thermal constraints.

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.

We present and analyze a new construction of bipolar balanced codes where each codeword contains equally many −1’s and +1’s. The new code is minimally modified as the number of symbol changes made to the source word for translating it into a balanced codeword is as small as possible. The balanced codes feature low redundancy and time complexity. Large look-up tables are avoided.

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.

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 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.

We consider noisy communications and storage systems that are hampered by varying offset of unknown magnitude such as low-frequency signals of unknown amplitude added to the sent signal. We study and analyze a new detection method whose error performance is independent of both unknown base offset and offset’s slew rate. The new method requires, for a codeword length$n\geq 12$, less than 1.5 dB more noise margin than Euclidean distance detection. The relationship with constrained codes based on mass-centered codewords and the new detection method is discussed.

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$.

In many channels, the transmitted signals do not only face noise, but offset mismatch as well. In the prior art, maximum likelihood (ML) decision criteria have already been developed for noisy channels suffering from signal independent offset. In this paper, such ML criterion is considered for the case of binary signals suffering from Gaussian noise and signal dependent offset. The signal dependency of the offset signifies that it may differ for distinct signal levels, i.e., the offset experienced by the zeroes in a transmitted codeword is not necessarily the same as the offset for the ones. Besides the ML criterion itself, also an option to reduce the complexity is considered. Further, a brief performance analysis is provided, confirming the superiority of the newly developed ML decoder over classical decoders based on the Euclidean or Pearson distances.

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.

Maximum likelihood (ML) decision criteria have been developed for channels suffering from signal independent offset mismatch. Here, such criteria are considered for signal dependent offset, which means that the value of the offset may differ for distinct signal levels rather than being the same for all levels. An ML decision criterion is derived, assuming uniform distributions for both the noise and the offset. In particular, for the proposed ML decoder, bounds are determined on the standard deviations of the noise and the offset which lead to a word error rate equal to zero. Simulation results are presented confirming the findings.

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.

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.

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.

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.

We consider the transmission and storage of data that use coded symbols over a channel, where a Pearson-distance-based detector is used for achieving resilience against unknown channel gain and offset, and corruption with additive noise. We discuss properties of binary Pearson codes, such as the Pearson noise distance that plays a key role in the error performance of Pearson-distance-based detection. We also compare the Pearson noise distance to the well-known Hamming distance, since the latter plays a similar role in the error performance of Euclidean-distance-based detection.

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.

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.

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 investigate a Knuth-like scheme for balancing q-ary code words, which has the virtue that lookup tables for coding and decoding the prefix are avoided by using precoding and error correction techniques. We show how the scheme can be extended to allow for error correction of single channel errors using a fast decoding algorithm that depends on syndromes only, making it considerably faster compared with the prior art exhaustive decoding strategy. A comparison between the new and prior art schemes, both in terms of redundancy and error performance, completes the study.

Minimum Pearson Distance (MPD) detection offers resilience against unknown channel gain and varying offset. MPD detection is used in conjunction with a set, S, of 2-ary codewords having specific properties. In this work, we study the properties of the codewords of S, compute the size of S, and derive its redundancy for asymptotically large values of the codeword length n. The redundancy of S is approximately 3/2 log2n + α; where α = log2√π/24 = -1.467.. for n odd and α = -0.467.. for n even.

The recently proposed Pearson codes offer immunity against channel gain and offset mismatch. These codes have very low redundancy, but efficient coding procedures were lacking. In this paper, systematic Pearson coding schemes are presented. The redundancy of these schemes is analyzed for memoryless uniform sources. It is concluded that simple coding can be established at only a modest rate loss.

We consider the transmission and storage of data that use coded binary symbols over a channel, where a Pearson distance-based detector is used for achieving resilience against additive noise, unknown channel gain, and varying offset. We study minimum Pearson distance (MPD) detection in conjunction with a set, S, of codewords satisfying a center-of-mass constraint. We investigate the properties of the codewords in S, compute the size of S, and derive its redundancy for asymptotically large values of the codeword length n. The redundancy of S is approximately (3/2) log2n + α, where α = log2(π/24)1/2= -1.467.. for n odd and α = -0.467.. for n even. We describe a simple encoding algorithm whose redundancy equals 2 log2n+ o(logn). We also compute the word error rate of the MPD detector when the channel is corrupted with additive Gaussian noise.

The Pearson distance has been advocated for improving the error performance of noisy channels with unknown gain and offset. The Pearson distance can only fruitfully be used for sets of q-ary codewords, called Pearson codes, that satisfy specific properties. We will analyze constructions and properties of optimal Pearson codes. We will compare the redundancy of optimal Pearson codes with the redundancy of prior art T-constrained codes, which consist of q-ary sequences in which T pre-determined reference symbols appear at least once. In particular, it will be shown that for q ≤ 3, the two-constrained codes are optimal Pearson codes, while for q ≥ 4 these codes are not optimal.

The error performance of optical storage and Non-Volatile Memory (Flash) is susceptible to unknown offset of the retrieved signal. Balanced codes offer immunity against unknown offset at the cost of a significant code redundancy, while minimum Pearson distance detection offers immunity with low-redundant codes at the price of lessened noise margin. We will present a hybrid detection method, where the distance measure is a weighted sum of the Euclidean and Pearson distance, so that the system designer may trade noise margin versus amount of immunity to unknown offset.

The reliability of mass storage systems, such as optical data recording and non-volatile memory (Flash), is seriously hampered by uncertainty of the actual value of the offset (drift) or gain (amplitude) of the retrieved signal. The recently introduced minimum Pearson distance detection is immune to unknown offset or gain, but this virtue comes at the cost of a lessened noise margin at nominal channel conditions. We will present a novel hybrid detection method, where we combine the outputs of the minimum Euclidean distance and Pearson distance detectors so that we may trade detection robustness versus noise margin. We will compute the error performance of hybrid detection in the presence of unknown channel mismatch and additive noise.

In this article, we study properties and algorithms for constructing sets of constant weight codewords with bipolar symbols, where the sum of the symbols is a constant q, q\neq 0. We show various code constructions that extend Knuth's balancing vector scheme, q=0, to the case where q>0. We compute the redundancy of the new coding methods. Finally, we generalize the proposed methods to encoding of imbalanced arrays in two or more dimensions.

The performance of certain transmission and storage channels, such as optical data storage and nonvolatile memory (flash), is seriously hampered by the phenomena of unknown offset (drift) or gain. We will show that minimum Pearson distance (MPD) detection, unlike conventional minimum Euclidean distance detection, is immune to offset and/or gain mismatch. MPD detection is used in conjunction with T-constrained codes that consist of q-ary codewords, where in each codeword T reference symbols appear at least once. We will analyze the redundancy of the new q-ary coding technique and compute the error performance of MPD detection in the presence of additive noise. Implementation issues of MPD detection will be discussed, and results of simulations will be given.

We will present coding techniques for transmission and storage channels with unknown gain and/or offset. It will be shown that a codebook of length-n q-ary codewords, S, where all codewords in S have equal balance and energy show an intrinsic resistance against unknown gain and/or offset. Generating functions for evaluating the size of S will be presented. We will present an approximate expression for the code redundancy for asymptotically large values of n.

We present a Knuth-like method for balancing q-ary codewords, which is characterized by the absence of a prefix that carries the information of the balancing index. Look-up tables for coding and decoding the prefix are avoided. We also show that this method can be extended to include error correction of single channel errors.

In this paper, we will present coding techniques for the character-constrained channel, where information is conveyed usingq-bit characters (nibbles), and wherewprescribed characters are disallowed. Using codes for the character-constrained channel, we present simple and systematic constructions of high-rate binary maximum runlength constrained codes. The new constructions have the virtue that large lookup tables for encoding and decoding are not required. We will compare the error propagation performance of codes based on the new construction with that of prior art codes.

Knuth's celebrated balancing method consists of inverting the first bits in a binary information sequence, such that the resulting sequence has as many ones as zeroes, and communicating the index to the receiver through a short balanced prefix. In the proposed method, Knuth's scheme is extended with error-correcting capabilities, where it is allowed to give unequal protection levels to the prefix and the payload. The proposed scheme is very general in the sense that any error-correcting block code may be used for the protection of the payload. Analyses with respect to redundancy and block and bit error probabilities are performed, showing good results while maintaining the simplicity features of the original scheme. It is shown that the Hamming distance of the code is of minor importance with respect to the error probability.

We will present simple and systematic constructions of high-rate binary maximum runlength constrained codes. The new construction has the virtue that large look-up tables for encoding and decoding are not required.

Knuth published a very simple algorithm for constructing bipolar codewords with equal numbers of +1's and -1's, called balanced codes. In our paper we will present new code constructions that generate balanced runlength limited sequences using a modification of Knuth's algorithm.

In this article, we study properties and algorithms for constructing sets of `constant weight' codewords with bipolar symbols, where the sum of the symbols is a constant q, q ≠ 0. We show various code constructions that extend Knuth's balancing vector scheme, q = 0, to the case where q >; 0. We compute the redundancy of the new coding methods.

We will study simple and systematic constructions of high-rate binary maximum runlength constrained codes, which are based on base conversion, where specific subsequences are disallowed. We will compare the error propagation performance of base-change codes with that of prior art codes.

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 prior art construction of sets of balanced codewords by Knuth is attractive for its simplicity and absence of look-up tables, but the redundancy of the balanced codes generated by Knuth's algorithm falls a factor of two short with respect to the minimum required. We present a new construction, which is simple, does not use look-up tables, and is less redundant than Knuth's construction. In the new construction, the user word is modified in the same way as in Knuth's construction, that is by inverting a segment of user symbols. The prefix that indicates which segment has been inverted, however, is encoded in a different, more efficient, way.

The sequence replacement technique converts an input sequence into a constrained sequence in which a prescribed subsequence is forbidden to occur. Several coding algorithms are presented that use this technique for the construction of maximum run-length limited sequences. The proposed algorithms show how all forbidden subsequences can be successively or iteratively removed to obtain a constrained sequence and how special subsequences can be inserted at predefined positions in the constrained sequence to represent the indices of the positions where the forbidden subsequences were removed. Several modifications are presented to reduce the impact of transmission errors on the decoding operation, and schemes to provide error control are discussed as well. The proposed algorithms can be implemented efficiently, and the rates of the constructed codes are close to their theoretical maximum. As such, the proposed algorithms are of interest for storage systems and data networks.

In 1986, Don Knuth published a very simple algorithm for constructing sets of bipolar codewords with equal numbers of “$1$”s and “${-1}$”s, called balanced codes. Knuth's algorithm is well suited for use with large codewords. The redundancy of Knuth's balanced codes is a factor of two larger than that of a code comprising the full set of balanced codewords. In this paper, we will present results of our attempts to improve the performance of Knuth's balanced codes.

The prior art construction of sets of balanced codewords by Knuth is attractive for its simplicity and absence of look-up tables, but the redundancy of the balanced codes generated by Knuth's algorithm falls a factor of two short with respect to capacity. We present a new construction, which is simple, does not use look-up tables, and is less redundant than Knuth's construction. In the new construction, the user word is modified in the same way as in Knuth's construction, that is by inverting a segment of user symbols. The prefix that indicates which segment has been inverted, however, is encoded and decoded in a different, more efficient, way.

We report a new method for designing (M,d, k) constrained codes for use in multi-level optical recording channels. The method allow us to design practical codes, which have simple encoder tables and decoders having fixed window length. The codes presented here for the d = 1 and d = 2 cases, achieve higher storage densities than previously reported codes, and come within 0.3 - 0.7% of capacity.

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].

In 1986, Don Knuth published a very simple algorithm for constructing sets of bipolar codewords with equal numbers of ‘1’s and ‘−1’s, called balanced codes. Knuth’s algorithm is, since look-up tables are absent, well suited for use with large codewords. The redundancy of Knuth’s balanced codes is a factor of two larger than that of a code comprising the full set of balanced codewords. In our paper we will present results of our attempts to improve the performance of Knuth’s balanced codes.

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.

We present capacity achieving multilevel run-length-limited (ML-RLL) codes that can be decoded by a sliding window of size 2.

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

Methods are developed to effectively combine guided scrambling and maximum run-length limited codes in order to impose a guaranteed maximum run-length constraint. It will be demonstrated that the combination of guided scrambling and a well-chosen maximum run-length limited code may offer a sound trade-off between overall code rate and performance in terms of the probability of violating the channel constraints.

We report on new dc-free runlength-limited codes (DCRLL) intended for the next generation of DVD. The efficiency of the newly developed DCRLL schemes is extremely close to the theoretical maximum, and as a result, significant density gains can be obtained with respect to prior art coding schemes. With a newly developed DCRLL (d=2) code we can achieve a 9% higher overall rate than that of DVD's EFMPlus.

A general method of constructing run-length limited (d, k) constrained codes from arbitrary sequences is introduced. This method is then combined with the method of guided scrambling for constructing a class of weakly constrained codes. The proposed codes are analyzed for the case of d=0 and are shown to give results which are better or comparable to those of the best available codes, however, at the cost of failure with some very low probability. For d>0, the code efficiency of the codes constructed according to the proposed method reduces significantly.

A general method of constructing (d, k) constrained codes from arbitrary sequences is introduced. This method is then used for constructing a class of weakly constrained codes. The proposed codes are analyzed for the case of d=0 and shown to give results which are better or comparable to those of the best available codes, however at the cost of failure with some very low probability.

We report on 20 years of development of codes for optical disk recording systems. A description of the state-of-the-art and feasible options for future extensions and improvements are given.

New methods are presented to protect maximum runlength-limited sequences against random and burst errors and to avoid error propagation. The methods employ parallel conversion techniques and enumerative coding algorithms that transform binary user information into constrained codewords. The new schemes have a low complexity and are very efficient. The approach can be used for modulation coding in recording systems and for synchronization and line coding in communication systems. The schemes enable the usage of high-rate constrained codes, as error control can be provided with similar capabilities as for unconstrained sequences.

We present an enumerative technique for encoding and decoding DC-free runlength-limited sequences. This technique enables the encoding and decoding of sequences approaching the maxentropic performance bounds very closely in terms of the code rate and low-frequency suppression capability. Use of finite-precision floating-point notation to express the weight coefficients results in channel encoders and decoders of moderate complexity. For channel constraints of practical interest, the hardware required for implementing such a quasi-maxentropic coding scheme consists mainly of a ROM of at most 5 kB.

We report on a new class of DC-free codes of rate (n-1)/n, odd. The spectral and runlength properties of the new codes have been evaluated by computer simulation.

We find an analytic expression for the maximum of the normalized entropy -/spl Sigma//sub i/spl epsiv/T/p/sub i/ln p/sub i///spl Sigma//sub i/spl epsiv/T/ip/sub i/ where the set T is the disjoint union of sets S/sub n/ of positive integers that are assigned probabilities P/sub n/, /spl Sigma//sub n/P/sub n/=1. This result is applied to the computation of the capacity of weakly (d,k)-constrained sequences that are allowed to violate the (d,k)-constraint with small probability.

Enumerative coding is an attractive algorithmic procedure for translating long source words into codewords and vice versa. The usage of long codewords makes it possible to approach a code rate which is as close as desired to Shannon's noiseless capacity of the constrained channel. Enumerative encoding is prone to massive error propagation as a single bit error could ruin entire decoded words. This contribution evaluates the effects of error propagation of the enumerative coding of runlength-limited sequences.

Enumerative coding is an attractive algorithmic procedure for translating long source words into codewords and vice versa. The usage of long codewords makes it possible to approach a code rate which is as close as desired to Shannon's noiseless capacity of the constrained channel. Enumerative encoding is prone to massive error propagation as a single bit error could ruin entire decoded words. This article evaluates the effects of error propagation of the enumerative coding of runlength limited sequences.

Constrained codes are a key component in digital recording devices that have become ubiquitous in computer data storage and electronic entertainment applications. This paper surveys the theory and practice of constrained coding, tracing the evolution of the subject from its origins in Shannon's classic 1948 paper to present-day applications in high-density digital recorders. Open problems and future research directions are also addressed.

We report on a class of high-rate dc-free codes, called multimode codes, where each source word can be represented by a codeword taken from a selection set of codeword alternatives. Conventional multimode codes are analyzed using a simple mathematical model. The criterion used to select the "best" codeword from the selection set available has a significant bearing on the performance. Various selection criteria are introduced and their effect on the performance of multimode codes is examined.

A new coding technique is proposed that translates user information into a constrained sequence using very long codewords. Huge error propagation resulting from the use of long codewords is avoided by reversing the conventional hierarchy of the error control code and the constrained code. The new technique is exemplified by focusing on (d, k)-constrained codes. A storage-effective enumerative encoding scheme is proposed for translating user data into long dk sequences and vice versa. For dk runlength-limited codes, estimates are given of the relationship between coding efficiency versus encoder and decoder complexity. We show that for most common d, k values, a code rate of less than 0.5% below channel capacity can be obtained by using hardware mainly consisting of a ROM lookup table of size 1 kbyte. For selected values of d and k, the size of the lookup table is much smaller. The paper is concluded by an illustrative numerical example of a rate 256/466, (d=2, k=15) code, which provides a serviceable 10% increase in rate with respect to its traditional rate 1/2, (2, 7) counterpart.

A new rate 4/6 (d=1, k'=11) runlength-limited code which is well adapted to byte-oriented storage systems is presented. The new code has the virtue that it can be decoded on a block basis, i.e., without knowledge of previous or next codewords, and, therefore, it does not suffer from error propagation. This code is particularly attractive as many commercially available Reed-Solomon codes operate in GF(2/sup 8/).

Traditional schemes for encoding and decoding runlength-constrained sequences using the enumeration principle require two sets of weighting coefficients. A new enumeration is presented requiring only one set of coefficients.

Describes a new technique for constructing fixed-length (d,k) runlength-limited block codes. The new codes are very close to block-decodable codes, as decoding of the retrieved sequence can be accomplished by observing (part of) the received codeword plus a very small part (usually only a single bit) of the previous codeword. The basic idea of the new construction is to uniquely represent each source word by a (d,k) sequence with specific predefined properties, and to construct a bridge of /spl beta/, 1/spl les//spl beta//spl les/d, merging bits between every pair of adjacent words. An essential element of the new coding principle is look ahead. The merging bits are governed by the state of the encoder (the history), the present source word to be translated, and by the upcoming source word. The new constructions have the virtue that only one look-up table is required for encoding and decoding.>

We report on block-coding techniques for partial-response channels with transfer function (1/spl mnplus/D/sup m/), m=1, 2, ... . We consider various constructions of block codes with prescribed minimum Euclidean distance. Upper and lower bounds to the size of a code with minimum squared Euclidean distance greater than unity are furnished. A table is presented of cardinalities of codes of small length with prescribed minimum squared Euclidean distance.

In digital recorders, the coded information is commonly grouped in large blocks, called frames. The authors concentrate on the frame synchronization problem of run-length-limited sequences, or (d, k) sequences. They commence with a brief description of (d, k)-constrained sequences, and proceed with the examination of the channel capacity. It is shown that for certain sync patterns, called repetitive-free sync patterns, the capacity can be formulated in a simple manner as it is solely a function of the (d, k) parameters and the length of the sync pattern. For each forbidden pattern and (d, k) constraints, methods for enumerating constrained sequences are given. Design considerations of schemes for encoding and decoding are addressed. Examples of prefix-synchronized (d, k) codes, based for the purpose of illustration on the sliding-block coding algorithm, are presented.>

The problem of appraising the spectral performance of codes based on a new algorithm for generating zero-disparity codewords presented by D.E. Knuth (1986) is addressed. In order to get some insight into the efficiency of Knuth's construction technique, the authors evaluate the spectral properties of its code streams. The structure of Knuth codes allows the derivation a simple expression for (an approximation to) the sum of variance of these codes. This quantity plays a key role in the spectral performance characterization of DC-balanced codes. The authors evaluate this expression and compare the sum variance of Knuth codes with the sum variance of the polarity bit codes for fixed redundancy. Under the premise that the sum variance can serve as a quantity to judge the width of the spectral notch, the authors conclude that codes based on Knuth's algorithm offer less spectral suppression than polarity bit codes with the same redundancy.>

The eigenstructure of bidiagonal Hessenberg-Toeplitz matrices is determined. These matrices occur as skeleton matrices of finite-state machines generating certain asymmetrically DC-constrained binary sequences that can be used for simulating pilot tracking tones in digital magnetic recording. The eigenstructure is used to calculate the Shannon upper bound to the entropy of the finite state machine as well as the power spectrum of the maxentropic process generated by it.>

Runlength-limited (RLL) sequences are formally defined, and the runlength distribution and spectral properties of ideal RLL sequences are analyzed. A detailed description is furnished of the limiting properties of RLL sequences, and a comprehensive review is given of the practical aspects involved in the translation of arbitrary data into RLL sequences. Examples of code implementation are presented to illustrate the variety of possible design tools.>

Coding techniques for improving the reliability of information storage on noisy magnetic recording channels are considered. It is assumed that the Lorentzian channel model applies and that the retrieved signal is perturbed with additive white Gaussian noise. The immunity against additive noise of state-of-the-art codes such as DC-free, runlength-limited, and trellis codes are assessed.>

A coding technique for improving the reliability of digital transmission over noisy partial-response channels with characteristics (+or-D/sup m/), m=1, 2, where the channel input symbols are constrained to be +or-1, is presented. In particular, the application of a traditional modulation code as an inner code of a concentrated coding scheme in which the outer code is designed for maximum (free) Hamming distance is considered. A performance comparison is made between the concentrated scheme and a coding technique presented by Wolf and G. Ungerboeck (see ibid., vol. COM-34, p.765-773, Aug. 1986) for the dicode channel with transfer function (1-D).>

A method is presented for designing binary channel codes in such a way that both the power spectral density function and its low-order derivatives vanish at zero frequency. The performance of the new codes is compared with that of channel codes designed with a constraint on the unbalance Of the number of transmitted positive and negative pulses. Some remarks are made on the error-correcting capabilities of these codes.

Many modulation systems used in magnetic and optical recording are based on binary run-length-limited codes. We generalize the concept ofdk-limited sequences of length n introduced by Tang and Bald by imposing constraints on the maximum number of consecutive zeros at the beginning and the end of the sequences. It is shown that the encoding and decoding procedures are similar to those of Tang and Bald. The additional constraints allow a more efficient merging of the sequences. We demonstrate two constructions of run-length-limited codes with merging rules of increasing complexity and efficiency and compare them to Tang and Bahl's method.

This paper describes a new recording code format, Eight to Fourteen Modulation (EFM), designed for digital audio discs with optical readout. Attention is focused primarily on trade offs between conflicting parameters such as information density and d.c. content that led to the choice of the adopted format EFM.