Search

Tietäväinen’s upper and lower bounds assert that for block-length- $n$ linear codes with dual distance $d$ , the covering radius $R$ is at most $({n}/{2})-(({1}/{2})-o(1))\sqrt {dn}$ and typically at least $({n}/{2})-\Theta (({dn\log {({n}/{d})}})^{1/2})$. The gap between those bounds on $R -({n}/{2})$ is a $\Theta (({\log {({n}/{d})}})^{1/2})$ factor related to the gap between the worst covering radius given $d$ and the sphere-covering bound. Our focus in this paper is on the case when $d = o(n)$ , i.e., when the code size is subexponential and the gap is $w(1)$. We show that up to a constant, the gap can be eliminated by relaxing the covering requirement to allow for missing $o(1)$ fraction of points. Namely, if the dual distance $d = o(n)$ , then for sufficiently large $d$ , almost all points can be covered with radius $R\leq ({n}/{2})-\Theta (({dn\log {({n}/{d})}})^{1/2})$. Compared with random linear codes, our bound on $R-({n}/{2})$ is asymptotically tight up to a factor less than 3. We give applications to dual-BCH codes. The proof builds on the author’s previous work on the weight distribution of cosets of linear codes, which we simplify in this paper and extend from codes to probability distributions on $\{0,1\}^{n}$ , thus enabling the extension of the earlier result to $(d-1)$ -wise independent distributions. [ABSTRACT FROM AUTHOR]

In addition to their applications in data storage, communications systems, and consumer electronics, linear complementary dual (LCD) codes—a class of linear codes—have been employed in cryptography recently. LCD cyclic codes were referred to as reversible cyclic codes in the literature. The objective of this paper is to construct several families of reversible cyclic codes over finite fields and analyze their parameters. The LCD cyclic codes presented in this paper have very good parameters in general, and contain many optimal codes. A well rounded treatment of reversible cyclic codes is also given in this paper. [ABSTRACT FROM PUBLISHER]

Because of their efficient encoding and decoding algorithms, cyclic codes—an interesting class of linear codes—are widely used in communication systems, storage devices, and consumer electronics. BCH codes form a special class of cyclic codes, and are usually among the best cyclic codes. A subclass of good BCH codes is the narrow-sense primitive BCH codes. However, the dimension and minimum distance of these codes are not known in general. The main objective of this paper is to study the dimension and minimum distances of a subclass of the narrow-sense primitive BCH codes with design distance \delta =(q-\ell 0)q^{m-\ell 1-1}-1 for certain pairs (\ell 0, \ell 1) , where 0 \leq \ell 0 \leq q-2 and 0 \leq \ell 1 \leq m-1 . The parameters of other related classes of BCH codes are also investigated, and some open problems are proposed in this paper. [ABSTRACT FROM PUBLISHER]

Cyclic codes are widely employed in communication systems, storage devices, and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over \mathrm GF(q) with length n=(q^m-1)/(q-1) . Little is known about this class of BCH codes when $q>2$ . The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length n=(3^{m}-1)/2 are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated. [ABSTRACT FROM PUBLISHER]

BCH codes are an important class of cyclic codes which have applications in satellite communications, DVDs, disk drives, and two-dimensional bar codes. Although BCH codes have been widely studied, their parameters are known for only a few special classes. Recently, Ding et al. made some new progress in BCH codes. However, we still have very limited knowledge on the dimension of BCH codes, not to mention the weight distribution of BCH codes. In this paper, we generalize the results on BCH codes from several previous papers. 1) The dimension of narrow-sense BCH codes of length $((q^{m}-1)/{\lambda })$ with designed distance $2\leq \delta \leq (({q^{\lceil (m+1)/2 \rceil }-1})/(\lambda)+1)$ is settled, where $\lambda $ is any factor of $(q-1)$. 2) The weight distributions of two classes of narrow-sense BCH codes of length $(({q^{m}-1})/2)$ with designed distance $\delta =(({(q-1)q^{m-1}-q^{\lfloor (m-1)/2\rfloor }-1})/2)$ and $\delta =(({(q-1)q^{m-1}-q^{\lfloor (m+1)/2\rfloor }-1})/2)$ are determined. 3) The weight distribution of a class of BCH codes of length $((q^{m}-1)/({q-1}))$ is determined. In particular, a subclass of this class of BCH codes is optimal with respect to the Griesmer bound. Some optimal linear codes obtained from this class of BCH codes are characterized. [ABSTRACT FROM AUTHOR]

