Search

We consider a variable-length source coding problem subject to local decodability constraints. In particular, we investigate the blocklength scaling behavior attainable by encodings of $r$ -sparse binary sequences, under the constraint that any source bit can be correctly decoded upon probing at most $d$ codeword bits. We consider both adaptive and non-adaptive access models, and derive upper and lower bounds that often coincide up to constant factors. Such a characterization for the fixed-blocklength analog of our problem, known as the bit probe complexity of static membership, remains unknown despite considerable attention from researchers over the last few decades. We also show that locally decodable schemes for sparse sequences are able to decode 0s (frequent source symbols) of the source with far fewer probes on average than they can decode 1s (infrequent source symbols), thus rigorizing the notion that infrequent symbols require high probe complexity, even on average. Connections to the fixed-blocklength model and to communication complexity are also briefly discussed. [ABSTRACT FROM AUTHOR]

This paper describes new, simple, recursive methods of construction for orientable sequences, i.e. periodic binary sequences in which any $n$ -tuple occurs at most once in a period in either direction. As has been previously described, such sequences have potential applications in automatic position-location systems, where the sequence is encoded onto a surface and a reader needs only examine $n$ consecutive encoded bits to determine its location and orientation on the surface. The only previously described method of construction (due to Dai et al.) is somewhat complex, whereas the new techniques are simple to both describe and implement. The methods of construction cover both the standard ‘infinite periodic’ case, and also the aperiodic, finite sequence, case. Both the new methods build on the Lempel homomorphism, first introduced as a means of recursively generating de Bruijn sequences. [ABSTRACT FROM AUTHOR]

The problem of universally predicting an individual continuous sequence using a deterministic finite-state machine (FSM) is considered. The empirical mean is used as a reference as it is the constant that fits a given sequence within a minimal square error. A reasonable prediction performance is the regret, namely the excess square-error over the reference loss. This paper analyzes the tradeoff between the number of states of the universal FSM and the attainable regret. This paper first studies the case of a small number of states. A class of machines, termed degenerated tracking memory (DTM), is defined and shown to be optimal for small enough number of states. Unfortunately, DTM machines become suboptimal and their regret does not vanish as the number of available states increases. Next, the exponential decaying memory (EDM) machine, previously used for predicting binary sequences, is considered. While the EDM machine has poorer performance for small number of states, it achieves a vanishing regret for large number of states. Following that, an asymptotic lower bound of \(O(k^{-2/3})\) on the achievable regret of any \(k\) -state machine is derived. This bound is attained asymptotically by the EDM machine. Finally, the enhanced exponential decaying memory machine is presented and shown to outperform the EDM machine for any number of states. [ABSTRACT FROM PUBLISHER]

Distributed Arithmetic Coding (DAC) is a practical realization of Slepian-Wolf coding that partitions source space into cosets. Coset Cardinality Spectrum (CCS) is an important property of DAC that was defined in our previous work. In this paper, we give two applications of CCS. First, we find that DAC bitstream is not compact. The rate loss of DAC bitstream is caused by two factors: unequal coset partitioning and bit indivisibility. It is proved that as code length goes to infinity, the expected value of bit-indivisibility rate loss will tend to 0.5 for any irrational Rate Change Step (RCS), where the RCS refers to the rate change when one source bit is flipped. With the help of CCS, the bit-indivisibility rate loss can be compensated to some extend. Especially, for any irrational RCS, as code length goes to infinity, the expected value of the remaining bit-indivisibility rate loss after compensation will tend to about 0.47. The second application of CCS is DAC decoder design. We derive the formula of path metric and find that in the original paper on DAC, the intuitive formula of path metric is not correct. The backward-replacing algorithm is proposed to make full use of memory. Experimental results confirm the correctness of theoretical analyses. [ABSTRACT FROM AUTHOR]

This paper considers the problem of variable-length coding over a discrete memoryless channel with noiseless feedback. This paper provides a stochastic control view of the problem whose solution is analyzed via a newly proposed symmetrized divergence, termed extrinsic Jensen–Shannon (EJS) divergence. It is shown that strictly positive lower bounds on EJS divergence provide nonasymptotic upper bounds on the expected code length. This paper presents strictly positive lower bounds on EJS divergence, and hence nonasymptotic upper bounds on the expected code length, for the following two coding schemes: 1) variable-length posterior matching and 2) MaxEJS coding scheme that is based on a greedy maximization of the EJS divergence. As an asymptotic corollary of the main results, this paper also provides a rate–reliability test. Variable-length coding schemes that satisfy the condition(s) of the test for parameters $R$ and $E$ are guaranteed to achieve a rate $R$ and an error exponent $E$ . The results are specialized for posterior matching and MaxEJS to obtain deterministic one-phase coding schemes achieving capacity and optimal error exponent. For the special case of symmetric binary-input channels, simpler deterministic schemes of optimal performance are proposed and analyzed. [ABSTRACT FROM AUTHOR]

