On balanced codes

In a balanced code each codeword contains equally many 1's and 0's. Parallel decoding balanced codes with 2^r (or 2^r -1) information bits are presented, where r is the number of check bits. The 2²-r-1 construction given by D.E. Knuth (ibid., vol.32, no.1, p.51-3, 1986) is improved. The new codes are shown to be optimal when Knuth's complementation method is used     

Optimal biphase sequences with large linear complexity derived fromsequences over Z4

New families of biphase sequences of size 2^r-1+1, r being a positive integer, are derived from families of interleaved maximal-length sequences over Z₄ of period 2(2^r-1). These sequences have applications in code-division spread-spectrum multiuser communication systems. The families satisfy the Sidelnikov bound with equality on &thetas;_max, which denotes the maximum magnitude of the periodic cross-correlation and out-of-phase autocorrelation values. One of the families satisfies the Welch bound on &thetas;_max with equality. The linear complexity and the period of all sequences are equal to r(r+3)/2 and 2(2 ^r-1), respectively, with an exception of the single m-sequence which has linear complexity r and period 2^r-1. Sequence imbalance and correlation distributions are also computed     

Ternary m-sequences with three-valued cross-correlation function:new decimations of Welch and Niho type

We show that the cross correlation between two ternary m-sequences of period 3ⁿ-1 that differ by the decimation d=2·3^m+1, where n=2m+1, takes on three different values. We conjecture the same result for the decimation d=2·3 ^r+1, where n is odd and r is defined by the condition 4r+1≡0 mod n. These two new cases form in a sense ternary counterparts of two previously confirmed binary cases, the conjectures of Welch and Niho (1972)     

High-order spectral-null codes-constructions and bounds

Let 𝒮(n.k) denote the set of all words of length n over the alphabet {+1,-1}, having a k th order spectral-null at zero frequency. A subset of 𝒮(n,k) is a spectral-null code of length n and order k. Upper and lower bounds on the cardinality of 𝒮(n,k) are derived. In particular we prove that (k-1) log₂ (n/k)⩽n-log₂ |𝒮(n,k)|⩽O(2^klog₂n) for infinitely many values of n. On the other hand, we show that 𝒮(n.k) is empty unless n is divisible by 2^m, where m=[log₂k]+1. Furthermore, bounds on the minimum Hamming distance d of 𝒮(n,k) are provided, showing that 2k⩽d⩽k(k-1)+2 for infinitely many n. We also investigate the minimum number of sign changes in a word x∈𝒮(n,k) and provide an equivalent definition of 𝒮(n,k) in terms of the positions of these sign changes. An efficient algorithm for encoding arbitrary information sequences into a second-order spectral-null code of redundancy 3 log₂n+O(log log n) is presented. Furthermore, we prove that the first nonzero moment of any word in 𝒮(n,k) is divisible by k!. This leads to an encoding scheme for spectral-null codes of length n and any fixed order k, with rate approaching unity as n→∞     

Disproof of a conjecture on the existence of balanced optimal covering codes

The minimum number of codewords in a binary code with length n and covering radius R is denoted by K(n,R), and corresponding codes are called optimal. A code with M words is said to be balanced in a given coordinate if the number of 0's and 1's in this coordinate are at least /spl lfloor/M/2/spl rfloor/. A code is balanced if it is balanced in all coordinates. It has been conjectured that among optimal covering codes with given parameters there is at least one balanced code. By using a computational method for classifying covering codes, it is shown that there is no balanced code attaining K(9,1)=62.     

Large families of quaternary sequences with low correlation

A family of quaternary (Z₄-alphabet) sequences of length L=2^r-1, size M⩾L²+3L+2, and maximum nontrivial correlation parameter C_max⩽2√(L+1)+1 is presented. The sequence family always contains the four-phase family 𝒜. When r is odd, it includes the family of binary Gold sequences. The sequence family is easily generated using two shift registers, one binary, the other quaternary. The distribution of correlation values is provided. The construction can be extended to produce a chain of sequence families, with each family in the chain containing the preceding family. This gives the design flexibility with respect to the number of intermittent users that can be supported, in a code-division multiple-access cellular radio system. When r is odd, the sequence families in the chain correspond to shortened Z₄-linear versions of the Delsarte-Goethals codes     

Modular implementation of efficient self-checking checkers for the Berger code

A technique for designing efficient checkers for conventional Berger code is proposed in this paper. The check bits are derived by partitioning the information bits into two blocks, and then using an addition array to sum the number of 1's in each block. The check bit generator circuit uses a specially designed 4-input 1's counter. Two other types of 1's counters having 2 and 3 inputs are also used to realize checkers for variable length information bits. Several variations of 2-bit adder circuits are used to add the number of 1's. The check bit generator circuit uses gates with fan-in of less than or equal to 4 to simplify implementation in CMOS. The technique achieves significant improvement in gate count as well as speed over existing approaches.     

