[<<][math][>>][..]

Tue Aug 3 09:06:50 CEST 2010

Minimal erase counter

How to make a counter that has a minimal number of erases (0->1
transitions).

i.e.

1111 erase
1110
1100
1000
1101 erase
1001
0001
...

It boils down to finding a sequence of paths through the bit-flip
hypercube from 111... to 000...

This is probably not unique, but how to find a representative with a
simple structure?  I.e. how to turn the directed (1->0) hypercube
graph into a tree?  (And step 2, how to order the branches of that
tree?)

The idea is to give each node only a single parent.  I.e. given a bit
vector, there is an algorithm to compute its parent.

10010011 ->
11010011

101001 ->
111001

[Reply][About]

[<<][math][>>][..]