Steganalysis of BCH code based stego schemes

The class of stego systems based on error correcting codes is one of the alternatives to conventional steganographic systems. In the context of code based steganography, the BCH code based stego system offers a very smart solution based on the hardness of syndrome decoding. It has been shown that syndrome decoding problem is able to resist the existing steganalysis attacks. In this paper, we introduce an attack against these systems using a new syndrome decoding method. This scheme also generates a direct estimate of the secret message bit locations by exploiting the embedding patterns. This new attack notably points out that BCH code based stego system with its original parameters do not provide sufficient security.     

Impulsive noise cancellation in multicarrier transmission

A parallel between Reed-Solomon codes in the complex field and multicarrier transmission using orthogonal frequency-division multiplexing (OFDM) is first presented. This shows that when the signal is sent over some channel composed of Gaussian plus impulsive noise, the impulsive noise can be removed by a procedure similar to channel decoding, using information carried by the "syndrome." This result is first derived in a simple situation (oversampled discrete multitone, additive channel), which is merely of theoretical interest. In any case, consecutive zeros, in the output of the OFDM modulator, do not correspond to real subcarriers. Pilot tones are transmitted for synchronization or channel-estimation purposes. These pilot tones are generally scattered among the information ones. Our approach is to use these pilot tones as syndromes, in order to correct impulsive noise. We show that the correction capacity is conditioned by the position of these pilot tones in the transmitted sequence. A protection subsystem based on hypotheses tests is introduced after the decoding operation in order to detect malfunctions of this decoder. The efficiency of this technique is corroborated with simulations in the slightly modified Hiperlan2 context. Other extensions are then provided in order to increase the practical usefulness of the method.     

秩距离BCH码的进一步研究

本文作者在“关于秩距离BCH码的校验矩阵及其秩距离”一文中提出了秩距离BCH码的概念，讨论了所给秩距离BCH码为最大秩距离BCH码时，码的生成多项式的根应满足的条件。本文在此基础上，讨论当线性秩距离码的生成多项式具有广义连续根时，它能构成秩距离BCH码的充分条件并给出了此充分条件。     

Algebraic decoding of the (32, 16, 8) quadratic residue code

An algebraic decoding algorithm for the 1/2-rate (32, 16, 8) quadratic residue (QR) code is found. The key idea of this algorithm is to find the error locator polynomial by a systematic use of the Newton identities associated with the code syndromes. The techniques developed extend the algebraic decoding algorithm found recently for the (32, 16, 8) QR code. It is expected that the algebraic approach developed here and by M. Elia (1987) applies also to longer QR codes and other BCH-type codes that are not fully decoded by the standard BCH decoding algorithm     

基于FPGA的RS(255,239)编译码器

编码是一种具有较强纠错能力的多进制BCH编码,其既可纠正随机错误,又可纠正突发错误。RS编译码器广泛应用于通信和存储系统,为解决高速存储器中数据可靠性的问题,文中提出了RS编码的实现方法,并对编码进行了时序仿真。仿真结果表明,该译码器可实现良好的纠错功能。     

On classical BCH codes and quantum BCH codes

It is a regular way of constructing quantum error-correcting codes via codes with self-orthogonal property, and whether a classical Bose-Chaudhuri-Hocquenghem (BCH) code is self-orthogonal can be determined by its designed distance. In this paper, we give the sufficient and necessary condition for arbitrary classical BCH codes with self-orthogonal property through algorithms. We also give a better upper bound of the designed distance of a classical narrow-sense BCH code which contains its Euclidean dual. Besides these, we also give one algorithm to compute the dimension of these codes. The complexity of all algorithms is analyzed. Then the results can be applied to construct a series of quantum BCH codes via the famous CSS constructions.     

The algebraic decoding of Goppa codes

An interesting class of linear error-correcting codes has been found by Goppa [3], [4]. This paper presents algebraic decoding algorithms for the Goppa codes. These algorithms are only a little more complex than Berlekamp's well-known algorithm for BCH codes and, in fact, make essential use of his procedure. Hence the cost of decoding a Goppa code is similar to the cost of decoding a BCH code of comparable block length.     

