пространство Хэмминга
Пространство Хэмминга двоичных строк длины 3. Расстояние между вершинами в кубическом графе равно расстоянию Хэмминга между строками.

В статистике и теории кодирования пространство Хэмминга обычно представляет собой множество всех двоичных строк длины N , где различные двоичные строки считаются смежными, если они отличаются только в одной позиции. Общее расстояние между любыми двумя двоичными строками тогда равно общему числу позиций, в которых соответствующие биты различны, называемому расстоянием Хэмминга . [1] [2] Пространства Хэмминга названы в честь американского математика Ричарда Хэмминга , который ввел это понятие в 1950 году. [3] Они используются в теории кодирования сигналов и передачи. 2 Н {\displaystyle 2^{N}}

В более общем смысле пространство Хэмминга можно определить над любым алфавитом (множеством) Q как множество слов фиксированной длины N с буквами из Q. [4] [5] Если Q — конечное поле , то пространство Хэмминга над Q — это N -мерное векторное пространство над Q. В типичном, двоичном случае поле, таким образом, есть GF(2) (также обозначается Z 2 ). [4]

В теории кодирования, если Q имеет q элементов, то любое подмножество C (обычно предполагается, что его мощность не менее двух) N -мерного пространства Хэмминга над Q называется q-ичным кодом длины N ; элементы C называются кодовыми словами . [4] [5] В случае, когда C является линейным подпространством своего пространства Хэмминга, оно называется линейным кодом . [4] Типичным примером линейного кода является код Хэмминга . Коды, определенные через пространство Хэмминга, обязательно имеют одинаковую длину для каждого кодового слова, поэтому они называются блочными кодами , когда необходимо отличать их от кодов переменной длины , которые определяются уникальной факторизацией на моноиде.

Расстояние Хэмминга наделяет пространство Хэмминга метрикой , которая необходима для определения основных понятий теории кодирования, таких как коды обнаружения и исправления ошибок . [4]

Также рассматривались пространства Хэмминга над неполевыми алфавитами, особенно над конечными кольцами (прежде всего над Z 4 ), что привело к появлению модулей вместо векторных пространств и кольцевых линейных кодов (идентифицируемых с подмодулями ) вместо линейных кодов. Типичная метрика, используемая в этом случае, — расстояние Ли . Существует изометрия Грея между (т. е. GF(2 2m )) с расстоянием Хэмминга и (также обозначаемая как GR(4,m)) с расстоянием Ли. [6] [7] [8] З 2 2 м {\displaystyle \mathbb {Z} _{2}^{2m}} З 4 м {\displaystyle \mathbb {Z} _{4}^{m}}

Ссылки

  1. ^ Бейлис, DJ (1997), Коды исправления ошибок: введение в математику, Chapman Hall/CRC Mathematics Series, т. 15, CRC Press, стр. 62, ISBN 9780412786907
  2. ^ Коэн, Г.; Хонкала, И.; Лицин, С.; Лобштейн, А. (1997), Покрывающие коды, Математическая библиотека Северной Голландии, т. 54, Elsevier, стр. 1, ISBN 9780080530079
  3. ^ Hamming, RW (апрель 1950 г.). «Error detection and error Correcting codes» (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. Архивировано (PDF) из оригинала 2022-10-09.
  4. ^ abcde Дерек Дж. С. Робинсон (2003). Введение в абстрактную алгебру . Вальтер де Грюйтер. С.  254– 255. ISBN 978-3-11-019816-4.
  5. ^ ab Cohen et al., Covering Codes , стр. 15
  6. ^ Маркус Греферат (2009). «Введение в теорию линейного кодирования колец». Массимилиано Сала; Тео Мора; Людовик Перре; Сёдзиро Саката; Карло Траверсо (ред.). Базисы Грёбнера, кодирование и криптография . Springer Science & Business Media. ISBN 978-3-540-93806-4.
  7. ^ «Коды Кердока и Препараты — Энциклопедия математики».
  8. ^ JH van Lint (1999). Введение в теорию кодирования (3-е изд.). Springer. Глава 8: Коды по . ISBN З 4 {\displaystyle \mathbb {Z} _{4}}  978-3-540-64133-9.


Значок заглушки

Эта статья по линейной алгебре — заглушка . Вы можете помочь Википедии, расширив ее.

Взято с "https://en.wikipedia.org/w/index.php?title=Пространство_Хэмминга&oldid=1251500943"