Two-dimensional multiplicative arrays over Zq−1 and girth-6 q-ary QC-LDPC codes based on quadratic-residues modulo p < q

Construction of q-ary quasi-cyclic low-density parity-check (QC-LDPC) codes based on two-dimensional multiplicative arrays over Z_q−1, q = 2^m, is studied. In particular, two-dimensional arrays formed by the set of quadratic-residue numbers modulo prime numbers less than q are considered.     

On the decoding of Reed-Solomon and BCH codes over integer residuerings

We present a decoding procedure for Reed-Solomon (RS) and BCH codes defined over an integer residue ring pgZ_q, where q is a power of a prime p. The proposed decoding procedure, as for RS and BCH codes over fields, consists of four major steps: (1) calculation of the syndromes; (2) calculation of the “elementary symmetric functions,” by a modified Berlekamp-Massey (1968, 1969) algorithm for commutative rings; (3) calculation of the error location numbers; and (4) calculation of the error magnitudes. The proposed decoding procedure also applies to the synthesis of a shortest linear-feedback shift register (LFSR), capable of generating a prescribed finite sequence of elements lying in a commutative ring with identity     

Abelian codes over Galois rings closed under certain permutations

We study n-length Abelian codes over Galois rings with characteristic p/sup a/, where n and p are relatively prime, having the additional structure of being closed under the following two permutations: (i) permutation effected by multiplying the coordinates with a unit in the appropriate mixed-radix representation of the coordinate positions and (ii) shifting the coordinates by t positions. A code is t-quasi-cyclic (t-QC) if t is an integer such that cyclic shift of a codeword by t positions gives another codeword. We call the Abelian codes closed under the first permutation as unit-invariant Abelian codes and those closed under the second as quasi-cyclic Abelian (QCA) codes. Using a generalized discrete Fourier transform (GDFT) defined over an appropriate extension of the Galois ring, we show that unit-invariant Abelian and QCA codes can be easily characterized in the transform domain. For t=1, QCA codes coincide with those that are cyclic as well as Abelian. The number of such codes for a specified size and length is obtained and we also show that the dual of an unit-invariant t-QCA code is also an unit-invariant t-QCA code. Unit-invariant Abelian (hence unit-invariant cyclic) and t-QCA codes over Galois field F/sub p//sup l/ and over the integer residue rings are obtainable as special cases.     

Shift-register synthesis and BCH decoding

It is shown in this paper that the iterative algorithm introduced by Berlekamp for decoding BCH codes actually provides a general solution to the problem of synthesizing the shortest linear feedback shift register capable of generating a prescribed finite sequence of digits. The shift-register approach leads to a simple proof of the validity of the algorithm as well as providing additional insight into its properties. The equivalence of the decoding problem for BCH codes to a shift-register synthesis problem is demonstrated, and other applications for the algorithm are suggested.     

Hyperelliptic curves encryption combined with block codes for Gaussian channel

In this paper, a new cryptographic system is constructed using a combination of a hyperelliptic curve of genus g = 2 over the Galois field GF(2ⁿ) and a Reed–Solomon code (N, K) over the Galois field GF(2^m) and this system uses a smaller key than the elliptic curves cryptosystem and the Rivest, Shamir, and Adleman cryptosystem. The design criterion for the combination can be expressed as the data compression condition and addressing capability of the code. In addition, the system performance is compared with other systems; extraordinary improvements of 8 and 16.5 dB can be obtained for a BER = 10^?5, when compared with binary phase shift keying and differential chaos shift keying, respectively. This system has a polynomial complexity, which depends on data length and the number of operations in GF(2ⁿ). Copyright © 2005 John Wiley & Sons, Ltd.     

A generalized correlation attack on a class of stream ciphers based on the Levenshtein distance

A statistical approach to cryptanalysis of a memoryless function of clock-controlled shift registers is introduced. In the case of zero-order correlation immunity, an algorithm for a shift register initial state reconstruction based on the sequence comparison concept is proposed. A constrained Levenshtein distance relevant for the cryptanalysis is defined and a novel recursive procedure for its efficient computation is derived. Preliminary experimental results are given and open theoretic problems are discussed.Following [11], a Boolean function f(x ₁,..., x _n) is said to be mth-order correlation immune if m is the maximum integer such that the random variable f(X ₁,..., X _n) is statistically independent of every set of m random variables chosen from the balanced and independent binary random variables X ₁,..., X _n.     

Multisequence shift register synthesis over commutative rings with identity with applications to decoding cyclic codes over integer residue rings

We present a new algorithm for solving the multisequence shift register synthesis problem over a commutative ring R with identity. Given a finite set of R-sequences, each of length L, the complexity of our algorithm in terms of R-multiplications is O(L/sup 2/) as L /spl rarr/ /spl infin/. An important application of this algorithm is in the decoding of cyclic codes over Z/sub q/ up to the Hartmann-Tzeng bound, where q is a prime power. Characterization of the set of monic characteristic polynomials of a prescribed set of multiple syndrome sequences leads to an efficient decoding procedure, which we further extend to decode cyclic codes over Z/sub m/ where m is a product of prime powers.     

