Алгоритм –это точно определенная, однозначная последовательность простых (элементарных) шагов, обеспечивающих решение любой задачи из некоторого класса. 2 страница
Алгоритм проверки и исправления последовательности бит в представлении Хемминга:
1. провести проверку всех битов четности;
2. если все биты четности верны, перейти к п.5;
3. вычислить сумму номеров всех неправильных битов четности;
4. инвертировать содержимое бита, номер которого равен сумме п.3;
5. исключить биты четности, передать правильный информационный код.
Избыточность кода Хемминга для различных длин передаваемых последовательностей приведена ниже:
Число информационных битов | Число контрольных битов | Избыточность |
1,5 | ||
1,31 | ||
1,06 |
Следовательно, выгоднее передавать и хранить более длинные последовательности битов.
1.5 Способы передачи информации в компьютерных линиях связи
В компьютерных линиях связи используются 2 способа передачи:
- параллельный – когда передаются одновременно все биты машинного слова;
- последовательный – когда биты передаются поочередно, начиная с младшего.
Параллельная передача.Для одновременной передачи нескольких сигналов, очевидно, требуется линия связи, количество проводников в которой совпадает с числом передаваемых сигналов. Такая линия связи называется шина.
Количество проводников определяет ширину или разрядность шины. Например, во внутренних линиях используется 16-ти и 32-х разрядные шины. Шина обеспечивает наиболее быстрый способ передачи информации, поскольку за 2 такта синхронизатора компьютера передается целое машинное слово.
В общем случае, если um – тактовая частота генератора, h – разрядность шины, а n – число тактов, за которые осуществляется передача, то пропускная способность канала параллельной передачи .
Например, при тактовой частоте генератора um = 300 МГц и ширинешины 32 бит, максимальная скорость
.
Параллельный способ передачи используется во внутренних линиях связи компьютера, на материнской плате при обмене с устройствами внешней памяти – магнитными дисками, CD, а также для связи с внешними устройствами, подключенными к параллельному порту компьютера (LPT – порт) – принтером и др.
К недостаткам параллельного канала передачи относят:
- невозможность передачи на большие расстояния (более нескольких метров), поскольку между параллельными проводниками имеется электроемкость, увеличивающаяся с их длиной. (Это приводит к тому, что при протекании импульса по какому-либо одному проводнику возникают наводки в других);
- высокая стоимость линии связи, так как данный способ требует специальных многожильных проводов.
Последовательная передача данных.Для передачи информации на большие расстояния используется последовательный способ передачи. Возможны два режима последовательной передачи: синхронный и асинхронный.
При синхронной передаче каждый передаваемый бит сопровождается импульсом синхронизации, информирующим приемник о наличии в линии информационного бита.
Синхроимпульсы управляют приемом информации. Следовательно, между передатчиком и приемником должны быть протянуты минимум 3 провода: один для передачи данных, второй – для передачи синхроимпульсов, третий – общий заземление.
Если расстояние между источником и приемником составляет несколько метров, то каждый из сигналов приходится посылать по экранированному кабелю, что значительно увеличивает стоимость линии связи.
Кроме того, такая передача оказывается целесообразной, если передается некоторый массив символов (не отдельные символы).
Эти обстоятельства приводят к тому, что синхронный способ связи не получил широкого распространения.
Асинхронный способ передачи не требует синхронизации действий приемника и передатчика; по этой причине для связи достаточно линии из двух проводников, причем оказывается возможным использование даже телефонных линий, то есть неспециализированных компьютерных. При этом источник и приемник информации должны быть согласованы по формату и скорости передачи.
Передача производится машинными словами (информационные биты), дополненными несколькими служебными. Например, передача 8-битного слова с одним контрольным битом (рисунок 1.4). В отсутствии передачи в линии поддерживается уровень сигнала, соответствующий логической единице (например, +5В).
Передатчик может начать пересылку в любой момент посредством генерации стартового бита, который переводит линию в состояние логического нуля на время t0 - по нему приемник узнает о том, что передача началась.
Источник и приемник должны быть согласованы по формату и скорости передачи данных - по длительности t0.
Затем, происходит передача информационных битов, начиная с младшего (0-го). За ними передается контрольный бит четности. И последним следует стоповый бит, который вновь переводит линию в состояние ожидания (то есть «1»).
Вся передаваемая цепочка от стартового до стопового бита называется кадром.
Передача следующего кадра может начаться сразу после стопового бита, причем новый стартовый бит может быть послан в любой момент времени, не обязательно кратный t0, например, 3,45t0 , или 0,7t0 - поэтому передача и называется асинхронной.
Для обеспечения максимальной защищенности сигнала приемник настраивается на считывание в середине бита.
Поскольку биты передаются по очереди, скорость передачи ниже, чем в параллельном способе.
На главное преимущество – нет ограничений на дальность передачи.
1.6 Связь компьютеров по телефонным линиям
Применение телефонных линий для осуществления связи между удаленными на большие расстояния компьютерами диктуется, в первую очередь, экономическими соображениями – в противном случае требуется прокладка специальных компьютерных линий и содержание служб, поддерживающих их работоспособность.
Использование двухпроводной линии и большие расстояния однозначно определяют способ передачи – последовательный.
Однако телефонные линии предназначены для передачи аналоговых сигналов с частотой человеческого голоса (верхняя граница – 3400 Гц).
При передаче по таким линиям сигналов с частотами, на которых работает компьютер (~ ГГц) – они будут быстро затухать. Поэтому передача осуществляется по схеме, приведенной на рисунке 1.5.
На передающем конце линии связи сначала осуществляется преобразование параллельного компьютерного кода в асинхронную последовательность. Затем посредством другого устройства – модема – производится модуляция двухуровневых импульсных компьютерных сигналов в аналоговые, которые без большого затухания и искажения могут распространяться в телефонных линиях.
На приемном конце происходит обратное преобразование.
Асинхронный преобразователь располагается в самом компьютере в виде блока, осуществляющего обмен последовательным способом с любым устройством – этот блок называется последовательным портом (COM – портом). Помимо модема к нему присоединяется мышь, джойстик и т.п.
При передаче данных по последовательным линиям связи возможны 3 режима: симплексный, полудуплексный и дуплексный.
Симплексная линия обеспечивает передачу только в одном направлении, например, от датчика к устройству обработки.
Полудуплексная связь обеспечивает передачу и получение информации в обоих направлениях – но не одновременно.
Дуплексная связь обеспечивает передачу и получение данных в обоих направлениях одновременно.
В случае, когда модем подключен параллельно к телефонному аппарату, скорость передачи данных не превышает всего несколько десятков кБ/с.
При выделенных линиях связи (предназначенных только для компьютерной связи) скорость увеличивается до нескольких сотен кБ/с. Такие линии выгодны при передаче больших объемов информации или срочной передачи данных. Применение спутниковой связи и каналов цифровой передачи данных повышает пропускную способность до нескольких МБ/с.
Контрольные вопросы и задачи
1. Назовите основные элементы любой линии связи и их назначение.
2. Как влияют шумы на процесс передачи данных?
3. Приведите примеры каналов связи.
4. Назовите основной принцип построения кодов, обнаруживающих ошибку, исправляющих ошибку.
Задача 1. Получено машинное слово, закодированное с использованием кода Хемминга.
Определите, была ли ошибка передачи, и устраните ее.
Задача 2. Сколько времени будет выводиться на экран монитора картинка размером 300х400 пикселей при цветовом режиме 16 бит на цвет, если для обмена используется 32 –разрядная шина, а частота тактового генератора 166 МГц?
2 Поколения ЭВМ. Основные устройства компьютера
2.1 Поколения электронных вычислительных машин
Современный компьютер (ЭВМ) – это универсальное, многофункциональное электронное автоматическое устройство для работы с информацией. По историческим меркам компьютерные технологии обработки информации еще очень молоды и находятся в самом начале своего развития. Но, тем не менее, сегодня можно говорить о прошедших поколениях в истории развития вычислительной техники.
Первый этап(ЭВМ первого поколения) — до конца 1950-х гг.
Точкой отсчета эры ЭВМ считают 1946 г., когда был создан электронный цифровой компьютер ENIAС (Electronic Numerical Integrator and Computer). Вычислительные машины этого поколения строились на электронных лампах, потребляющих огромное количество электроэнергии и выделяющих много тепла.
Числа в ЭВМ вводились с помощью перфокарт и набора переключателей, а программа задавалась соединением гнезд на специальных наборных платах. Производительность такой гигантской ЭВМ была ниже, чем современного калькулятора. Широкому использованию этих ЭВМ, кроме дороговизны, препятствовали также низкая надежность, ограниченность их ресурсов и чрезвычайно трудоемкий процесс подготовки, ввода и отладки программ, написанных на языке машинных команд. Основными их пользователями были ученые, решавшие наиболее актуальные научно-технические задачи, связанные с развитием реактивной авиации, ракетостроения и т. д.
Среди известных отечественных машин первого поколения необходимо отметить БЭСМ-1, «Стрела», «Урал», М-20. Типичные характеристики ЭВМ первого поколения (на примере БЭСМ-1, 1953 г.): емкость памяти 2048 слов; быстродействие 7000-8000 опер/с; разрядность 39 разрядов; арифметика двоичная с плавающей запятой; система команд трехадресная; устройство ввода перфолента; количество электронных ламп в аппаратуре около 4000; внешние запоминающие устройства - барабаны по 5120 слов и магнитная лента до 120 000 слов; вывод на быструю цифровую печать 30 строк в минуту. Отечественная ЭВМ М-20 (20 тыс. опер./с) была одной из самых быстродействующих машин первого поколения в мире.
Основной режим использования машин первого поколения состоял в том, что математик, составивший программу, садился за пульт управления машиной и производил необходимые вычисления. Чаще всего работа за пультом была связана с отладкой своей собственной программы — наиболее длительным по времени процессом. При этом уровень математика-программиста определялся его умением быстро находить и исправлять ошибки в своих программах, хорошо ориентироваться за пультом ЭВМ.
В этот период началась интенсивная разработка средств автоматизации программирования, создание входных языков разных уровней, систем обслуживания программ, упрощающих работу на машине и увеличивающих эффективность ее использования.
Второй этап(ЭВМ второго поколения) – до середины 1960-х гг.
Развитие электроники привело к изобретению в 1948 г. нового полупроводникового устройства – транзистора, который заменил лампы. (Создатели транзистора – сотрудники американской фирмы Bell Laboratories физики У. Шокли, У. Браттейн и Дж. Бардин, - за это достижение были удостоены Нобелевской премии). Появление ЭВМ, построенных на транзисторах, привело к уменьшению их габаритов, массы, энергопотребления и стоимости, а также к увеличению их надежности и производительности. Одной из первых транзисторных ЭВМ была созданная в 1955 г. бортовая ЭВМ для межконтинентальной баллистической ракеты ATLAS.
Если с технической точки зрения переход к машинам второго поколения четко очерчен переходом на полупроводники, то со структурной точки зрения ЭВМ второго поколения характеризуются расширенными возможностями по вводу-выводу, увеличенным объемом запоминающих устройств, развитыми системами программирования.
В рамках второго поколения все более четко проявляется разделение ЭВМ на малые, средние и большие, позволившие существенно расширить сферу применения ЭВМ, приступить к созданию автоматизированных систем управления (АСУ) предприятиями, целыми отраслями и технологическими процессами.
Стиль использования ЭВМ второго поколения характерен тем, что теперь математик-программист не допускался в машинный зал, а свою программу, обычно записанную на языке высокого уровня, отдавал в группу обслуживания, которая занималась дальнейшей обработкой его задачи — перфорированием и пропуском на машине.
Среди известных отечественных машин второго поколения необходимо отметить БЭСМ-4, М-220 (200 тыс. опер./с), «Наири», «Мир», «Минск», «Раздан», «Днепр»; Наилучшей отечественной ЭВМ второго поколения считается БЭСМ-6, созданная в 1966 г. Она имела основную и промежуточную память (на магнитных барабанах) объемами соответственно 128 и 512 кбайт, быстродействие порядка 1 млн. опер./с и довольно обширную периферию (магнитные ленты и диски, графопостроители, разнообразные устройства ввода-вывода).
В этот период появились так называемые алгоритмические языки высокого уровня, средства которых допускают описание всей необходимой последовательности вычислительных действий в наглядном, легко воспринимаемом виде. Программа, написанная на алгоритмическом языке, непонятна компьютеру, воспринимающему только язык своих собственных команд. Поэтому специальные программы, которые называются трансляторами, переводят программу с языка высокого уровня в машинный код.
Появился широкий набор библиотечных программ для решения разнообразных математических задач. Были созданы мониторные системы, управляющие режимом трансляции и исполнения программ. Из мониторных систем в дальнейшем выросли современные операционные системы (ОС) (комплексы служебных программ, обеспечивающих лучшее распределение ресурсов ЭВМ при исполнении пользовательских задач).
Первые ОС просто автоматизировали работу оператора ЭВМ, связанную с выполнением задания пользователя: ввод в ЭВМ текста программы, вызов нужного транслятора, вызов необходимых библиотечных программ и т. д. Теперь же вместе с программой и данными в ЭВМ вводится еще и инструкция, где перечисляются этапы обработки и приводится ряд сведений о программе и ее авторе. Затем в ЭВМ стали вводить сразу по нескольку заданий пользователей (пакет заданий), ОС стали распределять ресурсы ЭВМ между этими заданиями — появился мультипрограммный режим обработки.
Третий этап (ЭВМ третьего поколения) — до начала 1970-х гг.
Элементной базой в ЭВМ третьего поколения являются интегральные схемы. Создание технологии производства интегральных схем, состоящих из десятков электронных элементов, образованных в прямоугольной пластине кремния с длиной стороны не более 1 см, позволило увеличить быстродействие и надежность ЭВМ на их основе, а также уменьшить габариты, потребляемую мощность и стоимость ЭВМ.
Машины третьего поколения — это семейство машин с единой архитектурой, т. е. программно-совместимых. Они имеют развитые операционные системы, обладают возможностями мультипрограммирования, т. е. одновременного выполнения нескольких программ. Многие задачи управления памятью, устройствами и ресурсами стала брать на себя операционная система или же непосредственно сама машина.
Примеры машин третьего поколения — семейство IBM-360, IBM-370, PDP-11, отечественные ЕС ЭВМ (единая система ЭВМ), СМ ЭВМ (семейство малых ЭВМ) и др.
Быстродействие машин внутри семейства изменяется от нескольких десятков тысяч до миллионов операций в секунду. Емкость оперативной памяти достигает нескольких сотен тысяч слов.
В этот период широкое распространение получило семейство мини-ЭВМ. Простота обслуживания мини-ЭВМ, их сравнительно низкая стоимость и малые габариты позволяли снабдить этими машинами небольшие коллективы исследователей, разработчиков-экспериментаторов и т. д., т. е. дать ЭВМ прямо в руки пользователей. В начале 1970-х гг. с термином мини-ЭВМ связывали уже два существенно различных типа средств вычислительной техники:
· универсальный блок обработки данных и выдачи управляющих сигналов, серийно выпускаемых для применения в различных специализированных системах контроля и управления;
· универсальную ЭВМ небольших габаритов, проблемно-ориентированную пользователем на решение ограниченного круга задач в рамках одной лаборатории, технического участка и т. д., т. е. задач, в решении которых оказывались заинтересованы 10—20 человек, работавших над одной проблемой.
В период машин третьего поколения произошел крупный сдвиг в области применения ЭВМ. Если раньше ЭВМ использовались в основном для научно-технических расчетов, то в I960—1970-е гг. все больше места стала занимать обработка символьной информации.
Четвертый этап (ЭВМ четвертого поколения) — по настоящее время.
Этот этап условно делят на два периода: первый — до конца 1970-х гг. и второй — с начала 1980-х гг. по настоящее время.
В первый период успехи в развитии электроники привели к созданию больших интегральных схем (БИС), где в одном кристалле размещалось несколько десятков тысяч электронных элементов. Это позволило разработать более дешевые ЭВМ, имеющие большие объемы памяти и скорости выполнения команд: стоимость байта памяти и одной машинной операции резко снизилась. Но так как затраты на программирование почти не сокращались, то на первый план вышла задача экономии человеческих, а не машинных ресурсов.
Разрабатывались новые ОС, позволяющие программистам отлаживать свои программы прямо за дисплеем ЭВМ, что ускоряло разработку программ. Существовавшая в это время концепция первых этапов информационной технологии, согласно которой «процессор выполняет лишь ту часть работы по обработке данных, которую принципиально люди выполнить не могут, т. е. массовый счет», постепенно была заменена на новую: «все, что могут делать машины, должны делать машины; люди выполняют лишь ту часть работы, которую нельзя автоматизировать».
В 1971 г. был изготовлен первый микропроцессор — большая интегральная схема (БИС), в которой полностью размещался процессор ЭВМ простой архитектуры. Стала реальной возможность размещения в одной БИС почти всех электронных устройств несложной по архитектуре ЭВМ, т. е. возможность серийного выпуска простых ЭВМ малой стоимости. Появились дешевые микрокалькуляторы и микроконтроллеры — управляющие устройства, построенные на одной или нескольких БИС, содержащих процессор, память и системы связи с датчиками и исполнительными органами в объекте управления. Программа управления объектами вводилась в память ЭВМ либо при изготовлении, либо непосредственно на предприятии.
В 1970-х гг. стали выпускать и микроЭВМ — универсальные вычислительные системы, состоящие из процессора, памяти, схем сопряжения с устройствами ввода-вывода и тактового генератора, размещенных в одной БИС (однокристальная ЭВМ) или в нескольких БИС, установленных на одной плате (одноплатная ЭВМ). Примерами отечественных ЭВМ этого периода являются СМ-1800, «Электроника 60М» и др.
Второй период характеризуется улучшением технологии производства БИС, что позволило производить дешевые электронные схемы, содержащие миллионы элементов в кристалле, — схемы сверхбольшой степени интеграции (СБИС).
Появилась возможность создать настольный прибор с габаритами телевизора, в котором размещались микроЭВМ, клавиатура, а также схемы сопряжения с малогабаритным печатающим устройством, измерительной аппаратурой, другими ЭВМ и т. п. Благодаря ОС, обеспечивающей простоту общения с этой ЭВМ, большой библиотеки прикладных программ по различным отраслям человеческой деятельности, а также малой стоимости такой персональный компьютер становится необходимой принадлежностью любого специалиста. Кроме функций помощника в решении традиционных задач расчетного характера, персональный компьютер (ПК) способен выполнять функции личного секретаря; помогать в составлении личной картотеки; создавать, хранить, редактировать и размножать тексты и т. п.
С точки зрения структуры машины этого поколения представляют собой многопроцессорные и многомашинные комплексы, работающие на общую память и общее поле внешних устройств. Для этого периода характерно широкое применение систем управления базами данных, компьютерных сетей, систем распределенной обработки данных.
Таким образом, с каждым новым поколением ЭВМ увеличивались быстродействие и надежность их работы при уменьшении стоимости и размеров, совершенствовались устройства ввода и вывода информации. В соответствии с трактовкой компьютера – как технической модели информационной функции человека – устройства ввода приближаются к естественному для человека восприятию информации (зрительному, звуковому), и, следовательно, операция по ее вводу в компьютер становится все более удобной для человека.
Последующие поколения ЭВМ будут представлять, по-видимому, оптоэлектронные ЭВМ с массовым параллелизмом и нейронной структурой — с распределенной сетью большого числа (десятки тысяч) несложных процессоров, моделирующих структуру нейронных биологических систем; произойдет качественный переход от обработки данных к обработке знаний.
2.2 Компьютер как формальный исполнитель алгоритмов
(программ)
Компьютер – это многофункциональное электронное автоматическое устройство для накопления, обработки и передачи информации. На рисунке 2.1 приведена его структурная схема, где стрелками обозначено направление информационных потоков.
Работа компьютера имитирует информационную деятельность человека. Но компьютер – техническое устройство, поэтому для того, чтобы он выполнил определенные действия, им нужно управлять. Компьютер действует как автоматический формальный исполнитель алгоритмов обработки информации. Это главное свойство любого компьютера. Автоматизм в его работе означает, что некоторые свои действия он выполняет без вмешательства человека в соответствии со следующими общими принципами:
- двоичное кодирование информации;
- программное управление работой компьютера;
- хранимая (загружаемая) программа (идея фон Неймана – наряду с данными каждая команда программы размещается в памяти).
Рассмотрим, как в действительности происходит реализация этих принципов и осуществляется формальная автоматическая работа компьютера? Современный компьютер – это единство аппаратных средств (Hardware) и программного обеспечения (Software). Компьютерная программа – это закодированная информация о действиях, которые предписывается выполнять компьютеру, алгоритм для исполнения компьютером, записанный или на языке машинных двоичных кодов или на специальном языке программирования. Чтобы на компьютере можно было решать задачи – нужна совокупность программ – программное обеспечение.
Человек вводит с клавиатуры команды компьютерной программы, написанной им на языке программирования. Команды переводятся в машинный код благодаря программе-переводчику – транслятору с языка программирования на язык машинных кодов. Устройство управления (УУ) процессора воспринимает, считывая из памяти команду за командой, и затем организует их выполнение, используя соответствующие устройства компьютера. Эти устройства произведут действие, напечатают на бумаге, воспримут с клавиатуры, запишут на магнитный диск и т.д.
Для выполнения команд самим процессором в нем предусмотрено арифметико-логическое устройство (АЛУ). Выполнив одну команду, процессор переходит к следующей команде и так до тех пор, пока не встретит команду на окончание работы или команду, которую не сможет выполнить. Он не сможет выполнить команду, если она предназначается устройству, которое не подключено или отсутствует в его системе команд, или содержит синтаксическую ошибку.
Если программа составлена правильно, то компьютер выполнит ее за конечное число шагов и выдаст человеку результат решения задачи.
Выполнение команд осуществляется с помощью электронных схем, реализующих логические функции формальной булевой алгебры.
Человек не объясняет компьютеру свои цели и смысл каждой команды/программы. Очевидно, что компьютер и не сможет понять смысла совершаемых им действий. Более того, компьютер не обладает способностью к анализу результатов, например, относительно их соответствия постановке задачи. Компьютер не сможет обойтись без программы и исходных данных, подготовить которые под силу только человеку. Таким образом, и с этой точки зрения решение задачи компьютером – также формальное исполнение алгоритма ее решения, закодированного и хранимого вместе с данными в оперативной памяти. Поэтому нужно предусматривать точность в задании команд, поручаемых компьютеру для исполнения.
2.3 Основные устройства компьютера и их функции
Несмотря на огромное разнообразие вычислительной техники и ее необычайное быстрое совершенствование, фундаментальные принципы устройства машин во многом остаются неизменными. В частности, начиная с самых первых поколений, любая ЭВМ состоит из следующих основных устройств: процессор, память (внутренняя и внешняя) и устройства ввода и вывода информации. Рассмотрим более подробно назначение каждого из них.
Процессор является самым главным устройством компьютера, в котором собственно и происходит обработка всех видов информации. Другой важной функцией процессора является обеспечение согласованного действия всех узлов, входящих в состав компьютера. Соответственно, наиболее важными частями процессора являются арифметико-логическое устройство (АЛУ) и устройство управления (УУ).
Каждый процессор способен выполнять вполне определенный набор универсальных инструкций, называемых чаще всего машинными командами. Работа ЭВМ состоит в выполнении последовательности таких команд, подготовленных в виде программы. Процессор способен организовать считывание очередной команды, ее анализ и выполнение, а также при необходимости принять данные или отправить результаты их обработки на требуемое устройство. Выбрать, какую инструкцию программы исполнять следующей, также должен сам процессор, причем результат этого выбора часто может зависеть от обрабатываемой в данный момент информации.
Хотя внутри процессора всегда имеется специальные ячейки (регистры) для оперативного хранения обрабатываемых данных и некоторой служебной информации, в нем сознательно не предусмотрено место для хранения программы. Для этой важной цели в компьютере служит другое устройство – память.
Память в целом предназначена для хранения как данных, так и программ их обработки (принцип фон Неймана, упоминавшийся выше).
Начиная с самых первых ЭВМ, память сразу стали делить на внутреннюю и внешнюю. Исторически это было связано с размещением внутри или вне процессорного шкафа.
Под внутренней памятью современного компьютера принято понимать быстродействующую электронную память, расположенную на его системной плате. Сейчас такая память изготавливается на базе самых современных полупроводниковых технологий.
Наиболее существенная часть внутренней памяти называется оперативное запоминающее устройство (ОЗУ). Его главное назначение состоит в том, чтобы хранить данные и программы для решаемых в текущий момент задач. При выключении питания содержимое ОЗУ полностью теряется.