Главная » Хабрахабр » [Перевод] Ричард Хэмминг: Глава 11. Теория кодирования — II

[Перевод] Ричард Хэмминг: Глава 11. Теория кодирования — II

«Цель этого курса — подготовить вас к вашему техническому будущему.»

imageПривет, Хабр. Помните офигенную статью «Вы и ваша работа» (+219, 2442 в закладки, 393k прочтений)?

Мы ее переводим, ведь мужик дело говорит. Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся коды Хэмминга) есть целая книга, написанная по мотивам его лекций.

«Это не просто заряд положительного мышления; в ней описаны условия, которые увеличивают шансы сделать великую работу.» Это книга не просто про ИТ, это книга про стиль мышления невероятно крутых людей.

И ведем работу над изданием «в бумаге». Мы уже перевели 25 (из 30) глав.

11. Теория кодирования — II

(За перевод спасибо erosinka, которая откликнулась на мой призыв в «предыдущей главе».) Кто хочет помочь с переводом — пишите в личку или на почту magisterludi2016@yandex.ru

Во-первых, мы хотим, чтобы средняя длина L отправленного сообщения была как можно более маленькой (чтобы сохранить ресурсы). Две вещи должны быть ясны из предыдущей главы. Для самой простой теории, единственной, какую мы можем обсуждать здесь, нам понадобятся вероятности появления в сообщении индивидуальных символов. Во-вторых, это должно быть подкреплено статистической теорией, так как мы не можем знать какое сообщение будет отправлено, но мы можем знать некоторые статистистические данные, используя предыдущие сообщения, и последующие выходные данные, возможно, будут похожи на предыдущие. Какую длину li мы должны установить (учитывая что мы должны подчиняться неравенству Крафта), чтобы получить минимальную среднюю длину кода? Вопрос их получения не является частью теории, но они могут быть получены путем исследования прошлого опыта или воображаемым гаданием об использовании в будущем системы, которую Вы проектируете.
Таким образом, мы хотим мгновенно однозначно декодируемый код для данного набора входных символов, si, вместе с их вероятностями, pi. Хаффман решил эту проблему дизайна кода.

Если pi расположены в убывающем порядке, то li должны быть в возрастающем порядке. Хаффман первым показал, что следующие неравенства должны быть верны для кода минимальной длины.

image

Рассмотрим эффект перестановки символов, связанных с теми двумя, которые не в указанном порядке. Допустим, pi в указанном порядке, но хотя бы одна пара li — нет. Перед перестановкой вклад этих двух членов уравнения в среднюю длину кода L

image

и после перестановки

image

Разница может быть записана как Все остальные члены в сумме L остаются те же.

image

Таким образом для минимальной длины кода мы должны иметь два неравенства. Один из этих членов предполагается отрицательным, следовательно после перестановки двух символов средняя длина кода L уменьшится.

Далее Хаффман обнаружил, что мгновенно дешифруемый код имеет дерево решений, и каждый узел должен иметь два выхода, в противном случае это пустая попытка, следовательно, имеются два символа с наибольшей длинной, которые имеют одинаковую длину.

image

Пусть p(s1) = 0. Для иллюстрации кода ХАффмана мы используем классический пример. 2, p(s3) = 0. 4, p(s2) = 0. 1 и p(s5) = 0. 2, p(s4) = 0. Это изображено на рисунке 11. 1. (?) Повторяя это снова и снова он приходил к системе с двумя символами, для которых он знал, как приписать представление кода, а именно одному символу — 0, а другому — 1. I Тогда Хаффман утверждал на основании значений выше, что он мог комбинировать (объединить) два наименее частых символа (которые должны иметь одинаковую длину) в один символ с общей вероятностью с общими битами вплоть до последнего бита, который отбрасывается, таким образом получая код на один символ меньше.

image

Таким методом мы придем к коду минимальной длины L, снова смотрите рисунок 11. Теперь идя в обратную сторону, нам нужно на каждой стадии разделить символ, который получился из комбинации двух символов, сохраняя те же ведущие биты, но добавляя к одному символу 0, а к другому — 1. Следовательно, код Хаффмана имеет минимальную длину. I Так как если бы существовал другой код с меньшей длиной L’, то выполняя шаги вперед, которые изменяют среднюю длину кода на заданное число, он бы пришел к двум символам со средней длиной кода меньше, чем 1, что невозможно. II с соответствующим декодирующим деревом. Смотрите рисунок 11.

