Теорія інформації та кодування в задачах
43


немарковського джерела з алфавітом  ймовірності появи символів є таким:

Процес побудови коду ілюструється таблицею 2.2. Упорядковуємо символи джерела по незростанню значень ймовірностей їх появи, тобто ймовірність появи символу, який знаходиться на деякій позиції другої колонки таблиці, не повинна перевищувати ймовірність появи символу, що розташований вище.

Таблиця  2.2

p(xi)

xi

Кодова  комбінація

li

Номер поділу

1/2

x6

1

1

1

2

3

5

4

6

1/4

x1

01

2

1/8

x7

001

3

1/32

x2

00011

5

1/32

x3

00010

5

1/32

x4

00001

5

1/32

x5

00000

5

Можна упорядкувати символи також по незменшенню. Далі поділяємо множину упорядкованих символів горизонтальним відрізком на дві підмножини таким чином, щоб сума ймовірностей появи символів, розташованих над відрізком, була якомога ближче до суми ймовірностей появи символів, розташованих під відрізком. В даному випадку цю умову можна виконати ідеально, якщо відрізок провести між  та :

. Це буде перше розділення, що фіксується в п’ятій колонці таблиці 2.2. Симво