Search

Light nodes in blockchains improve the scalability of the system by storing a small portion of the blockchain ledger. In certain blockchains, light nodes are vulnerable to a data availability (DA) attack where a malicious node makes the light nodes accept an invalid block by hiding the invalid portion of the block from the nodes in the system. Recently, a technique based on LDPC codes called Coded Merkle Tree (CMT) was proposed by Yu et al. that enables light nodes to detect a DA attack by randomly requesting/sampling portions of the block from the malicious node. However, light nodes fail to detect a DA attack with high probability if a malicious node hides a small stopping set of the LDPC code. To mitigate this problem, Yu et al. used random LDPC codes that achieve large minimum stopping set size with high probability. Although effective, these codes are not necessarily optimal for this application, especially at short code lengths, which are relevant for low latency systems, IoT blockchains, etc.. In this paper, we focus on short code lengths and demonstrate that a suitable co-design of specialized LDPC codes and the light node sampling strategy can improve the probability of detection of DA attacks. We consider different adversary models based on their computational capabilities of finding stopping sets in LDPC codes. For a weak adversary model, we devise a new LDPC code construction termed as the entropy-constrained PEG (EC-PEG) algorithm which concentrates stopping sets to a small group of variable nodes. We demonstrate that the EC-PEG algorithm coupled with a greedy sampling strategy improves the probability of detection of DA attacks. For stronger adversary models, we provide a co-design of a sampling strategy called linear-programming-sampling (LP-sampling) and an LDPC code construction called linear-programming-constrained PEG (LC-PEG) algorithm. The new co-design demonstrates a higher probability of detection of DA attacks compared to approaches in earlier literature. [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]

Random interleavers are widely employed in digital communication systems to combat channel fading and burst errors. In applications such as grant-free access by Internet of Things (IoT) devices, accurately identifying a specific irregular interleaving pattern within an interleaver period is vital to both terminal recognition and data recovery. In this work, we investigate effective approaches for random interleaving pattern identification in Reed-Solomon (RS) coded data streams. We first propose an algorithm of low computational complexity to detect positions of code symbols belonging to the same RS codeword group (RSCG) under modest bit error rate. We further develop another low-complexity algorithm to successfully identify random interleaving patterns for RS code symbols within each RS codeword under moderate to high error rate applications. Our theoretical analysis and simulation results corroborate to demonstrate the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

Consider the identification (ID) via channels problem, where a receiver decides whether the transmitted identifier is its identifier, rather than decoding it. This model allows to transmit identifiers whose size scales doubly-exponentially in the blocklength, unlike common transmission codes with exponential scaling. Binary constant-weight codes (CWCs) suffice to achieve the ID capacity. Relating parameters of a binary CWC to the minimum distance of a code and using higher-order correlation moments, two upper bounds on binary CWC sizes are proposed. These bounds are also upper bounds on identifier sizes for ID codes constructed by using binary CWCs. We propose two constructions based on optical orthogonal codes (OOCs), which are used in optical multiple access schemes, have constant-weight codewords, and satisfy cyclic cross-correlation and auto-correlation constraints. These constructions are modified and concatenated with outer Reed-Solomon codes to propose new binary CWCs being optimal for ID. Improvements to the finite-parameter performance are shown by using outer codes with larger minimum distance vs. blocklength ratios. We illustrate ID regimes for which our ID code constructions perform significantly better than existing constructions. [ABSTRACT FROM AUTHOR]

In his pioneering work on LDPC codes, Gallager dismissed codes with parity-check matrices of weight two after proving that their minimum Hamming distances grow at most logarithmically with their code lengths. In spite of their poor minimum Hamming distances, it is shown that quasi-cyclic LDPC codes with parity-check matrices of column weight two have good capability to correct phased bursts of erasures which may not be surpassed by using quasi-cyclic LDPC codes with parity-check matrices of column weight three or more. By modifying the parity-check matrices of column weight two and globally coupling them, the erasure correcting capability can be further enhanced. Quasi-cyclic LDPC codes with parity-check matrices of column weight three or more that can correct phased bursts of erasures and perform well over the AWGN channel are also considered. Examples of such codes based on Reed-Solomon and Gabidulin codes are presented. [ABSTRACT FROM AUTHOR]

A Bose-Chaudhuri-Hocquenghem (BCH) is called quasi-reversible if there are consecutive elements a1, . . . , a2 in the defining set, where a1 is a negative integer and a2 is a positive integer. A matrix in band form presented in this article involves the use of the Newton identities and symmetric polynomial identities. This matrix is the coefficient matrix of a linear system. The solution to such a linear system is the coefficients of an error-locator polynomial for quasi-reversible BCH codes. Its computational complexity is significantly lower than BCH decoding using the linear system with coefficient matrix in column echelon form. This article also proposes a new partial syndrome matrix with radical locators and a lot of zeros. Such a matrix is still in band form. The expansion of its matrix determinant is exactly a radical-locator polynomial. Compared to the former radical-locator polynomials in the literature, the newly discovered radical-locator polynomial not only requires less storage memory but also results in computational benefits. Surprisingly, the resulting polynomials are much sparser than those for the narrow-sense BCH codes. Finally, a complete algebraic decoding algorithm for quasi-reversible BCH codes is provided. The error-locator and radical-locator polynomials of degree less than or equal to 5 are listed. [ABSTRACT FROM AUTHOR]

The interpolation based algebraic soft decoding yields a high decoding performance for Reed-Solomon (RS) codes with a polynomial-time complexity. Its computationally expensive interpolation can be facilitated using the module structure. The desired Gröbner basis can be achieved by reducing the basis of a module. This paper proposes the low-complexity Chase (LCC) decoding algorithm using this module basis reduction (BR) interpolation technique, namely the LCC-BR algorithm. By identifying $\eta $ unreliable symbols, $2^\eta $ decoding test-vectors will be formulated. The LCC-BR algorithm first constructs a common basis which will be shared by the decoding of all test-vectors. This eliminates the redundant computation in decoding each test-vector, resulting in a lower decoding complexity and latency. This paper further proposes the progressive LCC-BR algorithm that decodes the test-vectors sequentially and terminates once the maximum-likelihood decision decoding outcome is reached. Exploiting the difference between the adjacent test-vectors, this progressive decoding is realized without any additional memory cost. Complexity analysis shows that the LCC-BR algorithm yields a lower complexity and latency, especially for high rate codes, which will be validated by the numerical results. [ABSTRACT FROM AUTHOR]