In general, it is hard to find the cross correlation distribution between two sequences. In particular, there are only few cases that the cross correlation is three-valued. In this paper, new pairs of binary sequences with three cross correlation values are presented. These two sequences have different lengths: 2^2k-1 and 3(2^k-1) , respectively. We determine the cross correlation distribution between these two sequences. We also give the possible correlation values for the shift decimated sequences. The magnitude of cross correlation values is shown to be low. The techniques presented in this paper may be useful to handle other similar cases. [ABSTRACT FROM PUBLISHER]

Pursley and Sarwate established a lower bound on a combined measure of autocorrelation and crosscorrelation for a pair $(f,g)$ of binary sequences (i.e., sequences with terms in {−1, 1}). If $f$ is a nonzero sequence, then its autocorrelation demerit factor, $\text {ADF}(f)$ , is the sum of the squared magnitudes of the aperiodic autocorrelation values over all nonzero shifts for the sequence obtained by normalizing $f$ to have unit Euclidean norm. If $(f,g)$ is a pair of nonzero sequences, then their crosscorrelation demerit factor, $\text {CDF}(f,g)$ , is the sum of the squared magnitudes of the aperiodic crosscorrelation values over all shifts for the sequences obtained by normalizing both $f$ and $g$ to have unit Euclidean norm. Pursley and Sarwate showed that for binary sequences, the sum of $\text {CDF}(f,g)$ and the geometric mean of $\text {ADF}(f)$ and $\text {ADF}{(g)}$ must be at least 1. For randomly selected pairs of long binary sequences, this quantity is typically around 2. In this paper, we show that Pursley and Sarwate’s bound is met for binary sequences precisely when $(f,g)$ is a Golay complementary pair. We also prove a generalization of this result for sequences whose terms are arbitrary complex numbers. We investigate constructions that produce infinite families of Golay complementary pairs, and compute the asymptotic values of autocorrelation and crosscorrelation demerit factors for such families. [ABSTRACT FROM AUTHOR]

Pairs of binary sequences formed using linear combinations of multiplicative characters of finite fields are exhibited that, when compared with a random sequence pairs, simultaneously achieve significantly lower mean square autocorrelation values (for each sequence in the pair) and significantly lower mean square crosscorrelation values. If we define crosscorrelation merit factor analogously to the usual merit factor for autocorrelation, and if we define demerit factor as the reciprocal of merit factor, then randomly selected binary sequence pairs are known to have an average crosscorrelation demerit factor of 1. Our constructions provide sequence pairs with a crosscorrelation demerit factor significantly less than 1, and at the same time, the autocorrelation demerit factors of the individual sequences can also be made significantly less than 1 (which also indicates better than average performance). The sequence pairs studied here provide combinations of autocorrelation and crosscorrelation performance that are not achievable using sequences formed from single characters, such as maximal linear recursive sequences (m-sequences) and Legendre sequences. In this paper, exact asymptotic formulae are proved for the autocorrelation and crosscorrelation merit factors of sequence pairs formed using linear combinations of multiplicative characters. Data is presented that shows that the asymptotic behavior is closely approximated by sequences of modest length. [ABSTRACT FROM PUBLISHER]

Due to wide applications of binary sequences with a low correlation to communications, various constructions of such sequences have been proposed in the literature. Many efforts have been made to construct good binary sequences with various lengths. However, most of the known constructions make use of the multiplicative cyclic group structure of finite field $\mathbb {F}_{2^{n}}$ for a positive integer $n$. It is often overlooked in this community that all $2^{n}+1$ rational places (including “the place at infinity”) of the rational function field over $\mathbb {F}_{2^{n}}$ form a cyclic structure under an automorphism of order $2^{n}+1$. In this paper, we make use of this cyclic structure to provide an explicit construction of binary sequences with a low correlation of length $2^{n}+1$ via cyclotomic function fields over $\mathbb {F}_{2^{n}}$. Each family of our sequences has size $2^{n}-1$ and its correlation is upper bounded by $\lfloor 2^{(n+2)/2}\rfloor $. To the best of our knowledge, this is the first construction of binary sequences with a low correlation of length $2^{n}+1$. Moreover, our sequences can be constructed explicitly and have competitive parameters. In particular, compared with the Gold sequences of length $2^{n}-1$ for even $n$ , our sequences have a smaller correlation and a larger length although the family size of our sequences is slightly smaller. [ABSTRACT FROM AUTHOR]

This paper studies properties of binary runlength-limited sequences with additional constraints on their Hamming weight and/or their number of runs of identical symbols. An algebraic and a probabilistic (entropic) characterization of the exponential growth rate of the number of such sequences, i.e., their information capacity, are obtained by using the methods of multivariate analytic combinatorics, and properties of the capacity as a function of its parameters are stated. The second-order term in the asymptotic expansion of the rate of these sequences is also given, and the typical values of the relevant quantities are derived. Several applications of the results are illustrated, including bounds on codes for weight-preserving and run-preserving channels (e.g., the run-preserving insertion-deletion channel), a sphere-packing bound for channels with sparse error patterns, and the asymptotics of constant-weight sub-block constrained sequences. In addition, the asymptotics of a closely related notion— $q$ -ary sequences with fixed Manhattan weight—is briefly discussed, and an application in coding for molecular timing channels is illustrated. [ABSTRACT FROM AUTHOR]

