Роберт Марио Фано

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

БУ ВО ХАНТЫ-МАНСИЙСКОГО АВТОНОМНОГО ОКРУГА-ЮГРА «СУРГУТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Политехнический институт

Реферат

По дисциплине: Теория информации

На тему: Роберт Марио Фано

Выполнил:

Студент 1-го курса группы 606-72

Иванов И.И.

Руководитель:

Гавриленко Анна Владимировна

Сургут 2017

Роберт Марио Фано (Robert Mario Fano, 11 ноября 1917, Турин, Италия -- 13 июля 2016, Нейплс, Флорида, США) -- итальяно-американский учёный в области информатики, профессор-эмерит факультетов электротехники и компьютерных наук в Массачусетском технологическом институте, действительный член Национальной академии наук США и ряда других национальных академий. Фано известен по работам в области теории информации, он независимо от Клода Шеннона изобрел ранний алгоритм сжатия информации и вывел неравенство Фано.

Биография и карьера

Роберт Фано родился 11 ноября 1917 года в Турине в учёной и богатой еврейской семье. Его отец -- Джино Фано, мать, Роза Кассин, происходила из семьи инженеров и была художницей и музыкантом. Брат -- Уго Фано. Двоюродный брат -- Джулио Рака.

Учился в Политехническом университете Турина, одна после принятия в Италии антисемитских законов в 1939 году эмигрировал в Соединённые Штаты.

В 1941 году получил степень бакалавра в Массачусетском технологическом институте.

Затем 6 лет работал в Радиационной лаборатории Массачусетского технологического института.

В 1947 году защитил докторскую диссертацию.

В начале 1950-х годов предложил неравенство Фано (лемму), связывающую среднюю потерю информации через канал передачи с шумами с вероятностью ошибок при приёме сигнала. Лемма была опубликована в 1961 году. Неравенство применяется для вычисления нижней границы вероятности ошибки для любого декодера, и для получения границ для минимаксного риска в оценке плотности.

В 1958 году -- член Американской академии искусств и наук.

В начале 1960-х годов принимал участие в развитии компьютеров с разделением времени, например, создав совместно с Фернандо Корбато систему Compatible Time-Sharing System.

В 1963?1968 годах Фано основал и руководил проектом MAC, позже ставший лабораторией института Массачусетского технологического института (MIT Computer Science and Artificial Intelligence Laboratory).

В 1973 году -- действительный член Национальной академии инженерных наук США.

В 1978 году -- член Национальной академии наук США.

Труды посвящены теории информации, микроволновым системам, электромагнетизму и теории сетей. Независимо от Клода Шеннона изобрёл ранний алгоритм сжатия информации (Алгоритм Шеннона -- Фано).

Умер 13 июля 2016 года в Нейплсе, штат Флорида.

Труды

Условие Фано

Условие Фано (англ. Fano condition, в честь Роберта Фано) -- в теории кодирования -- достаточное условие построения самотерминирующегося кода (в другой терминологии, префиксного кода). Обычная формулировка этого условия выглядит так:

Никакое кодовое слово не может быть началом другого кодового слова.

Более «математическая» формулировка:

Если в код входит слово a, то для любой непустой строки b слова ab в коде не существует.

Примером кода, удовлетворяющего условию Фано, являются телефонные номера в традиционной телефонии. Если в сети существует номер 101, то номер 1012345 не может быть выдан: при наборе трёх цифр АТС прекращает понимать дальнейший набор и соединяет с адресатом по номеру 101. Однако для набора с сотового телефона это правило уже не действует, потому что требуется явное завершение последовательности знаков соответствующей кнопкой (обычно -- с изображением зелёной трубки), при этом 101, 1010 и 1012345 могут одновременно пониматься как разные адресаты.

Термин «условие Фано» не является традиционным для русскоязычного сообщества.

Алгоритм Шеннона-Фано