Прежде всего на каждом шаге процесса приписывание 0 и 1 каждому из символов — это произвольный процесс. Этот код не уникален. Это может привести в некоторых случаях к появлению очень разных кодов, но они оба будут иметь одинаковую среднюю длину. Во-вторых, если на каком-либо этапе имеется два символа с одинаковыми вероятностями, то не имеет значения, какой из них будет первым.

III с соответствующим декодирующим деревом на рисунке 11. Если поместить комбинированные члены как можно выше, мы получим рисунок 11. Средняя длина двух кодов одинакова, но коды и декодирующие деревья отличаются; первое — длинное, а второй — “ветвистое”, и второе менее изменчиво чем первое. IV.

Например, у вас может быть очень много данных предназначенных для хранилища бэкапов, и известно, что ее кодирование с подходящим кодом Хаффмана позволит сэкономить более, чем половину ожидаемого объема хранилища. Теперь мы приведем второй пример, чтобы вы были уверены в том, как работает кодирование Хаффмана, так как это естественное желание использовать в процессе разработки кодирующей системы код с как можно более короткой средней длиной. Сначала мы проверим, что сумма вероятностей равна 1. Пусть p(s1) = ⅓, p(s2) = ⅕, p(s3) = ⅙, p(s4) = 1/10, p(s5) = 1/12, p(s6) 1/20, p(s7) = 1/30, p(s8) = 1/30. Таким образом мы получаем общую вероятность Общий знаменатель дробей равен 60.

image

image

image

V, где мы опустили 60 в знаменателе вероятностей, так как лишь относительные величины имеют значение. Второй пример проиллюстрирован на рисунке 11. Мы вычисляем Какова средняя длина кода на символ?

image

58 Для блока кода в 8 символов каждый символ будет иметь длину 3 и средняя длина будет равняться 3, что больше, чем 2.

Каждый прямой шаг для кодирования Хаффмана это повторение одного и того же процесса: комбинировать 2 наименьшие вероятности, поместить новую сумму в правильное место в массиве и отметить его. Заметьте, насколько этот механический процесс подходит для машины. Эти программы легко написать для компьютера, таким образом компьютерная программа может вычислить код Хаффмана из данных si и их вероятностей pi. В обратном процессе, мы берем отмеченный символ и разделяем его. В самом деле, вы можете написать программу, которая сможет отобрать данные для хранения и найти оценку вероятностей (маленькие ошибки приводят только к маленьким изменениям L), найти код Хаффмана, провести кодирование и отправить первый декодирующий алгоритм (дерево) и затем закодированные данные, и все это без человеческого вмешательства! Вспомните, на практике вы хотите приписать символу возврата с очень маленькой вероятностью, так чтобы вы могли завершить декодирующий процесс в конце сообщения. Таким образом единожды написав программу, вы можете использовать ее в случаях, когда вы посчитаете ее полезной. В конце декодирования вы уже получили декодирующее дерево.

Следовательно, нам нужно посмотреть на улучшение средней длины кода L, которые мы можем ожидать при использовании кодирования Хаффмана, по сравнению с простых блочным кодированием, которое использует одинаковую длину для всех символов. Коды Хаффмана были использованы даже в некоторых компьютерах в инструкциях, так как они имели очень маленькую вероятность быть использованными.

Если имеется не точно 2^k символов, то некоторые из них будут короче, но трудно сказать, будет ли большинство из них короче на 1 бит, или же некоторые будут короче на 2 и более бит. Если все вероятности одинаковы и имеется точно 2^k символов, тогда исследование кодирование Хаффмана покажет, что вы получите стандартный блочный код с одинаковой длиной. В любом случае, значение L будет таким же, и не намного короче, чем в соответствующем блочном коде.