The noise model of deletions poses significant challenges in coding theory, with basic questions like the capacity of the binary deletion channel still being open. In this paper, we study the harder model of worst case deletions, with a focus on constructing efficiently decodable codes for the two extreme regimes of high-noise and high-rate. Specifically, we construct polynomial-time decodable codes with the following tradeoffs (for any \varepsilon > 0 ): 1) codes that can correct a fraction 1- \varepsilon of deletions with rate \mathop \mathrm poly\nolimits ( \varepsilon ) over an alphabet of size \mathop \mathrm poly\nolimits (1/ \varepsilon ) ; 2) binary codes of rate 1-\tilde O(\sqrt \varepsilon ) that can correct a fraction $ \varepsilon $ of deletions; and 3) Binary codes that can be list-decoded from a fraction (1/2- \varepsilon )$ of deletions with rate \mathop {\mathrm {poly}}\nolimits ( \varepsilon ) . This paper gives the first efficient constructions which meet the qualitative goals of correcting a deletion fraction approaching 1 over bounded alphabets, and correcting a constant fraction of bit deletions with rate approaching 1 over a fixed alphabet. The above-mentioned results bring our understanding of deletion code constructions in these regimes to a similar level as worst case errors. [ABSTRACT FROM PUBLISHER]

This paper studies problems in data reconstruction, an important area with numerous applications. In particular, we examine the reconstruction of binary and nonbinary sequences from synchronization (insertion/deletion-correcting) codes. These sequences have been corrupted by a fixed number of symbol insertions (larger than the minimum edit distance of the code), yielding a number of distinct traces to be used for reconstruction. We wish to know the minimum number of traces needed for exact reconstruction. This is a general version of a problem tackled by Levenshtein for uncoded sequences. We introduce an exact formula for the maximum number of common supersequences shared by sequences at a certain edit distance, yielding an upper bound on the number of distinct traces necessary to guarantee exact reconstruction. Without specific knowledge of the code words, this upper bound is tight. We apply our results to the famous single deletion/insertion-correcting Varshamov–Tenengolts (VT) codes and show that a significant number of VT code word pairs achieve the worst case number of outputs needed for exact reconstruction. We also consider extensions to other channels, such as adversarial deletion and insertion/deletion channels and probabilistic channels. [ABSTRACT FROM PUBLISHER]

Given a binary sequence with length $n$ , determining its minimal rational fraction representation (MRFR) has important applications in the design and cryptanalysis of stream ciphers. There are many studies of this problem since Klapper and Goresky first introduced an adaptive rational approximation algorithm with a time complexity of $O(n^{2}\log n\log \log n)$. In this paper, we revisit this problem by considering both adaptive and non-adaptive efficient algorithms. Compared with the state-of-art methods, we make several contributions to the problem of finding MRFR. Firstly, we find a general and precise recursive relationship between the minimal bases for two adjacent lattices generated by successive truncation sequences. This enables us to improve the currently fastest adaptive algorithm proposed by Li et al.. Secondly, by optimizing a time-consuming step of the well-known Lagrange reduction algorithm for 2-dimensional lattices, we obtain a non-adaptive, and yet practically faster MRFR-solving algorithm named global Euclidean algorithm. Thirdly, we identify theoretical flaws on some non-adaptive methods in the literature by counter-examples and correct the problems by designing modified Euclidean algorithm named partial Euclidean algorithm. Meanwhile, we further reduce the time complexity of existing algorithm from $O(n^{2})$ to $O(n\log ^{2}n\log \log n)$ by invoking the half-gcd algorithm. We also conduct a comprehensive experimental comparative analysis on the above algorithms to validate our theoretical analysis. [ABSTRACT FROM AUTHOR]

Consider two remote nodes (encoder and decoder), each with a binary sequence. The encoder’s sequence X differs from the decoder’s sequence Y by a small number of edits (deletions and insertions). The goal is to construct a message M, to be sent via a one-way error free link, such that the decoder can reconstruct X using M and Y. In this paper, we devise a coding scheme for this one-way synchronization model. The scheme is based on multiple layers of Varshamov-Tenengolts (VT) codes combined with off-the-shelf linear error-correcting codes, and uses a list decoder. We bound the expected list size of the decoder under certain assumptions, and validate its performance via numerical simulations. We also consider an alternative decoder that uses only the constraints from the VT codes (i.e., does not require a linear code), and has a smaller redundancy at the expense of a slightly larger average list size. [ABSTRACT FROM AUTHOR]

