Hamming符号
Hamming code
$ \mathbb{F}_q上の$ m − 1次元射影空間 $ \mathrm{PG}(m − 1, q)と表記する
以下を満たす集合
集合$ \mathbb{F}_{q}^{m} \backslash\{\mathbf{0}\}である
$ \mathbb{F}_{q}^{m} \backslash\{\mathbf{0}\}は、$ \mathbb{F}^m_qから$ \mathbf{0} = (0,\cdots, 0)を除いたを集合
$ 0が$ m個並んでいるmrsekut.icon
非零定数倍のベクトルを同一視して1点とみなしたものである
「非零定数倍のベクトルを同一視して1点とみなす」とは
$ \mathbf{a, b} ∈ \mathbb{F}_{q}^{m} \backslash\{\mathbf{0}\}に対して
「$ \mathrm{PG}(m − 1, q)の点として$ \boldsymbol{a}=\boldsymbol{b}」$ \Leftrightarrow「$ \exists \lambda \in \mathbb{F}_{q} \backslash\{0\} ; \boldsymbol{a}=\lambda \boldsymbol{b}」
このとき、$ \mathrm{PG}(m − 1, q)が含む点の個数$ \theta_{m−1}は以下で求まる
$ \theta_{m-1}=\frac{q^{m}-1}{q-1}=q^{m-1}+q^{m-2}+\cdots+q+1
$ \mathrm{PG}(m − 1, q)から検査行列$ Hを作る 2以上の整数$ mに対して、$ \mathrm{PG}(m − 1, q)の各点を表すベクトルを1つずつ選ぶ
それら全てを列として並べて行列を作る
$ H=\left[\boldsymbol{h}_{1}, \boldsymbol{h}_{2}, \ldots, \boldsymbol{h}_{n}\right]
$ \left\{{ }^{t} \boldsymbol{h}_{1}, \cdots,{ }^{t} \boldsymbol{h}_{n}\right\}=\operatorname{PG}(m-1, q)
$ n=\theta_{m-1}
$ s(H)=2
これの実演が例14.1
余次元$ mの$ q元Hamming符号
$ \mathrm{Ham}(m, q)と表記する
$ H を検査行列とする$ [n = θ_{m−1}, n−m, 3]_q 符号のこと 余次元mの2元Hamming符号
$ \mathrm{Ham}(m,2)と表す
3以上の整数$ mを用いて$ 1\sim2^m-1を$ mbitの2進数で表現し、それを列ベクトルとして昇順に並べたもの
例
$ m=3の時
$ H= \begin{pmatrix}0&0&0&1&1&1&1 \\ 0&1&1&0&0&1&1 \\ 1&0&1&0&1&0&1\end{pmatrix}.
列ベクトルが左から2進数で1, 2, .. , 7になっている
2元Hamming符号$ H_7
ベン図を用いることで誤り訂正ができる
$ u_1u_2...u_7を以下のようにベン図に書く
A,B,Cそれぞれの中で$ \Sigma c_i\equiv0 \pmod 2が成り立つ
https://image.slidesharecdn.com/slide-140829072757-phpapp01/95/-30-638.jpg?cb=1409297332