Design and analysis of concatenated coded DS/CDMA systems inasynchronous channels

We propose and analyze concatenated coding schemes for direct-sequence code-division multiple-access (DS/CDMA) systems in asynchronous channels. In the concatenated coding, bandwidth-efficient 2 ^2L-2-state L/(L+1)-rate 2-MTCM with biorthogonal signal constellation is used for the inner code, and (2^L-1,[(2^L -1)/L/2]) RS code is used for the outer code. It is shown that we can get considerable performance gain over the uncoded system without sacrificing the data transmission rate. The proposed system can be used as a coding scheme for reliable and high-speed integrated information services of mobile communication systems     

Majority logic decoding using combinatorial designs (Corresp.)

If the vectors of some constant weight in the dual of a binary linear code support a(nu,b,r,k,lambda)balanced incomplete block design (BIBD), then it is possible to correct[(r + 2 - 1)/2lambda]errors with one-step majority logic decoding. This bound is generalized to the case when the vectors of certain constant weight in the dual code support at-design. With the aid of this bound, the one-step majority logic decoding of the first, second, and third order Reed-Muller codes is examined.     

Construction of fixed-length insertion/deletion correctingrunlength-limited codes

An algorithm is presented for the construction of fixed-length insertion/deletion correcting runlength-limited (RLL) codes. In this construction binary (d,k)-constrained codewords are generated by codewords of a q-ary Lee metric based code. It is shown that this new construction always yields better codes than known constructions. The use of a q-ary Lee (1987) metric code (q odd) is based on the assumption that an error (insertion, deletion, or peak-shift) has maximal size (q-1)/2. It is shown that a decoding algorithm for the Lee metric code can be extended so that it can also be applied to insertion/deletion correcting RLL codes. Furthermore, such an extended algorithm can also correct some error patterns containing errors of size more than (q-1)/2. As a consequence, if s denotes the maximal size of an error, then in some cases the alphabet size of the generating code can be s+1 instead of 2·s+1     

Constructions of almost block-decodable runlength-limited codes

Describes a new technique for constructing fixed-length (d,k) runlength-limited block codes. The new codes are very close to block-decodable codes, as decoding of the retrieved sequence can be accomplished by observing (part of) the received codeword plus a very small part (usually only a single bit) of the previous codeword. The basic idea of the new construction is to uniquely represent each source word by a (d,k) sequence with specific predefined properties, and to construct a bridge of β, 1⩽β⩽d, merging bits between every pair of adjacent words. An essential element of the new coding principle is look ahead. The merging bits are governed by the state of the encoder (the history), the present source word to be translated, and by the upcoming source word. The new constructions have the virtue that only one look-up table is required for encoding and decoding     

On the norm and covering radius of the first-order Reed-Mullercodes

Let ρ(1,m) and N(1,m) be the covering radius and norm of the first-order Reed-Muller code R(1,m), respectively. It is known that ρ(1,2k+1)⩽lower bound [2^2k-2^(2k-1/2)] and N(1,2k+1)⩽2 lower bound [2^2k-2^(2k-1/2)] (k>0). We prove that ρ(1,2k+1)⩽2 lower bound [2^2k-1-2^(2k-3/2)] and N(1,2k+1)⩽4 lower bound [2^2k-1-2^(2k-3/2)] (k>0). We also discuss the connections of the two new bounds with other coding theoretic problems     

Intermediacy Prediction for High Speed Berger Code Checkers

We present an intermediacy prediction method that can be used to designhigh speed checkers for Berger codes, as well as for any other unordered code. In the proposed method, the received information and check bits are processed simultaneously toward an intermediate result. A two-rail code checker is then used to compare the two versions of such an intermediate result. Recall that, in conventional checkers for unordered codes, the received check bits remain idle until the received information bits are converted to the re-generated check bits. Therefore, our proposed intermediacy prediction method allows a checker's speed improvement. We show the application of our method to two well-Bergercode checker architectural solutions: (1) the threshold function based implementation, and (2) the Berger code partitioning design. We have verified that, as expected, the proposed method can improve the detecting speed of these existing solutions with moderate or minimum increase, and sometimes decrease, in hardware complexity.     

Construction of t-EC/AUED codes

A t-EC/AUED code is constructed by appending a single check symbol from an alphabet S to each word of an n-bit binary t-EC code of even weight. Conditions are derived for the construction of S and a procedure is given which, for some values of t, n, leads to codes with fewer check bits than known codes with equivalent properties     

