Как шум и ошибки привели к созданию теории информации: от Найквиста до Шеннона

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

Автор статьи: Владимир Куценко, программист, исследователь зарождения и развития новых ИТ-областей.

Структура реферата

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

Каждый раздел включает следующие компоненты

• Описание проблемы, которую стремились решить ученые.
• Анализ предложенных решений: какие методы и подходы были использованы.
• Из каких областей знаний были заимствованы идеи.
• Факторы, обеспечившие реализацию решений: технические, математические или инженерные принципы, которые сделали возможным применение данных подходов.

Основные разделы

• Гарри Найквист — Certain factors affecting telegraph speed (1924)
• Ральф Хартли — Transmission of information («Передача информации», 1928)
• Ричард Хемминг — Error Detecting and Error Correcting Codes (1950)
• Бернард Оливер, Джон Р. Пирс и Клод Шеннон — The Philosophy of PCM («Принципы кодово-импульсной модуляции», 1948)
• Клод Шеннон — The Mathematical Theory of Communication («Математическая теория связи», 1948)
• Выводы: анализ развития ключевых концепций и их влияния на становление теории информации

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

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

ЧИТАЙТЕ ТАКЖЕ

• Концентрированный реферат по «архитектуре фон Неймана», в котором рассматриваются ключевые концепции работы американского математика Джона фон Неймана «First Draft of a Report on the EDVAC
• Концентрированный реферат по «машине Тьюринга», в котором рассматриваются ключевые концепции теории вычислений

Гарри Найквист — Certain factors affecting telegraph speed (1924)

Описание проблемы

В 1920 году Гарри Найквист занимался проблемой увеличения скорости передачи данных по телеграфу, включая разведывательную информацию (intelligence). Для этого ему нужно было решить три задачи, которые не были решены до него, а именно: 

1. Ввести количественные измерения передачи данных в телеграфии.
2. Определить факторы, ограничивающие скорость передачи.
3. Найти способы устранения или минимизации влияния этих факторов.

ЦИТАТА. Certain Factors Affecting Telegraph Speed By H. NYQUIST

Synopsis: This paper considers two fundamental factors entering into the maximum speed of transmission of intelligence by telegraph.

ПЕРЕВОД. Некоторые факторы, влияющие на скорость телеграфа, автор — Г. Найквист

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

Источник: H. Nyquist. Certain factors affecting telegraph speed. Bell Syst. Tech. J. Vol. 3, 1922. P. 324.

Анализ предложенных решений

а) Физический уровень передачи: увеличение качества сигнала

Прежде всего Найквист определил передаваемый сигнал как набор элементов – так ученый называл импульсное напряжение, передаваемое через равные промежутки времени. Например, латинская буква «а» в кодировке Морзе состоит из пяти сигналов: сигнала для «точки», сигнала для «пробела» и трех сигналов для «тире».

ЦИТАТА. Before proceeding with this discussion two terms, which will be used in this paper, and which are considered to be of fundamental importance, will be defined—"signal element" and "line speed." It is usually possible, especially when sending is done mechanically, to divide the time into short intervals of approximately equal duration, such that each is characterized by a definite, not necessarily constant, voltage impressed at the sending end. The part of the signal which occupies one such unit of time will be called a "signal element." For example, the letter a in ordinary land telegraphy will be said to be made up of five signal elements, the first constituting a dot, the second a space and the next three a dash. The "line speed," as used in this paper, equals the number of signal elements per second divided by two. In ordinary land telegraphy the line speed is equal to the dot frequency when a series of dots separated by unit spaces is transmitted. КОНЕЦ ЦИТАТЫ.

ПЕРЕВОД. Прежде чем приступить к обсуждению, необходимо дать определение двум терминам, которые будут использоваться в данной статье и которые считаются фундаментально важными, — «элемент сигнала» и «скорость линии». Обычно, особенно при механической передаче, можно разделить время на короткие интервалы примерно одинаковой длительности, каждый из которых характеризуется определенным, не обязательно постоянным, напряжением, подаваемым на передающий конец. Часть сигнала, занимающая одну такую единицу времени, будет называться «элементом сигнала». Например, буква «a» в обычном наземном телеграфе состоит из пяти сигнальных элементов, первый из которых представляет собой точку, второй — пробел, а три последующих — тире. «Скорость линии», в контексте данной статьи, равна количеству сигнальных элементов в секунду, деленному на два. В обычной наземной телеграфии линейная скорость равна частоте точек, когда передается серия точек, разделенных единичными пробелами.

Источник: H. Nyquist. Certain factors affecting telegraph speed. Bell Syst. Tech. J. Vol. 3, 1922. P. 325.

Найквист также дал количественное определение качества сигнала. Оно зависело от двух параметров: от значения силы тока принимаемого сигнала и от количества помех (interference), создаваемых элементами сигнала.

ЦИТАТА. These factors are signal shaping and choice of codes. The first is concerned with the best wave shape to be impressed on the transmitting medium so as to permit of greater speed without undue interference either in the circuit under consideration or in those adjacent, while the latter deals with the choice of codes which will permit of transmitting a maximum amount of intelligence with a given number of signal elements. [...]

Signal Shaping

Several different wave shapes will be assumed and comparison will be made between them as to:

1. Excellence of signals delivered at the distant end of the circuit, and

2. Interfering properties of the signals. КОНЕЦ ЦИТАТЫ.

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

Формирование сигнала

Будут приняты несколько различных форм волн, и будет проведено сравнение между ними в отношении:

1. Превосходство сигналов, подаваемых на удаленный конец цепи, и

2. Мешающие свойства сигналов.

Источник: H. Nyquist. Certain factors affecting telegraph speed. Bell Syst. Tech. J. Vol. 3, 1922. P. 324.

Увеличение значений силы тока принимаемого сигнала

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

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

• Прямоугольная волна
• Синусоидальная волна
• Прямоугольная волна, пропущенная через заданную электрическую сеть элементов

ЦИТАТА. A number of different wave forms which might be employed to make up the telegraph signal elements will next be examined, consideration being given first to the waves which will be received at the distant end when the different wave forms are impressed at the transmitting end and second to the interference which will be produced in the higher range of frequencies which has been assigned to other uses.

Three forms of voltage waves which will be considered are shown in Fig. 1. A in that figure shows the simplest form of voltage wave, namely, the rectangular form which is produced by applying a battery for a given interval of time and then substituting a short circuit for it. C in the figure is the wave produced by transmitting the rectangular voltage wave A through an electrical network which is the one indicated by the letter D in the figure. (Other forms of networks might also be selected which would produce similar results.) B in the figure is a wave which has the shape of a half cycle of a sine wave. In what follows this wave will be referred to as the "halfcycle sine wave.” КОНЕЦ ЦИТАТЫ.

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

Три формы волн напряжения, которые будут рассмотрены, показаны на Рис. 1. Указателем А на этом рисунке показана простейшая форма волны напряжения, а именно прямоугольная форма, которая образуется при подаче напряжения на батарею в течение определенного промежутка времени и последующей замене её коротким замыканием. Указатель С на рисунке — это волна, возникающая при передаче прямоугольной волны напряжения А через электрическую сеть, обозначенную на рисунке буквой D. (Можно выбрать и другие формы сетей, которые дадут аналогичные результаты.) Указатель B на рисунке — это волна, имеющая форму полуцикла синусоиды. В дальнейшем она будет называться «полуцикловой синусоидой».

Источник: H. Nyquist. Certain factors affecting telegraph speed. Bell Syst. Tech. J. Vol. 3, 1922. P. 326.

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

ЦИТАТА. In considering the waves which will be received when the above waves are applied at the transmitting end, use will be made of the following general principles, which have been stated by Malcolm, for the case of a submarine cable circuit and discussed for the general case in Appendix A.

When a telegraph circuit is worked at a line speed as high as will be permitted by the available frequency range, the shape of the received signal will be practically independent of the shape of the transmitted signal, and further, the magnitude of the received signal will be approximately directly proportional to the area included within the impressed voltage wave.

The area included within the impressed voltage wave being of principal importance so far as the wave received at the distant end is concerned, the areas under the three voltage waves shown in Fig. 1 will next be examined. The areas under waves A and C will be found to be substantially equal while the area under the wave B is only about 0.6 as great. Consequently, it should be expected that waves A and C will be about equally good from the standpoint of the received signals, while wave B will be poorer, producing received signals only about 0.6 as great in magnitude. If the maximum voltage (or power) impressed at the sending end is limited to some given value, the rectangular wave is seen to be the optimum, since this wave has the maximum area. While the area shown under curve C is approximately equal to that under the rectangular wave, the effect produced when a number of signal elements of the same polarity and magnitude are sent in succession is such that the maximum voltage transmitted will exceed slightly the corresponding voltage for the case of the unmodified rectangular wave due to overlapping of adjacent signal elements.

The above comparison of the three waves of Fig. 1 from the standpoint of received signals holds not only for signal elements, but also for complex waves comprising a number of elements. Since for the speeds under consideration the received currents for different shapes of signals applied at the sending end are substantially of the same form, differing, at most, in magnitude, it follows from the principle of superposition that any complex signal, whether built up of elements of one shape or another at the sending end, will produce substantially the same wave form at the receiving end, the differences in the shapes of the elements at the sending end producing differences principally in magnitude of the received waves. КОНЕЦ ЦИТАТЫ.

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

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

Поскольку площадь, входящая в состав волны напряжения, имеет основное значение для волны, принимаемой на удаленном конце, далее будут рассмотрены площади под тремя волнами напряжения, показанными на рис. 1. Выяснится, что площади волн A и C практически равны, в то время как площадь волны B всего лишь на 0,6 больше. Следовательно, можно ожидать, что волны A и C будут примерно одинаково хороши с точки зрения принимаемых сигналов, в то время как волна B будет хуже, создавая принимаемые сигналы только примерно на 0,6 больше по величине. Если максимальное напряжение (или мощность), подаваемое на передающий конец, ограничено некоторым заданным значением, то оптимальной будет прямоугольная волна, поскольку она имеет максимальную площадь. Хотя площадь, показанная под кривой С, приблизительно равна площади прямоугольной волны, эффект, возникающий при последовательной передаче нескольких элементов сигнала одинаковой полярности и величины, таков, что максимальное передаваемое напряжение будет немного превышать соответствующее напряжение для случая немодифицированной прямоугольной волны из-за наложения соседних элементов сигнала.

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

