A class of 1-generator quasi-cyclic codes

If R = F/sub q/[x/spl rceil/]/(x/sup m/ - 1), S = F/sub qn/[x]/(x/sup m/ - 1), we define the mapping a_(x) /spl rarr/ A(x) =/spl sigma//sub 0//sup n-1/a/sub i/(x)/spl alpha//sub i/ from R/sup n/ onto S, where (/spl alpha//sub 0/, /spl alpha//sub i/,..., /spl alpha//sub n-1/) is a basis for F/sub qn/ over F/sub q/. This carries the q-ray 1-generator quasicyclic (QC) code R a_(x) onto the code RA(x) in S whose parity-check polynomial (p.c.p.) is defined as the monic polynomial h(x) over F/sub q/ of least degree such that h(x)A(x) = 0. In the special case, where gcd(q, m) = 1 and where the prime factorizations of x/sub m/ 1 over F/sub q/ and F/sub qn/ are the same we show that there exists a one-to-one correspondence between the q-ary 1-generator quasis-cyclic codes with p.c.p. h(x) and the elements of the factor group J* /I* where J is the ideal in S with p.c.p. h(x) and I the corresponding quantity in R. We then describe an algorithm for generating the elements of J*/I*. Next, we show that if we choose a normal basis for F/sub qn/ over F/sub q/, then we can modify the aforementioned algorithm to eliminate a certain number of equivalent codes, thereby rending the algorithm more attractive from a computational point of view. Finally in Section IV, we show how to modify the above algorithm in order to generate all the binary self-dual 1-generator QC codes.     

Note on decoding binary Goppa codes

The author gives a simple expression for the polynomial y(x) which solves the polynomial equation y(x)²≡t(x) mod G(x), where t(x), y(x) and G(x) are polynomials over the field GF(2^m). The solution of such an equation is a step in the so called Patterson algorithm for decoding binary Goppa codes. The result may also be useful for other applications     

Compression mappings on primitive sequences over Z/(p/sup e/)

Let Z/(p/sup e/) be the integer residue ring with odd prime p/spl ges/5 and integer e/spl ges/2. For a sequence a_ over Z/(p/sup e/), there is a unique p-adic expansion a_=a_/sub 0/+a_/spl middot/p+...+a_/sub e-1//spl middot/p/sup e-1/, where each a_/sub i/ is a sequence over {0,1,...,p-1}, and can be regarded as a sequence over the finite field GF(p) naturally. Let f(x) be a primitive polynomial over Z/(p/sup e/), and G'(f(x),p/sup e/) the set of all primitive sequences generated by f(x) over Z/(p/sup e/). Set /spl phi//sub e-1/ (x/sub 0/,...,x/sub e-1/) = x/sub e-1//sup k/ + /spl eta//sub e-2,1/(x/sub 0/, x/sub 1/,...,x/sub e-2/) /spl psi//sub e-1/(x/sub 0/,...,x/sub e-1/) = x/sub e-1//sup k/ + /spl eta//sub e-2,2/(x/sub 0/,x/sub 1/,...,x/sub e-2/) where /spl eta//sub e-2,1/ and /spl eta//sub e-2,2/ are arbitrary functions of e-1 variables over GF(p) and 2/spl les/k/spl les/p-1. Then the compression mapping /spl phi//sub e-1/:{G'(f(x),p/sup e/) /spl rarr/ GF(p)/sup /spl infin// a_ /spl rarr/ /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) is injective, that is, a_ = b_ if and only if /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) = /spl phi//sub e-1/(b_/sub 0/,...,b_/sub e-1/) for a_,b_ /spl isin/ G'(f(x),p/sup e/). Furthermore, if f(x) is a strongly primitive polynomial over Z/(p/sup e/), then /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) = /spl psi//sub e-1/(b_/sub 0/,...,b_/sub e-1/) if and only if a_ = b_ and /spl phi//sub e-1/(x/sub 0/,...,x/sub e-1/) = /spl psi//sub e-1/(x/sub 0/,...,x/sub e-1/) for a_,b_ /spl isin/ G'(f(x),p/sup e/).     

Cubic-spline interpolation. 1

