参考书：隐写学原理与技术 第11章 校验子格编码
两篇原始论文：
Minimizing Embedding Impact in Steganography using Trellis-Coded Quantization
Minimizing Additive Distortion in Steganography using Syndrome-Trellis Codes
STC toolbox
CSDN输入公式
背景：
已有的隐写编码局限性：
- 矩阵编码和GLSBM在分组上进行优化，但不能进行全局优化。
- 湿纸编码提取方程难构造。
校验子格编码STC基本解决以上问题，提供了求解加性模型PLS（限负载求最小失真）问题方法。
STC基本思想
STC的校验矩阵是由子矩阵排列成的带状阵，避免构造高维线性提取方程，基于局部性质进行优化，提前排除不可能达到最优的构造路线，最后选择全部满足局部提取方程，并且失真（嵌入次数或失真函数定义与隐写安全相关的指标）总和最低的构造路线。
STC类似于通信中的卷积码viterbi解码。
viterbi编码思想介绍：如何通俗地讲解 viterbi 算法？（知乎）
B站 【信息论基础】第7章有噪信道编码—卷积码
B站 国防科技大学-信息论与编码基础（国家级精品课）P65-66
STC算法描述
STC算法产生目标向量(最优涉密载体)y、奇偶校验矩阵H：
- 使式子 H y T = m Hy^{T}=m HyT=m 成立
- 寻找向量
y
y
y，使下列式子（失真和）最小，
D
(
x
,
y
)
D(x,y)
D(x,y) 为
x
x
x 和
y
y
y 之间的（汉明）距离
- m是要传递的秘密消息，长度为b，即 m = m 1 m 2 m 3 . . . m b m=m_1m_2m_3...m_b m=m1m2m3...mb
H为校验矩阵，由高为
h
h
h，宽为w的基础矩阵
H
^
h
×
w
\hat{H}_{h×w}
H^h×w生成。（涉密）原始载体的长度为
n
n
n ,
n
=
w
∗
b
n =w* b
n=w∗b。
基础矩阵
H
^
h
×
w
\hat{H}_{h×w}
H^h×w为
将基础矩阵按照对角线方向不断重复，得到下面的校验矩阵H。最后几次复制不完整，但不影响校验和提取。
STC编码可以看作通过逐步修改x或者逐步构造y，使得
H
y
T
=
m
Hy^{T}=m
HyT=m 并满足失真和最小。在逐步构造提取方程时，STC 每次通过新加入
w
w
w 个
y
y
y 中元素传输一个消息比特m，依次构造以下等式并记录其有效解
y
j
y_j
yj，与修改叠加量
e
j
e_j
ej;
由于矩阵H的特殊形式，根据矩阵乘法原理
H
y
T
=
m
Hy^{T}=m
HyT=m， 只有向量的 前w 比特能影响消息 m 的第一比特（第1子块），同样，m 的第二比特仅受 y 的 前2w 比特的影响，m的第三比特仅受 y 的第 w+1 位至第 3w 位的比特影响，以此类推。
STC算法格子图构成
为了描述STC算法，需要先介绍格子图的组成。
(1)子块。格子图包含m个子块，依次代表
H
m
×
n
H_{m×n}
Hm×n中对角线方向相应子矩阵
H
^
h
×
w
\hat{H}_{h×w}
H^h×w的处理；每个子块有
q
n
q^n
qn行w+1列，子块中两个相邻列上的节点由连线从左向右连接。
(2)位置(列编号)。除了每个子块的第一列，格子图的所有列依次编号为{1，2，…，n}，表示当前考虑修改的载体位置；每个子块的首列仅包括子块的局部校验子初态，因此，第i个子块的首列用
p
i
p_i
pi标识。
(3)局部校验子(行编号)。每行依次编号为{0，1，···，
q
n
q^n
qn-1}，一般用q进制表示当前得到的局部校验子(partialsyndrome)，即当前子块计算能够影响到的m中子段；注意局部校验子值是低位靠右，对应局部校验子向量的上部。
(4)节点。每个子块节点表示一个路径上阶段性的状态集合，它反映了一个阶段点上的位置、局部校验子与失真等的状态；连线通过的节点为可达节点；在两个子块间，按照当前考察区域上是否满足
(
H
y
)
i
=
m
i
(Hy)_i=m_i
(Hy)i=mi的原则选择可达节点进入下一子块的第一列，下一子块对应在下一区域隐藏下一个消息符号，当前局部校验子状态低位删除高位补0，因此子块首列节点总表示子块计算之前的初态集合。
(5)失真(节点标注)。节点上记录的数字表示连线上所表示嵌入方法当前的总失真(代价)，即截至目前连线上前面修改的加性失真总和；编码算法将适时比较各个节点上的失真状态，及时删除那些到达同一节点上失真更大或者相同的路径。
(6)连线。子块内每个可达节点的q个分支代表不同嵌入方法，这使得
e
i
e_i
ei不同；子块间的连线仅表示有效状态节点进入下一子块。注意，连线的方向并不表示特定的修改方式，它仅连接
y
i
y_i
yi当前的状态以及不修改或者修改后的状态；虚线表示删除的路径。
以上第i个子块图通过w层的发展确保了
m
i
m_i
mi可通过
H
y
=
m
Hy=m
Hy=m提取，
y
i
y_i
yi决定了是否以及如何将H的第i列加到校验子中。
具体例子
本节介绍的STC算法以载体系数修改数量作为秘密信息的嵌入代价衡量指标。
在 x = 10110001 x=1011 0001 x=10110001 中嵌入 m = 0111 m=0111 m=0111 ，求 y y y（也就是修改后的 x x x），失真为修改次数
-
对第1子块的处理：最初状态为0，从 p 0 p_0 p0列的00状态出发，此时失真为0。
00状态二分发展： 若 y 1 y_1 y1不修改，即保持原来的 x 1 x_1 x1，也就是1，对应将H的第1列加入校验子，进入 [ 1 1 ] \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} [11]（也就是11）状态，失真和 e 1 e_1 e1为0；若修改 y 1 y_1 y1，即把 x 1 x_1 x1改为0，对应不将H的第一列加入校验子，维持 [ 0 0 ] \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix} [00]（也就是00）状态，失真和 e 1 e_1 e1为1。
不修改 y 1 y_1 y1的11状态继续二分发展： 若保持 y 2 y_2 y2不修改，即保持原来的 x 2 x_2 x2，也就是0，对应不将H的第2列 [ 1 0 ] \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} [10]加入校验子，进入 [ 1 1 ] \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} [11]+ [ 0 0 ] \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix} [00]= [ 1 1 ] \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} [11]状态（这里的加号可理解为异或⊕），失真和 e 2 e_2 e2为0；若修改 y 2 y_2 y2，即把 x 2 x_2 x2改为1，对应将H的第2列 [ 1 0 ] \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} [10]加入校验子，进入 [ 1 1 ] \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} [11]+ [ 1 0 ] \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} [10]= [ 0 1 ] \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix} [01]状态，失真和 e 2 e_2 e2为1。修改 y 1 y_1 y1的00状态继续二分发展： 若保持 y 2 y_2 y2不修改，即保持原来的 x 2 x_2 x2，也就是0，对应不将H的第2列 [ 1 0 ] \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} [10]加入校验子，进入 [ 0 0 ] \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix} [00]+ [ 0 0 ] \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix} [00]= [ 0 0 ] \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix} [00]状态，失真和 e 2 e_2 e2为1；若修改 y 2 y_2 y2，即把 x 2 x_2 x2改为1，对应将H的第2列 [ 1 0 ] \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} [10]加入校验子，进入 [ 0 0 ] \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix} [00]+ [ 1 0 ] \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} [10]= [ 1 0 ] \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} [10]状态，失真和 e 2 e_2 e2为2。
这样就完成了对第一子块的处理。 m 1 m_1 m1为0，因此只有 [ 0 0 ] \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix} [00]和 [ 0 1 ] \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix} [01]状态可以进入下一子块，因为这两个状态满足低位为 0 的要求，失真和分别为1和2。
注意：这里的局部校验子是低位靠右，对应校验子向量的上部。如H的第二列向量（第1子块内） [ 0 1 ] \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix} [01] 对应的校验子是10。文章来源：https://www.toymoban.com/news/detail-448848.html
-
对第2子块的处理：对上面的
[
0
0
]
\begin{bmatrix} 0 \\ 0 \\ \end{bmatrix}
[00]和
[
0
1
]
\begin{bmatrix} 0 \\ 1 \\ \end{bmatrix}
[01]状态，删除低位（这里是0），在高位补0，分别进入
[
0
0
]
\begin{bmatrix} 0 \\ 0 \\ \end{bmatrix}
[00]和
[
1
0
]
\begin{bmatrix} 1 \\ 0 \\ \end{bmatrix}
[10]状态，失真和分别为1和2。
00状态二分发展： 若保持 y 3 y_3 y3不修改，即保持原来的 x 3 x_3 x3，也就是1，对应将H的第3列 [ 1 1 ] \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} [11]加入校验子，进入 [ 0 0 ] \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix} [00]+ [ 1 1 ] \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} [11]= [ 1 1 ] \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} [11]状态，失真和 e 3 e_3 e3为1；若修改 y 3 y_3 y3，即把 x 3 x_3 x3改为0，对应不将H的第3列加入校验子，维持 [ 0 0 ] \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix} [00]状态，失真和 e 3 e_3 e3为2。
01状态二分发展： 若保持 y 3 y_3 y3不修改，即保持原来的 x 3 x_3 x3 ，也就是1，对应将H的第3列 [ 1 1 ] \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} [11]加入校验子，进入 [ 1 0 ] \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} [10]+ [ 1 1 ] \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} [11]= [ 0 1 ] \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix} [01]状态，失真和 e 3 e_3 e3为2；若修改 y 3 y_3 y3，即把 x 3 x_3 x3改为0，对应不将H的第3列 [ 1 1 ] \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} [11]加入校验子，维持 [ 1 0 ] \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} [10]状态，失真和 e 3 e_3 e3为3。
–
上面的四种状态再分别二分发展：（为了后续表述方便，校验子不再写成向量形式）
11状态二分发展（此时失真和 e 3 e_3 e3为1）： 若保持 y 4 y_4 y4不修改，即保持原来的 x 4 x_4 x4，即1，对应将H的第4列10加入校验子，进入11+10=01状态，失真和 e 4 e_4 e4为1；若修改 y 4 y_4 y4，即把 x 4 x_4 x4改为0，对应不将H的第4列10加入校验子，维持11状态，失真和 e 4 e_4 e4为2。
00状态二分发展（此时失真和 e 3 e_3 e3为2）： 若保持 y 4 y_4 y4不修改，即保持原来的x_4，即1，对应将H的第4列10加入校验子，进入00+10=10状态，失真和 e 4 e_4 e4为2；若修改 y 4 y_4 y4，即把 x 4 x_4 x4改为0，对应不将H的第4列10加入校验子，维持00状态，失真和 e 4 e_4 e4为3。（失真和较大，被删除，用图中虚线表示）
10状态二分发展（此时失真和 e 3 e_3 e3为2）： 若保持 y 4 y_4 y4不修改，即保持原来的 x 4 x_4 x4，即1，对应将H的第4列10加入校验子，进入10+10=00状态，失真和 e 4 e_4 e4 为2；若修改 y 4 y_4 y4，即把 x 4 x_4 x4改为0，对应不将H的第4列10加入校验子，维持10状态，失真和 e 4 e_4 e4 为3。（失真和较大，被删除）
01状态二分发展（此时失真和 e 3 e_3 e3为3）： 若保持 y 4 y_4 y4不修改，即保持原来的 x 4 x_4 x4，即1，对应将H的第4列10加入校验子，进入01+10=11状态，失真和 e 4 e_4 e4为3（和上面的11状态相比，被删除）；若修改 y 4 y_4 y4，即把 x 4 x_4 x4改为0，对应不将H的第4列10加入校验子，维持01状态，失真和 e 4 e_4 e4为4。（失真和较大，被删除）
此时第二子块处理完毕。 m 2 m_2 m2为1，选择满足低位为1的状态，也就是01和11，失真和分别为1和2，其他路径被剪去。 - 对第3子块进行处理：对上面的01和11状态，删除低位（这里是1），在高位补0，分别进入00和01状态，失真和分别为1和2。再进行上述类似步骤；
- 最后一个子块不完整，使用时在高位补0 ，即第7列为 [ 1 0 ] \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} [10]，也就是01；第8列为 [ 0 0 ] \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix} [00]，也就是00；继续进行上述类似步骤；
- 对所有子块处理完毕后，找到失真和最小的路径，进行回溯，得到修改载体，如图所示。
STC解码
由于 H y T = m Hy^{T}=m HyT=m，STC 的解码过程就是用 带状矩阵 H H H 逐行乘以 y y y 并逐元素输出 m m m 的过程。发送方与接收方共享STC编码中的校验矩阵，接收方通过校验矩阵与载密图像相乘提取秘密消息。但实验表明，存在一个小的概率使 STC在嵌入时无法得到可行解，从而导致嵌入失败，不过这一般可以通过减少消息量或更换位置置乱密钥解决。文章来源地址https://www.toymoban.com/news/detail-448848.html
到了这里，关于【学习笔记】STC校验子格编码 syndrome-trellis code的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