10) и (1111... С другой стороны, если каждая из pi больше ⅔ (сумма всех последующий вероятностей, кроме последней), тогда вы получите код с запятой, в котором 1 символ имеет длину 1 (0), один символ — 2 (10), и так далее до конца, где у вас будет два символа одинаковой длины (q-1): (1111... В этом случае длина L может быть намного короче, чем у соответствующего блочного кода. 11).

Правило: кодирование Хаффмана окупается, если вероятности символов очень разные, и не окупается, когда они примерно равны.

Естественно спросить, какой порядок следует выбрать в случае двух равных вероятностей. Когда в процессе ХАффмана появляются две равные вероятности, они могут быть расположены в любом порядке, и таким образом коды могут получиться очень разными, хотя средняя длина кода L в обоих случаях будет одинаковой. Правило простое: каждую новую вероятность вставлять в таблицу как можно выше. Разумным критерием является минимизация вариации кода так, что сообщения одинаковой длины в исходных символах имеют примерно одинаковую длину в закодированном виде, вы не хотите, чтобы исходное короткое сообщение было случайно закодировано длинным сообщением. В самом деле, если вы поместите ее выше символа со слегка большей вероятностью, то вы значительно уменьшите вариацию и лишь слегка увеличите L; так что это хорошая стратегия.

Мы обратимся к кодирующему каналу с моделированным шумом. Выполнив все шаги мы перейдем к кодированию исходников (хотя мы ни в коем случае не прошли всю тему). Что можно сделать? Канал, по предположению, имеет шум, что означает, что некоторые биты были изменены в процессе передачи (или хранения).

К блоку из (n-1) битов нужно прикрепить n-ный бит с таким значением, что все n битов имеют четное количество 1 (или нечетное, если хотите, но мы будем использовать четное число). Обнаружение единственной ошибки довольно просто. Это называется проверкой на четность (нечетность).

Если проверка на четность не пройдена, будет известно, что есть как минимум одна ошибка, в действительности, нечетное количество ошибок. Таким образом, если все отправленные сообщения будут обладать этим свойством, то на принимающем конце можно проверить, выполнено ли оно. Так как является благоразумным использовать системы с низкой вероятностью ошибки в любой позиции, то вероятность нескольких ошибок должна быть ещё ниже.

С этими предположениями, вероятности ошибок равны Для математической пригодности мы делаем предположение, что канал имеет белый шум, что означает 1) каждая позиция в блоке из n бит имеет одинаковую вероятность ошибки с любой другой позицией и 2) ошибки в различных позициях некоррелированы, что означает независимы.

image

Выбор длины n для данной вероятности p является инженерным решением. Из этого следует, что, если, как обычно, p мало относительно длины блока n (что означает, произведение np мало), то множественные ошибки гораздо менее вероятны, чем единственные ошибки. Вы должны принять инженерное решение о том, как сбалансировать эти два эффекта.
При обнаружении единственной ошибки можно попросить переслать сообщение заново, ожидая корректного результата во второй раз, или в третий и так далее. Если n мало, то у вас будет бОльшая избыточность (отношение количества отправленных битов к минимально возможному количеству битов n/(n-1)), чем с бОльшим n, но если np велико, то у вас будет малая избыточность, но более высокая вероятность не обнаружить ошибку. Таким образом, повторные передачи должны зависеть от ожидаемой природы ошибок. Однако, если хранимое сообщение некорректно, то вы будете просить о повторной передаче до тех пор, пока не появится другая ошибка, и возможно, у вас будет две необнаруженные ошибки в схеме обнаружения одиночных ошибок.

Телефонная компания использовала в центральных офисах и в ранних релейных машинах код 2-из-5, что означало, что только 2 из 5 реле были в положении “включено”. Такие коды широко использовались даже во времена реле. Если не точно 2 реле были в положении “включено”, это означало ошибку, и был повтор. Такой код использовался для представления десятичной цифры, так как C(5, 2)=10. Так же существовал код 3-из-7, очевидно, код с проверкой нечетности.

Любая ошибка обнаруживалась машиной практически в момент совершения, и следовательно указывала техническому персоналу правильное направление, вместо того чтобы водить их за нос, заставляя менять настройки корректно работающих частей в попытках найти неисправность. Я впервые познакомился с этими кодами 2-из-5 в процессе использования релейного компьютера Модель 5 в Белл Лабс, и я был впечатлен не только их помощью в получении правильного ответа, но, что более важно по моему мнению, они давали техническому персоналу возможность в действительности обслуживать машины.

