Shared codeword blocks and edge acceptance circuits

Fix a finite ordered alphabet $\mathrm{\Sigma }=\{{\sigma }_0,\dots ,{\sigma }_{W-1}\}$ with $W\ge 2$. Put $k=\lceil {\log }_{2}W\rceil$ and $\mathrm{\ell }=2^k$. Let $u^{(0)},\dots ,u^{(2^k-1)}$ be the $k$-bit vectors in lexicographic order and define the codeword of ${\sigma }_i$ to be $C({\sigma }_i):={\mathrm{WH}}_k(u^{(i)})\in \{0,1{\}}^{\mathrm{\ell }},0\le i<W\mathrm{.}$ The map $C$ is injective, and every two distinct selected codewords have relative distance $\delta =1\mathrm{/}2$ by Distinct Walsh–Hadamard words differ on half the cube. Moreover, $W\le \mathrm{\ell }<2W$: the lower bound follows from $k=\lceil {\log }_{2}W\rceil$, and $2^{k-1}<W$ gives the strict upper bound.

For a constraint graph over $\mathrm{\Sigma }$ as in Constraint graph and labeling value, discard its isolated vertices (which do not affect its value). Give each remaining vertex $v$ one physical block $B_v\in \{0,1{\}}^{\mathrm{\ell }}$, shared by all incident edges. A block is valid when it equals $C(a)$ for some $a\in \mathrm{\Sigma }$; its decoded label is then the unique such $a$. The table order inside each block is that of Walsh–Hadamard encoding and relative Hamming distance.

For each edge $e=(v,w)$ with its specified endpoint order and relation $R_e\subseteq {\mathrm{\Sigma }}^2$, define an edge circuit with formal input pieces $X,Y\in \{0,1{\}}^{\mathrm{\ell }}$. Its Boolean function is $E_{R_e}(X,Y):={\bigvee }_{(a,b)\in R_e}([X=C(a)]\wedge [Y=C(b)]),$ where $[P]$ is $1$ when $P$ holds and $0$ otherwise, and the empty disjunction is $0$. Thus $E_{R_e}(X,Y)=1$ exactly when both blocks are valid and their decoded labels form a pair in $R_e$. This function has an explicit circuit in the AND/OR/NOT basis of Boolean circuits: basis, fan-in, size, and depth: compare each input bit to the corresponding constant codeword bit, conjoin the $2\mathrm{\ell }$ comparisons for each allowed pair, then OR the pair tests. The circuit uses $O(\mathrm{\mid }{R}_e\mathrm{\mid }\mathrm{\ell })$ gates (or the constant-zero output if $R_e=\mathrm{\varnothing }$), so at most $O(W^2\mathrm{\ell })=O(W^3)$ gates. In the graph, compose its first formal piece with $B_v$ and its second with $B_w$; for a loop $v=w$, both pieces use the same physical block, so the test is exactly the diagonal test $R_e(a,a)$ required for loops. Reversing an endpoint order transposes the relation and swaps the formal pieces. If the graph has no edges, it has no blocks or edge circuits after isolated vertices are discarded.