In this paper, we present the block Markov superposition transmission of BCH (BMST-BCH) codes, which can be constructed to obtain a very low error floor. To reduce the implementation complexity, we design a low complexity iterative sliding-window decoding algorithm, in which only binary and/or erasure messages are processed and exchanged between processing units. The error floor can be predicted by the proposed genie-aided lower bounds, while the waterfall performance can be analyzed by the density evolution method. To evaluate the error floor of the constructed BMST-BCH codes at a very low bit error rate (BER) region, we propose a fast simulation approach. Numerical results show that, at a target BER of $10^{-15}$ , the proposed BMST-BCH code with hard-decision can achieve a net coding gain (NCG) of 10.55 dB with 25% overhead, while a soft-decision design can yield an NCG of 10.74 dB. The construction of BMST-BCH codes is flexible to trade off latency against performance at all overheads of interest and may find applications in optical transport networks as an attractive candidate. [ABSTRACT FROM AUTHOR]

Binary quasi-reversible BCH codes whose defining set contains consecutive elements from negative to positive integers have received considerable attention in recent years due to their efficient decoding suitable for a wide range of applications. This paper combines the concept of the weight and quasi-reversible structures to introduce two subclasses of BCH codes: odd-like/even-like quasi-reversible BCH codes. The step-by-step decoding of these codes is developed as follows: First, the weight evaluation of a received polynomial is able to judge whether the number of errors is odd or even, which helps to simplify the decoding processes. Second, based on Chiò’s pivotal condensation process which can be easily implemented in a parallel computing architecture, the determinant calculation of the band matrix instead of Peterson’s matrix in column-echelon form is faster. Third, a newly proposed non-monic error-locator polynomial is sparser than the conventional ones. As a consequence, the theoretical analysis and experimental results validate potential benefits in requiring fewer finite field additions and multiplications used in the decoding of binary odd-like/even-like quasi-reversible BCH codes up to half the minimum distance when compared with the narrow-sense BCH codes with small error-correcting capability. [ABSTRACT FROM AUTHOR]

For the recently developed quasi-reversible BCH codes with long lengths and high error-correcting capability, this paper is aimed at proposing a new and faster decoding procedure. It consists of four steps: 1) compute the consecutive syndromes; 2) calculate the syndrome functions by the forward and backward recursions; 3) solve a linear subsystem together with one matrix multiplication in order to find an error-locator polynomial; 4) determine the errors from the obtained polynomial by using the root-finding algorithm. This procedure, especially in Steps 2 and 3, differs greatly from the conventional procedures, which determine an error-locator polynomial directly from solving a linear system with the aid of the consecutive syndromes. The key idea behind this decoding technique is that the computational complexity of such a small subsystem instead of an originally large linear system can be significantly reduced, although there are additional forward and backward syndrome calculations with low complexity increasing. Finally, the illustrative examples and numerical simulations can be helpful to demonstrate the accuracy and efficacy of the presented decoding technique at different error-correcting capabilities. [ABSTRACT FROM AUTHOR]

Interleaved Reed–Solomon codes admit efficient decoding algorithms which correct burst errors far beyond half the minimum distance in the random errors regime, e.g., by computing a common solution to the Key Equation for each Reed–Solomon code, as described by Schmidt et al. If this decoder does not succeed, it may either fail to return a codeword or miscorrect to an incorrect codeword, and good upper bounds on the fraction of error matrices for which these events occur are known. The decoding algorithm immediately applies to interleaved alternant codes as well, i.e., the subfield subcodes of interleaved Reed–Solomon codes, but the fraction of decodable error matrices differs, since the error is now restricted to a subfield. In this paper, we present new general lower and upper bounds on the fraction of error matrices decodable by Schmidt et al.’s decoding algorithm, thereby making it the only decoding algorithm for interleaved alternant codes for which such bounds are known. [ABSTRACT FROM AUTHOR]

This paper is devoted to studying two main problems: 1) computing the apparent distance of an Abelian code and 2) giving a notion of Bose, Ray-Chaudhuri, Hocquenghem (BCH) multivariate code. To do this, we first strengthen the notion of an apparent distance by introducing the notion of a strong apparent distance; then, we present an algorithm to compute the strong apparent distance of an Abelian code, based on some manipulations of hypermatrices associated with its generating idempotent. Our method uses less computations than those given by Camion and Sabin; furthermore, in the bivariate case, the order of computation complexity is reduced from exponential to linear. Then, we use our techniques to develop a notion of a BCH code in the multivariate case, and we extend most of the classical results on cyclic BCH codes. Finally, we apply our method to the design of Abelian codes with maximum dimension with respect to a fixed apparent distance and a fixed length. [ABSTRACT FROM AUTHOR]

