Binary Gray codes with long bit runs (Q1408531): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Luis A. Goddyn / rank | |||
Property / author | |||
Property / author: Luis A. Goddyn / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 04:15, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Binary Gray codes with long bit runs |
scientific article |
Statements
Binary Gray codes with long bit runs (English)
0 references
24 September 2003
0 references
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.
0 references
Hamilton cycle
0 references
Hamilton circle
0 references
spread
0 references
gap
0 references
threshold
0 references
Hamming distance
0 references