「Hamming(7,4)」を編集中
この編集を取り消せます。
下記の差分を確認して、本当に取り消していいか検証してください。よろしければ変更を保存して取り消しを完了してください。
| 最新版 | 編集中の文章 | ||
| 75行目: | 75行目: | ||
したがって、パリティビットカバレッジを正しく選択することにより、ハミング距離が1であるすべてのエラーを検出して修正することができます。これはハミングコードを使用する点です。 | したがって、パリティビットカバレッジを正しく選択することにより、ハミング距離が1であるすべてのエラーを検出して修正することができます。これはハミングコードを使用する点です。 | ||
| − | + | == Hamming matrices == | |
| − | == | + | Hamming codes can be computed in [[linear algebra]] terms through [[matrix (mathematics)|matrices]] because Hamming codes are [[linear code]]s. For the purposes of Hamming codes, two '''Hamming matrices''' can be defined: the '''code [[generator matrix]]''' '''G''' and the '''[[parity-check matrix]]''' '''H''': |
| − | |||
:<math>\mathbf{G} := \begin{pmatrix} | :<math>\mathbf{G} := \begin{pmatrix} | ||
| 100行目: | 99行目: | ||
* ''p''<sub>2</sub> covers ''d''<sub>1</sub>, ''d''<sub>3</sub>, ''d''<sub>4</sub> | * ''p''<sub>2</sub> covers ''d''<sub>1</sub>, ''d''<sub>3</sub>, ''d''<sub>4</sub> | ||
* ''p''<sub>3</sub> covers ''d''<sub>2</sub>, ''d''<sub>3</sub>, ''d''<sub>4</sub> | * ''p''<sub>3</sub> covers ''d''<sub>2</sub>, ''d''<sub>3</sub>, ''d''<sub>4</sub> | ||
| − | + | The remaining rows (3, 5, 6, 7) map the data to their position in encoded form and there is only 1 in that row so it is an identical copy. In fact, these four rows are [[linearly independent]] and form the [[identity matrix]] (by design, not coincidence). | |
| − | + | Also as mentioned above, the three rows of '''H''' should be familiar. These rows are used to compute the '''syndrome vector''' at the receiving end and if the syndrome vector is the [[null vector (vector space)|null vector]] (all zeros) then the received word is error-free; if non-zero then the value indicates which bit has been flipped. | |
| − | + | The four data bits — assembled as a vector '''p''' — is pre-multiplied by '''G''' (i.e., '''Gp''') and taken [[Modulo operation|modulo]] 2 to yield the encoded value that is transmitted. The original 4 data bits are converted to seven bits (hence the name "Hamming(7,4)") with three parity bits added to ensure even parity using the above data bit coverages. The first table above shows the mapping between each data and parity bit into its final bit position (1 through 7) but this can also be presented in a [[Venn diagram]]. The first diagram in this article shows three circles (one for each parity bit) and encloses data bits that each parity bit covers. The second diagram (shown to the right) is identical but, instead, the bit positions are marked. | |
| − | + | For the remainder of this section, the following 4 bits (shown as a column vector) will be used as a running example: | |
: <math>\mathbf{p} = \begin{pmatrix} d_1 \\ d_2 \\ d_3 \\ d_4 \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}</math> | : <math>\mathbf{p} = \begin{pmatrix} d_1 \\ d_2 \\ d_3 \\ d_4 \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}</math> | ||
