0
$\begingroup$

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!

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.