Multipartite secret sharing is an important research object in the area of secret sharing schemes. Compartmented access structures are an interesting class of multipartite access structures. The constructions of ideal linear schemes realizing compartmented access structures are studied by codes in this paper. We find that compartmented secret sharing is related to a class of codes called locally repairable codes which are being used widely in distributed and cloud storage systems. We study secret sharing schemes for compartmented access structures with upper bounds, compartmented access structures with lowers bounds and compartmented access structures with upper and lower bounds. We establish the relationships between secret sharing schemes for these compartmented access structures and locally repairable codes. Based on the relationships and some locally repairable codes, we obtain ideal linear schemes realizing these compartmented access structures by efficient methods. [ABSTRACT FROM AUTHOR]

By introducing several levels of recoverability for locally recoverable codes (LRCs), LRCs with hierarchical locality (H-LRCs) are defined for correcting different numbers of erasures. There are two major ingredients in this paper. The first is to investigate some properties and existence conditions of optimal H-LRCs with respect to a generalized Singleton-like bound for H-LRCs. The second ingredient is to propose several constructions of optimal H-LRCs by employing cyclic codes. Notably, the parameters of these optimal H-LRCs are flexible. [ABSTRACT FROM AUTHOR]

The algebraic soft-decision decoding (ASD) of Reed–Solomon (RS) codes yields a competent decoding performance with a polynomial-time complexity. But its complexity remains high due to the interpolation that generates the interpolation polynomial $Q(x,y)$. The progressive ASD (PASD) algorithm has been introduced to construct $Q(x,y)$ with a progressively enlarged $y$ -degree, adjusting its error-correction capability and computation to the received information. However, this progressive decoding is realized at the cost of memorizing the intermediate decoding information. To overcome this challenge, this paper proposes a new PASD algorithm which is evolved from the ASD using module minimization (MM) interpolation. Polynomial $Q(x,y)$ can be constructed through the image of the progressively enlarged submodule basis without the need of memorizing the intermediate decoding information, eliminating the memory cost of progressive decoding. The MM interpolation also attributes to a remarkably lower complexity than the original PASD algorithm. Furthermore, a complexity reducing variant is proposed based on assessing the degree of Lagrange interpolation polynomials. We also analyze the complexity of the proposed decoding methods and reveal their channel dependent feature. Our simulation results show their low-complexity and advanced decoding performances. [ABSTRACT FROM AUTHOR]

Motivated by applications of distributed storage systems to key-value stores, the multi-version coding problem has been formulated to efficiently store frequently updated data in asynchronous decentralized storage systems. Inspired by consistency requirements in distributed systems, the main goal in the multi-version coding problem is to ensure that the latest possible version of the data is decodable even if the data updates have not reached all the servers in the system. In this paper, we study the storage cost of ensuring consistency for the case where the data versions are correlated, in contrast to previous work where the data versions were treated as being independent. We provide multi-version code constructions that show that the storage cost can be significantly smaller than the previous constructions depending on the degree of correlation, despite the asynchrony and the decentralized nature. Our achievability results are based on Reed–Solomon codes and random binning. Through an information-theoretic converse, we show that our multi-version codes are asymptotically nearly optimal, within a factor of 2, in certain interesting regimes. [ABSTRACT FROM AUTHOR]

Designs and constructions of quasi-cyclic (QC) LDPC codes for the AWGN channel are presented. The codes are constructed based on the conventional parity-check matrices of Reed–Solomon (RS) codes and are referred to as RS-QC-LDPC codes. Several classes of RS-QC-LDPC codes are given. Cycle structural properties of the Tanner graphs of codes in these classes are analyzed and specific methods for constructing codes with girth at least eight and reducing their short cycles are presented. The designed codes perform well in both waterfall and low error-rate regions. [ABSTRACT FROM AUTHOR]

This paper proposes the symbol-level-stochastic Chase decoding algorithm (S-SCA) for the Reed–Solomon (RS) and Bose–Chaudhuri–Hocquenghem (BCH) codes, which is a soft-input soft-output (SISO) decoder. By the efficient usage of void space between constellation points for $q$ -ary modulations and using soft information at the input of the decoder, the S-SCA is capable of outperforming conventional symbol-level-Chase algorithm (S-CA) with a less computational cost. Since the S-SCA starts with the randomized generation of likely test-vectors, it reduces the complexity to polynomial order and also it does not need to find the least reliable symbols to generate test-vectors. The symbol-level-search bitwise-transmission stochastic Chase algorithm (SSBT-SCA) is also introduced for RS codes over binary phase shift keying (BPSK) transmission that is capable of generating symbol-level test-vectors with reduced complexity and to better mitigate burst errors. Simulation results show that by increasing the number of test-vectors, the performance of the algorithm can asymptotically approach the maximum-likelihood (ML) bound. The S-SCA provides near 2 dB decoding gain in comparison with S-CA for a (31, 25) RS code using 32-QAM, when 1024 test-vectors are used. Furthermore, the algorithm provides near 3 dB additional gain with 1024 test-vectors compared with S-CA that uses 65536 iterations when a (255, 239) RS code is used in an additive white Gaussian noise (AWGN) channel. For the Rayleigh fading channel and the same code, the algorithm provides more than 5 dB gain. Furthermore, for (63, 57) BCH codes and 8-PSK modulation, the proposed algorithm provides 3 dB gain with less complexity. [ABSTRACT FROM AUTHOR]

