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
PDFCS0783.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.

CopyrightThe 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.

To the list of the CS technical reports of 1993
To the main CS technical reports page

Computer science department, Technion
admin