On the computation of the performance probabilities for block codeswith a bounded-distance decoding rule

When a block code is used on a discrete memoryless channel with an incomplete decoding rule that is based on a generalized distance, the probability of decoding failure, the probability of erroneous decoding, and the expected number of symbol decoding errors can be expressed in terms of the generalized weight enumerator polynomials of the code. For the symmetric erasure channel, numerically stable methods to compute these probabilities or expectations are proposed for binary codes whose distance distributions are known, and for linear maximum distance separable (MDS) codes. The method for linear MDS codes saves the computation of the weight distribution and yields upper bounds for the probability of erroneous decoding and for the symbol error rate by the cumulative binomial distribution. Numerical examples include a triple-error-correcting Bose-Chaudhuri-Hocquenghem (BCH) code of length 63 and a Reed-Solomon code of length 1023 and minimum distance 31     

A generalized Euclidean algorithm for multisequence shift-registersynthesis

The problem of finding a linear-feedback shift register of shortest length capable of generating prescribed multiple sequences is considered. A generalized Euclidean algorithm, which is based on a generalized polynomial division algorithm, is presented. A necessary and sufficient condition for the uniqueness of the solution is given. When the solution is not unique, the set of all possible solutions is also derived. It is shown that the algorithm can be applied to the decoding of many cyclic codes for which multiple syndrome sequences are available. When it is applied to the case of a single sequence, the algorithm reduces to that introduced by Y. Sugiyama et al. (Inf. Control, vol.27, p.87-9, Feb. 1975) in the decoding of BCH codes     

Undetected error probabilities of binary primitive BCH codes forboth error correction and detection

We investigate the undetected error probabilities for bounded-distance decoding of binary primitive BCH codes when they are used for both error correction and detection on a binary symmetric channel. We show that the undetected error probability of binary linear codes can be simplified and quantified if the weight distribution of the code is binomial-like. We obtain bounds on the undetected error probability of binary primitive BCH codes by applying the result to the code and show that the bounds are quantified by the deviation factor of the true weight distribution from the binomial-like weight distribution     

A new procedure for decoding cyclic and BCH codes up to actualminimum distance

The paper presents a new procedure for decoding cyclic and BCH codes up to their actual minimum distance. It generalizes the Peterson decoding procedure and the procedure of Feng and Tzeng (1991) using nonrecurrent syndrome dependence relations. For a code with actual minimum distance d to correct up to t=[(d-1)/2] errors, the procedure requires a (2t+1)×(2t+1) syndrome matrix with known syndromes above the minor diagonal and unknown syndromes and their conjugates on the minor diagonal. In contrast to previous procedures, this procedure is primarily aimed at solving for the unknown syndromes instead of determining an error-locator polynomial. Decoding is then accomplished by determining the error vector as the inverse Fourier transform of the syndrome vector (S₀, S₁, S_n-1). The authors show that with this procedure, all binary cyclic and BCH codes of length <63 (with one exception) can be decoded up to their actual minimum distance. The procedure incorporates an extension of their fundamental iterative algorithm and a majority scheme for confirming the true values computed for the unknown syndromes. The complexity of this decoding procedure is O(n³)     

A simple decoding of BCH codes over GF(2m)

A simple decoding method for even minimum-distance Bose-Chaudhuri-Hochquenghem (BCH) codes is proposed. In the method the coefficients of an error locator polynomial are given as simple determinants (named Q determinants) composed of syndromes. The error evaluator is realized as a Q determinant divided by an error locator polynomial. The Q determinants can be efficiently obtained with very simple calculations on syndromes enabling the realization of a high-speed decoder of simple configuration. The number of calculations in obtaining the error locator and the error evaluator with the proposed method is smaller than that with the widely used Berlekamp-Massey algorithm when the number of correctable errors of the code is five or less. The proposed method can also be applied to the binary narrow-sense BCH codes of odd minimum distance     

Block error-correcting codes for systems with a very high BER: Theoretical analysis and application to the protection of watermarks

