Dentist 2:00On codes with low peak-to-average power ratio for multicode CDMA

Codes which reduce the peak-to-average power (PAPR) in multicode code-division multiple-access (MC-CDMA) communications systems are systematically studied. The problem of designing such codes is reformulated as a new coding-theoretic problem: codes with low PAPR are ones in which the codewords are far from the first-order Reed-Muller code. Bounds on the tradeoff between rate, PAPR, and error-correcting capability of codes for MC-CDMA follow. The connections between the code design problem, bent functions, and algebraic coding theory (in particular, the Kerdock codes and Delsarte-Goethals codes) are exploited to construct code families with flexible parameters for the small values of n of practical interest. In view of their algebraic structure, these codes enjoy efficient encoding and decoding algorithms. The correspondence concludes by listing open problems in algebraic coding theory and Boolean functions motivated by the correspondence.     

The Z4-linearity of Kerdock, Preparata, Goethals, andrelated codes

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson (1967), Kerdock (1972), Preparata (1968), Goethals (1974), and Delsarte-Goethals (1975). It is shown here that all these codes can be very simply constructed as binary images under the Gray map of linear codes over Z₄, the integers mod 4 (although this requires a slight modification of the Preparata and Goethals codes). The construction implies that all these binary codes are distance invariant. Duality in the Z₄ domain implies that the binary images have dual weight distributions. The Kerdock and “Preparata” codes are duals over Z₄-and the Nordstrom-Robinson code is self-dual-which explains why their weight distributions are dual to each other. The Kerdock and “Preparata” codes are Z₄-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z₄, which greatly simplifies encoding and decoding. An algebraic hard-decision decoding algorithm is given for the “Preparata” code and a Hadamard-transform soft-decision decoding algorithm for the I(Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z₄ , but extended Hamming codes of length n⩾32 and the Golay code are not. Using Z₄-linearity, a new family of distance regular graphs are constructed on the cosets of the “Preparata” code     

Constructions of algebraic-geometry codes

Based on curves over finite fields with many rational points, we present two constructions of linear codes from local expansions of functions at a fixed rational point. It turns out that codes from our constructions have the same bound on their parameters as Goppa's (1981) geometry codes. Furthermore, we prove that our second construction is equivalent to Goppa's construction. Finally, an additional construction of linear codes from maximal curves shows that these codes have better parameters than Goppa's geometry codes from maximal curves for a certain interval of parameters     

均衡弹性函数的结构与弹性阶

弹性函数是相关免疫布尔函数的自然推广。本文讨论均衡弹性函数,得到以下结果:给出了均衡弹性函数的一种结构,并因此得到了由均衡(n,m,2t)弹性函数构造均衡(n+1,m,2t+1)弹性函数的非线性方法;证明了均衡线性函数的弹性阶等于对应线性分组码的码字最小重最减1,且弹性阶上确界常常能由非线性函数所达到。     

满足k阶PC(l)的密码函数的新构造

该文基于线性分组码和双射函数,给出了满足七阶PC(l)的均衡相关免疫布尔函数新的构造方法。并据此进一步给出满足七阶PC(l)的(n,m,t)弹性函数的一般构造方法。此外,该文还揭示了这些函数的其它良好的密码学性质,如较高的非线性度、良好的代数次数、良好的构造计数等。     

(n+1,m,2t)均衡弹性函数的非线性构造方法

基于GF(2)n上(n,m,2t-1)均衡弹性函数,运用其对偶分布性质和各分量函数弹性阶的相关特性,得到了(n 1,m,2t)均衡弹性函数的非线性构造方法。这些方法使得自变量的维数与弹性阶同步增长,且函数的代数次数也相应增加,从而避免了线性构造的缺陷。     

环Fp+uFp上的Kerdock码和Preparata码

 Kerdock码和Preparata码是两类著名的二元非线性码,它们比相同条件下的线性码含有更多的码字.Hammons等人在1994年发表的文献中证明了这两类码可视为环Z₄上循环码在Gray映射下的像,从而使得这两类码的编码和译码变得非常简单.环F₂+uF₂是介于环Z₄与域F₄之间的一种四元素环,因此分享了环Z₄与域F₄的一些好的性质,此环上的编码理论研究成为一个新的热点.本文首次将Kerdock码和Preparata码的概念引入到环F_p+uF_p上,证明了它们是一对对偶码;并给出Kerdock码的迹表示;当p=2时,建立了环F₂+uF₂上这两类码与域F₂上的Reed-Muller码之间的联系;并证明了二元一阶Reed-Muller码是环F₂+uF₂上Kerdock码的线性子码的Gray像.     

Cyclic codes over Z4, locator polynomials, and Newton'sidentities

Certain nonlinear binary codes contain more codewords than any comparable linear code presently known. These include the Kerdock (1972) and Preparata (1968) codes that can be very simply constructed as binary images, under the Gray map, of linear codes over Z₄ that are defined by means of parity checks involving Galois rings. This paper describes how Fourier transforms on Galois rings and elementary symmetric functions can be used to derive lower bounds on the minimum distance of such codes. These methods and techniques from algebraic geometry are applied to find the exact minimum distance of a family of Z ₄. Linear codes with length 2^m (m, odd) and size 2(2^m+1-5m-2). The Gray image of the code of length 32 is the best (64, 2³⁷) code that is presently known. This paper also determines the exact minimum Lee distance of the linear codes over Z₄ that are obtained from the extended binary two- and three-error-correcting BCH codes by Hensel lifting. The Gray image of the Hensel lift of the three-error-correcting BCH code of length 32 is the best (64, 2³²) code that is presently known. This code also determines an extremal 32-dimensional even unimodular lattice     

几乎最优弹性plateaued函数的性质和构造

研究了几乎最优plateaued函数的非零线性结构个数, 证明了一个具有奇数个变元的几乎最优plateaued函数要么是没有非零线性结构的plateaued函数, 要么是有一个非零线性结构的部分bent函数; 一个具有偶数个变元的几乎最优plateaued函数的非零线性结构只可能是0, 1, 3个。还给出一种构造几乎最优弹性plateaued函数的方法, 可以使函数无非零线性结构、满足严格雪崩准则、具有良好的全局雪崩特征等。     

A construction of resilient functions with high nonlinearity

We provide a construction technique for multiple-output resilient functions F:F/sub 2//sup n//spl rarr/F/sub 2//sup m/ with high nonlinearity. The construction leads to the problem of finding a set of linear codes with a fixed minimum distance, having the property that the intersection between any two codes is the all-zero codeword only. This problem is considered, and existence results are provided. Moreover, the constructed functions obtain a nonlinearity superior to previous construction methods.     

Resilient functions over finite fields

Resilient functions play an important role in the art of information security. In this correspondence, we discuss the existence, construction, and enumeration of resilient functions over finite fields. We show that, for each finite field GF(q) with q > 3, we can easily construct a large number of (q, n, 1, n - 1) resilient functions, most of which include mixing terms. We give a general structure for (q, m + 1, m, 1) resilient functions, and present an example which is not of this general structure. We prove that (q, m + 2, m, 2) resilient functions exist for any m such that 1 < m < q when q > 2. We prove that (q, m + t, m, t) resilient functions exist for any (m, t) such that 1 < m < q and 2 < t < q when q > 3. By making some simple generalizations of former results, we also provide some new methods for constructing resilient functions.     

Further constructions of resilient Boolean functions with very highnonlinearity

One well-known method of generating key stream sequences for stream ciphers is to combine the outputs of several linear-feedback shift registers (LFSR) using a combining Boolean function. Here we concentrate on the design of good combining Boolean functions. We provide resilient Boolean functions with currently best known nonlinearity. These functions were not known earlier and the issues related to their existence were posed as open questions in the literature. Some of the functions we construct here achieve the provable upper bound on nonlinearity for resilient Boolean functions. Our technique interlinks mathematical results with classical computer search     

一种四元厄米特LCD码与厄米特自正交码的构造方法

有限域上线性互补对偶（LCD）码具有良好的结构和性质,并在双用户加法器信道中得到了广泛的应用.自正交码是编码理论中一类重要的线性码,常被用于构造量子纠错码.本文根据有限域上线性码是厄米特LCD码或厄米特自正交码的判定条件,通过选取合适的定义集,构造出了四类四元厄米特LCD码和厄米特自正交码.同时,本文还研究了这四类线性码的厄米特对偶码,并得到了一些四元最优线性码.     

Systematic authentication codes from highly nonlinear functions

Recently, highly nonlinear functions have been successfully employed to construct authentication codes with and without secrecy. In this paper, we construct four classes of systematic authentication codes from perfect nonlinear functions and almost-perfect nonlinear functions. The systematic authentication codes presented in this paper are either better than existing codes or as good as the best codes known.     

A [55,16,19] binary Goppa code and related codes having largeminimum distance

A [55,16,19] binary Goppa code is used to construct [57,17,17], [58,17,18], [59,17,19], and [60,17,20] codes. The first two codes have smaller redundancy than previously known codes (linear or nonlinear) of the same length and minimum distance. The last two codes have parameters previously attained only by nonlinear codes     

Codes from the Suzuki function field

We construct algebraic geometry (AG) codes from the function field F(2/sup 2n+1/)(x,y)/F(2/sup 2n+1/) defined by y(2/sup 2n+1/)-y=(x(2/sup 2n+/)-x) where n is a positive integer. These codes are supported by two places, and many have parameters that are better than those of any comparable code supported by one place of the same function field. To define such codes, we determine and exploit the structure of the Weierstrass gap set of an arbitrary pair of rational places of F(2/sup 2n+1/)(x,y)/F(2/sup 2n+1/). Moreover, we find some codes over F/sub 8/ with parameters that are better than any known code.     

Parity-check density versus performance of binary linear block codes over memoryless symmetric channels

We derive lower bounds on the density of parity-check matrices of binary linear codes which are used over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are expressed in terms of the gap between the rate of these codes for which reliable communications is achievable and the channel capacity; they are valid for every sequence of binary linear block codes if there exists a decoding algorithm under which the average bit-error probability vanishes. For every MBIOS channel, we construct a sequence of ensembles of regular low-density parity-check (LDPC) codes, so that an upper bound on the asymptotic density of their parity-check matrices scales similarly to the lower bound. The tightness of the lower bound is demonstrated for the binary erasure channel by analyzing a sequence of ensembles of right-regular LDPC codes which was introduced by Shokrollahi, and which is known to achieve the capacity of this channel. Under iterative message-passing decoding, we show that this sequence of ensembles is asymptotically optimal (in a sense to be defined in this paper), strengthening a result of Shokrollahi. Finally, we derive lower bounds on the bit-error probability and on the gap to capacity for binary linear block codes which are represented by bipartite graphs, and study their performance limitations over MBIOS channels. The latter bounds provide a quantitative measure for the number of cycles of bipartite graphs which represent good error-correction codes.     

Nonlinear Product Codes and Their Low Complexity Iterative Decoding

This paper proposes encoding and decoding for nonlinear product codes and investigates the performance of nonlinear product codes. The proposed nonlinear product codes are constructed as N‐dimensional product codes where the constituent codes are nonlinear binary codes derived from the linear codes over higher order alphabets, for example, Preparata or Kerdock codes. The performance and the complexity of the proposed construction are evaluated using the well‐known nonlinear Nordstrom‐Robinson code, which is presented in the generalized array code format with a low complexity trellis. The proposed construction shows the additional coding gain, reduced error floor, and lower implementation complexity. The (64, 24, 12) nonlinear binary product code has an effective gain of about 2.5 dB and 1 dB gain at a BER of 10^?6 when compared to the (64, 15, 16) linear product code and the (64, 24, 10) linear product code, respectively. The (256, 64, 36) nonlinear binary product code composed of two Nordstrom‐Robinson codes has an effective gain of about 0.7 dB at a BER of 10^?5 when compared to the (256, 64, 25) linear product code composed of two (16, 8, 5) quasi‐cyclic codes.     

Linear codes from narrow ray class groups of algebraic curves

By employing the narrow ray class groups of algebraic curves and the Hurwitz genus formula, we construct a class of linear codes over prime fields with reasonable parameters. In particular, we obtain some new codes compared with Brouwer's table.     

Very low rate trellis/Reed-Muller (TRM) codes

This paper considers a technique for very low rate channel coding. The main application for such codes is in spread-spectrum systems where significant bandwidth spreading is possible. New, very low rate binary channel codes based on a combination of a trellis code with a first-order Reed-Muller block code (trellis/Reed-Muller (TRM) codes) are presented. The construction technique for TRM codes, which is considered in this paper, is related to Kerdock (1972) codes. It is shown that these TRM codes provide a better tradeoff between rate and gain than other existing very low rate codes, such as the orthogonal or superorthogonal convolutional codes, and the IS-95 uplink code. Due to their improved performance, TRM codes can significantly increase the bandwidth efficiency of spread-spectrum multiple-access systems