Hamming metric decoding of alternant codes over Galois rings

The standard decoding procedure for alternant codes over fields centers on solving a key equation which relates an error locator polynomial and an error evaluator polynomial by a syndrome sequence. We extend this technique to decode alternant codes over Galois rings. We consider the module M={(a, b): as≡b mod x^r} of all solutions to the key equation where s is the syndrome polynomial and r, is the number of rows in a parity-check matrix for the code. In decoding we seek a particular solution (Σ, Ω)∈M which we prove can be found in a Grobner basis for M. We present an iterative algorithm which generates a Grobner basis modulo x^k+1 from a given basis modulo x^k. At the rth step, a Grobner basis for M is found, and the required solution recovered     

Fibonacci and Galois representations of feedback-with-carry shiftregisters

A feedback-with-carry shift register (FCSR) with "Fibonacci" architecture is a shift register provided with a small amount of memory which is used in the feedback algorithm. Like the linear feedback shift register (LFSR), the FCSR provides a simple and predictable method for the fast generation of pseudorandom sequences with good statistical properties and large periods. In this paper, we describe and analyze an alternative architecture for the FCSR which is similar to the "Galois" architecture for the LFSR. The Galois architecture is more efficient than the Fibonacci architecture because the feedback computations are performed in parallel. We also describe the output sequences generated by the d-FCSR, a slight modification of the (Fibonacci) FCSR architecture in which the feedback bit is delayed for d clock cycles before being returned to the first cell of the shift register. We explain how these devices may be configured so as to generate sequences with large periods. We show that the d-FCSR also admits a more efficient "Galois" architecture     

准循环多进制LDPC码构造

该文研究准循环多进制LDPC码的构造,给出多进制LDPC码的设计流程和构造方法.详细讨论了多进制LDPC码的性能影响因素,综合考虑了环长和环的连通性对性能的影响,研究了母矩阵扩展中偏移因子的选择以及GF(q)上非零元素替代.同时提出了次优解的搜索方法,以降低搜索复杂度.最后,将提出的方法用于不同阶数下LDPC码的构造.仿真结果表明,通过新方法构造得到的多进制LDPC码与二进制码相比,在BPSK调制方式下在误帧率10-4附近有0.2 dB的性能提升;在有限域阶数与调制阶数匹配的情况下,有更大的性能提升.与相近码长,相同码率的多进制循环码相比,该文构造得到的多进制LDPC码在误帧率10-4附近有0.25 dB的性能提升.     

Multisequence Linear Shift Register Synthesis and Its Application to BCH Decoding

This concise paper demonstrates the decoding of BCH codes by using a multisequence linear feedback shift register (MLFSR) synthesis algorithm. The algorithm is investigated and developed. With this algorithm, a class of good codes has been found with errorcorrecting capability at least as good as the BCH bound. The application of this algorithm to BCH decoding is discussed.     

An algorithm of complete decoding of double-error-correcting goppa codes

In this paper an algorithm of complete decoding procedure for the Goppa codes with generater polynomialG(z)=z ²+z+β and parameters (2 ^m , 2 ^m , −2m, 5) is shown. The algorithm requires at mostm times calculating inner product of vectors overGF(2) and finding roots of quadratic equation inGF(2 ^m ). Form≤12, the algorithm has been realized.     

Cyclic codes over the ring $$ Z_{P^2 } $$ of length pe

The study of cyclic codes over rings has generated a lot of public interest. In this paper, we study cyclic codes and their dual codes over the ring Zp^2 of length p^e, and find a set of generators for these codes. The ranks and minimal generator sets of these codes are studied as well, which play an important role in decoding and determining the distance distribution of codes.     

环Fpm+uFpm上长为pk的循环码计数

环R=Fpm+uFpm上长为pk的循环码可看作R[x]/＜xpk-1＞上的理想.该文通过对R[x]/＜xpk-1＞上理想的研究,得到了环Fpm+uFpm上长为的循环码的唯一表示方法和计数,并给出了该环上长为pk的循环自对偶码的结构和计数.     

A generalization of the Berlekamp-Massey algorithm formultisequence shift-register synthesis with applications to decodingcyclic codes

A generalization of the Berlekamp-Massey algorithm is presented for synthesizing minimum length linear feedback shift registers for generating prescribed multiple sequences. A more general problem is first considered, that of finding the smallest initial set of linearly dependent columns in a matrix over an arbitrary field, which includes the multisequence problem as a special case. A simple iterative algorithm, the fundamental iterative algorithm (FIA), is presented for solving this problem. The generalized algorithm is then derived through a refinement of the FIA. Application of this generalized algorithm to decoding cyclic codes up to the Hartmann-Tzeng (HT) bound and Roos bound making use of multiple syndrome sequences is considered. Conditions for guaranteeing that the connection polynomial of the shortest linear feedback shift register obtained by the algorithm will be the error-locator polynomial are determined with respect to decoding up to the HT bound and special cases of the Roos bound     