Cyclic codes are an interesting class of linear codes due to their efficient encoding and decoding algorithms. Bose-Ray-Chaudhuri-Hocquenghem (BCH) codes form a subclass of cyclic codes and are very important in both theory and practice as they have good error-correcting capability and are widely used in communication systems, storage devices, and consumer electronics. However, the dimension and minimum distance of BCH codes are not known in general. The objective of this paper is to determine the Bose and minimum distances of a class of narrow-sense primitive BCH codes. [ABSTRACT FROM AUTHOR]

Forward error correction (FEC) plays a vital role in coherent optical systems employing multi-level modulation. However, much of coding theory assumes that additive white Gaussian noise (AWGN) is dominant, whereas coherent optical systems have significant phase noise (PN) in addition to AWGN. This changes the error statistics and impacts FEC performance. In this paper, we propose a novel semianalytical method for dimensioning binary Bose-Chaudhuri-Hocquenghem (BCH) codes for systems with PN. Our method involves extracting statistics from pre-FEC bit error rate (BER) simulations. We use these statistics to parameterize a bivariate binomial model that describes the distribution of bit errors. In this way, we relate pre-FEC statistics to post-FEC BER and BCH codes. Our method is applicable to pre-FEC BER around 10-3 and any post-FEC BER. Using numerical simulations, we evaluate the accuracy of our approach for a target post-FEC BER of 10-5. Codes dimensioned with our bivariate binomial model meet the target within 0.2-dB signal-to-noise ratio. [ABSTRACT FROM PUBLISHER]

Several new families of multi-memory classical convolutional Bose-Chaudhuri-Hocquenghem codes as well as families of unit-memory quantum convolutional codes are constructed in this paper. Our unit-memory classical and quantum convolutional codes are optimal in the sense that they attain the classical (quantum) generalized Singleton bound. The constructions presented in this paper are performed algebraically and not by computational search. [ABSTRACT FROM PUBLISHER]

Historically, LCD cyclic codes were referred to as reversible cyclic codes, which had applications in data storage. Due to a newly discovered application in cryptography, there has been renewed interest in LCD codes. In this paper, we explore two special families of LCD cyclic codes, which are both BCH codes. The dimensions and the minimum distances of these LCD BCH codes are investigated. [ABSTRACT FROM AUTHOR]

The Rosenbloom–Tsfasman metric has attracted the attention of many researchers as a generalization of the Hamming metric that is relevant to practical problems. Codes for this metric were considered. In particular, Reed–Solomon codes were generalized to be compatible with this metric. In this paper, a generalization of BCH codes for the Rosenbloom–Tsfasman metric is proposed. This generalization is based on considering BCH codes as subfield subcodes of Reed–Solomon codes. By characterizing these subfield subcodes, an explicit construction of BCH codes for the Rosenbloom–Tsfasman metric is provided. Two important properties of Reed–Solomon codes and BCH codes for the Rosenbloom–Tsfasman metric are studied and compared with those for the Hamming metric. These properties are cyclic structure and duality. The approach is based on Galois-Fourier transforms associated with Hasse derivatives. [ABSTRACT FROM PUBLISHER]

In this paper, we compare performance of three classes of forward error correction schemes for 40-Gb/s optical transmission systems. The first class is based on the concatenation of Reed-Solomon codes and this is employed in the state-of-the-art fiber-optics communication systems. The second class is the turbo product codes with Bose-Chaudhuri-Hocquenghen component codes. The application of these codes in optical communication systems was extensively studied by Sab and Lemarie, and Mizuochi The third class is the low-density parity-check (LDPC) codes that have attracted much attention over the past decade. We present enhanced decoding algorithms for Turbo product codes and LDPC codes that use probability density function of output sequences instead of calculating initial likelihood ratios assuming (inaccurate) Gaussian or chi-square approximation. The analysis in this paper shows that the LDPC codes perform better than the other codes in the waterfall region at bit error rates as low as 10-9. We also presented error floors results obtained by analyzing decoding failures of hard-decision iterative decoders [ABSTRACT FROM PUBLISHER]

