Обобщённая теорема о пределах кодирования

УДК 519.72

Изложение статьи: Горшков А.В. Обобщённая теорема о пределах кодирования. // Потенциал.–2023.№7. – С.64–77.

Аннотация

В 2008 году доказана и в 2010 году опубликована теорема об информационном канале с воздействием, связывающая в единое неравенство скорость (а также цену) кода с тремя параметрами: удельной (на символ) энтропией текста, удельной (на позицию кода) энтропией воздействия на код в канале, удельной (на позицию сообщения) энтропией ошибки сообщения в целом после декодирования. Предельными частными случаями являются утверждения: криптографической теоремы Котельникова–Шеннона, теоремы о пропускной способности канала с помехой Шеннона, и др. Это позволяет оценивать помехоустойчивость, криптостойкость и скорость.

2. Пояснения об основных понятиях

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

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

Назовём «априорным признаком истинности сообщения» (АПИС) результат известного получателю алгоритма преобразования декодированного сообщения, разрешающего относительно свойства «не изменено/изменено» ли сообщение вследствие воздействия в канале.

4. Бригада наблюдателей

Клод Шеннон при рассмотрении канала с шумом постулировал «идеального», «волшебного» одиночного наблюдателя, сообщающего номинальному получателю об изменениях кодовых слов в канале вследствие помех, причём проверяющего и неизменность сообщений самого себя, сообщающего получателю и об изменениях в сообщениях самого себя, но никакой возможный метод его работы Шеннон, к сожалению, не указал. Мы поступим иначе (Рис.2) […]

5. Условия теорем

Пусть пользователи (отправитель и получатель) знают все параметры канала связи.
Требуется найти основные характеристики.

Теорема 1.

ЕСЛИ канал однонаправленный, дискретный, двоичный A=2; получатель не располагает АПИС; статистическое распределение воздействия не зависит от времени («стационарно»); кодируемые тексты длиной Lтекст>=1, не исключено, что бесконечные; мощность множества кодируемых текстов М натуральна и постоянна, причём 1<=M<=A^Lтекст; количество переданных текстов велико >>1 и, возможно, стремится к бесконечности; удельная (на знак текста) энтропия исходного текста 0<=Hтекст<=1; воздействие обладает удельной (на позицию кода) энтропией 0<=Hвозд<1; удельная (на позицию сообщения) энтропия ошибки «сообщения в целом после декодирования» 0<=HБяк<=1; длина сообщения равна длине текста Lсообщ=Lтекст, ТО существует «бригада наблюдателей» в совокупности с получателем такие, что средняя цена кода при стремлении длины текста к бесконечности – см. Формулу (1).

Теорема 2.

ЕСЛИ, во изменение двух условий Теоремы 1, допустимая ошибка декодера неабсолютна HБяк<>1, текст негарантированный Hтекст<>0, ТО существует «бригада наблюдателей» в совокупности с получателем такие, что средняя скорость кода при стремлении длины текста к бесконечности – см. Формулу (2)  

Теорема 3. 

ЕСЛИ, во изменение трёх условий Теоремы 1, воздействие совершенное Hвозд=1, а HБяк<>1 и Hтекст<>0, ТО код с ненулевой скоростью невозможен  Vкод=0 (3).

6. ДОКАЗАТЕЛЬСТВА ТЕОРЕМ
[…]

Примечание 1.

Чем больше длина сообщения, тем меньшую по вероятности долю в длине кода составляют затраты на нецелость и округление, и левая часть неравенства (0) становится всё ближе к равенству. Поэтому можно выдвинуть гипотезу, что при устремлении длины текста к бесконечности существует код такой, что цена кода сколь угодно близка к нижнему пределу (1), а скорость кода сколь угодно близка к верхнему пределу (2).

Примечание 2.

Если в канале действует в качестве воздействия разумный мощный осведомлённый (то есть знающий метод кодирования и параметры) противник, то он может применить следующую тактику. Он выждет до тех пор, пока длина сообщений от i-го наблюдателя, т.е. в (i+1)-м канале, не станет равной 1 бит. Тогда он инвертирует его (превратит в противоположный). Это заметит (i+1)-й наблюдатель и отправит в (i+2)-й канал сообщение об этом. Противник инвертирует и его. И так до бесконечности. Наименьшая требуемая цена кода станет бесконечной, скорость кода нулевой; но энтропия такого воздействия <1 , может быть, даже =0 при изменении всех битов в канале («полная инверсия»), следовательно, согласно Теоремам 1–2, должен существовать метод принимать информацию даже при таком воздействии.
Чтобы устранить влияние такой помехи, советские учёные Харкевич и Блох предложили дополнить канал «перемежителем» у отправителя кода (то есть перестановщиком битов кодированного текста на случайные места) и «деперемежителем» у получателя (то есть возвращателем битов кода после воздействия обратно на свои места). Если  перемежитель и деперемежитель ключезависимые, причём отправитель и получатель согласовали управляющие ими ключи по секретному от противника, причём достоверному (не подверженному воздействию противника), вспомогательному каналу, то воздействие противника подействует на лишь случайные позиции кода. Именно такую возможность для пользователей мы и подразумевали при доказательстве Теорем 1–3.

