Syndrome-trellis code was introduced to minimize embedding distortion in steganography. See this paper: Minimizing Embedding Impact in Steganography using Trellis-Coded Quantization.
Background information
The following paragraph can be found on this website:
Syndrome-trellis codes are essentially binary linear convolutional
codes represented by parity-check matrix. This representation allows
to use them for information embedding problems, where no channel code
is required.
The diagram below shows an example of STC taken from the paper. It was said that the goal is to find a vector
$y$ such that
$Hy=m$ where
$H$ is the shared parity-check matrix between the sender and receiver, and
$m$ is the secret message to be communicated. I understood the vector
$y$ as the resulting stego-image that will be communicated to the receiver, whom will then be able to extract
$m$ using the shared
$H$.
Each
$y$ satisfying
$Hy=m$ is represented as a path through the trellis, where the path starts in the leftmost all-zero state and extends to the right. The path shows the step-by-step calculation of the (partial) syndrome using more and more bits of
$y$. For example, the first two edges in Figure 2, that connect the state 00 from column
$p0$ with states 11 and 00 in the next column, correspond to adding
$(y1 = 1)$ or not adding
$(y1 = 0)$ the first column of
$H$ to the syndrome, respectively. In general, we call the state in the trellis *reachable*, if there is a path connecting this state with the leftmost all-zero state.
I do not understand this part of the paper named at the top (p. 5):
From each reachable state, two edges extend to the right; they correspond to adding or not adding the next column of matrix H to the current partial syndrome and are labeled 1 and 0, respectively. The edge labels along the path in the trellis thus correspond to individual bits of the stego object y.
Question
How does the reachable state extend to the right? It was said that there are only 2 extensions per reachable state and each correspond to adding/not adding the next column of matrix
H and are labelled 1 and 0 respectively. For the column
$p0$, it was extended to state 00 and 11. The state 11 is to add the first column "11" of the matrix
H? However, in the next column to the right of
$p0$ at state 00, the node extends to state 00 and state 10. Why does it extend to 10 and not 01 since 01 is the next column of the matrix
H?
Figure 2, from p. 7 of "Minimizing Embedding Impact in Steganography using Trellis-Coded Quantization":