We analyze interleaved concatenation schemes of polar codes with outer binary BCH codes and convolutional codes. We show that both BCH-polar and Conv-polar codes can have a frame error rate that decays exponentially with the code length for all rates up to capacity, which is a substantial improvement in the error exponent over stand-alone polar codes. Interleaved concatenation with long constraint length convolutional codes is an effective way to leverage the fact that polarization increases the cutoff rate of the channel. Simulation results show that Conv-polar codes when decoded with the proposed soft-output multistage iterative decoding algorithm can outperform stand-alone polar codes decoded with successive cancellation or belief propagation decoding. It may be comparable to stand-alone polar codes with list decoding in the high SNR regime. In addition to this, we show that the proposed concatenation scheme requires lower memory and decoding complexity in comparison to belief propagation and list decoding of polar codes. Practically, the scheme enables rate compatible outer codes which ease hardware implementation. Our results suggest that the proposed method may strike a better balance between performance and complexity compared to existing methods in the finite-length regime. [ABSTRACT FROM AUTHOR]

BCH codes are an interesting type of cyclic codes and have wide applications in communication and storage systems. Generally, it is very hard to determine the minimum distances of BCH codes. In this paper, we determine the weight distributions of two classes of primitive BCH codes $\mathcal C_{(q, m, \delta _{2})}$ and $\mathcal C_{(q, m, \delta _{3})}$ and their extended codes, which solve two problems proposed by Ding et al. It is shown that the extended codes $\overline {\mathcal C}_{(q, m, \delta _{2})}$ have four nonzero weights. We also employ the Hartmann-Tzeng bound to present the minimum distance of the dual code $\mathcal C_{(q, m, \delta _{2})}^\perp $ for $q \ge 5$. Inspired by the idea, we then determine the dimensions of a class of cyclic codes and give lower bounds on their minimum distances, which is greatly improved comparing with the BCH bound. Some optimal codes are obtained. [ABSTRACT FROM AUTHOR]

New quantum maximum-distance-separable (MDS) codes with parameters [[q^2 + 1, q^2 -2d + 3, d]]q, where q=2^t, t\geq 1 and 3\leq d\leq q+1 is an odd integer, are constructed in this paper. [ABSTRACT FROM PUBLISHER]

The Adaptive Belief Propagation (ABP) algorithm was recently proposed by Jiang and Narayanan for the soft decoding of Reed-Solomon (RS) codes. In this paper, simplified versions of this algorithm are investigated for the turbo decoding of product codes. The complexity of the Turbo-oriented Adaptive Belief propagation (TAB) algorithm is significantly reduced by moving the matrix adaptation step outside of the belief propagation iteration loop. A reduced-complexity version of the TAB algorithm that offers a trade-off between performance and complexity is also proposed. Simulation results for the turbo decoding of product codes show that belief propagation based on adaptive parity check matrices is a practical alternative to the currently very popular Chase-Pyndiah algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we adopt a restricted Gaussian elimination on the Hankel structured augmented syndrome matrix to reinterpret an early-stopped version of the Berlekamp-Massey algorithm in which only (t + e) iterations are needed to be performed for the decoding of BCH codes up to t errors, where a is the number of errors actually occurred with e ≤ t, instead of the 2t iterations required in the conventional Berlekamp-Massey al- gorithm. The minimality of (t + e) iterations in this early-stopped Berlekamp-Massey (ESBM) algorithm is justified and related to the subject of simultaneous error correction and detection in this paper. We show that the multiplicative complexity of the ESBM algorithm is upper bounded by (te + e² - 1)∀e ≤ t and except for a trivial case, the ESBM algorithm is the most efficient algorithm for finding the error-locator polynomial. [ABSTRACT FROM AUTHOR]

In this paper, we establish the connection between the Orthogonal Optical Codes (OOC) and binary compressed sensing matrices. We also introduce deterministic bipolar m\times n RIP fulfilling \pm 1 matrices of order k such that m\leq \cal O\big (k (\log 2 n)^{{ \log 2 k}\over { \ln \log 2 k}}\big ). The columns of these matrices are binary BCH code vectors where the zeros are replaced by -1. Since the RIP is established by means of coherence, the simple greedy algorithms such as Matching Pursuit are able to recover the sparse solution from the noiseless samples. Due to the cyclic property of the BCH codes, we show that the FFT algorithm can be employed in the reconstruction methods to considerably reduce the computational complexity. In addition, we combine the binary and bipolar matrices to form ternary sensing matrices (\0,1,-1\ elements) that satisfy the RIP condition. [ABSTRACT FROM AUTHOR]