We consider the problem of downloading content from a cellular network that is cached at the wireless edge while achieving privacy. In particular, we consider private information retrieval (PIR) of content from a library of files, i.e., the user wishes to download a file and does not want the network to learn any information about which file she is interested in. To reduce the backhaul usage, content is cached at the wireless edge in a number of small-cell base stations (SBSs) using maximum distance separable codes. We propose a PIR scheme based on generalized Reed–Solomon codes for this scenario that achieves privacy against a number of spy SBSs that collaborate. The proposed PIR scheme is an extension of a scheme by Kumar et al. to the case of multiple code rates, suitable for the scenario where files have different popularities. We derive the backhaul rate and optimize the content placement to minimize it. We prove that uniform content placement is optimal, i.e., all files that are cached should be stored using the same code rate. This is in contrast to the case where no PIR is required. Furthermore, we show numerically that popular content placement is optimal for some scenarios. [ABSTRACT FROM AUTHOR]

This paper proposes multilevel Reed–Solomon (MRS) codes and their iterative multistage soft decoding (IMSD) for visible light communication (VLC), realizing both high decoding performance and transmission spectrum efficiency. The proposed IMSD algorithm decodes the MRS codes level-by-level through iterating either hard decisions or extrinsic information of RS coded bits. Each level RS decoding is realized by cascading the adaptive belief propagation (ABP) algorithm that produces the extrinsic information and the Berlekamp–Massey (BM) algorithm that estimates the codeword. The earlier level decoding provides better a priori information for the later ones. A complexity reducing IMSD (CR-IMSD) algorithm is also proposed to facilitate the decoding. This paper further investigates a joint design of color-shift keying (CSK) constellation and the MRS code, optimizing the decoding performance. The CSK constellation is designed by considering both the set partitioning (SP) criterion and the harmonic mean of constellation’s minimum squared Euclidean distance (MSED). The MRS codes are further designed using the capacity and the equal error probability rules. Our simulation results show that the IMSD algorithm achieves significant iterative decoding gains. The performance of the designed MRS code is 0.3 dB away from the capacity limit at the bit error rate (BER) of 10−9. [ABSTRACT FROM AUTHOR]

Locally decodable codes and locally correctable codes (LCCs) have several important applications, such as private information retrieval, secure multiparty computation, and circuit lower bounds. Three major parameters are considered in LCCs: query complexity, message length, and codeword length. The most familiar LCCs in the regime of low query complexity are the generalized Reed–Muller (GRM) codes. However, it has not previously been determined whether there exist codes that have shorter codeword lengths than GRM codes with the same query complexity and message length. In this paper, we show that the projective Reed–Muller (PRM) codes are such LCCs for some parameters. The GRM code is specified by the alphabet size $q$ , the number of variables $m$ , and the degree $d$ , where $d\le q-2$. When $d= q-2$ and $q-1$ is a power of a prime, we prove that there exists a PRM code with shorter codeword length than the GRM code with the same query complexity and message length. We also present for these PRM codes a perfectly smooth local decoder to recover a symbol in a codeword by accessing not more than $q$ symbols at the coordinates of the codeword. [ABSTRACT FROM AUTHOR]

In this paper, two new decoding algorithms to decode Reed–Solomon codes during transmission over burst Rayleigh fading channels with additive white Gaussian noise (AWGN) are proposed. They only conduct error correction for coded symbols located in the pure AWGN region and conduct error and erasure correction for those symbols located in the burst fading region by treating those coded symbols that are very likely erroneous as erasures. The first algorithm does not need to know the fading locations in advance, while the second algorithm assumes that the fading locations are known. In addition, the performance of such two algorithms is studied when a pre-computed threshold is used to determine the erasures of the code. Simulation results show that our proposed algorithms not only significantly perform better than the classic Berlekamp–Messay algorithm with a comparable computational complexity but also achieve a better tradeoff between the performance and the computational complexity when compared with other existing algorithms. In particular, our algorithms exhibit excellent robustness for tested various code parameters and fading configurations. Furthermore, a more detailed mathematical analysis is also developed in this paper in order to estimate the performance of the new algorithms in the burst Rayleigh fading channels. We observe that the performance of the first algorithm can only be estimated relatively accurately when encountering burst deep-fading, whereas the performance prediction for the second algorithm is always in agreement with the simulation results for various fading cases. [ABSTRACT FROM AUTHOR]

In this paper, we devise a fast encoding algorithm for triply extended Reed–Solomon codes. The proposed approach requires approximately two XORs per bit, which improves the prior result of three XORs per bit established by certain maximum distance separable (MDS) array codes. We also prove that, for MDS codes with two and three parities, the scheduling algorithms require at least two XORs per bit. To the best of our knowledge, this is the first provable scheduling algorithm for the triple-parity MDS codes to approach the theoretical lower bounds. The implementation with SIMD instructions is provided. The simulations show that the proposed approach is competitive, as compared with other cutting edge implementations. [ABSTRACT FROM AUTHOR]

Distributed storage systems suffer from significant repair traffic generated due to the frequent storage node failures. This paper shows that properly designed low-density parity-check (LDPC) codes can substantially reduce the amount of required block downloads for repair thanks to the sparse nature of their factor graph representation. In particular, with a careful construction of the factor graph, both low repair-bandwidth and high reliability can be achieved for a given code rate. First, a formula for the average repair bandwidth of LDPC codes is developed. This formula is then used to establish that the minimum repair bandwidth can be achieved by forcing a regular check node degree in the factor graph. Moreover, it is shown that given a fixed code rate, the variable node degree should also be regular to yield minimum repair bandwidth, under some reasonable minimum variable node degree constraint. It is also shown that for a given repair-bandwidth requirement, LDPC codes can yield substantially higher reliability than the currently utilized Reed–Solomon codes. Our reliability analysis is based on a formulation of the general equation for the mean-time-to-data-loss (MTTDL) associated with LDPC codes. The formulation reveals that the stopping number is closely related to the MTTDL. It is further shown that LDPC codes can be designed such that a small loss of repair-bandwidth optimality may be traded for a large improvement in erasure-correction capability and thus the MTTDL. [ABSTRACT FROM PUBLISHER]

