A brief introduction to Pearl’s BP

We first provide a brief introduction to the BP algorithm, in particular a version of Pearl’s BP. We use an example to illustrate the procedure. The details and formal description can be found in Ref. [168].

Take Fig. 8.9 for instance, where a random variable X has parents U₁, U₂, …, U_M and children Y₁, Y₂, …, Y_N. Here the parent nodes are characterized by the following equality of conditional probability:

$\begin{array}{l}\hfill P(X|\text{all other random variables})=P(X|U_1,U_2,\dots ,U_M),\end{array}$

that is, given the random variables in the parent nodes, X is independent of all nonparent nodes. As indicated by the name, we say that a node is a child of X if X is a parent of it. The message passing of Pearl’s BP is illustrated by dotted arrows and dashed arrows in the figure. The dashed arrows transmit π-messages from a parent to its children. For instance, the message passing from U_m to X is ${\pi }_{U_{\text{m}},X}(U_{\text{m}})$, which is the prior information of U_m given that all the information U_m has been received. The dotted arrows transmit λ-messages from child to parent. For instance, the message passed from Y_n to X is ${\lambda }_{Y_n,X}(X)$, which is the likelihood of X given that the information Y_n has been received. After X receives all π-messages (i.e., ${\pi }_{U_{\text{m}},X}(U_{\text{m}})$ from its parents U₁, U₂, …, U_M) and all λ-messages (i.e., ${\lambda }_{Y_n,X}(X)$, X from its children Y₁, Y₂, …, Y_N), X updates its local belief information BEL_X(x), and transmits λ-messages ${\lambda }_{X,U_{\text{m}}}(U_{\text{m}})$ to its parents and π-messages ${\pi }_{X,Y_n}(\mathbf{x})$ to its children. The expressions for these messages are given by

$\begin{array}{ll}\hfill {\pi }_X(\mathbf{x})& =\sum _{\mathbf{U}}p(\mathbf{x}|\mathbf{U})\prod _{m=1}^M{\pi }_{U_{\text{m}},X}(U_{\text{m}}),\hfill \end{array}$

$\begin{array}{ll}\hfill {\gamma }_X(\mathbf{U})& =\sum _{\mathbf{x}}\prod _{n=1}^N{\lambda }_{Y_n,X}(\mathbf{x})p(\mathbf{x}|\mathbf{U}),\hfill \end{array}$

$\begin{array}{ll}\hfill BE{L}_X(\mathbf{x})& =\alpha \times \prod _{n=1}^N{\lambda }_{Y_n,X}(\mathbf{x})\times {\pi }_X(\mathbf{x}),\hfill \end{array}$

$\begin{array}{ll}\hfill {\lambda }_{X,U_{\text{m}}}(U_{\text{m}})& =\sum _{\mathbf{U},\ne U_{\text{m}}}{\gamma }_X(\mathbf{U})\times \prod _{j\ne m}{\pi }_{U_j,X}(U_j),\hfill \end{array}$

$\begin{array}{ll}\hfill {\pi }_{X,Y_n}(\mathbf{x})& ={\pi }_X(\mathbf{x})\times \prod _{i\ne n}{\lambda }_{Y_i,X}(\mathbf{x}),\hfill \end{array}$

where U = (U₁, U₂, …, U_M) and Y = (Y₁, Y₂, …, U_N).

In the initialization stage of Pearl’s BP, the initial values are defined as

