Error Correcting Sequence and Projective De Bruijn Graph |
| |
Authors: | Mariko Hagita Makoto Matsumoto Fumio Natsu Yuki Ohtsuka |
| |
Affiliation: | (1) Department of Computer Science and Engineering, Ochanomizu University, 2-2-1 Otsuka Bunkyo-ku, Tokyo 112-8610, Japan;(2) Department of Mathematics, Hiroshima University, Higashi-Hiroshima 739-8526, Japan |
| |
Abstract: | Let X be a finite set of q elements, and n, K, d be integers. A subset C ⊂ X n is an (n, K, d) error-correcting code, if #(C) = K and its minimum distance is d. We define an (n, K, d) error-correcting sequence over X as a periodic sequence {a i } i=0,1,... (a i ∈ X) with period K, such that the set of all consecutive n-tuples of this sequence form an (n, K, d) error-correcting code over X. Under a moderate conjecture on the existence of some type of primitive polynomials, we prove that there is a error correcting sequence, such that its code-set is the q-ary Hamming code with 0 removed, for q > 2 being a prime power. For the case q = 2, under a similar conjecture, we prove that there is a error-correcting sequence, such that its code-set supplemented with 0 is the subset of the binary Hamming code [2 m − 1, 2 m − 1 − m, 3] obtained by requiring one specified coordinate being 0. Received: October 27, 2005. Final Version received: December 31, 2007 |
| |
Keywords: | Error-correcting code Hamming code m-sequence de Bruijn graph projective de Bruijn graph |
本文献已被 SpringerLink 等数据库收录! |
|