Теорема Шеннона о кодировании исходного кода

• Определение и применение энтропии

  • Энтропия — мера неопределенности информации, измеряется в битах. 
  • Используется для оценки эффективности сжатия данных. 

• Кодирование источника

  • Кодирование источника — преобразование символов в биты для восстановления исходного значения. 
  • Теорема Шеннона утверждает, что для энтропии источника H(X) и скорости передачи n(H(X) + ε), где ε > 0, существует кодер, который восстанавливает исходные данные с вероятностью не менее 1 — ε. 

• Теорема о кодировании источника для кодов символов

  • Для случайного источника X и кода f от Σ∗1 до Σ∗2, существует кодер, который кодирует X в n(H(X) + ε) битов с вероятностью не менее 1 — ε. 
  • Минимальное ожидаемое количество битов для кодирования зависит от энтропии источника и размера алфавита. 

• Кодирование нестационарных источников

  • Для нестационарных источников с дискретным временем, типичные наборы Aen могут быть определены для обеспечения вероятности не менее 1 — δ. 
  • При достаточно большом n, мощность типичного набора меньше, чем 2n(Hn(X) + ε), что позволяет эффективно кодировать данные с высокой вероятностью.