Источник: H. Nyquist. Certain factors affecting telegraph speed. Bell Syst. Tech. J. Vol. 3, 1922. P. 326-327.

Уменьшение количества помех

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

ЦИТАТА. Consideration will next be given to the relative interference which the different wave forms of Fig. 1 will produce in the frequency range assigned to other circuits. Since interference into other circuits results from having the telegraph signal elements contain frequencies which spread into the ranges assigned to other circuits, it is evident that the wave will be the best from the standpoint of interference which contains the least amount of these outside frequencies. making use of a method which is discussed in Appendix C, the frequency components of the three waves illustrated in Fig. 1 have been computed and are shown in Fig. 2. The frequency marked 1/2 T in the drawing equals the line speed. T in this connection has the same value as in Fig. 1. The letters in this figure refer to the corresponding waves in Fig. 1, A being the components of an isolated rectangular wave, B the corresponding components for the half-cycle sine wave, and C those for the rectangular wave after it has been transmitted through the network D in Fig. 1. It is seen from Fig. 2 that the rectangular wave form A contains the greatest amount of currents of higher frequencies and is, therefore, the poorest from the standpoint of interference. The half-cycle sine wave contains less. of these higher frequencies although, as will be seen, the highfrequency components are far from negligible. The wave C is the best from the standpoint of interference, since it contains the least amount of these higher frequencies.

From the preceding it is concluded that for the case under consideration, the wave form C in Fig. 1 produced by sending a rectangular shaped signal element through a suitable network is the most suitable. This wave form is almost the optimum from the standpoint of the received signals while from the standpoint of interference into other circuits it leaves little to be desired. КОНЕЦ ЦИТАТЫ.

ПЕРЕВОД. Далее будет рассмотрен вопрос об относительных помехах, которые различные формы волн рис. 1 будут создавать в диапазоне частот, отнесенных к другим цепям. Поскольку помехи в других цепях возникают в результате того, что элементы телеграфного сигнала содержат частоты, которые распространяются в диапазоны, отведенные другим цепям, очевидно, что наилучшей с точки зрения помех будет та волна, которая содержит наименьшее количество этих внешних частот. Используя метод, который рассматривается в Приложении С, были вычислены частотные компоненты трех волн, изображенных на рис. 1, и показаны на рис. 2. Частота, обозначенная на рисунке 1/2 T, равна линейной скорости. T в этом соединении имеет то же значение, что и на рис. 1. Буквы на этом рисунке обозначают соответствующие волны на рис. 1: A — компоненты изолированной прямоугольной волны, B — соответствующие компоненты для полупериодической синусоидальной волны, C — для прямоугольной волны после её передачи через сеть D на рис. 1. Из рис. 2 видно, что прямоугольная волна формы А содержит наибольшее количество токов более высоких частот и, следовательно, является самой плохой с точки зрения интерференции. Полуцикловая синусоида содержит меньше этих высоких частот, хотя, как мы увидим, высокочастотные компоненты далеко не пренебрежимо малы. Волна C является наилучшей с точки зрения интерференции, так как она содержит наименьшее количество этих высоких частот.

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

Источник: H. Nyquist. Certain factors affecting telegraph speed. Bell Syst. Tech. J. Vol. 3, 1922. P. 327-329.

б) Логический уровень передачи: увеличение скорости передачи информации

Количественное определение передачи информации

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

ЦИТАТА.

APPENDIX B

Use has been made of the formula 

W = K log m 

where W = the speed of transmission of intelligence, K = a constant, and m = the number of current values employed. 

The assumptions which underlie this formula and its derivation will now be given.

Let us assume a code whose characters are all of the same duration. This is usually the case in printer codes. If n is the number of signal elements per character, then the total number of characters which can be construed equals mⁿ. In order that two such systems should be equivalent, the total number of characters that can be distinguished should be the same. In other words,

mⁿ = const. (1) 

This equation may also be written

n log m = const. (2)

The speed with which intelligence can be transmitted over a circuit is directly proportional to the line speed and inversely proportional to the number of signal elements per character provided that the relations above are satisfied. Hence, we may write

W = s/n (3) 

where s is the line speed. Substituting the value of n derived from the equation above, this equation becomes 

W = (s log m) / const. (4) 

which may also be written 

W = K log m (5) 

КОНЕЦ ЦИТАТЫ.

ПЕРЕВОД.

ПРИЛОЖЕНИЕ В

Использована 

W = K log m 

где W = скорость передачи информации, K = константа, а m = количество используемых значений тока. 

Теперь будут приведены предположения, лежащие в основе этой формулы и её вывода.

Предположим, что код состоит из символов одинаковой длительности. Так обычно поступают в принтерных кодах. Если n — число элементов сигнала на символ, то общее число символов, которые могут быть истолкованы, равно mⁿ. Для того чтобы две такие системы были эквивалентны, общее число различаемых символов должно быть одинаковым. Другими словами,

mⁿ = const. (1) 

Это уравнение также можно записать следующим образом:

n log m = const. (2)

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

W = s/n (3) 

где s — это скорость линии. Если подставить значение n, полученное из уравнения выше, мы получим уравнение следующего вида:

W = (s log m) / const. (4) 

которое также можно записать следующим образом:

W = K log m (5) 

Источник: H. Nyquist. Certain factors affecting telegraph speed. Bell Syst. Tech. J. Vol. 3, 1922. P. 342-343.

в) Уплотнение кодирования сигнала

Физический уровень

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

ЦИТАТА. Comparison will then be made between the theoretical possibilities indicated by the formula and the results obtained by various codes in common use, including the Continental and American Morse codes as applied to land lines, radio and carrier circuits, and the Continental Morse code as applied to submarine cables. It will be shown that the Continental and American Morse codes applied to circuits using two current values are materially slower than the code which it is theoretically possible to obtain because of the fact that these codes are arranged so as to be readily deciphered by the ear. On the other hand, the Continental Morse code, as applied to submarine cables, or other circuits where three current values are employed, will be shown to produce results substantially on par with the ideal. Taking the above factors into account, it will be shown that if a given telegraph circuit using Continental Morse code with two current values were rearranged so as to make possible the use of a code employing three current values, it would be possible to transmit over the rearranged circuit about 2.2 times as much intelligence with a given number of signal elements.

It will then be pointed out why it is not feasible on all telegraph circuits to replace the codes employing two current values with others employing more than two current values, so as to increase the rate of transmitting intelligence. The circuits, for which the possibilities of thus securing increases in speed appear greatest, are pointed out, as well as those for which the possibilities appear least.

Theoretical Possibilities Using Codes with Different Numbers of Current Values

The speed at which intelligence can be transmitted over a telegraph circuit with a given line speed, i.e., a given rate of sending of signal elements, may be determined approximately by the following formula, the derivation of which is given in Appendix B.

W = K log m

Where W is the speed of transmission of intelligence, m is the number of current values, and, K is a constant.

By the speed of transmission of intelligence is meant the number of characters, representing different letters, figures, etc., which can be transmitted in a given length of time assuming that the circuit transmits a given number of signal elements per unit time.

Substituting numerical values in this formula gives the following table which indicates the possibilities of speeding up the transmission of intelligence by increasing the number of current values.

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

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

Теоретические возможности использования кодов с различным числом значений тока

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

W = K log m

Где W — скорость передачи информации, m —  число текущих значений, а K — константа.

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

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

Источник: H. Nyquist. Certain factors affecting telegraph speed. Bell Syst. Tech. J. Vol. 3, 1922. P. 332-333.

Уплотнение кодирования на логическом уровне

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

ЦИТАТА. It will be seen that the figures deduced for the Continental Morse and the American Morse are substantially identical for two current values. This result probably does not correspond with practice; it is thought that the difference in speed between these two codes is considerably greater, say on the order of 10 or 15 per cent, in favor of the American Morse. The discrepancy is due partly to the fact that no account has been taken of figures and punctuation marks in the present computations and partly to the fact that the assumptions as to relative lengths of space is not strictly in accordance with practice.

From the foregoing, it is seen that there is a two-fold gain in changing from the two-current-value American or Continental Morse codes to the three-current-value Continental code. In the first place, there is a theoretical increase in the ratio of 1.6:1 which accompanies the change from the two-current-value to the three-currentvalue code. In the second place, there is an incidental increase in the ratio of 1.4:1, due to the fact that the present two-current-value codes are longer than would be necessary, if receiving were done by means other than the ear. The total increase in going from the two-currentvalue Continental or American Morse codes to the three-currentvalue Continental code is, therefore, in the ratio of 1.6 X 1.4:1 or 2.2:1, provided the line speed is the same. In this connection it should be noted that in the case of the American Morse, the ratio is probably somewhat less than this for the reasons pointed out above. КОНЕЦ ЦИТАТЫ.

ПЕРЕВОД. Видно, что цифры, выведенные для континентального Морзе и американского Морзе, практически идентичны для двух значений тока. Этот результат, вероятно, не соответствует практике; считается, что разница в скорости между этими двумя кодами значительно больше, порядка 10 или 15 процентов, в пользу американского Морзе. Это расхождение частично объясняется тем, что в настоящих расчетах не учитывались цифры и знаки препинания, а частично тем, что предположения об относительной длине пространства не строго соответствуют практике.

Из вышесказанного видно, что переход от двухточечного американского или континентального кодов Морзе к трехточечному континентальному коду дает двойную выгоду. Во-первых, теоретически увеличивается соотношение 1,6:1, которое сопровождает переход от двухтонового кода к трехтоновому. Во-вторых, существует случайное увеличение соотношения 1,4:1, связанное с тем, что нынешние коды с двумя значениями тока длиннее, чем это было бы необходимо, если бы прием осуществлялся с помощью других средств, кроме уха. Таким образом, общее увеличение при переходе от двухтокового континентального или американского кода Морзе к трехтоковому континентальному коду составляет 1,6 X 1,4:1 или 2,2:1, при условии, что скорость линии одинакова. В связи с этим следует отметить, что в случае американского кода Морзе это соотношение, вероятно, несколько меньше указанного по причинам, указанным выше.

