2014 dxdy logo

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

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




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


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

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

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

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

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


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

(Оффтоп)

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

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


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

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

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

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


12/07/15
2907
г. Чехов
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
2907
г. Чехов
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
2907
г. Чехов
Точно ведь. :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
586
Беларусь, Минск
Mihaylo
В учебниках формула Хартли рассматривается как частный случай формулы Шеннона. Поскольку я изучаю теоретические основы информатики по учебникам, постольку мне было интересно узнать про обратный вывод. Но исходя из результатов обсуждения, я понял, что формула Шеннона не выводится из формулы Хартли. К чему тогда Вы сообщаете недостоверные сведения? :-(

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


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

А вообще, самым загадочным является число $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
2907
г. Чехов
arseniiv в сообщении #1431717 писал(а):
Вы про то, что мы можем считать некоторые буквы алфавита тождественными, а так же считать за буквы нового алфавита последовательности букв старых? Так это никто не запрещает делать, тут нет никаких волшебных не учитываемых кем-то там вещей, всё банально.

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

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


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

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

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


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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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