Array codes have been widely used in communication and storage systems. To reduce computational complexity, one important property of the array codes is that only exclusive OR operations are used in the encoding and decoding processes. Cauchy Reed–Solomon codes, Rabin-like codes, and circulant Cauchy codes are existing Cauchy maximum-distance separable (MDS) array codes that employ Cauchy matrices over finite fields, circular permutation matrices, and circulant Cauchy matrices, respectively. All these codes can correct any number of failures; however, a critical drawback of existing codes is the high decoding complexity. In this paper, we propose a new construction of Rabin-like codes based on a quotient ring with a cyclic structure. The newly constructed Rabin-like codes have more supported parameters (prime $p$ is extended to an odd number), such that the world sizes of them are more flexible than the existing Cauchy MDS array codes. An efficient decoding method using LU factorization of the Cauchy matrix can be applied to the newly constructed Rabin-like codes. It is shown that the decoding complexity of the proposed approach is less than that of existing Cauchy MDS array codes. Hence, the Rabin-like codes based on the new construction are attractive to distributed storage systems. [ABSTRACT FROM PUBLISHER]

Motivated by applications involving hot data, the notion of (r, t) -availability was introduced, where a symbol is said to have (r, t) -availability if it can be reconstructed, respectively, from t disjoint repair alternatives of other symbols, each of size at most r . The key to constructing a family of locally repairable codes with (r, t) -availability is the design of a membership matrix for dividing global parities into local ones such that each repair group contains only one parity symbol. Although explicit designs of membership matrices are available, it remains unclear whether membership matrices with significantly better parameters can be constructed, which was a question left open. To tackle the open problem, this paper first provides a connection between the design of membership matrices and the design of a combinatorial object in the well-known combinatorial design theory, called resolvable configurations. This paper then proposes several direct designs of membership matrices based on Euclidean geometry, finite fields, circulant permutation matrices, affine permutation matrices, and Reed–Solomon codes. By leveraging the notion of resolvable configurations and the Kronecker product, this paper further proposes a two-step design of membership matrices. The proposed direct and two-step designs of membership matrices are shown to have significantly better parameters than those recently available. [ABSTRACT FROM AUTHOR]

A low-complexity systematic encoding algorithm for polar codes with Reed–Solomon (RS) kernel is presented. The proposed method relies on fast Fourier transform-based RS encoding techniques. An application of polar codes in storage systems is considered. [ABSTRACT FROM AUTHOR]

Erasure codes, such as LT and Raptor codes, are designed for the purpose of erasure-resilient distribution of data over computer networks. To achieve a small reception overhead, however, LT and Raptor codes must be used with a large design length $k$, making these codes unsuitable for real-time applications. In this paper, we propose a new class of erasure codes based on Reed–Solomon codes that unlike other Reed–Solomon-based erasure codes are rateless and also, unlike other rateless codes, guarantee zero overhead even for small $k$. Moreover, they have a reasonable computational complexity of coding when $k$ is not too large. In fact, a practical implementation of subfield subcodes of Reed-Solomon codes with arbitrarily large block lengths is presented. [ABSTRACT FROM AUTHOR]

In this paper, we devise new scalable decoder architectures for Reed–Solomon (RS) codes, comprising three parts: error-only decoding, error-erasure decoding, and their decoding for singly extended RS codes. New error-only decoders are devised through algorithmic transformations of the inversionless Berlekamp–Massey algorithm (IBMA). We first generalize the Horiguchi–Koetter formula to evaluate error magnitudes using the error locator polynomial $\Lambda(x)$ and the auxiliary polynomial $B(x) $ produced by IBMA, which effectively eliminates the computation of error evaluator polynomial. We next devise an enhanced parallel inversionless Berlekamp–Massey algorithm (ePIBMA) that effectively takes advantage of the generalized Horiguchi–Koetter formula. The derivative ePIBMA architecture requires only $2t+1$ ( $t$ denotes the error correction capability) systolic cells, in contrast with $3t$ or more cells of the existing regular architectures based on IBMA or the Euclidean algorithm. Moreover, it may literally function as a linear-feedback-shift-register encoder. New error-erasure decoders are devised through algorithmic transformations of the inversionless Blahut algorithm (IBA) . The proposed split parallel inversionless Blahut algorithm (SPIBA) yields merely $2t+1$ systolic cells, which is the same number as the error-only decoder ePIBMA. The task is partitioned into two separate steps, computing the complementary error erasure evaluator polynomial followed by computing error-erasure locator polynomial, both utilizing SPIBA. Surprisingly, it has exactly the same number of cells and literally the same complexity and throughput as the proposed error-only decoder architecture ePIBMA; it employs 33% less hardware and at the same time achieves more than twice faster throughput, than the serial architecture IBA. we further propose a unified parallel inversionless Blahut algorithm (UPIBA) by incorporating the key virtues of the error-only decoder ePIBMA into SPIBA. The complexity and throughput of the rderivative UPIBA architecture are literally the same as ePIBMA and SPIBA, while performing almost equally efficiently as ePIBMA on error-only decoding and as SPIBA on error-erasure decoding. UPIBA also inherits the dynamic power saving feature of ePIBMA and SPIBA. Indeed, UPIBA renders highly attractive for on-the-fly implementation of error-erasure decoding. We finally demonstrate that the proposed decoders, i.e., ePIBMA, SPIBA, and UPIBA, can be magically migrated to decode singly extended RS codes, with negligible add-ons, except that an extra multiplexer is added to their critical paths. To the author's best knowledge, this is the first time that a high-throughput decoder for singly extended RS codes is explored. [ABSTRACT FROM PUBLISHER]

Regenerating codes provide an efficient way to recover data at failed nodes in distributed storage systems. It has been shown that regenerating codes can be designed to minimize the per-node storage (called MSR) or minimize the communication overhead for regeneration (called MBR). In this work, we propose new encoding schemes for error-correcting MSR and MBR codes that generalize our earlier results on error-correcting regenerating codes. General encoding schemes for product-matrix MSR and MBR codes are derived such that the encoder based on Reed-Solomon (RS) codes is no longer limited to the Vandermonde matrix proposed earlier. Furthermore, MSR codes and MBR codes with the least update complexity can be found. A decoding scheme is proposed that utilizes RS codes to perform data reconstruction for MSR codes. The proposed decoding scheme has better error correction capability and incurs least number of node accesses when errors are present. A new decoding scheme is also proposed for MBR codes that is more capable and can correct more error-patterns. Simulation results are presented that exhibit the superior performance of the proposed schemes. [ABSTRACT FROM PUBLISHER]