Negacyclic codes of length 2/sup s/ over galois rings

Codes over the ring of integers modulo 4 have been studied by many researchers. Negacyclic codes such that the length n of the code is odd have been characterized over the alphabet Zopf₄, and furthermore, have been generalized to the case of the alphabet being a finite commutative chain ring. In this paper, we investigate negacyclic codes of length 2^s over Galois rings. The structure of negacyclic codes of length 2^s over the Galois rings GR(2^a,m), as well as that of their duals, are completely obtained. The Hamming distances of negacyclic codes over GR(2^a,m) in general, and over Zopf₂ ^a in particular are studied. Among other more general results, the Hamming distances of all negacyclic codes over Zopf₂ ^a of length 4,8, and 16 are given. The weight distributions of such negacyclic codes are also discussed     

A transform decoder for Reed-Solomon codes in multiple-user communication systems

Encoding and decoding algorithms for Reed-Solomon codes based on Fourier-like transforms on finite field and finite rings are discussed. Classes of codes are proposed for two different types of multiple-user communication systems: a multichannel communication system and a multiaccess communication system. For the first system, a fast decoding algorithm is developed that uses transforms on a finite ring which is isomorphic to a direct sum of Galois fields. For the second system, an efficient (in terms of information rate) coding scheme is proposed which utilizes a direct sum of Galois fields.     

Channel coding for satellite mobile channels

The deployment of channel coding and interleaving to enhance the bit-error performance of a satellite mobile radio channel is addressed for speech and data transmissions. Different convolutional codes (CC) using Viterbi decoding with soft decision are examined with inter-block interleaving. Reed-Solomon (RS) codes with Berlekamp-Massey hard decision decoding or soft decision trellis decoding combined with block interleaving are also investigated. A concatenated arrangement employing RS and CC coding as the outer and inner coders, respectively, is used for transmissions via minimum shift keying (MSK) over Gaussian and Rayleigh fading channels. For an interblock interleaving period of 2880 bits, a concatenated arrangement of an RS(48,36). over the Galois field GF(256) and punctured PCC(3,1,7) yielding an overall coding rate of 1/2, provides a coding gain of 42dB for a BER of 10^?6, and an uncorrectable error detection probability of 1–10^?9.     

A doubling procedure for constructing minimal broadcast networks

Broadcast is the task of disseminating a message from any node to all the other nodes in a network. A minimal broadcast network (mbn) withn nodes is a communication network in which a message originated at any node can be broadcasted in [log₂ n] time units. An optimal broadcast network (obn) is an mbn with minimum number of edges. No method is known for constructing an obn with an arbitrary number of nodes. In this paper, a new method called the doubling procedure is presented to construct mbn's with 2n and 2n–1 nodes when an obn or a good mbn withn nodes is known. The new construction method is based on the concepts of center node and center node set of an mbn. An algorithm is proposed to find a center node set of a given mbn. It is shown that an obn with 2n nodes can be constructed based on a known obn withn nodes for alln 9,n=15, 31 and 63,n=2 ^m –1 andn=2 ^m ,mZ ⁺, by applying the doubling procedure. This method also generates the best mbn's for some values of [n64.     

Facile Synthesis of Manganese‐Oxide‐Containing Mesoporous Nitrogen‐Doped Carbon for Efficient Oxygen Reduction

Developing low‐cost non‐precious metal catalysts for high‐performance oxygen reduction reaction (ORR) is highly desirable. Here a facile, in situ template synthesis of a MnO‐containing mesoporous nitrogen‐doped carbon (m‐N‐C) nanocomposite and its high electrocatalytic activity for a four‐electron ORR in alkaline solution are reported. The synthesis of the MnO‐m‐N‐C nanocomposite involves one‐pot hydrothermal synthesis of Mn₃O₄@polyaniline core/shell nanoparticles from a mixture containing aniline, Mn(NO₃)₂, and KMnO₄, followed by heat treatment to produce N‐doped ultrathin graphitic carbon coated MnO hybrids and partial acid leaching of MnO. The as‐prepared MnO‐m‐N‐C composite catalyst exhibits high electrocatalytic activity and dominant four‐electron oxygen reduction pathway in 0.1 M KOH aqueous solution due to the synergetic effect between MnO and m‐N‐C. The pristine MnO shows little electrocatalytic activity and m‐N‐C alone exhibits a dominant two‐electron process for ORR. The MnO‐m‐N‐C composite catalyst also exhibits superior stability and methanol tolerance to a commercial Pt/C catalyst, making the composite a promising cathode catalyst for alkaline methanol fuel cell applications. The synergetic effect between MnO and N‐doped carbon described provides a new route to design advanced catalysts for energy conversion.