хемминг теория кодирования и теория информации
Ричард Хэмминг: Глава 10. Теория кодирования — I
«Цель этого курса — подготовить вас к вашему техническому будущему.»
Привет, Хабр. Помните офигенную статью «Вы и ваша работа» (+219, 2442 в закладки, 394k прочтений)?
Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся коды Хэмминга) есть целая книга, написанная по мотивам его лекций. Мы ее переводим, ведь мужик дело говорит.
Это книга не просто про ИТ, это книга про стиль мышления невероятно крутых людей. «Это не просто заряд положительного мышления; в ней описаны условия, которые увеличивают шансы сделать великую работу.»
Мы уже перевели 28 (из 30) глав. И ведем работу над изданием «в бумаге».
Теория кодирования — I
Рассмотрев компьютеры и принцип их работы, сейчас мы будем рассматривать вопрос представления информации: как компьютеры представляют информацию, которую мы хотим обработать. Значение любого символа может зависит от способа его обработки, у машины нет никакого определенного смысла у используемого бита. При обсуждении истории программного обеспечения 4 главе мы рассматривали некоторый синтетический язык программирования, в нём код инструкции останова совпадал с кодом других инструкций. Такая ситуация типична для большинства языков, смысл инструкции определяется соответствующей программой.
Для упрощения проблемы представления информации рассмотрим проблему передачи информации от точки к точке. Этот вопрос связан с вопросом сохранения информация. Проблемы передачи информации во времени и в пространстве идентичны. На рисунке 10.1 представлена стандартная модель передачи информации.
Рисунок 10.1
Слева на рисунке 10.1 находится источник информации. При рассмотрении модели нам неважна природа источника. Это может быть набор символов алфавита, чисел, математических формул, музыкальных нот, символов, которыми мы можем представить танцевальные движения — природа источника и значение хранящихся в нём символов не является частью модели передачи. Мы рассматриваем только источник информации, с таким ограничением получается мощная, общая теория, которую можно распространить на многие области. Она является абстракцией из многих приложений.
Когда в конце 1940 годов Шеннон создал теорию информации, считалось, что она должна была называться теорией связи, но он настоял на термине информация. Этот термин стал постоянной причиной как повышенного интереса, так и постоянных разочарований в теории. Следователи хотели строить целые «теории информации», они вырождались в теории о наборе символов. Возвращаясь к модели передачи, у нас есть источник данных, которые необходимо закодировать для передачи.
Кодер состоит из двух частей, первая часть называется кодер источника, точное название зависит от типа источника. Источникам разных типов данных соответствуют разные типы кодеров.
Вторая часть процесса кодирования называется кодирование канала и зависит от вида канала для передачи данных. Таким образом, вторая часть процесса кодирования согласована с типом канала передачи. Таким образом, при использовании стандартных интерфейсов данные из источника в начале кодируются согласно требованиям интерфейса, а потом согласно требованиям используемого канала передачи данных.
Согласно модели, на рисунке 10.1 канал передачи данных подвергается воздействию «дополнительного случайного шума». Весь шум в системе объединен в этой точке. Предполагается, что кодер принимает все символы без искажений, а декодер выполняет свою функцию без ошибок. Это некоторая идеализация, но для многих практических целей она близка к реальности.
Фаза декодирования также состоит из двух этапов: канал — стандарт, стандарт- приемник данных. В конце передачи данных передаются потребителю. И снова мы не рассматриваем вопрос, как потребитель трактует эти данные.
Как было отмечено ранее, система передачи данных, например, телефонных сообщений, радио, ТВ программ, представляет данные в виде набора чисел в регистрах вычислительной машины. Повторю снова, передача в пространстве не отличается от передачи во времени или сохранения информации. Есть ли у вас есть информация, которая потребуется через некоторое время, то ее необходимо закодировать и сохранить на источнике хранения данных. При необходимости информация декодируется. Если система кодирования и декодирования одинаковая, мы передаем данные через канал передачи без изменений.
Фундаментальная разница между представленной теорией и обычной теорией в физике — это предположение об отсутствии шума в источнике и приемнике. На самом деле, ошибки возникают в любом оборудовании. В квантовой механике шум возникает на любых этапах согласно принципу неопределённости, а не в качестве начального условия; в любом случае, понятие шума в теории информации не эквивалентно аналогичному понятию в квантовой механике.
Для определенности будем далее рассматривать бинарную форму представления данных в системе. Другие формы обрабатываются похожим образом, для упрощения не будем их рассматривать.
Начнем рассмотрение систем с закодированными символами переменной длины, как в классическом коде Морзе из точек и тире, в котором часто встречающиеся символы — короткие, а редкие — длинные. Такой подход позволяет достичь высокой эффективности кода, но стоит отметить, что код Морзе — тернарный, а не бинарный, так как в нём присутствует символ пробела между точками и тире. Если все символы в коде одинаковой длины, то такой код называется блочным.
Первое очевидное необходимое свойство кода — возможность однозначно декодировать сообщение при отсутствии шума, по крайней мере, это кажется желаемым свойством, хотя в некоторых ситуациях этим требованием можно пренебречь. Данные из канала передачи для приемника выглядят как поток символов из нулей и единичек.
Будем называть два смежных символа двойным расширением, три смежных символ тройным расширением, и в общем случае если мы пересылаем N символов приемник видит дополнения к базовому коду из N символов. Приемник, не зная значение N, должен разделить поток в транслируемые блоки. Или, другими словами, у приемника должна быть возможность выполнить декомпозицию потока единственным образом для того, чтобы восстановить исходное сообщение.
Рассмотрим алфавит из небольшого числа символов, обычно алфавиты намного больше. Алфавиты языков начинается от 16 до 36 символов, включая символы в верхнем и нижнем регистре, числа знаки, препинания. Например, в таблице ASCII 128 = 2^7 символов.
Рассмотрим специальный код, состоящий из 4 символов s1, s2, s3, s4
s1 = 0; s2 = 00; s3 = 01; s4 = 11.
Как приёмник должен трактовать следующее полученное выражение
Как s1s1s4 или как s2s4?
Вы не можете однозначно дать ответ на этот вопрос, этот код однозначно нет декодируется, следовательно, он неудовлетворительный. С другой стороны, код
s1 = 0; s2 = 10; s3 = 110; s4 = 111
декодирует сообщение уникальным способом. Возьмем произвольную строку и рассмотрим, как ее будет декодировать приемник. Вам необходимо построить дерево декодирования Согласно форме на рисунке 10.II. Строка
может быть разбита на блоки символов
110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110,…
согласно следующему правилу построения дерева декодирования:
Если вы находитесь в вершине дерева, то считываете следующий символ. Когда вы достигаете листа дерева, вы преобразовывает последовательность в символ и возвращайтесь назад на старт.
Причина существования такого дерева в том, что ни один символ не является префиксом другого, поэтому вы всегда знаете, когда необходимо вернуться в начало дерево декодирования.
Необходимо обратить внимание на следующее. Во-первых, декодирование строго поточный процесс, при котором каждый бит исследуется только однажды. Во-вторых, в протоколах обычно включаются символы, которые являются маркером окончания процесса декодирования и необходимы для обозначения конца сообщения.
Отказ от использования завершающего символа является частой ошибкой при дизайне кодов. Конечно же можно предусмотреть режим постоянного декодирования, в этом случае завершающая символ не нужен.
Следующий вопрос — это коды для поточного (мгновенного) декодирования. Рассмотрим код, который получается из предыдущего отображением символов
s1 = 0; s2 = 01; s3 = 011; s4 = 111.
Предположим мы получили последовательность 011111. 111. Единственный способ, которым можно декодировать текст сообщения: группировать биты с конца по 3 в группе и выделять группы с ведущим нулем перед единичками, после этого можно декодировать. Такой код декодируемый единственным способом, но не мгновенным! Для декодирования необходимо дождаться окончания передачи! В практике такой подход нивелирует скорость декодирования (теорема Макмиллана), следовательно, необходимо поискать способы мгновенного декодирования.
Рассмотрим два способа кодирования одного и того же символа, Si:
s1 = 0; s2 = 10; s3 = 110; s4 = 1110, s5 = 1111,
Дерево декодирование этого способа представлено на рисунке 10.III.
s1 = 00; s2 = 01; s3 = 100; s4 = 110, s5 = 111,
Дерево декодирование это ухода представлены на рисунке 10.IV.
Наиболее очевидным способом измерения качество кода — это средняя длина для некоторого набора сообщений. Для этого необходимо вычислить длину кода каждого символа, помноженную на соответствующую вероятность появления pi. Таким образом получится длина всего кода. Формула средней длины L кода для алфавита из q символов выглядит следующим образом
где pi — вероятность появления символа si, li — соответствующая длина закодированного символа. Для эффективного кода значение L должно быть как можно меньше. Если P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 и p5 = 1/16, тогда для кода #1 получаем значение длины кода
Полученные значения говорят о предпочтительности первого кода.
Если у всех слов в алфавите будет одинаковая вероятность возникновения, тогда более предпочтительным будет второй код. Например, при pi = 1/5 длина кода #1
этот результат показывает предпочтительность 2 кода. Таким образом, при разработке «хорошего» кода необходимо учитывать вероятность возникновения символов.
Рассмотрим неравенство Крафта, которое определяет предельное значение длины кода символа li. По базису 2 неравенство представляется в виде
Это неравенство говорит о том, что в алфавите не может быть слишком много коротких символов, в противном случае сумма будет довольно большой.
Рассмотрим доказательство теорема Макмиллана. Применим неравенство Крафта к непоточно декодируем кодам. Доказательство построено на том факте, что для любого числа K > 1 n-ая степень числа заведомо больше линейной функции от n, где n — довольно большое число. Возведем неравенство Крафта в n-ую степень и представим выражение в виде суммы
где Nk число символов длины k, суммирование начинаем с минимальной длины n-го представление символа и заканчиваем максимальной длины nl, где l — максимальная длина закодированного символа. Из требования уникального декодирования следует, что. Сумма представляется в виде
Если K > 1, тогда необходимо n установить довольно большим для того, чтобы неравенство стало ложным. Следовательно, k Содержание книги и переведенные главы
Ричард Хэмминг: Глава 13. Теория информации
«Цель этого курса — подготовить вас к вашему техническому будущему.»
Привет, Хабр. Помните офигенную статью «Вы и ваша работа» (+219, 2588 в закладки, 429k прочтений)?
Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся коды Хэмминга) есть целая книга, написанная по мотивам его лекций. Мы ее переводим, ведь мужик дело говорит.
Это книга не просто про ИТ, это книга про стиль мышления невероятно крутых людей. «Это не просто заряд положительного мышления; в ней описаны условия, которые увеличивают шансы сделать великую работу.»
За перевод спасибо Андрею Пахомову.
Теория Информации была разработана К. Э. Шенноном в конце 1940х годов. Руководство Лабораторий Белла настаивало, чтобы он назвал ее «Теория Связи», т.к. это намного более точное название. По очевидным причинам, название «Теория Информации» обладает значительно большим воздействием на публику, поэтому Шеннон выбрал именно его, и именно оно известно нам по сей день. Само название предполагает, что теория имеет дело с информацией, это и делает ее важной, поскольку мы все глубже проникаем в информационную эпоху. В этой главе я затрону несколько основных выводов из этой теории, приведу не строгие, а скорее интуитивно понятные доказательства некоторых отдельных положений этой теории, чтобы вы поняли, чем на самом деле является «Теория Информации», где вы можете ее применять, а где нет.
Прежде всего, что такое “информация”? Шеннон отождествляет информацию с неопределенностью. Он выбрал отрицательный логарифм вероятности события в качестве количественной меры информации, которую вы получаете при наступлении события с вероятностью p. Например, если я скажу вам, что в Лос-Анжелесе туманная погода, тогда р близок к 1, что по большому счету, не дает нам много информации. Но если я скажу, что в июне в Монтерей идет дождь, то в этом сообщении будет присутствовать неопределенность, и оно будет содержать в себе больше информации. Достоверное событие не содержит в себе никакой информации, поскольку log 1 = 0.
Остановимся на этом подробнее. Шеннон полагал, что количественная мера информации должна быть непрерывной функцией от вероятности события p, а для независимых событий она должна быть аддитивной – количество информации, полученное в результате осуществления двух независимых событий, должно равняться количеству информации, полученному в результате осуществления совместного события. Например, результат броска игральных костей и монеты обычно рассматриваются как независимые события. Переведем вышесказанное на язык математики. Если I (p) – это количество информации, которое содержится в событии с вероятностью p, то, для совместного события, состоящего из двух независимых событий x с вероятностью p1 и y с вероятностью p2 получаем
(x и y независимые события)
Это функциональное уравнение Коши, истинное для всех p1 и p2. Для решения этого функционального уравнения предположим, что
Если p1 = p 2 и p2 = p, тогда
и т.д. Расширяя этот процесс, используя стандартный метод для экспонент, для всех рациональных чисел m / n, верно следующее
Из предполагаемой непрерывности информационной меры, следует, что логарифмическая функция является единственным непрерывным решением функционального уравнения Коши.
В теории информации принято принимать основание логарифма равное 2, поэтому бинарный выбор содержит ровно 1 бит информации. Следовательно, информация измеряется по формуле
Давайте приостановимся и разберемся, что же произошло выше. Прежде всего, мы так и не дали определение понятию “информация”, мы просто определили формулу ее количественной меры.
Во-вторых, эта мера зависит от неопределенности, и, хотя она в достаточной степени подходит для машин — например, телефонных системы, радио, телевидения, компьютеров и т. д. — она не отражает нормального человеческого отношения к информации.
В-третьих, это относительная мера, она зависит от текущего состояния вашего знания. Если вы смотрите на поток “случайных чисел” из генератора случайных чисел, вы предполагаете, что каждое следующее число неопределенно, но, если вы знаете формулу для вычисления «случайных чисел», следующее число будет известно, и, соответственно, не будет содержать в себе информации.
Таким образом, определение, данное Шенноном для информации, во многих случаях подходит для машин, но, похоже, не соответствует человеческому пониманию этого слова. Именно по этой причине «Теорию информации» следовало назвать «Теорией связи». Тем не менее, уже слишком поздно чтобы менять определения (благодаря которым теория приобрела свою первоначальную популярность, и которые все еще заставляют людей думать, что эта теория имеет дело с «информацией»), поэтому мы вынуждены с ними смириться, но при этом вы должны чётко понимать, насколько определение информации, данное Шенноном, далеко от своего общеупотребительного смысла. Информация Шеннона имеет дело с чем-то совершенно другим, а именно с неопределенностью.
Вот о чем нужно подумать, когда вы предлагаете какую-либо терминологию. Насколько предложенное определение, например, определение информации данное Шенноном, согласуется с вашей первоначальной идеей и насколько оно отличается? Почти нет термина, который бы в точности отражал ваше ранее видение концепции, но в конечном итоге, именно используемая терминология отражает смысл концепции, поэтому формализация чего-то посредством чётких определений всегда вносит некоторый шум.
Рассмотрим систему, алфавит которой состоит из символов q с вероятностями pi. В этом случае среднее количество информации в системе (её ожидаемое значение) равно:
Это называется энтропией системы с распределением вероятности
Энтропия распределения вероятности играет главную роль в теории кодирования. Неравенство Гиббса для двух разных распределений вероятности pi и qi является одним из важных следствий этой теории. Итак, мы должны доказать, что
Доказательство опирается на очевидный график, рис. 13.I, который показывает, что
а равенство достигается только при x = 1. Применим неравенство к каждому слагаемому суммы из левой части:
Если алфавит системы связи состоит из q символов, то принимая вероятность передачи каждого символа qi = 1/q и подставляя q, получаем из неравенства Гиббса
Это говорит о том, что если вероятность передачи всех q символов одинакова и равна — 1 / q, то максимальная энтропия равна ln q, в противном случае выполняется неравенство.
В случае однозначно декодируемого кода, мы имеем неравенство Крафта
Теперь если мы определим псевдовероятности
где конечно 
= 1, что следует из неравенства Гиббса,
и применим немного алгебры (помните, что K ≤ 1, поэтому мы можем опустить логарифмический член, и возможно, усилить неравенство позже), то получим
где L — это средняя длина кода.
Таким образом, энтропия является минимальной границей для любого посимвольного кода со средней длиной кодового слова L. Это теорема Шеннона для канала без помех.
Теперь рассмотрим главную теорему об ограничениях систем связи, в которых информация передаётся в виде потока независимых бит и присутствует шум. Подразумевается, что вероятность корректной передачи одного бита P > 1 / 2, а вероятность того, что значение бита будет инвертировано при передачи (произойдет ошибка) равняется Q = 1 — P. Для удобства предположим, что ошибки независимы и вероятность ошибки одинакова для каждого отправленного бита — то есть в канале связи присутствует «белый шум».
Путь мы имеем длинный поток из n бит, закодированные в одно сообщение — n — мерное расширение однобитового кода. Значение n мы определим позже. Рассмотрим сообщение, состоящее из n-битов как точку в n-мерном пространстве. Поскольку у нас есть n-мерное пространство — и для простоты будем предполагать, что каждое сообщение имеет одинаковую вероятность возникновения — существует M возможных сообщений (M также будет определено позже), следовательно, вероятность любого оправленного сообщения равняется
(отправитель)
График 13.II
Далее рассмотрим идею о пропускной способности канала. Не вдаваясь в подробности, пропускная способность канала определяется как максимальный объем информации, который может быть надежно передан по каналу связи, с учётом использования максимально эффективного кодирования. Нет доводов в пользу того, что через канал связи может быть передано больше информации, чем его емкость. Это можно доказать для бинарного симметричного канала (который мы используем в нашем случае). Емкость канала, при побитовой отправки, задается как
где, как и раньше, P — вероятность отсутствия ошибки в любом отправленном бите. При отправке n независимых битов емкость канала определяется как
когда мы отправляем какое-либо из М равновероятных сообщений ai, мы имеем
При отправке n бит мы ожидаем возникновение nQ ошибок. На практике, для сообщения состоящего из n-бит, мы будем иметь приблизительно nQ ошибок в полученном сообщении. При больших n, относительная вариация ( вариация = ширина распределения, )
распределения числа ошибок будет все более узкой с ростом n.
Итак, со стороны передатчика, я беру сообщение ai для отправки и рисую сферу вокруг него радиусом
который немного больше на величину равную e2, чем ожидаемое число ошибок Q, (рисунок 13.II). Если n достаточно велико, то существует сколь угодно малая вероятность появления точки сообщения bj на стороне приемника, которая выходит за пределы этой сферы. Зарисуем ситуацию, как вижу ее я с точки зрения передатчика: мы имеем любые радиусы от переданного сообщения ai к полученному сообщению bj с вероятностью ошибки равной (или почти равной) нормальному распределению, достигающего максимума в nQ. Для любого заданного e2 существует n настолько большое, что вероятность того, что полученная точка bj, выходящая за пределы моей сферы, будет настолько малой, насколько вам будет угодно.
Теперь рассмотрим эту же ситуацию с вашей стороны (рис. 13.III). На стороне приемника есть сфера S( r) того же радиуса r вокруг принятой точки bj в n-мерном пространстве, такая, что если принятое сообщение bj находится внутри моей сферы, тогда отправленное мной сообщение ai находится внутри вашей сферы.
Как может возникнуть ошибка? Ошибка может произойти в случаях, описанных в таблице ниже:
Здесь мы видим, что, если в сфере построенной вокруг принятой точки существует еще хотя бы еще одна точка, соответствующая возможному отправленному не закодированному сообщению, то при передачи произошла ошибка, так как вы не можете определить какое именно из этих сообщений было передано. Отправленное сообщение не содержит ошибки, только если точка, соответствующая ему, находится в сфере, и не существует других точек, возможных в данном коде, которые находятся в той же сфере.
Мы имеет математическое уравнение для вероятности ошибки Ре, если было отправлено сообщение ai
Мы можем выбросить первый множитель во втором слагаемом, приняв его за 1. Таким образом получим неравенство
повторно применяем к последнему члену справа
Приняв n достаточно большим, первый член может быть принят сколь угодно малым, скажем, меньше некоторого числа d. Поэтому мы имеем
Теперь рассмотрим, как можно построить код простой замены для кодирования M сообщений, состоящих из n бит. Не имея представления о том, как именно строить код (коды с коррекцией ошибки еще не были изобретены), Шеннон выбрал случайное кодирование. Подбросьте монетку для каждого из n битов в сообщении и повторите процесс для М сообщений. Всего нужно сделать nM бросков монеты, поэтому возможны
кодовых словарей, имеющие одинаковую вероятность ½nM. Конечно, случайный процесс создания кодового словаря означает, что есть вероятность появления дубликатов, а также кодовых точек, которые будут близки друг к другу и, следовательно, будут источником вероятных ошибок. Нужно доказать, что если это не происходит с вероятностью выше, чем любой небольшой выбранный уровень ошибки, то заданное n достаточно велико.
Решающим момент заключается в том, что Шеннон усреднил все возможные кодовые книги, чтобы найти среднюю ошибку! Мы будем использовать символ Av [.], чтобы обозначить среднее значение по множеству всех возможных случайных кодовых словарей. Усреднение по константе d, конечно, дает константу, так как для усреднения каждый член совпадает с любым другим членом в сумме,
который может быть увеличен (M–1 переходит в M )
Для любого конкретного сообщения, при усреднении всех кодовых книг, кодирование пробегает все возможные значения, поэтому средняя вероятность того, что точка находится в сфере, — это отношение объема сферы к общему объему пространства. Объем сферы при этом
где s=Q+e2 Содержание книги и переведенные главы