Non-Gaussian noise/interference severely limits communication performance of narrowband powerline communication (PLC) systems. Such noise/interference is dominated by periodic impulsive noise whose statistics varies with the AC cycle. The periodic impulsive noise statistics deviates significantly from that of additive white Gaussian noise, thereby causing dramatic performance degradation in conventional narrowband PLC systems. In this paper, we propose a robust transmission scheme and corresponding receiver methods to combat periodic impulsive noise in OFDM-based narrowband PLC. Towards that end, we propose (1) a time-frequency modulation diversity scheme at the transmitter and a diversity demodulator at the receiver to improve communication reliability without decreasing data rates; and (2) a semi-online algorithm that exploits the sparsity of the noise in the frequency domain to estimate the noise power spectrum for reliable decoding at the diversity demodulator. In the simulations, compared with a narrowband PLC system using Reed-Solomon and convolutional coding, whole-packet interleaving and DBPSK/BPSK modulation, our proposed transceiver methods achieve up to 8 dB gains in Eb/N0 with convolutional coding and a smaller-sized interleaver/deinterleaver. [ABSTRACT FROM PUBLISHER]

RS-LDPC codes, constructed based on the codewords of Reed-Solomon (RS) codes with two information symbols, are an important class of LDPC codes. In this paper, we present two representations, namely, quasi-cyclic (QC) representation and vector representation, for RS-LDPC codes. Under the first representation, most part of the parity-check matrix of a full-length RS-LDPC code consists of circulant permutation matrices and zero matrices. As a result, the class of codes can enjoy the advantages in hardware implementation as QC-LDPC codes. In addition, the base matrix under the QC representation of an RS-LDPC code can be explicitly given such that the rank of its parity-check matrix can be analyzed combinatorially. Under the second representation, each permutation matrix in the parity-check matrix of an RS-LDPC code is defined by a nonbinary vector, whose entries are a permutation of entries in the field from which the RS code is constructed. Then, the “affine invariance” property is proved for full-length RS-LDPC codes, which can facilitate the structural analysis of the codes. [ABSTRACT FROM PUBLISHER]

Traditionally, Reed-Solomon (RS) codes have been employed in magnetic data storage devices due to their effectiveness in correcting random errors and burst errors caused by thermal asperities and inter-symbol interference (ISI). However, as storage densities increase the effect of ISI becomes more severe and much longer RS codes are needed, but this requires significantly increasing the size of the finite field. A possible replacement for RS codes are the one-point Hermitian codes, which are a class of algebraic-geometric (AG) code that have larger block sizes and minimum Hamming distances over the same finite field. In this paper, we present a novel iterative soft detection-decoding algorithm for interleaved Hermitian codes. The soft decoding employs a joint adaptive belief propagation (ABP) algorithm and Koetter-Vardy (KV) list decoding algorithm. It is combined with a maximum a posteriori (MAP) partial response (PR) equalizer and likelihoods from the output of the KV or the ABP algorithm are fed back to the equalizer. The proposed scheme's iterative detection-decoding behavior will be analyzed by utilizing the Extrinsic Information Transfer (ExIT) chart. Our simulation results demonstrate the performance gains achieved by iterations and Hermitian codes' performance advantage over RS codes. [ABSTRACT FROM AUTHOR]

A scheme for concatenating the recently invented polar codes with non-binary MDS codes, as Reed-Solomon codes, is considered. By concatenating binary polar codes with interleaved Reed-Solomon codes, we prove that the proposed concatenation scheme captures the capacity-achieving property of polar codes, while having a significantly better error-decay rate. We show that for any ε > 0, and total frame length N, the parameters of the scheme can be set such that the frame error probability is less than 2^-N^1-ε, while the scheme is still capacity achieving. This improves upon 2^-N^0.5-ε, the frame error probability of Arikan's polar codes. The proposed concatenated polar codes and Arikan's polar codes are also compared for transmission over channels with erasure bursts. We provide a sufficient condition on the length of erasure burst which guarantees failure of the polar decoder. On the other hand, it is shown that the parameters of the concatenated polar code can be set in such a way that the capacity-achieving properties of polar codes are preserved. We also propose decoding algorithms for concatenated polar codes, which significantly improve the error-rate performance at finite block lengths while preserving the low decoding complexity. [ABSTRACT FROM AUTHOR]

This work compares theoretically the performance of several representative practical multiple description (MD) frameworks with L≥ 3 symmetric descriptions. The first scenario is the classic unequal erasure protection (UEP) scheme using a successively refinable code (SRC) and Reed-Solomon codes. The second scenario is an improvement upon UEP by applying domain partitioning and permuted Reed-Solomon codes. The third scenario uses a finer partitioning and erasure correction via repetition codes. Additionally, the MD lattice vector quantizer and another recent MD scheme are considered in the comparison. The aforementioned MD schemes are compared in terms of the expected squared error asymptotically achievable as the rate R of a description approaches ∞, assuming independent description losses. Our analysis reveals that the improvement of the second scenario upon the first one when R→ ∞ can reach up to 1.68 dB, but it approaches 0 as the description loss rate p goes to 0 and L approaches ∞. Additionally, we find that the first two schemes outperform the third one with an unbounded gain when R→ ∞, as p→ 0 or L→ ∞. Further, we show that the first three scenarios achieve unbounded improvements over the other two as R→ ∞ and p→ 0. On the other hand, we point out that some of the results of our asymptotic analysis rely on strong assumptions and therefore an experimental validation is needed before applying them to practical situations. [ABSTRACT FROM PUBLISHER]

