Search

In this paper, we consider encoding strategies for the Z-channel with noiseless feedback. We analyze the combinatorial setting where the maximum number of errors inflicted by an adversary is proportional to the number of transmissions, which goes to infinity. Without feedback, it is known that the rate of optimal asymmetric-error-correcting codes for the error fraction $\tau \ge 1/4$ vanishes as the blocklength grows. In this paper, we give an efficient feedback encoding scheme with $n$ transmissions that achieves a positive rate for any fraction of errors $\tau < 1$ and $n\to \infty $. Additionally, we state an upper bound on the rate of asymptotically long feedback asymmetric error-correcting codes. [ABSTRACT FROM AUTHOR]

Dirty paper coding (DPC) offers an information-theoretic result for pre-cancellation of known interference at the transmitter. In this letter, we propose practical DPC schemes that use only one error correction code. Our designs focus on practical use from the viewpoint of complexity. For fair comparison with previous schemes, we compute the complexity of proposed schemes by the number of operations used. Simulation results show that compared to previous DPC schemes, the proposed schemes require lower transmission power to maintain the bit error rate to be within 10^-5 . [ABSTRACT FROM PUBLISHER]

This paper proposes Value-Aware solid-state drive (SSD) with fast access speed and low power consumption by eliminating error-correcting code (ECC). Value-Aware SSD utilizes the error tolerance of image recognition application using a deep neural network (DNN) to enhance reliability. In a previous paper, which proposes Value-Aware SSD, fast ECC decoder is implemented and SSD is evaluated with the 32-bit floating-point data format. On the other hand, in this paper, the proposed Value-Aware SSD is analyzed with 32-bit and 8-bit fixed-point data format and achieves the higher reliability even without ECC by newly proposed two techniques, Critical Bit Error Reduction (CBER) and Middle & Lower Page Error Reduction (M&L-PER). CBER and M&L-PER are proposed for 32-bit and 8-bit data format of application, respectively. These techniques modulate the threshold voltage ($V_{\mathrm {TH}}$) distribution of memory cells by recognizing the importance of each stored bit. By proposed CBER, as much as 15% bit error rate (BER) of NAND flash is allowed while the application provides high image recognition accuracy. Even if bit precision is truncated to 8 bit, 3.9% BER is accepted by M&L-PER. The fast read access and low power consumption are realized because ECC is not required. Finally, this paper analyzes the Value-Aware techniques with 3-D multi-level cell (MLC) NAND flash to compare the effects for 3D-MLC and triple-level cell (TLC) NAND flash. [ABSTRACT FROM AUTHOR]

In an interesting paper, Prof. C. Ding provided three constructions of cyclic codes of length being a product of two primes. Numerical data shows that many codes from these constructions are best cyclic codes of the same length and dimension over the same finite field. However, not much is known about these codes. In this paper, we explain some of the numerical data by developing a general method on cyclic codes of composite length and on estimating the minimum distance. We also provide a general construction of cyclic codes of composite length which are related to Ding’s constructions. Numerical data shows that it produces many best cyclic codes as well. Finally, we point out how these cyclic codes can be used to construct convolutional codes with large free distance. [ABSTRACT FROM AUTHOR]

M. Fossorier proposed how to determine the necessary and sufficient conditions for the existence of cycles in the Tanner graph of quasi‐cyclic LDPC (QC‐LDPC) codes, which has been widely investigated in the study of LDPC codes. This paper presents some new necessary and sufficient conditions for the existence of cycles with arbitrary lengths and proposes a simple and novel method for counting cycles of QC‐LDPC codes based on the improved conditions. Numerical results show that, compared with the existing methods, the presented method is effective and feasible and can enumerate cycles of QC‐LDPC codes in a cyclic‐shift way. [ABSTRACT FROM AUTHOR]

This letter considers the network error-correction capacity in the presence of Byzantine attacks. Unlike prior papers, which assume no delay in any part of networks, we consider the effects of processing delays in the nodes. We prove that these processing delays have no impact on the network error-correction capacity region for any directed network. [ABSTRACT FROM PUBLISHER]

The construction of a quasi-cyclic low density parity-check (QC-LDPC) matrix is usually carried out in two steps. In the first step, a prototype matrix is defined according to certain criteria (size, girth, check and variable node degrees, and so on). The second step involves the expansion of the prototype matrix. During this last phase, an integer value is assigned to each non-null position in the prototype matrix corresponding to the right-rotation of the identity matrix. The problem of determining these integer values is complex. The state-of-the-art solutions use either some mathematical constructions to guarantee a given girth of the final QC-LDPC code, or a random search of values until the target girth is satisfied. In this paper, we propose an alternative/complementary method that reduces the search space by defining large equivalence classes of topologically identical matrices through row and column permutations using additive, structural, and multiplicative transformations. Selecting only a single element per equivalence class can reduce the search space by a few orders of magnitude. Then, we use the formalism of constraint programming to list the exhaustive sets of solutions for a given girth and a given expansion factor. An example is presented in all sections of the paper to illustrate the methodology. [ABSTRACT FROM AUTHOR]