Источник: H. Nyquist. Certain factors affecting telegraph speed. Bell Syst. Tech. J. Vol. 3, 1922. P. 334-335.

Из каких областей знаний были заимствованы идеи

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

Факторы, обеспечившие реализацию решений

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

• H. W. Malcolm. Theory of the Submarine Telegraph and Telephone Cable. The Electrician Printing & Publishing Co. March 1917.
• J. R. Carson. Theory of the Transient Oscillations of Electrical Networks and Transmission Systems. A.I.E.E. Trans. Vol. XXXVIII. 1919. P. 345.

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

Необходимость передачи большого объема данных, которая возникла в 1920-х годах, подтолкнула разрабатывать соответствующую теорию, а также оптимизировать линии связи, которые существовали на то время: провода, радио и подводные кабеля.

Ральф Хартли — Transmission of information («Передача информации», 1928)

Описание проблемы

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

ЦИТАТА. Хотя частотные соотношения, касающиеся электрической связи, интересны даже и сами по себе, однако их рассмотрение в данном случае едва ли было бы оправдано, если бы мы не могли вывести из них некоторых вполне общих практических приложений к технике связи. Я надеюсь, что в этом направлении мне удалось установить количественную меру, посредством которой можно сравнивать пропускную способность различных систем передачи информации. При этом я буду рассматривать применение этой меры к системам телеграфии, телефонии, передачи изображений и телевидения как по проводам, так и по радиоканалам. Окажется, конечно, что в очень многих случаях экономически невыгодно полностью использовать физические возможности системы. Однако такой подход зачастую полезен для оценки возможного улучшения работы, ожидаемого в результате усовершенствования аппаратуры или цепей, а также для выявления ошибок в теории работы какой-либо предлагаемой системы. КОНЕЦ ЦИТАТЫ.

Источник: Р. Хартли. Передача информации. // Теория информации и ее приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 5-6.

Анализ предложенных решений

а) Измерение количества информации 

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

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

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

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

ЦИТАТА. Пусть при каждом выборе возможны три различных символа. При двух последовательных выборах возможны 3² = 9 различных перестановок или последовательностей символов. Подобным же образом при n выборах возможны 3ⁿ различных последовательностей. Предположим, что вместо этой системы, в которой используются три значения тока, имеется другая, где в линию можно подать любое произвольное число s различных значений тока и отличить их друг от друга на приемном конце. Тогда число символов, возможных при каждом выборе, есть s, а число различных последовательностей есть sⁿ. 

Рассмотрим случай печатающей телеграфной системы типа Бодо, где оператор выбирает буквы или другие знаки, каждый из которых при передаче состоит из последовательности нескольких символов (обычно пяти). В качестве первичных символов мы можем представлять себе различные значения тока, в качестве вторичных символов — их последовательности, представляющие те или иные знаки. На передающем конце может делаться выбор как первичных, так и вторичных символов. Пусть оператор выбирает последовательность из n₂ знаков, каждый из которых создается последовательностью n₁ первичных выборов. При каждом выборе он имеет в своем распоряжении столько различных вторичных символов, сколько различных последовательностей может получиться в результате n₁ выборов из s первичных символов. Если обозначить число вторичных символов через s₂, то 

s₂ = sⁿ¹ (1)

В системе Бодо 

s₂ = 2⁵ = 32 знака (2)

Число возможных последовательностей вторичных символов, получающихся в результате n₂ вторичных выборов, есть 

s₂ⁿ² = sⁿ¹ⁿ² (3) 

Но n₁n₂ есть число n выборов первичных символов, необходимое для создания той же последовательности в отсутствие механизма для группировки первичных символов во вторичные. Мы видим, таким образом, что полное число возможных последовательностей есть sⁿ независимо от того, группируются ли первичные символы в целях их интерпретации или нет. 

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

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

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

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

Н = Кn, (4)

где К — константа, зависящая от числа s возможных при каждом выборе символов. Возьмем две системы, в которых s имеет значения s₁ и s₂, и пусть соответствующие константы будут К₁ и К₂. Определим эти константы следующим условием: если числа выборов n₁ и n₂ в двух системах таковы, что число возможных последовательностей в обеих системах одинаково, то одинаково и количество информации, т. е. если 

s₁ⁿ¹ = s₂ⁿ², (5)

то

Н = К₁n₁ = К₂n₂, (6)

откуда

К₁ / log s₁ = К₂ / log s₂. (7)

Это соотношение справедливо для всех значений s только тогда, когда К связано с s соотношением 

К = К₀ log s, (8),

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

H = n log s, (9) 
H = log sⁿ. (10) 

Сделанное нами сводится, следовательно, к тому, что в качестве практической меры информации мы берем логарифм числа возможных последовательностей символов. КОНЕЦ ЦИТАТЫ.

Источник: Р. Хартли. Передача информации. // Теория информации и ее приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 9-12.

б) Определение ограничивающих факторов

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

Во-первых, взаимной интерференцией символов

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

ЦИТАТА. Чтобы обеспечить максимальную скорость передачи, выборы должны делаться с постоянной скоростью. На первый взгляд может показаться, что в начале передачи сообщения, когда имеется меньшее число предшествующих символов, создающих интерференцию, можно делать выборы с меньшими интервалами. Однако при этом предполагается, что перед началом работы система бездействовала. Фактически же передача предшествующего сообщения могла быть закончена последовательностью, создающей максимальную интерференцию. КОНЕЦ ЦИТАТЫ.

Источник: Р. Хартли. Передача информации. // Теория информации и ее приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 17.

Во-вторых, накоплением энергии в различных электрических элементах системы

Частота передачи символов ограничена процессами накопления и рассеивания энергии в элементах системы.

ЦИТАТА. [...] …во всех случаях мы находим, что если все диссипативные и накапливающие элементы подвергаются той же участи, как в только что рассмотренном простом случае, то все показатели затухания и собственные частоты изменяются подобным же образом. При исследовании механических систем нужно заменить электрические сопротивления их механическими эквивалентами, а индуктивности и емкости — массами и коэффициентами жесткости. Позднее мы используем тот общий вывод, согласно которому пропорциональное изменение всех накапливающих энергию элементов, не сопровождающееся изменением диссипативных элементов приводит к обратному изменению возможной скорости передачи. КОНЕЦ ЦИТАТЫ.

Источник: Р. Хартли. Передача информации. // Теория информации и ее приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 22-23.

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

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

Это приводит нас к важному выводу, что максимальная скорость передачи информации, возможная в системе, частотный диапазон которой ограничен некоторой областью, пропорциональна ширине этой полосы частот. Отсюда и следует, что общее количество информации, которое может быть передано посредством такой системы, пропорционально произведению передаваемой полосы частот на время, в течение которого система используется для передачи. КОНЕЦ ЦИТАТЫ.

Источник: Р. Хартли. Передача информации. // Теория информации и ее приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 24.

в) Определение способов повышения скорости передачи информации

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

Физический уровень представления сообщений

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

ЦИТАТА. Процесс модуляции, столь широко применяемый в радиосвязи и в передаче по проводам на несущей частоте, позволяет сдвинуть частотный диапазон сообщения в новое положение на шкале частот без изменения ширины полосы. Это сразу же следует из того общеизвестного факта, что стационарное описание сигнала, получаемого при модуляции несущей частоты символами, содержит две боковые полосы, в каждой из которых имеются компоненты, соответствующие каждой стационарной компоненте модулирующего сигнала. Частота каждой компоненты боковой полосы отличается от несущей на частоту соответствующей компоненты модулирующего сигнала. Исключение одной из боковых полос дает сигнал, сохраняющий всю информацию, заключенную в модулирующих символах, и занимающий частотный диапазон такой же ширины, как и модулирующий сигнал, но только сдвинутый по шкале частот в новое положение, определяемое несущей частотой. Допустимый интервал между этими смещенными сообщениями при работе на несущей частоте определяется избирательностью фильтров, используемых для их разделения. КОНЕЦ ЦИТАТЫ.

Источник: Р. Хартли. Передача информации. // Теория информации и ее приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 25-26.

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

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

Источник: Р. Хартли. Передача информации. // Теория информации и ее приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 26.

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

ЦИТАТА. И хотя согласование диапазонов сообщений и линий при наличии их в достаточном количестве теоретически возможно посредством модуляции и подразделения частотных диапазонов сообщений, однако практически это не всегда целесообразно. Иногда желательнее воспользоваться другим, уже упомянутым способом преобразования, который заключается в записи последовательности символов и ее воспроизведении с другой скоростью для получения сигнала, используемого для передачи. Таким именно образом используется лента при телеграфной передаче сообщений. Здесь последовательность символов представляет ряды выборов вторичных символов. Эти выборы делаются с такой скоростью, при которой оператору удобно манипулировать ключами перфорирующей машины. Электрический сигнал, подаваемый в линию соответственно положению отверстий в ленте, представляет соответствующую последовательность первичных символов. Скорость их подачи на линию определяется скоростью ленты при воспроизведении. Так как при заданном числе различных первичных символов требуемый частотный диапазон пропорционален скорости выполнения выборов, то очевидно, что частотный диапазон сообщения, воспроизводимого с ленты, может быть согласован с частотным диапазоном любой имеющейся линии, по крайней мере, постольку, поскольку дело касается ширины полосы. КОНЕЦ ЦИТАТЫ.

Источник: Р. Хартли. Передача информации. // Теория информации и ее приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 26-27.

Логический уровень представления сообщений

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

ЦИТАТА. Если первообразное сообщение является непрерывной функцией времени, как в случае речи, то можно воспользоваться тем же методом, заменив ленту фонограммой. Очевидно, что и в этом случае требуемый частотный диапазон линии прямо пропорционален скорости воспроизведения и обратно пропорционален времени; для этого достаточно учесть, что неточно определенный сигнал эквивалентен последовательности конечных ступеней, а точно определенный сигнал — последовательности бесконечно малых ступеней. Со стационарной точки зрения все частотные компоненты изменяются в отношении скоростей записи и воспроизведения; следовательно, в том же отношении изменяются и занимаемые диапазоны. КОНЕЦ ЦИТАТЫ.

Источник: Р. Хартли. Передача информации. // Теория информации и ее приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 28.

