WikiSort.ru - Не сортированное

Теоремы Шеннона для источника без памяти связывают энтропию источника и возможность сжатия кодированием с потерями и последующим неоднозначным декодированием.

Прямая теорема показывает, что с помощью кодирования с потерями возможно достичь степени сжатия

${\displaystyle {\frac {N}{L}}\approx {\frac {H\left(U\right)\left({1+\varepsilon }\right)}{\log _{2}D}}}$ ,

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

Формулировка теорем

Пусть заданы:

• ${\displaystyle U}$  — некоторый источник сообщений, а также множество всех его сообщений ${\displaystyle u_{1},u_{2},...,u_{K}}$
• ${\displaystyle \Omega }$  — множество всех входных последовательностей длины ${\displaystyle L}$ , которое разделяется на:
  • ${\displaystyle M_{L}}$  — множество входных последовательностей однозначного декодирования
  • ${\displaystyle M_{L}^{C}}$  — множество входных последовательностей неоднозначного декодирования
• ${\displaystyle D}$  — количество букв в алфавите кодера (в сообщениях после кодирования)
• ${\displaystyle N}$  — длина сообщений после кодирования

Прямая теорема

Для источника без памяти ${\displaystyle U}$ с энтропией ${\displaystyle H\left(U\right)}$ и любого ${\displaystyle \varepsilon >0}$ существует последовательность множеств однозначного декодирования ${\displaystyle M_{L}}$ мощности ${\displaystyle 2^{L\left({1+\varepsilon }\right)H\left(U\right)}}$ такая, что вероятность множества неоднозначного декодирования стремится к нулю ${\displaystyle P\left({M_{L}^{C}}\right)\to 0}$ при увеличении длины блока ${\displaystyle L\to \infty }$ . Другими словами, сжатие возможно.

Обратная теорема

Пусть задан источник без памяти ${\displaystyle U}$ с энтропией ${\displaystyle H\left(U\right)}$ и любой ${\displaystyle \varepsilon _{1}>0}$ . Для любой последовательности множеств однозначного декодирования ${\displaystyle M_{L}}$ мощности ${\displaystyle 2^{L\left({1-\varepsilon _{1}}\right)H\left(U\right)}}$ вероятность множества неоднозначного декодирования стремится к единице: ${\displaystyle P\left({M_{L}^{C}}\right)\to 1}$ при увеличении длины блока ${\displaystyle L\to \infty }$ . Другими словами, сжатие невозможно.

Литература

• Габидулин Э. М., Пилипчук Н. И. Глава 6. Кодирование с потерями // Лекции по теории информации — МФТИ, 2007. — С. 89–93. — 214 с. — ISBN 978-5-7417-0197-3
  <a href='https://wikidata.org/wiki/Track:Q4130888'></a><a href='https://wikidata.org/wiki/Track:Q27473237'></a><a href='https://wikidata.org/wiki/Track:Q27473383'></a>