Constacyclic codes are well-known generalizations of cyclic and negacyclic codes. Due to their rich algebraic structure, constacyclic codes are used to construct quantum codes and symbol-pair codes. Let ${\mathbb {F}}_{q}$ be a finite field with order $q$ , where $q$ is a positive power of a prime $p$. Suppose that $n$ is a positive integer and the product of distinct prime factors of $n$ divides $q-1$ , i.e., $rad(n)\mid (q-1)$. In this paper, we explicitly factorize the polynomial $x^{n}-\lambda $ for each $\lambda \in {\mathbb {F}}_{q}^{*}$. As applications, first, we obtain all repeated-root $\lambda $ -constacyclic codes and their dual codes of length $np^{s}$ over ${\mathbb {F}}_{q}$ ; second, we determine all simple-root LCD cyclic codes and LCD negacyclic codes of length $n$ over ${\mathbb {F}}_{q}$ ; third, we list all self-dual repeated-root negacyclic codes of length $np^{s}$ over ${\mathbb {F}}_{q}$. In contrast to known results, the lengths of constacyclic codes in this paper have more flexible parameters. [ABSTRACT FROM AUTHOR]

This paper presents a new construction of error correcting codes which achieves optimal recovery of a streaming source over a packet erasure channel. The channel model considered is the sliding-window erasure model, with burst and arbitrary losses, introduced by Badr et al. We present a simple construction, when the rate of the code is at least 1/2, which achieves optimal error correction in this setup. Our proposed construction is explicit and systematic. It uses off-the-shelf maximum distance separable (MDS) codes and maximum rank distance (MRD) Gabidulin block codes as constituent codes and combines them in a simple manner. This is in contrast to other recent works, where the construction involves a careful design of the generator or parity check matrix from first principles. The field size requirement which depends on the constituent MDS and MRD codes is also analyzed. [ABSTRACT FROM AUTHOR]

The user datagram protocol is the most widely used protocol for streaming multimedia data over the Internet. Like other protocols at the network and transport layers, it uses the Internet Checksum (IC) to detect channel errors. The consequence of this is that each corrupted packet is dropped, which can degrade the quality of service perceived by a user. In this paper, the authors present a solution to this problem based on integer codes capable of correcting single and double adjacent errors. The presented codes are a generalization of the IC, which makes them easy to implement in software. [ABSTRACT FROM AUTHOR]

Quantum key distribution (QKD) can provide information-theoretically secure keys for two parties of legitimate communication, and information reconciliation, as an indispensable component of QKD systems, can correct errors present in raw keys based on error-correcting codes. In this paper, we first describe the basic knowledge of information reconciliation and its impact on continuous variable QKD. Then we introduce the information schemes and the corresponding error correction codes employed. Next, we introduce the rate-compatible codes, the hardware acceleration of the reconciliation algorithm, the research progress of information reconciliation, and its application in continuous variable QKD. Finally, we discuss the future challenges and conclude. [ABSTRACT FROM AUTHOR]

Due to the emergence of extremely high density memory along with the growing number of embedded memories, memory yield is an important issue. Memory self-repair using redundancies to increase the yield of memories is widely used. Because high density memories are vulnerable to soft errors, memory error correction code (ECC) plays an important role in memory design. In this paper, methods to exploit spare columns including replaced defective columns are proposed to improve memory ECC. To utilize replaced defective columns, the defect information needs to be stored. Two approaches to store defect information are proposed—one is to use a spare column and the other is to use a content-addressable-memory. Experimental results show that the proposed method can significantly enhance the ECC performance. [ABSTRACT FROM AUTHOR]

A new family of scalable codes with locality and availability for information repair in data storage systems for e-health applications was presented recently. The construction was based on a graph of the [7, 3-4] Simplex code. In this paper it is shown that the construction can be generalized via tessellation in a Euclidian plane. The codes obtained have new interesting recoverability properties. They can in some cases repair damage to many storage nodes in multiple connected graphs via sequential decoding, which is similar to healing wounds in biological systems. The advantages of the original codes, namely the availability, functionality, efficiency and high data accessibility, will be preserved also in these new codes. The computational complexity and communication costs of their incrementation will remain constant and modest. These codes could be adapted to disaster recovery because it is straightforward to place the nodes so that the graph is easily mapped on a real structure in space. [ABSTRACT FROM AUTHOR]

In coded caching, a single server is connected to a set of users through a shared bottleneck link, which is assumed to be error free. During non-peak hours, all the users fill their local cache with portions of the files available. During the delivery phase, each user requests a file and the server delivers coded transmissions to meet the demands. In this paper, the links between the server and the users are assumed to be error prone. Prefetching errors are also considered. A new delivery scheme is required to meet the demands of each user even after receiving a finite number of transmissions in error in the presence of erroneous portions of files in the cache. The minimum average rate and minimum peak rate for this problem are characterized. Closed form expressions for average and peak rates for a particular caching scheme, namely, symmetric batch prefetching are established when there are no prefetching errors. An optimal linear error correcting delivery scheme is proposed for coded caching problems with symmetric batch prefetching in the absence of prefetching errors. In addition to this, lower bounds are established for the optimal rate required when there are prefetching errors in symmetric batch prefetching. [ABSTRACT FROM AUTHOR]

In the $q$ -ary online (or “causal”) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword $\mathbf {x} =(x_{1},\ldots,x_{n}) \in \{0,1,\ldots,q-1\}^{n}$ symbol-by-symbol via a channel limited to at most $pn$ errors and $p^{*} n$ erasures. The channel is “online” in the sense that at the $i$ th step of communication the channel decides whether to corrupt the $i$ th symbol or not based on its view so far, i.e., its decision depends only on the transmitted symbols $(x_{1},\ldots,x_{i})$. This is in contrast to the classical adversarial channel in which the corruption is chosen by a channel that has full knowledge of the sent codeword $\mathbf {x}$. In this paper, we study the capacity of $q$ -ary online channels for a combined corruption model, in which the channel may impose at most $pn$ errors and at most $p^{*} n$ erasures on the transmitted codeword. The online channel (in both the error and erasure case) has seen a number of recent studies, which present both upper and lower bounds on its capacity. In this paper, we give a full characterization of the capacity as a function of $q,p$ , and $p^{*}$. [ABSTRACT FROM AUTHOR]

