Questions tagged [gray-codes]
A Gray code is a cyclic ordering of binary strings so that two successive values differ in only one bit (a Hamming distance of 1).
12 questions
1
vote
1
answer
73
views
"Gray code" for $[\omega]^{<\omega}$
Let $\newcommand{\oo}{[\omega]^{<\omega}}\oo$ denote the collection of finite subsets of the set of non-negative integers $\newcommand{\o}{\omega}\o$.
If $A,B$ are any sets, let $A \,\triangle \, B ...
- 48.8k
0
votes
0
answers
30
views
Why standardized LDPC codes, such 5G NR, have 4 cycles in its parity check matrix?
We all know that short cycles in Tanner Graph are detrimental in error performance. So, Why standardized 5G NR LDPC codes have 4-cycles? 3rd generation Partnership Project (3GPP) had announced Base ...
- 1
4
votes
0
answers
162
views
Multiset of Hamming distances for a tour of all subsets
Consider a list of all the subsets of $\{1,\ldots,n\}$, in any order. Using binary notation, one such list for $n=3$ is
$$ 010, 100, 110, 011, 000, 111, 001, 101. $$
Now consider the Hamming distance ...
- 37.7k
2
votes
0
answers
77
views
Counting matchings in middle levels of the Boolean lattice
Let $k$ be a nonnegative integer and consider $C_k$, the set of all subsets $A$ of size $k$ in $[2k+1]=\{1,2,\ldots,2k+1\}$ as well as $C_{k+1}$, the set of all subsets $B$ of size $k+1$ in $[2k+1]$. ...
7
votes
3
answers
2k
views
"Gray code" for building teams
Motivation. In a team of $n$ people, we had the task to build subteams of a fixed size $k<n$ such that every day, $1$ person of the subteam is replaced by another person in the team, but not in the ...
- 48.8k
2
votes
0
answers
121
views
Balanced Gray codes for powers of 2
All of the binary 4-bit cyclic balanced Gray code sequences can be formed from simple reversals, bit-permutations, and circular shifts of the one Wikipedia example:
...
- 1,547
13
votes
3
answers
421
views
Maximal distance between $2d+1$ points on the $(d-1)$-sphere
If one arranges $2d$ points on the sphere $\mathbf S^{d-1}\subset\Bbb R^d$ at the vertices of the crosspolytope, then one can achieve a minimal spherical distance of $\pi/2$ between any two points, ...
- 13.6k
6
votes
1
answer
315
views
Are Gray codes in $\{0,1\}^n$ isomorphic?
Let $n\in\mathbb{N}$ be a positive integer. Two elements of $\{0,1\}^n$ form an edge if and only if their Hamming distance equals $1$. It is known that $\{0,1\}^n$ endowed with this graph structure ...
- 48.8k
2
votes
1
answer
1k
views
New Perfect 2-bit Error Correction Code - Are there any other?
I have recently looked through perfect error correcting codes and found the Hamming(7,3) and Golay(23,7). Using a computer program I have found a new 2 bit perfect error correcting code: Code(90, 2).
...
- 31
1
vote
1
answer
121
views
Hamiltonian Path through $n$-bit strings with maximum number of $0\mapsto 1$ transitions
Let $G_n$ be the complete graph whose vertices are the $2^n$ $n$-bit strings. Let $H_n$ denote the Hamiltonian path through $G_n$ that uses the maximum number of edges that correspond to a single bit ...
1
vote
1
answer
117
views
How many non-overlapping k-hop neighborhoods can be uniquely colored on an $N$-dimensional hypercube?
Imagine I have a $N$-dimensional hypercube. My aim is to distinctly color as many non-overlapping $k$-hop neighborhoods as possible (i.e. sets of vertices connected by a Manhattan distance of at most ...
3
votes
1
answer
1k
views
Sprague-Grundy sequence for the ruler game
Consider the game "Ruler", which is defined as follows. We start with finitely many coins in a line. A move in this game consists of turning over any number of coins, but they must be consecutive, ...
- 14k