ハミング空間

統計学と符号理論において、ハミング空間とは通常、長さNのすべてのバイナリ文字列の集合であり、異なるバイナリ文字列は、1つの位置のみが異なる場合に隣接していると見なされます。任意の2つのバイナリ文字列間の合計距離は、対応するビットが異なる位置の合計数であり、ハミング距離と呼ばれます。^[1]^[2]ハミング空間は、1950年にこの概念を導入したアメリカの数学者リチャード・ハミングにちなんで名付けられました。 ^[3]ハミング空間は、符号化信号と伝送の理論で使用されます。 $2^{N}$

より一般的には、ハミング空間は任意のアルファベット（集合）Q上で、 Qの文字からなる固定長Nの単語の集合として定義できます。^[4]^[5]Qが有限体である場合、 Q上のハミング空間はQ上のN次元ベクトル空間です。典型的なバイナリケースでは、体はGF(2) （ Z ₂とも表記されます）です。^[4]

符号理論では、Q がq個の要素を持つ場合、Q上のN次元ハミング空間の任意の部分集合 C (通常は少なくとも 2 の濃度を想定) は長さ N のq 元符号と呼ばれ、 Cの要素は符号語と呼ばれます。^[4]^[5]Cがハミング空間の線型部分空間である場合、それは線型符号と呼ばれます。^[4]線型符号の典型的な例はハミング符号です。ハミング空間を介して定義された符号は、すべての符号語に対して必然的に同じ長さを持つため、モノイド上の一意の因数分解によって定義される可変長符号と区別する必要がある場合、ブロック符号と呼ばれます。

ハミング距離はハミング空間にメトリックを与え、これは誤り検出符号や誤り訂正符号などの符号理論の基本概念を定義する上で不可欠である。^[4]

非体アルファベット上のハミング空間も考慮されており、特に有限環上（特にZ ₄上）ではベクトル空間の代わりにモジュールが生成され、線形コードの代わりに環線形コード（サブモジュールで識別される）が生成されます。この場合に使用される典型的なメトリックはリー距離です。ハミング距離を持つ（つまり GF(2 ^2m )）とリー距離を持つ（GR(4,m) とも表記）の間にはグレイ等長変換が存在します。 ^[6]^[7]^[8] $\mathbb {Z} _{2}^{2m}$ $\mathbb {Z} _{4}^{m}$

参考文献

^ ベイリス、DJ (1997)、誤り訂正符号：数学入門、チャップマンホール/CRC数学シリーズ、第15巻、CRCプレス、p. 62、ISBN 9780412786907
^ Cohen, G.; Honkala, I.; Litsyn, S.; Lobstein, A. (1997)、Covering Codes、North-Holland Mathematical Library、vol. 54、Elsevier、p. 1、ISBN 9780080530079
^ Hamming, RW (1950 年 4 月). 「エラー検出およびエラー訂正コード」(PDF) . The Bell System Technical Journal . 29 (2): 147–160. doi : 10.1002/j.1538-7305.1950.tb00463.x . hdl : 10945/46756 . ISSN 0005-8580. S2CID 61141773. 2022 年 10 月 9 日のオリジナルからアーカイブ(PDF) 。
^ abcde Derek JS Robinson (2003).抽象代数入門. Walter de Gruyter. pp. 254–255. ISBN 978-3-11-019816-4。
^ ab Cohen et al., Covering Codes、p. 15より
^ Marcus Greferath (2009)。「リング線形符号化理論入門」。Massimiliano Sala、Teo Mora、Ludovic Perret、Shojiro Sakata、Carlo Traverso (編)。Gröbner Bases, Coding , and Cryptography。Springer Science & Business Media。ISBN 978-3-540-93806-4。
^ 「Kerdock および Preparata コード - 数学百科事典」。
^ JH van Lint (1999).符号理論入門（第3版）. Springer. 第8章: 以上のコード. ISBN $\mathbb {Z} _{4}$ 978-3-540-64133-9。

[1] ベイリス、DJ (1997)、誤り訂正符号：数学入門、チャップマンホール/CRC数学シリーズ、第15巻、CRCプレス、p. 62、ISBN 9780412786907

[2] Cohen, G.; Honkala, I.; Litsyn, S.; Lobstein, A. (1997)、Covering Codes、North-Holland Mathematical Library、vol. 54、Elsevier、p. 1、ISBN 9780080530079

[3] Hamming, RW (1950 年 4 月). 「エラー検出およびエラー訂正コード」(PDF) . The Bell System Technical Journal . 29 (2): 147–160. doi : 10.1002/j.1538-7305.1950.tb00463.x . hdl : 10945/46756 . ISSN 0005-8580. S2CID 61141773. 2022 年 10 月 9 日のオリジナルからアーカイブ(PDF) 。

[Robinson2003-4] Derek JS Robinson (2003).抽象代数入門. Walter de Gruyter. pp. 254–255. ISBN 978-3-11-019816-4。

[cc15-5] Cohen et al., Covering Codes、p. 15より

[Greferath2009-6] Marcus Greferath (2009)。「リング線形符号化理論入門」。Massimiliano Sala、Teo Mora、Ludovic Perret、Shojiro Sakata、Carlo Traverso (編)。Gröbner Bases, Coding , and Cryptography。Springer Science & Business Media。ISBN 978-3-540-93806-4。

[7] 「Kerdock および Preparata コード - 数学百科事典」。

[Lint1999-8] JH van Lint (1999).符号理論入門（第3版）. Springer. 第8章: 以上のコード. ISBN $\mathbb {Z} _{4}$ 978-3-540-64133-9。