# How to build a syndrome trellis from the parity check matrix

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}}$$.

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!

• If you have come up with an answer, you can move it to an answer below. It's ok to answer your own question. Commented Apr 1, 2022 at 18:27

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}$$.