Кому нужна математика? Понятная книга о том, как устроен цифровой мир (Литвак, Райгородский) - страница 24

Рис. 3.2. Расстояние Хэмминга между двумя кодовыми словами – число позиций, на которых у этих слов стоят разные символы. На рисунке это расстояние равно трем. Позиции, где два кодовых слова отличаются друг от друга, заключены в рамки

Что происходит, если при передаче, скажем, слова 111000 произошла одна ошибка?

Получится другое слово, которое будет отличаться от 111000 всего на одной позиции. Иначе говоря, если у нас при передаче происходит не больше одной ошибки, расстояние Хэмминга между отправленным и полученным кодовым словом будет не больше единицы. Давайте снова посмотрим на перечень (3.1) предыдущего раздела:

111000, 011000, 101000, 110000, 111100, 111010, 111001.

Расстояние Хэмминга между словом 111000 и любым другим словом из перечня не превосходит 1. Значит, этот список – не что иное, как шар радиуса 1 с центром 111000!

Кстати, подобное определение можно ввести и для обычных слов русского языка одинаковой длины. Например, расстояние Хэмминга между словами «дочка» и «точка» равно единице, а между словами «точка» и «галка» – трем. Если слово «точка» – это центр шара Хэмминга радиуса 1, то слово «дочка» входит в этот шар, а слово «галка» – нет.

Шары Хэмминга очень трудно себе представить даже для маленьких кодов. На рис. 3.3 мы изобразили расстояния Хэмминга между кодовыми словами длины 3. Расстояния Хэмминга могут быть 0, 1, 2 или 3. На рисунке чем темнее цвет, тем больше расстояние. Если взять, например, колонку 000, то шар Хэмминга радиуса 1 – это все белые и светло-серые квадратики в этой колонке: 000, 001, 010, 100. Сразу видно, что расположение белых и, скажем, самых темных квадратиков в колонках неодинаковое, хотя, конечно, в рисунке много закономерностей. Например, рисунок из самых светлых тонов (белый и светло-серый) абсолютно симметричен рисунку из двух оставшихся более темных тонов.

Рис. 3.3. Расстояние Хэмминга между кодовыми словами длины 3. Справа изображен цветовой код. Расстояния: 0, 1, 2, 3. Чем темнее цвет, тем больше расстояние

Кодовые слова длины 3 – очень простой пример, их всего восемь. Стоит чуть увеличить длину кодового слова, и из-за уже знакомого нам экспоненциального закона слов станет так много, что картинка нам не поможет. Профессор Джон Слэни из Австралийского национального университета сделал замечательный рисунок, на котором изображены расстояния Хэмминга между кодовыми словами длины 8, а это всего один байт. Таких слов 256. Советуем заглянуть на веб-страницу Слэни http://users.cecs.anu.edu.au/~jks/Hamming.html и посмотреть на этот рисунок. Вам сразу станет понятно, что он никак не поможет найти хороший код. Картинка скорее напоминает красивый коврик. Нам нужен другой математический аппарат, и, к счастью, такой аппарат есть. Теория кодирования тесно связана с комбинаторикой – наукой о комбинациях тех или иных объектов.