IT. Ральф Хартли или как посчитать информацию?

Статья будет полезна тем, кто интересуется историей науки.

Перед разработчиками любой системы, в т.ч. связи стоит извечный вопрос: «Как повысить эффективность системы? Как при минимальных затратах получить максимум пользы, в каких бы единицах эта польза бы не оценивалась». Сколько писем и с какой скоростью может передать посыльный? Сколько ямщиков нужно для пересылки корреспонденции из Петербурга в Москву?

В начале XX века стали возникать новые вопросы. Двадцатые годы прошлого столетия называют бурные или ревущие двадцатые (англ. Roaring Twenties). Легче перечислить те отрасли, где не было кардинальных перемен, чем те которых коснулся научно-технический прогресс. Урбанизация в США в 1920-х годах достигла пика. Впервые количество городских жителей Америки превысило сельское население. В крупнейших городах проживало около 15 % населения, была практически завершена «электрификация всей страны» и созданы энергосбытовые компании.

Очевидно, что для отрасли «Почта. Телеграф. Телефон» – это было время бурного развития, но новые возможности формулируют новые задачи. В июле 1928 года, в корпоративном научном журнале Bell System Technical Journal Ральф Хартли публикует статью «Transmission of Information (Передача информации)».

Во введении к статье написано: «Хотя, технические характеристики систем связи интересны сами по себе, вряд ли будет оправдано их обсуждение в данном случае, если мы не сможем вывести из них что-то общее, имеющее практическое применение в проектировании систем связи. В этом направлении я надеюсь разработать количественную меру, позволяющую сравнивать возможности различных систем по передаче информации. При этом я буду обсуждать применение количественных мер в системах телеграфии, телефонии, телевидения как по проводам, так и по радиоканалам.

Предложенный метод измерения информации оказался настолько хорош, что был принят за основу, а сама статья не потеряла актуальности до сих пор. Официально перевод на русский язык был сделан в конце 50-х годов и опубликован в Сборнике переводов иностранных статей по теории информации и ее приложениям к связи. Под ред Харкевич А.А., Москва: Гос. изд. физико-математической литературы – 1959. За это время первоисточник забылся, а сама формула начала жить самостоятельной жизнью, обрастать трактовками, ее изучают школьники и студенты. Для понимания сути задачи всегда интересно почитать первоисточник. Попробуем прочитать ту часть статьи, в которой делается вывод формулы, которая нынче называется формулой Хартли. Сейчас это еще возможно сделать без привлечения специалистов по древним языкам.

Единственной сложностью для современного читателя может быть понимание примеров, основанных на коде Бодо, используемом в то время для передачи телеграфных сообщений. Современные таблицы строятся на основе 256 (28=256) первичных символов (битов), когда буквы, знаки препинания и типографские символы записываются в виде восьмиразрядного двоичного числа. Код Бодо́ — цифровой, первоначально синхронный 5-битный код, т. е. каждый знак алфавита кодируется пятиразрядным двоичным числом. Например, символ A кодируется следующим способом ..o.. Использовался в телеграфе и был понятен тогдашним читателям статьи.

Ральф Винтон Лайон Хартли

О Ральфе Хартли написано много и мало, что известно. Родился в 1888 г. в городке Спрусмонт (штат Невада). Деловой центр района, на тот момент, один из наиболее значительных и современных в Неваде. На пике развития население города насчитывало от 500 до 700 человек. Городок переживал взлеты и падения в зависимости от финансового состояния владельцев шахты. В 1883 году владелец ранчо Джаспер Харрелл скупил рудники в этом районе, город был переименован в Джаспар. Первая школа открылась здесь в 1885 году. Рудник Ада Х. открылся в 1886 году. В этом же году Компания Juniper Consolidated Mining Co. построила плавильный завод и закрыла его в следующем, за ней закрылась плавильная печь. Сама компания Starr King Co. прекратила существование в 1890 году. В этом круговороте городских событий успел родиться Ральф Хартли. Он получил высшее образование со степенью A.B. (бакалавр искусств) в Университете Юты в 1909. Как стипендиат Родса, получил степень B.A. (бакалавр искусств) в 1912 и степень B.Sc. (бакалавр наук) в 1913 в Оксфордском университете.  После возвращения из Англии Хартли приступил к работе в научно-исследовательской лаборатории Western Electric, являющейся производственной базой телефонной компании AT&T Александра Белла. Того самого Александра Белла (Alexander Graham Bell) который изобрел телефонную связь, запатентовал изобретение и основал компанию, определившую всё дальнейшее развитие телекоммуникационной отрасли в США. В нынешние времена это бы означало: после окончания университета, он поступил на работу в исследовательскую лабораторию Марка Цукерберга. Уже в тот момент можно было говорить о «success story» (история успеха), но это было только начало. Технические разработки, патенты, научные статьи – и не по одной штуке – результат деятельности инженера.

 И так, перейдем к статье.

