Kandaurova_N_Vychislitelnye_sistemy_seti_i_telekommunikatsii
.pdfD:/Студент/№ группы/ФИО студента/№ работы (а также создать копию отчѐта о работе на любом внешнем ЗУ) и представить преподавателю для защиты;
6)защитить результаты выполненной работы, ответить на контрольные вопросы.
Примечание. Только после представления отчѐта (результатов выполненной работы) в электронном виде преподавателю и еѐ защиты она считается выполненной.
Контрольные вопросы
1.Каково основное предназначение счѐтчиков в устройствах вычислительных систем, сетей и телекоммуникаций?
2.Из чего состоят счетчики?
3.Счетчик – это элемент, узел, блок или устройство вычислительных систем, сетей и телекоммуникаций?
4.Какую функцию позволяет осуществить многоразрядный двоичный счетчик?
5.Напишите формулу подсчѐта N сигналов счетчика, состоящего из n- триггеров?
6.Каковы дополнительные функции счѐтчиков в устройствах вычислительных систем, сетей и телекоммуникаций?
7.Дейсвительно ли функционально различают суммирующие, вычитающие и реверсивные счетчики?
8.Какое свойство Т-триггеров положено в основу построения любого счетчика?
9.Построите таблицу переходов 3-разрядного суммирующего счетчика.
10.Изобразите функциональную схему счетчика на Т-триггерах.
11.Нарисуйте временную диаграмму работы счетчика на Т-триггерах.
290
Лабораторная работа № 14. СИНТЕЗ СХЕМЫ СУММИРУЮЩЕГО УЗЛА ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
Цель:
1) закрепить теоретические знания и получить практические навыки синтеза схем с памятью на примере суммирующих узлов, состоящих из сумматора и регистров, и широко применяемых в устройствах вычислительных систем, сетей и телекоммуникаций;
2) получить и закрепить практические навыки разработки суммирующих узлов в электронном виде в различных программных средах.
Краткие теоретические сведения
Обработка информации в схемах вычислительных систем, сетей и телекоммуникаций обеспечивается преобразователями (цифровыми автоматами) двух видов: комбинационными схемами и схемами с памятью.
Схемы с памятью. Наличие памяти в схеме позволяет запоминать промежуточные состояния обработки и учитывать их значения в дальнейших преобразованиях. В качестве простейших запоминающих элементов в современных ЭВМ используются триггеры, из которых могут быть построены сумматоры.
Сумматор – это узел вычислительной системы, в котором суммируются коды чисел. Как правило, любой сумматор представляет собой комбинацию одноразрядных сумматоров. Сумматоры различают по принципам построения: накапливающего типа и комбинационного типа. Сумматоры накапливающего типа строят на сложных JKRS-триггерах, дополняя их выходы достаточно сложными схемами формирования и распространения переносов. Процесс сложения при этом осуществляется поэтапно. Сначала на триггерах сумматора фиксируется код первого операнда, затем на счетные коды разрядов подается код второго операнда. По зависимостям
Si p(ab ab) b(a p ap) a(b p bp) p(a b) b(a p) a(b p); Pi ab ap bp
на каждом триггере формируются одноразрядные суммы и значения переносов между разрядами. Учет возникающих переносов задерживает формирование окончательного результата суммы и может требовать дополнительных тактов сложения. Из-за этого многоразрядные схемы сумматора накапливающего типа используются достаточно редко.
Для построения сумматоров чаще применяют сумматоры комбинационного типа. Логика работы такого сумматора представлена данными таблица 14.1.
Обычно у комбинационного сумматора на входе и выходе имеются регистры для хранения и преобразования кодов операндов и результата (рисунок 14.1).
291
Таблица 14.1 – Таблица истинности одноразрядного комбинационного сумматора на 3 входа
Значения |
Перенос из |
|
Разряд |
|
Перенос в |
||
двоичных чисел |
предыдущего |
|
|
следующий |
|||
|
суммы |
|
|||||
|
A и В |
разряда |
|
|
разряд |
||
|
|
Si |
|
||||
|
|
|
|
|
|
Pi |
|
ai |
|
bi |
pi–1 |
|
|||
|
|
|
|
||||
0 |
|
0 |
0 |
0 |
0 |
||
0 |
|
0 |
1 |
|
1 |
0 |
|
0 |
|
1 |
0 |
|
1 |
0 |
|
0 |
|
1 |
1 |
0 |
|
1 |
|
1 |
|
0 |
0 |
|
1 |
0 |
|
1 |
|
0 |
1 |
0 |
|
1 |
|
1 |
|
1 |
0 |
0 |
|
1 |
|
1 |
|
1 |
1 |
|
1 |
|
1 |
Регистр Рг1 предназначается для хранения кода первого операнда Оп1, регистр Рг2 – для хранения кода второго операнда Оп2. Сумматор по сигналам из устройства управления (УУ) настраивается на выполнение определенной машинной операции, соответствующей коду операции, находящемуся в коде команды. Результат выполняемой операции фиксируется в регистре Рг3. При необходимости этот результат может использоваться для продолжения вычислений. Для этого предусматривается возможность перезаписи содержимого регистра Рг3 на Рг1 в качестве значения одного из операндов при выполнении очередной операции.
|
Результат |
|
Рг3 |
из УУ |
|
|
Сумматор |
Рг1 |
Рг2 |
Оп1 |
Оп2 |
Рисунок 14.1 – Упрощенная схема сумматора комбинационного типа
Выполнение лабораторной работы
Для получения зачѐта по лабораторной работе необходимо:
1)знать вышеизложенный теоретический материал по синтезу структурных схем с памятью на примере суммирующих узлов, состоящих из сумматора комбинационного типа и регистров, и широко применяемых в устройствах вычислительных систем, сетей и телекоммуникаций;
292
2)выбрать из таблицы 14.2 тип суммирующего узла по № задания, соответствующему № студента в журнале учебной группы (или другим способом по согласованию с преподавателем);
Таблица 13.2 – Варианты заданий
№ |
|
Тип |
|
№ |
|
Тип |
|
|
№ |
|
Тип |
|
|
суммирующего |
|
|
суммирующего |
|
|
|
суммирующего |
|
|||
задания |
|
|
задания |
|
|
|
задания |
|
|
|||
|
узла |
|
|
узла |
|
|
|
узла |
|
|||
|
|
|
|
|
|
|
|
|
|
|||
1 |
|
|
|
6 |
|
|
|
|
11 |
|
С 1 входным |
|
|
Без перезаписи |
|
|
С перезаписью |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
Рг без |
|
||
|
|
результата в |
|
|
|
результата в |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
перезаписи |
|
||
|
|
Рг1 |
|
|
|
Рг1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
результата |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
7 |
|
С 1 входным |
|
12 |
|
С 1 входным |
|
|
|
С перезаписью |
|
|
|
|
|
||||||
|
|
|
|
|
Рг без |
|
|
|
|
Рг с |
|
|
|
|
результата в |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
перезаписи |
|
|
|
|
перезаписью |
|
|
|
|
Рг1 |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
результата |
|
|
|
|
результата |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
3 |
|
С 1 входным |
|
8 |
|
С 1 входным |
|
13 |
|
Без перезаписи |
|
|
|
|
|
|
|
|
|||||||
|
|
Рг без |
|
|
|
Рг с |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
результата в |
|
||
|
|
перезаписи |
|
|
|
перезаписью |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рг1 |
|
||
|
|
результата |
|
|
|
результата |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
4 |
|
С 1 входным |
|
9 |
|
Без перезаписи |
|
|
14 |
|
С перезаписью |
|
|
|
|
|
|
|
|
||||||
|
|
Рг с |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
результата в |
|
|
|
|
результата в |
|
|
|
|
перезаписью |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
Рг1 |
|
|
|
|
Рг1 |
|
|
|
|
результата |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
10 |
|
|
|
|
15 |
|
С 1 входным |
|
|
Без перезаписи |
|
|
С перезаписью |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
Рг без |
|
||
|
|
результата в |
|
|
|
результата в |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
перезаписи |
|
||
|
|
Рг1 |
|
|
|
Рг1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
результата |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
3)разработать, в соответствии со своим заданием, теоретическим материалом и логическими зависимостями, и нарисовать упрощенную схему
сумматора комбинационного типа, для примера такая схема с 2-мя входными Рг и с перезаписью результата в Рг1 (задание № 2) показана на рисунке 14.1, она разработана в среде MS Word Рисование;
4)составить таблицу истинности одноразрядного комбинационного
сумматора на 3 входа (см. таблицу 14.1), где Si – функция одноразрядной
суммы и Pi – функция формирования переноса в старший разряд, а pi-1 – сигнал переноса из младшего соседнего разряда. Эта таблица разработана в помощь студентам при выполнении задания лабораторной работы;
5)нарисовать обозначение одноразрядного комбинационного сумматора на 3 входа, применяемое на принципиальных электрических схемах, для примера это обозначение одного разряда комбинационного сумматора представлено на рисунке 14.2, которое создано с помощью программы Рисование;
293
ai |
|
SM |
Si |
|
|
||||
bi |
||||
|
|
|||
pi |
|
|
Pi |
|
|
|
|||
Рисунок 14.2 – Условное изображение одного разряда комбинационного сумматора на принципиальных электрических схемах
6)материалы всей работы (отчѐт о работе) оформить в электронной среде MS Word, Paint, Visio или Рисование и сохранить на логическом диске D:/Студент/№ группы/ФИО студента/№ работы (а также создать копию отчѐта о работе на любом внешнем ЗУ) и представить преподавателю для защиты;
7)защитить результаты выполненной работы, ответить на контрольные вопросы.
Примечание. Только после представления отчѐта (результатов выполненной работы) в электронном виде преподавателю и еѐ защиты она считается выполненной.
Контрольные вопросы
1.Каково предназначение сумматоров в устройствах вычислительных систем, сетей и телекоммуникаций?
2.Сумматор – это элемент, узел, блок или устройство в вычислительных системах, сетях и телекоммуникациях?
3.Из чего состоит любой сумматор?
4.Какие различают сумматоры по принципам построения?
5.На каких триггерах строят сумматоры накапливающего типа?
6.Что формируется на каждом триггере сумматора накапливающего типа?
7.Каковы недостатки работы сумматора накапливающего типа?
8.Из-за чего многоразрядные схемы сумматора накапливающего типа используются достаточно редко?
9.Какого типа чаще всего применяют сумматоры?
10.Постпойте таблицу истинности одноразрядного комбинационного сумматора на 3 входа.
11.Сколько регистров имеется на входе и выходе комбинационного сумматора?
12.Для чего предназначается Регистр Рг1?
13.Для чего предназначается регистр Рг2?
14.Где вырабатываются сигналы на выполнение определенной машинной операции?
15.Для чего предназначается регистр Рг3?
16.Нарисуйте упрощенную схему сумматора комбинационного типа.
294
17. Лабораторная работа № 15. ИССЛЕДОВАНИЕ МЕТОДОВ
НЕРАЗРУШАЮЩЕГО СЖАТИЯ ИНФОРМАЦИИ
Цель работы:
1)изучить методы неразрушающего сжатия информации и алгоритм минимального неравномерного кодирования, одного из самых применяемых методов неразрушающего сжатия;
2)освоить генерацию кодовых таблиц равномерного и минимального неравномерного кодирования.
Краткие теоретические сведения
Сжатие информации – это перевод информации в такую форму записи, при которой размер файла сокращается. Сжатие бывает:
неразрушающее – состоит в удалении из информации избыточной информации, полезная информация остается без изменений, применяется к текстовым и программным файлам;
разрушающее – кроме избыточной информации удаляется часть полезной, хотя может быть и не самая важная часть, применяется к аудио и видео.
Входе данной работы будем рассматривать методы сжатия применительно исключительно к неразрушающему сжатию. Для упрощения
изложения рассмотрим сжатие на примере текстовых файлов. Но, рассматриваемые методы применимы к любым файлам, содержимое которых можно представить как последовательность двоичных кодов.
Понятие кодовой таблицы. При кодировании каждому символу исходного сообщения, ставится в соответствие некоторая битовая комбинация кода. Список, в котором указано соответствие кодов исходного сообщения кодам сжатого, называется кодовой таблицей (таблицей соответствия). Основным приѐмом кодирования информации для еѐ сжатия, является построение специальных кодовых таблиц (таблица 15.1). Удачно построенная таблица обеспечивает наименьший размер файла и сжатие файла.
Таблица 15.1 – Пример кодовой таблицы
Символ |
Код |
Ф |
00 |
а |
01 |
й |
10 |
л |
11 |
Минимальное равномерное кодирование. Для кодирования одного символа требуется, как минимум, n = log 2 N бит информации, где N – объем
алфавита. Такой код длиной n = log 2 N принято называть минимальным,
295
величину n – минимальной кодовой длиной, а сообщения, составленные из кодов такой длины – минимальными равномерными кодами.
В реальных файлах стандартных форматов, используется кодирование символов с использованием стандартных кодов. Стандартные текстовые коды ASCII (American Standard Code for Information Interchange –
Американский стандартный код для обмена информацией) всегда 8-битовые, независимо от того, каков реальный объем алфавита сообщения. На рисунке 15.1 приведена таблица соответствия кодов ASCII. Всего в таблице можно разместить 28=256 символов.
Рисунок 15.1 – Таблица соответствия кодов ASCII
Вней 8-битовый 16-ричный код символа образуется из цифры столбца
ицифры строки. Таблица состоит из 2-ух частей: слева (00-7F) основной
стандарт используется для кодирования букв латинского алфавита и управляющих символов; справа (80-FF) расширение – для кодирования букв национального алфавита (в каждой стране свои) и символов псевдографики.
С целью сжатия такие файлы могут быть перекодированы с использованием кодовых таблиц использующих коды с длиной, соответствующей минимальной кодовой длине.
296
Алгоритм кодирования:
1.Подсчитываем N – объем алфавита.
2.Вычисляем nmin = log 2 N .
3.Составляем нестандартную кодовую таблицу с кодами длиной nmin вместо кодов стандартной длины, равной 8 бит.
4.Перекодируем исходный файл из стандартных кодов – в минимальные коды, используя составленную кодовую таблицу, получаем сжатый файл.
5.Приложить к файлу полученную уникальную кодовую таблицу, чтобы в дальнейшем было возможно прочитать содержимое сжатого файла.
Алгоритм декодирования. Декодер, используя приложенную к файлу уникальную кодовую таблицу, определяет символы и заменяет минимальные равномерные коды на стандартные код из стандартной кодовой таблицы
(рисунок 15.1).
Адаптивные и вариантные кодовые таблицы. Не во всех случаях необходимо прилагать к сжатому файлу использованную при сжатии кодовую таблицу. Возможны два варианта: 1) с передачей уникальной кодовой таблицы составленной для данного сообщения, такие кодовые таблицы принято называть адаптивными; 2) с использованием заранее подготовленных таблиц (принято называть вариантными). Тогда ещѐ при разработке программ сжатия файлов и данных, составляется множество вариантов кодовых таблиц для различных типичных случаев содержимого сжимаемого файла. В ходе кодирования определяется, какая из таблиц больше подходит под данный файл, и именно эта таблица и используется при кодировании. В данном случае потребуется передать только номер варианта таблицы. Первый метод используется при кодировании файлов большого размера, второй – малого.
Коэффициент сжатия. В различных источниках используется либо
формула k |
Nисходного |
, либо формула |
k |
Nсжатого |
. При минимальном |
|
|
||||
|
Nсжатого |
|
Nисходного |
||
равномерном кодировании без учета кодовой таблицы коэффициент сжатия
составит |
k |
log 2 |
N |
, где N – число символов сообщения, n – длина |
n |
|
|||
|
|
|
|
стандартного кода.
Неразрушающее групповое кодирование. Дополнительное сжатие можно обеспечить, если в файле встречаются часто повторяющиеся последовательности символов. Например, часто повторяются одни и те же слова.
Тогда, при составлении уникальной кодовой таблицы, можно предусмотреть передачу одним кодом не только отдельных символов, но и часто повторяющихся последовательностей символов. Кодеру тогда нужно будет просмотреть сжимаемый файл, найти повторяющиеся последовательности, и включить в кодовую таблицу коды для каждой из найденных последовательностей.
297
Минимальное неравномерное кодирование. Различие с методом равномерного минимального кодирования проявляется при составлении кодовой таблицы. Для часто встречающихся символов используются очень короткие коды, длиной меньше nmin = log 2 N . Тогда для редких символов,
придется использовать длинные коды, длиной даже больше чем nmin.
Кроме этого, в силу того, что задача дешифрации при использовании этого метода оказывается, не так тривиальна, различия имеются также в алгоритме дешифрации.
Дешифрация минимальных неравномерных кодов. Как определить границы между отдельными кодами? Это возможно методом последовательного разбора, но только если наложить на используемые коды дополнительное ограничение – никакие первые биты длинных кодов, не должны совпадать с короткими кодами. Если означенное условие выполнено, возможна дешифрация с использованием метода последовательного разбора.
Метод последовательного разбора:
1.Считываем из файла первый бит.
2.Интерпретируя этот бит, как возможный код, просматриваем кодовую таблицу и ищем, нет ли в таблице такого кода.
3.Если нет, считывается второй бит и т.д., пока не получим совпадение считанного кода с одним из кодов кодовой таблицы. Затем читаем, таким образом символ найден.
4.С того места, где закончен поиск предыдущего символа, аналогично начинаем поиск нового символа. Повторяем алгоритм поиска нового символа до тех пор, пока не будут определены все символы.
Алгоритмы генерации кодовой таблицы. Необходимо составить такую кодовую таблицу, чтобы часто встречающиеся символы в ней были закодированы короткими кодами и при этом короткие коды не совпадали с первыми битами длинных кодов.
Пример для закрепления. Если известна кодовая таблица (таблица 15.2), декодировать из минимального неравномерного кода сообщение
01001011000110111101011001111010011111.
Таблица 15.2 – Кодовая таблица для закрепления метода последовательного разбора
Символ |
|
Код |
|
|
|
м |
|
0 |
|
|
|
а |
|
10 |
|
|
|
_ |
|
1100 |
|
|
|
ы |
|
1101 |
|
|
|
л |
|
1110 |
|
|
|
р |
|
11110 |
|
|
|
у |
|
11111 |
|
|
|
298 |
|
|
Выполнение лабораторной работы
Для получения зачѐта по лабораторной работе необходимо:
1)знать вышеизложенный теоретический материал о методах неразрушающего сжатия информации и алгоритм минимального неравномерного кодирования, одного из самых применяемых методов неразрушающего сжатия;
2)освоить генерацию кодовых таблиц равномерного и минимального неравномерного кодирования;
3)выбрать из таблицы 15.3 содержание сообщения по № задания, соответствующему № студента в журнале учебной группы (или другим способом по согласованию с преподавателем);
Таблица 15.3 – Варианты заданий
№ |
Содержание сообщений |
|
задания |
||
|
||
1 |
Вычислительные системы и сети |
|
2 |
Вычислительные сети и системы |
|
3 |
Вычислительные системы и телекоммуникации |
|
4 |
Вычислительные сети и телекоммуникации |
|
5 |
Процессор обрабатывает информацию |
|
6 |
Компьютер имеет процессор и сопроцессор |
|
7 |
Арифметико-логическое устройство |
|
8 |
Микропроцессорная регистровая память |
|
|
|
|
9 |
Оперативное запоминающее устройство |
|
|
|
|
10 |
Внешнее запоминающее устройство |
|
11 |
Мультиплексор передачи данных |
|
|
|
|
12 |
Модулятор и демодулятор – устройство |
|
|
|
|
12 |
Шифратор и дешифратор – устройство |
|
13 |
Операционная система Windows XP Pro |
|
|
|
|
14 |
Системное программное обеспечение |
|
|
|
|
15 |
Прикладное программное обеспечение |
|
16 |
Инструментальное программное обеспечение |
|
|
|
|
17 |
Сетевая операционная система Net Ware |
|
|
|
|
18 |
Сетевая операционная система Linux |
|
19 |
Текстовый процессор MS Word |
|
|
|
|
20 |
Табличный процессор MS Excel |
4)закодировать в стандартный равномерный код ASCII (рисунок 15.1) своѐ сообщение из таблицы 15.3;
5)разработать кодовую таблицу минимального неравномерного кодирования для своего сообщения;
6)закодировать в минимальный неравномерный код свой вариант сообщения;
7)определить коэффициент сжатия при минимальном неравномерном кодировании, для своего варианта сообщения;
299