Cache vulnerability due to soft errors is one of the reliability concerns in embedded systems. Dynamic reconfiguration techniques are widely studied for improving cache energy without considering the implications of cache vulnerability. Maintaining a useful data longer in the cache can be beneficial for energy improvement due to reduction in miss rates, however, longer data retention negatively impacts the vulnerability due to soft errors. This paper studies the tradeoff between energy efficiency improvement and reduction in cache vulnerability during cache reconfiguration. We propose a heuristic approach for both intertask and intratask cache reconfiguration in multitasking systems. Experimental results demonstrate that our proposed approach can significantly improve both vulnerability (25% on average) and energy efficiency (21% on average) for data cache without violating real-time constraints. [ABSTRACT FROM AUTHOR]

Linear codes with certain special properties have received renewed attention in recent years due to their practical applications. Among them, binary linear complementary dual (LCD) codes play an important role in implementations against side-channel attacks and fault injection attacks. Self-orthogonal codes can be used to construct quantum codes. In this paper, four classes of binary linear codes are constructed via a generic construction which has been intensively investigated in the past decade. Simple characterizations of these linear codes to be LCD or self-orthogonal are presented. Resultantly, infinite families of binary LCD codes and self-orthogonal codes are obtained. Infinite families of binary LCD codes from the duals of these four classes of linear codes are produced. Many LCD codes and self-orthogonal codes obtained in this paper are optimal or almost optimal in the sense that they meet certain bounds on general linear codes. In addition, the weight distributions of two sub-families of the proposed linear codes are established in terms of Krawtchouk polynomials. [ABSTRACT FROM AUTHOR]

The rank modulation scheme has been proposed for efficient writing and storing data in nonvolatile memory storage. Error correction in the rank modulation scheme is done by considering permutation codes. In this paper, we consider codes in the set of all permutations on n elements, S_{n} , using the Kendall \tau -metric. The main goal of this paper is to derive new bounds on the size of such codes. For this purpose, we also consider perfect codes, diameter perfect codes, and the size of optimal anticodes in the Kendall \tau -metric, structures which have their own considerable interest. We prove that there are no perfect single-error-correcting codes in S_{n} , where n>4 is a prime or 4\leq n\leq 10 . We present lower bounds on the size of optimal anticodes with odd diameter. As a consequence, we obtain a new upper bound on the size of codes in S_{n} with even minimum Kendall \tau -distance. We present larger single-error-correcting codes than the known ones in S5 and S7 . [ABSTRACT FROM AUTHOR]

This paper deals with Hadamard \mathbb Z2 \mathbb Z4 {Q}8 -codes, which are binary codes after a Gray map from a subgroup of direct products of \mathbb Z2 , \mathbb Z4 , and Q8 , where Q8 is the quaternionic group. In a previous work, these codes were classified in five shapes. In this paper, we analyze the allowable range of values for the rank and dimension of the kernel, which depends on the particular shape of the code. We show that all these codes can be represented in a standard form, from a set of generators, which can help in understanding the characteristics of each shape. The main results we present are the characterization of Hadamard \mathbb Z2 \mathbb Z4 {Q}8 -codes as a quotient of a semidirect product of \mathbb Z2 \mathbb Z4 -linear codes and the construction of Hadamard \mathbb Z2 \mathbb Z4 {Q}8 -codes with each allowable pair of values for the rank and dimension of the kernel. [ABSTRACT FROM AUTHOR]

In magnetic recording systems, consecutive sections experience different signal-to-noise ratios (SNRs). To perform error correction over these systems, one approach is to use an individual block code for each section. However, the performance over a section affected by a lower SNR is weaker compared to the performance over a section affected by a higher SNR. Spatially-coupled (SC) codes are a family of graph-based codes with capacity approaching performance and low latency decoding. An SC code is constructed by partitioning an underlying block code to several component matrices, and coupling copies of the component matrices together. The contribution of this paper is threefold. First, we present a new partitioning technique to efficiently construct SC codes with column weights 4 and 6. Second, we present an SC code construction for channels with SNR variation. Our SC code construction provides local error correction for each section by means of the underlying codes that cover one section each, and simultaneously, an added level of error correction by means of coupling among the underlying codes. Third, we introduce a low-complexity interleaving scheme specific to SC codes that further improves their performance over channels with SNR variation. Our simulation results show that our SC codes outperform individual block codes by more than one and two orders of magnitudes in the error floor region compared to the block codes with and without regular interleaving, respectively. This improvement is more pronounced by increasing the memory and column weight. [ABSTRACT FROM AUTHOR]

In this paper, some affine and rational functions are applied to define a class of LDPC codes, called RLDPC codes, which can be classified in two types, type-I and type-II, depending on being equivalent or not with APM-LDPC codes, respectively. Then, for each type, some explicit methods are provided to generate RLDPC codes with girth at least 6. While, cyclotomic cosets are used to generate type-I RLDPC codes, normal and diameter RLDPC codes are proposed as a class of type-II RLDPC codes which are analyzed for the existence of 4-cycles. Finally, simulation results show that the constructed type-II RLDPC codes outperform the randomly constructed QC LDPC codes, APM-LDPC codes and the LDPC codes based on PEG. [ABSTRACT FROM AUTHOR]

