Score:0

How to build a syndrome trellis from the parity check matrix

bd flag

Background

In the paper "Minimizing Embedding Impact in Steganography using Trellis-Coded Quantization" and in this question on this forum, a so called Syndrome Trellis is built from a parity check matrix. The figure below shows the example from the paper, where the trellis on the right is built from matrix $\hat{\mathbb{H}}$.

Example of Syndrome Trellis from paper1

Question

Why does the edge from trellis column $1$ to $2$ go from state $00$ to $10$? I would have expected it to go from state $00$ to $01$, as the second column of $\hat{\mathbb{H}}$ is $\left(\begin{matrix} 0 \\ 1 \end{matrix}\right)$ and $00 \oplus 01 = 01$.

Any help would be highly appreciated!

ph flag
If you have come up with an answer, you can move it to an answer below. It's ok to answer your own question.
Score:1
bd flag

Alright, so I think, I figured it out: The states seem to store the current value of the syndrome, so of $\mathbf{m}=\mathbb{H}y$, where the least significant bit of the state corresponds to that entry of $\mathbf{m}$ with the smallest index that is currently affected by the calculation.

In the example:

From trellis column $p_0$ to $1$:

The structure of $\mathbb{H}$ is such that only $\mathbb{m}_1$ and $\mathbb{m}_2$ can change, if $y_1$ is assigned a value.

  • State $00$ means: currently, both $\mathbb{m}_1$ and $\mathbb{m}_2$ are $0$. If $y_1=0$ nothing changes. If $y_1 =1$, then the partial syndrome reads $\mathbb{m}_1=1$ and $\mathbb{m}_2=1$. Thus, we go to state $11$.

From trellis column $1$ to $2$:

Still, only $\mathbb{m}_1$ and $\mathbb{m}_2$ are affected by the assignment of a value to $y_2$.

  • State $00$ means: currently, both $\mathbb{m}_1$ and $\mathbb{m}_2$ are $0$. If $y_2=0$ nothing changes. If $y_2 =1$, then the partial syndrome reads $\mathbb{m}_1=0$ and $\mathbb{m}_2=1$. Thus, we go to state $10$. This corresponds to evaluating $00 \oplus 10 = 10$, where the second column $\left(\begin{matrix} 0 \\ 1 \end{matrix}\right)$ of $\hat{\mathbb{H}}$ is interpreted as $10$ to match the states.
  • State $11$ means: currently, both $\mathbb{m}_1$ and $\mathbb{m}_2$ are $1$. If $y_2=0$ nothing changes. If $y_2=1$, the the partial syndrome reads $\mathbb{m}_1 = 1$ and $\mathbb{m}_2 = 0$, which corresponds to state $01$.

From trellis column $2$ to $p_1$:

$\mathbb{m}_1$ cannot be affected anymore, so the least significant bit of the state now stores the current value of $\mathbb{m}_2$ and the second least significant bit the one of $\mathbb{m}_3$.

Though it is still unclear to me why this is done in this manner, I am happy to have figured that the states encode $\mathbb{m}$ with the least significant bit corresponding to the current entry of $\mathbb{m}$.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.