High-Order Spectral-Null Codes—Constructions and Bounds

Abstract

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) log2 (n/k) ≤ n - log2|ℒ(k,n)| ≤ 0(2klog2 n) for infinitely many values of n. On the other hand, we show that ℒ(n,k) is empty unless n is divisible by 2m, where m — [log2k] + 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 log2 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! and then show how to construct a word 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 → ∞. © 1994 IEEE