# Technical Report CS0783

 TR#: CS0783 Class: CS Title: HIGH-ORDER SPECTRAL-NULL CODES: CONSTRUCTIONS AND BOUNDS. Authors: R.M. Roth, P.H. Siegal and A. Vardy PDF CS0783.pdf Abstract: Let \mbox{\boldmathS}(n,k) denote the set of all sequences of length n over the alphabet \{+1.-1\}, having a k-th order spectral-null at zero frequency. A subset of \mbox{\boldmathS}(n,k) is a spectral-null code of length n and order k. Upper and lower bounds on the cardinality of \mbox{\boldmathS}(n,k) are derived. In particular, we prove that O(2^k \log_2 n) \geq n - \log_2|\mbox{\boldmathS}(N,K)| \Geq O(K \Log_2 N) for infinitely many values of n. On the other hand, we show that if n is not divisible by 2^m for m=\lfloor \log_2 k \rfloor+1, then \mbox{\boldmathS}(n,k) is empty. Furthermore, bounds on the minimum Hamming distance of d of \mbox{\boldmathS}(n,k) are provided, showing that 2k \leq d \leq k(k-1)+2 for infinitely many n. We also investigate the minimum number of sign changes in a sequence \underbar{x} \in \mbox{\boldmathS}(n,k) and provide an equivalent definition of \mbox{\boldmathS}(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_2 N+O(\Log \Log N) is presented. Furthermore, we prove that the first nonzero moment of any sequence in \mbox{\boldmathS}(n,k) is divisible by k! and then show how to construct a sequence with a spectral null of order k whose first nonzero moment is any even multiple of 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 \rightarrow \infty. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1993/CS/CS0783), rather than to the URL of the PDF files directly. The latter URLs may change without notice.