Родились сегодня:
lSemperFi


Лидеры рейтинга

ID: 259041

Алексеев Владимир Николаевич

Мастер-Эксперт

391

Россия, пос. Теплоозёрск, ЕАО


ID: 401284

Михаил Александров

Советник

379

Россия, Санкт-Петербург


ID: 401888

puporev

Профессор

215

Россия, Пермский край


ID: 400669

epimkin

Профессионал

111


ID: 405338

vovaromanov.jr

1-й класс

103


ID: 242862

Hunter7007

Мастер-Эксперт

29

Россия, Омск


ID: 137394

Megaloman

Мастер-Эксперт

25

Беларусь, Гомель


8.10.2

13.10.2021

JS: 2.10.2
CSS: 4.6.0
jQuery: 3.6.0
DataForLocalStorage: 2021-10-27 22:16:01-standard


Консультации и решение задач по информатике.

Администратор раздела: Коцюрбенко Алексей Владимирович (Старший модератор)

Консультация онлайн # 108852

Раздел: Информатика
Автор вопроса: lyalya
Дата: 10.11.2007, 20:22 Консультация закрыта
Поступило ответов: 1

Уважаемы эксперты, помогите решить данные задачки. Заранее благодарна.
1.Синтезировать коды Шеннона фано и Хафмена для указанной ниже группы символов (символ/вероятность)
z1/0.03
z2/0.13
z3/0.20
z4/0.17
z5/0.21
z6/0.07
z7/0.08
z8/0.11

2. Произвести преобразование десятичного числа в двоичное и определить для него код Хемминга D:=39

3. Определите значение переданного с использованием кода Хемминга числа. При передаче кода имело место однократная ошибка. 10111100010

Ответ # 193149 от Воробьёв Алексей Викторович
Здравствуйте, lyalya!

1.Синтезировать коды Шеннона фано и Хафмена для указанной ниже группы символов (символ/вероятность)
z1/0.03
z2/0.13
z3/0.20
z4/0.17
z5/0.21
z6/0.07
z7/0.08
z8/0.11
Сначала сортируем в порядке возрастания вероятности:
z1/0.03
z6/0.07
z7/0.08
z8/0.11
z2/0.13
z4/0.17
z3/0.20
z5/0.21
Начинаем суммировать пока не найдём максимально близко к 1/2. z1 + z6 + z7 + z8 + z2 = 0.42, z1 + z6 + z7 + z8 + z9 + z4 = 0.59.
Выбираем первый вариант, т.к. он ближе к половине. Всем символам левой половины присваиваем 1, а правой 0.
Теперь каждую половину пытаемся поделить пооплам как можно точнее:
z1 + z6 + z7 = 0.18, z8 + z2 = 0.24
z4 + z3 = 0.37, z5 = 0.21.
Ко всем символам левых половин добавляем 1, а правых 0.
У нас уже появился первый код: z5 = 00
Продолжаем делить оставшиеся коды:
z1 + z6 = 0.10, z7 = 0.08
z8 = 0.11, z2 = 0.13
z4 = 0.17, z3 = 0.20
Ко всем символам левых половин добавляем 1, а правых 0. Получим, z7 = 110, z8 = 101, z2 = 100, z4 = 011, z3 = 010.
Наконец расщепляем последнюю пару и опять левому добавляем 1: z1 = 1111, а правому 0: z6 = 1110.
Итого:
z1 -> 1111
z2 -> 100
z3 -> 010
z4 -> 011
z5 -> 00
z6 -> 1110
z7 -> 110
z8 -> 101

Учтите, что присвоение 1 и 0 левой или правой части при каждом делении - произвольный выбор и в ответе Вы можете увидеть инвертированные коды.

2. Произвести преобразование десятичного числа в двоичное и определить для него код Хемминга D:=39

39 = 32 + 7 = 32 + 4 + 3 = 32 + 4 + 2 + 1 = 100111.

Для шестибитовых данных нам надо 4 контрольных бита.
Код будет иметь 10 бит выглядеть DDPDDDPDPP, так как биты чётности должны находиться на 1,2,4 и 8 позициях.
DDPDDDPDPP
10P011P1PP Подставим наши данные
-0-0-1-1-P P=0 Для первого бита чётности проверяются биты в нечётных позициях (BIT1 = 1). Сумма должна быть чётной, т.е. в нашем случае P = 0
1--01--1P- P=1 Для второго бита чётности проверяются биты в позициях с BIT2 = 1 (2,3,6,7,10). Сумма должна быть чётной, т.е. в нашем случае P = 1
---011P--- P=0 Для третьего бита чётности проверяются биты в позициях с BIT3 = 1 (4,5,6,7). Сумма должна быть чётной, т.е. в нашем случае P = 0
10P------- P=1 Для четвёртого бита чётности проверяются биты в позициях с BIT4 = 1 (8,9,10). Сумма должна быть чётной, т.е. в нашем случае P = 1
1010110110 Подставим биты чётности в наш код.

Код Хемминга для 39 равен 1010110110.

3. Определите значение переданного с использованием кода Хемминга числа. При передаче кода имело место однократная ошибка. 10111100010

10111100010
1-1-1-0-0-0 P=1 Для первого бита чётности проверяются биты в нечётных позициях (BIT1 = 1).
10--11--01- P=0 Для второго бита чётности проверяются биты в позициях с BIT2 = 1 (2,3,6,7,10).
----1100--- P=0 Для третьего бита чётности проверяются биты в позициях с BIT3 = 1 (4,5,6,7).
1011------- P=1 Для четвёртого бита чётности проверяются биты в позициях с BIT4 = 1 (8,9,10,11).
Код ошибки 1001 = 9 соответсвует позиции ошибочного бита, т.е.
10111100010 принятый код
10011100010 исправленный код (исправлен 9 бит с 1 на 0)
DDDPDDDPDPP маска кода. Биты чётности стоят на 1, 2, 4 и 8 позициях.
100 110 0 переданные данные
1001100 = 64 + 8 + 4 = 76

Воробьёв Алексей Викторович

Посетитель
10.11.2007, 23:27
Мини-форум консультации # 108852
Нет сообщений в мини-форуме
Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.

Лучшие эксперты раздела

Зенченко Константин Николаевич

Старший модератор

Рейтинг: 162

Gluck

9-й класс

Рейтинг: 81

Коцюрбенко Алексей Владимирович

Старший модератор

Рейтинг: 70

Megaloman

Мастер-Эксперт

Рейтинг: 25

CradleA

Мастер-Эксперт

Рейтинг: 1

Лысков Игорь Витальевич

Мастер-Эксперт

Рейтинг: 0