Reed-Solomon convolutional concatenated (RSCC) code is a popular coding scheme whose application can be found in wireless and space communications. However, iterative soft decoding of the concatenated code is yet to be developed. This paper proposes a novel iterative soft decoding algorithm for the concatenated code, aiming to better exploit its error-correction potential. The maximum a posteriori (MAP) algorithm is used to decode the inner convolutional code. Its soft output will be deinterleaved and then given to the soft-in-soft-out (SISO) decoder of the outer Reed-Solomon (RS) code. The RS SISO decoder integrates the adaptive belief propagation (ABP) algorithm and the Koetter-Vardy (KV) list decoding algorithm, attempting to find out the transmitted message. It feeds back both the deterministic and the extrinsic probabilities of RS coded bits, enabling the soft information to be exchanged between the inner and outer decoders. An extrinsic information transfer (EXIT) analysis of the proposed algorithm is presented, analyzing its iterative decoding behavior for RSCC codes. The EXIT analysis also leads to the design insight of inner code in the concatenation. Computational complexity of the proposed algorithm is also analyzed. Finally, the iterative decoding performance is shown and its advantage over the existing decoding algorithms is demonstrated. [ABSTRACT FROM AUTHOR]

In this paper, the extended Reed-Solomon codes are modified to construct a new family of 2-D codes for asynchronous optical code-division multiple access (O-CDMA). In addition of having expanded and asymptotically optimal cardinality, these 2-D asynchronous optical codes can be partitioned into multiple tree structures of code subsets, in which code cardinality is a function of the (periodic) cross-correlation value assigned to the subset. The performance of these 2-D optical codes is analyzed and compared with that of the multilevel prime codes. Our results show that the unique partition property of the new optical codes supports a trade-off between code cardinality and performance for meeting different system requirements, such as user capacity and throughput. In addition, the multiple tree structures of the new codes potentially support applications that require rapid switching of many codewords, such as in O-CDMA-network gateway or in strategic environments where code obscurity is essential. [ABSTRACT FROM PUBLISHER]

Multilevel flash memories store more than one bit per storage cell and are further characterized by large word (page) sizes and very low target error rates. In this paper, a high-rate error control scheme is presented that uses inner trellis-coded modulation (TCM) for storing two bits per cell with five possible charge levels. The coded subset-label bits and the uncoded signal-label bits of TCM are independently protected by separate outer Reed-Solomon (RS) codes. The resulting scheme permits multistage decoding. Errors made by the TCM decoder in the subset-label bits occur in bursts and are corrected by the associated first RS decoder prior to determining signal-label bits and correcting errors in those bits by the associated second RS decoder. The multi-stage decoding avoids the significant spread of errors from subset-label bits into the generally larger number of signal-label bits which is typical for conventional serial RS-TCM concatenation when the inner TCM system operates at relatively low SNR. The error performance of the proposed scheme is evaluated at low error rates by a mixed simulation-analytic method. It is shown that the proposed scheme exhibits highly favorable performance vs. complexity tradeoffs compared to the other schemes. [ABSTRACT FROM AUTHOR]

The algebraic soft-decision decoding (ASD) algorithm is a polynomial-time soft decoding algorithm for Reed-Solomon (RS) codes. It outperforms both the algebraic hard-decision decoding (AHD) and the conventional unique decoding algorithms, but with a high computational cost. This paper proposes a progressive ASD (PASD) algorithm that enables the conventional ASD algorithm to perform decoding with an adjustable designed factorization output list size (OLS). The OLS is enlarged progressively leading to an incremental computation for the interpolation and an enhanced error-correction capability. Multiple factorizations are performed in order to find out the intended message polynomial which will be validated by a cyclic redundant check (CRC) code. The incremental interpolation constraints are introduced to characterize the progressive decoding. The validity analysis of the algorithm shows the PASD algorithm is a natural and computationally saving generalization of the ASD algorithm, delivering the same interpolation solution. The average decoding complexity of the algorithm is further theoretically characterized, revealing its dependence on the channel condition. The simulation results further validate the analysis by showing that the average decoding complexity can be converged to the minimal level in a good channel condition. Finally, performance evaluation shows the PASD algorithm preserves the error-correction capability of the ASD algorithm. [ABSTRACT FROM PUBLISHER]

Algebraic soft-decision (ASD) decoding algorithm of Reed-Solomon (RS) codes can achieve better performance-complexity tradeoff than other soft-decision decoding algorithms. The interpolation is a major step of ASD algorithms. In the case that multiple test vectors are involved, the interpolation needs to be carried out for each vector and leads to very high hardware complexity. To enable the sharing of computation results in the interpolation for different vectors, a backward interpolation scheme was developed previously to eliminate points from a given interpolation result, which is a Grobner basis. However, this scheme can only eliminate all points in the same code position when their multiplicities are all one and the number of points is one less than the number of polynomials in the Grobner basis. Larger multiplicities are required to achieve better error-correcting performance. Moreover, for general ASD algorithms, the points in the same code position may have different multiplicities. In this paper, a generalized backward interpolation algorithm is proposed through constructing equivalent Grobner basis. It is capable of reducing the multiplicity of each point in the same code position by one at a time until zero, and the multiplicity of each point can be different. As an example, the proposed scheme is applied to a Chase-type decoding that has multiplicity two in the flipping points, and efficient hardware architectures are developed. For a (255, 239) RS code with eight test vectors, employing the proposed backward interpolation leads to 18% area reduction and 23% speedup compared to repeating the interpolation over the flipping points for each test vector. [ABSTRACT FROM PUBLISHER]

This paper proposes an iterative soft-decision decoding algorithm for one of the most popular algebraic-geometric (AG) codes — Hermitian codes. The algorithm is designed by integrating the two most powerful soft-decision decoding algorithms, the adaptive belief propagation (ABP) algorithm and the Koetter-Vardy (KV) list decoding algorithm. The ABP algorithm performs iterative decoding based on an adapted parity-check matrix of a Hermitian code to enhance the reliability of the soft received information. With the enhanced reliability, the KV algorithm performs soft-decision list decoding to obtain the original message. Since the matrix adaptation relies on bit reliabilities, regrouping of the unreliable bits is introduced to assist the ABP decoding. A complexity reducing ABP-KV decoding approach is proposed based on assessing the soft information provided by the ABP algorithm and determining whether the following KV decoding steps should be carried out. Geometric interpretation of the ABP algorithm is presented, demonstrating the necessity of performing matrix adaptation. Our performance analysis shows the proposed iterative decoding algorithm outperforms both the existing decoding approaches for Hermitian codes and the ABP-KV decoding of Reed-Solomon (RS) codes. [ABSTRACT FROM PUBLISHER]

