On the (n, t)-antipodal Gray codes

Gerard J. Chang, Sen Peng Eu*, Chung Heng Yeh


研究成果: 雜誌貢獻期刊論文同行評審

3 引文 斯高帕斯(Scopus)


An n-bit Gray code is a circular listing of all 2n n-bit binary strings in which consecutive strings differ at exactly one bit. For n ≤ t ≤ 2n - 1, an (n, t)-antipodal Gray code is a Gray code in which the complement of any string appears t steps away from the string, clockwise or counterclockwise. Killian and Savage proved that an (n, n)-antipodal Gray code exists when n is a power of 2 or n = 3, and does not exist for n = 6 or odd n > 3. Motivated by these results, we prove that for odd n ≥ 3, an (n, t)-antipodal Gray code exists if and only if t = 2n - 1 - 1. For even n, we establish two recursive constructions for (n, t) codes from smaller (n, t). Consequently, various (n, t)-antipodal Gray codes are found for even n's. Examples are for t = 2n - 1 - 2k with k odd and 1 ≤ k ≤ n - 3 when n ≥ 4, for t = 2n - k when n ≥ 2 k with 1 ≤ k ≤ 3, for t = n when n = 2k ≥ 2 (an alternative proof for Killian and Savage's result) ...etc.

頁(從 - 到)82-90
期刊Theoretical Computer Science
出版狀態已發佈 - 2007 4月 20

ASJC Scopus subject areas

  • 理論電腦科學
  • 電腦科學(全部)


深入研究「On the (n, t)-antipodal Gray codes」主題。共同形成了獨特的指紋。