Вопрос № 9.
Сжатие данных.
1. Поиск повторяющихся последовательностей (миллион нулей).
2. Составление словаря лексических единиц.(45, 94, 169).
3. Код Хармена (3 бита для кодирования N поколения; Верх пирамиды 0, и по возрастающей вниз.
Алгоритмы сжатия без потерь.
Если при сжатии данных происходит только изменение их структуры, то метод сжатия обратим. Из результирующего кода можно восстановить исходный массив путем применения обратного метода. Обратимые методы применяются для сжатия любых типов данных. Характерными форматами сжатия без потерь информации являются:
.GIF, .ITF, PCX и многие другие для графических данных;
.AVI для видеоданных;
.ZIP, .ARJ, .RAR, .LZH, .LH, .CAB и многие другие для любых типов данных.
Алгоритмы обработки методов.
При исследовании методов сжатия данных иметь в виду существование следующих доказанных теорем.
Для любой последовательности данных существует теоретический предел сжатия, который не может быть превышен без потери части информации.
Для любого алгоритма сжатия модно указать такую последовательность данных, для которой он обеспечивает лучшую степень сжатия, чем другие методы.
Для любого алгоритма сжатия можно указать такую последовательность данных, для которой данный алгоритм вообще не получить сжатия.
Таким образом, обсуждая различные методы сжатия, следует иметь в виду, что наивысшую эффективность они демонстрируют для данных разных типов и разных объемов.
Современные программные средства для создания и обслуживания архивов обеспечивают выполнение следующих функций:
извлечение информации из архивов;
создание новых архивов;
добавление информации в имеющийся архив;
тестирование целостности структуры архивов;
полное или частичное восстановление поврежденных архивов;
защита архивов от просмотра и несанкционированных изменений.
Перечислим основные методы сжатия цифровых данных.
Основная проблема передачи данных – возникновение ошибок. Причинами ошибок могут быть: загрязнение поверхности магнитного диска, случайный сбой электронной схемы, влияние какого–либо излучения и др.
Для обнаружения ошибок, возникающих при передаче данных разработано множество технологий. Один из наиболее простых способов построен на следующем принципе. Если каждая обрабатываемая битовая комбинация будет состоять из нечетного количества знаков, то обнаруженная комбинация с четным количеством битов будет свидетельствовать о возникновении ошибки. Для возможности такой проверки битовые комбинации дополняют так называемым битом четности (контрольным битом). Кроме того, разработаны такие методы, которые позволяют не только выявить ошибки при передаче данных, но и исправить их. Принцип действия кода с исправлением ошибок основан на понятии дистанции Хэмминга.
Вопрос № 11.
При рассмотрении компьютерных устройств принято различать их архитектуру и структуру.
Архитектурой компьютера называется его описание на некотором общем уровне, включающее описание пользовательских возможностей программирования, системы команд, системы адресации, организации памяти и т.д. Архитектура определяет принципы действия, информационные связи и взаимное соединение основных логических узлов компьютера: процессора, оперативного ЗУ, внешних ЗУ и периферийных устройств. Общность архитектуры разных компьютеров обеспечивает их совместимость с точки зрения пользователя. |
Структура компьютера — это совокупность его функциональных элементов и связей между ними. Элементами могут быть самые различные устройства — от основных логических узлов компьютера до простейших схем. Структура компьютера графически представляется в виде структурных схем, с помощью которых можно дать описание компьютера на любом уровне детализации. |
Наиболее распространены следующие архитектурные решения.
Теоретические основы построения и функционирования ЭВМ, кардинальным образом не изменившиеся до настоящего времени, были сформулированы выдающимся математиком Джоном фон Нейманом в 1945–1947 гг. и известны как принципы фон Неймана. Среди них была идея представления обрабатываемых данных и программы в числовой форме и их размещения в памяти машины. Для упрощения логических схем фон Нейман предложил использовать двоичную систему счисления.
Согласно принципам фон Неймана, компьютер должен иметь следующие устройства:
арифметико-логическое устройство, выполняющее арифметические и логические операции;
устройство управления, которое организует процесс выполнения программ и координирует взаимодействие всех устройств ЭВМ во время ее работы;
запоминающее устройство или память для хранения данных и программ;
устройства ввода- вывода.
Память компьютера должна состоять из некоторого количества пронумерованных (имеющих собственные адреса) ячеек, в каждой из которых могут находиться обрабатываемые данные или программные инструкции. Все ячейки памяти должны быть доступны для других устройств компьютера.
В общих чертах работа компьютера, построенного по принципам фон Неймана, выглядит так: вначале при помощи устройства ввода в память компьютера вводится программа. Затем устройство управления считывает содержимое той ячейки памяти, где находится первая инструкция (команда) программы и организует ее выполнение (считывание из памяти данных, выполнение арифметических или логических операций, ввод новых данных в память или запись туда результатов обработки, вывод данных из памяти на устройство вывода и др.) Далее в устройство управления попадает команда из следующей ячейки памяти и т.д. Важно отметить, что последовательность выполнения команд может меняться в зависимости от выполнения некоторых условий, задаваемых в самой программе. Для этого существуют специальные команды передачи управления.
Совокупность наиболее общих принципов построения и организации функционирования информационно-вычислительной системы принято называть архитектурой. Описанную выше классическую архитектуру ЭВМ, часто называемую фон-неймановской, можно изобразить следующей схемой (см. рис. 2.1), на которой черными стрелками обозначены пути передачи данных, а белыми – управляющие связи. Арифметико-логическое устройство и устройство управления объединены в единое устройство, называемое центральным процессором.
Рис. 2.1. Классическая фон-неймановская архитектура ЭВМ
Схема устройства современных компьютеров несколько отличается от приведенной выше. Уже в машинах первого поколения произошло разделение памяти на оперативную (сравнительно небольшую по объему, но быстродействующую) для хранения данных, к которым ЭВМ часто обращается в процессе работы, и внешнюю для хранения больших массивов данных и библиотек программ. Память современных ЭВМ представляет собой сложную многоуровневую иерархическую структуру, где на верхнем уровне иерархии расположена самая быстродействующая память (кэш-память), в которую при решении очередной задачи помещаются наиболее интенсивно используемые фрагменты данных и программ. В современных ЭВМ может быть несколько уровней кэш-памяти, причем кэш-память первого уровня, как правило, находится внутри центрального процессора. Радикально увеличилось количество и возможности внешних устройств накопления, ввода и вывода данных и др. Функции непосредственного управления работой внешних устройств перешли к специальным управляющим устройствам – контроллерам или адаптерам. Обмен данными между устройствами осуществляется через системную магистраль передачи данных, называемую шиной. В общем случае шина состоит из трех частей:
шина данных, по которой собственно осуществляется обмен данными;
адресная шина, определяющая, куда и откуда передаются данные;
шина управления, передающая управляющие сигналы.
Физически шина – это просто набор проводников, однако именно она является функциональным центром конструкции современного компьютера. Соответствующая схема представлена на рис. 2.2.
Рис. 2.2. Шинная архитектура современных компьютеров
Важнейшим параметром шины является ее разрядность – число одновременно передаваемых бит данных. В результате перехода на шинную архитектуру появилась возможность организовать прямой (без непосредственного участия центрального процессора) обмен данными между устройствами, в частности, режим прямого доступа к оперативной памяти. Все вышеперечисленные изменения привели к существенному росту производительности ЭВМ. Вместе с тем, на данный момент подавляющее большинство современных компьютеров в общих чертах соответствует классическим принципам фон Неймана.
Классификация современных компьютеров.
Номенклатура
видов ЭВМ в настоящее время достаточно
обширна. Компьютеры различаются по
назначению, мощности, габаритным
размерам, устойчивости по отношению к
неблагоприятным воздействиям и т.д.
Самая общая схема классификации ЭВМ,
исходя из их производительности, размеров
и функционального назначения, приведена
на рисунке 2.3. 
Наиболее мощные среди всех существующих в рассматриваемый период времени ЭВМ, созданные на пределе современных им технических возможностей, принято называть суперкомпьютерами. Они предназначены для решения столь важных и сложных задач, что вопрос об их стоимости и прямом экономическом эффекте от их использования зачастую не имеет принципиального значения. В числе задач, решаемых с применением супер-ЭВМ, – сложнейшие научно-технические расчеты, задачи, связанные с обороноспособностью государства, создание и поддержка гигантских банков данных, управление региональными энергетическими системами и др.
Большие ЭВМ по сравнению с суперкомпьютерами более доступны. Помимо сложных научно-технических расчетов, их применяют в качестве центральных машин автоматизированных систем управления крупных предприятий, банков.
Мини-ЭВМ появились в начале 70-х гг. Они, как правило, достаточно резко отличаются от больших ЭВМ уменьшенными размерами и, соответственно, меньшей производительностью и стоимостью. Их традиционные области применения – системы управления предприятиями среднего размера, в частности, обслуживание локальных вычислительных сетей масштаба предприятия, управление технологическими процессами. Нередко компьютеры этого класса используются крупными учебными заведениями, сочетающими учебную деятельность с научной.
Микро-ЭВМ обязаны своим появлением микропроцессорам. Это самый многочисленный класс компьютеров, и поэтому в составе микро-ЭВМ выделяют дополнительные подклассы. Мы используем классификацию, принятую в [1].
Наиболее мощные микро-ЭВМ часто обслуживают достаточно многочисленные группы пользователей, работая в режиме разделения времени между большим количеством мелких задач. Назовем их многопользовательскими микро-ЭВМ.