Теория кодирования

9.5.L 1, 2, 3, 4, 4 ;

9.6.L 1, 2, 3, 4, 4, 4 ;

9.7.L 1, 2, 3, 4, 4, 4, 4 ;

9.8.L 1, 3, 3, 3, 3, 3, 3 ;

9.9.L 1, 4, 4, 4, 4, 4, 4, 4, 4

9.10.L 3, 3, 3, 3, 3, 3 .

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

10.1.1011;

10.2.010;

10.3.011;

10.4.1001;

10.5.1101;

10.6.10101011;

10.7.111001111;

10.8.100010011;

10.9.0110111011.

Разберем решение задачи 10.1.

Построим по методу Хэмминга кодовое слово для сообщения

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

Между информационными разрядами разместилось 3 контрольных разряда, найдем их из уравнений 11 .

Заполнив контрольные разряды, получим кодовое слово в коде Хэмминга 0110011.

11. По каналу связи передавалось кодовое слово, построенное по методу Хэмминга для сообщения . После передачи по каналу связи,

33

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

11.1.1001110;

11.2.110;

11.3.101110;

11.4.011110 ;

11.51001011;

11.6.0101101;

11.7.1011101;

11.8.1100011;

11.9.11011100110;

11.10.1010101010100;

11.11.001011110111111.

Рассмотрим решение задачи 11.1.

34

Заключение

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

35

Персоналии

Клод Шеннон родился 30 апреля 1916 года в городе Петоцки, штат Мичиган, США. В 1936 году Клод Шеннон оканчивает Мичиганский университет, получив степень бакалавра по двум специальностям: математика и электротехника. Статья, написанная по его магистерской работе 1937 года, «Символьный анализ реле и коммутаторов» стала причиной вручения ему Премии имени Альфреда Нобеля Американского института инженеров-электриков (1940 г.). В 1940 году Шеннон получает докторскую степень по математике и степень магистра по электротехнике.

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

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

Теоремы, сформулированные и доказанные Клодом Шенноном, являются выдающимися достижениями в теории кодирования.

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

За выдающиеся достижения в науке Клод Шеннон награжден Национальной медалью науки США.

Ричард Уэсли Хэмминг (родился 11 февраля 1915 г. в Чикаго, США) американский математик, человек с разносторонними интересами и большими достижениями в самых разных областях математики и техники. Он принимал участие в Манхэттенском проекте, ему принадлежат труды по теории информации, статистике. Широчайшую известность ему принесла работа по созданию помехоустойчивого кода, который получил его имя, хотя она занимает

36

ничтожное место среди множества его трудов. Хэмминга можно назвать гением одной идеи.

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

Дэвид Хаффман родился в 1925 году в штате Огайо, США. Хаффман получил степень бакалавра электротехники в государственном университете Огайо в возрасте 18 лет. Впоследствии он получил степень магистра в университете Огайо и степень доктора в Массачусетском институте технологий. В 1952 году Хаффман создал алгоритм префиксного кодирования с минимальной избыточностью (известный как алгоритм Хаффмана). Он также сделал вклад во множество других областей науки и техники (по большей части в электронике). Хаффман получил ряд ценных наград за вклад в науку, в том числе медаль Ричарда Хемминга от Института инженеров электричества и электроники

(1999 г.).

37

Список литературы

1.Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа, 2003.

2.Шевелев Ю.П. Дискретная математика. Учебное пособие.

Лань. 2008.

3.Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике: Учеб. Пособие для втузов – 3-е изд., перераб. – М.: Физматлит, 2004.

4.Новиков Ф.А. Дискретная математика для магистров и бакалавров: Санкт-Петербург, 2011.

5.Плотников А.Д. Дискретная математика. Учебное пособие. Новое знание, 2005.

38