On the (n, t)-antipodal Gray codes

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

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)82-90
Number of pages9
JournalTheoretical Computer Science
Volume374
Issue number1-3
DOIs
Publication statusPublished - 2007 Apr 20

Fingerprint

Gray Code
Strings
Odd
Anticlockwise
Clockwise
Consecutive
Complement
Binary
If and only if
Alternatives

Keywords

  • Antipodal
  • Complement
  • Gray code
  • Hamiltonian cycle
  • Period
  • n-cube

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

On the (n, t)-antipodal Gray codes. / Chang, Gerard J.; Eu, Sen Peng; Yeh, Chung Heng.

In: Theoretical Computer Science, Vol. 374, No. 1-3, 20.04.2007, p. 82-90.

Research output: Contribution to journalArticle

Chang, Gerard J. ; Eu, Sen Peng ; Yeh, Chung Heng. / On the (n, t)-antipodal Gray codes. In: Theoretical Computer Science. 2007 ; Vol. 374, No. 1-3. pp. 82-90.
@article{05113cb978374a70b37d29fbd21d93e9,
title = "On the (n, t)-antipodal Gray codes",
abstract = "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.",
keywords = "Antipodal, Complement, Gray code, Hamiltonian cycle, Period, n-cube",
author = "Chang, {Gerard J.} and Eu, {Sen Peng} and Yeh, {Chung Heng}",
year = "2007",
month = "4",
day = "20",
doi = "10.1016/j.tcs.2006.12.005",
language = "English",
volume = "374",
pages = "82--90",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1-3",

}

TY - JOUR

T1 - On the (n, t)-antipodal Gray codes

AU - Chang, Gerard J.

AU - Eu, Sen Peng

AU - Yeh, Chung Heng

PY - 2007/4/20

Y1 - 2007/4/20

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

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

KW - Antipodal

KW - Complement

KW - Gray code

KW - Hamiltonian cycle

KW - Period

KW - n-cube

UR - http://www.scopus.com/inward/record.url?scp=33947432006&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33947432006&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2006.12.005

DO - 10.1016/j.tcs.2006.12.005

M3 - Article

AN - SCOPUS:33947432006

VL - 374

SP - 82

EP - 90

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-3

ER -