The rationale of our design is that although much of the literature of cooperative systems assumes perfect coherent detection, the assumption of having any channel estimates at the relays imposes an unreasonable burden on the relay station. Hence, non-coherently detected Reed-Solomon (ReS) coded Slow Frequency Hopping (SFH) assisted M-ary Frequency Shift Keying (FSK) is proposed for cooperative wireless networks, subjected to both partial-band interference and Rayleigh fading. Erasure insertion (EI) assisted ReS decoding based on the joint maximum output-ratio threshold test (MO-RTT) is investigated in order to evaluate the attainable system performance. Compared to the conventional error-correction-only decoder, the EI scheme may achieve an E_b/N_0 gain of approximately 3 dB at the Codeword Error Probability, P_w, of 10^-4, when employing the ReS(31,20) code combined with 32-FSK modulation. Additionally, we evaluated the system's performance, when either equal gain combining (EGC) or selection combining (SC) techniques are employed at the destination's receiver. The results demonstrated that in the presence of one and two assisting relays, the EGC scheme achieves gains of 1.5 dB and 1.0 dB at the P_w of 10^-6, respectively, compared to the SC arrangement. Furthermore, we demonstrated that for the same coding rate and packet size, the ReS(31,20) code using EI decoding is capable of outperforming convolutional coding, when 32-FSK modulation is considered, whilst LDPC coding had an edge over the above two schemes. [ABSTRACT FROM AUTHOR]

This paper presents two new large classes of QC-LDPC codes, one binary and one non-binary. Codes in these two classes are constructed by array dispersions of row-distance constrained matrices formed based on additive subgroups of finite fields. Experimental results show that codes constructed perform very well over the AWGN channel with iterative decoding based on belief propagation. Codes of a subclass of the class of binary codes have large minimum distances comparable to finite geometry LDPC codes and they offer effective trade-off between error performance and decoding complexity when decoded with low-complexity reliability-based iterative decoding algorithms such as binary message passing decoding algorithms. Non-binary codes decoded with a Fast-Fourier Transform based sum-product algorithm achieve significantly large coding gains over Reed-Solomon codes of the same lengths and rates decoded with either the hard-decision Berlekamp-Massey algorithm or the algebraic soft-decision Kötter-Vardy algorithm. They have potential to replace Reed-Solomon codes in some communication or storage systems where combinations of random and bursts of errors (or erasures) occur. [ABSTRACT FROM AUTHOR]

A sphere decoder searches for the closest lattice point within a certain search radius. The search radius provides a tradeoff between performance and complexity. We focus on analyzing the performance of sphere decoding of linear block codes. We analyze the performance of soft-decision sphere decoding on AWGN channels and a variety of modulation schemes. A hard-decision sphere decoder is a bounded distance decoder with the corresponding decoding radius. We analyze the performance of hard-decision sphere decoding on binary and q-ary symmetric channels. An upper bound on the performance of maximum-likelihood decoding of linear codes defined over Fq (e.g. Reed-Solomon codes) and transmitted over q-ary symmetric channels is derived and used in the analysis. We then discuss sphere decoding of general block codes or lattices with arbitrary modulation schemes. The tradeoff between the performance and complexity of a sphere decoder is then discussed. [ABSTRACT FROM AUTHOR]

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]

This paper proposes the first complete soft-decision list decoding algorithm for Hermitian codes based on the Koetter-Vardy's Reed-Solomon code decoding algorithm. For Hermitian codes, interpolation processes trivariate polynomials which are defined over the pole basis of a Hermitian curve. In this paper, the interpolated zero condition of a trivariate polynomial with respect to a multiplicity matrix M is redefined followed by a proof of the validity of the soft-decision scheme. This paper also introduces a new stopping criterion for the algorithm that tranforms the reliability matrix Π to the multiplicity matrix M. Geometric characterisation of the trivariate monomial decoding region is investigated, resulting in an asymptotic optimal performance bound for the soft-decision decoder. By defining the weighted degree upper bound of the interpolated polynomial, two complexity reducing modifications are introduced for the soft-decision scheme: elimination of unnecessary interpolated polynomials and pre-calculation of the coefficients that relate the pole basis monomials to the zero basis functions of a Hermitian curve. Our simulation results and analyses show that soft-decision list decoding of Hermitian code can outperform Koetter-Vardy decoding of Reed-Solomon code which is defined in a larger finite field, but with less decoding complexity. [ABSTRACT FROM AUTHOR]

Gao's algorithm similar to Shiozaki's algorithm for decoding nonsystematic Reed-Solomon (RS) codes which is a subclass of the redundant residue polynomial codes is considered here. This algorithm computes the message polynomial directly without explicitly finding the error-locator polynomial and error- evaluator polynomial. In this letter, a simplified decoding algorithm to correct both errors and erasures is used in conjunction with Gao's algorithm for efficiently decoding RS codes. In addition, we show that the extended Gao algorithm similar to the Shiozaki-Truong-Cheung-Reed algorithm significantly reduces the decoding complexity. [ABSTRACT FROM AUTHOR]

The recently approved IEEE 802.15.4a standard defines an ultra-wideband (UWB) based physical layer using concatenated coding with mixed binary phase-shift keying and binary pulse-position modulation (BPSK-BPPM) and direct-sequence spreading with time hopping. The concatenated code consists of an outer Reed-Solomon (RS) and an inner convolutional code, and the coding and modulation are combined such that both coherent and noncoherent receiver architectures are supported. In this paper, the error-rate performance of IEEE 802.15.4a compliant UWB radios is investigated. To this end, semi-analytical expressions for the bit-error rate (BER) and frame-error rate (FER) of the coded UWB system are derived. The presented framework is comprehensive in that (i) different methods for generating reliability information (i.e., decoding metrics), (ii) the effects of suboptimal multipath combining, and (iii) coherent and noncoherent reception methods are included. Furthermore, a particularly suited errors-and-erasures RS decoding scheme is devised. The evaluation of the error-rate expressions together with simulation results for realistic UWB channels show that (i) the error-rate approximations are tight over wide ranges of BER and FER, (ii) symbol-wise metrics are clearly advantageous over bit-wise metrics for decoding of the convolutional code, (iii) combining the 5 to 10 strongest multipath components approaches the performance of full combining within 1-2 dB for residential and 3-5 dB for outdoor UWB environments, and (iv) the simplicity of noncoherent detection comes at loss of more than 10 dB in signal-to-noise ratio compared to coherent detection. [ABSTRACT FROM AUTHOR]

