{ "version": "https:\/\/jsonfeed.org\/version\/1", "title": "Light, заметки с тегом: код Хэмминга", "home_page_url": "https:\/\/boyarkirk.ru\/?go=tags\/kod-hemminga\/", "feed_url": "https:\/\/boyarkirk.ru\/?go=tags%2Fkod-hemminga%2Fjson%2F", "icon": "https:\/\/boyarkirk.ru\/user\/userpic@2x.jpg", "author": { "name": "Серёга", "url": "https:\/\/boyarkirk.ru\/", "avatar": "https:\/\/boyarkirk.ru\/user\/userpic@2x.jpg" }, "items": [ { "id": "9", "url": "https:\/\/boyarkirk.ru\/?go=all\/prostoy-kod-hemminga-praktika\/", "title": "Простой код Хэмминга. Практика.", "content_html": "

ВНИМАНИЕ! Это разжёванная версия замечательной статьи, которая есть на хабре<\/a>!
\nЕсли вам нужно лаконичное объяснение, то вам туда! Если же вы в этом ничего не понимаете и требуется пошаговое разбирательство, то милости прошу читать дальше. То есть, где вам понятнее — там и читайте. Статья на хабре<\/a> не моя, но я считаю, что она шикарна!<\/p>\n

Итак. Задача. Использовать код Хэмминга для двоичного сообщения, длина слова у которого составляет 16 бит. Исходное сообщение возьмём такое «0100010000111101». То есть в слове 16 «букв», каждая из которых может принимать значение либо «0», либо «1».<\/p>\n

\n\"\"\n<\/div>\n

Кодирование<\/h2>\n

Сначала в исходное сообщение добавляем контрольные биты и устанавливаем их в нуль.
\nКонтрольные биты располагаются в тех номерах битов, которые равны степеням двойки (ибо алфавит двоичный).
\nТо есть. Два в степени нуль — это единица, два в степени 1 = два, два в степени 2 = четыре, а два в степени 3 = восемь, два в степени 4 = 16
\nЗначит контрольные биты будут находиться в «буквах»(битах) под номерами 1, 2, 4, 8 и 16.<\/p>\n

\n\"\"\n<\/div>\n

В остальные номера бит переписываем исходное сообщение.<\/p>\n

\n\"\"\n<\/div>\n

Видно, что длина «слова» из-за такой избыточности увеличилась на пять «букв». В данном случае, конечно. У вас количество дополнительных бит будет зависеть от длины исходного «слова».<\/p>\n

Теперь нужно вычислить эти контрольные биты.
\nКаждый контрольный бит с номером N «контролирует» непрерывную последовательность из N битов, через каждые N битов.<\/p>\n

Вот на картинке отмечено иксами (X), какие биты нужно использовать для вычисления первого контрольного бита (с номером «1»)<\/p>\n

\n\"\"\n<\/div>\n

Для вычисления контрольно бита нужно просто сложить все «буквы» нашего «слова», которые он контролирует, а затем принять нелёгкое решение: если сумма получилась чётная, то пишем в результате нуль, а если нечётная — единицу.<\/p>\n

Вычисляем первый бит<\/b>.
\nСкладываем биты под номерами 3,5,7,9,11,13,15,17,19,21
\nЭто будет 0 + 1 + 0 + 0 + 0 + 0 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 = 5
\nПолучилось 5 (пять). Сумма нечётная (на два нацело не делится). Значит пишем в первый бит единицу:<\/p>\n

\n\"\"\n<\/div>\n

Теперь вычислим контрольный бит номер 2<\/b>. Для него нужно будет найти сумму каждых двух бит следующих друг за другом непрерывно, через каждые два бита. Такие биты я тоже отметил на картинке.<\/p>\n

\n\"\"\n<\/div>\n

То есть будем теперь суммировать биты, начитая с третьего по номеру, и далее те, которые отмечены иксом (X).
\nИх номера 3, 6, 7, 10, 11, 14, 15, 18, 19.
\nЭто будет 0 + 0 + 0 + 1 + 0 + 0 + 1 + 1 + 1 = 4
\nЧетыре — число чётное, значит оставляем в нашем втором бите нуль.<\/p>\n

\n\"\"\n<\/div>\n

Переходим к вычислению третьего контрольного бита<\/b>. Но это у нас он контрольный — третий. А в сообщении этот бит записан под номером 4<\/b> — четыре.<\/p>\n

\n\"\"\n<\/div>\n

Значит и использовать будем все попадающие под наше правило биты, начиная с пятого.
\nА это биты под номерами 5, 6, 7, 12, 13, 14, 15, 20, 21.
\nСкладываем их: 1 + 0 + 0 + 0 + 0 + 0 + 1 + 0 + 1 = 3
\nВ итоге у нас нечётное число, значит пишем в наш контрольный бит единицу.<\/p>\n

\n\"\"\n<\/div>\n

Осталось всего ничего — вычислить два оставшихся контрольных бита<\/b>, которые под номерами 8 и 16.<\/p>\n

В восьмом оставляем нуль потому, что в той последовательности, которую мы используем для вычисления присутствуют две единицы, дающие в сумме чётное число.<\/p>\n

\n\"\"\n<\/div>\n

А в 16-м тоже сумма бит получается чётной — оставляем нуль:<\/p>\n

\n\"\"\n<\/div>\n

В итоге мы получили слово с кодом Хэмминга, которое содержит избыточные биты (в сумме 21): «100110000100001011101».<\/p>\n

Декодирование<\/h2>\n

А теперь представим, что к нам пришло сообщение с ошибкой. Вот оно «100110001100001011101».
\nМы знаем, что в него добавлены избыточные биты по алгоритму Хемминга, и нам надо проверить, есть в нём ошибка или нет.<\/p>\n

Для этого нужно поступить следующим образом. Сначала вычисляем заново все контрольные биты по предыдущему алгоритму.
\nДля этого сначала обнуляем все биты, находящиеся на номерах степеней двойки:<\/p>\n

\n\"\"\n<\/div>\n

В первом оставляем нуль, ибо в подконтрольных битах чётное число единиц.<\/p>\n

\n\"\"\n<\/div>\n

Вычисляем все остальные контрольные биты по описанному выше алгоритму (мне лень заново его описывать тут), и получаем, что не совпадают контрольные биты под номерами 1 и 8:<\/p>\n

\n\"\"\n<\/div>\n

Теперь складываем номера этих контрольных бит: 1 + 8, и получаем 9 — номер бита, в котором закралась ошибка! Ура! Теперь просто меняем девятый бит на обратный — с единицы на нуль, — и получаем исходное сообщение!<\/p>\n

Отметим, что это самый простейший алгоритм Хемминга, который может исправить только одну ошибку в слове. Об остальных алгоритмах данная статья умалчивает. :)<\/p>\n", "date_published": "2015-12-30T04:55:22+00:00", "date_modified": "2016-09-09T08:31:00+00:00", "image": "https:\/\/boyarkirk.ru\/pictures\/_023.jpg", "_date_published_rfc2822": "Wed, 30 Dec 2015 04:55:22 +0000", "_rss_guid_is_permalink": "true", "_rss_guid": "https:\/\/boyarkirk.ru\/?go=all\/prostoy-kod-hemminga-praktika\/", "_e2_data": { "is_favourite": false, "links_required": [], "og_images": [ "https:\/\/boyarkirk.ru\/pictures\/_023.jpg", "https:\/\/boyarkirk.ru\/pictures\/_024.jpg", "https:\/\/boyarkirk.ru\/pictures\/_025.jpg", "https:\/\/boyarkirk.ru\/pictures\/_027.jpg", "https:\/\/boyarkirk.ru\/pictures\/_028.jpg", "https:\/\/boyarkirk.ru\/pictures\/_029.jpg", "https:\/\/boyarkirk.ru\/pictures\/_030.jpg", "https:\/\/boyarkirk.ru\/pictures\/_031.jpg", "https:\/\/boyarkirk.ru\/pictures\/_032.jpg", "https:\/\/boyarkirk.ru\/pictures\/_033.jpg", "https:\/\/boyarkirk.ru\/pictures\/_035.jpg", "https:\/\/boyarkirk.ru\/pictures\/_036.jpg", "https:\/\/boyarkirk.ru\/pictures\/_038.jpg", "https:\/\/boyarkirk.ru\/pictures\/_039.jpg" ] } } ], "_e2_version": 3254, "_e2_ua_string": "E2 (v3254; Aegea)" }