Broadcasting on Two-Dimensional Regular Grids

• Published in: IEEE transactions on information theory 2022-10, Vol.68 (10), p.6297-6334
• Main Authors: Makur, Anuran, Mossel, Elchanan, Polyanskiy, Yury
• Format: Article
• Language: English
• Subjects: Apexes; Automata; Automata theory; Boolean; Boolean algebra; Boundary conditions; Broadcasting; Cellular automata; Cellular communication; Communication networks; Discrete time systems; Graph theory; linear code; Linear programming; Martingales; Noise level; Noise levels; Noise measurement; oriented bond percolation; Percolation; potential function; Principal component analysis; probabilistic cellular automata; Probabilistic logic; Statistical analysis; supermartingale; Two dimensional displays
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2022.3177667

We study an important specialization of the general problem of broadcasting on directed acyclic graphs, namely, that of broadcasting on two-dimensional (2D) regular grids. Consider an infinite directed acyclic graph with the form of a 2D regular grid, which has a single source vertex X at layer 0, and k + 1 vertices at layer k \geq 1 , which are at a distance of k from X . Every vertex of the 2D regular grid has outdegree 2, the vertices at the boundary have indegree 1, and all other non-source vertices have indegree 2. At time 0, X is given a uniform random bit. At time k \geq 1 , each vertex in layer k receives transmitted bits from its parents in layer k-1 , where the bits pass through independent binary symmetric channels with common crossover probability \delta \in \left({0,\frac {1}{2}}\right) during the process of transmission. Then, each vertex at layer k with indegree 2 combines its two input bits using a common deterministic Boolean processing function to produce a single output bit at the vertex. The objective is to recover X with probability of error better than \frac {1}{2} from all vertices at layer k as k \rightarrow \infty . Besides their natural interpretation in the context of communication networks, such broadcasting processes can be construed as one-dimensional (1D) probabilistic cellular automata, or discrete-time statistical mechanical spin-flip systems on 1D lattic