Из каких областей знаний были заимствованы идеи

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

Факторы, обеспечившие реализацию решений

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

Ричард Хемминг — Error Detecting and Error Correcting Codes (1950)

Описание проблемы

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

ЦИТАТА. The author was led to the study given in this paper from a consideration of large scale computing machines in which a large number of operations must be performed without a single error in the end result. This problem of "doing things right" on a large scale is not essentially new; in a telephone central office, for example, a very large number of operations are performed while the errors leading to wrong numbers are kept well under control, though they have not been completely eliminated. [...]

In some situations self checking is not enough. For example, in the Model 5 Relay Computers built by Bell Telephone Laboratories for the Aberdeen Proving Grounds,' observations in the early period indicated about two or three relay failures per day in the 8900 relays of the two computers, representing about one failure per two to three million relay operations. The self checking feature meant that these failures did not introduce undetected errors. Since the machines were run on an unattended basis over nights and week-ends, however, the errors meant that frequently the computations came to a halt although often the machines took up new problems. The present trend is toward electronic speeds in digital computers where the basic elements are somewhat more reliable per operation than relays. However, the incidence of isolated failures, even when detected, may seriously interfere with the normal use of such machines. Thus it appears desirable to examine the next step beyond error detection, namely error correction. [...]

The need for error correction having assumed importance only recently, very little is known about the economics of the matter. It is clear that in using such codes there will be extra equipment for encoding and correcting errors as well as the lowered effective channel capacity referred to above. Because of these considerations applications of these codes may be expected to occur first only under extreme conditions. Some typical situations seem to be:

a. unattended operation over long periods of time with the minimum of standby equipment.

b. extremely large and tightly interrelated systems where a single failure incapacitates the entire installation.

c. signaling in the presence of noise where it is either impossible or uneconomical to reduce the effect of the noise on the signal.

These situations are occurring more and more often. The first two are particularly true of large scale digital computing machines, while the third occurs, among other places, in "jamming" situations. КОНЕЦ ЦИТАТЫ.

ПЕРЕВОД. На исследование, приведенное в этой статье, автора натолкнуло рассмотрение крупномасштабных вычислительных машин, в которых необходимо выполнять большое количество операций без единой ошибки в конечном результате. Эта проблема «правильного» выполнения операций в больших масштабах не является принципиально новой; например, в центральном офисе телефонной связи выполняется очень большое число операций, а ошибки, приводящие к неправильным числам, держатся под контролем, хотя они и не были полностью устранены. [...]

В некоторых ситуациях самопроверки недостаточно. Например, в релейных компьютерах модели 5, построенных Bell Telephone Laboratories для Абердинского полигона, наблюдения в ранний период показали, что в 8900 реле двух компьютеров происходило примерно два-три сбоя в день, то есть примерно один сбой на два-три миллиона релейных операций. Благодаря функции самопроверки эти сбои не приводили к необнаруженным ошибкам. Однако, поскольку машины работали без присмотра по вечерам и выходным, ошибки приводили к тому, что вычисления часто прекращались, хотя нередко машины брались за решение новых задач. В настоящее время наблюдается тенденция к использованию электронных скоростей в цифровых компьютерах, где основные элементы несколько надежнее в эксплуатации, чем реле. Однако единичные сбои, даже если они обнаружены, могут серьезно помешать нормальному использованию таких машин.  Поэтому представляется желательным рассмотреть следующий шаг за обнаружением ошибок, а именно исправление ошибок. [...]

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

a. работа без присмотра в течение длительных периодов времени с минимальным количеством резервного оборудования.

b. чрезвычайно большие и тесно взаимосвязанные системы, где один отказ выводит из строя всю установку.

c. передача сигнала в присутствии шума, когда уменьшить влияние шума на сигнал либо невозможно, либо нерентабельно.

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

Источник: R. Hamming. Error detecting and error correcting codes. Bell Syst. Tech. J. 29 (2), 1950. PP. 147-149.

Анализ предложенных решений

Избыточность при передаче информации использовалась для обнаружения ошибок еще до работ Хемминга. Например, одно и то же сообщение передавали дважды, чтобы повысить вероятность его правильного получения. Хемминг также рассматривал уже существовавшие методы контроля ошибок. В частности, это был код 2-5, когда десятичные цифры кодировались последовательностью из 5 битов, содержащей ровно две единицы, а остальные биты были нулями; код 3-7 — это модификация кода 2-5, в которой использовались три единицы и четыре нуля; а также контрольные суммы — когда, например, в конце телеграммы передавалось сообщение о количестве слов.

ЦИТАТА. In transmitting information from one place to another digital machines use codes which are simply sets of symbols to which meanings or values are attached. Examples of codes which were designed to detect isolated errors are numerous; among them are the highly developed 2 out of 5 codes used extensively in common control switching systems and in the Bell Relay Computers,' the 3 out of 7 code used for radio telegraphy, and the word count sent at the end of telegrams. КОНЕЦ ЦИТАТЫ.

ПЕРЕВОД. При передаче информации из одного места в другое цифровые машины используют коды, которые представляют собой просто наборы символов, к которым прикреплены значения или величины. Примеры кодов, которые были разработаны для обнаружения отдельных ошибок, многочисленны; среди них высокоразвитые коды 2-5, широко используемые в общих системах коммутации управления и в компьютерах Bell Relay Computers, код 3-7, используемый в радиотелеграфии, и счетчик слов, отправляемый в конце телеграмм.

Источник: R. Hamming. Error detecting and error correcting codes. Bell Syst. Tech. J. 29 (2), 1950. PP. 147-148.

Также Хемминг использовал избыточность, чтобы корректировать полученные сообщения.

а) Добавление информации о целостности порции сообщения

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

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

Пример: рассмотрим код чисел последовательностью из 7 битов. По формуле Хемминга он будет содержать 3 контрольных и 4 информационных бита. Первый тип располагается на позициях #1, #2 и #4, а другой займет #3, #5, #6 и #7 позиции. Эти 4 бита могут кодировать 16 различных значений.

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

1. Проверяются позиции, где в двоичном представлении номер позиции содержит единицу в первом разряде справа:

• 1 (1)
• 3 (11)
• 5 (101)
• 7 (111)

2. Затем проверяются позиции, где единица стоит во втором разряде справа:

• 2 (10)
• 3 (11)
• 6 (110)
• 7 (111)

3. Далее проверяются позиции, где единица стоит в третьем разряде справа:

• 4 (100)
• 5 (101)
• 6 (110)
• 7 (111)

Каждый контрольный бит проверяет четность единиц в своей группе битов. Если в какой-то группе число единиц нечетное, записывается «1», если четное — «0». Полученное двоичное число указывает на позицию ошибки.

Пример работы алгоритма: рассмотрим число 12, закодированное последовательностью 0111100. 