The need to interpolate is widespread, and the approaches to interpolation are just as widely varied. For example, sampling a signal via a sample and-hold circuit at uniform, T-second intervals produces an output signal that is a piecewise-constant (or zero-order) interpolation of the signal samples. Similarly, a digital-to-analog (D/A) converter that incorporates no further post-filtering produces an output signal that is (ideally) piecewise-constant. One very effective, well-behaved, computationally efficient interpolator is the cubic spline. The approach is to fit cubic polynomials to adjacent pairs of points and choose the values of the two remaining parameters associated with each polynomial such that the polynomials covering adjacent intervals agree with one another in both slope and curvature at their common endpoint. The piecewise-cubic interpolating function g(x) that results is twice continuously differentiable. We develop the basic algorithm for cubic-spline interpolation     

基于公约式权重的截短线性分组码盲识别方法

针对通信信号侦察处理中的截短线性分组码的盲识别问题,提出了一种基于公约式权重最大化的识别方法.算法对侦收的码字序列进行不同长度的分段,计算分段码字与xn+1的最大公约式并按公约式阶数进行滤除,通过高阶公约式的个数估计码字长度.同时根据公约式的出现概率定义公约式的权重,利用权重最大的公约式实现码字生成多项式的估计.仿真实验表明算法有效可行,并理论分析了算法的容错性和计算复杂度.和已有算法相比较,本文算法在相同的误码率条件下,具有更高的检测识别概率,且同时具备截短码字和非截短码字的识别能力.     

Feedback with carry shift registers synthesis with the Euclidean algorithm

Feedback with carry shift registers (FCSR) were introduced by Klapper and Goresky (1994). They are very similar to classical linear feedback shift registers (LFSR) used in many pseudorandom generators. The main difference is the fact that the elementary additions are not additions modulo 2 but with propagation of carries. The mathematical models for LFSR are equivalently linear recurring sequences over GF(2) or rational series in the set GF(2)[[x]]. For FCSR, the "good" model is the one of rational 2-adic numbers. It is well known, that the series generated by a LFSR can be synthesized by either the Berlekamp-Massey algorithm for binary linear recurring sequences or the extended Euclidean algorithm in the set GF(2)[x] of binary polynomials. Klapper and Goresky (1997) give an algorithm for the FCSR synthesis. This algorithm is similar to those of Berlekamp-Massey and is based on De Weger and Mahler's rational approximation theory. In this correspondence, we prove that it is possible to synthesize the FCSR with the extended Euclidean algorithm in the ring /spl Zopf/ of integers. This algorithm is clearly equivalent to the previous one, however, it is simpler to understand, to implement, and to prove. Our algorithm is still valid in the case of g-adic integers where g is a positive integer. We also give a near-adaptative version of this algorithm.     

Exact thresholds and optimal codes for the binary-symmetric channel and Gallager's decoding algorithm A

