= Round-robin arbitration with idle memory
Store both the last recipient index $L$ and a current-grant valid <bit> $V$. With $k$ possible recipients, an idle period clears $V$ while preserving $L$. The <Moore machine> grants requester $j$ precisely when $V\land[L=j]$ holds. For $k>1$, its $k$ idle states are distinguishable by a subsequent pair of competing requests with different positions in the cyclic order; active states have distinct outputs. Thus all $2k$ states are distinguishable and $\lceil\log_2(2k)\rceil$ state bits suffice and are necessary for this output convention. A continuously asserted request receives a grant within $k$ decisions, because before that grant the cyclic scan cannot pass it to choose a later asserted request.
Back to article page