Алгоритм Шеннона -- Фано -- один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Роберт Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже и является логическим продолжением алгоритма Шеннона. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся -- кодом большей длины. Коды Шеннона -- Фано префиксные, то есть никакое кодовое слово не является префиксом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов.

Кодирование Шеннона -- Фано (англ. Shannon-Fano coding) -- алгоритм префиксного неоднородного кодирования. Относится к вероятностным методам сжатия (точнее, методам контекстного моделирования нулевого порядка). Подобно алгоритму Хаффмана, алгоритм Шеннона -- Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его (первичного) алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов -- более длинными двоичными последовательностями.

Алгоритм был независимо друг от друга разработан Шенноном (публикация «Математическая теория связи», 1948 год) и, позже, Фано (опубликовано как технический отчёт).

Основные этапы: фано шеннон информатика кодирование

1. Символы первичного алфавита m₁ выписывают по убыванию вероятностей.

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

3. В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части -- «1».

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

Когда размер подалфавита становится равен нулю или единице, то дальнейшего удлинения префиксного кода для соответствующих ему символов первичного алфавита не происходит, таким образом, алгоритм присваивает различным символам префиксные коды разной длины. На шаге деления алфавита существует неоднозначность, так как разность суммарных вероятностей {\displaystyle p_{0}-p_{1}}Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Код Шеннона -- Фано строится с помощью дерева. Построение этого дерева начинается от корня. Всё множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0, как в случае кода Хаффмана.

При построении кода Шеннона -- Фано разбиение множества элементов может быть произведено, вообще говоря, несколькими способами. Выбор разбиения на уровне n может ухудшить варианты разбиения на следующем уровне (n + 1) и привести к неоптимальности кода в целом. Другими словами, оптимальное поведение на каждом шаге пути ещё не гарантирует оптимальности всей совокупности действий. Поэтому код Шеннона -- Фано не является оптимальным в общем смысле, хотя и дает оптимальные результаты при некоторых распределениях вероятностей. Для одного и того же распределения вероятностей можно построить, вообще говоря, несколько кодов Шеннона -- Фано, и все они могут дать различные результаты. Если построить все возможные коды Шеннона -- Фано для данного распределения вероятностей, то среди них будут находиться и все коды Хаффмана, то есть оптимальные коды.

Исходные символы:

· A (частота встречаемости 50)

· B (частота встречаемости 39)

· C (частота встречаемости 18)

· D (частота встречаемости 49)

· E (частота встречаемости 35)

· F (частота встречаемости 24)

Полученный код: A -- 11, B -- 101, C -- 100, D -- 00, E -- 011, F -- 010.

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

Неравенство Фано

В начале 1950-х Фано предложил неравенство (лемму), связывающую среднюю потерю информации через канал передачи с шумами с вероятностью ошибок при приёме сигнала. Лемма была опубликована в 1961 году.

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

Членство в академиях и награды

Фано стал действительным членом Национальной академии инженерных наук в 1973, Национальной академии наук США в 1978 и Американской академии искусств и наук в 1958.

В 1976 году Фано получил награду им. Шеннона за работы в области теории информации.

Библиография

Кроме работ в области теории информации, Фано написал несколько статей и книг о микроволновых системах, электромагнетизме, теории сетей.

· Microwave Transmission Circuits, под ред. George L. Ragan, том 9 в серии Radiation Laboratory Series (соавтор, 1948).

· Electromagnetic Energy Transmission and Radiation (с Lan Jen Chu и Richard B. Adler, 1960).

· Electromagnetic Fields, Energy, and Forces (с Chu и Adler, 1960).

· Robert M. Fano, Transmission of Information: A Statistical Theory of Communications. Cambridge, Mass., M.I.T. Press, 1961, ISBN 978-0262561693

· Р. Фано, Передача информации. Статистическая теория связи / Пер. с англ. яз. И. А. Овсеевич, Р. Л. Добрушин. М.: Мир, 1965. 440 с.

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

URL: https://ru.wikipedia.org - Википедия

Размещено на Allbest.ru