Binary Gray codes with long bit runs
type: Item
instance of: scholarly article
title: Binary Gray codes with long bit runs
zbMATH Open document ID: 1023.05080
author: Pavol Gvozdjak
author: Luis Goddyn
published in: The Electronic Journal of Combinatorics
publication date: 2003-09-24T00:00:00Z
full work available at URL: https://eudml.org/doc/122966
full work available at URL: v10i1r27.html
review text: Summary: We show that there exists an \(n\)-bit cyclic binary Gray code all of whose bit runs have length at least \(n - 3\log_2 n\). That is, there exists a cyclic ordering of \(\{0,1\}^n\) such that adjacent words differ in exactly one (coordinate) bit, and such that no bit changes its value twice in any subsequence of \(n-3\log_2 n\) consecutive words. Such Gray codes are `locally distance preserving' in that Hamming distance equals index separation for nearby words in the sequence.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 1985368
zbMATH Keywords: Hamilton cycle
zbMATH Keywords: Hamilton circle
zbMATH Keywords: spread
zbMATH Keywords: gap
zbMATH Keywords: threshold
zbMATH Keywords: Hamming distance
MaRDI profile type: Publication
Recommended article: Q3816026
Recommended article: Binary tree gray codes
Recommended article: Q3119334
Recommended article: Balanced Gray codes
Recommended article: Q4863495
Recommended article: Gray codes with bounded weights
Recommended article: Gray codes with restricted density
Recommended article: Gray Code Compression
Recommended article: Q4016807
Recommended article: A technique for generating Gray codes
description: scientific article; zbMATH DE number 1985368