Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Построение эффективных кодов методом Хаффмена и кодирование дискретного сигнала






    Задание к работе: выполнить кодирование исходного текста методом Хаффмена. Частоты символов алфавита заимствовать из задания 7.

    Решение задачи:

    1) для построения кода выполним следующие шаги:

    q используем в качестве исходных данных графы 1 и 2 таблицы 7.2, расположив их в графах 1 и 2 таблицы 8.1,

    q выполним последовательное объединение частот в соответствии с методом Хаффмена (графа 3 таблицы 8.1, красным цветом показана объединенная частота),


    Таблица 8.1

    Символ алфавита Частота символа fi Этапы объединения частот
         
    I II III IV V VI VII VIII IX X XI XII
    в 0, 2 0, 2 0, 2 0, 2 0, 2 0, 2 0, 2 0, 2 0, 25 0, 35 0, 4 0, 6  
    и 0, 15 0, 15 0, 15 0, 15 0, 15 0, 15 0, 2 0, 2 0, 2 0, 25 0, 35 0, 4 -
    а 0, 1 0, 1 0, 1 0, 1 0, 1 0, 15 0, 15 0, 2 0, 2 0, 2 0, 25 - -
    е 0, 1 0, 1 0, 1 0, 1 0, 1 0, 1 0, 15 0, 15 0, 2 0, 2 - - -
    л 0, 05 0, 1 0, 1 0, 1 0, 1 0, 1 0, 1 0, 15 0, 15 - - - -
    н 0, 05 0, 05 0, 1 0, 1 0, 1 0, 1 0, 1 0, 1 - - - - -
    о 0, 05 0, 05 0, 05 0, 1 0, 1 0, 1 0, 1 - - - - - -
    п 0, 05 0, 05 0, 05 0, 05 0, 1 0, 1 - - - - - - -
    р 0, 05 0, 05 0, 05 0, 05 0, 05 - - - - - - - -
    с 0, 05 0, 05 0, 05 0, 05 - - - - - - - - -
    т 0, 05 0, 05 0, 05 - - - - - - - - - -
    ч 0, 05 0, 05 - - - - - - - - - - -
    ь 0, 05 - - - - - - - - - - - -

     

    q построим бинарное дерево и закодируем его ребра (рисунок 8.1, коды ребер заключены в окружности),

     

           
       
     


    0, 6 0, 4

     

     

    0, 35 0, 25 0, 2(в) 0, 2

     
     


    0, 2 0, 15(и) 0, 15 0, 1(а) 0, 1 0, 1

    0, 1(е) 0, 1 0, 1 0, 05(л) 0, 05(с) 0, 05(т) 0, 05(п) 0, 05(р)

     

    0, 05(ч) 0, 05(ь) 0, 05(н) 0, 05(о)

     

    Рисунок 8.1. Кодовое бинарное дерево для задания

    q начиная с корня дерева, «соберем» коды ребер и сформируем коды символов исходного алфавита (таблица 8.2):


     

    Таблица 8.2

    Символ алфавита в и а е л н о п р с т ч ь
    Код                          

     

    2) для кодирования исходного текста используем таблицу 8.2. Имеем (для простоты закодируем отдельно фамилию, имя и отчество):

    петров 0001 1111 0010 0000 10110 01

    иван 110 01 100 10111

    васильевич 01 100 0011 110 1010 11100 1111 01 110 11101






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.