Когда мы говорим о способности системы передавать информацию, мы подразумеваем некую количественную меру информации. Информация - это очень эластичный термин, и сначала необходимо будет придать ему более конкретное значение применительно к настоящему обсуждению.

Очень точное определение. Эластичный – легко изменяющийся под влиянием каких либо условий, т.е. в зависимости от контекста термин информация приобретает разные значения.

В качестве отправной точки для этого давайте рассмотрим элементы коммуникации, независимо от того, каким образом проходила коммуникация: по проводам, прямой речью, письменно или любым другим способом.

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

Например, в предложении «Яблоки красные» первое слово исключает другие виды фруктов и все другие предметы в целом. Второй обращает внимание на какое-то свойство или состояние яблок, а третий исключает другие возможные цвета. Однако это не исключает возможности, касающиеся размера яблок, и эта дополнительная информация может быть передана путем последующего выбора.

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

Устранение психологических факторов

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

 

Рисунок 1.

Из-за помех символы, получаемые приемником записывающего устройства на другом конце кабеля, не так четко различимы, в отличие от отправленных оператором. На рис. 1 в точке A показана последовательность положений клавиш, а в точках B, C и D – кривые, построенные записывающим устройством при приеме по кабелю связи все большей длины.

Для самого короткого кабеля B восстановить исходную последовательность несложно. Однако для промежуточной длины C требуется больше внимания, чтобы отличить, какое положение ключа представляет конкретная часть записи. В D символы стали безнадежно неразличимы. Способность системы передавать конкретную последовательность символов зависит от возможности распознавания принимающей стороной результатов различных выборов, сделанных отправляющей стороной.

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

Браво, автор! Вполне современная шутка.
– До нас не доходят ваши СМС сообщения.
– Попробуйте перечитать их дважды.

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

Количественное выражение информации

При каждом выборе доступны три положения ключа (+/-/0). Два последовательных выбора делают возможными 32 или 9 различных перестановок или наборов символов. Точно так же n вариантов выбора делают возможными 3n различных наборов. Предположим, что вместо этой системы, в которой используется три значения тока (+/-/0), предоставляется одна, в которой может быть любое произвольное число s значений тока. Тогда количество символов, доступных при каждом выборе, равно s, а количество различных наборов символов равно sn.

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

Рассмотрим случай системы печатного телеграфа типа Бодо, в которой оператор выбирает буквы или другие символы, которые кодируются при передаче последовательностью других символов. Мы можем думать о различных текущих значениях как о первичных символах и о различных их последовательностях, которые представляют закодированные или вторичные символы (буквы – прим. переводчика).

Затем на передающей стороне может быть сделан выбор между первичными или вторичными символами. Пусть оператор выберет последовательность из n2 символов каждая, состоящую из последовательности n1 первичных символов. При каждом выборе ему будет доступно столько различных вторичных символов, сколько различных последовательностей может возникнуть в результате выполнения n1 выборов из числа s первичных символов. Обозначим количество вторичных символов s2, то

\[s_2 = s^n_1.\] \[(1)\]
Для системы Бодо
\[s^2 = 2^5 = 32,\]
\[s_2^{n_1}=s^{n_1 n_2}.\] \[(3)\]

Теперь n1n2 – это число n вариантов выбора первичных символов, которые потребовались бы для создания той же последовательности, если бы не было механизма для группировки первичных символов во вторичные символы. Таким образом, мы видим, что общее количество возможных последовательностей составляет sn независимо от того, были сгруппированы первичные символы для целей интерпретации или нет.

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