In this paper, we present some construction methods for punctured binary array/sequence pairs (PBAPs/PBSPs) with ideal/optimal correlation constant using their algebraic counterparts punctured difference set pairs in Abelian groups. In addition, we provide new construction techniques of PBAPs/PBSPs via geometry and also using the embeddable sequence pairs of smaller lengths to obtain larger ones. PBAPs/PBSPs find a plethora of applications in radar systems, cryptography, frame synchronization, mismatched filtering, and various other engineering fields. [ABSTRACT FROM AUTHOR]

The goal of this paper is to present constructions of high-rate nonbinary write-once memory (WOM) codes for multilevel flash memories. The constructions provided here are all based on the basic idea of mapping high-rate binary codebooks to nonbinary codebooks. The proposed codes maintain the same length and encoding complexity as their underlying binary constituents. We begin by presenting some elementary, yet rate-efficient constructions. Afterward, we consider a high-rate two-write WOM-code defined over an alphabet of size four. In addition, we consider the application of our constructions to the creation of fixed-rate WOM codes. The constructions presented in this paper improve upon the best-known code constructions for certain code lengths. [ABSTRACT FROM AUTHOR]

The Johnson-type upper bound on the maximum size of a code of length n , distance d=2w-1 , and constant composition \overline w is \lfloor \dfrac \vphantom R^.nw1\rfloor , where w is the total weight and w_{1} is the largest component of {\overline {w}} . Recently, Chee et al. proved that this upper bound can be achieved for all constant-composition codes of sufficiently large lengths. Let Nccc({\overline {w}}) be the smallest such length. The determination of Nccc({\overline {w}}) is trivial for binary codes. This paper provides a lower bound on Nccc({\overline {w}}) , which is shown to be tight for all ternary and quaternary codes by giving new combinatorial constructions. Consequently, by the refining method, we determine the values of Nccc({\overline {w}}) , for all $q$ -ary constant-composition codes, provided that 3w_{1}\geq w with finite possible exceptions. [ABSTRACT FROM AUTHOR]

Levenshtein improved the famous Welch bound on aperiodic correlation for binary sequences by utilizing some properties of the weighted mean square aperiodic correlation. Following Levenshtein's idea, a new correlation lower bound for quasi-complementary sequence sets (QCSSs) over the complex roots of unity is proposed in this paper. The derived lower bound is shown to be tighter than the Welch bound for QCSSs when the set size is greater than some value. The conditions for meeting the new bound with equality are also investigated. [ABSTRACT FROM PUBLISHER]

In this paper, we revisit a method to produce binary sequences using the most significant bit map from \bf Z4 to the binary field. This method is useful for the construction of binary sequences with low correlation and large family size. There may be more cases where starting with \bf Z4 could help researchers design new low correlation sequences for code-division multiple access application. [ABSTRACT FROM AUTHOR]

In this paper, we give three new constructions of binary sequences of period 4N with optimal autocorrelation value or optimal autocorrelation magnitude using N x 4 interleaved sequences. Yu and Gong recently found any binary sequence of period 4N with optimal autocorrelation value constructed from an almost difference set by Arasu et al. is an N x 4 interleaved sequence for which all four columns in its N x 4 array are shift equivalent up to the complement. We found that it is not necessary that four columns are shift equivalent. Instead, it could be a pair of related sequences together with their shifts as the column sequences. The first construction is to use a generalized GMW sequence of period N = 22k - 1 and its modified version, the second construction is to use a twin prime sequence of length N = p(p + 2) and its modified version, and the third construction, a pair of Legendre sequences of period N = p (p odd prime) with their respective first terms complementary (the 2-level autocorrelation property is not needed for the Legendre sequence). The comparison with the known constructions are given. For the new sequences with optimal autocorrelation value, their corresponding new almost difference sets are also derived. [ABSTRACT FROM AUTHOR]

This paper investigates basic trade-offs between energy and delay in wireless communication systems using finite blocklength theory. We first assume that data arrive in constant stream of bits, which are put into packets and transmitted over a communications link. Our results show that depending on exactly how energy is measured, in general energy depends on $\sqrt {d^{-1}}$ or $\sqrt {d^{-1}\log {d}}$ , where $d$ is the delay. This means that the energy decreases quite slowly with increasing delay. Furthermore, to approach the absolute minimum of −1.59 dB on energy, bandwidth has to increase very rapidly, much more than what is predicted by infinite blocklength theory. We then consider the scenario when data arrive stochastically in packets and can be queued. We devise a scheduling algorithm based on finite blocklength theory and develop bounds for the energy-delay performance. Our results again show that the energy decreases quite slowly with increasing delay. [ABSTRACT FROM AUTHOR]

The error linear complexity spectrum constitutes a well-known cryptographic criterion for sequences, indicating how the linear complexity of the sequence decreases as the number of bits allowed to be modified per period increases. In this paper, via defining an association between $2^{n}$ -periodic binary sequences and Boolean functions on $n$ variables, it is shown that the error linear complexity spectrum also provides useful cryptographic information for the corresponding Boolean function $f$ - namely, it yields an upper bound on the minimum Hamming distance between $f$ and the set of functions depending on fewer number of variables. Therefore, the prominent Lauder-Paterson algorithm for computing the error linear complexity spectrum of a sequence may also be used for efficiently determining approximations of a Boolean function that depend on fewer number of variables. Moreover, it is also shown that, through this approach, low-degree approximations of a Boolean function can be also obtained in an efficient way. [ABSTRACT FROM AUTHOR]