$\begin{array}{l}\hfill {\lambda }_{X,U}(\mathbf{u})=\left\{\begin{array}{ll}p({\mathbf{x}}_0|\mathbf{u}),& X\text{is evidence},\mathbf{x}={\mathbf{x}}_0,\\ 1,& X\text{is not evidence}\end{array}\right.\end{array}$

and

$\begin{array}{l}\hfill {\pi }_{X,Y}(\mathbf{x})=\left\{\begin{array}{ll}\delta (\mathbf{x},{\mathbf{x}}_0),& X\text{is evidence},\mathbf{x}={\mathbf{x}}_0,\\ p(\mathbf{x}),& X\text{is not evidence}.\end{array}\right.\end{array}$

Iterative decoding

Based on the tools of a Bayesian network, we can derive the iterative decoding procedure. Fig. 8.10 shows the procedure of message passing in the decoding of a CPS: x_t−2 summarizes all the information obtained from previous time slots and transmits π-message π_{xt−2, xt−1}(x_t−2) to x_t−1. The BP procedure can be implemented in either synchronous or asynchronous manner. To accelerate the procedure, we implement the asynchronous Pearl BP. The updating order and message passing in one iteration are given in Procedure 9.

The algorithm has been tested in the context of voltage control in smart grids [165]. Numerical results have shown that the performance of both decoding and system state estimation is substantially improved, when compared with traditional separate decoding and estimation. One potential challenge in joint decoding and estimation is the possibility of error propagation; i.e., the decoding error or estimation error will be propagated to the next time slot, since the decoding and estimation procedures in different time slots are correlated. An effective approach to handle error propagation is to monitor the performance and restart the decoding/estimation procedure once performance degradation is detected.

System model

We assume that the communication channel has binary input and output. The transmitter has a time-varying state x_t, which is represented by the vertex of a graph G. The edges in the graph G show the possibility of state transitions. It is assumed that G is known to both the transmitter and receiver. This setup is similar to the random walk on graphs.

The time is divided into rounds and channel use times. In each round, the state of the transmitter makes one move in G, and then the transmitter can use the communication channel M times. The encoded bits are based on all the history of the transmitter state. The goal of the design is to find a coding scheme that enables the receiver to obtain accurate estimation of the transmitter’s state with a large probability. Hence the transmitter can be considered as the combination of physical dynamics and communication transmitter. The coding rate is given by

$\begin{array}{l}\hfill \rho =\frac{log\Delta }{M},\end{array}$

where Δ is the maximum out-degree or in-degree of nodes in the graph G.

The receiver outputs an estimation on x_t, which is denoted by ${\widehat{x}}_t$, based on all the received coded bits. The error of decoding is represented by the shortest length between x_t and ${\widehat{x}}_t$ in the graph G, which is denoted by $d_G(x,\widehat{x})$. The communication scheme has an error exponent κ if

$\begin{array}{l}\hfill P(d_G(x,\widehat{x})\ge l)\le exp(-\kappa l).\end{array}$

It was shown in Ref. [169] that the communication is online efficient if the time and space complexities of coding and decoding are of the order of ${(logt)}^{O(1)}$. If the coding scheme has a positive rate, positive error exponent and is online efficient, then we say that the code is asymptotically good.

Note that the problem considered above is more like a system estimation problem. The control procedure is not considered; i.e., the system state x_t evolves independently of the communication performance. However, the system state is closely related to the control problems, since the error of system state estimation substantially determines the performance of control; meanwhile the system state x_t can be considered as the system state in which the impact of control has been removed.

Concept of trajectory codes

The trajectory of the transmitter’s state can be represented by a path in the corresponding graph G, whose initial time is denoted by t₀. If two trajectories, γ and γ′, have the same length, the same starting time and the same initial vertex, we denote this by γ ∼ γ′. The distance between two trajectories indicates the number of different states in the two trajectories and is denoted by τ(γ, γ′).

A trajectory code, denoted by χ, maps from a trajectory to a certain alphabet in a concatenation manner:

$\begin{array}{l}\hfill \chi (\gamma )=\left(\right.\chi (\gamma (t_0+1),t_0+1),\dots ,\chi (\gamma (t_0+t),t_0+t)\left)\right..\end{array}$

The Hamming distance between two equal-length codewords is denoted by h. The relative distance of a trajectory code is denoted by

$\begin{array}{l}\hfill \delta =\underset{\gamma \sim {\gamma }^{\prime }}{inf}\frac{h(\chi (\gamma ),\chi ({\gamma }^{\prime }))}{\tau (\gamma ,{\gamma }^{\prime })},\end{array}$

which implies the capability of distinguishing two different trajectories of the transmitter’s state. A trajectory code is said to be asymptotically good if it has a positive rate and provides a positive relative distance.

Obviously, the larger the relative distance δ, the more capable the receiver is of estimating the transmitter’s state. When δ is large, even if there are some transmission errors, the remaining discrepancy between two codewords can still be used to distinguish the two different state trajectories. Then the major challenge is the existence and construction of an asymptotically good trajectory code. The following theorem guarantees the existence of correspondence:

The details of the proof are given in Ref. [169]. Here we provide a sketch of the proof, which is based on the probabilistic approach and random coding, similarly to Shannon’s random coding argument [33]. First we consider a random coding scheme; i.e., the transmitter randomly selects an output from the output alphabet for each possible input (i.e., a state, or equivalently a vertex in G). Consider two trajectories γ₁ and γ₂, which satisfy γ₁ ∼ γ₂ but do not have common vertices except for the initial one. We call these two trajectories twins. It is easy to verify that

$\begin{array}{l}\hfill \underset{{\gamma }_1\sim {\gamma }_2}{inf}\frac{h(\chi (\gamma ),\chi ({\gamma }^{\prime }))}{\tau (\gamma ,{\gamma }^{\prime })}=\underset{{\gamma }_1,{\gamma }_2\text{are twins}}{inf}\frac{h(\chi (\gamma ),\chi ({\gamma }^{\prime }))}{\tau (\gamma ,{\gamma }^{\prime })}.\end{array}$

Then we define the event

$\begin{array}{l}\hfill A_{\gamma }=\left\{\left.\gamma =({\gamma }_1,{\gamma }_2)\right|{\gamma }_1\sim {\gamma }_2,\frac{h(\chi (\gamma ),\chi ({\gamma }^{\prime }))}{\tau (\gamma ,{\gamma }^{\prime })})\le \delta \right\}.\end{array}$

If we can prove

$\begin{array}{l}\hfill {\cap }_{\gamma }{A}_{\gamma }^c\ne \varphi ,\end{array}$

then there exists at least one asymptotically good trajectory code. In Ref. [169], Eq. (8.129) is proved by citing the Lovasz Local Lemma.

Construction of trajectory codes

Although the existence of trajectory codes has been proved, it is still not clear how to construct these codes. In Ref. [169], two approaches are proposed to construct trajectory codes for the special case of d-dimensional grids. In this book, we provide a brief introduction to the first method.

Note that the grid graph is determined by the set of vertices V_n, d to be

$\begin{array}{l}\hfill V_{n,d}={\{-n/2+1,n/2\}}^d.\end{array}$

Two nodes with distance 1 have a connecting edge. The goal of the construction procedures is to design a trajectory code

$\begin{array}{l}\hfill \chi :V_{n,d}\times \{1,\dots ,n/2\}\to S,\end{array}$

which is asymptotically good.

The first approach of construction is based on two codes, where $n_1\in \Theta (logn)$ and k is the least even integer no less than $\frac{12}{1-\delta }+4$.

• Block code: Consider a block code $\eta :V_{n,d}\to R_1^{n_1}$, where R₁ is a particular finite alphabet. Intuitively, η encodes each vertex in V_n, d to a block code with codeword length n₁. We assume that the block code η has a positive rate and a relative distance (1 + δ)/2. The coding and decoding procedures can be computed in a time of order $n_1^{O(1)}$. η can be rewritten as

$\begin{array}{l}\hfill \eta (x)=({\eta }_1(x,1),\dots ,{\eta }_1(x,n_1)),\end{array}$

where ${\eta }_1:V_{n,d}\times \{1,\dots ,n_1\}\to R_1$.

• Recursive code: We assume that ${\chi }_1:V_{k{n}_1,\dots ,d}\times \{1,\dots ,k{n}_1/2\}\to S_1$ is a trajectory code with relative distance (1 + δ)/2, where S₁ is a finite alphabet. The construction of this code will be provided later.

Now we cover the space V_n, d by overlapping tiles. The tile placed at vertex x = (x₁, …, x_d, x_d+1) ∈ V_n, d is the mapping defined as

$\begin{array}{l}\hfill {\sigma }_x(y)=({\chi }_1(y-x),{\eta }_1(x_1,\dots ,x_d,(y_{d+1}-x_{d+1}\text{mod}{n}_1))),\end{array}$

which maps from the domain

$\begin{array}{l}\hfill \left(\prod _{i=1}^d(x_1-k{n}_1/2+1,\dots ,x_i+k{n}_1/2)\right)\times (x_{d+1}+1,\dots ,x_{d+1}+k{n}_1/2),\end{array}$

to S₁ × R₁.

We assume that n can be divided by kn₁. Then we pick out the tiles placed at the locations x having the following form:

$\begin{array}{l}\hfill x=(n_{1}k{z}_1+n_1{a}_1,\dots ,n_{1}k{z}_{d+1}+n_1{a}_{d+1}),\end{array}$

where {z_i}_i satisfy

$\begin{array}{l}\hfill (z_1,\dots ,z_{d+1})\in {\left\{-\frac{n}{2k{n}_1}+1,\dots ,\frac{n}{2k{n}_1}\right\}}^d\times \left\{1,\dots ,\frac{n}{2k{n}_1}\right\},\end{array}$

and

$\begin{array}{l}\hfill (a_1,\dots ,a_{d+1})\in {\left\{-\frac{k}{2}+1,\dots ,\frac{k}{2}\right\}}^d\times \{0,\dots ,k-1\}.\end{array}$

The set of these tiles, which actually form a covering of V_n, d, are labeled using (a₁, …, a_d+1). Hence there are a total of k^d+1 such sets. This procedure is illustrated in Fig. 8.11, in which we set n₁ = 4 and k = 2.

The trajectory code is then given by

$\begin{array}{l}\hfill \chi (y)={\{{\chi }_{(a_1,\dots ,a_{d+1})(y)}\}}_{(a_1,\dots ,a_{d+1})},\end{array}$

that is, for each state y, the coder output is the concatenation of all the coder outputs at the tiles satisfying Eq. (8.135).

The intuition behind the complicated procedure of construction is given below:

• The coder for long trajectories (of the order of n) is based on the coders for short trajectories (of the order of $logn$).

• When the transmitter state is at a particular point of R^d, the coder output is determined by the output of the tiles close to it.

• The coder output of each tile in Eq. (8.133) consists of the recursive coder output, which encodes the transmitter state with respect to the center point of the tile, and the output of the block coder, which encodes the location of the center point of the tile.

It was shown in Ref. [169] that the above construction of trajectory codes can achieve the relative distance δ < 1, whose proof is involved. Then the only unsolved problem is the construction of the coder χ₁ for each tile. Since the problem size is much smaller, it is possible to obtain the coder by using exhaustive search, thus solving the whole problem.

System model

We consider a linear system with system state x and observations y, which are given by

$\begin{array}{l}\hfill \mathbf{x}(t+1)=\mathbf{F}\mathbf{x}(t)+\mathbf{G}\mathbf{u}(t)+\mathbf{w}(t)\end{array}$

and

$\begin{array}{l}\hfill \mathbf{y}(t)=\mathbf{H}\mathbf{x}(t)+\mathbf{v}(t),\end{array}$

where u(t) is the control action, w(t) and v(t) are bounded noise processes. It is assumed that (F, G) are controllable and (F, H) are observable.

At time t, the sensor observes y(t) and generates a k-bit message, which is a function of all existing observations. Suppose that n bits can be transmitted for the k information bits. Hence the data transmission rate is k/n.

Anytime reliability

According to the discussion in Chapter 5, the communication should satisfy the anytime reliability in order to stabilize the linear system. We say that an encoder-decoder pair can achieve (R, β, d₀)-reliability over a particular communication channel if

$\begin{array}{l}\hfill P(min\{\tau :\widehat{b}(\tau |t)\ne b_{\tau }\}=t-d+1)\le \eta 2^{-n\beta d},\forall d\ge d_0,\forall t,\end{array}$

where $\widehat{b}(\tau |t)$ denotes the estimation of b_τ (the message transmitted at time τ) given the received messages until time t, and η is a constant. Intuitively Eq. (8.141) indicates that the probability of decoding error decreases exponentially with elapsed time.

Note that this definition of anytime reliability is not literally the same as the original one in Ref. [13]. In Ref. [13], the encoder-decoder pair can achieve α-anytime reliability if

$\begin{array}{l}\hfill P(\widehat{b}(\tau |t)\ne b(\tau ))\le K{2}^{-\alpha (t-\tau )},\end{array}$

for any t and τ. However, it is easy to see that these two definitions are equivalent. First, if Eq. (8.141) holds, then we have

$\begin{array}{ll}\hfill P(\widehat{b}(\tau |t)\ne b(\tau ))& \le \sum _{d=t-\tau }^{\infty }P(min\{\tau :\widehat{b}(\tau |t)\ne b_{\tau }\}=t-d+1)\hfill \\ \hfill & \le \sum _{d=t-\tau }^{\infty }\eta 2^{-n\beta d}\hfill \\ \hfill & =\frac{\eta 2^{-n\beta (t-\tau )}}{1-2^{-n\beta }},\hfill \end{array}$

which implies β-anytime reliability. The first inequality arises because the event that b_τ is incorrectly decoded belongs to the event that the first incorrectly decoded message is b_s, where s ≤ τ.

On the other hand, if the encoder-decoder pair is α-anytime reliable according to Eq. (8.142), we have

$\begin{array}{ll}\hfill P(min\{\tau :\widehat{b}(\tau |t)\ne b_{\tau }\}=t-d+1)& \le P(\widehat{b}(t-d+1|t)\ne b(t-d+1))\hfill \\ \hfill & \le K{2}^{-\alpha d},\hfill \end{array}$

where the first inequality arises because the event that the first decoding error happens for b_t−d belongs to the event that b_t−d is incorrectly decoded. According to the conclusion in Ref. [13, Theorem 5.2], the anytime reliability can guarantee the stability of linear systems with sufficiently small outage probability.

Linear tree codes

Ref. [170] proposed the use of linear tree codes to design the anytime reliable code. Note that the concept of tree codes will be explained in the next section. Due to the requirement of causal coding, the output of linear tree codes c_r at time slot r is given by

$\begin{array}{l}\hfill c_r=f_r(b_{1:r})=\sum _{k=1}^r{G}_{rk}{b}_k,\end{array}$

where b_k is the k-bit information symbol generated at time k, the subscript r is the current time index, and {G_rk} are the n × k generating matrices. This coding procedure is illustrated in Fig. 8.12.

Hence the overall generating matrix can be written as

$\begin{array}{l}\hfill {\mathbf{G}}_{n,R}=\left(\begin{array}{lllll}\hfill G_{11}\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill \cdots \hfill \\ \hfill G_{21}\hfill & \hfill G_{22}\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill ⋮\hfill \\ \hfill G_{r1}\hfill & \hfill G_{r2}\hfill & \hfill \cdots \hfill & \hfill G_{rr}\hfill & \hfill \cdots \hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill \\ \hfill \hfill \end{array}\right).\end{array}$

The parity check matrix of G_n, R is denoted by H_n, R, which satisfies

$\begin{array}{l}\hfill {\mathbf{G}}_{n,R}{\mathbf{H}}_{n,R}=0.\end{array}$

It is easy to verify that H_n, R also has the lower triangular matrix form.

Maximum likelihood decoding

We assume that maximum likelihood (ML) decoding is used. Since we want to test whether the communication is anytime reliable, we focus on the probability of the event that the earliest wrongly decoded message is d time slots ago. Denoting this probability by $P_{t,d}^e$, we use the union bound to upper bound $P_{t,d}^e$:

$\begin{array}{l}\hfill P_{t,d}^e\le \sum _{c\in {\mathcal{C}}_{t,d}}P(\text{0 is decoded as}c),\end{array}$

where ${\mathcal{C}}_{t,d}$ is the set of codewords whose earliest nonzero symbol occurs at time t − d, and we assume that an all-zero sequence is transmitted.

It was shown in Ref. [171] that the error probability of ML decoding is bounded by

$\begin{array}{l}\hfill P(0\text{is decoded as}c)\le {\zeta }^{\parallel c\parallel },\end{array}$

where ζ is the Bhattacharya parameter, which is defined as (here we assume a discrete channel output alphabet $\mathcal{Z}$)

$\begin{array}{l}\hfill \xi =\sum _{z\in \mathcal{Z}}\sqrt{p(z|X=0)p(z|X=1)}.\end{array}$

Hence according to the union bound in Eq. (8.148), we have

$\begin{array}{l}\hfill P_{t,d}^e\le \sum _{w_{min,d}^t\le w\le nd}{N}_{w,d}^t{\zeta }^2,\end{array}$

where w is the weight of decoder output c, $N_{w,d}^t$ is the number of codes in ${\mathcal{C}}_{t,d}$ having weight w, and $w_{min,d}$ is the minimum weight of the codes in ${\mathcal{C}}_{t,d}$. The reason why w ≤ nd is that there is no error before the t − dth message. This motivates the following definition:

The first requirement on the full rank of H_n, R is to guarantee that the encoding procedure is invertible. The second condition implies

$\begin{array}{l}\hfill P_{t,d}^e\le \eta 2^{-\alpha \left({log}_2\left(\frac{1}{\zeta }\right)-\theta \right)},\end{array}$

where

$\begin{array}{l}\hfill \eta ={\left(1-2^{{log}_2\left(\frac{1}{\zeta }\right)-\theta }\right)}^{-1}.\end{array}$

Based on the above discussion, we have the following proposition:

Code construction

Now the challenge is how to construct a linear code satisfying the requirement of (α, θ, d₀)-anytime distance. In Ref. [170], the following Toeplitz structure was considered:

$\begin{array}{l}\hfill {\mathbf{H}}_{n,R}^{TZ}=\left(\begin{array}{lllll}\hfill H_1\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill \cdots \hfill \\ \hfill H_2\hfill & \hfill H_1\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill ⋮\hfill \\ \hfill H_r\hfill & \hfill H_{r-1}\hfill & \hfill \cdots \hfill & \hfill H_1\hfill & \hfill \cdots \hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill \\ \hfill \hfill \end{array}\right),\end{array}$

which assures the causality of the coding procedure.

Then a random construction approach for ${\mathbf{H}}_{n,R}^{TZ}$ is proposed in Procedure 10.

The main theorem in Ref. [170] shows that the above construction results in an anytime reliable code with a large probability.

The detailed proof of this theorem in Ref. [170] is quite involved. In this book, we provide an intuitive sketch of the proof. Consider time slot t. Suppose that an all-zero codeword is sent and consider a codeword c≠0. If $H_{r,R}^t\mathbf{c}=0$, then c may be confused with the correct one, which results in a decoding error. Due to the requirement of anytime reliability, we are interested in the locations of errors (or equivalently the nonzero elements of c). Since we require that the messages before time t − d be correctly decoded, we have

$\begin{array}{l}\hfill \left\{\begin{array}{l}\mathbf{c}(\tau )=0,\forall \tau \le t-d,\\ \mathbf{c}(t-d+1)\ne 0\\ {\mathbf{H}}_{n,R}^t\mathbf{c}=0,\end{array}\right.\end{array}$

where c = (c₀, …, c_t). This is equivalent to

$\begin{array}{l}\hfill \left(\begin{array}{lllll}\hfill H_1\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill \cdots \hfill \\ \hfill H_2\hfill & \hfill H_1\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill ⋮\hfill \\ \hfill H_r\hfill & \hfill H_{r-1}\hfill & \hfill \cdots \hfill & \hfill H_1\hfill & \hfill \cdots \hfill \end{array}\right)\left(\begin{array}{l}\hfill c_{t-d+1}\hfill \\ \hfill c_{t-d+2}\hfill \\ \hfill ⋮\hfill \\ \hfill c_t\hfill \end{array}\right)=\left(\begin{array}{l}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill ⋮\hfill \\ \hfill 0\hfill \end{array}\right),\end{array}$

which can be rewritten as

$\begin{array}{l}\hfill \left(\begin{array}{lllll}\hfill C_{1-d+1}\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill \cdots \hfill \\ \hfill C_{t-d+2}\hfill & \hfill C_{t-d+1}\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill ⋮\hfill \\ \hfill C_t\hfill & \hfill C_{t-1}\hfill & \hfill \cdots \hfill & \hfill C_{t-d+1}\hfill & \hfill \cdots \hfill \end{array}\right)\left(\begin{array}{l}\hfill h_1\hfill \\ \hfill h_2\hfill \\ \hfill ⋮\hfill \\ \hfill h_d\hfill \end{array}\right)=\left(\begin{array}{l}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill ⋮\hfill \\ \hfill 0\hfill \end{array}\right),\end{array}$

where $h_i=\mathrm{vec}(H_i^T)$ and $C_i=\mathrm{diag}(c_i^T,\dots ,c_i^T)$. Since H₁ has been fixed in the construction procedure, we have

$\begin{array}{l}\hfill \left(\begin{array}{lllll}\hfill C_{1-d+1}\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill \cdots \hfill \\ \hfill C_{t-d+2}\hfill & \hfill C_{t-d+1}\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill ⋮\hfill \\ \hfill C_{t-1}\hfill & \hfill C_{t-2}\hfill & \hfill \cdots \hfill & \hfill C_{t-d+1}\hfill & \hfill \cdots \hfill \end{array}\right)\left(\begin{array}{l}\hfill h_2\hfill \\ \hfill h_3\hfill \\ \hfill ⋮\hfill \\ \hfill h_d\hfill \end{array}\right)=\left(\begin{array}{l}\hfill C_{t-d+2}\hfill \\ \hfill C_{t-d+3}\hfill \\ \hfill ⋮\hfill \\ \hfill C_t\hfill \end{array}\right)h_1,\end{array}$

and C_t−d+1h₁ = 0. We abbreviate Eq. (8.162) to

$\begin{array}{l}\hfill \mathbf{C}\mathbf{h}={\mathbf{C}}^{\prime }{\mathbf{h}}_1.\end{array}$

Hence the higher dimensional vector h cannot be arbitrarily chosen due to the linear constraint in Eq. (8.163). So h must be selected within a lower dimensional subspace. Since {h_i}, i = 2, …, t, are randomly chosen, the corresponding probability that h falls in a lower dimensional subspace can be bounded by the following lemma:

The detailed evaluation of the upper bound will lead to the desired conclusion.

Construction of potent tree codes

In Ref. [174], the existence of good tree code with large relative Hamming distance is only assumed; the detailed construction of the code is not discussed. It was not until recent years that the explicit construction of the tree code was discussed [175], in which some intuitions were provided at the beginning. Since the random coding scheme has achieved great success in traditional information theory, the first idea for the code construction is to try the random coding scheme; i.e., we randomly assign output alphabets to each edge in the tree. This looks reasonable, since we require two paths in the tree with large discrepancies (as illustrated in Fig. 8.14A); otherwise it is hard to distinguish the two trajectories V P′ and V P. Since the outputs are randomly assigned, the output sequences should have a large Hamming distance with a large probability.

However, this is not the only requirement. We should let short divergent paths in the tree have sufficiently large Hamming distances. This nontrivial requirement is illustrated in Fig. 8.14B. Suppose that the transmission errors make the pebbles diverge from the correct path to wrong locations A, A′, B, B′. Assume that these short divergent paths have small relative Hamming distances. Then it is possible that the agents keep making mistakes due to the small relative Hamming distances. For example, the agent may be distracted to the wrong location A and return to the correct path after recognizing the mistake; however, it makes a mistake soon after and diverges to A′. In the subsequent procedure, the agent keeps falling into wrong locations such as B and B′. Hence in Ref. [174] it is required that all paths have large Hamming distances.

However, it is not necessary to require all paths to have large Hamming distances, which incurs too many constraints. It is argued in Ref. [175] that we can allow some branches in the tree to have small relative Hamming distances. As illustrated in Fig. 8.14C, each path from the root to a leaf is allowed to have some small diverged branches that have small relative Hamming distances. It is shown in Ref. [175] that this requirement can assure the success of protocol simulation.

To quantify the above requirement on the tree code, we need the following definition of a potent tree code:

For a detailed construction of potent tree code, it is proposed in Ref. [175] to use the ϵ-biased sample space, which is defined as follows:

It is shown in Ref. [175] that an ϵ-biased sample space can be constructed as follows: consider a prime p > (n/ϵ)²; a point in S is given by a number x in [0, 1, …, p − 1] mapped to the n-bit sequence (r₀(x), …, r_n−1(x)), where

$\begin{array}{l}\hfill r_i(x)=\frac{1-{\chi }_p(x+i)}{2},\end{array}$

and χ_p(x) denotes the quadratic character of x (mod p).

Once an ϵ-biased sample space S is constructed, we can use it to build an (ϵ, α)-potent tree code. For simplicity, we assume that the output of each edge in the tree is binary. Since there are a total of d^N edges in a d-ary tree, the outputs of all edges in the tree can be described by a d^N-bit sequence: we sort the edges in the tree in a predetermined order and then assign each element in the sequence to an edge. This forms a d-ary small biased tree code.

Small biased tree codes have a useful property defined as follows:

The intuitive explanation of the property of (ϵ, k)-independence is that the corresponding sequence is very close to uniformly distributed for any k-subset. It is shown in Ref. [175] that if a sample space is ϵ-biased then it is also ((1 − 2^−k)ϵ, k)-independent, for any k. This property guarantees that, with a large probability, the small divergent branches in a small biased tree code have reasonable relative Hamming distances, since their bit assignments are “very random.”

In Ref. [175], the following theorem guarantees that the construction of small biased tree codes leads to potent tree codes, with a large probability:

The detailed proof is given in Ref. [175]. Here we provide a brief summary of the basic idea of the proof. Consider a node v. It is possible that there exists another node u having the same depth such that u forms a bad interval of l. To that end, we need to check the last l bits leading to v and u, denoted by W_l(v) and W_l(u), respectively. Due to the property of small biasedness in Definition (26), the Hamming distance between W_l(v) and W_l(u) should be large with a large probability. As will be shown later, potent tree codes can accomplish the task of iterative communications.

Explicit construction of tree codes

In the above discussion, the construction of potent tree codes is based on a random coding scheme. It is of substantial theoretic importance since it can prove the existence of potent tree codes. However, it is of no use in practice due to the complexity caused by the lack of efficient coding and decoding schemes.

A breakthrough in the deterministic and efficient construction of tree codes was made by Braverman [176]. The corresponding cost of computation time is subexponential; i.e., the time costs of code construction, encoding, and decoding are all $2^{n^{ϵ}}$ for a tree code with size n, where ϵ is a small number.

In this book, we focus on the deterministic construction of tree code. The corresponding coding and decoding complexities can be found in Ref. [176]. The basic idea of tree code construction is to combine multiple small-sized tree codes and then obtain a large-scale tree code. To that end, we introduce an operation called tree code product, i.e., we construct a tree code with depth d₁ × d₂ from two tree codes having depths d₁ and d₂.

First we assume that a tree code with depth d has been constructed. Here we assume that d is small such that we can use exhaustive search to find the tree code. Then we convert it to a local tree code of depth D ≫ d and locality l. Note that a local tree code with depth D and locality l, as well as other parameters, is defined as follows:

The construction of the local tree code with a much larger depth D is carried out by repeating the mapping $\mathcal{T}$ provided by the original tree code with a much smaller depth d. It is shown in Ref. [176] that this construction satisfies the requirement for local tree code.

Based on the conversion from a tree code to a local tree code with much larger depth, we can combine two tree codes with smaller depths to obtain a new tree code with a larger depth, which is stated in the following theorem:

The procedures of code construction and encoding are illustrated in Fig. 8.15. Essentially, the encoding is a concatenation of an inner code ${\mathcal{T}}_i^{\prime }$ and an outer code T_o′. The inner code ${\mathcal{T}}_i^{\prime }$ is a local tree code, which is obtained from ${\mathcal{T}}_i$. It takes care of the divergent paths whose divergence is short. Then the coding output is fed into the outer code T_o′, which takes care of longer paths. ${\mathcal{T}}_o^{\prime }$ is obtained from an intermediate code ${\mathcal{T}}_o^{″}$. Simply speaking, ${\mathcal{T}}_o^{″}$ is obtained by spreading ${\mathcal{T}}_o$ over different blocks. Then the output of ${\mathcal{T}}_o^{″}$ is protected by traditional error correction codes, thus forming ${\mathcal{T}}_o^{\prime }$. The details of the construction can be found in Ref. [176].