Кодування Шеннона, назване на честь творця, Клода Шеннона, — безвтратна техніка стиснення даних для побудови префіксного коду, яка ґрунтується на наборі символів і їх імовірностях (розрахованих або виміряних). Кодування Шеннона субоптимальне в тому сенсі, що не досягає найменшої можливої очікуваної довжини кодового слова, подібно до кодування Гаффмана, і не краще але інколи рівне кодуванню Шеннона — Фано.
Метод був першим у своєму роді, цю методику використано під час доведення в його статті 1948 року «Математична теорія зв'язку».
Цей метод кодування породив галузь теорії інформації, і без нього світ не мав би жодного з багатьох наступників; наприклад кодування Шеннона — Фано, кодування Гаффмана або арифметичного кодування. Значна частина нашого повсякденного життя пов'язана з цифровими даними, і це було б неможливим без кодування Шеннона та постійної еволюції його методів.
У кодуванні Шеннона символи розміщуються в порядку від найбільш імовірних до найменш імовірних. Їм призначаються коди з перших цифр двійкового розкладу кумулятивної ймовірності . Тут позначає функцію стеля, яка округлює до найближчого цілого значення, більшого або рівного .
Приклад У таблиці наведено приклад кодування методом Шеннона. За підсумковим кодом можна помітити, що він є менш оптимальним, ніж алгоритм Шеннона — Фано.
Перший крок — підрахунок імовірностей кожного символу. Потім рахується число для кожної ймовірності. Наприклад, для воно дорівнює 3 ( — найменший степінь двійки —3, отже ). Після цього підраховується сума ймовірностей від 0 до i—1 і переводиться в двійкову форму. Потім дробова частина усікається зліва до знаків. aip (ai)liСума pnвід n=0 до i—1Сума за p(ai) binпідсумковий кодa 10.3620.00.000000a 20.1830.360.0100010a 30.1830.540.1000100a 40.1240.720.10111011a 50.0940.840.11011101a 60.0740.930.11101110
Примітки