The Lee metric measures the circular distance between two elements in a cyclic group and is particularly appropriate as a measure of distance for data transmission under phase-shift-keying modulation over a white noise channel. In this paper, using newly derived properties on Newton's identities, we initially investigate the Lee distance properties of a class of BCH codes and show that (for an appropriate range of parameters) their minimum Lee distance is at least twice their designed Hamming distance. We then make use of properties of these codes to devise an efficient algebraic decoding algorithm that successfully decodes within the above lower bound of the Lee error-correction capability. Finally, we propose an attractive design for the corresponding VLSI architecture that is only mildly more complex than popular decoder architectures under the Hamming metric; since the proposed architecture can also be used for decoding under the Hamming metric without extra hardware, one can use the proposed architecture to decode under both distance metrics (Lee and Hamming). [ABSTRACT FROM AUTHOR]

The peak-to-mean envelope power ratio (PMEPR) of a code employed in orthogonal frequency-division multiplexing (OFDM) systems can be reduced by permuting its coordinates and by rotating each coordinate by a fixed phase shift. Motivated by some previous designs of phase shifts using suboptimal methods, the following question is considered in this paper. For a given binary code, how much PMEPR reduction can be achieved when the phase shifts are taken from a 2h-ary phase-shift keying (2h-PSK) constellation? A lower bound on the achievable PMEPR is established, which is related to the covering radius of the binary code. Generally speaking, the achievable region of the PMEPR shrinks as the covering radius of the binary code decreases. The bound is then applied to some well understood codes, including nonredundant BPSK signaling, BCH codes and their duals, Reed-Muller codes, and convolutional codes. It is demonstrated that most (presumably not optimal) phase-shift designs from the literature attain or approach our bound. [ABSTRACT FROM AUTHOR]

A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC. [ABSTRACT FROM AUTHOR]

Targeting on the future fault-prone hybrid CMOS/nanodevice digital memories, this paper presents two fault-tolerance design approaches that integrally address the tolerance for defects and transient faults. These two approaches share several key features, including the use of a group of Bose-Chaudhuri-Hocquenghem (BCH) codes for both defect tolerance and transient fault tolerance, and integration of BCH code selection and dynamic logical-to-physical address mapping. The first approach is straightforward and easy to implement but suffers from a rapid drop of achievable storage capacity as defect densities and/or transient fault rates increase, while the second approach can achieve much higher storage capacity under high defect densities and/or transient fault rates at the cost of higher implementation complexity and longer memory access latency. Based on extensive computer simulations and BCH decoder circuit design, we have demonstrated the effectiveness of the presented approaches under a wide range of defect densities and transient fault rates, while taking into account of the fault-tolerance storage overhead and BCH decoder implementation cost in CMOS domain [ABSTRACT FROM PUBLISHER]

Every bit of information in a storage or memory device is bound by a multitude of performance specifications, and is subject to a variety of reliability impediments. At the other end, the physical processes tamed to remember our bits offer a constant source of risk to their reliability. These include a variety of noise sources, access restrictions, intercell interferences, cell variabilities, and many more issues. Tying together this vector of performance figures with that vector of reliability issues is a rich matrix of emerging coding tools and techniques. Channel coding schemes ensure target reliability and performance and have been at the core of memory systems since their nascent age. In this survey, we first overview the fundamentals of channel coding and summarize well-known codes that have been used in nonvolatile memories (NVMs). Next, we demonstrate why the conventional coding approaches ubiquitously based on symmetric channel models and optimization for the Hamming metric fail to address the needs of modern memories. We then discuss several recently proposed innovative coding schemes. Behind each coding scheme lies an interesting theoretical framework, building on deep ideas from mathematics and the information sciences. We also survey some of the most fascinating bridges between deep theory and storage performance. While the focus of this survey is primarily on the pervasive multilevel NAND Flash, we envision that other benefiting memory technologies will include phase change memory, resistive memories, and others. [ABSTRACT FROM PUBLISHER]

We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes, our method exploits code symmetry. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In other words, we show that symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed–Muller codes with increasing blocklength and converging rate achieves capacity. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to all affine-invariant codes and, thus, to extended primitive narrow-sense BCH codes. This also resolves, in the affirmative, the existence question for capacity-achieving sequences of binary cyclic codes. The primary tools used in the proof are the sharp threshold property for symmetric monotone Boolean functions and the area theorem for extrinsic information transfer functions. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the GLDPC codes with Reed-Muller (RM) and Bose-Chaudhuri-Hocquenghem (BCH) codes as component codes. GLDPC codes with RM codes as component codes is an attractive option for high-speed optical transmission because they provide excellent coding gains, while the RM codes can be decoded using low-complexity maximum a posteriori probability (MAP) decoding based on fast Walsh-Hadamard transform. Several classes of GLDPC codes (with component RM or BCH codes) outperforming the turbo product codes in terms of decoding complexity and coding gain are presented. We also identify several turbo product codes suitable for use in optical communications. [ABSTRACT FROM PUBLISHER]