The prefixed Varshamov-Tenengolts (VT) codes, which are subsets of VT codes with predetermined prefixes, can be used for error correction over segmented edit channels. In this paper, we investigate the construction and analysis of this class of codes. First, we derive upper bounds on the size of zero-error codes for segmented edit channels with segment-by-segment decoding. Second, we establish a one-to-one correspondence between prefixed VT codes and Levenshtein codes. Based on this relation, we can obtain explicit formulas on the size of prefixed VT codes via the existing results on the size of Levenshtein codes. Third, we construct a new zero-error prefixed VT code and show that the size of the constructed code is strictly larger than that of the existing prefixed VT code for the segmented deletion channel. Finally, an efficient systematic encoding method of prefixed VT codes is proposed for the segmented edit channels. [ABSTRACT FROM AUTHOR]

With the rapid development of technology scaling and cell density improvement for capacity increase and cost reduction, nand flash memory is confronted with degraded reliability. On one hand, while low-density parity-check (LDPC) codes have been deployed in today's nand flash memories to enhance reliability, flash read latency has still been a performance bottleneck with the increased raw bit error rates (RBER). On the other hand, significant process variations (PV) have been found on existing nand flash memories, which introduce great reliability variations among different flash blocks. Recent studies have proposed to exploit PV to improve endurance by better wear leveling or to improve write performance. These approaches are prone to allocate read data to blocks with low reliability, which further degrades read performance. This paper proposes to enhance read performance of LDPC-equipped nand flash memory by exploiting the reliability variations from PV. The paper consists of three parts. First, a block grouping approach is presented to categorize flash blocks according to their reliability. Second, according to the grouping scheme, a data placement scheme is proposed, which allocates read-hot data to flash blocks with high reliability. At the same time, the read-cold data is moved to blocks with low reliability. As a result, the read performance is enhanced. However, allocating high reliable blocks for read-hot data collides with previous PV-based wear leveling methods. To address the issue, the third part is a grouping partition scheme which limits the amount of high reliable blocks occupied by read-hot data. Therefore, read performance enhancement can be achieved and the wear leveling schemes will be impacted slightly. Experiment results present that, the proposed approach can provide significant read performance improvement on LDPC-equipped nand flash memory and is compatible with the previous PV-based wear leveling. [ABSTRACT FROM AUTHOR]

This paper proposes a generator polynomial model-based eye diagram estimation method for the error-correction codes (ECCs), which are the Bose–Chaudhuri–Hocquenghem (BCH) code and the Reed–Solomon (RS) code. The ECCs compensate for the channel loss at the bit level, so most of the systems include the ECC block. The BCH and RS codes are the generator polynomial-based ECCs; this paper proposes the generator polynomial model-based method. The model provides the accurate probability density function of the code words for the BCH and RS code. Thus, the proposed method is capable of achieving the signal integrity analysis for the system level. For verification, we design the BCH and RS encoders. The estimated eye diagrams are nearly the same as that of the transient simulation for the BCH and RS codes. Furthermore, the voltage bathtub curves are the same up to 10−8. For a smaller bit-error rate value, the proposed method only provides the bathtub curve. This paper successfully verifies the eye diagram estimation method for the BCH and RS codes. [ABSTRACT FROM AUTHOR]

Mixed kernels of polar codes are mapping functions having inputs of different alphabet sizes that are used to construct polar coding scheme. These schemes are constructed by incorporating several (homogeneous) kernels, each one over different alphabet size. In this paper, the idea of mixed-kernels construction is introduced and analyzed. An asymptotic analysis of the proposed scheme shows that its polarization properties are strongly related to the ones of the constituent kernels. Simulation of finite length instances of the scheme indicate their advantages both in error correction performance and complexity compared to the known polar coding structures. [ABSTRACT FROM AUTHOR]

Commitment Scheme is the way to hide the information and that information is revealed to the receiver in the later stage. The commitment scheme uses witness value to open the commitment. The role of witness value differentiates the fuzzy commitment scheme from a commitment scheme. Fuzzy commitment scheme allows the use of corrupted witness. In this paper, a generalized fuzzy commitment scheme is introduced that has the capability to reconstruct the secret from corrupted committed message and corrupted witness. The paper presents the fuzzy commitment scheme with the codes and analyzes the scheme with BCH and RS codes. [ABSTRACT FROM AUTHOR]

By storing multibit per cell, multilevel cell (MLC) NAND flash memory achieves high storage capacity, but sacrificing data reliability. Error correction codes, such as Bose–Chaudhuri–Hocquenghem (BCH) codes, are widely used to ensure data reliability. However, high raw bit error rates induced by interference noises make BCH codes become insufficient to guarantee data reliability. Low-density parity-check (LDPC) codes are considered as the replacement due to the stronger error correction capability. Nevertheless, directly exploiting LDPC codes introduces a concern about decoding latency because of their iterative decoding in the soft decision process. To develop effective LDPC decoding algorithms, it is necessary to have a more profound understanding on flash failure patterns. This paper first observes the pair-bit errors (PBEs) characteristic of MLC NAND flash memory on a real field-programmable gate array testing platform, then proposes a PBE-aware LDPC (PAL) decoding scheme-based upon this observation, in which PBE provides the promotion information for LDPC decoding to reduce decoding latency. Simulation results show that the decoding latency can be reduced by up to 54%, compared with the conventional LDPC codes. [ABSTRACT FROM AUTHOR]

