WikiSort.ru - Не сортированное

«Математическая теория связи» (англ. A Mathematical Theory of Communication) — статья, опубликованная Клодом Шенноном в 1948 году в реферативном журнале американской телефонной компании «Bell System»^[1] и сделавшая его всемирно известным. Содержа в себе большое количество инновационных и плодотворных идей, эта работа инициировала многие научные исследования по всему миру, продолжающиеся по сей день, положив начало развитию методов обработки, передачи и хранения информации.

Об авторе

Клод Э́лвуд Ше́ннон (англ. Claude Elwood Shannon) — американский математик и инженер, основатель теории информации, автор многих книг и статей по кибернетике.

История

Само понятие теории информации появилось задолго до публикации этой статьи. Множество авторов своими работами закладывали фундамент новой теории. Например, в том же журнале компании «Bell System» в 1924 году была публикация Найквиста, содержащая в себе некоторые положения, лежащие в основе данной статьи^[2].

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

Содержание

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

В книге вводится логарифмическая функция как мера информации, и показывается её удобство:

Она удобна практически. Параметры, важные в инженерных приложениях — такие, как время, пропускная способность, число переключателей и так далее — обычно меняются линейно при логарифмическом изменении числа возможных вариантов. К примеру, добавление одного переключателя удваивает число возможных состояний их группы, увеличивая на единицу его логарифм по основанию 2. Увеличение в два раза времени приводит к квадратичному росту числа сообщений, или удвоению их логарифма, и так далее. Она близка к нашему интуитивному представлению о такой мере. Это тесно связано с предыдущим пунктом, так как мы интуитивно измеряем величины, линейно сравнивая их со стандартами. Так, нам кажется, что на двух перфокартах можно разместить в два раза больше информации, а по двум одинаковым каналам — передать её в два раза больше. Она удобна математически. Многие предельные переходы просты в логарифмах, в то время как в терминах числа вариантов они достаточно нетривиальны. К. Шеннон[3]

Также вводится понятие обобщённой системы связи, состоящей из источника информации, передатчика, канала, приемника и пункта назначения. Шеннон разделяет все системы на дискретные, непрерывные и смешанные.

Влияние на различные направления науки

^[2] Много времени спустя после своего появления, вопреки распространенному мнению, эта работа Шеннона была почти безвестной. Вот что пишет, например, по этому поводу академик А. Н. Колмогоров:

— Мне вспоминается, что ещё на международном съезде математиков в Амстердаме (1954 г.) мои американские коллеги, специалисты по теории вероятностей, считали мой интерес к работам Шеннона несколько преувеличенным, так как это более техника, чем математика. А. Колмогоров[4]

Но постепенно ученые из различных областей науки стали проявлять к статье все больший интерес. Сейчас трудно назвать область человеческих знаний, в которой замечательную формулу не пытались бы так или иначе применить. Количество публикаций росло, что не могло не вызвать ответной реакции со стороны самого Шеннона, так как изначально эта мера предназначалась только для сугубо прикладных задач техники связи. В 1956 году он опубликовал коротенькую статью «Бандвагон», в которой горячо призывал писать скромнее о теории информации, не считать эту теорию всемогущей и универсальной, не преувеличивать её значения:

Очень редко удается открыть одновременно несколько тайн природы одним и тем же ключом. Здание нашего несколько искусственно созданного благополучия слишком легко может рухнуть, как только в один прекрасный день окажется, что при помощи нескольких магических слов, таких, как «информация», «энтропия», «избыточность», нельзя решить всех нерешённых проблем. К. Шеннон[5]

В результате появилось два понятия — «теория информации» и «теория передачи информации». Первая определяет такие фундаментальные понятия, как «количество информации», и применяется для решения самых разнообразных проблем различных разделов науки. Вторая — уже своим названием отражает адекватную сферу применения её идей^[6].

С развитием теории передачи информации стали сталкиваться с проблемой поиска надежных методов кодирования и декодирования. Это привело к появлению нового большого раздела теории передачи информации — теории кодирования. Мы знаем, что во-первых из шенноновской теории информации следовал тот важный вывод, что построение слишком хороших каналов является расточительством; экономически выгоднее использовать кодирование. Во вторых, из-за того, что основная теорема кодирования Шеннона не конструктивна, то есть она лишь доказывает существование оптимального помехоустойчивого кода, обеспечивающего предельное согласование сигнала с каналом, только обосновывает принципиальную возможность построения помехоустойчивых кодов, обеспечивающих идеальную передачу, но не указывает способ их построения. В итоге теория Шеннона мобилизовала усилия ученых на разработку конкретных кодов.^[7]

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

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

В последовательном декодировании вводится класс неблоковых кодов бесконечной длины, которые можно описать деревом и декодировать с помощью алгоритмов поиска по дереву. Наиболее полезными древовидными кодами являются коды с тонкой структурой, известные под названием свёрточных кодов^[8].

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

Настоящее время

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

• В развитии теории кодирования достигнуты большие успехи. Появилось много различных помехоустойчивых кодов, отличающихся друг от друга основанием, расстоянием, избыточностью, структурой, функциональным назначением, энергетической эффективностью, корреляционными свойствами, алгоритмами кодирования и декодирования, формой частотного спектра (см. Помехоустойчивое кодирование).
• В наше время практические рекомендации, полученные на основе теории алгоритмов, имеют большой успех в области проектирования и разработки программных систем^[9].

Сама статья по-прежнему сохраняет актуальность, являясь основополагающей для многих работ.

Литература

• Оригинал статьи: Shannon C. E. A Mathematical Theory of Communication (англ.) // Bell System Technical Journal^[en] : журнал. — 1948. — Vol. 27. — P. 379—423.
• Русский перевод: Шеннон К. Э. Математическая теория связи // Работы по теории информации и кибернетике / Пер. С. Карпова. — М.: ИИЛ, 1963. — 830 с.

Ссылки