Информационные биты (на позициях #3, #5, #6, #7) кодируют само число 12: ХХ1Х110. Контрольные биты (#1, #2, #4) выбираются так, чтобы во всех проверках четность соблюдалась. 

Если при передаче сообщение изменилось, то алгоритм Хемминга выявляет ошибку. К примеру, если заменить в этой записи пятый бит с 1 на 0, то получится 0111000. Алгоритм проверяет биты на позициях 1, 3, 5 и 7, чтобы определить, что количество единиц в этих позициях четное. Если это не так, значит, ошибка есть в одной из этих позиций. В данном случае результат проверки: 1, — что означает, что ошибка была обнаружена.

Затем выполняется вторичная проверка битов на позициях 2, 3, 6 и 7 на четность числа единиц. Так как количество единиц в этих позициях четное, ошибок в этих позициях обнаружено не будет. Результат проверки: 0. Общий результат проверки: 01.

Следом выполняется проверка третьего порядка по позициям 4, 5, 6 и 7. Число единиц в этих позициях снова нечетное, что указывает на наличие ошибки в одной из этих позиций. Результат проверки: 1. Общий результат проверки: 101, что соответствует числу 5. Это означает, что ошибка находится в 5-й позиции.

ЦИТАТА. We now determine the positions over which each of the various parity checks is to be applied. The checking number is obtained digit by digit, from right to left, by applying the parity checks in order and writing down the corresponding 0 or 1 as the case may be. Since the checking number is to give the position of any error in a code symbol, any position which has a 1 on the right of its binary representation must cause the first check to fail. Examining the binary form of the various integers we find

1 =       1
3 =     11
5 =   101
7 =   111
9 = 1001
Etc.

have a 1 on the extreme right. Thus the first parity check must use positions

1, 3, 5, 7, 9, ...

In an exactly similar fashion we find that the second parity check must use those positions which have 1's for the second digit from the right of their binary representation,

2 =       10
3 =       11
6 =     110
j =      111
10 = 1010
11 = 1011
Etc., 

the third parity check

4 =        100
5 =        101
6 =        110
7 =        111
12 =    1100
13 =    1101
14 =    1110
15 =    1111
20 = 10100
Etc.

It remains to decide for each parity check which positions are to contain information and which the check. The choice of the positions 1, 2, 4, 8, ... for check positions, as given in the following table, has the advantage of making the setting of the check positions independent of each other. All other positions are information positions. Thus we obtain Table II.

As an illustration of the above theory we apply it to the case of a sevenposition code. From Table I we find for n = 7, m = 4 and k = 3. From Table II we find that the first parity check involves positions 1, 3, 5, 7 and is used to determine the value in the first position; the second parity check, positions 2, 3, 6, 7, and determines the value in the second position; and the third parity check, positions 4,5,6, 7, and determines the value in position four. This leaves positions 3, 5, 6, 7 as information positions. The results of writing down all possible binary numbers using positions 3, 5, 6, 7, and then calculating the values in the check positions 1, 2, 4, are shown in Table III.

Thus a seven-position single error correcting code admits of 16 code symbols. There are, of course, 2⁷ — 16 = 112 meaningless symbols. In some applications it may be desirable to drop the first symbol from the code to avoid the all zero combination as either a code symbol or a code symbol plus a single error, since this might be confused with no message. This would still leave 15 useful code symbols.

As an illustration of how this code "works" let us take the symbol 0 1 1 1 1 0 0 corresponding to the decimal value 12 and change the 1 in the fifth position to a 0. We now examine the new symbol:

0 1 1 1 0 0 0

by the methods of this section to see how the error is located. From Table II the first parity check is over positions 1,3, 5, 7 and predicts a 1 for the first position while we find a 0 there; hence we write a

1 .

The second parity check is over positions 2, 3, 6, 7, and predicts the second position correctly; hence we write a 0 to the left of the 1, obtaining

0 1 .

The third parity check is over positions 4,5,6, 7 and predicts wrongly; hence we write a 1 to the left of the 0 1, obtaining

1 0 1 .

This sequence of 0's and 1's regarded as a binary number is the number 5; hence the error is in the fifth position. The correct symbol is therefore obtained by changing the 0 in the fifth position to a 1. КОНЕЦ ЦИТАТЫ.

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

1 =       1
3 =     11
5 =   101
7 =   111
9 = 1001
И т. д.

имеют 1 в крайнем правом ряду. Таким образом, первая проверка четности должна использовать позиции

1, 3, 5, 7, 9, ...

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

2 =       10
3 =       11
6 =     110
j =      111
10 = 1010
11 = 1011
И т. д.,

третья проверка четности:

4 =        100
5 =        101
6 =        110
7 =        111
12 =    1100
13 =    1101
14 =    1110
15 =    1111
20 = 10100
И т. д.

Остается решить для каждой проверки четности, какие позиции должны содержать информацию, а какие проверку. Выбор позиций 1, 2, 4, 8, ... для позиций проверки, как указано в следующей таблице, имеет то преимущество, что установка позиций проверки не зависит друг от друга. Все остальные позиции являются информационными. Таким образом, мы получаем таблицу II.

В качестве иллюстрации вышеизложенной теории мы применим её к случаю семипозиционного кода. Из таблицы I мы находим, что n = 7, m = 4 и k = 3. Из таблицы II находим, что первая проверка четности включает позиции 1, 3, 5, 7 и используется для определения значения в первой позиции; вторая проверка четности — позиции 2, 3, 6, 7 и определяет значение во второй позиции; третья проверка четности — позиции 4, 5, 6, 7 и определяет значение в четвертой позиции. В качестве информационных позиций остаются позиции 3, 5, 6, 7. Результаты записи всех возможных двоичных чисел с использованием позиций 3, 5, 6, 7, а затем вычисления значений в контрольных позициях 1, 2, 4, показаны в таблице III.

Таким образом, семипозиционный однократный код с коррекцией ошибок состоит из 16 кодовых символов. Разумеется, существует 2⁷ — 16 = 112 бессмысленных символов. В некоторых приложениях может быть желательно исключить первый символ из кода, чтобы избежать нулевой комбинации как кодового символа или кодового символа плюс одна ошибка, так как это может быть спутано с отсутствием сообщения. В этом случае остается 15 полезных кодовых символов.

В качестве иллюстрации того, как этот код «работает», возьмем символ 0 1 1 1 1 1 1 0 0, соответствующий десятичному значению 12, и заменим 1 в пятой позиции на 0. Теперь рассмотрим новый символ:

0 1 1 1 0 0 0

с помощью методов этого раздела, чтобы увидеть, как находится ошибка. Из таблицы II первая проверка на четность проводится по позициям 1, 3, 5, 7 и предсказывает 1 для первой позиции, в то время как мы находим там 0; следовательно, мы пишем

1 . 

Вторая проверка на четность проходит по позициям 2, 3, 6, 7 и правильно предсказывает вторую позицию; следовательно, мы пишем 0 слева от 1, получая

0 1 .

Третья проверка на четность проходит по позициям 4, 5, 6, 7 и предсказывает неверно, поэтому слева от 0 1 пишем 1, получая

1 0 1 .

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

Источник: R. Hamming. Error detecting and error correcting codes. Bell Syst. Tech. J. 29 (2), 1950. PP. 150-153.

б) Минимизация избыточности

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

Он заметил, что если добавить к двоичному коду бит четности, то символы можно расположить в многомерном пространстве, где каждая координата соответствует биту.

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

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

Хемминг вывел математическое неравенство, определяющее минимальное количество контрольных битов в зависимости от количества информационных битов m и требуемого расстояния d. Для случая коррекции одной ошибки (d = 3) формула имеет вид:

2ᵏ ≥ m + k + 1

Для общего случая расстояния неравенство выглядит так:

где С (n, k) обозначает биномиальный коэффициент из n по k.

ЦИТАТА. 

5. A Geometrical Model

When examining various problems connected with error detecting and correcting codes it is often convenient to introduce a geometric model. The model used here consists in identifying the various sequences of 0's and 1's which are the symbols of a code with vertices of a unit n-dimensional cube. The code points, labelled x, y, z, ... , form a subset of the set of all vertices of the cube.

Into this space of 2ⁿ points we introduce a distance, or, as it is usually called, a metric, D(x, y). The definition of the metric is based on the observation that a single error in a code point changes one coordinate, two errors, two coordinates, and in general d errors produce a difference in d coordinates. Thus we define the distance D(x, y) between two points x and y as the number of coordinates for which x and y are different. This is the same as the least number of edges which must he traversed in going from x to y. This distance function satisfies the usual three conditions for a metric, namely,

D(x, y) = 0    if and only if x = y
D(x, y) = D(y, x) > 0    if x ≠ y
D(x, y) + D(y, z) ≥ D(x, z) (triangle inequality).

As an example we note that each of the following code points in the threedimensional cube is two units away from the others,

0  0  1
0  1  0
1  0  0
1  1  1

To continue the geometric language, a sphere of radius r about a point x is defined as all points which are at a distance r from the point x. Thus, in the above example, the first three code points are on a sphere of radius 2 about the point (1, 1, 1). In fact, in this example anyone code point may be chosen as the center and the other three will lie on the surface of a sphere of radius 2.

If all the code points are at a distance of at least 2 from each other, then it follows that any single error will carry a code point over to a point that is not a code point, and hence is a meaningless symbol. This in turn means that any single error is detectable. If the minimum distance between code points is at least three units then any single error will leave the point nearer to the correct code point than to any other code point, and this means that any single error will be correctable. This type of information is summarized in the following table:

Conversely, it is evident that, if we are to effect the detection and correction listed, then all the distances between code points must equal or exceed the minimum distance listed. Thus the problem of finding suitable codes is the same as that of finding subsets of points in the space which maintain at least the minimum distance condition. The special codes in sections 2, 3, and 4 were merely descriptions of how to choose a particular subset of points for minimum distances 2, 3, and 4 respectively. КОНЕЦ ЦИТАТЫ.

ПЕРЕВОД. 

5. Геометрическая модель

При рассмотрении различных проблем, связанных с кодами, обнаруживающими и исправляющими ошибки, часто бывает удобно ввести геометрическую модель. Используемая здесь модель состоит в определении различных последовательностей 0 и 1, которые являются символами кода с вершинами единичного n-мерного куба. Точки кода, обозначенные x, y, z, ... образуют подмножество множества всех вершин куба.

В это пространство из 2ⁿ точек мы вводим расстояние, или, как его обычно называют, метрику, D(x, y). Определение метрики основано на наблюдении, что одна ошибка в кодовой точке изменяет одну координату, две ошибки — две координаты, а в общем случае d ошибок дают разницу в d координатах. Таким образом, мы определяем расстояние D(x, y) между двумя точками x и y как количество координат, для которых x и y различны. Это то же самое, что наименьшее число ребер, которые нужно пройти, чтобы перейти от x к y. Эта функция расстояния удовлетворяет обычным трем условиям для метрики, а именно^

D(x, y) = 0    тогда и только тогда, когда x = y
D(x, y) = D(y, x) > 0    если x ≠ y
D(x, y) + D(y, z) ≥ D(x, z) (неравенство треугольника).

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

0  0  1
0  1  0
1  0  0
1  1  1

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

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

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

Источник: R. Hamming. Error detecting and error correcting codes. Bell Syst. Tech. J. 29 (2), 1950. PP. 154-156.

Из каких областей знаний были заимствованы идеи

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

Факторы, обеспечившие реализацию решений

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

Бернард Оливер, Клод Шеннон и Джон Р. Пирс— The Philosophy of PCM («Принципы кодово-импульсной модуляции», 1948)

Описание проблемы

Книга «Принципы кодово-импульсной модуляции» была результатом совместных трудов ученых и инженеров. В том числе, Клода Шеннона, о котором мы поговорим отдельно в следующем разделе. В 1948 году он и его коллеги обобщили ряд идей своих предшественников, а также собственные разработки, объединив их в единую теорию кодово-импульсной модуляции (PCM, Pulse Code Modulation).

Проблема, которую они решали, берет начало во времена Второй мировой войны. Перед инженерами стояла задача разработать способ передачи телефонных сигналов по линиям связи так, чтобы их невозможно было расшифровать в случае перехвата. Эта задача стала основой проекта «Проект Х», запущенного в 1940 году. Основные требования к системе заключались в следующем: 

• Закодировать аналоговый сигнал на передающей стороне
• Передать его по линии связи
• Расшифровать сигнал на принимающей стороне с учетом возможных шумов и помех

Клод Шеннон сосредоточился только на аспекте восстановления сигнала при низком соотношении «сигнал – шум».

ЦИТАТА. 

4.3 Project X—A True Secrecy System for Speech

4.3.1 Introduction

One of the more closely guarded projects in World War II, and for years thereafter, was known simply as "Project X." It concerned the origination and development of a completely secret speech enciphering and transmission system, which by its nature could not possibly be deciphered by other than its intended receiver. To the people who worked on it, it was known as the "X System." To the people in the Signal Corps who handled the system, it was most generally known as "Sigsaly" or "Ciphony I," and to the people in the telephone and radio transmission centers who handled its inviolate trunk circuits and were curious about its function, it was nicknamed the "Green Hornet" because the audible control tones were similar to the signature theme of a well-known radio program.

While the project was important as the initial development of a completely secret speech transmission system, historically it was also important as the pioneering digital speech transmission system employing a form of pulse code modulation. It was one of the starting points of the digital transmission age that followed. [...]

4.3.2 Invention

