Лидеры рейтинга
Мастер-Эксперт
939
Мастер-Эксперт
466
Академик
392
Мастер-Эксперт
328
Профессионал
190
Профессор
70
Профессор
52
8.1.6
02.01.2021
JS: 2.2.2
CSS: 4.2.0
jQuery: 3.5.1
Консультации и решение задач по алгебре, геометрии, анализу, дискретной математике.
Администратор раздела: Коцюрбенко Алексей Владимирович (Старший модератор)
|
|
Перейти к консультации №: |
|
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Установить при помощи алгоритма Маркова, обладает ли данная схема кодирования свойством взаимной однозначности. Если обладает – обосновать при помощи построенного графа, если не обладает – предъявить неоднозначно декодируемое слово и раскодировать его в алфавите сообщений двумя способами
| a1 | a2 | a3 | a4 | a5 |
| b1b2 | b3b1b2 | b2b2b3 | b2b3b3 | b1b2b2b3 |
Состояние: Консультация закрыта
Здравствуйте, KoreanLamer!
Рассмотрим все возможные разложения кодовых слов:
где в круглых скобках заключены префиксы и суффиксы, а в квадратных - кодовые слова (Λ обозначает пустой префикс, суффикс или кодовое слово). Тогда имеем набор префиксов Λ, b1, b2, b3, b2b2, b2b3, b3b1, b1b2b2 и набор суффиксов Λ, b2, b3, b2b3, b3b3. Построим множество S, содержащее все префиксы, являющиеся одновременно и суффиксами:
Для этого множества построим граф, вершины которого соответствуют элементам множества S, а каждое ребро связывает пару вершин, являющихся префиксом и суффиксом одного и того же кодового слова. В данном случае таких слов будет четыре: (Λ)b1b2(b2b3), (b2b3)Λ(b3), (b3)b1b2(Λ) и (b2)Λ(b2b3).
При этом в графе имеется ориентированный замкнутый цикл, содержащий вершину Λ, которому соответствует кодовая последовательность b1b2b2b3b3b1b2, декодируемая двумя способами: (b1b2)(b2b3b3)(b1b2) → a1a4a1 и (b1b2)(b2b3)(b3b1b2) → a5a2. Следовательно, данная схема кодирования не обладает свойством взаимной однозначности.
|
|
Консультировал: Коцюрбенко Алексей Владимирович (Старший модератор) Дата отправки: 16.12.2020, 18:40
5
Здравствуйте, большое спасибо за помощь ----- Дата оценки: 17.12.2020, 15:48 |
Рейтинг ответа:
0 Сообщение модераторам Отправлять сообщения |
|
Коцюрбенко Алексей Владимирович
Старший модератор ID: 312929
0
|
KoreanLamer: У Вас в условии задачи одно и тоже кодовое слово b1b2b2b3 повторяется дважды - для a4 и a5. Проверьте, всё ли правильно? |
|
Посетитель ID: 403724
0
|
Коцюрбенко Алексей Владимирович: Да, ошибся в написании условия |
Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.
