Методичка по ТИиК

2) переместительный:

а+ b = b+ а;

а* b = b* а;

3) распределительный:

Наименьшим элементом алгебры логики является 0, наибольшим

ин в е р с и и ) , обозначаемая чертой над элементом.

По определению:

Справедливы, например, такие соотношения:

Логический синтез вычислительных схем

Логические блоки, в соответствии с международным стандартом:

20

схема ИЛИ, реализующая операцию логического сложения;

схема И, реализующая операцию логического умножения;

схема НЕ, реализующая операцию инверсии ;

Схема И-НЕ, реализующая операцию инвертора и отрицание результата схемы И.

Задания для всех вариантов:

1.Дано логическое выражение в результате преобразования, получим какое выражение?

2.Приведена таблица истинности:

В заголовке третьего столбца таблицы должно быть указано, какое логическое выражение?

3.Из данных логических функций тождественно ложной является …

Аи не А или В

Аи не В или не А

Аи не В и не А

Аи не В или А

4.Даны высказывания А = «Я люблю учиться» и В= «сдавать экзамены». Конъюнкцией этих высказываний будет…

5.С помощью таблицы истинности получите результат логической функции F=A√B

21

возможно при следующей комбинации входных параметров A, B, C

8. Определите на входе логической схемы при F=1 возможна какая комбинация сигналов (A, B, C, D)?

9.Логическая функция A√B√¬(A√B) после преобразования примет вид.

10.Если на входы логической схемы

22

Лабораторная работа 6

Рассмотрим некоторые коды, позволяющие сделать передачу информации более эффективной, что достигается путем сжатия сообщения. Начнем с кода Шеннона–Фано. Алгоритм состоит в следующем: буквы исходного алфавита сообщения выписываются в столбец в порядке убывания их вероятностей; производится разбиение на две группы с равной по возможности суммарной вероятностью, всем буквам верхней группы в качестве первого символа кодовой комбинации приписывается «1», а нижней

– «0»; затем производятся следующие разбиения до тех пор, пока в каждой подгруппе не останется одна буква (при каждом разбиении появляется новый символ кодовой комбинации по правилам, изложенным выше).

Эффективность кода рассчитывается следующим образом

причем в случае двоичного алфавита формула имеет вид

где средняя длина кодовой комбинации равна

n(zi) – число символов в кодовой комбинации. Эффективность является безразмерной величиной и всегда меньше либо равна 1, т.е. æ ≤ 1. Чем ближе этот показатель к единице, тем эффективнее код.

23

Пример 4. Проведем кодирование методом Шеннона–Фано и рассчитаем характеристики кода. Пусть исходный алфавит состоит из восьми букв и заданы их вероятности. Проведем разбиения по алгоритму Шеннона– Фано и составим кодовые комбинации.

Рассчитаем энтропию по формуле (6)

H 0,25 log 2 0,25 0,20 log 2 0,20 0,15 log 2 0,15 3 0,10 log 2 0,100,06 log 2 0,06 0,04 log 2 0,04 2,79 (бит).

Рассчитаем среднюю длину кодовой комбинации по формуле (14)

l 0,25 2 0,20 2 0,15 3 0,10 3 0,10 4

ср

0,10 4 0,06 4 0,04 4 2,85.

Эффективность кода, согласно (13), равна

æ 2,792,85 0,98.

Эффективность кодирования можно увеличить, если проводить кодирование блоков, состоящих из нескольких букв алфавита.

Пример 5. Проведем блоковое кодирование по методу Шеннона–Фано. Пусть алфавит состоит из двух независимых букв с заданными вероятностями p(z1)=0,8 и p(z2)=0,2.

Рассчитаем энтропию

H (Z ) 0,8log 0,8 0,2log 0,2 0,72 (бит).

Очевидно, что при кодировании по одной букве lср=1 и æ1=0,72.

Проведем кодирование блоков, состоящих из двух букв. Ниже приведена таблица с разбиениями и соответствующими кодовыми комбинациями.

zizj p(zizj) код.комб.

24

вероятностей для независимых событий

p(zizj) = p(zi)∙p(zj).

Рассчитаем основные характеристики

lср= 0,64∙1+0,16∙2+0,16∙3+0,04∙3 ≈ 1,56;

В последней формуле учли, что энтропия увеличится в 2 раза, согласно (10),

H (Z, Z) H (Z) H (Z) 2 H (Z) .

При кодировании блоков из трех букв эффективность возрастает еще больше.

lср= 0,512∙1+0,128∙9+0,032∙15+0,008∙5 ≈ 2,184;

Таким образом, имеем æ1 ‹ æ2 ‹ æ3 .

Задачи (блок E)для выполнения:

1 – 10. Провести кодирование по одной и блоками по две буквы, используя метод Шеннона – Фано. Сравнить эффективности кодов. Данные взять из задач блока C.

25

26

Характеристики кода рассчитываются по тем же формулам, что и для кода Шеннона–Фано

Код Хаффмана можно использовать и для кодирования блоков из букв так, как это было рассмотрено выше для кода Шеннона–Фано, что увеличит эффективность передачи информации.

Задачи (блок F)для выполнения:

1 – 10. Алфавит передаваемых сообщений состоит из независимых букв Si. Вероятности появления каждой буквы в сообщении заданы. Определить и сравнить эффективность кодирования сообщений методом Хаффмана при побуквенном кодировании и при кодировании блоками по две буквы.

Библиографический список:

1.Информатика [Текст]: учебник / В. В. Трофимов [и др.] ; под ред. В. В. Трофимова ; С.-Петерб. гос. ун-т экономики и финансов. - М. : Юрайт, 2011. -

911 с.

2.Информатика [Текст] : учебник / В. В. Трофимов [и др.] ; под ред. В. В. Трофимова ; С.-Петерб. гос. ун-т экономики и финансов (СПбГУЭФ). - М.

:Юрайт : Высшее образование, 2010. - 911 с.

3.Острейковский, Владислав Алексеевич, Информатика : учеб. пособие для студентов учреждений сред. проф. образования / В. А. Острейковский. - М. : Высшая школа, 2003. - 319 с.

4.Романова, Ю.Д. Информатика и информационные технологии: учебное пособие /Ю.Д. Романова, И.Г. Лесничая, В.И. Шестаков, И.В. Мисинг, П.А. Музычкин; под ред. Ю.Д. Романовой. – 3-е изд., перераб. И доп. – М.: Эксмо, 2008. – С. 309-404. – (Высшее экономическое образование).

28