Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 199800
07.12.2020, 08:53
0.00 руб.
16.12.2020, 16:23
0 3 1
Образование
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Установить при помощи алгоритма Маркова, обладает ли данная схема кодирования свойством взаимной однозначности. Если обладает – обосновать при помощи построенного графа, если не обладает – предъявить неоднозначно декодируемое слово и раскодировать его в алфавите сообщений двумя способами
[table]
[row][col]a1[/col][col]a2[/col][col]a3[/col][col]a4[/col][col]a5[/col][/row]
[row][col]b1b2[/col][col]b3b1b2[/col][col]b2b2b3[/col][col]b2b3b3[/col][col]b1b2b2b3[/col][/row]
[/table]

Обсуждение

давно
Коцюрбенко Алексей Владимирович
Старший Модератор
312929
1973
12.12.2020, 06:51
общий
Адресаты:
У Вас в условии задачи одно и тоже кодовое слово b[sub]1[/sub]b[sub]2[/sub]b[sub]2[/sub]b[sub]3[/sub] повторяется дважды - для a[sub]4[/sub] и a[sub]5[/sub]. Проверьте, всё ли правильно?
давно
KoreanLamer
Посетитель
403724
28
12.12.2020, 14:02
общий
Адресаты:
Да, ошибся в написании условия
a1| a2 |a3 |a4 |a5
b1b2| b3b1b2 |b2b2b3 |b2b3b3 |b1b2b2b|
давно
Коцюрбенко Алексей Владимирович
Старший Модератор
312929
1973
16.12.2020, 18:40
общий
это ответ
Здравствуйте, KoreanLamer!

Рассмотрим все возможные разложения кодовых слов:





где в круглых скобках заключены префиксы и суффиксы, а в квадратных - кодовые слова ([$923$] обозначает пустой префикс, суффикс или кодовое слово). Тогда имеем набор префиксов [$923$], b[sub]1[/sub], b[sub]2[/sub], b[sub]3[/sub], b[sub]2[/sub]b[sub]2[/sub], b[sub]2[/sub]b[sub]3[/sub], b[sub]3[/sub]b[sub]1[/sub], b[sub]1[/sub]b[sub]2[/sub]b[sub]2[/sub] и набор суффиксов [$923$], b[sub]2[/sub], b[sub]3[/sub], b[sub]2[/sub]b[sub]3[/sub], b[sub]3[/sub]b[sub]3[/sub]. Построим множество S, содержащее все префиксы, являющиеся одновременно и суффиксами:

Для этого множества построим граф, вершины которого соответствуют элементам множества S, а каждое ребро связывает пару вершин, являющихся префиксом и суффиксом одного и того же кодового слова. В данном случае таких слов будет четыре: ([$923$])b[sub]1[/sub]b[sub]2[/sub](b[sub]2[/sub]b[sub]3[/sub]), (b[sub]2[/sub]b[sub]3[/sub])[$923$](b[sub]3[/sub]), (b[sub]3[/sub])b[sub]1[/sub]b[sub]2[/sub]([$923$]) и (b[sub]2[/sub])[$923$](b[sub]2[/sub]b[sub]3[/sub]).

При этом в графе имеется ориентированный замкнутый цикл, содержащий вершину [$923$], которому соответствует кодовая последовательность b[sub]1[/sub]b[sub]2[/sub]b[sub]2[/sub]b[sub]3[/sub]b[sub]3[/sub]b[sub]1[/sub]b[sub]2[/sub], декодируемая двумя способами: (b[sub]1[/sub]b[sub]2[/sub])(b[sub]2[/sub]b[sub]3[/sub]b[sub]3[/sub])(b[sub]1[/sub]b[sub]2[/sub]) [$8594$] a[sub]1[/sub]a[sub]4[/sub]a[sub]1[/sub] и (b[sub]1[/sub]b[sub]2[/sub])(b[sub]2[/sub]b[sub]3[/sub])(b[sub]3[/sub]b[sub]1[/sub]b[sub]2[/sub]) [$8594$] a[sub]5[/sub]a[sub]2[/sub]. Следовательно, данная схема кодирования не обладает свойством взаимной однозначности.
5
Здравствуйте, большое спасибо за помощь
Форма ответа