We study the capacity of a general channel under the requirement that the error probability decreases exponentially to zero. A formula of this capacity is established by using information spectrum methods. Specifically, we show that this capacity equals to the supremum, over all input processes, of the input-output inf-information rate under exponential decreasing constraint. We also show that, when the code rate is below the capacity, the probability for a random code not having exponentially decreasing error probability is double exponentially small.

De Bruijn sequences can be categorized by the weight of the truth tables of the generating functions. Among all the weight classes, the numbers of de Bruijn sequences with minimum and maximum weights draw much attention. Fredricksen and Mayhew proposed six conjectures about them, some of which have remained unsolved for about forty years. In this paper, we give the exact formulas of de Bruijn sequences with extremal weights and then prove all the conjectures in the affirmative.

We propose the concept of partial cycle structure of feedback shift registers, and study its applications in searching the characteristic functions of de Bruijn sequences. We show that, if a function generates de Bruijn sequences then its partial cycle structure does not contain cycles, and conversely, if the partial cycle structure of a function does not contain cycles then it can be extended into a function that generates de Bruijn sequences. By using this property, we analyze the low degree terms in the characteristic functions of de Bruijn sequences, and in particular give a full description of the linear terms in them. We also design an algorithm to search the characteristic functions of de Bruijn sequences which should perform better than the random search algorithm.

We study the adjacency graphs of feedback shift registers (FSRs) with affine characteristic functions. We first show that, similar to the linear case, the output sequences of FSRs with affine characteristic functions also have the direct sum decompositions. The only difference from the linear case is that one component of the decomposition is a family of affine sequences, rather than linear sequences. Then, based on this fact, we give a relationship between the adjacency graphs of FSRs with affine characteristic functions and the generalized adjacency graphs of FSRs whose characteristic functions correspond to the components of the decomposition. This relationship establishes the algebraic structure of adjacency graphs and greatly simplifies the calculation of them. At last, we especially study the adjacency graph of the FSR whose characteristic function is$q_{k}(x)+1$where$q_{k}(x)$is the linear function corresponding to the polynomial$(1+x)^{k}$. We prove that for any two cycles of this FSR, the number of conjugate pairs shared by them is no more than 4 if$k$is a power of 2, and no more than 2 if$k$is not a power of 2.

De Bruijn sequences and l-sequences are defined to be the maximum-period sequences generated by feedback shift registers (FSRs) and feedback with carry shift registers (FCSRs), respectively. In this paper we give some relationships between de Bruijn sequences and l-sequences, and we propose an efficient method to generate de Bruijn sequences from l-sequences. The experimental results indicate that this method should be able to generate de Bruijn sequences of any order.

We study the cross-join pairs in the cycles of linear feedback shift registers whose characteristic polynomials are of the form$l(x) = p_{1}(x)p_{2}(x)\cdots p_{k}(x)$, where$p_{i}(x), 1\leq i\leq k$are primitive polynomials of coprime degrees. Firstly, we use Coppersmithet al.’sgenerating function theory to derive the lower and upper bounds for the number of cross-join pairs. Then we design an algorithm to generate these cross-join pairs. The algorithm requires a preparatory phase which costs$O(2^{n'})$time where$n'$is the largest degree of$p_{i}(x), 1\leq i\leq k$, and after that it costs only$O(n^{3})$time to generate one cross-join pair where$n$is the degree of$l(x)$. We also consider a special class of cross-join pairs, for which the preparatory phase costs only$O(2^{n''})$time where$n''$is the second-largest degree of$p_{i}(x), 1\leq i\leq k$. The number of these special cross-join pairs is about$\frac {1}{12}2^{2n-n'}$. We present some experimental results, which validate our analysis and demonstrate the efficiencies of the algorithms. These cross-join pairs can be used in the cross-joining method to construct de Bruijn sequences.

In this paper, we analyze the weight class distribution of de Bruijn sequences. The main tool we use is the generating function theory, proposed recently by Coppersmith et al. By analyzing the weights of cycles generated by the pure circulating register, we give explicit formulas for the numbers of de Bruijn sequences in the extremal weight classes. Moreover, we use these formulas to prove some conjectures proposed by Fredricksen and Mayhew, which seems have been opened for a long time. In addition to these theoretical results, some experimental results are also provided.

We study the problem of constructing De Bruijn sequences by joining cycles of linear feedback shift registers (LFSRs) with reducible characteristic polynomials. The main difficulty for joining cycles is to find the location of conjugate pairs between cycles, and the distribution of conjugate pairs in cycles is defined to be adjacency graphs. Let$l(x)$be a characteristic polynomial, and$l(x)=l_{1}(x)l_{2}(x)\cdots l_{r}(x)$be a decomposition of$l(x)$into pairwise co-prime factors. First, we show a connection between the adjacency graph of$\mathrm {FSR}(l(x))$and the association graphs of$\mathrm {FSR}(l_{i}(x))$,$1\leq i\leq r$. By this connection, the problem of determining the adjacency graph of$\mathrm {FSR}(l(x))$is decomposed to the problem of determining the association graphs of$\mathrm {FSR}(l_{i}(x))$,$1\leq i\leq r$, which is much easier to handle. Then, we study the association graphs of LFSRs with irreducible characteristic polynomials and give a relationship between these association graphs and the cyclotomic numbers over finite fields. At last, as an application of these results, we explicitly determine the adjacency graphs of some LFSRs and show that our results cover the previous ones.

We consider the adjacency graphs of the linear feedback shift registers (LFSRs) with characteristic polynomials of the form$l(x)p(x)$, where$l(x)$is a polynomial of small degree and$p(x)$is a primitive polynomial. It is shown that their adjacency graphs are closely related to the association graph of$l(x)$and the cyclotomic numbers over finite fields. By using this connection, we give a unified method to determine their adjacency graphs. As an application of the method, we explicitly calculate the adjacency graphs of LFSRs with the characteristic polynomials of the form$(1+x+x^{3}+x^{4})p(x)$, and construct a large class of De Bruijn sequences from them.

In this paper, a family of new de Bruijn sequences is proposed through the construction of maximum-length nonlinear feedback shift registers (NFSRs). Let$k$be a positive integer and$p_{0}(x), p_{1}(x), \ldots , p_{k}(x)$be the primitive polynomials in$\mathbb {F}_{2}[x]$with their degrees strictly increasing and pairwise coprime. We determine the cycle structure and adjacency graphs of linear feedback shift registers (LFSRs) with characteristic polynomial$q(x)=\prod \nolimits _{i=0}^{k}p_{i}(x)$. In the case that$p_{0}(x)=1+x$, an algorithm is proposed to produce maximum-length NFSRs from these LFSRs, and it is shown that the algorithm can generate$O(2^{(2^{k}-1)n})~n$-stage maximum-length NFSRs with memory complexity$O(2^{k}kn)$and time complexity$O(2^{n-d_{k}}kn)$, where$n$and$d_{k}$are the degrees of$q(x)$and$p_{k}(x)$, respectively. Finally, we illustrate the proposed algorithm in the case of$k=2$. In this case, we prove that for any integer$n\geq 8$, the algorithm can produce$n$-stage maximum-length NFSRs with time complexity as low as$O(n^{{\rm {log}{log}}(n)}$).