Покажите с помощью дерева что кодовая таблица из примера 2 удовлетворяет?

8 ответов на вопрос “Покажите с помощью дерева что кодовая таблица из примера 2 удовлетворяет?”

  1. at0ne Ответить

    Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 10 классы | Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, сокращенный курс, 2 часа в неделю) | Кодирование и декодирование
    Урок 5
    Кодирование и декодирование
    §5. Язык и алфавит. §6. Кодирование

    Содержание урока

    §5. Язык и алфавит
    §6. Кодирование
    Кодирование
    Двоичное кодирование
    Вопросы и задания
    Задачи
    Декодирование
    Вопросы и задания
    Задачи

    §6. Кодирование

    Задачи

    1. Расшифруйте сообщение, записанное с помощью кода Морзе, которое используется как международный сигнал бедствия:
    .
    2. Покажите с помощью дерева, что кодовая таблица из примера 2 удовлетворяет «обратному» условию Фано.
    3. Для кодирования сообщения используется таблица

    Найдите все способы декодирования сообщения 1111001011.
    4. Для кодирования сообщения используется таблица

    Найдите все способы декодирования сообщения 1111001001100.
    5. Для кодирования сообщения используется таблица

    Найдите все способы декодирования сообщения 1111001010.
    6. Для кодирования сообщения используется таблица

    Найдите все способы декодирования сообщения 01110011.
    7. Для кодирования сообщения используется таблица

    Декодируйте сообщение 0110100011000.
    8. Для кодирования сообщения, состоящего только из букв А, В, С, D и Е, используется неравномерный двоичный код:

    Какие из сообщений были переданы без ошибок:
    1) 110000010011110
    2) 110000011011110
    3) 110001001001110
    4) 110000001011110
    *9. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 0, Б = 10, В = 110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
    *10. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 0, Б = 100, В = 101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
    *11. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 01, Б = 1, В = 001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
    *12. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = О, Б = 100, В =110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
    *13. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 00, Б = 11, В = 100 и Г = 10. Определите, допускает ли такой код однозначное декодирование сообщения. Выполняется ли для него условие Фано?
    Следующая страница §5. Язык и алфавит
    Cкачать материалы урока

  2. apofiz Ответить

    ✎ 1 вариант решения основан на логических умозаключениях:
    Найдём самые короткие возможные кодовые слова для всех букв.
    Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
    Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
    Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
    Суммарная длина всех четырёх кодовых слов равна:
    (Н)1 + (К)2 + (Л)3 + (М)3 = 9
    ✎ 2 вариант решения:
    Будем использовать дерево. Влево откладываем 0, вправо — 1:

    Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
    (Н) -> 0 -> 1 символ
    (К) -> 10 -> 2 символа
    (Л) -> 110 -> 3 символа
    (М) -> 111 -> 3 символа
    Суммарная длина всех четырёх кодовых слов равна:
    (Н)1 + (К)2 + (Л)3 + (М)3 = 9
    Ответ: 9

  3. maksim_vet. Ответить

    Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 10 классы | Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, базовый уровень) | Кодирование и декодирование
    Урок 4
    Кодирование и декодирование
    §5. Язык и алфавит. §6. Кодирование

    Содержание урока

    §5. Язык и алфавит
    §6. Кодирование
    Кодирование
    Двоичное кодирование
    Вопросы и задания
    Задачи
    Декодирование
    Вопросы и задания
    Задачи

    §6. Кодирование

    Задачи

    1. Расшифруйте сообщение, записанное с помощью кода Морзе, которое используется как международный сигнал бедствия:
    .
    2. Покажите с помощью дерева, что кодовая таблица из примера 2 удовлетворяет «обратному» условию Фано.
    3. Для кодирования сообщения используется таблица

    Найдите все способы декодирования сообщения 1111001011.
    4. Для кодирования сообщения используется таблица

    Найдите все способы декодирования сообщения 1111001001100.
    5. Для кодирования сообщения используется таблица

    Найдите все способы декодирования сообщения 1111001010.
    6. Для кодирования сообщения используется таблица

    Найдите все способы декодирования сообщения 01110011.
    7. Для кодирования сообщения используется таблица

    Декодируйте сообщение 0110100011000.
    8. Для кодирования сообщения, состоящего только из букв А, В, С, D и Е, используется неравномерный двоичный код:

    Какие из сообщений были переданы без ошибок:
    1) 110000010011110
    2) 110000011011110
    3) 110001001001110
    4) 110000001011110
    *9. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 0, Б = 10, В = 110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
    *10. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 0, Б = 100, В = 101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
    *11. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 01, Б = 1, В = 001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
    *12. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = О, Б = 100, В =110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
    *13. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 00, Б = 11, В = 100 и Г = 10. Определите, допускает ли такой код однозначное декодирование сообщения. Выполняется ли для него условие Фано?
    Следующая страница §5. Язык и алфавит
    Cкачать материалы урока

  4. rust1973 Ответить

    Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 10 классы | Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углубленный курс, 4 часа в неделю) | Кодирование и декодирование
    Уроки 7 – 8
    Кодирование и декодирование
    §5. Язык и алфавит. §6. Кодирование

    Содержание урока

    §5. Язык и алфавит
    §6. Кодирование
    Кодирование
    Двоичное кодирование
    Вопросы и задания
    Задачи
    Декодирование
    Вопросы и задания
    Задачи

    §6. Кодирование

    Задачи

    1. Расшифруйте сообщение, записанное с помощью кода Морзе, которое используется как международный сигнал бедствия:
    .
    2. Покажите с помощью дерева, что кодовая таблица из примера 2 удовлетворяет «обратному» условию Фано.
    3. Для кодирования сообщения используется таблица

    Найдите все способы декодирования сообщения 1111001011.
    4. Для кодирования сообщения используется таблица

    Найдите все способы декодирования сообщения 1111001001100.
    5. Для кодирования сообщения используется таблица

    Найдите все способы декодирования сообщения 1111001010.
    6. Для кодирования сообщения используется таблица

    Найдите все способы декодирования сообщения 01110011.
    7. Для кодирования сообщения используется таблица

    Декодируйте сообщение 0110100011000.
    8. Для кодирования сообщения, состоящего только из букв А, В, С, D и Е, используется неравномерный двоичный код:

    Какие из сообщений были переданы без ошибок:
    1) 110000010011110
    2) 110000011011110
    3) 110001001001110
    4) 110000001011110
    *9. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 0, Б = 10, В = 110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
    *10. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 0, Б = 100, В = 101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
    *11. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 01, Б = 1, В = 001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
    *12. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = О, Б = 100, В =110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
    *13. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 00, Б = 11, В = 100 и Г = 10. Определите, допускает ли такой код однозначное декодирование сообщения. Выполняется ли для него условие Фано?
    Следующая страница §5. Язык и алфавит
    Cкачать материалы урока

  5. SeverРЄ Ответить

    Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.
    Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент (корень), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями. Каждый элемент бинарного дерева называется узлом. Связи между узлами дерева называются его ветвями.
    Способ представления бинарного дерева:

    A — корень дерева
    В — корень левого поддерева
    С — корень правого поддерева
    Корень дерева расположен на уровне с минимальным значением.
    Узел D, который находится непосредственно под узлом B, называется потомком B. Если D находится на уровне i, то B – на уровне i-1. Узел B называется предком D.
    Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой.
    Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.
    Остальные элементы – внутренние узлы (узлы ветвления).
    Число потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева.
    Число ветвей, которое нужно пройти от корня к узлу x, называется длиной пути к x. Корень имеет длину пути равную 0; узел на уровне i имеет длину пути равную i.
    Бинарное дерево применяется в тех случаях, когда в каждой точке вычислительного процесса должно быть принято одно из двух возможных решений.
    Имеется много задач, которые можно выполнять на дереве.
    Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.
    Если рассматривать задачу как единый последовательный процесс, то отдельные узлы посещаются в определенном порядке и могут считаться расположенными линейно.
    Способы обхода дерева
    Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.

    Существует три способа обхода дерева:
    Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
    Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
    Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.
    Реализация дерева
    Узел дерева можно описать как структуру:

  6. binnijs13 Ответить

    Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 10 классы | Практические работы для 10 класса (по учебнику К.Ю. Полякова, Е.А. Еремина) | Практическая работа № 5 «Декодирование»
    Практическая работа № 5
    «Декодирование»
    1. Для кодирования сообщения используется таблица1
    1 Выберите вариант по указанию учителя.
    Вариант 1:

    Сообщение: 0101110010110 (Ответы: ГБАДДА, ДДБВДА)
    Вариант 2:

    Сообщение: 01011100101101 (Ответы: ААВААД, ААВГБА)
    Вариант 3:

    Сообщение: 0010001001001 (Ответы: БВГББ, ВДГББ)
    Вариант 4:

    Сообщение: 0100001101000010 (Ответы: БАДГАБ, ГАВГАБ)
    Вариант 5:

    Сообщение: 1010000011011000 (Ответы: ААГВВГ, АБГДВГ)
    Используя средства текстового процессора, изобразите двоичное дерево, соответствующее этому коду.
    2. Выполняется ли для этой кодовой таблицы условие Фано? Обратное условие Фано? Почему?
    Ответ:

    3. Найдите все способы декодирования сообщение, записанное под таблицей:
    Ответ:

    Проверьте свой ответ с помощью программы decode.
    4. Замените код одного символа так, чтобы выполнилось условие Фано (или обратное условие Фано). Выделите зеленым фоном ячейку таблицы с измененным кодом символа.

    5. Сократите код одного символа в таблице, полученной в п. 4 так, чтобы условие Фано (или обратное условие Фано) по-прежнему выполнялось. Выделите фиолетовым фоном ячейку таблицы с измененным кодом символа.

  7. LOSTRANGER Ответить

    Выделим в дереве какую-нибудь одну вершину, которую назовем корнем. Полученное дерево с выделенной вершиной называется корневым.
    Для задания (с точностью до изоморфизма) корневых деревьев используют код из 0 и 1, который мы определим индуктивно.
    Определение. Кодом корневого дерева с одним ребром является . Пусть деревья и с корнями a и b соответственно (см. рис.) имеют коды и . Тогда кодом дерева с корнем с является код , а кодом дерева с корнем – код .
    Пример 1.Написать код дерева, изображенного на рисунке.
    Итак, код дерева – .
    Справедливо следующее утверждение: для того, чтобы последовательность нулей и единиц являлась кодом некоторого дерева необходимо и достаточно, чтобы число нулей и единиц в этой последовательности было одинаковым, причем в любом начальном отрезке последовательности количество нулей было не меньше количества единиц.
    Чтобы построить корневое дерево по коду из нулей и единиц, нужно разбить последовательность на пары 0 и 1, следуя правилу: первая попавшаяся в коде единица образует пару с предшествующим нулем; каждая следующая единица образует пару с ближайшим слева неиспользованным нулем. Если образованные таким образом пары пометить снизу кода фигурными скобками, то каждая такая скобка будет соответствовать ребру графа.
    Пример 2. Построить дерево по коду .
    Для задания помеченных деревьев, т.е. деревьев, вершины которых занумерованы, используют код из натуральных чисел.
    Пусть дано помеченное дерево. Чтобы построить его код из натуральных чисел действуем следующим образом. Находим висячую вершину с наименьшим номером. Записываем номер смежной с ней вершины (это начало кода), после чего удаляем эту висячую вершину вместе с инцидентным ей ребром. Для полученного в результате данной операции дерева находим висячую вершину с наименьшим номером, записываем номер смежной с ней вершины (это продолжение кода), после чего удаляем эту висячую вершину вместе с инцидентным ей ребром. Так поступаем до тех пор, пока не останется последнее ребро.
    Заметим, что длина кода из натуральных чисел на единицу меньше числа ребер и на две единицы меньше числа вершин данного дерева.
    Пример 3.На рисунке изображено помеченное дерево. Его код .
    Построение дерева по коду из натуральных чисел рассмотрим на примере кода . Прежде всего, заметим, что дерево, которое нам предстоит построить, имеет 8 вершин.
    Будем преобразовывать последовательность 224466, действуя по следующей схеме. Вместо первого числа запишем наименьшее натуральное число, которое в этой последовательности не встречается, т.е. 1; получим последовательность 124466. Вместо второго числа в новой последовательности запишем наименьшее, не встречающееся в ней, т.е. 3; получим последовательность 134466, и т.д. Действуем так до тех пор, пока все числа в исходной последовательности не будут заменены. Расположим все последовательности друг под другом; под последней из них запишем код дерева. Выпишем пары вершин, записанные друг под другом в последних двух строчках: (12), (32), (24), (54), (46), (76). Каждая такая пара – это пара концов одного из ребер дерева. Этот список дополняем парой вершин, отсутствующих в предпоследней строчке, т.е. парой (6,8). Теперь строим дерево: отмечаем на плоскости точки – вершины дерева и соединяем их ребрами согласно списку (см. рисунок к примеру 3).

  8. volhv75doc Ответить

    Вообще говоря, древовидными кодами могут быть названы произвольные коды, имеющие древовидную структуру, подобную показанной на фиг. 6.2 или фиг. 6.4. При таком широком определении древовидных кодов коды, порождаемые сверточными кодерами, являются лишь подмножеством множества древовидных кодов.

    6.1.2. Принцип последовательного декодирования

    Предположим, что задан некоторый древовидный код и попытаемся по принятой последовательности определить передававшуюся последовательность. Для этого сначала будем передвигаться поочередно вдоль каждого пути кодового дерева, сравнивая принятую последовательность с последовательностью,
    соответствующей пути, по которому мы движемся. Если при этом удается обнаружить некоторый путь, которому соответствует последовательность, почти совпадающая с принятой последовательностью, то естественно считать, что эта последовательность и передавалась. Метод декодирования, предложенный Возенкрафтом, предусматривает вначале поиск на кодовом дереве пути из ребра, соответствующая которому кодовая последовательность находится на каком-то определенном расстоянии от переданной последовательности, и далее декодирование первого информационного символа (первым переданным информационным символом считается первый информационный символ первого ребра найденного пути).

    Фиг. 6.4. Пример древовидного кода скоростью
    Поскольку далее декодирование второго и последующих информационных символов осуществляется точно так же, как и первого информационного символа, то этот алгоритм был назван алгоритмом последовательного декодирования.
    Одним из критериев близости пути на кодовом дереве к принятой последовательности является расстояние Хэмминга между ними; если расстояние Хэмминга между последовательностями длины не превышает определенный порог то последовательности можно считать совпадающими. В случае двоичного симметричного канала порог выбирается таким образом, чтобы вероятность того, что расстояние Хэмминга между
    передававшейся и принятой последовательностями было больше чем не превышала величины где некоторая заданная постоянная. При этом вероятность того, что расстояние Хэмминга между правильным путем дерева и принятой последовательностью больше чем при больших оказывается чрезвычайно малой.
    Предположим, что этот метод декодирования используется в двоичном симметричном канале с вероятностью перехода Тогда, поскольку в этом случае в канале ошибки в различных символах возникают независимо с вероятностью перехода то расстояние Хэмминга, вычисляемое вдоль правильного пути, как показано на фиг. 6.5, почти всегда будет возрастать со скоростью вместе с числом обработанных символов.

    Фиг. 6.5. Число декодированных символов и расстояние Хэмминга для последовательного декодера.
    В тоже время расстояние Хэмминга, вычисляемое вдоль любого другого пути кодового дерева, будет возрастать со скоростью поскольку различные пути кодового дерева отличаются друг от друга приблизительно в половине символов. Таким образом, расстояния Хэмминга, вычисленные вдоль правильного и ошибочного пути кодового дерева, оказываются различными. При этом, даже если на начальном этапе декодирования путь кодового дерева был выбран неправильно, то через некоторое время ошибка будет обнаружена, поиск правильного пути будет продолжен и в конце концов правильный путь будет найден.
    Этот алгоритм последовательного декодирования был обобщен Рейффеном [6] на случай произвольного дискретного канала без памяти. Обобщение было сделано путем замены расстояния Хэмминга на другую функцию, являющуюся обобщением расстояния Хэмминга.
    Дискретный канал без памяти с входным алфавитом из К символов и выходным алфавитом из символов определяется совокупностью переходных вероятностей
    где -вероятность того, что при передаче входного символа на выходе канала будет принят символ Расстояние между путем кодового дерева содержащим символов, и принятой последовательностью определяется равенством

    где

    Величина представляет собой вероятность появления на выходе канала символа и, в случае, если на входе канала символ появляется с вероятностью Расстояние, определяемое формулой (6.1), является количеством информации между последовательностями и в случае, когда пары статистически независимы и символы на входе канала появляются с вероятностями Если правую часть (6.1) представить в виде логарифма произведения, то можно заметить, что величина определяется вероятностью которая в случае двоичного симметричного канала является монотонно убывающей функцией расстояния Хэмминга между последовательностями Следовательно, в случае двоичного симметричного канала введенное выше расстояние эквивалентно расстоянию Хэмминга. Однако поскольку в случае произвольного дискретного канала без памяти введенная функция не может быть интерпретирована в терминах расстояния Хэмминга, то будем называть ее в дальнейшем ценой пути.
    Алгоритм последовательного декодирования, предложенный Фано [23], предусматривает вычисление и использование при декодировании наряду с ценой пути также некоторых порогов. Этот алгоритм является алгоритмом того же типа, что и алгоритм Возенкрафта, но если среднее число операций, необходимых для декодирования одного символа, в случае использования алгоритма Возенкрафта при скоростях передачи, меньших определенной скорости растет как небольшая степень кодового ограничения, то для алгоритма Фано это среднее число в тех же условиях не зависит от длины кодового ограничения. Это упрощает анализ алгоритма декодирования Фано. Кроме того, достоинством алгоритма Фано является также то, что он допускает более простую техническую реализацию, чем алгоритм Возенкрафта. В силу этого приблизительно с 1964 г. исследования алгоритмов последовательного декодирования в значительной степени были связаны с исследованием алгоритма
    Фано. По тем же причинам алгоритм Фано будет детально рассмотрен в данной книге. В последние годы независимо Джели-нек [7] и Зигангиров [8] предложили алгоритм последовательного декодирования, часто называемый стек-алгоритмом. Нельзя сказать, что этот алгоритм во всех отношениях лучше алгоритма Фано, но так как его описание значительно проще описания алгоритма Фано и поскольку он хорошо иллюстрирует принцип последовательного декодирования, то этот алгоритм также будет кратко рассмотрен ниже.

Добавить ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *