2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней. На страницу 1, 2  След.
 
 Теория информации и теория шифрования: формулы Хартли и Шеннона
Сообщение18.12.2019, 17:50 


12/07/15
3552
г. Чехов
druggist в сообщении #1429146 писал(а):
Можно ли в эту стройную систему включить еще и шифрование - защиту информации, не технологии, а смысл?

Не верьте научно-популярным книжкам, которые утверждают, что теория Шеннона работает только с синтаксисом. (В самих этих же книжках приводятся сотни примеров, в которых манипулируется смысл сообщения и точно не написание/синтаксис, но авторы почему-то это не замечают.)

А с синтаксисом хорошо работает формула Хартли. Вообще эта формула более универсальна.

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

 Профиль  
                  
 
 Re: Теория информации и теория шифрования
Сообщение19.12.2019, 09:22 
Аватара пользователя


11/03/12
643
Беларусь, Минск
Mihaylo в сообщении #1430843 писал(а):
И самое интересное, что из формулы Хартли можно вывести формулу Шеннона.

(Оффтоп)

Хотелось бы узнать, как это сделать.

 Профиль  
                  
 
 Re: Теория информации и теория шифрования
Сообщение19.12.2019, 15:37 
Заслуженный участник


27/04/09
28128
Да, мне тоже интересно, зачем так цепляться за исторические понятия, которые замечательно уже покрыты более универсальными и имеющими ясные причины существовать (представьте, что на этом месте была бы «релятивистская масса»). Когда мы не знаем распределение символов, мы можем явным образом применить принцип максимальной энтропии и получить своё вожделенное равномерное распределение, и это по-моему более сознательно.

Ну или если формула Хартли выводится так же аккуратно как формула Шеннона, и при этом без даже неявного упоминания вероятностей, я вчитаюсь и наверняка скажу «ладно, защищайте её сколько угодно». Достаточно ссылки.

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

 Профиль  
                  
 
 Re: Теория информации и теория шифрования
Сообщение20.12.2019, 03:54 


12/07/15
3552
г. Чехов
arseniiv в сообщении #1430990 писал(а):
Когда мы не знаем распределение символов, мы можем явным образом применить принцип максимальной энтропии и получить своё вожделенное равномерное распределение, и это по-моему более сознательно.

Можем. А можем придумать еще тысячу способов вычисления числа степеней свободы $N$. Не надо накладывать ограничение на формулу Хартли.

arseniiv в сообщении #1430990 писал(а):
Ну или если формула Хартли выводится так же аккуратно как формула Шеннона, и при этом без даже неявного упоминания вероятностей, я вчитаюсь и наверняка скажу «ладно, защищайте её сколько угодно». Достаточно ссылки.

https://de.ifmo.ru/bk_netra/page.php?in ... utindex=13
Комментарий в двух словах: применяется формула Стирлинга-Муавра. Вместо вероятности можете говорить о частоте символов в тексте.

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

С формулой Шеннона все сложнее. Популярны попытки вычислять энтропию (плотность энтропии) непрерывных величин с помощью формулы Шеннона. Так вот там получается почти красивый результат, но с корявой дельтой, которая далеко не стремится к нулю. Эту дельту отбрасывают и называют это дифференциальной энтропией, типа мы сравниваем информационные меры двух непрерывных величин, корявая дельта сокращается, нас интересует относительная информация, а не абсолютная. Пруф здесь, формулы 6.22 и 6.23: https://studref.com/475212/tehnika/info ... oobscheniy
При применении формулы Хартли эта дельта не образуется. Так это еще одно свидетельство того, что формула Шеннона является приблизительной.

 Профиль  
                  
 
 Re: Теория информации и теория шифрования: формулы Хартли и Шенн
Сообщение21.12.2019, 19:57 
Заслуженный участник


27/04/09
28128
Mihaylo в сообщении #1431060 писал(а):
Популярны попытки вычислять энтропию (плотность энтропии) непрерывных величин с помощью формулы Шеннона.
Да, непрерывный случай — вещь хитрая, потому что нет равномерного распределения на всей оси, потому насколько-то полезный результат будет только для величин, распределённых на конечном промежутке. Но это-то другая история.

Mihaylo в сообщении #1431060 писал(а):
https://de.ifmo.ru/bk_netra/page.php?index=25&layer=3&tutindex=13
Комментарий в двух словах: применяется формула Стирлинга-Муавра. Вместо вероятности можете говорить о частоте символов в тексте.
Так это ж не про формулу Хартли.

Mihaylo в сообщении #1431060 писал(а):
При применении формулы Хартли эта дельта не образуется.
Это очень интересно было бы увидеть в деталях.

Кстати если кому интересно, вот одна из уже корректно определённых в непрерывном случае величин:
(en.wikipedia) Kullback—Leibler divergence (что упоминается в разделе Properties).

 Профиль  
                  
 
 Re: Теория информации и теория шифрования: формулы Хартли и Шенн
Сообщение22.12.2019, 04:21 


12/07/15
3552
г. Чехов
arseniiv в сообщении #1431326 писал(а):
Так это ж не про формулу Хартли.

Ну вот же она, явно применена в формуле (3) по ссылке:
$I = H_0 - H_1 = \ln(\frac{N!}{N_1!N_2!...N_M!}) - \ln(2) = \frac{1}{\ln(2)}\cdot \ln(\frac{N!}{N_1!N_2!...N_M!})$

 Профиль  
                  
 
 Re: Теория информации и теория шифрования: формулы Хартли и Шенн
Сообщение22.12.2019, 18:37 
Заслуженный участник


27/04/09
28128
Mihaylo
А, это вы отвечали на вопрос angor6 больше тогда. Но кроме того вы сейчас написали что-то не то: в тексте $H_0, H_1$ не упоминаются, и правый знак равенства вообще в общем случае неверен, в смысле что $\ln a - \ln b\not\equiv \frac1{\ln b} \ln a$, откуда вы вообще так решили, и не издеваетесь ли вы часом. :wink:

-- Вс дек 22, 2019 20:38:29 --

(Короче с намечающимся уровнем всё понятно. Я на таком уровне обсуждать ничего не буду, ладно? Я с удовольствием послушаю более квалифицированную защиту формулы Хартли или чего угодно, но не такую.)

 Профиль  
                  
 
 Re: Теория информации и теория шифрования: формулы Хартли и Шенн
Сообщение23.12.2019, 08:03 


12/07/15
3552
г. Чехов
Точно ведь. :shock:
Там была идея такая:
$\log_2\frac{N!}{N_1!N_2!...N_M!} = \frac{1}{\ln(2)}\cdot \ln \frac{N!}{N_1!N_2!...N_M!}$

 Профиль  
                  
 
 Re: Теория информации и теория шифрования: формулы Хартли и Шенн
Сообщение23.12.2019, 14:42 
Аватара пользователя


11/03/12
643
Беларусь, Минск
Mihaylo
В учебниках формула Хартли рассматривается как частный случай формулы Шеннона. Поскольку я изучаю теоретические основы информатики по учебникам, постольку мне было интересно узнать про обратный вывод. Но исходя из результатов обсуждения, я понял, что формула Шеннона не выводится из формулы Хартли. К чему тогда Вы сообщаете недостоверные сведения? :-(

 Профиль  
                  
 
 Re: Теория информации и теория шифрования: формулы Хартли и Шенн
Сообщение23.12.2019, 21:25 


12/07/15
3552
г. Чехов
На экзамене, конечно, следует говорить, что формула Хартли - частный случай, иначе схлопочете неуд.

А вообще, самым загадочным является число $N$, а не вероятность $p_i$. Вероятность $p_i$ - это вполне конкретная вероятность. Если Вы под $N$ понимаете нечто в узком смысле - число букв в алфавите, например, то да, формула Хартли становится настолько частным случаем, что ужасно подумать.

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

Рассмотрите частный случай
$N = \frac{M!}{N_1!N_2!...N_M!}$ - это число перестановок букв алфавита размером $M$ с повторениями.

Для перехода к формуле Шеннона нужно применить формулу Стирлинга-Муавра и определение частоты символа
$p_i \approx f_i = \frac{N_i}{M}$

Данный факт широко известен. Можете подсмотреть в классической книге Л. Бриллюэна "Наука и теория информации", перевод А.А. Харкевича 1960, страница 24.

Этот факт редко попадает в современные перепечатки классических трудов, и он до сих пор не понят. :lol:

 Профиль  
                  
 
 Re: Теория информации и теория шифрования: формулы Хартли и Шенн
Сообщение23.12.2019, 21:38 
Заблокирован


16/04/18

1129
Mihaylo - спасибо за Стирлинга-Муавра, исторически правильно.

 Профиль  
                  
 
 Re: Теория информации и теория шифрования: формулы Хартли и Шенн
Сообщение23.12.2019, 22:29 
Заслуженный участник


27/04/09
28128
Mihaylo в сообщении #1431562 писал(а):
Там была идея такая:
$\log_2\frac{N!}{N_1!N_2!...N_M!} = \frac{1}{\ln(2)}\cdot \ln \frac{N!}{N_1!N_2!...N_M!}$
Ну это даже не идея, это банальное школьное выражение логарифма по одному основанию через логарифм по другому. :-)

Mihaylo в сообщении #1431704 писал(а):
Фактически же $N$ - это число комбинаций, а комбинаций чего - это специально не оговаривается, и это правильный подход. Смотря какую информацию хотите измерить, то число и подставляется. Не надо ограничиваться размером алфавита! И в этом случае формула Хартли становится более универсальной, чем формула Шеннона. Вот такие вот делишки творятся.
Вы про то, что мы можем считать некоторые буквы алфавита тождественными, а так же считать за буквы нового алфавита последовательности букв старых? Так это никто не запрещает делать, тут нет никаких волшебных не учитываемых кем-то там вещей, всё банально.

 Профиль  
                  
 
 Re: Теория информации и теория шифрования: формулы Хартли и Шенн
Сообщение24.12.2019, 07:08 


12/07/15
3552
г. Чехов
arseniiv в сообщении #1431717 писал(а):
Вы про то, что мы можем считать некоторые буквы алфавита тождественными, а так же считать за буквы нового алфавита последовательности букв старых? Так это никто не запрещает делать, тут нет никаких волшебных не учитываемых кем-то там вещей, всё банально.

Именно. Но из этого следуют важные вещи.

 Профиль  
                  
 
 Re: Теория информации и теория шифрования: формулы Хартли и Шенн
Сообщение24.12.2019, 08:49 


27/02/09
2858
Mihaylo в сообщении #1431704 писал(а):
А вообще, самым загадочным является число $N$,

А что тут такого сильно загадочного? Возьмите, например, в качестве $N$ кусок текста длины $N$ на языке с алфавитом длины $M$ (включая пробел), если текст достаточно длинный, применяйте на здоровье формулу Стирлинга. Другой пример - термодинамика, Больцман(Хартли) и Гиббс(Шеннон), там "текст" длинный по определению

 Профиль  
                  
 
 Re: Теория информации и теория шифрования: формулы Хартли и Шенн
Сообщение24.12.2019, 13:03 
Заслуженный участник


27/04/09
28128
Mihaylo в сообщении #1431758 писал(а):
Но из этого следуют важные вещи.
Ну из многого следуют важные вещи; какие именно в этом случае?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: HungryLion


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group