Generalized integrated interleaved (GII) codes nest short BCH sub-codewords to form more powerful BCH codewords. They can potentially achieve hyper-speed decoding with excellent error-correction capability. In particular, short GII-BCH codes are among the best candidates for the new fast storage class memories (SCMs). Miscorrections severely degrade the performance of short GII-BCH codes. Although they were effectively mitigated in previous designs, the involved repeated Chien search and higher-order syndrome computation cause long latency. This brief proposes efficient and low-latency nested decoding schemes for short GII-BCH codes. A strategy is developed to select sub-words for further nested decoding to mitigate miscorrections by keeping track of the error locator polynomials, instead of waiting for the lengthy Chien search. Formulas are also derived to estimate the effects on the error-correcting performance. Besides, a low-complexity linear feedback shift register (LFSR) architecture is developed to accelerate the higher-order nested syndrome computation. For an example GII-BCH code targeting at SCMs, the proposed design reduces the worst-case nested decoding latency by 26% with 8.5% area overhead and negligible performance loss compared to prior methods. [ABSTRACT FROM AUTHOR]

An extension of polar codes is proposed, which allows some of the frozen symbols, called dynamic frozen symbols, to be data-dependent. A construction of polar codes with dynamic frozen symbols, being subcodes of extended BCH codes, is proposed. The proposed codes have higher minimum distance than classical polar codes, but still can be efficiently decoded using the successive cancellation algorithm and its extensions. The codes with Arikan, extended BCH and Reed-Solomon kernel are considered. The proposed codes are shown to outperform LDPC and turbo codes, as well as polar codes with CRC. [ABSTRACT FROM AUTHOR]

The bilateral minimum distance of a binary linear code is the maximum d such that all nonzero codewords have weights between d and n-d . Let be a binary linear code whose dual has bilateral minimum distance at least d , where d is odd. Roughly speaking, we show that the average L_\infty -distance—between the weight distribution of a random cosets of Q and the binomial distribution decays quickly as the bilateral minimum distance d of the dual of Q increases. For d = \Theta (1) . On the other d=\Theta (n) extreme, it decays like and e^{-\Theta (d)} . It follows that, almost all cosets of Q have weight distributions very close to the to the binomial distribution. In particular, we establish the following bounds. If the dual of Q has bilateral minimum distance at least d=2t+1 , where t\geq 1 -distance is at most \min \ (e\ln (n/2t))^t(2t/n)^(t/2), \sqrt 2 e^-(t/10)\ . For the average L1 -distance, we conclude the bound \min \ (2t+1)(e\ln (n/2t))^t (2t/n)^(t/2)-1, \sqrt 2(n+1)e^-(t/10)\ , which gives nontrivial results for $t\geq 3$ . We give applications to the weight distribution of cosets of extended Hadamard codes and extended dual BCH codes. Our argument is based on Fourier analysis, linear programming, and polynomial approximation techniques. [ABSTRACT FROM PUBLISHER]

Today’s communication system design heavily depends on computer simulation for performance evaluation. The burgeoning ultra-reliable communication systems, however, pose a significant simulation challenge as such systems operate at very low packet error rates (PERs) whereas the required simulation time of the conventional Monte Carlo (MC) method is many times the inverse of the PER. Various importance sampling-type techniques have been developed for more efficient simulation of channel-coded transmission, but they typically rely on exploiting code weaknesses (for the generation of error-causing noise samples) and most works on soft-decision decoding only treat binary signaling. In this paper, we propose to use a function, termed the noise gauging function (NGF), that roughly measures the error-causing propensity of noise samples and we present a way to adaptively optimize the noise sampling under such a function for simulation efficiency. Both binary and nonbinary signalings are considered. And the proposed technique does not require detailed knowledge of the code weaknesses, although some high-level understanding of the code properties can benefit the design of efficient NGFs. We investigate the application of the proposed technique to several common channel codes. Numerical results indicate an approximately 10- to 1,000-fold speedup versus MC.