This paper examines the queueing performance of communication systems that transmit encoded data over unreliable channels. A fading formulation suitable for wireless mobile applications is considered, where errors are caused by a discrete channel with correlated behavior over time. For carefully selected channel models and arrival processes, a tractable Markov structure composed of queue length and channel state is identified. This facilitates the analysis of the stationary behavior of the system, leading to evaluation criteria such as bounds on the probability of the queue exceeding a threshold. Specifically, this paper focuses on system models with scalable arrival profiles, which are based on Poisson processes, and finite-state channels with memory. These assumptions permit the rigorous comparison of system performance for codes with arbitrary block lengths and code rates. Based on the resulting characterizations, it is possible to select the best code parameters for delay-sensitive applications over various channels. Random codes and BCH codes are then employed as a means to study the relationship between code parameter selection and the queueing performance of point-to-point data links. The methodology introduced herein offers a new perspective on the joint queueing–coding analysis of finite-state channels with memory, and it is supported by numerical simulations. [ABSTRACT FROM PUBLISHER]

This paper investigates fundamental properties of nonlinear binary codes by looking at the codebook matrix not row-wise (codewords), but column-wise. The family of weak flip codes is presented and shown to contain many beautiful properties. In particular the subfamily fair weak flip codes, which goes back to Shannon et al. and which was shown to achieve the error exponent with a fixed number of codewords $\mathsf {M}$ , can be seen as a generalization of linear codes to an arbitrary number of codewords. The fair weak flip codes are related to binary nonlinear Hadamard codes. Based on the column-wise approach to the codebook matrix, the $r$ -wise Hamming distance is introduced as a generalization to the well-known and widely used (pairwise) Hamming distance. It is shown that the minimum $r$ -wise Hamming distance satisfies a generalized $r$ -wise Plotkin bound. The $r$ -wise Hamming distance structure of the nonlinear fair weak flip codes is analyzed and shown to be superior to many codes. In particular, it is proven that the fair weak flip codes achieve the $r$ -wise Plotkin bound with equality for all $r$. In the second part of this paper, these insights are applied to a binary erasure channel with an arbitrary erasure probability 0 < $\delta$ < 1. An exact formula for the average error probability of an arbitrary (linear or nonlinear) code using maximum likelihood decoding is derived and shown to be expressible using only the $r$ -wise Hamming distance structure of the code. For a number of codewords $\mathsf {M}$ satisfying $\mathsf {M}\le 4$ and an arbitrary finite blocklength $n$ , the globally optimal codes (in the sense of minimizing the average error probability) are found. For $\mathsf {M}$ = 5 or $\mathsf {M}$ = 6 and an arbitrary finite blocklength $n$ , the optimal codes are conjectured. For larger $\mathsf {M}$ , observations regarding the optimal design are presented, e.g., that good codes have a large $r$ -wise Hamming distance structure for all $r$. Numerical results validate our code design criteria and show the superiority of our best found nonlinear weak flip codes compared with the best linear codes. [ABSTRACT FROM AUTHOR]

Two-dimensional magnetic recording (TDMR) is a promising technology for boosting areal densities (ADs) using sophisticated signal processing algorithms within a systems framework. The read/write channel architectures have to effectively tackle 2-D inter-symbol interference (ISI), 2-D synchronization errors, media and electronic noise sources, as well as thermal asperities resulting in burst erasures. The 1-D low-density parity check (LDPC) codes are well studied to correct large 1-D burst errors/erasures. However, such 1-D LDPC codes are not suitable for correcting 2-D burst errors/erasures due to the 2-D span of errors. In this paper, we propose construction of a native 2-D LDPC code to effectively correct 2-D burst erasures. We also propose a joint detection and decoding engine based on the generalized belief propagation algorithm to simultaneously handle 2-D ISI, as well as correct bit/burst errors for TDMR channels. This paper is novel in two aspects: 1) we propose the construction of native 2-D LDPC codes to correct large 2-D burst erasures and 2) we develop a 2-D joint signal detection-decoder engine that incorporates 2-D ISI constraints, and modulation code constrains along with LDPC decoding. The native 2-D LDPC code can correct >20% more burst erasures compared with the 1-D LDPC code over a 128 $\times $ 256 2-D page of detected bits. Also, the proposed algorithm is observed to achieve a signal-to-noise ratio gain of >0.5 dB in bit error rate performance (translating to 10% increase in ADs around the 1.8 Tb/in2 regime with grain sizes of 9 nm) as compared with a decoupled detector-decoder system configuration over a small 2-D LDPC code of size 16 $\times $ 16. The efficacy of our proposed algorithm and system architecture is evaluated by assessing AD gains via simulations for a TDMR configuration comprising of a 2-D generalized partial response over the Voronoi media model assuming perfect 2-D synchronization. [ABSTRACT FROM PUBLISHER]

Memory contents are usually corrupted due to soft errors caused by external radiation and hence the reliability of memory systems is reduced. In order to enhance the reliability of memory systems, error correcting codes (ECC) are widely used to detect and correct errors. Single bit error correcting with double bits errors detecting codes are generally used in memory systems. But in case of multiple cell errors, these codes are unable to detect and correct errors. Recently, single byte error correcting Reed Solomon (SEC-RS) codes are used to detect and correct single byte error in memory systems. In this paper, a new single byte error correcting (SEC) code is proposed based on the concept of cellular automata (termed as CASEC). The main aim of this work is to reduce the area and power of SEC encoder and decoder circuit without affecting delay. In this paper, CASEC(10,8,8), CASEC(18,16,8), 2xCASEC(10,8,4) and 2xCASEC(19,6,4) codecs are designed and implemented. CASEC(18,16,8) codec has 67.79 percent lesser hardware complexity compared to existing design. Proposed codecs are simulated and synthesized for both FPGA and ASIC platforms. It is found that speed of the proposed design is almost equal to the existing design but requires lesser area and power. Area-delay product (ADP) of proposed CASEC(10,8,8), CASEC(18,16,8), 2xCASEC(10,8,4) codecs are better compared to the existing designs. [ABSTRACT FROM AUTHOR]

