Question

2. Побудувати двійковий код ОНК Шеннона-Фано та для ансаблю повідомлень з імовірностями 0,1;0,12;0,14;0,06;0,01;0,09;0,12;0,03;0,1;0,02;0,02;0,01;0,14;0,04

Answer 1

Для побудови двійкового коду ОНК Шеннона-Фано потрібно виконати наступні кроки:

1. Відсортувати символи в порядку спадання за їхмівірностями:

0,14; 0,12; 0,12; 0,1; 0,1; 0,09; 0,06; 0,04; 0,03; 0,02; 0,02; 0,01; 0,01

2. Розділити вихідний набір на дві підгрупи з приблизно однаковими сумарними імовірностями.

Група 1: 0,14; 0,12; 0,12; 0,1; 0,1; 0,09
Група 2: 0,06; 0,04; 0,03; 0,02; 0,02; 0,01; 0,01

3. Присвоїти першій групі бітовий префікс "0", а другій групі - "1".

Група 1: 0,14; 0,12; 0,12; 0,1; 0,1; 0,09
Група 2: 0,06; 0,04; 0,03; 0,02; 0,02; 0,01; 0,01

4. Рекурсивно повторити кроки 2 і 3 для кожної підгрупи до тих пір, поки не буде можливо більше поділити на підгрупи.

Група 1:
0,14: 0
0,12: 10
0,12: 11
0,1: 100
0,1: 101
0,09: 110

Група 2:
0,06: 11100
0,04: 11101
0,03: 11110
0,02: 111110
0,02: 111111
0,01: 1111010
0,01: 1111011

Таким чином, отримуємо двійковий код ОНК Шеннона-Фано для даного набору імовірностей:

0,14: 0
0,12: 10
0,12: 11
0,1: 100
0,1: 101
0,09: 110
0,06: 11100
0,04: 11101
0,03: 11110
0,02: 111110
0,02: 111111
0,01: 1111010
0,01: 1111011