Skip to main content
LibreTexts - Ukrayinska

5.9: Ефективне кодування джерела

  1. Last updated
  2. Save as PDF
  • Page ID
    29800

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Якщо джерело має\(n\) можливі символи, то код фіксованої довжини для нього вимагатиме\(\log_2(n)\) (або наступного вищого цілого числа) бітів на символ. Середня інформація на символ\(I\) не може бути більшою, ніж це, але може бути меншою, якщо символи мають різні ймовірності. Чи можна закодувати потік символів з такого джерела з меншою кількістю бітів в середньому, використовуючи код змінної довжини з меншою кількістю бітів для більш ймовірних символів і більшою кількістю бітів для менш ймовірних символів?

    Безумовно. Код Морзе є прикладом коду змінної довжини, який робить це досить добре. Існує загальна процедура побудови кодів такого роду, які є дуже ефективними (насправді, вони вимагають в середньому менше, ніж\(I\) + 1 біт на символ, навіть якщо\(I\) він значно нижче\(\log_2(n)\). Коди називаються кодами Хаффмана після випускника MIT Девіда Хаффмана (1925 - 1999), і вони широко використовуються в системах зв'язку. Див. Розділ 5.10.