Mrs. Gerber’s Lemma lower bounds the entropy at the output of a binary symmetric channel in terms of the entropy of the input process. In this paper, we lower bound the output entropy via a different measure of input uncertainty, pertaining to the minimum mean squared error prediction cost of the input process. We show that in many cases our bound is tighter than the one obtained from Mrs. Gerber’s Lemma. As an application, we evaluate the bound for binary hidden Markov processes, and obtain new estimates for the entropy rate. [ABSTRACT FROM PUBLISHER]

In this paper, a new class of (N,K) near-optimal partial Hadamard codebooks is proposed. The construction of the proposed codebooks from Hadamard matrices is based on binary row selection sequences, which are generated by quadratic residue mapping of p -ary m -sequences. The proposed codebooks have parameters and K=({p-1}/{2p})(N+\sqrt{N})+1 for an odd prime p$ and an even positive integer $n$ . We prove that the maximum magnitude of inner products between the code vectors of the proposed codebooks asymptotically achieves the Welch bound equality for sufficiently large $p$ and derive their inner product distribution. [ABSTRACT FROM PUBLISHER]

Binary sequences with low odd correlation have important applications in communication systems to reduce interference. In this paper, using the interleaving technique, we present a generic connection between binary sequences with low odd correlation and quaternary sequences with low even correlation. As a result, some new binary sequences with optimal odd auto-correlation magnitude are obtained. Besides, two sets consisting of 2^n+1 binary sequences of period 2(2^n-1) with the maximum odd correlation magnitude 2^((n+1)/ 2)+2 are derived, which are the first two optimal classes of binary sequence sets achieving the Sarwate bound on the odd correlation magnitude in the literature. [ABSTRACT FROM PUBLISHER]

The objects of study of this paper are communication channels in which the dominant type of noise are symbol shifts, the main motivating examples being timing and bit-shift channels. Two channel models are introduced and their zero-error capacities and zero-error-detection capacities determined by explicit constructions of optimal codes. Model A can be informally described as follows: 1) The information is stored in an $n $ -cell register, where each cell is either empty or contains a particle of one of $P $ possible types and 2) due to the imperfections of the device each of the particles may be shifted several cells away from its original position over time. Model B is an abstraction of a single-server queue: 1) The transmitter sends packets from a $P $ -ary alphabet through a queuing system with an infinite buffer and a first-in-first-out service procedure and 2) each packet is being processed by the server for a random number of time slots. More general models including additional types of noise that the particles/packets can experience are also studied, as are the continuous-time versions of these problems. [ABSTRACT FROM AUTHOR]

We study the tandem duplication distance between binary sequences and their roots. In other words, the quantity of interest is the number of tandem duplication operations of the form x = {a} {b} {c} \to {y} = {a} {b} {b} {c} , where x and y are sequences and a , b , and c are their substrings, needed to generate a binary sequence of length $n$ starting from a square-free sequence from the set {0, 1, 01, 10, 010, 101}. This problem is a restricted case of finding the duplication/deduplication distance between two sequences, defined as the minimum number of duplication and deduplication operations required to transform one sequence to the other. We consider both exact and approximate tandem duplications. For exact duplication, denoting the maximum distance to the root of a sequence of length $n$ by $f(n)$ , we prove that $f(n)=\Theta (n)$ . For the case of approximate duplication, where a $\beta $ -fraction of symbols may be duplicated incorrectly, we show that the maximum distance has a sharp transition from linear in $n$ to logarithmic at $\beta =1/2$ . We also study the duplication distance to the root for the set of sequences arising from a given root and for special classes of sequences, namely, the De Bruijn sequences, the Thue–Morse sequence, and the Fibonacci words. The problem is motivated by genomic tandem duplication mutations and the smallest number of tandem duplication events required to generate a given biological sequence. [ABSTRACT FROM AUTHOR]

A pair of binary sequences is generalized from the concept of a two-level autocorrelation function of a single binary sequence. In this paper, new families of binary sequence pairs with period N=np, where \gcd(n,p)=1, and optimal correlation values -1 are constructed, as well as new families of binary sequence pairs with three-level correlation and period N\equiv 0(mod\;4). For the new binary sequence pairs with optimal correlation values, their corresponding new difference set pairs and almost difference set pairs are also derived. [ABSTRACT FROM PUBLISHER]

