「Hamming(7,4)」を編集中
この編集を取り消せます。
下記の差分を確認して、本当に取り消していいか検証してください。よろしければ変更を保存して取り消しを完了してください。
最新版 | 編集中の文章 | ||
163行目: | 163行目: | ||
シンドローム '' 'z' ''は[[ヌルベクトル(ベクトル空間)|ヌルベクトル]]なので、受信者はエラーが発生していないと判断できます。この結論は、データベクトルに '' 'G' ''を乗算すると、基底の変化が '' 'H'の[カーネル(行列)|カーネル]であるベクトル部分空間に発生するという観測に基づいています'' '。送信中に何も起こらない限り、 '' '' 'は' '' '' 'のカーネルに残り、乗算はヌルベクトルを生成します。 | シンドローム '' 'z' ''は[[ヌルベクトル(ベクトル空間)|ヌルベクトル]]なので、受信者はエラーが発生していないと判断できます。この結論は、データベクトルに '' 'G' ''を乗算すると、基底の変化が '' 'H'の[カーネル(行列)|カーネル]であるベクトル部分空間に発生するという観測に基づいています'' '。送信中に何も起こらない限り、 '' '' 'は' '' '' 'のカーネルに残り、乗算はヌルベクトルを生成します。 | ||
− | == | + | == Error correction == |
− | + | Otherwise, suppose a ''single'' bit error has occurred. Mathematically, we can write | |
− | |||
:<math>\mathbf{r} = \mathbf{x} +\mathbf{e}_i</math> | :<math>\mathbf{r} = \mathbf{x} +\mathbf{e}_i</math> | ||
− | + | modulo 2, where '''e'''<sub>''i''</sub> is the <math>i_{th}</math> [[unit vector]], that is, a zero vector with a 1 in the <math>i^{th}</math>, counting from 1. | |
− | |||
: <math>\mathbf{e}_2 = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}</math> | : <math>\mathbf{e}_2 = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}</math> | ||
− | + | Thus the above expression signifies a single bit error in the <math>i^{th}</math> place. | |
− | + | Now, if we multiply this vector by '''H''': | |
:<math>\mathbf{Hr} = \mathbf{H} \left( \mathbf{x}+\mathbf{e}_i \right) = \mathbf{Hx} + \mathbf{He}_i</math> | :<math>\mathbf{Hr} = \mathbf{H} \left( \mathbf{x}+\mathbf{e}_i \right) = \mathbf{Hx} + \mathbf{He}_i</math> | ||
− | '' 'x' '' | + | Since '''x''' is the transmitted data, it is without error, and as a result, the product of '''H''' and '''x''' is zero. Thus |
: <math> \mathbf{Hx} + \mathbf{He}_i = \mathbf{0} + \mathbf{He}_i = \mathbf{He}_i</math> | : <math> \mathbf{Hx} + \mathbf{He}_i = \mathbf{0} + \mathbf{He}_i = \mathbf{He}_i</math> | ||
+ | Now, the product of '''H''' with the <math>i^{th}</math> standard basis vector picks out that column of '''H''', we know the error occurs in the place where this column of '''H''' occurs. | ||
− | + | For example, suppose we have introduced a bit error on bit #5 | |
− | |||
− | |||
− | |||
: <math>\mathbf{r} = \mathbf{x}+\mathbf{e}_5 = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix}</math> | : <math>\mathbf{r} = \mathbf{x}+\mathbf{e}_5 = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix}</math> | ||
− | [[Image:Hamming(7,4) example 1011 bit 5 error.svg|thumb|300px| | + | [[Image:Hamming(7,4) example 1011 bit 5 error.svg|thumb|300px|A bit error on bit 5 causes bad parity in the red and green circles]] |
− | + | The diagram to the right shows the bit error (shown in blue text) and the bad parity created (shown in red text) in the red and green circles. The bit error can be detected by computing the parity of the red, green, and blue circles. If a bad parity is detected then the data bit that overlaps ''only'' the bad parity circles is the bit with the error. In the above example, the red and green circles have bad parity so the bit corresponding to the intersection of red and green but not blue indicates the errored bit. | |
− | |||
− | + | Now, | |
: <math>\mathbf{z} = \mathbf{Hr} = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix} | : <math>\mathbf{z} = \mathbf{Hr} = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix} | ||
\begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 3 \\ 4 \\ 3 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} </math> | \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 3 \\ 4 \\ 3 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} </math> | ||
− | + | which corresponds to the fifth column of '''H'''. Furthermore, the general algorithm used (''see [[Hamming code#General algorithm]]'') was intentional in its construction so that the syndrome of 101 corresponds to the binary value of 5, which indicates the fifth bit was corrupted. Thus, an error has been detected in bit 5, and can be corrected (simply flip or negate its value): | |
− | '' 'H' '' | ||
:<math> \mathbf{r}_{\text{corrected}} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ \overline{1} \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} </math> | :<math> \mathbf{r}_{\text{corrected}} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ \overline{1} \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} </math> | ||
− | + | This corrected received value indeed, now, matches the transmitted value '''x''' from above. | |
− | |||
==デコード== | ==デコード== |