We show that for the case of the binary-symmetric channel and Gallager's decoding algorithm A the threshold can, in many cases, be determined analytically. More precisely, we show that the threshold is always upper-bounded by the minimum of (1-/spl lambda//sub 2//spl rho/'(1))/(/spl lambda/'(1)/spl rho/'(1)-/spl lambda//sub 2//spl rho/'(1)) and the smallest positive real root /spl tau/ of a specific polynomial p(x) and we observe that for most cases this bound is tight, i.e., it determines the threshold exactly. We also present optimal degree distributions for a large range of rates. In the case of rate one-half codes, for example, the threshold x/sub 0//sup */ of the optimal degree distribution is given by x/sup *//sub 0//spl sim/0.0513663. Finally, we outline how thresholds of more complicated decoders might be determined analytically.     

The Design of Discrete N-Section and Continuously Tapered Symmetrical Microwave TEM Directional Couplers

A method is presented for the computer-aided design of either N-section discrete or continuously tapered symmetrical microwave couplers. The coupling distribution function k(x) is parametrized in the form k(x, p/spl ovbr/), and a special optimization process (of the generalized Remez type) is used to determine the set of parameters p/spl ovbr/ which produce an optimum power coupling response. Standard parametric forms based on an approximate Fourier analysis as well as more general spline parametric forms for k(x, p/spl ovbr/) are developed and illustrated.     

The empirical distribution of rate-constrained source codes

Let X = (X/sub 1/,...) be a stationary ergodic finite-alphabet source, X/sup n/ denote its first n symbols, and Y/sup n/ be the codeword assigned to X/sup n/ by a lossy source code. The empirical kth-order joint distribution Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rceil/(x/sup k/,y/sup k/) is defined as the frequency of appearances of pairs of k-strings (x/sup k/,y/sup k/) along the pair (X/sup n/,Y/sup n/). Our main interest is in the sample behavior of this (random) distribution. Letting I(Q/sup k/) denote the mutual information I(X/sup k/;Y/sup k/) when (X/sup k/,Y/sup k/)/spl sim/Q/sup k/ we show that for any (sequence of) lossy source code(s) of rate /spl les/R lim sup/sub n/spl rarr//spl infin//(1/k)I(Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rfloor/) /spl les/R+(1/k)H (X/sub 1//sup k/)-H~(X) a.s. where H~(X) denotes the entropy rate of X. This is shown to imply, for a large class of sources including all independent and identically distributed (i.i.d.). sources and all sources satisfying the Shannon lower bound with equality, that for any sequence of codes which is good in the sense of asymptotically attaining a point on the rate distortion curve Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rfloor//spl rArr//sup d/P(X/sup k/,Y~/sup k/) a.s. whenever P(/sub X//sup k//sub ,Y//sup k/) is the unique distribution attaining the minimum in the definition of the kth-order rate distortion function. Consequences of these results include a new proof of Kieffer's sample converse to lossy source coding, as well as performance bounds for compression-based denoisers.     

Polynomials for narrowband signal processing

A novel window function series in the form of two-term polynomials suitable for narrow mainlobe width applications is described. The mainlobe width of the polynomial series can assume values between /spl plusmn/1/T to /spl plusmn/1.5/T, where T is the window duration and the asymptotic decay can be either 6dB/octave or 12dB/octave depending on the criterion imposed. The polynomial series has the narrowest mainlobe width of all the windows reported so far, with 12 dB/octave decay of sidelobes. It is shown that, theoretically, the series achieves the mainlobe width of a rectangular window while maintaining the higher decay of sidelobes.     

On the generators of /spl Zopf//sub 4/ cyclic codes of length 2/sup e/

Results are presented on the generators of ideals in the ring /spl Zopf//sub 4/[x]/(x/sup n/-1). In particular, each ideal (cyclic code) has a unique distinguished set of generators that characterizes any cyclic code. Some results about dual codes are also included.     

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.     

Locally testable cyclic codes

Cyclic linear codes of block length n over a finite field F/sub q/ are linear subspaces of F/sub q//sup n/ that are invariant under a cyclic shift of their coordinates. A family of codes is good if all the codes in the family have constant rate and constant normalized distance (distance divided by block length). It is a long-standing open problem whether there exists a good family of cyclic linear codes. A code C is r-testable if there exists a randomized algorithm which, given a word x/spl isin//sub q//sup n/, adaptively selects r positions, checks the entries of x in the selected positions, and makes a decision (accept or reject x) based on the positions selected and the numbers found, such that 1) if x/spl isin/C then x is surely accepted; ii) if dist(x,C) /spl ges/ /spl epsi/n then x is probably rejected. ("dist" refers to Hamming distance.) A family of codes is locally testable if all members of the family are r-testable for some constant r. This concept arose from holographic proofs/PCP's. Recently it was asked whether there exist good, locally testable families of codes. In this paper the intersection of the two questions stated is addressed. Theorem. There are no good, locally testable families of cyclic codes over any (fixed) finite field. In fact the result is stronger in that it replaces condition ii) of local testability by the condition ii') if dist (x,C) /spl ges/ /spl epsi/n then x has a positive chance of being rejected. The proof involves methods from Galois theory, cyclotomy, and diophantine approximation.     

On the computation of weight enumerators for convolutional codes

Performance bounds for maximum-likelihood decoding of convolutional codes over memoryless channels are commonly measured using the distance weight enumerator T(x,y), also referred to as the transfer function, of the code. This paper presents an efficient iterative method to obtain T(x,y) called the state reduction algorithm. The algorithm is a systematic technique to simplify signal flow graphs that algebraically manipulate the symbolic adjacency matrix associated with the convolutional code. Next, the algorithm is modified to compute the first few terms of the series expansion of T(1,y) and {/spl part/T(x,y)//spl part/x}/sub x=1/ (the distance spectra) without first computing the complete T(x,y).     

On bent and semi-bent quadratic Boolean functions

The maximum-length sequences, also called m-sequences, have received a lot of attention since the late 1960s. In terms of linear-feedback shift register (LFSR) synthesis they are usually generated by certain power polynomials over a finite field and in addition are characterized by a low cross correlation and high nonlinearity. We say that such a sequence is generated by a semi-bent function. Some new families of such function, represented by f(x)=/spl Sigma//sub i=1//sup (n-1)/2/c/sub i/Tr(x(2/sup i/)+1), n odd and c/sub i//spl isin/F/sub 2/, have recently (2002) been introduced by Khoo et al. We first generalize their results to even n. We further investigate the conditions on the choice of c/sub i/ for explicit definitions of new infinite families having three and four trace terms. Also, a class of nonpermutation polynomials whose composition with a quadratic function yields again a quadratic semi-bent function is specified. The treatment of semi-bent functions is then presented in a much wider framework. We show how bent and semi-bent functions are interlinked, that is, the concatenation of two suitably chosen semi-bent functions will yield a bent function and vice versa. Finally, this approach is generalized so that the construction of both bent and semi-bent functions of any degree in certain range for any n/spl ges/7 is presented, n being the number of input variables.     

On acceptance criterion for efficient successiveerrors-and-erasures decoding of Reed-Solomon and BCH codes

We describe an efficient algorithm for successive errors-and-erasures decoding of BCH codes. The decoding algorithm consists of finding all necessary error locator polynomials and errata evaluator polynomials, choosing the most appropriate error locator polynomial and errata evaluator polynomial, using these two polynomials to compute a candidate codeword for the decoder output, and testing the candidate for optimality via an originally developed acceptance criterion. Even in the most stringent case possible, the acceptance criterion is only a little more stringent than Forney's (1966) criterion for generalised minimum distance (GMD) decoding. We present simulation results on the error performance of our decoding algorithm for binary antipodal signals over an AWGN channel and a Rayleigh fading channel. The number of calculations of elements in a finite field that are required by our algorithm is only slightly greater than that required by hard-decision decoding, while the error performance is almost as good as that achieved with GMD decoding. The presented algorithm is also applicable to efficient decoding of product RS codes     

Application of Sampling Theorem to the Synthesis of Transmission Line Tapers and Antenna Radiation Patterns (Correspondence)

In this note it is demonstrated how the sampling theorem may be used to reduce the problems of transmission line taper synthesis and antenna aperture field synthesis to that of optimizing a polynomial. In both cases the problem may be stated mathematically in the following form: find the function g(x) which is zero outside the domain - /spl pi//spl les/x/spl les//spl pi/ that will yield a desired f(u) where f(u) is given by the fourier transform of g(x).     

Connection between primitive generators of GF(2n)

Primitive polynomials over GF(2) are used for generating maximal-length sequences. Powers of a root ? of such a polynomial are delay operators on the generated sequence. Given two primitive polynomials of degree n with ?1, and ?2 their roots, it is shown which parameter is needed in order to find ?1x from ?2x without knowledge of x.     

Closest point search in lattices

In this semitutorial paper, a comprehensive survey of closest point search methods for lattices without a regular structure is presented. The existing search strategies are described in a unified framework, and differences between them are elucidated. An efficient closest point search algorithm, based on the Schnorr-Euchner (1995) variation of the Pohst (1981) method, is implemented. Given an arbitrary point x /spl isin/ /spl Ropf//sup m/ and a generator matrix for a lattice /spl Lambda/, the algorithm computes the point of /spl Lambda/ that is closest to x. The algorithm is shown to be substantially faster than other known methods, by means of a theoretical comparison with the Kannan (1983, 1987) algorithm and an experimental comparison with the Pohst (1981) algorithm and its variants, such as the Viterbo-Boutros (see ibid. vol.45, p.1639-42, 1999) decoder. Modifications of the algorithm are developed to solve a number of related search problems for lattices, such as finding a shortest vector, determining the kissing number, computing the Voronoi (1908)-relevant vectors, and finding a Korkine-Zolotareff (1873) reduced basis.     

一种二进制伪随机序列盲识别方法

针对二进制伪随机序列生成多项式盲识别方法存在的需要预先知道生成多项式阶数、算法容错性能较差且复杂度较高的问题。该文提出首先将接收序列按照估计的生成多项式阶数建立分析矩阵,然后利用伽罗华域高斯列消元的方法识别出接收序列生成多项式的阶数,最后根据生成多项式的阶数构造关于生成多项式系数的方程组。为降低算法复杂度,在有限的多项式库中进行匹配搜索,能够满足该方程组的多项式就是接收序列的生成多项式。仿真结果表明,提出的方法能够区分接收序列是m序列、Gold序列或者是其他二进制伪随机序列,并有效识别其各自的生成多项式,且具有较好的容错性能。