This paper addresses the problem of error-correction for extremely noisy channels (BER from 0.1 to 0.5), such as those obtained for image or video watermarking. Minimum distance arguments are used to identify a region for which no other code is as efficient as repetition codes, whatever the rate, at least when bounded decoding is considered. However, in order to obtain a reasonable and sufficiently low BER, repetition codes are not very efficient. We present a coding scheme concatenating a repetition code with another one, and design rules in order to select these codes for a given watermarking application are developed. The repetition code lowers the huge channel BER, as no other code can do this part of the job. Then, the second more powerful code working at a lower BER achieves a larger BER reduction. In this paper, this role is devoted to BCH codes, as members of a classical family. Thanks to their moderate decoding complexity, they turn out to be an interesting cost versus performance trade-off, while more efficient coding schemes based on soft decoding are far more complex. However, we also provide an idea of the solutions to consider for watermarking applications with fewer complexity limitations, for which more powerful decoding techniques can be implemented.     

The algebraic decoding of the (41, 21, 9) quadratic residue code

A new algebraic approach for decoding the quadratic residue (QR) codes, in particular the (41, 21, 9) QR code, is presented. The key ideas behind this decoding technique are a systematic application of the Sylvester resultant method to the Newton identities associated with the syndromes to find the error-locator polynomial, and next a method for determining error locations by solving certain quadratic, cubic, and quartic equations over GF(2^m) in a new way which uses Zech's logarithms for the arithmetic. The logarithms developed for Zech's logarithms save a substantial amount of computer memory by storing only a table of Zech's logarithms. These algorithms are suitable for implementation in a programmable microprocessor or special-purpose VLSI chip. It is expected that the algebraic methods developed can apply generally to other codes such as the BCH and Reed-Solomon codes     

乘积码迭代译码算法研究

介绍了在分组码的软输入软输出译码基础上以扩展BCH码为子码的乘积码的迭代译码算法,提出了在高带宽利用率调制方式下的算法应用方式,并给出了仿真结果。最后与传统的并联卷级码代译码方案比较,发现在高编码效率时,乘积码迭代译码方案有着较好的应用性。     

Algebraic decoding of the (23,12,7) Golay code (Corresp.)

It is shown that the algebraic method for decoding three-error-correcting BCH codes is also applicable to complete decoding of the(23,12,7)Golay code.     

Estimation of the exponent of the decoding error probability for a special generalized LDPC code

A special construction of a generalized low-density parity-check (LDPC) code and a low-complexity algorithm for his code decoding are proposed. A lower estimate of the exponent of the decoding error probability is obtained for the considered code and the decoding algorithm. This estimate leads the conclusion that, in an ensemble of considered LDPC codes, there are codes with rates as high as the code capacity and the exponent of the decoding error probability exceeds zero.     

Estimating the fraction of erasure patterns correctable by linear codes

The conditional probability (fraction) of the successful decoding of erasure patterns of high (greater than the code distance) weights is investigated for linear codes with the partially known or unknown weight spectra of code words. The estimated conditional probabilities and the methods used to calculate them refer to arbitrary binary linear codes and binary Hamming, Panchenko, and Bose–Chaudhuri–Hocquenghem (BCH) codes, including their extended and shortened forms. Error detection probabilities are estimated under erasure-correction conditions. The product-code decoding algorithms involving the correction of high weight erasures by means of component Hamming, Panchenko, and BCH codes are proposed, and the upper estimate of decoding failure probability is presented.     

纠两个错的二元BCH码的代数完全译码

本文提出纠两个错的二元BCH码的代数完全译码方法。它实现起来比Hartmann的一步一步译码方法速度快,并且当对应校验子S1、S3的错误图样重量为3时,能找出所有对应同样校验子的重量为3的错误图样。同时,本文也建立了GF(2m)上三次方程在GF(2m)上有三个不同根的判别式,这在纠三个错的二元BCH码的完全译码中十分重要。     

On high-speed decoding of the (23,12,7) Golay code

An algebraic decoding method for triple-error-correcting binary BCH codes applicable to complete decoding of the (23,12,7) Golay code has been proved by M. Elia (see ibid., vol.IT-33, p.150-1, 1987). A modified step-by-step complete decoding algorithm of this Golay code is introduced which needs fewer shift operations than Kasami's error-trapping decoder. Based on the algorithm, a high-speed hardware decoder of this code is proposed