Let p=ef+1 be an odd prime for some e and f, and let Fp be the finite field with p elements. In this paper, we explicitly describe the trace representations of the binary characteristic sequences (of period p) of all the cyclic difference sets D which are some union of cosets of eth powers He in Fp^{\ast }(\triangleq Fp\backslash \{0\}) for e\leq 12. For this, we define eth power residue sequences of period p, which include all the binary characteristic sequences mentioned above as special cases, and reduce the problem of determining their trace representations to that of determining the values of the generating polynomials of cosets of He in Fp^{\ast } at some primitive pth root of unity, and some properties of these values are investigated. Based on these properties, the trace representation and linear complexity not only of the characteristic sequences of all the known eth residue difference sets, but of all the sixth power residue sequences are determined. Furthermore, we have determined the linear complexity of a nonconstant eth power residue sequence for any e to be either p-1 or p whenever (e,(p-1)/n)=1, where n is the order of 2 mod p. [ABSTRACT FROM PUBLISHER]

Sequences with optimal autocorrelation property are needed in certain communication systems and cryptography. In this paper, a construction of balanced quaternary sequences with period N \equiv 2 (mod\ 4) and optimal autocorrelation value and a construction of almost balanced binary sequences with period N \equiv 0 (mod\ 4) and optimal autocorrelation value are presented. Both constructions are a generalization of earlier ones. [ABSTRACT FROM AUTHOR]

This paper studies the error linear complexity spectrum of binary sequences with period 2n. A precise categorization of those sequences having two distinct critical points in their spectra, as well as an enumeration of these sequences, is given. An upper bound on the maximum number of distinct critical points that the spectrum of a sequence can have is proved, and a construction which yields a lower bound on this number is given. In the process simpler proofs of some known results on the linear complexity and k-error linear complexity of sequences with period 2n are provided. [ABSTRACT FROM AUTHOR]

Given a computable probability measure $P$ over natural numbers or infinite binary sequences, there is no computable, randomized method that can produce an arbitrarily large sample such that none of its members are outliers of $P$. In addition, given a binary predicate $\gamma $ , the length of the smallest program that computes a complete extension of $\gamma $ is less than the size of the domain of $\gamma $ plus the amount of information that $\gamma $ has with the halting sequence. [ABSTRACT FROM AUTHOR]

Cross-bifix-free sets are sets of words such that no prefix of any word is a suffix of any other word. In this paper, we introduce a general constructive method for the sets of cross-bifix-free binary words of fixed length. It enables us to determine a cross-bifix-free words subset which has the property to be non-expandable. [ABSTRACT FROM PUBLISHER]

The known families of binary sequences having asymptotic merit factor 6.0 are modifications to the families of Legendre sequences and Jacobi sequences. In this paper, we show that at N=pq, there are many suitable modifications other than the Jacobi or modified Jacobi sequences. Furthermore, we will give three new modifications to the character sequences of length N=pq. Based on these new modifications, for any pair of large p and q, we can construct a binary sequence of length 2pq so that such families of sequences have asymptotic merit factor 6.0 without cyclic shifting of the base sequences. [ABSTRACT FROM AUTHOR]

We analyze a class of high performance, low decoding-data-flow error-correcting codes suitable for high bit-rate optical-fiber communication systems. A spatially coupled split-component ensemble is defined, generalizing from the most important codes of this class, staircase codes and braided block codes, and preserving a deterministic partitioning of component-code bits over code blocks. Our analysis focuses on low-complexity iterative algebraic decoding, which, for the binary erasure channel, is equivalent to a generalization of the peeling decoder. Using the differential equation method, we derive a vector recursion that tracks the expected residual graph evolution throughout the decoding process. The threshold of the recursion, for asymptotically long component codes, is found using potential function analysis. We generalize the analysis to mixture ensembles consisting of more than one type of component code. We give an example of a mixture ensemble consisting of two component codes, which has better performance than spatially-coupled split-component ensembles consisting of only one component code. The analysis extends to the binary symmetric channel by assuming miscorrection-free component-code decoding. Simple upper bounds on the number of errors correctable by the ensemble are derived. Finally, we analyze the threshold of spatially coupled split-component ensembles under beyond bounded-distance component decoding. [ABSTRACT FROM PUBLISHER]

The (classical) crosscorrelation is an important measure of pseudorandomness of two binary sequences for applications in communications. The arithmetic crosscorrelation is another figure of merit introduced by Goresky and Klapper generalizing Mandelbaum’s arithmetic autocorrelation. First we observe that the arithmetic crosscorrelation is constant for two binary sequences of coprime periods, which complements the analogous result for the classical crosscorrelation. Then we prove upper bounds for the constant arithmetic crosscorrelation of two Legendre sequences of different periods and of two binary $m$ -sequences of coprime periods, respectively. [ABSTRACT FROM AUTHOR]

The DNA storage channel is considered, in which the $M$ Deoxyribonucleic acid (DNA) molecules comprising each codeword are stored without order, sampled $N$ times with replacement, and then sequenced over a discrete memoryless channel. For a constant coverage depth $M/N$ and molecule length scaling $\Theta (\log M)$ , lower (achievability) and upper (converse) bounds on the capacity of the channel, as well as a lower (achievability) bound on the reliability function of the channel are provided. Both the lower and upper bounds on the capacity generalize a bound which was previously known to hold only for the binary symmetric sequencing channel, and only under certain restrictions on the molecule length scaling and the crossover probability parameters. When specified to binary symmetric sequencing channel, these restrictions are completely removed for the lower bound and are significantly relaxed for the upper bound in the high-noise regime. The lower bound on the reliability function is achieved under a universal decoder, and reveals that the dominant error event is that of outage – the event in which the capacity of the channel induced by the DNA molecule sampling operation does not support the target rate. [ABSTRACT FROM AUTHOR]