Shannon in his 1956 seminal paper introduced the concept of the zero error capacity, C0 , of a noisy channel. This is defined as the least upper bound of rates, at which, it is possible to transmit information with zero probability of error. At present not many codes are known to achieve the zero error capacity. In this paper, some codes which achieve zero error capacities in limited magnitude error channels are described. The code lengths of these zero error capacity achieving codes can be of any finite length $n=1,2,\ldots$ , in contrast to the long lengths required for the known regular capacity achieving codes, such as turbo codes, LDPC codes, and polar codes. Both wrap around and non-wrap around limited magnitude error models are considered in this paper. For non-wrap around error model, the exact value of zero error capacities is derived, and optimal non-systematic and systematic codes are designed. The non-systematic codes achieve the zero error capacity with any finite length. The optimal systematic codes achieve the systematic zero error capacity of the channel, which is defined as the zero error capacity with the additional requirements that the communication must be carried out with a systematic code. It is also shown that the rates of the proposed systematic codes are equal to or approximately equal to the zero error capacity of the channel. For the wrap around model bounds are derived for the zero error capacity and in many cases the bounds give the exact value. In addition, optimal wrap around non-systematic and systematic codes are developed which either achieve or are close to achieving the zero error capacity with finite length. [ABSTRACT FROM PUBLISHER]

Linear programming approaches have been applied to derive upper bounds on the size of classical and quantum codes. In this paper, we derive similar results for general quantum codes with entanglement assistance by considering a type of split weight enumerator. After deriving the MacWilliams identities for these enumerators, we are able to prove algebraic linear programming bounds, such as the Singleton bound, the Hamming bound, and the first linear programming bound. Our Singleton bound and Hamming bound are more general than the previous bounds for entanglement-assisted quantum stabilizer codes. In addition, we show that the first linear programming bound improves the Hamming bound when the relative distance is sufficiently large. On the other hand, we obtain additional constraints on the size of Pauli subgroups for quantum codes, which allow us to improve the linear programming bounds on the minimum distance of quantum codes of small length. In particular, we show that there is no $[[27, 15, 5]]$ or $[[28, 14, 6]]$ stabilizer code. We also discuss the existence of some entanglement-assisted quantum stabilizer codes with maximal entanglement. As a result, the upper and lower bounds on the minimum distance of maximal-entanglement quantum stabilizer codes with length up to 20 are significantly improved. [ABSTRACT FROM PUBLISHER]

Quantum error-correcting codes play the role of suppressing noise and decoherence in quantum systems by introducing redundancy. Some strategies can be used to improve the parameters of these codes. For example, entanglement can provide a way for quantum error-correcting codes to achieve higher rates than the one obtained by means of the traditional stabilizer formalism. Such codes are called entanglement-assisted quantum error-correcting (EAQEC) codes. In this paper, we utilize algebraic geometry codes to construct several families of EAQEC codes derived from the Euclidean and the Hermitian construction. Three families constructed here consist of codes whose quantum Singleton defect is equal to zero, one, or two. We also construct families of EAQEC codes with an encoding rate exceeding the quantum Gilbert-Varshamov bound. Additionally, asymptotically good towers of linear complementary dual codes are used to obtain asymptotically good families of EAQEC codes consuming maximal entanglement. Furthermore, a simple comparison with the quantum Gilbert-Varshamov bound demonstrates that, by utilizing the proposed construction, it is possible to generate an asymptotically family of EAQEC codes that exceeds this bound. [ABSTRACT FROM AUTHOR]

In this paper, a voltage-scaled SRAM for both error-free and error-tolerant applications is presented that dynamically manages the energy/quality trade-off based on application need. Two variation-resilient techniques, write assist and Error Correcting Code, are selectively applied to bit positions having larger impact on the overall quality, while jointly performing voltage scaling to improve overall energy efficiency. The impact of process variations, voltage and temperature on the energy-quality tradeoff is investigated. A 28 nm CMOS 32 kb SRAM shows 35% energy savings at iso-quality and operates at a supply 220 mV below a baseline voltage-scaled SRAM, at the cost of 1.5% area penalty. The impact of the SRAM quality at the system level is evaluated by adopting a H.264 video decoder as case study. [ABSTRACT FROM AUTHOR]

In this paper we extend the notion of locally repairable codes to secret sharing schemes. The main problem that we consider is to find optimal ways to distribute the shares of a secret among a set of storage-nodes (participants) such that the content of each node (share) can be recovered by using the contents of only few other nodes, and at the same time the secret can be reconstructed by only some allowable subsets of nodes. As a special case, an eavesdropper observing some set of specific nodes (such as less than certain number of nodes) does not get any information. In other words, we propose to study a locally repairable distributed storage system that is secure against a passive eavesdropper that can observe some subsets of nodes. We provide a number of results related to such systems, including upper bounds and achievability results on the number of bits that can be securely stored with these constraints. In particular, we provide conditions under which a locally repairable code can be turned into a secret sharing scheme and extend the results of secure repairable storage to cooperative repair and storage on networks. In addition, we consider perfect secret sharing schemes over general access structures under locality constraints and give an example of a perfect secret sharing scheme that can have small locality. Finally, we provide a lower bound on the size of a share compared with the size of the secret that shows how locality affects the sizes of shares in a perfect scheme. [ABSTRACT FROM PUBLISHER]

