Неаддитивность энтропии приводит, иногда, к "парадоксальным" ситуациям.
В термодинамике известен парадокс Гиббса, аналогичный "парадокс" может быть предложен для информационной энтропии.
Пусть M - произвольное сообщение длины L с энтропией H.
Назовем арифметическое объединение сообщений (удвоение длины) последовательным соединением сообщений и логическое объединение (через побитовую операцию) - параллельным соединением сообщений.
Точный вид логической операции неважен, пусть, например, это будет XOR. Пример можно подобрать для любой.
Объединим два разных независимых сообщения M длиной L в одно.
При последовательном соединении сообщений энтропия результирующего соединения будет равна их сумме. При параллельном соединении сообщений энтропия результирующего соединения будет не больше единицы.
Объединим два идентичных сообщения M длиной L в одно.
При последовательном соединении сообщений энтропия результирующего соединения не изменяется. При параллельном соединении сообщений энтропия результирующего соединения в точности равна нулю.
Аналогично парадоксу Гиббса в термодинамике, в зависимости от того, известна ли нам идентичность (или независимость) сообщений, результирующая энтропия меняется скачком.
Энтропия и парадокс Гиббса
© Copyright: Инвариант, 2019
Свидетельство о публикации №219021301966
Свидетельство о публикации №219021301966
Рецензии
Параллельный сигнал не добавляет энтропии, если он идентичен. Но не добавляет и информации. Трудно измерить информацию и энтропию при последовательном включении, но обе они отличны от нуля. "честно-честно" – это не то же самое, что "честно".
Ник.
Ник Пичугин 14.02.2019 11:22 • Заявить о нарушении
Ник.
Ник Пичугин 14.02.2019 11:22 • Заявить о нарушении
> Параллельный сигнал не добавляет энтропии, если он идентичен. Но не добавляет и информации.
Не так. Это обычный криптопримитив - XOR. Результирующая энтропия может быть сделана любой (информация утеряна в любом случае).
Считается энтропия по обычным формулам, что для последовательного, что для параллельного включения (например, для ASCII алфавита - 256 байт).
> "честно-честно"
Это последовательное включение. А параллельное (XOR) - это набор тождественно нулевых байт (по самому смыслу операции XOR - несовпадение).
Инвариант 14.02.2019 11:58 Заявить о нарушении
Не так. Это обычный криптопримитив - XOR. Результирующая энтропия может быть сделана любой (информация утеряна в любом случае).
Считается энтропия по обычным формулам, что для последовательного, что для параллельного включения (например, для ASCII алфавита - 256 байт).
> "честно-честно"
Это последовательное включение. А параллельное (XOR) - это набор тождественно нулевых байт (по самому смыслу операции XOR - несовпадение).
Инвариант 14.02.2019 11:58 Заявить о нарушении
Хороший пример, где интенсивно используются обе операции (конкатенация и XOR, в наших терминах - последовательное и параллельное соединение) - сеть Фейстеля (см. вики). Статья на хабре: "Почему сеть Фейстеля работает? Объяснение 'на пальцах'" http://habr.com/ru/post/140404/
Инвариант 14.02.2019 12:40 Заявить о нарушении
Инвариант 14.02.2019 12:40 Заявить о нарушении
Не понимаю, почему информация будет утеряна в случае идентичных сигналов при параллельной подаче.
По формулам любой компьютер посчитает, а Вы посчитайте, когда у Вас вместо конкретного сигнала имеется понятие «сигнала». Передайте качество процесса.
Ник Пичугин 14.02.2019 13:02 Заявить о нарушении
По формулам любой компьютер посчитает, а Вы посчитайте, когда у Вас вместо конкретного сигнала имеется понятие «сигнала». Передайте качество процесса.
Ник Пичугин 14.02.2019 13:02 Заявить о нарушении
> Не понимаю, почему информация будет утеряна в случае идентичных сигналов при параллельной подаче
В силу самой операции XOR (несовпадение): (X XOR X) = 0.
См. вики: Сложение по модулю 2
Инвариант 14.02.2019 13:21 Заявить о нарушении
В силу самой операции XOR (несовпадение): (X XOR X) = 0.
См. вики: Сложение по модулю 2
Инвариант 14.02.2019 13:21 Заявить о нарушении
Спасибо за объяснения, Инвариант, я понял. Есть вещи, постигнуть которые мой слабый ум просто не в состоянии – и Вики мне не поможет. Потеря информации при нулевой энтропии к таким вещам явно относится.
Удачи. С уважением, Ник.
Ник Пичугин 14.02.2019 15:15 Заявить о нарушении
Удачи. С уважением, Ник.
Ник Пичугин 14.02.2019 15:15 Заявить о нарушении
> Потеря информации при нулевой энтропии
Я подозреваю, что вы рассматриваете сообщение как некую сумму информации и энтропии, что полностью неверно (А шенноновское "количество информации" - это инвариант деформации сообщения, произведение его энтропии на битовый размер).
Во-вторых, сами операции сложения ("параллельное соединение") и умножения ("последовательное соединение") деструктивны: 2+2=4 - полностью потеряна информация о слагаемых, 2*2=4 - полностью потеряна информация о сомножителях.
Что касается энтропии, смотрите на нее как на плотность объекта (фрактальная плотность). Если объект "рыхлый" - он может быть уплотнен. Если достиг максимальной плотности ("энтропийный предел") - то уже все.
Например, если у вас есть 10-символьный алфавит 0..9, то сообщение 0123456789 - максимально плотное: все допустимые состояния заняты. Оно несжимаемо (как и любая его перестановка - энтропия безразлична к порядку). А сообщение 0000000000 (или любая другая цифра 10 раз) - абсолютно сжимаемо, 9/10 состяний в нем свободно.
К слову, не читайте дрянных книжек: если встретите где-либо "энтропия - мера беспорядка", можете смело закрывать, автор просто не понимает того, о чем пишет.
Операция XOR деструктивна. Естественно, информация после выполнения потеряна. А энтропия может быть сделана любой - от 0 до 1 подходящим подбором операндов. Собственно, идея шифрования в этом и заключается - подобрать такую гамму, чтобы энтропия сообщения была как можно ближе к 1 (квазислучайное).
Инвариант 15.02.2019 00:22 Заявить о нарушении
Я подозреваю, что вы рассматриваете сообщение как некую сумму информации и энтропии, что полностью неверно (А шенноновское "количество информации" - это инвариант деформации сообщения, произведение его энтропии на битовый размер).
Во-вторых, сами операции сложения ("параллельное соединение") и умножения ("последовательное соединение") деструктивны: 2+2=4 - полностью потеряна информация о слагаемых, 2*2=4 - полностью потеряна информация о сомножителях.
Что касается энтропии, смотрите на нее как на плотность объекта (фрактальная плотность). Если объект "рыхлый" - он может быть уплотнен. Если достиг максимальной плотности ("энтропийный предел") - то уже все.
Например, если у вас есть 10-символьный алфавит 0..9, то сообщение 0123456789 - максимально плотное: все допустимые состояния заняты. Оно несжимаемо (как и любая его перестановка - энтропия безразлична к порядку). А сообщение 0000000000 (или любая другая цифра 10 раз) - абсолютно сжимаемо, 9/10 состяний в нем свободно.
К слову, не читайте дрянных книжек: если встретите где-либо "энтропия - мера беспорядка", можете смело закрывать, автор просто не понимает того, о чем пишет.
Операция XOR деструктивна. Естественно, информация после выполнения потеряна. А энтропия может быть сделана любой - от 0 до 1 подходящим подбором операндов. Собственно, идея шифрования в этом и заключается - подобрать такую гамму, чтобы энтропия сообщения была как можно ближе к 1 (квазислучайное).
Инвариант 15.02.2019 00:22 Заявить о нарушении
Еще раз спасибо – теперь уже за дополнительную лекцию, после которой я стал лучше понимать специфику Вашей специальности. В частности, ее терминологию (ее понимание): «энтропии», «рождения» и «потери» информации. Преобразование информации понимается как потеря – это действительно любопытно! Надеюсь и я оказаться для Вас чем-нибудь полезным, попробую прямо сейчас. Вероятно, Вы знаете, что «энтропия информации» по Шеннону) – это одно, а энтропия физических систем – это другое. И во втором смысле она действительно «мера хаоса», это уже моя специальность. И Шеннон ведь не с потолка взял свой термин.
С уважением, Ник.
Ник Пичугин 15.02.2019 15:28 Заявить о нарушении
С уважением, Ник.
Ник Пичугин 15.02.2019 15:28 Заявить о нарушении
> «энтропия информации» по Шеннону) – это одно, а энтропия физических систем – это другое.
На самом деле, оба понятия относятся к одно и тому же явлению - фракталу. У Клаузиуса - к газовому фракталу (идеальный газ), у Шеннона - к текстовому (сообщение).
В самом общем смысле, реакция системы на приложенную силу обратна ее импедансу ("термодинамическая тройка"). Клаузиус вывел энтропию, практически, из опыта - как изменение "тепловой координаты" системы в ответ на действие "тепловой силы" (температуры). Произведение этих двух параметров (экстенсивного и интенсивного) имеет смысл работы (энергии деформации).
Для произвольного фрактала всегда можно указать две измеримых характеристики - геометрический размер и плотность. Их произведение дает массу (меру). Неважно, о каком фрактале идет речь: идеальный газ, Млечный путь, текст - суть та же.
Информационная энтропия (Шеннона) имеет прямую аналогию в термодинамике (как координата деформации), а длина (сжимаемого) сообщения - аналог абсолютной температуры. Упаковка/распаковка текста - прямой аналог цикла Карно.
> И Шеннон ведь не с потолка взял свой термин.
Этот термин был предложен ему фон Нейманом (http://www.eoht.info/page/Neumann-Shannon+anecdote), много занимавшимся и термодинамической и квантовой энтропией, и сразу узнавшим в выведенной Шенноном формуле знакомую сущность.
Шеннон ввел информационную энтропию как плотность текстового фрактала. Помноженная на его размер, она дает меру ("массу") для текста (по Шеннону "количество информации"). Поделив эту "массу" на пропускную способность ("тару"), получаем расчет необходимого числа "контейнеров" для транспорта сообщения.
На самом деле, значение работы Шеннона далеко выходит за рамки теории связи, и именно после его работ стало понятно значение "информационной энтропии" как универсальной характеристики ("плотности") произвольного фрактального объекта.
Инвариант 15.02.2019 17:59 Заявить о нарушении
На самом деле, оба понятия относятся к одно и тому же явлению - фракталу. У Клаузиуса - к газовому фракталу (идеальный газ), у Шеннона - к текстовому (сообщение).
В самом общем смысле, реакция системы на приложенную силу обратна ее импедансу ("термодинамическая тройка"). Клаузиус вывел энтропию, практически, из опыта - как изменение "тепловой координаты" системы в ответ на действие "тепловой силы" (температуры). Произведение этих двух параметров (экстенсивного и интенсивного) имеет смысл работы (энергии деформации).
Для произвольного фрактала всегда можно указать две измеримых характеристики - геометрический размер и плотность. Их произведение дает массу (меру). Неважно, о каком фрактале идет речь: идеальный газ, Млечный путь, текст - суть та же.
Информационная энтропия (Шеннона) имеет прямую аналогию в термодинамике (как координата деформации), а длина (сжимаемого) сообщения - аналог абсолютной температуры. Упаковка/распаковка текста - прямой аналог цикла Карно.
> И Шеннон ведь не с потолка взял свой термин.
Этот термин был предложен ему фон Нейманом (http://www.eoht.info/page/Neumann-Shannon+anecdote), много занимавшимся и термодинамической и квантовой энтропией, и сразу узнавшим в выведенной Шенноном формуле знакомую сущность.
Шеннон ввел информационную энтропию как плотность текстового фрактала. Помноженная на его размер, она дает меру ("массу") для текста (по Шеннону "количество информации"). Поделив эту "массу" на пропускную способность ("тару"), получаем расчет необходимого числа "контейнеров" для транспорта сообщения.
На самом деле, значение работы Шеннона далеко выходит за рамки теории связи, и именно после его работ стало понятно значение "информационной энтропии" как универсальной характеристики ("плотности") произвольного фрактального объекта.
Инвариант 15.02.2019 17:59 Заявить о нарушении
А! Вот такая жесткая аналогия… Неудивительно, что фон Нейман ее увидел. Начинает доходить и до меня.
Если определяется «температура», и если «фрактал» – термин, я так понимаю, что вводмтся и функция распределения с переходом в статистику?
Инвариант, Вы извините, что я наглею. Просто я нигде не видел такого доступного изложения основ информатики Шеннона.
Отдельное спасибо за ссылку, я давно ее искал.
Ник Пичугин 16.02.2019 18:58 Заявить о нарушении
Если определяется «температура», и если «фрактал» – термин, я так понимаю, что вводмтся и функция распределения с переходом в статистику?
Инвариант, Вы извините, что я наглею. Просто я нигде не видел такого доступного изложения основ информатики Шеннона.
Отдельное спасибо за ссылку, я давно ее искал.
Ник Пичугин 16.02.2019 18:58 Заявить о нарушении
> Если определяется «температура», и если «фрактал» – термин, я так понимаю, что вводится и функция распределения с переходом в статистику?
Ну, фон Нейман этими терминами не оперировал. Шеннон тоже. Понятие фрактала Мандельброт сформулировал 30 годами позже. Но статистическое обоснование - да, по факту то же самое (через плотность вероятности). Шеннон искал (и нашел) меру на дереве выбора (см. оригинальную статью), а поскольку дерево - суть фрактал - то, естественно, и мера на дереве оказалась мерой на фрактале.
Просто с позиций сегодняшних знаний, стало возможным переформулировать некоторые классические результаты. (Например, "Размышления. Трансформатор Шеннона" http://www.proza.ru/2017/06/14/170)
Инвариант 16.02.2019 21:27 Заявить о нарушении
Ну, фон Нейман этими терминами не оперировал. Шеннон тоже. Понятие фрактала Мандельброт сформулировал 30 годами позже. Но статистическое обоснование - да, по факту то же самое (через плотность вероятности). Шеннон искал (и нашел) меру на дереве выбора (см. оригинальную статью), а поскольку дерево - суть фрактал - то, естественно, и мера на дереве оказалась мерой на фрактале.
Просто с позиций сегодняшних знаний, стало возможным переформулировать некоторые классические результаты. (Например, "Размышления. Трансформатор Шеннона" http://www.proza.ru/2017/06/14/170)
Инвариант 16.02.2019 21:27 Заявить о нарушении