This paper presents algebraic methods for constructing high performance and efficiently encodable non-binary quasi-cyclic LDPC codes based on flats of finite Euclidean geometries and array masking. Codes constructed based on these methods perform very well over the AWGN channel. With iterative decoding using a Fast Fourier Transform based sum-product algorithm, they achieve significantly large coding gains over Reed-Solomon codes of the same lengths and rates decoded with either algebraic hard-decision Berlekamp-Massey algorithm or algebraic soft-decision Kötter-Vardy algorithm. Due to their quasi-cyclic structure, these non-binary LDPC codes on Euclidean geometries can be encoded using simple shift-registers with linear complexity. Structured non-binary LDPC codes have a great potential to replace Reed-Solomon codes for some applications in either communication or storage systems for combating mixed types of noise and interferences. [ABSTRACT FROM AUTHOR]

This paper presents a novel Reed-Solomon codes based transmission scheme called RS-SC-CP. While RS-SC-CP is essentially a Reed-Solomon (RS) coded single carrier with cyclic prefix (SC-CP) system, a filter bank representation of the RS code is used. This filter bank representation unveils a DFT synthesis bank, just as in a traditional Orthogonal Frequency Division Multiplexing (OFDM) system (allbeit in a finite field). Therefore, RS-SC-CP is topologically equivalent with OFDM. As such, the RS-SC-CP system inherits the advantages of an SC-CP system over a traditional OFDM system like a low Peak to Average Power Ratio (PAPR). But, more importantly, it allows us to use a novel equalization technique that resembles a traditional OFDM equalizer. The equalizer of an RS-SC-CP receiver is split into two stages: the first stage encompasses a partial equalization in the complex field, which ensures that the residual channel response has integer coefficients. It is calculated using a Minimum Mean Square Error (MMSE) criterion. The residual ISI is removed by a Galois field equalizer in the second stage, posterior to the RS decoding removing the noise. Finally, the performance of the RS-SC-CP system is further evaluated by simulations showing the performance gain of the RS-SC-CP system compared to a traditional coded OFDM or Single Carrier with Cyclic Prefix (SC-CP) scheme. [ABSTRACT FROM AUTHOR]

Optimization of the transmission range in terms of maximizing information efficiency is studied in this paper for mobile ad hoc networks (MANETs) with frequency-hopped (FH) CDMA and multiple antennas. Realistic channel models are employed to account for path-loss, log-normal shadowing, and Rayleigh fading. The shadowing and fading are assumed time-varying with different time-scales due to mobility and hopping. The receiver employs decision-feedback demodulation for differential unitary space-time modulation and erasure insertion decoding for Reed-Solomon codes [14] [15]. The decoding error probability is derived based on distributions of the multiple access interference power and the signal-to-interference ratio in a dwell for ground propagation model. The trade-off between information efficiency and transmission range is studied in detail and insight is obtained into the impact of various factors, including the spreading gain, modulation and coding schemes, feedback length, erasure insertion, order of spatial diversity, time-variation of the shadowing, and channel statistics such as Doppler frequency and shadowing spread. [ABSTRACT FROM AUTHOR]

In this paper two symbol-level soft-decision decoding algorithms for Reed-Solomon codes, derived form the Ordered Statistics (OS) and from the Generalized Minimum-Distance (GMD) decoding methods, are presented and analyzed. Both the OS and the GMD algorithms are based on the idea of producing a list of candidate code words, among which the one having the larger likelihood is selected as output. We propose variants of the mentioned algorithms that allow to finely tune the size of the list in order to obtain the desired decoding complexity. The method proposed by Agrawal and Vardy for computing the error probability of the GMD algorithm is extended to our decoding methods. Examples are presented where these algorithms are applied to singly-extended Reed-Solomon codes over GF(16) used as outer codes in a 128-dimensional coded modulation scheme that attains good performance, with manageable decoding complexity. [ABSTRACT FROM AUTHOR]

This paper presents an analytical model for the study of Hybrid ARQ techniques on Discrete Time Markov Channels by means of an appropriate Markov chain, which tracks the transmission outcome and can be used to evaluate several performance metrics, including throughput, loss probability, number of retransmissions, and delay. The analysis is carried out with the assumptions that the information frame is encoded by the source with a linear block code and hard decoding is used at the receiver side. We finally present numerical evaluations for the performance of a truncated Type II Hybrid ARQ technique based on Reed Solomon erasure codes. [ABSTRACT FROM AUTHOR]

This paper presents five methods for constructing nonbinary LDPC codes based on finite geometries. These methods result in five classes of nonbinary LDPC codes, one class of cyclic LDPC codes, three classes of quasi-cyclic LDPC codes and one class of structured regular LDPC codes. Experimental results show that constructed codes in these classes decoded with iterative decoding based on belief propagation perform very well over the AWGN channel and they achieve significant coding gains over Reed-Solomon codes of the same lengths and rates with either algebraic hard-decision decoding or Kötter-Vardy algebraic soft-decision decoding at the expense of a larger decoding computational complexity. [ABSTRACT FROM AUTHOR]

In this letter, Fedorenko and Trifonov's procedure is applied to evaluate the syndrome of the received word in time-domain Reed-Solomon decoders. This application leads to a substantial reduction of the computational complexity of the syndrome polynomial for correcting both errors and erasures. Moreover, simulation results for this new syndrome method are given. [ABSTRACT FROM AUTHOR]