Closed-form designs of complex orthogonal space-time block codes of rates (k+1)/(2k) for 2k-1 or 2k transmit antennas

In this correspondence, we present systematic and closed-form constructions of complex orthogonal space-time block codes from complex orthogonal designs of rates (k+1)/2k for 2k-1 or 2k transmit antennas for any positive integer k.     

Design of Embedded Self-Testing Checkers for t-UED and BUED Codes

In this article we present a new method for designing self-testing checkers for t-UED and BUED codes. The main idea of this method is to map words of the considered code to words of a code of the same type in which the value of t or the number of check bits is reduced and repeating this with the obtained words until a parity code is obtained, or to translate the code words into words of a code for which such a mapping is possible. First we consider Borden codes for t = 2 ^k – 1, Bose, and Bose-Lin codes. The mapping operation is realized by averaging weights and check symbol values of the code words. The resulting checkers have a simple and regular structure. This structure is independent on the set of code words that is provided by the circuit under check. The checkers are very well suited for use as embedded checkers since they are self-testing with respect to single stuck-at faults under very weak assumptions. All three checker types can be tested with 2 or 3 code words. We also propose a novel approach to design checkers for Blaum codes that require much less code word tests than existing solutions.     

4-phase sequences with near-optimum correlation properties

Two families of four-phase sequences are constructed using irreducible polynomials over Z₄. Family A has period L =2^r-1. size L+2. and maximum nontrivial correlation magnitude C_max⩽1+√(L+1), where r is a positive integer. Family B has period L=2(2^r-1). size (L+2)/4. and C_max for complex-valued sequences. Of particular interest, family A has the same size and period as the family of binary Gold sequences. but its maximum nontrivial correlation is smaller by a factor of √2. Since the Gold family for r odd is optimal with respect to the Welch bound restricted to binary sequences, family A is thus superior to the best possible binary design of the same family size. Unlike the Gold design, families A and B are asymptotically optimal whether r is odd or even. Both families are suitable for achieving code-division multiple-access and are easily, implemented using shift registers. The exact distribution of correlation values is given for both families     

A Method of Examining Orchard Codes for Minimum Hamming Distance Five

Orchard codes are linear, systematic tree codes of rate(n - 1)/nand infinite block length. Calculation of parity bits is over prior parity bits, as well as prior information bits. The memory needed to encode is about half that of comparable convolutional self-orthogonal codes. After a brief review of recent work involving two-error-correcting orchard codes [1], [2], the authors present a method of analysis of orchard codes to establish whether minimal distance criteria are met. It is assumed that parity is taken over three bits per track. The code introduced by Scott and Goetschel [1], and a truncated version of the code designed by Shiozaki [2], are then analyzed. New orchard codes, designed on the basis of the analysis method, are presented. The method is extendible to codes designed to correct more than two errors, although extension beyond three errors is computationally intensive.     

删余型Turbo码分量编码器盲识别算法

摘 要:无法获得完整的递归系统卷积码(Recursive System Code,RSC)码字,传统的盲识别方法就不适用于删余型Turbo码的识别。于是该算法在识别序列的构造上进行了改进,针对Turbo码在删余位上的码字与对应的RSC码有所区别的情况,将该位上的码字视为“0”和“1”等概率出现的误码,从而对删余位进行归零处理并选取合适的截取序列进行匹配度计算,根据最后匹配度的总分布情况对删余型Turbo码分量编码器的参数进行识别。仿真结果表明针对码长为256,码率为1/2的删余型Turbo码,在最大误比特率不超过0.033的情况下正确识别率能保持在80%以上。      

On MDS extensions of generalized Reed- Solomon codes

An(n, k, d)linear code overF=GF(q)is said to be {em maximum distance separable} (MDS) ifd = n - k + 1. It is shown that an(n, k, n - k + 1)generalized Reed-Solomon code such that2leq k leq n - lfloor (q - 1)/2 rfloor (k neq 3 {rm if} qis even) can be extended by one digit while preserving the MDS property if and only if the resulting extended code is also a generalized Reed-Solomon code. It follows that a generalized Reed-Solomon code withkin the above range can be {em uniquely} extended to a maximal MDS code of lengthq + 1, and that generalized Reed-Solomon codes of lengthq + 1and dimension2leq k leq lfloor q/2 rfloor + 2 (k neq 3 {rm if} qis even) do not have MDS extensions. Hence, in cases where the(q + 1, k)MDS code is essentially unique,(n, k)MDS codes withn > q + 1do not exist.