Skip to main content
Bumped by Community user
deleted 1651 characters in body
Source Link

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!

Answer

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

In the example:

From trellis column $p_0$ to $1$:

  • 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$:

  • 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 be, 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}$.

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!

Answer

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

In the example:

From trellis column $p_0$ to $1$:

  • 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$:

  • 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 be, 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}$.

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!

added 1649 characters in body
Source Link

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!

Answer

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

In the example:

From trellis column $p_0$ to $1$:

  • 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$:

  • 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 be, 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}$.

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!

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!

Answer

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

In the example:

From trellis column $p_0$ to $1$:

  • 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$:

  • 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 be, 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}$.

Source Link

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

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!