Generalized integrated interleaved (GII) error-correcting codes nest sub-codewords to form codewords of more powerful codes. They can achieve hyper-speed decoding with good error correction capability. For GII codes built on BCH codes, the first decoding stage is to decode individual BCH sub-words. This stage largely determines the throughput and dominates the area of the overall decoder. Unlike that in traditional BCH decoding, longer polynomials need to be kept in the key-equation solver (KES) step of the first stage in order to continue the KES step in the second-stage nested decoding of GII codes. To take advantage of the very fast storage class memories (SCMs), GII codes with 3-error-correcting BCH sub-codewords can be utilized. This brief proposes a low-complexity and high-speed design for the KES of 3-error-correcting BCH sub-word decoding. Formulas are developed to compute the KES results directly instead of utilizing the traditional iterative process. More importantly, through analyzing the properties of the involved variables, the coefficients are scaled and reformulated to substantially reduce the complexity. Detailed hardware implementation architectures are also developed in this brief. Our design achieves three times throughput with 20.2% smaller area than the best prior design for a code over $GF(2^{10})$. [ABSTRACT FROM AUTHOR]

We generalize Steane's enlargement construction of binary quantum codes to q-ary quantum codes.We then apply this result to BCH codes and the study of asymptotic bounds, and obtain improvements to the quantum BCH codes constructed by Aly and Klappenecker and the quantum asymptotic bounds from algebraic geometry codes obtained by Feng, Ling, and Xing. [ABSTRACT FROM AUTHOR]

A novel method to recursively construct a set of precoded polar codes of various rates and short-to-moderate lengths is presented. The proposed code design method minimizes the successive cancellation (SC) decoding error probability estimate under three constraints. The first constraint is the minimum distance requirement to improve the maximum-likelihood (ML) performance of the resulting code and therefore the performance under the SC list (SCL) decoding. The other two constraints introduce preselected supercode and subcode, where the supercode ensures fast computation of the minimum distance and the subcode ensures reduction of the search space size. The supercode is given by the Plotkin sum of shorter codes, which are nested to simplify computation of low-weight codewords. These low-weight codewords are needed to satisfy the minimum distance constraint. The simulation results indicate that the proposed precoded polar codes of lengths 128 and 256 provide a better frame error rate (FER) than polar codes with CRC and e-BCH polar subcodes under the SCL decoding algorithm with the list size $8-128$. [ABSTRACT FROM AUTHOR]

The design of a single-chip optical transceiver to optimize the performance of a short-distance optical datalink is proposed. The transceiver includes an embedded hybrid automatic repeat request (ARQ) controller capable of operation at several gigahertz clock rates. The hybrid ARQ controller uses a combination of packet retransmission protocols and forward error correction (FEC) to minimize bit errors and achieve a transmitter power coding gain of several dB. Conventional FEC codes such as Reed-Solomon codes cannot be used due to their excessive hardware cost and delays. A practical multilevel coding scheme is explored. The inner codes consist of small linear block codes with reasonable FEC capability, such as small BCH codes, which can be encoded and decoded with reasonable hardware cost and delay. The outer code for a complete packet consists of a long linear block code with excellent error detection ability, such as a cycle redundancy check code. Low-power pipelined on-chip FEC decoders with estimated throughputs of several hundred gigabits per second per square millimeter are proposed. Mathematical analysis indicates that substantial coding gains are possible, which can be used to increase the data rate or the distance span of the link. The proposed designs can be used in short-distance optical transceivers for 10-Gb ethernet, fiberchannel, and very short reach optical datalinks, and are scalable to future two-dimensional optical datalinks with Terabits of capacity. [ABSTRACT FROM PUBLISHER]

In the military surveillance and security information systems, correct blind reconstruction of signal parameters from unknown signals is very important. Especially, many blind reconstruction methods of error-correcting codes have been proposed, and their theoretical performance analysis is essential for both the defender who wants to prevent information leakage and the challenger who wants to extract information from the intercepted signals. However, a proper performance analysis of most blind reconstruction methods has not been performed yet. Among many blind reconstruction methods of BCH codes proposed so far, the blind reconstruction method based on consecutive roots of generator polynomials proposed by Jo, Kwon, and Shin, called the JKS method, shows the best performance under the unknown channel information. However, the performance of the JKS method is only evaluated through simulation without performing theoretical analysis. In this paper, the JKS method is asymptotically analyzed under the binary symmetric channel with the cross-over probability $p$ . Since the blind reconstruction performance heavily depends on how many and which received codewords are used even for the same channel environment, sufficiently many codewords are assumed to perform asymptotic analysis. More specifically, an asymptotic threshold on $p$ , up to which blind reconstruction is successful, is derived when the number of received codewords is sufficiently large, which can be used as a new performance metric for blind reconstruction methods. Finally, the validity of the asymptotic analysis is confirmed through simulation.

