2015-06-04
350
1924 г. – определение логарифмической меры количества информации для многоуровневой телеграфии (Г. Найквист);
1925 г. – экспериментально-теоретическое исследование атмосферных радиопомех как потока случайных импульсов (Дж. Карсон);
1927 г. – экспериментально-теоретическое исследование тепловых эле-ктрических шумов резисторов (Дж. Джонсон, Г. Найквист);
1928 г. – определение логарифмической меры количества информации в знаковых системах и качественная оценка скорости передачи информации в каналах без шумов (Р. Хартли);
1928 г. – установление предельно достижимой скорости телеграфирования в отсутствие помех (Г. Найквист);
1930 г. – разработка «нерасшифровываемого» кода (Г. Вернем, Дж. Маборн);
1932 г. – исследование модели гауссовских шумов как совокупности случайных синусоид (Г. Найквист);
1940 г. – «переоткрытие» теоремы отсчётов В. А. Котельникова и асимптотическая оценка пропускной способности канала с шумами (К. Шеннон);
1942 г. – разработка общей теории случайных шумов и их преобразований в электрических цепях (С. Райс);
|
|
|
1948 г. – разработка кода, обнаруживающего и исправляющего одну ошибку в пачке из 7 элементарных посылок (Р. Хэмминг);
1948 г. – разработка теории информации (К. Шеннон);
1949 г. – разработка теории криптографии (К. Шеннон);
1940-1950 гг. – разработка шести моделей ЭВМ.
Это был «серебряный век» Белловских лабораторий – при наличии в них свободного творческого климата. Например, К. Шеннон спокойно разъезжал по длинным коридорам БТЛ на одноколёсном велосипеде и занимался решением тех научных задач, которые захватывали его сознание на данное время.
С 1950 г. финансирование научно-исследовательских работ в БТЛ сущест-
венно сократилось, а научные исследования приобрели сугубо прикладной характер, стали строго регламентироваться и по-бюрократически жёстко планироваться.
Интересно и поучительно проследить, как зарождались и логически развивались основные понятия прикладной теории информации в Белловских телефонных лабораториях в период «серебряного века» БТЛ.
В 1924 г. Гарри Найквист опубликовал работу «Некоторые факторы, влияющие на скорость телеграфирования», в которой он показал следующее ([54], p. 332-333): «Скорость, с которой сообщение может передаваться по телеграфной линии, имеющей заданную... частоту следования элементарных сигналов, может быть определена приблизительно следующей формулой... W = K log m, где W – скорость передачи сообщения, m – число уровней тока [используемых для телеграфии – Г. Х.], а K – константа». Другими словами, скорость передачи сообщений (Найквист использует термин “intelligence”, а не многозначный термин “information”) при многоуровневой двуполярной телеграфии с элементарными посылками одинаковой длительности τэ пропорциональна логарифму количества «чётко различимых уровней» телеграфирования.
|
|
|
Это была первая попытка решения Проблемы № 3. При этом Найквист ясно осознал разделение формирующейся прикладной теории информации на информационную статику (логарифм числа «чётко различимых уровней») и информационную динамику (константа K).
На с. 343 Г. Найквист добавляет, что чтобы установить формулу для случая неравных длительностей телеграфных знаков (литер), необходимо принять во внимание относительную частотность различных литер.
В статье [54] 1928 г. Найквист выясняет вопрос о максимально возможном значении K в формуле W = K log m, которое ограничивается (в отсутствие помех) конечностью полосы пропускания телеграфной линии, рассматриваемой Найквистом как фильтр нижних частот с «частотой среза» B. Он отмечает, что обычно телеграфная посылка – прямоугольный импульс тока длительностью τэ. На выходе телеграфной линии, из-за ограничения величины B, посылка «расплывается» и интерферирует с последующей посылкой. Поэтому следующую посылку приходится отправлять тогда, когда на приёмном телеграфном аппарате практически уже затухли переходные процессы.
Найквист предлагает использовать в качестве элементарной посылки сигнал с равномерным, в пределах полосы частот [0, B ], спектром – нереализуемый сигнал вида s (t) = sin (at)/(at) – и синтезирует физически реализуемый сигнал, моменты пересечения нулевого уровня которого наступают через промежутки времени, равные τэ. Это позволяет обеспечить предельно достижимую (в отсутствие помех) скорость телеграфирования W макс = 2 B. Отметим, что математические вопросы синтеза физически реализуемых сигналов и фильтров были решены А. Н. Колмогоровым и Н. Винером 10-15 лет спустя.
Он также пишет: «... если посылать 2 N различных значений тока в секунду, то все синусоидальные составляющие сигнала с частотами выше N окажутся избыточными в том смысле, что для восстановления посланного сигнала эти составляющие необязательны». Это – предвосхищение теоремы отсчётов Котельникова-Шеннона.
В том же 1928 г. Ральф Хартли в статье «Передача информации» [50], как уже упоминалось выше, определил количество информации (он впервые в технической литературе употребляет термин “information”), содержащейся в последовательности из n знаков, выражением H = n log s, где s – количество всевозможных различных знаков (объём алфавита) – информационная статика. Для максимизации скорости передачи информации первичные символы (знаки алфавита) следует закодировать вторичными с учётом ограничений, накладываемых на выбор знаков алфавита (как это и сделали в 1832 г. П. Шиллинг, а в 1838 г. – С. Морзе и А. Вайл). Там же Хартли, исходя из «эвристических соображений», утверждал, что количество знаковой информации, которое может быть передано по данному каналу связи (без шумов), пропорционально ширине его полосы пропускания и времени передачи информации.
Таким образом, Найквист и Хартли вплотную подошли к решению Проблемы № 3 ПТИ.
Ещё в 1920 г. в неопубликованном меморандуме Дж. Карсон пришёл к выводу, что при многоканальной телефонии с временным разделением каналов требуется гораздо бóльшая полоса пропускания многоканальной линии связи, чем в одноканальном случае [49]. В 1936 г. Г. Найквист показал (в неопубликованных меморандумах от 24.08.36 г. и от 12.11.36 г.), что если использовать предложенный им в статье 1928 г. [54] метод нелинейной обработки передаваемых сигналов, то можно значительно сузить необходимую для многоканальной телефонии полосу частот канала связи.
В статье К. Шеннона 1940 г. ([46], с. 433-460; опубликована статья в 1949 г.) и в его же статье 1948 г. ([46], с. 243-332) прикладная теория информации получила фундаментальное математическое обоснование.
|
|
|
П.3. Основные этапы развития теории кодирования [4, 5].
В области оптимального кодирования источников сообщений (сжатия информации):
1948 г. – алгоритм Шеннона-Фано;
1951 г. – «перекодировка» серий одинаковых символов А. Лайммеля (США);
1951 г. – метод кодирования Д. Хаффмена (США);
1956 г. – кодирование с использованием преобразования Карунена-Лоэва (Г. Крамер, М. Метьюз – США);
1956 г. – векторное квантование (Г. Штейнхаус – Франция);
1962 г. – апертурное сжатие (Дж. Халм, Р. Шомбург – США);
1966 г. – «универсальные коды» Б. М. Фитигофа (СССР), Линча-Девидс-сона (США);
1968 г. – «адаптивное кодирование» Р. Е. Кричевского (СССР);
1976 г. – универсальные коды Я. Зива и А. Лемпеля (США).
В области помехоустойчивого (канального) кодирования:
1949 г. – линейные коды М. Голея (США);
1949 г. – коды Р. Хэмминга (США);
1954 г. – итерированные коды П. Элайса (США);
1954 г. – линейные коды с мажоритарным декодированием (И. Рид, Д. Мал-лер – США);
1955 г. – свёрточные коды (П. Элайс – США; Л. М. Финк, В. И. Шляпоберский – СССР; 1956 г. – Р. Фано; 1959 г. – Д. Хегельбергер, США);
1955-56 гг. – циклические коды (Н. Цирлер, Д. Хаффмен, С. Голомб – США);
1957 г. – циклические коды Е. Прейнджа (США);
1959/60 г. – БЧХ-коды (Р. Боуз, Д. Рой-Чоудхури, А. Хоквингем – США);
1960 г. – линейные блочные коды (И. Рид, Г. Соломон – США);
1960 г. – «перемежение» (А. А. Харкевич, Э. Л. Блох: СССР; 1970 г. – Дж. Рамсей: США);
1964 г. – коды А. Витерби (США);
1965 г. – каскадные коды (Г. Форни – США; Э. Л. Блох и В. В. Зяблов – СССР);
1976 г. – «треллис-модуляция» (Г. Унгербоек – США);
1993 г. – «турбокоды» (К. Берроу, А. Главью – США).