Sequences with low aperiodic autocorrelation and crosscorrelation are used in communications and remote sensing. Golay and Shapiro independently devised a recursive construction that produces families of complementary pairs of binary sequences. In the simplest case, the construction produces the Rudin–Shapiro sequences, and in general it produces what we call Golay–Rudin–Shapiro sequences. Calculations by Littlewood show that the Rudin–Shapiro sequences have low mean square autocorrelation. A sequence’s peak sidelobe level is its largest magnitude of autocorrelation over all nonzero shifts. Høholdt, Jensen, and Justesen showed that there is some undetermined positive constant $A$ such that the peak sidelobe level of a Rudin–Shapiro sequence of length $2^{n}$ is bounded above by $A(1.842626\ldots)^{n}$ , where $1.842626\ldots $ is the positive real root of $X^{4}-3 X-6$. We show that the peak sidelobe level is bounded above by $5(1.658967\ldots)^{n-4}$ , where $1.658967\ldots $ is the real root of $X^{3}+X^{2}-2 X-4$. Any exponential bound with lower base will fail to be true for almost all $n$ , and any bound with the same base but a lower constant prefactor will fail to be true for at least one $n$. We provide a similar bound on the peak crosscorrelation (largest magnitude of crosscorrelation over all shifts) between the sequences in each Rudin–Shapiro pair. The methods that we use generalize to all families of complementary pairs produced by the Golay–Rudin–Shapiro recursion, for which we obtain bounds on the peak sidelobe level and peak crosscorrelation with the same exponential growth rate as we obtain for the original Rudin–Shapiro sequences. [ABSTRACT FROM AUTHOR]

We propose coding techniques that simultaneously limit the length of homopolymers runs, ensure the GC-content constraint, and are capable of correcting a single edit error in strands of nucleotides in DNA-based data storage systems. In particular, for given ℓ, ε > 0, we propose simple and efficient encoders/decoders that transform binary sequences into DNA base sequences (codewords), namely sequences of the symbols A, T, C and G, that satisfy all of the following properties: 1) runlength constraint: the maximum homopolymer run in each codeword is at most ℓ ; 2) GC-content constraint: the GC-content of each codeword is within [0.5−ε, 0.5 + ε] ; 3) error-correction: each codeword is capable of correcting a single deletion, or single insertion, or single substitution error. While various combinations of these properties have been considered in the literature, this work provides generalizations of codes constructions that satisfy all the properties with arbitrary parameters of ℓ and ε. Furthermore, for practical values of ℓ and ε, we show that our encoders achieve higher rates than existing results in the literature and approach capacity. Our methods have low encoding/decoding complexity and limited error propagation. [ABSTRACT FROM AUTHOR]

In literature, there are several methods to construct Gold sequences. One of the constructions is via the trace function from extension field of $\mathbb {F}_{2}$. Estimation of correlation of this construction is based on number of rational points of elliptic curves. In this article, we generalize this construction from finite fields of even characteristic to odd characteristics by using multiplicative quadratic character. Again, estimation of correlation of this construction is based on number of rational points of elliptic curves. Thus, we obtain binary sequences which have more flexibility on length while still possessing low correlation property. Moreover, some of the sequences are optimally balanced. [ABSTRACT FROM AUTHOR]

Borwein and Mossinghoff investigated the Rudin-Shapiro-like sequences, which are infinite families of binary sequences, usually represented as polynomials. Each family of Rudin-Shapiro-like sequences is obtained from a starting sequence (which we call the seed) by a recursive construction that doubles the length of the sequence at each step, and many sequences produced in this manner have exceptionally low aperiodic autocorrelation. Borwein and Mossinghoff showed that the asymptotic autocorrelation merit factor for any such family is at most 3, and found the seeds of length 40 or less that produce the maximum asymptotic merit factor of 3. The definition of Rudin-Shapiro-like sequences was generalized by Katz, Lee, and Trunov to include sequences with arbitrary complex coefficients, among which are families of low autocorrelation polyphase sequences. Katz, Lee, and Trunov proved that the maximum asymptotic merit factor is also 3 for this larger class. Here we show that a family of such Rudin-Shapiro-like sequences achieves asymptotic merit factor 3 if and only if the seed is either of length 1 or is the interleaving of a pair of Golay complementary sequences. For small seed lengths where this is not possible, the optimal seeds are interleavings of pairs that are as close as possible to being complementary pairs, and the idea of an almost-complementary pair makes sense of remarkable patterns in previously unexplained data on optimal seeds for binary Rudin-Shapiro-like sequences. [ABSTRACT FROM AUTHOR]