американский транснациональный телекоммуникационный конгломерат) однажды спросил меня, как использовать кодирование, если люди использовали алфавит из 26 букв, 10 десятичных цифр и пробел. Нарушая временную последовательности повествования, но оставаясь в идейной, AT&T (прим. Я знал из данных по ошибкам набора телефонных номеров и из долгого опыта в программировании, что у людей есть сильно выраженная склонность к переставлению смежных цифр: 67 может стать 76, а так же к замене изолированных цифр (обычно удваивая цифру: 556 вероятно станет 566). Это типично для именования инвентаря, именования частей и многих других наименований вещей, включая именование зданий. Я привел двоих очень способных людей в переговорную комнату и задал им вопрос. Таким образом, обнаружение однократных ошибок недостаточно. В частности, он предложил обозначить числами 0, 1, 2, … 36 символы 0, 1, … 9, A, B, …, Z, пробел. Я отвергал предложение за предложением как недостаточно хорошие, пока наконец один из них, Эд Гильберт, не предложил взвешенный код. Затем он вычислял не сумму значений, а имел ли к-тый символ значение (отмеченное для удобства) Sk, тогда для сообщения из n символов мы вычисляем

image

Чтобы закодировать сообщение из n символов, оставьте первый символ, k=1, пустым и независимо от значения остатка, которое меньше 37, вычьте его из 37 и используйте соответствующий символ для проверки, который нужно поставить на первую позицию. “По модулю” здесь означает, что взвешенная сумма делится на 37 и только остаток от деления используется. Если вы рассмотрите перестановку любых двух различных символов или замену единственного символа, вы заметите, что это сломает взвешенную проверку четности, по модулю 37 (при условии, что заменённые символы находятся на расстоянии не равном 37 символов). Таким образом, все сообщение с проверяющим символом на первой позиции будет иметь проверочную сумму равную 0. Не вникая в детали, отметим, что важно, чтобы модуль был простым числом, каким 37 и является.

Расположите символы по порядку в столбце и вычислите промежуточные суммы, затем промежуточные суммы промежуточных сумм по модулю 37, затем дополните это по отношению к 37, и вы получите контрольный символ. Чтобы получить взвешенную сумму символом (фактически, их значения), при желании вы можете избегать произведений и использовать только сложения и вычитания. Как иллюстрация с использованием w, x, y, z.

image

На принимающей стороне вы повторно вычитаете модуль до тех пор, пока не получите или a-0 (корректный символ) или a — отрицательное число (неправильный символ).

Ошибка будет обнаружена до того, как заказ покинет вас и следовательно, её легко исправить. Если вам необходимо использовать это кодирование, например, для наименования инвентаря, то если неправильное название появилось впервые во время передачи, если не раньше (возможно, в предварительном процессе), то ошибка будет обнаружена, вам не придётся ждать до тех пор, пока заказ не будет доставлен до штаб-квартиры, чтобы позднее получить ответ, что не существует такого наименования, или получить неправильный заказ. Да! Просто? Эффективно против ошибок человека (в отличие от примера с белым шумом), да!

Это тот же код, только в нем используется 10 десятичных цифр, и число 10 не является простым числом, поэтому им пришлось ввести 11-й символ X, который может появляться временами во время проверки на четность — действительно, примерно каждая 11-я книга будет иметь X как последний символ в номере ISBN для проверки на четность. Действительно, в наши дни вы можете увидеть подобный код на книгах с ISBN номером. Проверьте это сами на ваших учебниках. Тире в основном выполняют декоративную функцию и не используются в кодировании. Многие другие крупные организации могли бы использовать такие коды для хорошего эффекта, если бы они хотели приложить усилия.

Материал выше дает простой код с обнаружением ошибок для машин, и взвешенный код для использования человеком. Я многократно указывал, что я верю, что в будущем информация в форме символов будет важна, и материальные вещи будут менее важны, и следовательно, теория кодирования (представления) информации в удобные коды — это нетривиальная тема. Это всего лишь 2 примера, как теория кодирования может помочь в ситуациях, где возможна машинная и человеческая ошибка.

Очевидно, при данных вероятностях различных ветвлений в программных меню вы можете при желании придумать способ уменьшить суммарное количество нажатий клавиш. Когда вы думаете об интерфейсе человек-компьютер, одна из вещей, которая вам может пригодиться, это необходимость сделать как можно меньше нажатий клавиш человеком — кодирование ХАффмана под прикрытием! В более широком смысле “автоматизированное программирование” в языках высокого уровня является попыткой достичь чего-то наподобие кодирования Хаффмана, чтобы для решения желаемых задач использовать сравнительно небольшое количество нажатий клавиш, а для остальных задач использовать другие клавиши. Таким образом один и тот же набор меню может быть настроен под привычки различных людей, вместо того, чтобы предлагать всем одинаковый интерфейс.

Продолжение следует...

Кто хочет помочь с переводом, версткой и изданием книги — пишите в личку или на почту magisterludi2016@yandex.ru

Кстати, мы еще запустили перевод еще одной крутейшей книги — «The Dream Machine: История компьютерной революции»)