Для конкретной технической системы и ее режима работы s можно считать фиксированным, а количество вариантов выбора n увеличивается по мере продолжения связи. Следовательно, объем передаваемой информации будет увеличиваться экспоненциально с увеличением количества вариантов наборов, а вклад одного набора в общую передаваемую информацию будет постепенно увеличиваться. Несомненно, такое усиление часто происходит в общении с психологической точки зрения. Например, одно слово «да» или «нет» в конце продолжительной дискуссии может иметь чрезвычайно большое значение. Однако такие случаи – скорее исключение, чем правило. Постоянное изменение предмета обсуждения и даже вовлеченных лиц на практике ограничивает совокупное действие этого экспоненциального отношения сравнительно короткими периодами. Более того, мы устанавливаем меру, которая не должна зависеть от психологических факторов. Когда мы рассматриваем систему передачи данных с технической точки зрения, мы не видим необходимости экспоненциального увеличения мощности оборудования для передачи увеличивающейся информации. Различные используемые первичные символы столь же различимы на принимающей стороне как для одного первичного набора, так и для другого. Система телеграфа демонстрирует, что передать одно сообщение из десяти слов не сложнее, чем предыдущее. Телефонная система, которая теперь успешно передает речь, будет продолжать делать это, пока система остается неизменной.

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

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

\[H=K_n,\] \[(4)\]

где K - константа, которая зависит от количества символов s, доступных при каждом выборе. Возьмем любые две системы, для которых s имеет значения s1 и s2, и пусть соответствующие константы равны К1 и К2. Затем мы ограничим эти константы следующим условием: всякий раз, когда количество вариантов выбора n1 и n2 для двух систем таково, что количество возможных последовательностей одинаково для обеих систем, тогда количество информации также одинаково для обеих, т.е. когда

\[s_1^{n_1} = s_2^{n_2},\] \[(5)\]
\[H=K_1 n_1=K_2 n_2,\] \[(6)\]

из этого следует:
\[K_1/logs_1=K_2/logs_2,\] \[(7)\]

Это соотношение будет выполняться для всех значений s, только тогда когда K связано с s отношением
\[K=K_0 logs,\] \[(8)\]

где K0 одинаково для всех систем. Поскольку K0 произвольно, мы можем опустить его, если сделаем логарифмическое основание произвольным. Выбранная конкретная база фиксирует размер единицы информации. Подставляя это значение K в (4) получаем

\[H=nlogs,\] \[(9)\]
\[H=logs^n\] \[(10)\]

Вот она знаменитая формула Хартли. В современном виде это звучит так:
Формула Хартли, хартлиевское количество информации или мера Хартли – логарифмическая мера информации, которая определяет количество информации, содержащееся в сообщении.

\[I=Klog_2 N,\] \[(11)\]

Где N – количество символов в используемом алфавите (мощность алфавита), K – длина сообщения (количество символов в сообщении), I – количество информации в сообщении в битах.

Если мы положим n равным единице, мы увидим, что информация, связанная с одним набором, является логарифмом количества доступных символов. Например, в упомянутой выше системе Бодо количество s первичных символов или текущих значений равно 2, а информационное содержание одного набора – log 2; для символа, который включает 5 вариантов набора, будет 5 log 2. Тот же результат будет получен, если мы рассмотрим символ как вторичный символ и возьмем логарифм количества этих символов, то есть log 25 или 5 log 2. Информация, связанная со 100 символами, будет равна 500 log 2. Количественное значение информации будет зависеть от логарифмической функции. Увеличение количества символов в сообщении с 2 до 10, то есть в пять раз, увеличило бы информативность данного сообщения в соотношении:

\[log_2 10/log_2 2=3.3.\] \[(12)\]

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

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

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

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

\[\sum_1^{n_2} logs_2=nlogs,\] \[(13)\]

где n - общее количество первичных символов или длин точек, присвоенных символам n2. Это говорит о том, что первичные символы представляют собой наиболее удобную основу для оценки информации.

Так и порешили – информацию будем считать в битах.

Что же остается в итоге? Что предложил Хартли?

 – Сделал попытку дать определение понятия «информация».

– Показал, что количество информации зависит от количества символов в используемом алфавите (мощность алфавита) и длины сообщения.

– Предложил измерять информацию в первичных символах, в настоящее время информация измеряется в битах.