跳到主要内容

Hamming 码

经典​

定义生成矩阵

G=(0001111011001110101011111111)G=\left(\begin{array}{lllllll}0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)

称它的行向量构成的空间为 CC，包含 16 个码字。它的补空间是

C⊥={x∣x⋅c=0∀c∈C}C^{\perp}=\{x \mid x \cdot c=0 \forall c \in C\}

对应的生成矩阵是

H=(000111101100111010101)H=\left(\begin{array}{lllllll}0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)

它们具有性质 GHT=0GH^T=0。

定理​

一个码 CC 如果码字间最小的非零距离是 dd，那么码可以校正 t=(d−1)/2t=(d-1)/2 个错误，检出 d−1d-1 个错误。

编码过程​

将 m 编码为 mGmG

解码过程​

设收到的信息为 r=mG+er=mG+e，则

rHT=(mG+e)HT=eHTr H^{T}=(m G+e) H^{T}=e H^{T}

则结果对应于 HTH^T 的某一行，通过这个信息可以得出 ee。

量子​

编码过程​

∣0⟩L=18∑c∈H∣c⟩|0\rangle_{L}=\frac{1}{\sqrt{8}} \sum_{c \in H}|c\rangle ∣1⟩L=18∑c∈H∣c⊕1111111⟩|1\rangle_{L}=\frac{1}{\sqrt{8}} \sum_{c \in H}|c \oplus 1111111\rangle

解码过程​

计算特征：

(b4⊕b5⊕b6⊕b7,b2⊕b3⊕b6⊕b7,b1⊕b3⊕b5⊕b7)\left(b_{4} \oplus b_{5} \oplus b_{6} \oplus b_{7}, \quad b_{2} \oplus b_{3} \oplus b_{6} \oplus b_{7}, \quad b_{1} \oplus b_{3} \oplus b_{5} \oplus b_{7}\right)

可以判断出哪个位出现翻转错误。类似地，由于这种码对 n 元 Hadamard 变换具有不变性

H⊗7∣0⟩L=12(∣0⟩L+∣1⟩L)H^{\otimes 7}|0\rangle_{L}=\frac{1}{\sqrt{2}}\left(|0\rangle_{L}+|1\rangle_{L}\right) H⊗7∣1⟩L=12(∣0⟩L−∣1⟩L)H^{\otimes 7}|1\rangle_{L}=\frac{1}{\sqrt{2}}\left(|0\rangle_{L}-|1\rangle_{L}\right)

同理，一个逻辑的 σx\sigma_x 即是 σx7\sigma_x^7，σz\sigma_z 也是如此。

符号翻转错误可以用两种方式