Содержание книги и переведенные главы

Предисловие

  1. Intro to The Art of Doing Science and Engineering: Learning to Learn (March 28, 1995) Перевод: Глава 1
  2. «Foundations of the Digital (Discrete) Revolution» (March 30, 1995) Глава 2. Основы цифровой (дискретной) революции
  3. «History of Computers — Hardware» (March 31, 1995) Глава 3. История компьютеров — железо
  4. «History of Computers — Software» (April 4, 1995) Глава 4. История компьютеров — Софт
  5. «History of Computers — Applications» (April 6, 1995) Глава 5. История компьютеров — практическое применение
  6. «Artificial Intelligence — Part I» (April 7, 1995) Глава 6. Искусственный интеллект — 1
  7. «Artificial Intelligence — Part II» (April 11, 1995) Глава 7. Искусственный интеллект — II
  8. «Artificial Intelligence III» (April 13, 1995) Глава 8. Искуственный интеллект-III
  9. «n-Dimensional Space» (April 14, 1995) Глава 9. N-мерное пространство
  10. «Coding Theory — The Representation of Information, Part I» (April 18, 1995) (пропал переводчик :((( )
  11. «Coding Theory — The Representation of Information, Part II» (April 20, 1995)
  12. «Error-Correcting Codes» (April 21, 1995) (готово)
  13. «Information Theory» (April 25, 1995) (пропал переводчик :((( )
  14. «Digital Filters, Part I» (April 27, 1995) Глава 14. Цифровые фильтры — 1
  15. «Digital Filters, Part II» (April 28, 1995) Глава 15. Цифровые фильтры — 2
  16. «Digital Filters, Part III» (May 2, 1995) Глава 16. Цифровые фильтры — 3
  17. «Digital Filters, Part IV» (May 4, 1995) Глава 17. Цифровые фильтры — IV
  18. «Simulation, Part I» (May 5, 1995) (в работе)
  19. «Simulation, Part II» (May 9, 1995) Глава 19. Моделирование — II
  20. «Simulation, Part III» (May 11, 1995)
  21. «Fiber Optics» (May 12, 1995) Глава 21. Волоконная оптика
  22. «Computer Aided Instruction» (May 16, 1995) (пропал переводчик :((( )
  23. «Mathematics» (May 18, 1995) Глава 23. Математика
  24. «Quantum Mechanics» (May 19, 1995) Глава 24. Квантовая механика
  25. «Creativity» (May 23, 1995). Перевод: Глава 25. Креативность
  26. «Experts» (May 25, 1995) Глава 26. Эксперты
  27. «Unreliable Data» (May 26, 1995) Глава 27. Недостоверные данные
  28. «Systems Engineering» (May 30, 1995) Глава 28. Системная Инженерия
  29. «You Get What You Measure» (June 1, 1995) Глава 29. Вы получаете то, что вы измеряете
  30. «How Do We Know What We Know» (June 2, 1995) пропал переводчик :(((
  31. Hamming, «You and Your Research» (June 6, 1995). Перевод: Вы и ваша работа

Кто хочет помочь с переводом, версткой и изданием книги — пишите в личку или на почту magisterludi2016@yandex.ru


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Создание пакетов для Kubernetes с Helm: структура чарта и шаблонизация

Теперь подойдём к практике с другой стороны — с точки зрения создателя чартов (т.е. Про Helm и работу с ним «в общем» мы рассказали в прошлой статье. И хотя эта статья пришла из мира эксплуатации, она получилась больше похожей на ...

[Из песочницы] Экономим на RAID-контроллере, или как накормить Варю иопсами

В наш век облачных сервисов, AWS Lambda и прочих шаред хостингов абсолютно неосязаемых вычислительных ресурсов иногда хочется немножко своего. Кроме желания, иногда бывают и потребности вдумчиво покрутить тот или иной программный продукт с минимальными затратами на платформу. Найти какие-то излишки ...