We first introduce a family of binary $pq^{2}$ -periodic sequences based on the Euler quotients modulo $pq$ , where $p$ and $q$ are two distinct odd primes and $p$ divides $q-1$. The minimal polynomials and linear complexities are determined for the proposed sequences provided that $2^{q-1} \not \equiv 1 \mod {q^{2}}$. The results show that the proposed sequences have high linear complexities. [ABSTRACT FROM AUTHOR]

We determine the 2-adic complexity of the Ding-Helleseth-Martinsen (DHM) binary sequences by using cyclotomic numbers of order four, “Gauss periods” and “quadratic Gauss sums” on finite field $\mathbb {F}_{{q}}$ and valued in $\mathbb {Z}_{2^{{N}}-1}$ , where ${q} \equiv 5\pmod 8$ is a prime number and ${N}=2{q}$ is the period of the DHM sequences. [ABSTRACT FROM AUTHOR]

Using the method for constructing binary self-dual codes with an automorphism of order square of a prime number, we have classified all binary self-dual codes with length 76 having minimum weight $d=14$ via automorphism of order 9. Up to equivalence, there are six self-dual [76, 38, 14] codes with an automorphism of type 9-(8, 0, 4). All codes obtained have new values of the parameter in their weight enumerator, thus more than doubling the number of known values. [ABSTRACT FROM AUTHOR]

We analyze the connection between the autocorrelation of a binary sequence and its run structure given by the run length encoding. We show that both the periodic and the aperiodic autocorrelation of a binary sequence can be formulated in terms of the run structure. The run structure is given by the consecutive runs of the sequence. Let C=(C0,C1,\ldots,Cn) denote the autocorrelation vector of a binary sequence and \triangle the difference operator. We prove that the kth component of \triangle ^2(C) can be directly calculated by using the consecutive runs of total length k. In particular, this shows that the kth autocorrelation is already determined by all consecutive runs of total length l< k. In the aperiodic case, we show how the run vector R can be efficiently calculated and give a characterization of skew-symmetric sequences in terms of their run length encoding. [ABSTRACT FROM AUTHOR]

The characterization of a binary function by partial frequency information is considered. We show that it is possible to reconstruct binary signals from incomplete frequency measurements via the solution of a simple linear optimization problem. We further prove that if a binary function is spatially structured (e.g., a general black-white image or an indicator function of a shape), then it can be recovered from very few low frequency measurements in general. These results would lead to efficient methods of sensing, characterizing and recovering a binary signal or a shape as well as other applications like deconvolution of binary functions blurred by a low-pass filter. Numerical results are provided to demonstrate the theoretical arguments. [ABSTRACT FROM PUBLISHER]

The problem of constructing a binary machine with the minimum number of stages generating a given binary sequence is addressed. Binary machines are a generalization of nonlinear feedback shift registers (NLFSRs) in which both connections, feedback and feedforward, are allowed and no chain connection between the register stages is required. An algorithm for constructing a shortest binary machine generating a given periodic binary sequence is presented. [ABSTRACT FROM AUTHOR]

Binary sequences with optimal autocorrelation are needed in many applications. Two constructions of binary sequences with optimal autocorrelation of period N \equiv 0\ (mod\ 4) are investigated. The two constructions are powerful and generic in the sense that many classes of binary sequences with optimal autocorrelation could be obtained from binary sequences with ideal autocorrelation. General results on the minimal polynomials of these binary sequences are derived. Based on the results, both the linear complexities and the minimal polynomials are determined. [ABSTRACT FROM AUTHOR]

The maximization of a full-rank quadratic form over the binary alphabet can be performed through exponential-complexity exhaustive search. However, if the rank of the form is not a function of the problem size, then it can be maximized in polynomial time. By introducing auxiliary spherical coordinates, we show that the rank-deficient quadratic-form maximization problem is converted into a double maximization of a linear form over a multidimensional continuous set, the multidimensional set is partitioned into a polynomial-size set of regions which are associated with distinct candidate binary vectors, and the optimal binary vector belongs to the polynomial-size set of candidate vectors. Thus, the size of the candidate set is reduced from exponential to polynomial. We also develop an algorithm that constructs the polynomial-size candidate set in polynomial time and show that it is fully parallelizable and rank-scalable. Finally, we demonstrate the efficiency of the proposed algorithm in the context of adaptive spreading code design. [ABSTRACT FROM AUTHOR]

We combine the concepts of the p-periodic Legendre sequence, the (q - 1)-periodic Sidelnikov sequence and the two-prime generator to introduce a new p(q - 1)-periodic sequence called Legendre-Sidelnikov sequence. We show that this new sequence is balanced if p = q. For an arbitrary odd prime p and an arbitrary power q of an odd prime with gcd(p, q - 1) = 1 we determine the exact values of its (periodic) autocorrelation function and deduce an upper bound on its aperiodic autocorrelation function showing that it is small compared to its period. [ABSTRACT FROM AUTHOR]