During the first two or three months following the inception of the project in October 1940, a large part of the thinking and experimentation reflected earlier thinking on speech privacy. There was no lack of ideas. A search by the Patent Department at the time uncovered about 80 patents But all of these methods invariably had one fault in common: they were just complex ways of transmitting speech that a person could undo with the necessary equipment and enough time. These were privacy, not secrecy, systems. In a secrecy system it is assumed that an eavesdropper having the same equipment as the intended receiver cannot determine the message unless he knows the coding sequence. КОНЕЦ ЦИТАТЫ.

ПЕРЕВОД. 

4.3 Проект X — Система истинной секретности речи

4.3.1 Введение

Один из наиболее тщательно охраняемых проектов во время Второй мировой войны и в течение многих лет после неё был известен просто как «Проект X». Он касался создания и разработки совершенно секретной системы шифрования и передачи речи, которая по своей природе не могла быть расшифрована никем, кроме её адресата. Людям, которые над ним работали, он был известен как «Система Х». Людям в Корпусе связи, которые работали с этой системой, она была известна как «Сигсали» или «Сифони I», а людям в телефонных и радиопередающих центрах, которые работали с её неприкосновенными магистральными цепями и интересовались ее функциями, она была прозвана «Зеленым шершнем», потому что звуковые сигналы управления были похожи на сигнальную тему известной радиопрограммы.

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

4.3.2 Изобретение

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

Источник: M. D. Fagen. A History of Engineering and Science in the Bell System: National Science in War and Peace (1925-1975). Bell Telephone Laboratories, 1978. PP. 296-299.

Анализ предложенных решений

а) Представление сигнала в виде последовательности дискретных значений

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

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

ЦИТАТА. In early January 1941, both R. C. Mathes and R. K. Potter discussed the adding of random noise signals in the syllabic range to the control signals of the vocoder, with the thought of using the same noise signals in opposite polarity to remove the masking at the receiving end. But it became clear that unless a large ratio of noise to signal were used the presence of speech signals would be apparent, and that if large amounts were used it would be at least difficult, and probably impossible, to balance out.

At this point, a letter was received from W. G. Radley, of the British Post Office, requesting design information 26 on the vocoder and hinting that it was to be used in a secrecy system. This acted as a stimulus to the brainstorming that was going on at Bell Labs. Incidentally, the information that was sent to the British was sunk by submarine attack and had to be forwarded a second time.

As mentioned above, the outstanding example of a perfect ciphering system was the Vernam system 27 used on telegraph signals. It involved the addition of a random or non repeating set of on-off telegraph signals to the message signals by a process now called Modulo 2 addition, or, more commonly, "half-adding." The Vernam process as used with teletypewriters is illustrated in Fig. 5-4. To readers trained· in logic, Fig. 5-32 may provide an explanation in more familiar terms. In this diagram the on-off (0, 1) values of a possible telegraph message and a key are shown in lines (a) and (b). The Modulo 2 addition of the two signals is shown in (c). It will be noted that if the sum of the message and the key do not exceed 1, the sum of the two values is obtained. If the sum is equal to 2 (M = 1 and K =1), a 0 is substituted. This means that if the message value is 0, either 0 or 1 can result, depending on the key value; likewise, if the message is 1, then 1 or Ocan result. Hence, if the key has a random occurrence of values, it will result in a transmitted message that is also random and cannot be undone unless a copy of the key tape is available. With this tape at hand, the key signals can be added to the transmitted signal to provide the original message. The feeling that this same sort of process was necessary in communicating speech was a constant nagging thought with people who were working on the problem.

Finally, in late February, the first real breakthrough resulted from a proposal by R. K. Potter 28 that the individual vocoder channels be treated as on-off channels by the use of a relay with a suitably adjusted bias. This solved the problem of adding the key, as in the Vernam approach, but experiments in the vocoder by 0. 0. Gruenz soon indicated that the quality and intelligibility of vocoder speech was badly mutilated. The next obvious step was to use two relays adjusted to different values in each channel to improve the quality; while there was some improvement with this move, it was becoming apparent that quite a number of step values were needed to get the quality that might be acceptable. This approach will be recognized as the process now known as quantization — i.e., representing a continuously variable signal by means of a series of steps which approximate the continuous function. It is interesting to note that up to the point of using two or more steps per channel, the rationale called for treating the on-off pattern of the 10 vocoder channels as a telegraph character. The addition of the N-level dimension in each channel shook the thinking loose from this mooring. КОНЕЦ ЦИТАТЫ.

ПЕРЕВОД. В начале января 1941 года Р. К. Матес и Р. К. Поттер обсуждали добавление случайных шумовых сигналов в слоговом диапазоне к управляющим сигналам вокодера, с мыслью использовать те же шумовые сигналы с противоположной полярностью для устранения маскировки на приемной стороне. Но стало ясно, что если не использовать большое соотношение шума и сигнала, то присутствие речевых сигналов будет очевидным, а если использовать большое количество, то выровнять баланс будет как минимум трудно, а возможно и невозможно.

В этот момент было получено письмо от У. Г. Рэдли из британского почтового ведомства с просьбой предоставить информацию о конструкции вокодера и намеком на то, что он будет использоваться в системе секретности. Это послужило стимулом для мозгового штурма, который проводился в Bell Labs. Кстати, информация, отправленная британцам, была потоплена в результате атаки подводной лодки, и ее пришлось пересылать во второй раз.

Как уже упоминалось выше, выдающимся примером совершенной системы шифрования была система Вернама, использовавшаяся для телеграфных сигналов. Она включала в себя добавление к сигналам сообщения рандомного или неповторяющегося набора телеграфных сигналов по принципу, который сейчас называется сложением по модулю 2, или, чаще, «половинным добавлением». Процесс Вернама, используемый в телетайпах, показан на рис. 5-4. Для читателей, подкованных в логике, рис. 5-32 может дать объяснение в более привычных терминах. На этой диаграмме в линиях (a) и (b) показаны значения включения-выключения (0, 1) возможного телеграфного сообщения и ключа. Сложение этих двух сигналов по модулю 2 показано в (c). Отметим, что если сумма сообщения и ключа не превышает 1, то получается сумма двух значений. Если сумма равна 2 (М = 1 и К =1), то проставляется 0. Это означает, что если значение сообщения равно 0, то в зависимости от значения ключа может получиться либо 0, либо 1; аналогично, если сообщение равно 1, то получится 1 или 0. Следовательно, если ключ имеет случайную комбинацию значений, то в результате будет передано сообщение, которое также является случайным и не может быть отменено, пока не будет доступна копия ключевой ленты. Имея под рукой эту ленту, сигналы ключа могут быть добавлены к переданному сигналу, чтобы получить оригинальное сообщение. Чувство, что такой же процесс необходим для передачи речи, постоянно не давало покоя людям, работавшим над этой проблемой.

Наконец, в конце февраля первый реальный прорыв был достигнут благодаря предложению Р. К. Поттера о том, чтобы отдельные каналы вокодера рассматривались как каналы включения-выключения с помощью реле с соответствующим образом настроенным смещением. Это решило проблему добавления ключа, как в подходе Вернама, но эксперименты с вокодером Груенца вскоре показали, что качество и разборчивость речи вокодера были сильно искажены. Следующим очевидным шагом было использование двух реле, настроенных на разные значения в каждом канале для улучшения качества; хотя при таком подходе наблюдалось некоторое улучшение, становилось очевидным, что для получения приемлемого качества необходимо довольно большое количество значений шага. Этот подход будет известен как квантование — т.е. представление непрерывно изменяющегося сигнала с помощью серии шагов, которые приближают непрерывную функцию. Интересно отметить, что до момента использования двух или более шагов на канал, обоснование требовало рассматривать схему включения-выключения 10 каналов вокодера как телеграфный символ. Добавление N-уровневого измерения в каждом канале освободило мышление от этой привязки.

Источник: M. D. Fagen. A History of Engineering and Science in the Bell System: National Science in War and Peace (1925-1975). Bell Telephone Laboratories, 1978. PP. 296-299.

ЦИТАТА. Невозможно, конечно, передать тонкое мгновенное значение. Мгновенное значение сигнала передается часто как высота импульса или как его положение во времени. Помехи, искажения и взаимное влияние импульсов изменяют высоту и положение и вносят ошибку в полученную информацию о величине отсчета. Обычно ошибка возрастает по мере того, как сигнал усиливается последовательными повторителями, и накопление шума кладет предел расстоянию, на которое сигнал может быть передан даже при наличии достаточного усиления. Возможно, впрочем, ограничиться только некоторыми дискретными уровнями высоты или положения передаваемого импульса. Тогда при взятии отсчета должен передаваться уровень, ближайший к истинному. После приема и усиления мы получим уровень, немного отличающийся от какого-либо из установленных. Если помехи и искажения не слишком велики, мы можем с уверенностью сказать, какой именно уровень сигнал должен был бы иметь. После этого сигнал может быть заново сформирован или может быть создан новый сигнал, имеющий снова первоначально переданный уровень. 

Представление сигнала некоторыми установленными дискретными уровнями называется квантованием. Оно неизбежно вносит ошибку в определение величины отсчетов и порождает шум квантования. Но если сигнал находится в квантованном состоянии, он может передаваться на любое расстояние без дальнейшей потери качества, если только добавочный шум в сигнале, принимаемом каждым повторителем, не настолько велик, чтобы нельзя было распознать правильный уровень каждого данного сигнала. Квантование сокращает наш «алфавит». Если принятый сигнал лежит между a и b и ближе, скажем, к b то мы считаем, что передано b, Если шум достаточно мал, мы всегда будем правы. КОНЕЦ ЦИТАТЫ.

Источник: Б. М. Оливер, Дж. Р. Пирс, К. Е. Шеннон. Принципы кодово-импульсной модуляции. // Теория информации и её приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 38.

б) Кодирование последовательности дискретных значений

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

ЦИТАТА. Квантованный отсчет может быть передан в виде одиночного импульса, имеющего либо некоторую возможную дискретную высоту, либо некоторое дискретное положение по отношению к исходному положению. Однако, если требуется большое количество различных высот, например сто, то затруднительно сделать схемы, способные отличить их друг от друга. С другой стороны, очень легко осуществить схему, которая отличала бы наличие импульса от его отсутствия. Положим, далее, что несколько импульсов образуют кодовую группу для обозначения отдельного отсчета. Каждый импульс может быть налицо (1) или отсутствовать (0). Если взять три импульса, то можно составить комбинации, приведенные в следующей таблице: 

