Free-ride coding, as an approach that admits transmission of a few extra bits over a low-density parity-check (LDPC) coded link without bandwidth expansion, is applied in this paper to construct ...coupled LDPC codes. Firstly, we present a syndrome channel model and derive the lower and upper bounds on its capacity (referred to as accessible capacity), indicating the feasibility of the reliable transmission of extra bits. Secondly, we present the performance evaluation on both the word error rate (WER) and the bit error rate (BER) for the free-ride codes with simple lower and upper bounds. Then we propose three applications of free-ride coding to construct coupled LDPC codes, including implicit globally-coupled LDPC (GC-LDPC) codes, partial product-LDPC codes, and terminated spatially-coupled LDPC (SC-LDPC) codes, all of which have the figure of merits that they share the same code rates with the basic component LDPC codes. Simulation results show that: 1) the proposed GC-LDPC codes can outperform the component LDPC codes, yielding a coding gain of up to 0.8 dB; 2) the proposed product codes with (3, 6)-regular LDPC component codes of length 1024 can lower the WER from 10 -2 down to 10 -6 at the SNR around 2 dB; 3) the proposed terminated SC-LDPC codes can perform as well as the conventional terminated SC-LDPC codes but without any rate loss.
Randomly Punctured LDPC Codes Mitchell, David G. M.; Lentmaier, Michael; Pusane, Ali E. ...
IEEE journal on selected areas in communications,
02/2016, Volume:
34, Issue:
2
Journal Article
Peer reviewed
Open access
In this paper, we present a random puncturing analysis of low-density parity-check (LDPC) code ensembles. We derive a simple analytic expression for the iterative belief propagation (BP) decoding ...threshold of a randomly punctured LDPC code ensemble on the binary erasure channel (BEC) and show that, with respect to the BP threshold, the strength and suitability of an LDPC code ensemble for random puncturing is completely determined by a single constant that depends only on the rate and the BP threshold of the mother code ensemble. We then provide an efficient way to accurately predict BP thresholds of randomly punctured LDPC code ensembles on the binary-input additive white Gaussian noise channel (BI-AWGNC), given only the BP threshold of the mother code ensemble on the BEC and the design rate, and we show how the prediction can be improved with knowledge of the BI-AWGNC threshold. We also perform an asymptotic minimum distance analysis of randomly punctured code ensembles and present simulation results that confirm the robust decoding performance promised by the asymptotic results. Protograph-based LDPC block code and spatially coupled LDPC code ensembles are used throughout as examples to demonstrate the results.
It is always interesting and important to construct non-Reed-Solomon type MDS codes in coding theory and finite geometries. In this paper, we prove that many non-Reed-Solomon type MDS codes from ...arbitrary genus algebraic curves can be constructed. It is proved that MDS algebraic geometry (AG) codes from higher genus curves are not equivalent to MDS AG codes from lower genus curves. For genus one case, we construct MDS AG codes of small consecutive lengths from elliptic curves. New self-dual MDS AG codes over <inline-formula> <tex-math notation="LaTeX">{\mathbf{F}}_{2^{s}} </tex-math></inline-formula> from elliptic curves are also constructed. These MDS AG codes are not equivalent to Reed-Solomon codes, not equivalent to known MDS twisted Reed-Solomon codes and not equivalent to Roth-Lempel MDS codes. Hence many non-Reed-Solomon type MDS AG codes, which are not equivalent to known MDS twisted-Reed-Solomon codes and Roth-Lempel MDS codes, can be obtained from arbitrary genus algebraic curves. It is interesting open problem to construct explicit longer MDS AG codes from maximal curves.
One formidable difficulty in quantum communication and computation is to protect information-carrying quantum states against undesired interactions with the environment. To address this difficulty, ...many good quantum error-correcting codes have been derived as binary stabilizer codes. Fault-tolerant quantum computation prompted the study of nonbinary quantum codes, but the theory of such codes is not as advanced as that of binary quantum codes. This paper describes the basic theory of stabilizer codes over finite fields. The relation between stabilizer codes and general quantum codes is clarified by introducing a Galois theory for these objects. A characterization of nonbinary stabilizer codes over F q in terms of classical codes over F q 2 is provided that generalizes the well-known notion of additive codes over F 4 of the binary case. This paper also derives lower and upper bounds on the minimum distance of stabilizer codes, gives several code constructions, and derives numerous families of stabilizer codes, including quantum Hamming codes, quadratic residue codes, quantum Melas codes, quantum Bose-Chaudhuri-Hocquenghem (BCH) codes, and quantum character codes. The puncturing theory by Rains is generalized to additive codes that are not necessarily pure. Bounds on the maximal length of maximum distance separable stabilizer codes are given. A discussion of open problems concludes this paper
Locally repairable codes with hierarchical locality (H-LRCs) are designed to correct different numbers of erasures, which play a crucial role in large-scale distributed storage systems. In this ...paper, we construct three classes of <inline-formula> <tex-math notation="LaTeX">q </tex-math></inline-formula>-ary optimal H-LRCs by employing matrix product codes, concatenated codes and cyclic codes, respectively. The first two constructions are based on the idea of constructing new codes from old, which produces several new classes of optimal H-LRCs whose lengths can reach up to <inline-formula> <tex-math notation="LaTeX">q^{2}+q </tex-math></inline-formula> or unbounded. The final construction generates a class of new optimal cyclic H-LRCs whose lengths divide <inline-formula> <tex-math notation="LaTeX">q-1 </tex-math></inline-formula>. Compared with the previously known ones, our constructions are new in the sense that their parameters are not covered by the codes available in the literature.
Additive Asymmetric Quantum Codes Ezerman, M. F.; San Ling; Sole, P.
IEEE transactions on information theory,
08/2011, Volume:
57, Issue:
8
Journal Article
Peer reviewed
Open access
We present a general construction of asymmetric quantum codes based on additive codes under the trace Hermitian inner product. Various families of additive codes over F 4 are used in the construction ...of many asymmetric quantum codes over F 4 .
This paper presents a thorough performance analysis of dual-hop cognitive amplify-and-forward (AF) relaying networks under spectrum-sharing mechanism over independent nonidentically distributed ...(i.n.i.d.) Formula Omitted fading channels. In order to guarantee the quality of service (QoS) of primary networks, both the maximum tolerable peak interference power Formula Omitted at the primary users (PUs) and the maximum allowable transmit power Formula Omitted at the secondary users (SUs) are considered to constrain transmit power at the cognitive transmitters. For integer-valued fading parameters, a closed-form lower bound for the outage probability (OP) of the considered networks is obtained. Moreover, assuming arbitrary-valued fading parameters, the lower bound in integral form for the OP is derived. In order to obtain further insights into the OP performance, asymptotic expressions for the OP at high SNRs are derived, from which the diversity/coding gains and the diversity-multiplexing gain tradeoff (DMT) of the secondary network can be readily deduced. It is shown that the diversity gain and the DMT are solely determined by the fading parameters of the secondary network, whereas the primary network only affects the coding gain. The derived results include several others available in previously published studies as special cases, such as those for Nakagami- Formula Omitted fading channels. In addition, performance evaluation results have been obtained by Monte Carlo computer simulations, which have verified the accuracy of the theoretical analysis.
Binary code similarityapproaches compare two or more pieces of binary code to identify their similarities and differences. The ability to compare binary code enables many real-world applications on ...scenarios where source code may not be available such as patch analysis, bug search, and malware detection and analysis. Over the past 22 years numerous binary code similarity approaches have been proposed, but the research area has not yet been systematically analyzed. This article presents the first survey of binary code similarity. It analyzes 70 binary code similarity approaches, which are systematized on four aspects: (1) the applications they enable, (2) their approach characteristics, (3) how the approaches are implemented, and (4) the benchmarks and methodologies used to evaluate them. In addition, the survey discusses the scope and origins of the area, its evolution over the past two decades, and the challenges that lie ahead.
The explosion in the volumes of data being stored online has resulted in distributed storage 's transitioning to erasure coding based schemes. Local Reconstruction Codes (LRCs) have emerged as the ...codes of choice for these applications. These codes can correct a small number of erasures (which is the typical case) by accessing only a small number of remaining coordinates. An <inline-formula> <tex-math notation="LaTeX">(n,r,h,a,q) </tex-math></inline-formula>-LRC is a linear code over <inline-formula> <tex-math notation="LaTeX">\mathbb {F}_{q} </tex-math></inline-formula> of length <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula>, whose codeword symbols are partitioned into <inline-formula> <tex-math notation="LaTeX">g=n/r </tex-math></inline-formula> local groups each of size <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula>. Each local group has <inline-formula> <tex-math notation="LaTeX">a </tex-math></inline-formula> local parity checks that allow recovery of up to <inline-formula> <tex-math notation="LaTeX">a </tex-math></inline-formula> erasures within the group by reading the unerased symbols in the group. There are a further <inline-formula> <tex-math notation="LaTeX">h </tex-math></inline-formula> "heavy" parity checks to provide fault tolerance from more global erasure patterns. Such an LRC is Maximally Recoverable (MR), if it corrects all erasure patterns which are information-theoretically correctable under the stipulated structure of local and global parity checks, namely patterns with up to <inline-formula> <tex-math notation="LaTeX">a </tex-math></inline-formula> erasures in each local group and an additional <inline-formula> <tex-math notation="LaTeX">h </tex-math></inline-formula> (or fewer) erasures anywhere in the codeword. The existing constructions require fields of size <inline-formula> <tex-math notation="LaTeX">n^{\Omega (h)} </tex-math></inline-formula> while no superlinear lower bounds were known for any setting of parameters. Is it possible to get linear field size similar to the related MDS codes (e.g., Reed-Solomon codes)? In this work, we answer this question by showing superlinear lower bounds on the field size of MR-LRCs. When <inline-formula> <tex-math notation="LaTeX">a,h </tex-math></inline-formula> are constant and the number of local groups <inline-formula> <tex-math notation="LaTeX">g \geqslant h </tex-math></inline-formula>, while <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula> may grow with <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula>, our lower bound simplifies to <inline-formula> <tex-math notation="LaTeX">q \geqslant \Omega _{a,h}\left ({n\cdot r^{\min \{a,h-2\}}}\right) </tex-math></inline-formula>. MR-LRCs deployed in practice have a small number of global parities, typically <inline-formula> <tex-math notation="LaTeX">h=2,3 </tex-math></inline-formula>. We complement our lower bounds by giving constructions with small field size for <inline-formula> <tex-math notation="LaTeX">h \leqslant 3 </tex-math></inline-formula>. When <inline-formula> <tex-math notation="LaTeX">h=2 </tex-math></inline-formula>, we give a linear field size construction, whereas previous constructions required quadratic field size in some parameter ranges. Note that our lower bound is superlinear only if <inline-formula> <tex-math notation="LaTeX">h \geqslant 3 </tex-math></inline-formula>. When <inline-formula> <tex-math notation="LaTeX">h=3 </tex-math></inline-formula>, we give a construction with <inline-formula> <tex-math notation="LaTeX">O(n^{3}) </tex-math></inline-formula> field size, whereas previous constructions needed <inline-formula> <tex-math notation="LaTeX">n^{\Theta (a)} </tex-math></inline-formula> field size. This makes the choices <inline-formula> <tex-math notation="LaTeX">r=3, a=1, h=3 </tex-math></inline-formula> the next simplest non-trivial setting to investigate regarding the existence of MR-LRCs over fields of near-linear size. We answer this question in the positive via a novel approach based on elliptic curves and arithmetic progression free sets.
In recent years, due to the spread of multi-level non-volatile memories (NVMs), Formula Omitted-ary write-once memory (WOM) codes have been extensively studied. By using WOM codes, it is possible to ...rewrite NVMs Formula Omitted times before erasing the cells. Use of WOM codes enables the improvement of the performance of the storage device; however, it may also increase errors caused by inter-cell interference (ICI). This paper presents WOM codes that restrict the imbalance between code symbols throughout the write sequence, hence decreasing ICI. We first specify the imbalance model as a bound Formula Omitted on the difference between codeword levels. Then, a two-cell code construction for general Formula Omitted and input size is proposed. An upper bound on the write count is also derived, showing the optimality of the proposed construction. In addition to direct WOM constructions, we derive closed-form optimal write regions for codes constructed with continuous lattices. On the coding side, the proposed codes are shown to be competitive with known codes not adhering to the bounded imbalance constraint. On the memory side, we show how the codes can be deployed within flash wordlines, and quantify their bit-error rate advantage using accepted ICI models.
PDF
![[Formula Omitted]-Imbalance...](http://api.summon.serialssolutions.com/2.0.0/image/issn/XR4PS5YY4K/0733-8716/small "[Formula Omitted]-Imbalance WOM Codes for Reduced Inter-Cell Interference in Multi-Level NVMs")