In this paper, we reinterpret the $(k+2,k)$ zigzag code in coding matrix and then propose an optimal exact repair strategy for its parity nodes, whose repair disk I/O approaches a lower bound derived in this paper. [ABSTRACT FROM PUBLISHER]

A new method to construct q-ary complementary sequence sets (CSSs) and complete complementary codes (CCCs) of size N is proposed by using desired para-unitary (PU) matrices. The concept of seed PU matrices is introduced and a systematic approach on how to compute the explicit forms of the functions in constructed CSSs and CCCs from the seed PU matrices is given. A general form of these functions only depends on a basis of the functions from ZN to Zq and representatives in the equivalent class of Butson-type Hadamard (BH) matrices. Especially, the realization of Golay pairs from our general form exactly coincides with the standard Golay pairs. The realization of ternary complementary sequences of size 3 is first reported here. For the realization of the quaternary complementary sequences of size 4, almost all the sequences derived here are never reported before. Generalized seed PU matrices and the recursive constructions of the desired PU matrices are also studied, and a large number of new constructions of CSSs and CCCs are given accordingly. From the perspective of this paper, all the known results of CSSs and CCCs with explicit GBF form in the literature (except non-standard Golay pairs) are constructed from the WHT matrices. This suggests that the proposed method with other BH matrices will yield a large number of new CSSs and CCCs with the significantly increasing number of the sequences of low peak-to-mean envelope power ratio. [ABSTRACT FROM AUTHOR]

This paper presents a novel PUF-based key generation architecture featuring run-time instability monitoring and adaptive error correction, overcoming the limitations of conventional architectures with fixed correction bits set at design or testing time. Run-time information from on-chip sensors is fused by a lightweight machine learning algorithm evaluating the minimum number of correction bits necessary to meet the required key error rate (KER). The number of correction bits in the subsequent error-correcting code (ECC) is made tunable and adapted accordingly. This reduces the dominant ECC energy compared to traditional correction bits margining for the worst case across corners, operating conditions, and application-specific KER target. The proposed architecture is demonstrated and exemplified by a 40-nm testchip implementing a monostable PUF, the proposed instability sensors, and BCH ECC featuring scalable correction. 1.8X energy reduction was measured over a baseline margined for iso-KER. Its 1.27 pJ/bit energy is the lowest compared to prior art that includes the necessary ECC. Adjustable correction also enables application-level energy-security tradeoff, saving energy when the KER target can be relaxed. On-chip monitoring reduces the traditionally high cost of PUF testing due to the necessary voltage/temperature sweeps. [ABSTRACT FROM AUTHOR]

We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints $P $ and $N $ respectively, the list decoding capacity is equal to $\frac {1}{2}\log \frac {P}{N}$. Random spherical codes achieve constant list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain conjecture that originates in analytic number theory is true, then the list size grows as a polynomial function of the gap-to-capacity. [ABSTRACT FROM AUTHOR]

Channel coding plays a pivotal role in ensuring reliable communication over wireless channels. With the growing need for ultra-reliable communication in emerging wireless use cases, the significance of channel coding has amplified. Furthermore, minimizing decoding latency is crucial for critical-mission applications, while optimizing energy efficiency is paramount for mobile and the Internet of Things (IoT) communications. As the fifth generation (5G) of mobile communications is currently in operation and 5G-advanced is on the horizon, the objective of this paper is to assess prominent channel coding schemes in the context of recent advancements and the anticipated requirements for the sixth generation (6G). In this paper, after considering the potential impact of channel coding on key performance indicators (KPIs) of wireless networks, we review the evolution of mobile communication standards and the organizations involved in the standardization, from the first generation (1G) to the current 5G, highlighting the technologies integral to achieving targeted KPIs such as reliability, data rate, latency, energy efficiency, spectral efficiency, connection density, and traffic capacity. Following this, we delve into the anticipated requirements for potential use cases in 6G. The subsequent sections of the paper focus on a comprehensive review of three primary coding schemes utilized in past generations and their recent advancements: low-density parity-check (LDPC) codes, turbo codes (including convolutional codes), and polar codes (alongside Reed-Muller codes). Additionally, we examine alternative coding schemes like Fountain codes (also known as rate-less codes), sparse regression codes, among others. Our evaluation includes a comparative analysis of error correction performance and the performance of hardware implementation for these coding schemes, providing insights into their potential and suitability for the upcoming 6G era. Lastly, we will briefly explore considerations such as higher-order modulations and waveform design, examining their contributions to enhancing key performance indicators in conjunction with channel coding schemes.

Recently, Etzion et al. introduced metrics on ${\mathbb{F}}_{2}^{n}$ based on directed graphs on $n$ vertices and developed some basic coding theory on directed graph metric spaces. In this paper, we consider the problem of classifying directed graphs, which admit the extended Hamming codes to be a perfect code. We first consider weighted poset metrics as a natural generalization of poset metrics and investigate interrelation between the weighted poset metrics and the directed graph-based metrics. In the next, we classify weighted posets on a set with eight elements and directed graphs on eight vertices, which admit the extended Hamming code $\tilde {\mathcal {H }}_{3}$ to be a two-perfect code. We also construct some families of such structures for any $k \geq 3$ , which can be viewed as generalizations of some results presented by Etzion et al. and Hyun and Kim. Those families enable us to construct packing or covering codes of radius 2 under certain maps. [ABSTRACT FROM AUTHOR]