Кодовые обозначения представляют собой по существу числа, записанные в двоичной системе. В этой системе разряды соответствуют числам 1, 2, 4, 8, т. е. единица в первом разряде изображает 1, единица во втором разряде изображает 2, единица в третьем разряде изображает 4 и т. д. Мы видим, что кодовыми группами из n двоичных («да — нет») импульсов мы можем представить 2ⁿ значений. Например, семь импульсов дают 128 уровней отсчета. 

Возможно, конечно, кодировать мгновенное значение при помощи некоторого количества импульсов, которым присвоены величины 0, 1, 2 (основание 3; троичный код) или 0, 1, 2, 3 (основание 4; четверичный код) и т. д., вместо импульсов с присвоенными величинами 0, 1 (основание 2; двоичный код). Если бы импульсу были присвоены десять уровней, то каждый импульс в кодовой группе представлял бы собой просто цифру в обычном десятичном числе, выражающем мгновенное значение сигнала. Если n есть число импульсов в группе, а b — основание, то число квантованных уровней, могущих быть представленными кодом, есть bⁿ. КОНЕЦ ЦИТАТЫ.

Источник: Б. М. Оливер, Дж. Р. Пирс, К. Е. Шеннон. Принципы кодово-импульсной модуляции. // Теория информации и её приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 38-39.

ЦИТАТА. A problem developed, however, in the transmission of the pitch signal of the vocoder, which turned out to be much more susceptible to the quantizing effect. Experiments soon indicated that it was going to need some 30 or more steps. The thought of uHing five channels to transmit this signal was not easy to accept. Shortly thereafter, a suggestion was made by R. H. Badgley and R. L. Miller to use a technique which was likened to a vernier. The pitch signal would first be quantized to the nearest of the six levels, and then this value would be subtracted from the original signal. The remainder was then coded again to six levels. КОНЕЦ ЦИТАТЫ.

ПЕРЕВОД. Однако возникла проблема при передаче сигнала высоты тона вокодера, который оказался гораздо более восприимчивым к эффекту квантования. Эксперименты вскоре показали, что для этого потребуется около 30 или более ступеней. Мысль об использовании пяти каналов для передачи этого сигнала было нелегко принять. Вскоре после этого было выдвинуто предложение Р. Х. Бэджли и Р. Л. Миллера использовать технику, которая была подобно верньеру. Сигнал высоты тона сначала квантуется до ближайшего из шести уровней, а затем это значение вычитается из исходного сигнала. Затем остаток снова кодировался до шести уровней.

Источник: M. D. Fagen. A History of Engineering and Science in the Bell System: National Science in War and Peace (1925-1975). Bell Telephone Laboratories, 1978. PP. 304.

в) Разделение передачи кодированных значений

Закодированные значения передавались либо последовательно в разные промежутки времени по одному и тому же каналу, либо параллельно по разным каналам связи.

ЦИТАТА. Кодовые группы затем передаются либо в виде временной последовательности импульсов (временное разделение) по одному и тому же каналу, либо путем частотного разделения, либо по раздельным каналам. КОНЕЦ ЦИТАТЫ.

Источник: Б. М. Оливер, Дж. Р. Пирс, К. Е. Шеннон. Принципы кодово-импульсной модуляции. // Теория информации и её приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 40.

г) Восстановление исходного сообщения из «набора образцов»

На принимающей стороне восстановление сигнала затруднялось наличием шумов. Однако Шеннон, опираясь на ранние исследования Гарри Найквиста, доказал, что для точного восстановления сигнала ограниченной полосы частот достаточно дискретизировать его с частотой, вдвое превышающей максимальную частоту исходного сигнала.

ЦИТАТА. Назначением системы передачи является, вообще говоря, воспроизведение на выходе системы некоторой функции времени, заданной на входе. Во всякой реальной системе приходится иметь дело только с определенным классом функций, а именно с функциями с ограниченным спектром. Сигнал, не содержащий частот выше W₀, не может представляться бесконечным числом независимых значений в секунду. может в действительности представляться в точности 2W₀ независимыми значениями в секунду, и совокупность значений, отстоящих друг от друга во времени на t₀ секунд, где t₀ = 1/(2W₀), определяет сигнал полностью. Простое доказательство этого дано в приложении I. Итак, чтобы передать сигнал с ограниченным спектром длительностью T, не требуется передавать полностью всю непрерывную функцию времени. Достаточно передать конечную совокупность 2W₀T независимых величин, получаемых путем отсчета мгновенных значений сигнала с постоянной скоростью 2W₀ отсчетов в секунду. 

Если читателю покажется удивительным, что 2W₀T отдельных данных описывают полностью непрерывную функцию на интервале 7, то следует напомнить, что достаточно 2W₀T синусных и косинусных коэффициентов ряда Фурье, которым может быть представлена наша функция, принимая во внимание, что она не содержит частот выше W₀. КОНЕЦ ЦИТАТЫ.

Источник: Б. М. Оливер, Дж. Р. Пирс, К. Е. Шеннон. Принципы кодово-импульсной модуляции. // Теория информации и её приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 36-37.

Побочные результаты

Развитие PCM привело к нескольким важным открытиям. Кодово-импульсная модуляция позволяла изменять ширину полосы передачи, тем самым улучшая соотношение «сигнал – шум». В отличие от амплитудной и частотной модуляции, PCM давала возможность минимизировать потери качества сигнала при передаче. Хотя это не было главной целью исследования, полученные результаты оказались полезными для дальнейшего развития теории информации.

ЦИТАТА. КИМ дает большее увеличение отношения сигнал/шум, чем другие системы, вроде ЧМ, также использующие широкую полосу. При применении двоичной («да — нет») КИМ сигнал высокого качества может быть получен в таких плохих условиях в смысле шума и помех, что едва возможно распознать наличие каждого импульса. Более того, при применении восстанавливающих повторителей, обнаруживающих наличие или отсутствие импульса, а затем излучающих импульсы исправленной формы и с надлежащим расположением во времени, первоначальное отношение сигнал/шум может быть сохранено на протяжении длинной цепи повторителей. 

КИМ естественно ведет к многоканальной системе с временным разделением. 

КИМ не дает увеличения отношения сигнал/шум в условиях сильного сигнала или малого шума. 

КИМ передатчики и приемники несколько сложнее, чем применяемые при других видах модуляции. 

В общем представляется, что КИМ идеальным образом подходит для многоканальных систем связи, в которых требуется стандартное качество и высокая надежность. КОНЕЦ ЦИТАТЫ.

Источник: Б. М. Оливер, Дж. Р. Пирс, К. Е. Шеннон. Принципы кодово-импульсной модуляции. // Теория информации и её приложения. Под ред. А. А. Харкевича. М.: Государственное издательство физико-математической литературы, 1959. C. 53.

Из каких областей знаний были заимствованы идеи

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

Хотя сама книга мало уделяла внимания методам шифрования, ее идеи основывались на работах Шеннона в области криптографии и теории секретных систем.

Благодаря чему стали возможны ходы

«Квантование» аналогового сигнала стало логичным шагом, так как прототип этого метода уже существовал в телеграфной передаче сообщений.

Важную роль сыграли исследования Найквиста, который еще в 1928 году в работе Certain Topics in Telegraph Transmission Theory показал, что для точного восстановления сигнала достаточно отбирать его дискретные значения с частотой, вдвое превышающей максимальную частоту сигнала. Его выводы, основанные на разложении Фурье, стали теоретическим фундаментом PCM.

Клод Шеннон — The Mathematical Theory of Communication («Математическая теория связи», 1948)

Описание проблемы

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

Первая — определить фундаментальные ограничения кодирования информации

ЦИТАТА. С точки зрения логики теория кодирования приводит к теории информации, и теория информации определяет границы того, что можно достичь подходящим методом кодирования информации. Таким образом, обе теории тесно связаны между собой, хотя в прошлом их развитие шло в значительной мере независимо. КОНЕЦ ЦИТАТЫ.

Источник: Р. В. Хэмминг. Теория кодирования и теория информации. М.: Радио и связь, 1983. C. 6.

Вторая — предложить наиболее эффективные методы кодирования информации

ЦИТАТА. Shannon told me recently that he had been working toward information theory as early as 1940, when he was a National Research Fellow at Princeton. Although we worked in quite different fields, I saw Shannon frequently after the war, during the gestation of information theory at Bell Laboratories. When he visited my office I asked him if he had proved any new theorems; if he had, I asked him to write them down in a notebook (alas, the notebook has been lost, but there were few theorems in it). I cannot really give any details of the progress of communication theory in Shannon’s mind. I do remember lots of talk about pulse code modulation and digital transmission, and criteria sometimes wrong-for optimizing these. In the end, The Mathematical Theory of Communication, and the book based on it came as a bomb, and something of a delayed-action bomb. КОНЕЦ ЦИТАТЫ.

ПЕРЕВОД. Недавно Шеннон сказал мне, что он работал над теорией информации еще в 1940 году, когда был национальным научным сотрудником в Принстоне. Хотя мы работали в совершенно разных областях, я часто видел Шеннона после войны, во время становления теории информации в Bell Laboratories. Когда он приходил ко мне в офис, я спрашивал его, доказал ли он какие-нибудь новые теоремы; если да, то просил записать их в блокнот (увы, блокнот был утерян, но теорем в нем было немного). Я не могу подробно рассказать о том, как развивалась теория связи в сознании Шеннона. Я помню много разговоров о импульсно-кодовой модуляции и цифровой передаче, а также критерии, иногда ошибочные, для их оптимизации. В конце концов, «Математическая теория связи» и основанная на ней книга стали бомбой, причем бомбой замедленного действия.

Источник: J. R. Pierce. The Early Days of Information Theory. IEEE Transactions on Information Theory. Vol. IT-19, 1. January 1973.

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

Анализ предложенных решений

Для выявления ограничений и взаимосвязей параметров кодирования Шеннон использовал математический аппарат и новые определения величин, что позволило ему доказать ключевые теоремы.

а) Введение статистической компоненты в составляющую информации