7. Исследовательские задачи

Задача 1.

Попробуйте обобщить условия теорем и формулы выводов теорем на дискретные не обязательно двоичные A>=2 симметричные каналы; при этом учтите, что в условиях теорем все энтропии будут ограничены не 1, а log2A. Проверьте, правда ли, что: – см. Формулы (4).

Задача 2 (очень повышенной трудности).

Зная Lтекста>=1 и Hвозд, оцените величину n+1 и, таким образом, обобщите Теоремы 1–3 и формулы (1–3) на случай конечных текстов.

8. Частные следствия теорем 1–3

Следствие 1:  не существует алгоритма при условиях теоремы 1 с ценой кода меньшей, чем по формуле (1), и не существует алгоритма при условиях теоремы 2 со скоростью кода большей, чем по формуле (2). Это утверждение очевидно из формулировки теорем 1–2, поскольку является лишь  частью их результатов.

Следствие 2. Пусть разрешена сколь угодно большая избыточность (см. выше п.3) кода, ненулевое воздействие тоже может быть сколь угодно велико. Вопрос: возможно ли гарантированно исправить все изменения в канале?
Решение: […]
Итак, при данных условиях цена кода бесконечна, скорость нулевая, то есть гарантированно исправить все изменения при произвольном воздействии в канале невозможно даже при сколь угодно большой избыточности.
Эта лемма известна, например, в учебнике Новикова […].

Следствие 3. Пусть воздействие есть помеха (см. выше п.2). Найти: «пропускную способность» (наибольшую скорость приёма информации получателем) такого информационного канала.
Решение: […] и получим 0<=Vинф<=1-Hпомех .
Это известная формула Шеннона (1949 г.) […] о пропускной способности канала с помехой.

Следствие 4. Пусть исходное двоичное сообщение предельно сжато Hтекст=1. Пусть также декодеру разрешено исправлять ошибки, возникшие в двоичном дискретном канале вследствие симметричных независимых помех, возникающих с вероятностью 0<=pизменения_бита<=1, необязательно гарантированно 0<=pошибки_декодера_в_бите<=1. Найти предельную скорость кода.
Решение: Подставим заданные параметры в (2), получаем – см. Формулу (4+).
Это формула скорости помехоустойчивого приёма сжатых сообщений с необязательно гарантированным исправлением помех, известная в статье В.Варгаузина […] со ссылкой на Мак-Кея […].

Следствие 5. Пусть помеха ненулевая и при этом негарантированная Hпомех>0, избыточность кода нулевая Ц=1 и текст сжат Нтекст=1, скорость приёма информации ненулевая Vинф>0. Возможен ли при таких условиях совершенно достоверный приём HБяк=0?
Решение: […] Итак, приём при указанных условиях невозможен.
Это есть теорема Котельникова (1946 г.) о невозможности совершенно достоверного приёма без избыточности с ненулевой скоростью при наличии помех, причём при отсутствии гарантированного (в каждой позиции) изменения (инверсии) знаков в двоичном канале.

Следствие 6. Пусть ошибок декодирования не должно быть HБяк=0 , помехи в канале отсутствуют, отправитель предварительно сжимает (возможно, не полностью) текст. Найти наименьшую цену кода.
Решение: это совершенно определённое воздействие, т.е. Hвозд=0. Подставим это и условие в (1), получим Ц>=Hтекст.
Это часть теоремы Шеннона об экономичном («оптимальном») кодировании (сжатии).

Следствие 7. Пусть отправитель сжимает и зашифровывает текст с помощью ключа, неизвестного (или неполностью известного) криптоаналитику НКлючаШифра>0. Найти: меру неопределённости расшифрованного сообщения для криптоаналитика.
Решение: […] воздействие здесь есть шифрование, Нвозд=НКлючаШифра , ищем меру неопределённости расшифрованного сообщения НБяк. Из (1) и (2) находим: – см. Формулы (5).

Отсюда очевидно, что для криптостойкости благоприятно повышение НКлючаШифра , а также уменьшение Ц и увеличение Vкод. Увеличение Нтекст увеличивает криптостойкость, следовательно, если исходный текст низкоэнтропийный (например, сообщение на человеческом том или ином национальном языке), то его целесообразно перед зашифрованием упаковывать (разумеется, озаботившись устранением вредного влияния известной противнику, служебной, части упакованного файла на криптостойкость ключа, например, эту служебную часть не шифровать или, если очень хочется шифровать и её, то другим ключом).