The successive-cancellation list (SCL) and successive-cancellation flip (SCF) decoding can be used to improve the performance of polar codes, especially for short to moderate length codes. However, their serial decoding nature results in significant decoding latencies. Implementing some operations in parallel can reduce their decoding latencies. This paper presents fast implementations of the SCL and SCF decoders. In particular, we propose fast parallel list decoders for five newly identified types of nodes in the decoding tree of a polar code, which significantly improves the decoding latency. We also present novel fast SCF decoders that decode some special nodes in the decoding tree of a polar code without serially computing bit log-likelihood ratios. Using our proposed fast parallel SCF decoders, we observed an improvement up to 81% with respect to the original SCF decoder. This significant reduction in the decoding latency is observed without sacrificing the bit-error-rate performance of the code. [ABSTRACT FROM AUTHOR]

In recent years, communicating information using molecules via diffusion has attracted significant interest in bio-medical applications. To date, most of the studies have concentrated on point-to-point molecular communication (MC), whereas in a realistic environment, multiple MC transmitters are likely to transmit molecular messages simultaneously sharing the same propagation medium, resulting in significant performance variation of the MC system. In this type of large-scale MC system, the collective signal strength at the desired receiver can be impaired by the interference caused by other MC transmitters, which may degrade the system reliability and efficiency. This paper presents the first tractable analytical framework for the collective signal strength at a partially absorbing receiver due to the desired transmitter under the impact of a swarm of interfering transmitters in a 3D large-scale MC system using stochastic geometry. To combat the multi-user interference and the intersymbol interference (ISI) in the multi-user environment, we propose Reed–Solomon (RS) error correction coding, due to its high effectiveness in combating burst and random errors, as well as the two types of information molecule modulating scheme, where the transmitted bits are encoded using two types of information molecules at consecutive bit intervals. We derive analytical expressions for the bit error probability (BEP) of the large-scale MC system with the proposed two schemes to show their effectiveness. The results obtained using Monte Carlo simulations, match exactly with the analytical results, justifying the accuracy of the derivations. Results reveal that both schemes improve the BEP by a factor of 3–4 compared with that of a conventional MC system without using any ISI mitigation techniques. Due to the implementation simplicity, the two-type molecule encoding scheme is better than the RS error correction coding scheme, as the RS error correction coding scheme involves additional encoding and decoding process at both the transmitter and receiver nodes. Furthermore, the proposed analytical framework can be generalized to the analysis of other types of receiver designs and performance characterization in multi-user large-scale MC systems. Also, the two types of information molecule modulating scheme can be extended to M-type of information molecule modulating scheme without loss of generality. [ABSTRACT FROM AUTHOR]

In recent years, flash memory has been widely used in embedded systems, portable devices, and high-performance storage products due to its nonvolatility, shock resistance, low power consumption, and high performance natures. To reduce the product cost, multi-level-cell (MLC) flash memory has been proposed; compared with the traditional single-level-cell (SLC) flash memory that only stores one bit of data per cell, each MLC cell can store two or more bits of data. Thus MLC can achieve a larger capacity and reduce the cost per unit. However, MLC also suffers from the degradation in both performance and reliability. In this paper, we try to enhance the reliability and reduce the product cost of flash-memory-based solid-state drive (SSD) from a totally different perspective. We propose the half-level-cell (HLC) scheme to manage and reuse the worn-out space in SSD; through our management scheme, the system can treat two bad pages as a normal page without sacrificing performance and reliability. The proposed scheme is purely on software/firmware-level, thus there is no need to change the hardware. The experiment results show that the lifetime of SSD with our proposed HLC scheme can be extended to 50.56% under the Windows workload and up to 65.45% under the multimedia workload. When we apply the HLC scheme to flash-memory cache of hybrid storage systems, the response time can be improved up to 20.57%. [ABSTRACT FROM AUTHOR]

Error Correction Codes (ECCs) are commonly used to protect memories against soft errors with an impact on memory area and delay. For large memories, the area overhead is mostly due to the additional cells needed to store the parity check bits. In terms of delay, the overhead is mostly needed to detect and correct errors when the data is read from the memory. Most ECCs that can correct more than one error have a complex decoding process and so are limited in high speed memory applications. One exception is One Step Majority Logic Decodable (OS-MLD) codes for which decoding can be done in parallel at high speed. Unfortunately, there are only a few OS-MLD codes that provide a limited choice in terms of block sizes, error correction capabilities and code rate. Therefore, there is considerable interest in a novel construction of OS-MLD codes to provide additional choices for protecting memories. In this paper, a new method to construct Double Error Correction (DEC) OS-MLD codes is presented. This method is based on the use of parity check matrices in which two bits have at most two parity check equations in common; the proposed method provides codes that require a smaller number of parity check bits than existing codes like Orthogonal Latin Square (OLS) codes. The drawback of the proposed Two Bit Overlap (TBO) codes is that they require slightly more complex decoding than OLS codes. Therefore, they provide an intermediate solution between OLS and non OS-MLD codes in terms of decoding delay and number of parity check bits. The proposed TBO codes have been implemented for some block sizes and compared to both OLS and BCH codes to illustrate the trade off in delay and memory overhead. Finally, this paper discusses the generalization of the proposed scheme to codes with larger error correction capabilities. [ABSTRACT FROM AUTHOR]