Согласно Шеннону, информация представляет собой последовательность вероятных выборов из конечного набора сообщений. Например, при составлении предложения человек может выбрать любое слово из словаря, но выбор второго слова часто зависит от первого, третьего — от первых двух и так далее. Аналогичные зависимости существуют между буквами в словах и целыми предложениями.

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

ЦИТАТА. Рассмотрим теперь источник с щений. Как следует математически описывать источник сообщений и какое количество информации, измеряемое числом битов в секунду, создается данным источником? Главная сторона этого вопроса заключается в использовании статистических сведений об источнике для уменьшения пропускной способности канала путем применения надлежащего метода кодирования информации. В телеграфии, например, сообщения, которые должны быть переданы, состоят из последовательностей букв. Эти последовательности, однако, не являются вполне случайными. Вообще говоря, они образуют фразы и имеют статистическую структуру, скажем, английского языка. Буква Е встречается чаще, чем Q; последовательность ТН чаще, чем ХР, и т. д.

Наличие такой структуры позволяет получить некоторую экономию времени (или пропускной способности канала) с помощью подходящего кодирования сообщений в последовательности сигналов. В ограниченных пределах это уже делается в телеграфии путем использования наиболее короткого символа в канале — точки — для наиболее распространенной в английском языке буквы Е, в то время как редко встречающиеся буквы Q, Х, Z представляются более длинными последовательностями точек и тире. Этот принцип проводится еще дальше в некоторых коммерческих кодах, где наиболее употребительные слова и фразы представляются четырех- или пятибуквенными кодовыми группами, что дает значительную экономию среднего времени. В стандартизированных и поздравительных телеграммах, используемых в настоящее время, этот принцип развивается еще дальше. Там проводится кодирование одного или двух предложений в относительно короткую последовательность цифр. 

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

1. Печатные тексты на таких языках, как английский, немецкий, китайский. 

2. Непрерывные источники сообщений, которые превращены в дискретные с помощью некоторого процесса квантования. Например, квантованная речь из ИКМ-передатчика или квантованный телевизионный сигнал. 

З. Математические случаи, когда просто определяется абстрактно некоторый вероятностный процесс, который порождает последовательность символов. КОНЕЦ ЦИТАТЫ.

Источник: К. Шеннон. Работы по теории информации и кибернетике. М.: Издательство иностранной литературы, 1963.  C. 250-251. 

б) Определение меры информации как производной функции от количества и вероятности событий

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

Например, если все символы сообщения представляют собой одну и ту же букву (например, «ААААААА»), то вероятность появления следующего символа «А» равна 1, а всех остальных — 0. В таком случае мера информации равна 0, так как сообщение не несет новой информации для получателя.

ЦИТАТА. Предположим, что имеется некоторое множество возможных событий, вероятности осуществления которых суть р₁, р₂, .., рₙ. Эти вероятности известны, но это — все, что нам известно относительно того, какое событие произойдет. Можно ли найти меру того, насколько велик «выбор» из такого набора событий или сколь неопределен для нас его исход?

Если имеется такая мера, скажем H(р₁, р₂, .., рₙ), то разумно потребовать, чтобы она обладала следующими свойствами: 

1. Н должна быть непрерывной относительно рᵢ.

2. Если все рᵢ, равны, рᵢ = 1/n, то Н должна быть монотонно возрастающей функцией от n. В случае равновероятных событий имеется больше возможностей выбора или неопределенности, чем в случае, когда имеются равновероятные события.

3. Если бы выбор распадался на два последовательных выбора, то первоначальная Н должна была бы быть взвешенной суммой индивидуальных значений Н. [...] 

Т е о р е м а 2. Существует единственная функция H, удовлетворяющая трем перечисленным выше свойствам. При этом H имеет вид

где К — некоторая положительная константа. КОНЕЦ ЦИТАТЫ.

Источник: К. Шеннон. Работы по теории информации и кибернетике. М.: Издательство иностранной литературы, 1963.  C. 259-260.

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

ЦИТАТА. 3. Пусть имеются два события х и у с m исходами для первого и n исходами для второго. Пусть p(i,j) означает вероятность совместного осуществления исхода i для х и ј для у. Энтропия совместного события равна 

в то время как 

Легко показать, что 

причем равенство имеет место только в том случае, когда события независимы [т. е. p(i, j) = p(i)*p(j)]. Неопределенность совместного события меньше или равна сумме неопределенностей отдельных событий. КОНЕЦ ЦИТАТЫ.

Источник: К. Шеннон. Работы по теории информации и кибернетике. М.: Издательство иностранной литературы, 1963.  C. 262.

ЦИТАТА.Определим условную энтропию Нₓ(у) величины у как величину, получаемую в результате осреднения энтропии у, вычисленной по всем значениям х, с весами, соответственно равными вероятностям этих значений х. Таким образом, 

Эта величина показывает, какова в среднем неопределенность значения у, когда известно значение х. Подставляя значение pᵢ(j) , получим 

Или

Неопределенность (или энтропия) совместного события (х, у) равна неопределенности события х плюс неопределенность события у, когда х известно.

6. Из п. З и 5 имеем 

Отсюда 

Неопределенность события у не возрастает от того, что событие х становится известным. Она уменьшается, если только события х и у не являются независимыми. В противном случае она не изменяется. КОНЕЦ ЦИТАТЫ.

Источник: К. Шеннон. Работы по теории информации и кибернетике. М.: Издательство иностранной литературы, 1963.  C. 263.

В завершение он определил энтропию источника как условную энтропию всех его символов.

в) Вывод ограничений на основе теорем и доказательств из ранее определенных мер

Шеннон сформулировал две фундаментальные теоремы, определяющие ограничения передачи информации.

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

ЦИТАТА. Подтвердим теперь нашу интерпретацию величин Н как скорости создания информации доказательством того факта, что Н определяет пропускную способность канала, необходимую при наиболее эффективном кодировании. 

Т е о р е м а 9. Пусть источник имеет энтропию Н (бит на символ), а канал имеет пропускную способность С (бит в секунду). Тогда можно закодировать сообщения на выходе источника таким образом, чтобы передавать символы по каналу со средней скоростью С/Н — е символов в одну секунду, где е — сколь угодно мало. Передавать со средней скоростью, большей чем C/H, невозможно. 

Обратная часть теоремы, утверждающая, что нельзя превзойти скорость C/H, может быть доказана, если заметить, что энтропия в секунду на входе канала равна энтропии источника, так как передатчик должен быть невырожденным преобразователем, и что эта энтропия не может превосходить пропускной способности канала. Отсюда Н'≤С и число символов в секунду равно Н'/Н≤С/H. КОНЕЦ ЦИТАТЫ.

Источник: К. Шеннон. Работы по теории информации и кибернетике. М.: Издательство иностранной литературы, 1963.  C. 270. 

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

ЦИТАТА. Т е о р е м а 11. Пусть дискретный канал обладает пропускной способностью С, а дискретный источник — энтропией в секунду Н. Если Н≤С, то существует такая система кодирования, что сообщения источника могут быть переданы по каналу с произвольно малой частотой ошибок (или со сколь угодно малой ненадежностью). Если Н>С, то можно источник таким образом, что ненадежность будет меньше чем Н — С + е, где е сколь угодно мало. Не существует способа кодирования, обеспечивающего ненадежность, меньшую чем Н — С. КОНЕЦ ЦИТАТЫ.

Источник: К. Шеннон. Работы по теории информации и кибернетике. М.: Издательство иностранной литературы, 1963.  C. 281.

Из каких областей знаний были заимствованы идеи

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

Факторы, обеспечившие реализацию решений

Развитие теории информации стало возможным благодаря двум ключевым этапам в изучении передачи данных:

• Разработка методов измерения информации и увеличения скорости ее передачи. Исследования Найквиста и Хартли сыграли важную роль в понимании ограничений на передачу данных.
• Распознание шума как неотъемлемой части передачи информации и разработка методов его устранения. На физическом уровне борьба с шумами велась с помощью кодово-импульсной модуляции (PCM), разработанной коллективом ученых. На логическом уровне для коррекции ошибок применялось кодирование с исправлением ошибок, предложенное Ричардом Хеммингом.

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

Выводы: анализ развития ключевых концепций и их влияния на становление теории информации

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

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

Обе работы были сосредоточены на измерении информации и способах её передачи через каналы с ограниченной пропускной способностью.

Влияние шумов и методы их устранения

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

Открытие кодово-импульсной модуляции (PCM)

Ранее существовавшие методы модуляции — амплитудная (AM) и частотная (FM) — не обеспечивали достаточной защиты от шумов. Амплитудная модуляция (AM) увеличивала уровень шума пропорционально увеличению амплитуды сигнала. Частотная модуляция (FM) эффективно боролась с шумами, но только в том случае, если частота передачи значительно превышала частоту исходного сигнала.

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

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

Изобретение кодирования с возможностью самокоррекции (код Хемминга)

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

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

Роль Клода Шеннона в формировании теории информации

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

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

Автор статьи – Владимир Куценко
Литературные редакторы – Захар Федин, Марат Каюмов
Иллюстрации – издательство «Ливрезон», при использовании обложки статьи использовалась нейросеть DALL-E

Сильные разработки создаются не в одиночку, а в коллективе. LIVREZON CLUB объединяет более 50-ти коллективов в разных отраслях научного знания. В ежедневном режиме они делятся опытом, собирают новые данные, пишут книги и статьи, тестируют технологии и получают друг от друга полезную обратную связь. 

Хотите присоединиться к коллективу разработчиков? Пишите на info@livrezon.com

ЧТО ТАКОЕ БАЗА ЗНАНИЙ?

Концентрированная книга издательства LIVREZON складывается из сотен и тысяч проанализированных источников литературы и масс-медиа. Авторы скрупулёзно изучают книги, статьи, видео, интервью и делятся полезными материалами, формируя коллективную Базу знаний. 

Пример – это фактурная единица информации: небанальное воспроизводимое преобразование, которое используется в исследовании. Увы, найти его непросто. С 2017 года наш Клуб авторов собрал более 80 тысяч примеров. Часть из них мы ежедневно публикуем здесь. 

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

📎 База знаний издательства LIVREZON – только полезные материалы.