奇偶检验矩阵

编码理论里,线性区块码 C奇偶检验矩阵(英语:parity-check matrix)是描述码字英语codeword的成分间必须满足的线性关系的一个矩阵。它可以用来决定一个特定向量是否为码字,也用在解码算法中。

定义

形式上,线性码 C 的奇偶检验矩阵 H对偶码 C生成矩阵。这就意味着当且仅当矩阵-向量乘积 Hc = 0(一些作者[1]会写成其等价形式cH = 0)时,码字 c 才会在 C 中。

奇偶检验矩阵的行是奇偶检验方程的系数。[2] 也就是说,它们表示每个码字中的某些数字(成分)如何线性组合可以等于零。例如,奇偶检验矩阵

 ,

紧凑表示了向量   要成为 C 的码字必须满足的奇偶检验方程,

 .

根据定义,奇偶检验矩阵直接遵循该码的最小距离为,使得奇偶检验矩阵 H 的任意 d - 1 列都线性无关并且存在 d 列线性相关的最小数 d

建立奇偶检验矩阵

某一给定码的奇偶校验矩阵可以从其生成矩阵导出(反之亦然)。[3] 若一 [n,k] 码的生成矩阵是标准形式

 ,

则奇偶检验矩阵为

 ,

因为

 .

取反是在有限域 Fq 内进行的。注意如果所处的域的特征为 2(即在这个域中 1 + 1 = 0),如在二元码英语binary code中一样,因此 -P = P,所以取反是不需要的。

例如,如果一个二元码的生成矩阵

 ,

则其奇偶检验矩阵就是

 .

伴随式

对向量空间环境中的任意(行)向量 xs = Hx 称为 x伴随式英语Syndrome decoding。当且仅当 s = 0 时向量 x 为码字。计算伴随式是伴随式解码英语syndrome decoding算法的基础。[4]

参见

注释

  1. ^ 比如Roman 1992,p. 200
  2. ^ Roman 1992,p. 201
  3. ^ Pless 1998,p. 9
  4. ^ Pless 1998,p. 20

参考文献