Geometric properties of high-order spectral-null codes
摘要
Let S(N, q) be the set of all binary words of length N having a q-th order spectral-null at zero frequency. Any subset of S(N, q) is a spectral-null code of length N and order q. Such codes have been recently considered by the digital recording community because of the useful properties they induce on the signal stored in digital recording medias (such as Optical Disks, Magnetic Disks, etc.). Considering the elements of S(N,q) as points of the euclidean geometry of IR N , S(N,q) can be regarded as the algebraic variety which coincides with the intersection of the N dimensional hypercube with a certain hyperspace of dimension N - q. We derive many interesting geometric properties of S(N, q). In particular, we determine easily computable bijections f:Π h i = 1 IR N i → IR N , with N = Σ h i = 1 N i , such that f(S(N 1 , q ),S(N 2 , q ),...,S(N h , q )) ⊆ S(N,q'), for q ≤ q'. This, not only enables us to get examples of q-th order spectral-null words, but allows to obtain simple geometric constructions for systematic q-th order spectral-null codes, q > 1. We also derive an asymptotic expression for the cardinality of S(N, 2) (this is done by proving some new results on the theory of number partitions) which allows to get an explicit expression for the redundancy of S(N,2). Further, using a certain set of isometries of IR N which fix S(N, 1), we are able to define random walks over the variety S(N,1) which always intersect S(N, 2). This allows us to define a new efficient recursive method to encode k information bits into a second-order spectral-null code of length N(k) < k + 3 log 2 k + O (log log k). The codes obtained with this method are less redundant than the codes found in the literature.