# How does Syndrome-Trellis Code (STC) work?

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": You have to add or not add the following column using an XOR operation. Let me explain the first states.

From $$p_0$$ to $$1$$:

We are in the $$00$$ state, if we do nothing, we continue in the $$00$$ state. But if we add $$11$$ (first H column) we go to state $$11 = 00 \oplus 11$$.

From $$1$$ to $$2$$:

If we are in the $$00$$ state and we do nothing, we continue in the 00 state, but if we add $$10$$ (second H column) we go to state $$10 = 10 \oplus 00$$. If we are in the $$11$$ state and we do nothing, we continue in the $$11$$ state, but if we add $$10$$ (second H column) we go to state $$01 = 10 \oplus 11$$.

From $$p_1$$ to $$3$$:

If we are in the $$00$$ state and we do nothing, we continue in the $$00$$ state, but if we add $$11$$ (third H column) we go to state $$11 = 00 \oplus 11$$. If we are in the $$01$$ state and we do nothing, we continue in the $$01$$ state, but if we add $$11$$ (third H column) we go to state $$10 = 01 \oplus 11$$).

And the same with the following states.

• Thanks for the explanation! Aug 5 at 10:45