Рассмотрим упрощённый пример. Пусть длина ключа равна длине исходного текста L0, ключ шифрования совершенно случайный HКлючаШифра=1, Vкод>0 , Ц<бесконечности. Тогда из (5) и свойств удельной энтропии следует 1>=HБяк>=1, т.е. HБяк=1, то есть криптостойкость совершенная (абсолютная). Это значит, что для получения исходного сообщения криптоаналитику придётся рассмотреть 2^L0 равнозначных вариантов.
Ещё пример. Пусть Ц=Vкод=1 (зашифрование без добавления избыточности) и Hтекст=1 (текст заранее предельно упакован), тогда из (5) получаем HБяк>=HКлючаШифра. То есть при данных условиях криптостойкость не менее чем неопределённость ключа шифрования, наименьшая (наихудшая) криптостойкость равна неопределённости ключа шифрования. Это есть криптографическая теорема Котельникова (1941 г.) – Шеннона (1945 г.), она же «о сочетании секретного и предельно экономичного кодирований» […].

Ещё пример. Пусть Ц=Vкод=1 (зашифрование без добавления избыточности), сообщение может быть упаковано 0<=Hтекст<=1. Тогда из (5) следует – см. Формулу (6).
Это есть обобщение криптографической теоремы Котельникова–Шеннона на случай неполностью упакованного заранее текста, то есть формула сочетания секретного и экономичного кодирований.

Следствие 8. Рассмотрим сочетание достоверного и экономичного кодирований.
Из (1) следует    – см. Формулу (7).
отсюда очевидно, на максимально достижимое снижение неопределённости результата декодирования HБяк благотворно влияет не только уменьшение Hпомех и увеличение Ц, но и уменьшение Нтекст.

Следствие 9. Рассмотрим сочетание секретного и достоверного кодирований. Из (7) видно, что любое увеличение цены кода Ц увеличивает верхнюю границу достоверности для номинального получателя – см. Формулу (7+), т.к. при этом Hвозд имеет смысл Hпомех , то есть неполное знание вектора помехи.  Но при этом уменьшается нижняя граница секретности от противника HБяк, т.к. при этом  Нвозд имеет смысл HКлюча , то есть неполное знание противником ключа расшифрования.
Влияние сжатия при этом тоже неоднозначно: увеличение Нтекст (предварительное сжатие) повышает криптостойкость HБяк и уменьшает достоверность очистки от помех 1-HБяк .

9. ЗАКЛЮЧЕНИЕ

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

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

АПРОБАЦИИ И ПУБЛИКАЦИИ:

1. Горшков А.В. Обобщённая теорема кодирования и оценки практически достижимой скорости помехоустойчивого приёма в сколь угодно грязных каналах в однонаправленных системах без априорной информации о сообщении, а также в двунаправленных с признаком истинности декодирования. (25 с.) // (08.06.2008) ...
2. Горшков А.В. Единая теорема кодирования и её частные следствия. (2008 г.) / Научно-практическая конференция преподавателей и сотрудников ЮУрГУ. Секция информатики. - Челябинск. - 12.04.2010.
3. Горшков А.В. Единая теорема кодирования и её частные следствия. (2008 г., направлена в марте 2010 г.) // ХХХ Российская школа по проблемам науки и технологий. Секция "Динамика и управление". - Миасс. - 15-17.06.2010 // Наука и технологии. Тезисы докладов XXX Российской школы, посвящённой 65-летию Победы. - Миасс: МСНТ, 2010. - С.59.
4. Горшков А.В. Единая теорема кодирования и следствия из неё. // Актуальные проблемы современной науки: Труды 11-й Международной конференции молодых учёных и студентов (16-18.11.2010). Естественные науки. Часть 20: Приборостроение, радиотехника и связь. Самара: Изд-во СГОУ(Н), 2010. - С.8-12.
5. Горшков А.В. Обобщённая теорема кодирования и частные следствия из неё. / Доклад. 63-я научно-практическая Конференция ЮУрГУ. Секция радиотехники. 29.04.2011.
6. Горшков А.В. Обобщённая теорема кодирования и частные следствия из неё. // Цифровые радиоэлектронные системы. - 2011. №8. С.65-70. - Электронный ресурс http://crts.niics.ru/vol8/a10_08.zip
7. Горшков А.В. Теорема кодирования в общем случае. // Электронный ресурс (конкурс "Свободный полёт") http://novmysl.finam.ru/files/konkurs2012/gor.rar - 04.2012. - 10 с.
8. Горшков А.В. Обобщённая теорема о пределах кодирования. // Потенциал.–2023.№7. – С.64–77.