In this work, cyclic-skew-cyclic codes and sum-rank BCH codes are introduced. Cyclic-skew-cyclic codes are characterized as left ideals of a suitable non-commutative finite ring, constructed using skew polynomials on top of polynomials (or vice versa). Single generators of such left ideals are found, and they are used to construct generator matrices of the corresponding codes. The notion of defining set is introduced, using pairs of roots of skew polynomials on top of poynomials. A lower bound (called sum-rank BCH bound) on the minimum sum-rank distance is given for cyclic-skew-cyclic codes whose defining set contains certain consecutive pairs. Sum-rank BCH codes, with prescribed minimum sum-rank distance, are then defined as the largest cyclic-skew-cyclic codes whose defining set contains such consecutive pairs. The defining set of a sum-rank BCH code is described, and a lower bound on its dimension is obtained. Thanks to it, tables are provided showing that sum-rank BCH codes beat previously known codes for the sum-rank metric for binary $2 \times 2 $ matrices (i.e., codes whose codewords are lists of $2 \times 2 $ binary matrices, for a wide range of list lengths that correspond to the code length). Finally, a decoder for sum-rank BCH codes up to half their prescribed distance is obtained. [ABSTRACT FROM AUTHOR]

The generalized integrated interleaved (GII) codes nest BCH sub-codewords to form codewords of more powerful BCH codes. They can achieve hyper-throughput decoding with excellent error-correcting performance and are among the most suitable codes for next-generation memories. However, the new storage class memories require high code rate and short codeword length. In this case, the sub-codewords have small correction capability. The miscorrections of the sub-codewords lead to much more severe degradation on the GII error-correcting performance compared to the miscorrections of classic BCH codes. This letter investigates the miscorrections in GII decoding. Three low-complexity methods are developed to identify and mitigate the miscorrections by utilizing the nested syndromes, adding one single parity to each sub-codeword, and keeping track of the error locator polynomial degree. Besides, formulas for estimating the miscorrection rates are given. Using the proposed mitigation methods, the actual GII decoding performance becomes very close to that of the case without any miscorrections. [ABSTRACT FROM AUTHOR]

The video performance of a 155-Mbps wireless asynchronous transfer mode (WATM) proposal and that of a 2-Mbps Universal Mobile Telecommunications System (UMTS) concept is evaluated for a range of low- to high-quality video application scenarios, various propagation conditions, and video bit rates using the H.263 video codec, assisted by a novel packetization and packet acknowledgment scheme. Orthogonal frequency-division multiplexing is invoked over the highly dispersive channels for conveying high-rate video signals. Various binary Bose-Chaudhuri-Hochquenghem and turbo codes are investigated comparatively, with the conclusion that due to the high error resilience of the video packetization and acknowledgment scheme, the increased power of the higher complexity turbo codec does not translate to substantially improved overall system robustness, although the bit error rate and acknowledgment flag error rate are significantly reduced. The whole range of video resolutions and system parameters is summarized in a number of tables. The required channel signal-to-noise ratio for near-unimpaired video quality is about 16 dB for the inherently lower quality, lower resolution video frame formats, but slightly higher, about 18 dB, for the high-definition formats, where the error-induced subjective video degradations become more objectional over the highly dispersive worst case channels used [ABSTRACT FROM PUBLISHER]

Polar codes have drawn much research attention in the last ten years for their capacity-achieving property. However, their conventional successive cancellation decoding method performs not well at a short or moderate length. In order to improve the performance, concatenation with other error-correction codes has been proved an effective approach, whereas current concatenation schemes using rate-optimized method are too complex to implement with long decoding latency. In this paper, we propose a critical set protected BCH-Polar code with its corresponding decoding architecture. In the proposed concatenation scheme, we only provide extra protection to partial information bits in the critical set, which is constructed based on the channel reliability. For its corresponding decoding architecture, we redesign some components and adopt the Look-up table decoding method for BCH codes, resulting in much degradation of decoding latency. Compared with existing decoders, the hardware implementation shows low decoding latency and high throughput-area efficiency.

An explicit construction of an infinite family of cyclic codes is presented which, over GF(4) (resp., GF(8)), have approximately 8/9 (resp., 48/49) the redundancy of BCH codes of the same minimum distance and length. As such, the new codes are the best codes currently known in a regime where the minimum distance is fixed and the code length goes to infinity. [ABSTRACT FROM PUBLISHER]